]>
Commit | Line | Data |
---|---|---|
781aab86 | 1 | use crate::ascii::Char as AsciiChar; |
48663c56 XL |
2 | use crate::convert::TryFrom; |
3 | use crate::mem; | |
781aab86 | 4 | use crate::net::{Ipv4Addr, Ipv6Addr}; |
353b0b11 | 5 | use crate::num::NonZeroUsize; |
6a06907d | 6 | use crate::ops::{self, Try}; |
a7813a04 | 7 | |
94222f64 XL |
8 | use super::{ |
9 | FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce, TrustedStep, | |
10 | }; | |
17df50a5 XL |
11 | |
12 | // Safety: All invariants are upheld. | |
13 | macro_rules! unsafe_impl_trusted_step { | |
14 | ($($type:ty)*) => {$( | |
15 | #[unstable(feature = "trusted_step", issue = "85731")] | |
16 | unsafe impl TrustedStep for $type {} | |
17 | )*}; | |
18 | } | |
781aab86 | 19 | unsafe_impl_trusted_step![AsciiChar char i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize Ipv4Addr Ipv6Addr]; |
a7813a04 | 20 | |
f9f354fc | 21 | /// Objects that have a notion of *successor* and *predecessor* operations. |
a7813a04 | 22 | /// |
f9f354fc XL |
23 | /// The *successor* operation moves towards values that compare greater. |
24 | /// The *predecessor* operation moves towards values that compare lesser. | |
f9f354fc | 25 | #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] |
17df50a5 | 26 | pub trait Step: Clone + PartialOrd + Sized { |
f9f354fc XL |
27 | /// Returns the number of *successor* steps required to get from `start` to `end`. |
28 | /// | |
29 | /// Returns `None` if the number of steps would overflow `usize` | |
30 | /// (or is infinite, or if `end` would never be reached). | |
31 | /// | |
32 | /// # Invariants | |
33 | /// | |
34 | /// For any `a`, `b`, and `n`: | |
35 | /// | |
36 | /// * `steps_between(&a, &b) == Some(n)` if and only if `Step::forward_checked(&a, n) == Some(b)` | |
136023e0 | 37 | /// * `steps_between(&a, &b) == Some(n)` if and only if `Step::backward_checked(&b, n) == Some(a)` |
f9f354fc XL |
38 | /// * `steps_between(&a, &b) == Some(n)` only if `a <= b` |
39 | /// * Corollary: `steps_between(&a, &b) == Some(0)` if and only if `a == b` | |
40 | /// * Note that `a <= b` does _not_ imply `steps_between(&a, &b) != None`; | |
3dfed10e | 41 | /// this is the case when it would require more than `usize::MAX` steps to get to `b` |
f9f354fc | 42 | /// * `steps_between(&a, &b) == None` if `a > b` |
041b39d2 | 43 | fn steps_between(start: &Self, end: &Self) -> Option<usize>; |
3157f602 | 44 | |
f9f354fc XL |
45 | /// Returns the value that would be obtained by taking the *successor* |
46 | /// of `self` `count` times. | |
47 | /// | |
48 | /// If this would overflow the range of values supported by `Self`, returns `None`. | |
49 | /// | |
50 | /// # Invariants | |
51 | /// | |
52 | /// For any `a`, `n`, and `m`: | |
53 | /// | |
54 | /// * `Step::forward_checked(a, n).and_then(|x| Step::forward_checked(x, m)) == Step::forward_checked(a, m).and_then(|x| Step::forward_checked(x, n))` | |
60c5eb7d | 55 | /// |
f9f354fc XL |
56 | /// For any `a`, `n`, and `m` where `n + m` does not overflow: |
57 | /// | |
58 | /// * `Step::forward_checked(a, n).and_then(|x| Step::forward_checked(x, m)) == Step::forward_checked(a, n + m)` | |
59 | /// | |
60 | /// For any `a` and `n`: | |
61 | /// | |
62 | /// * `Step::forward_checked(a, n) == (0..n).try_fold(a, |x, _| Step::forward_checked(&x, 1))` | |
63 | /// * Corollary: `Step::forward_checked(&a, 0) == Some(a)` | |
f9f354fc | 64 | fn forward_checked(start: Self, count: usize) -> Option<Self>; |
3157f602 | 65 | |
f9f354fc XL |
66 | /// Returns the value that would be obtained by taking the *successor* |
67 | /// of `self` `count` times. | |
68 | /// | |
69 | /// If this would overflow the range of values supported by `Self`, | |
70 | /// this function is allowed to panic, wrap, or saturate. | |
71 | /// The suggested behavior is to panic when debug assertions are enabled, | |
72 | /// and to wrap or saturate otherwise. | |
73 | /// | |
74 | /// Unsafe code should not rely on the correctness of behavior after overflow. | |
60c5eb7d | 75 | /// |
f9f354fc XL |
76 | /// # Invariants |
77 | /// | |
78 | /// For any `a`, `n`, and `m`, where no overflow occurs: | |
79 | /// | |
80 | /// * `Step::forward(Step::forward(a, n), m) == Step::forward(a, n + m)` | |
81 | /// | |
82 | /// For any `a` and `n`, where no overflow occurs: | |
83 | /// | |
84 | /// * `Step::forward_checked(a, n) == Some(Step::forward(a, n))` | |
85 | /// * `Step::forward(a, n) == (0..n).fold(a, |x, _| Step::forward(x, 1))` | |
86 | /// * Corollary: `Step::forward(a, 0) == a` | |
87 | /// * `Step::forward(a, n) >= a` | |
88 | /// * `Step::backward(Step::forward(a, n), n) == a` | |
f9f354fc XL |
89 | fn forward(start: Self, count: usize) -> Self { |
90 | Step::forward_checked(start, count).expect("overflow in `Step::forward`") | |
91 | } | |
3157f602 | 92 | |
f9f354fc XL |
93 | /// Returns the value that would be obtained by taking the *successor* |
94 | /// of `self` `count` times. | |
95 | /// | |
96 | /// # Safety | |
97 | /// | |
98 | /// It is undefined behavior for this operation to overflow the | |
99 | /// range of values supported by `Self`. If you cannot guarantee that this | |
100 | /// will not overflow, use `forward` or `forward_checked` instead. | |
101 | /// | |
102 | /// # Invariants | |
103 | /// | |
104 | /// For any `a`: | |
105 | /// | |
106 | /// * if there exists `b` such that `b > a`, it is safe to call `Step::forward_unchecked(a, 1)` | |
107 | /// * if there exists `b`, `n` such that `steps_between(&a, &b) == Some(n)`, | |
108 | /// it is safe to call `Step::forward_unchecked(a, m)` for any `m <= n`. | |
109 | /// | |
110 | /// For any `a` and `n`, where no overflow occurs: | |
111 | /// | |
112 | /// * `Step::forward_unchecked(a, n)` is equivalent to `Step::forward(a, n)` | |
f9f354fc XL |
113 | unsafe fn forward_unchecked(start: Self, count: usize) -> Self { |
114 | Step::forward(start, count) | |
115 | } | |
3157f602 | 116 | |
5869c6ff | 117 | /// Returns the value that would be obtained by taking the *predecessor* |
f9f354fc XL |
118 | /// of `self` `count` times. |
119 | /// | |
120 | /// If this would overflow the range of values supported by `Self`, returns `None`. | |
121 | /// | |
122 | /// # Invariants | |
123 | /// | |
124 | /// For any `a`, `n`, and `m`: | |
125 | /// | |
126 | /// * `Step::backward_checked(a, n).and_then(|x| Step::backward_checked(x, m)) == n.checked_add(m).and_then(|x| Step::backward_checked(a, x))` | |
127 | /// * `Step::backward_checked(a, n).and_then(|x| Step::backward_checked(x, m)) == try { Step::backward_checked(a, n.checked_add(m)?) }` | |
128 | /// | |
129 | /// For any `a` and `n`: | |
130 | /// | |
131 | /// * `Step::backward_checked(a, n) == (0..n).try_fold(a, |x, _| Step::backward_checked(&x, 1))` | |
132 | /// * Corollary: `Step::backward_checked(&a, 0) == Some(a)` | |
f9f354fc | 133 | fn backward_checked(start: Self, count: usize) -> Option<Self>; |
041b39d2 | 134 | |
f9f354fc XL |
135 | /// Returns the value that would be obtained by taking the *predecessor* |
136 | /// of `self` `count` times. | |
137 | /// | |
138 | /// If this would overflow the range of values supported by `Self`, | |
139 | /// this function is allowed to panic, wrap, or saturate. | |
140 | /// The suggested behavior is to panic when debug assertions are enabled, | |
141 | /// and to wrap or saturate otherwise. | |
142 | /// | |
143 | /// Unsafe code should not rely on the correctness of behavior after overflow. | |
144 | /// | |
145 | /// # Invariants | |
146 | /// | |
147 | /// For any `a`, `n`, and `m`, where no overflow occurs: | |
148 | /// | |
149 | /// * `Step::backward(Step::backward(a, n), m) == Step::backward(a, n + m)` | |
150 | /// | |
151 | /// For any `a` and `n`, where no overflow occurs: | |
152 | /// | |
153 | /// * `Step::backward_checked(a, n) == Some(Step::backward(a, n))` | |
154 | /// * `Step::backward(a, n) == (0..n).fold(a, |x, _| Step::backward(x, 1))` | |
155 | /// * Corollary: `Step::backward(a, 0) == a` | |
156 | /// * `Step::backward(a, n) <= a` | |
157 | /// * `Step::forward(Step::backward(a, n), n) == a` | |
f9f354fc XL |
158 | fn backward(start: Self, count: usize) -> Self { |
159 | Step::backward_checked(start, count).expect("overflow in `Step::backward`") | |
160 | } | |
dc9dc135 | 161 | |
f9f354fc XL |
162 | /// Returns the value that would be obtained by taking the *predecessor* |
163 | /// of `self` `count` times. | |
164 | /// | |
165 | /// # Safety | |
166 | /// | |
167 | /// It is undefined behavior for this operation to overflow the | |
168 | /// range of values supported by `Self`. If you cannot guarantee that this | |
169 | /// will not overflow, use `backward` or `backward_checked` instead. | |
170 | /// | |
171 | /// # Invariants | |
172 | /// | |
173 | /// For any `a`: | |
174 | /// | |
175 | /// * if there exists `b` such that `b < a`, it is safe to call `Step::backward_unchecked(a, 1)` | |
176 | /// * if there exists `b`, `n` such that `steps_between(&b, &a) == Some(n)`, | |
177 | /// it is safe to call `Step::backward_unchecked(a, m)` for any `m <= n`. | |
178 | /// | |
179 | /// For any `a` and `n`, where no overflow occurs: | |
180 | /// | |
181 | /// * `Step::backward_unchecked(a, n)` is equivalent to `Step::backward(a, n)` | |
f9f354fc XL |
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")] | |
17df50a5 | 240 | impl Step for $u_narrower { |
f9f354fc XL |
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 | 271 | #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] |
17df50a5 | 272 | impl Step for $i_narrower { |
f9f354fc XL |
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 | |
94222f64 | 282 | // the difference that might not fit inside the range of isize. |
f9f354fc XL |
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 | 335 | #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] |
17df50a5 | 336 | impl Step for $u_wider { |
f9f354fc XL |
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 | 360 | #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] |
17df50a5 | 361 | impl Step for $i_wider { |
f9f354fc XL |
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 | 410 | #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] |
17df50a5 | 411 | impl Step for char { |
f9f354fc XL |
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 | |
781aab86 FG |
489 | #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] |
490 | impl Step for AsciiChar { | |
491 | #[inline] | |
492 | fn steps_between(&start: &AsciiChar, &end: &AsciiChar) -> Option<usize> { | |
493 | Step::steps_between(&start.to_u8(), &end.to_u8()) | |
494 | } | |
495 | ||
496 | #[inline] | |
497 | fn forward_checked(start: AsciiChar, count: usize) -> Option<AsciiChar> { | |
498 | let end = Step::forward_checked(start.to_u8(), count)?; | |
499 | AsciiChar::from_u8(end) | |
500 | } | |
501 | ||
502 | #[inline] | |
503 | fn backward_checked(start: AsciiChar, count: usize) -> Option<AsciiChar> { | |
504 | let end = Step::backward_checked(start.to_u8(), count)?; | |
505 | ||
506 | // SAFETY: Values below that of a valid ASCII character are also valid ASCII | |
507 | Some(unsafe { AsciiChar::from_u8_unchecked(end) }) | |
508 | } | |
509 | ||
510 | #[inline] | |
511 | unsafe fn forward_unchecked(start: AsciiChar, count: usize) -> AsciiChar { | |
512 | // SAFETY: Caller asserts that result is a valid ASCII character, | |
513 | // and therefore it is a valid u8. | |
514 | let end = unsafe { Step::forward_unchecked(start.to_u8(), count) }; | |
515 | ||
516 | // SAFETY: Caller asserts that result is a valid ASCII character. | |
517 | unsafe { AsciiChar::from_u8_unchecked(end) } | |
518 | } | |
519 | ||
520 | #[inline] | |
521 | unsafe fn backward_unchecked(start: AsciiChar, count: usize) -> AsciiChar { | |
522 | // SAFETY: Caller asserts that result is a valid ASCII character, | |
523 | // and therefore it is a valid u8. | |
524 | let end = unsafe { Step::backward_unchecked(start.to_u8(), count) }; | |
525 | ||
526 | // SAFETY: Caller asserts that result is a valid ASCII character. | |
527 | unsafe { AsciiChar::from_u8_unchecked(end) } | |
528 | } | |
529 | } | |
530 | ||
531 | #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] | |
532 | impl Step for Ipv4Addr { | |
533 | #[inline] | |
534 | fn steps_between(&start: &Ipv4Addr, &end: &Ipv4Addr) -> Option<usize> { | |
535 | u32::steps_between(&start.to_bits(), &end.to_bits()) | |
536 | } | |
537 | ||
538 | #[inline] | |
539 | fn forward_checked(start: Ipv4Addr, count: usize) -> Option<Ipv4Addr> { | |
540 | u32::forward_checked(start.to_bits(), count).map(Ipv4Addr::from_bits) | |
541 | } | |
542 | ||
543 | #[inline] | |
544 | fn backward_checked(start: Ipv4Addr, count: usize) -> Option<Ipv4Addr> { | |
545 | u32::backward_checked(start.to_bits(), count).map(Ipv4Addr::from_bits) | |
546 | } | |
547 | ||
548 | #[inline] | |
549 | unsafe fn forward_unchecked(start: Ipv4Addr, count: usize) -> Ipv4Addr { | |
550 | // SAFETY: Since u32 and Ipv4Addr are losslessly convertible, | |
551 | // this is as safe as the u32 version. | |
552 | Ipv4Addr::from_bits(unsafe { u32::forward_unchecked(start.to_bits(), count) }) | |
553 | } | |
554 | ||
555 | #[inline] | |
556 | unsafe fn backward_unchecked(start: Ipv4Addr, count: usize) -> Ipv4Addr { | |
557 | // SAFETY: Since u32 and Ipv4Addr are losslessly convertible, | |
558 | // this is as safe as the u32 version. | |
559 | Ipv4Addr::from_bits(unsafe { u32::backward_unchecked(start.to_bits(), count) }) | |
560 | } | |
561 | } | |
562 | ||
563 | #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] | |
564 | impl Step for Ipv6Addr { | |
565 | #[inline] | |
566 | fn steps_between(&start: &Ipv6Addr, &end: &Ipv6Addr) -> Option<usize> { | |
567 | u128::steps_between(&start.to_bits(), &end.to_bits()) | |
568 | } | |
569 | ||
570 | #[inline] | |
571 | fn forward_checked(start: Ipv6Addr, count: usize) -> Option<Ipv6Addr> { | |
572 | u128::forward_checked(start.to_bits(), count).map(Ipv6Addr::from_bits) | |
573 | } | |
574 | ||
575 | #[inline] | |
576 | fn backward_checked(start: Ipv6Addr, count: usize) -> Option<Ipv6Addr> { | |
577 | u128::backward_checked(start.to_bits(), count).map(Ipv6Addr::from_bits) | |
578 | } | |
579 | ||
580 | #[inline] | |
581 | unsafe fn forward_unchecked(start: Ipv6Addr, count: usize) -> Ipv6Addr { | |
582 | // SAFETY: Since u128 and Ipv6Addr are losslessly convertible, | |
583 | // this is as safe as the u128 version. | |
584 | Ipv6Addr::from_bits(unsafe { u128::forward_unchecked(start.to_bits(), count) }) | |
585 | } | |
586 | ||
587 | #[inline] | |
588 | unsafe fn backward_unchecked(start: Ipv6Addr, count: usize) -> Ipv6Addr { | |
589 | // SAFETY: Since u128 and Ipv6Addr are losslessly convertible, | |
590 | // this is as safe as the u128 version. | |
591 | Ipv6Addr::from_bits(unsafe { u128::backward_unchecked(start.to_bits(), count) }) | |
592 | } | |
593 | } | |
594 | ||
a7813a04 XL |
595 | macro_rules! range_exact_iter_impl { |
596 | ($($t:ty)*) => ($( | |
597 | #[stable(feature = "rust1", since = "1.0.0")] | |
598 | impl ExactSizeIterator for ops::Range<$t> { } | |
c30ab7b3 SL |
599 | )*) |
600 | } | |
a7813a04 | 601 | |
cdc7bbd5 XL |
602 | /// Safety: This macro must only be used on types that are `Copy` and result in ranges |
603 | /// which have an exact `size_hint()` where the upper bound must not be `None`. | |
604 | macro_rules! unsafe_range_trusted_random_access_impl { | |
605 | ($($t:ty)*) => ($( | |
606 | #[doc(hidden)] | |
607 | #[unstable(feature = "trusted_random_access", issue = "none")] | |
94222f64 XL |
608 | unsafe impl TrustedRandomAccess for ops::Range<$t> {} |
609 | ||
610 | #[doc(hidden)] | |
611 | #[unstable(feature = "trusted_random_access", issue = "none")] | |
612 | unsafe impl TrustedRandomAccessNoCoerce for ops::Range<$t> { | |
cdc7bbd5 XL |
613 | const MAY_HAVE_SIDE_EFFECT: bool = false; |
614 | } | |
615 | )*) | |
616 | } | |
617 | ||
c30ab7b3 SL |
618 | macro_rules! range_incl_exact_iter_impl { |
619 | ($($t:ty)*) => ($( | |
0531ce1d | 620 | #[stable(feature = "inclusive_range", since = "1.26.0")] |
a7813a04 XL |
621 | impl ExactSizeIterator for ops::RangeInclusive<$t> { } |
622 | )*) | |
623 | } | |
624 | ||
17df50a5 XL |
625 | /// Specialization implementations for `Range`. |
626 | trait RangeIteratorImpl { | |
627 | type Item; | |
628 | ||
629 | // Iterator | |
630 | fn spec_next(&mut self) -> Option<Self::Item>; | |
631 | fn spec_nth(&mut self, n: usize) -> Option<Self::Item>; | |
353b0b11 | 632 | fn spec_advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize>; |
17df50a5 XL |
633 | |
634 | // DoubleEndedIterator | |
635 | fn spec_next_back(&mut self) -> Option<Self::Item>; | |
636 | fn spec_nth_back(&mut self, n: usize) -> Option<Self::Item>; | |
353b0b11 | 637 | fn spec_advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize>; |
17df50a5 XL |
638 | } |
639 | ||
640 | impl<A: Step> RangeIteratorImpl for ops::Range<A> { | |
a7813a04 XL |
641 | type Item = A; |
642 | ||
643 | #[inline] | |
17df50a5 | 644 | default fn spec_next(&mut self) -> Option<A> { |
a7813a04 | 645 | if self.start < self.end { |
17df50a5 XL |
646 | let n = |
647 | Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld"); | |
f9f354fc | 648 | Some(mem::replace(&mut self.start, n)) |
a7813a04 XL |
649 | } else { |
650 | None | |
651 | } | |
652 | } | |
653 | ||
654 | #[inline] | |
17df50a5 XL |
655 | default fn spec_nth(&mut self, n: usize) -> Option<A> { |
656 | if let Some(plus_n) = Step::forward_checked(self.start.clone(), n) { | |
657 | if plus_n < self.end { | |
658 | self.start = | |
659 | Step::forward_checked(plus_n.clone(), 1).expect("`Step` invariants not upheld"); | |
660 | return Some(plus_n); | |
661 | } | |
662 | } | |
663 | ||
664 | self.start = self.end.clone(); | |
665 | None | |
666 | } | |
667 | ||
c295e0f8 | 668 | #[inline] |
353b0b11 | 669 | default fn spec_advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> { |
c295e0f8 XL |
670 | let available = if self.start <= self.end { |
671 | Step::steps_between(&self.start, &self.end).unwrap_or(usize::MAX) | |
672 | } else { | |
673 | 0 | |
674 | }; | |
675 | ||
676 | let taken = available.min(n); | |
677 | ||
678 | self.start = | |
679 | Step::forward_checked(self.start.clone(), taken).expect("`Step` invariants not upheld"); | |
680 | ||
353b0b11 | 681 | NonZeroUsize::new(n - taken).map_or(Ok(()), Err) |
c295e0f8 XL |
682 | } |
683 | ||
17df50a5 XL |
684 | #[inline] |
685 | default fn spec_next_back(&mut self) -> Option<A> { | |
f9f354fc | 686 | if self.start < self.end { |
17df50a5 XL |
687 | self.end = |
688 | Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld"); | |
689 | Some(self.end.clone()) | |
f9f354fc | 690 | } else { |
17df50a5 | 691 | None |
a7813a04 XL |
692 | } |
693 | } | |
041b39d2 XL |
694 | |
695 | #[inline] | |
17df50a5 XL |
696 | default fn spec_nth_back(&mut self, n: usize) -> Option<A> { |
697 | if let Some(minus_n) = Step::backward_checked(self.end.clone(), n) { | |
698 | if minus_n > self.start { | |
699 | self.end = | |
700 | Step::backward_checked(minus_n, 1).expect("`Step` invariants not upheld"); | |
701 | return Some(self.end.clone()); | |
702 | } | |
703 | } | |
704 | ||
705 | self.end = self.start.clone(); | |
706 | None | |
707 | } | |
c295e0f8 XL |
708 | |
709 | #[inline] | |
353b0b11 | 710 | default fn spec_advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> { |
c295e0f8 XL |
711 | let available = if self.start <= self.end { |
712 | Step::steps_between(&self.start, &self.end).unwrap_or(usize::MAX) | |
713 | } else { | |
714 | 0 | |
715 | }; | |
716 | ||
717 | let taken = available.min(n); | |
718 | ||
719 | self.end = | |
720 | Step::backward_checked(self.end.clone(), taken).expect("`Step` invariants not upheld"); | |
721 | ||
353b0b11 | 722 | NonZeroUsize::new(n - taken).map_or(Ok(()), Err) |
c295e0f8 | 723 | } |
17df50a5 XL |
724 | } |
725 | ||
726 | impl<T: TrustedStep> RangeIteratorImpl for ops::Range<T> { | |
727 | #[inline] | |
728 | fn spec_next(&mut self) -> Option<T> { | |
729 | if self.start < self.end { | |
fe692bf9 | 730 | let old = self.start; |
17df50a5 | 731 | // SAFETY: just checked precondition |
fe692bf9 FG |
732 | self.start = unsafe { Step::forward_unchecked(old, 1) }; |
733 | Some(old) | |
17df50a5 XL |
734 | } else { |
735 | None | |
736 | } | |
737 | } | |
738 | ||
739 | #[inline] | |
740 | fn spec_nth(&mut self, n: usize) -> Option<T> { | |
fe692bf9 | 741 | if let Some(plus_n) = Step::forward_checked(self.start, n) { |
041b39d2 | 742 | if plus_n < self.end { |
f035d41b | 743 | // SAFETY: just checked precondition |
fe692bf9 | 744 | self.start = unsafe { Step::forward_unchecked(plus_n, 1) }; |
dfeec247 | 745 | return Some(plus_n); |
041b39d2 XL |
746 | } |
747 | } | |
748 | ||
fe692bf9 | 749 | self.start = self.end; |
041b39d2 XL |
750 | None |
751 | } | |
2c00a5a8 | 752 | |
c295e0f8 | 753 | #[inline] |
353b0b11 | 754 | fn spec_advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> { |
c295e0f8 XL |
755 | let available = if self.start <= self.end { |
756 | Step::steps_between(&self.start, &self.end).unwrap_or(usize::MAX) | |
757 | } else { | |
758 | 0 | |
759 | }; | |
760 | ||
761 | let taken = available.min(n); | |
762 | ||
763 | // SAFETY: the conditions above ensure that the count is in bounds. If start <= end | |
764 | // then steps_between either returns a bound to which we clamp or returns None which | |
765 | // together with the initial inequality implies more than usize::MAX steps. | |
766 | // Otherwise 0 is returned which always safe to use. | |
fe692bf9 | 767 | self.start = unsafe { Step::forward_unchecked(self.start, taken) }; |
c295e0f8 | 768 | |
353b0b11 | 769 | NonZeroUsize::new(n - taken).map_or(Ok(()), Err) |
c295e0f8 XL |
770 | } |
771 | ||
17df50a5 XL |
772 | #[inline] |
773 | fn spec_next_back(&mut self) -> Option<T> { | |
774 | if self.start < self.end { | |
775 | // SAFETY: just checked precondition | |
fe692bf9 FG |
776 | self.end = unsafe { Step::backward_unchecked(self.end, 1) }; |
777 | Some(self.end) | |
17df50a5 XL |
778 | } else { |
779 | None | |
780 | } | |
781 | } | |
782 | ||
783 | #[inline] | |
784 | fn spec_nth_back(&mut self, n: usize) -> Option<T> { | |
fe692bf9 | 785 | if let Some(minus_n) = Step::backward_checked(self.end, n) { |
17df50a5 XL |
786 | if minus_n > self.start { |
787 | // SAFETY: just checked precondition | |
788 | self.end = unsafe { Step::backward_unchecked(minus_n, 1) }; | |
fe692bf9 | 789 | return Some(self.end); |
17df50a5 XL |
790 | } |
791 | } | |
792 | ||
fe692bf9 | 793 | self.end = self.start; |
17df50a5 XL |
794 | None |
795 | } | |
c295e0f8 XL |
796 | |
797 | #[inline] | |
353b0b11 | 798 | fn spec_advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> { |
c295e0f8 XL |
799 | let available = if self.start <= self.end { |
800 | Step::steps_between(&self.start, &self.end).unwrap_or(usize::MAX) | |
801 | } else { | |
802 | 0 | |
803 | }; | |
804 | ||
805 | let taken = available.min(n); | |
806 | ||
807 | // SAFETY: same as the spec_advance_by() implementation | |
fe692bf9 | 808 | self.end = unsafe { Step::backward_unchecked(self.end, taken) }; |
c295e0f8 | 809 | |
353b0b11 | 810 | NonZeroUsize::new(n - taken).map_or(Ok(()), Err) |
c295e0f8 | 811 | } |
17df50a5 XL |
812 | } |
813 | ||
814 | #[stable(feature = "rust1", since = "1.0.0")] | |
815 | impl<A: Step> Iterator for ops::Range<A> { | |
816 | type Item = A; | |
817 | ||
818 | #[inline] | |
819 | fn next(&mut self) -> Option<A> { | |
820 | self.spec_next() | |
821 | } | |
822 | ||
823 | #[inline] | |
824 | fn size_hint(&self) -> (usize, Option<usize>) { | |
825 | if self.start < self.end { | |
826 | let hint = Step::steps_between(&self.start, &self.end); | |
827 | (hint.unwrap_or(usize::MAX), hint) | |
828 | } else { | |
829 | (0, Some(0)) | |
830 | } | |
831 | } | |
832 | ||
781aab86 FG |
833 | #[inline] |
834 | fn count(self) -> usize { | |
835 | if self.start < self.end { | |
836 | Step::steps_between(&self.start, &self.end).expect("count overflowed usize") | |
837 | } else { | |
838 | 0 | |
839 | } | |
840 | } | |
841 | ||
17df50a5 XL |
842 | #[inline] |
843 | fn nth(&mut self, n: usize) -> Option<A> { | |
844 | self.spec_nth(n) | |
845 | } | |
846 | ||
2c00a5a8 XL |
847 | #[inline] |
848 | fn last(mut self) -> Option<A> { | |
849 | self.next_back() | |
850 | } | |
851 | ||
852 | #[inline] | |
49aad941 FG |
853 | fn min(mut self) -> Option<A> |
854 | where | |
855 | A: Ord, | |
856 | { | |
2c00a5a8 XL |
857 | self.next() |
858 | } | |
859 | ||
860 | #[inline] | |
49aad941 FG |
861 | fn max(mut self) -> Option<A> |
862 | where | |
863 | A: Ord, | |
864 | { | |
2c00a5a8 XL |
865 | self.next_back() |
866 | } | |
cdc7bbd5 | 867 | |
c295e0f8 XL |
868 | #[inline] |
869 | fn is_sorted(self) -> bool { | |
870 | true | |
871 | } | |
872 | ||
873 | #[inline] | |
353b0b11 | 874 | fn advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> { |
c295e0f8 XL |
875 | self.spec_advance_by(n) |
876 | } | |
877 | ||
cdc7bbd5 XL |
878 | #[inline] |
879 | unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item | |
880 | where | |
94222f64 | 881 | Self: TrustedRandomAccessNoCoerce, |
cdc7bbd5 | 882 | { |
9c376795 | 883 | // SAFETY: The TrustedRandomAccess contract requires that callers only pass an index |
cdc7bbd5 XL |
884 | // that is in bounds. |
885 | // Additionally Self: TrustedRandomAccess is only implemented for Copy types | |
886 | // which means even repeated reads of the same index would be safe. | |
887 | unsafe { Step::forward_unchecked(self.start.clone(), idx) } | |
888 | } | |
a7813a04 XL |
889 | } |
890 | ||
c30ab7b3 | 891 | // These macros generate `ExactSizeIterator` impls for various range types. |
c30ab7b3 | 892 | // |
f9f354fc XL |
893 | // * `ExactSizeIterator::len` is required to always return an exact `usize`, |
894 | // so no range can be longer than `usize::MAX`. | |
895 | // * For integer types in `Range<_>` this is the case for types narrower than or as wide as `usize`. | |
896 | // For integer types in `RangeInclusive<_>` | |
897 | // this is the case for types *strictly narrower* than `usize` | |
898 | // since e.g. `(0..=u64::MAX).len()` would be `u64::MAX + 1`. | |
899 | range_exact_iter_impl! { | |
900 | usize u8 u16 | |
901 | isize i8 i16 | |
902 | ||
a2a8927a | 903 | // These are incorrect per the reasoning above, |
f9f354fc XL |
904 | // but removing them would be a breaking change as they were stabilized in Rust 1.0.0. |
905 | // So e.g. `(0..66_000_u32).len()` for example will compile without error or warnings | |
906 | // on 16-bit platforms, but continue to give a wrong result. | |
907 | u32 | |
908 | i32 | |
909 | } | |
cdc7bbd5 XL |
910 | |
911 | unsafe_range_trusted_random_access_impl! { | |
912 | usize u8 u16 | |
913 | isize i8 i16 | |
914 | } | |
915 | ||
916 | #[cfg(target_pointer_width = "32")] | |
917 | unsafe_range_trusted_random_access_impl! { | |
918 | u32 i32 | |
919 | } | |
920 | ||
921 | #[cfg(target_pointer_width = "64")] | |
922 | unsafe_range_trusted_random_access_impl! { | |
923 | u32 i32 | |
924 | u64 i64 | |
925 | } | |
926 | ||
f9f354fc XL |
927 | range_incl_exact_iter_impl! { |
928 | u8 | |
929 | i8 | |
930 | ||
a2a8927a | 931 | // These are incorrect per the reasoning above, |
f9f354fc XL |
932 | // but removing them would be a breaking change as they were stabilized in Rust 1.26.0. |
933 | // So e.g. `(0..=u16::MAX).len()` for example will compile without error or warnings | |
934 | // on 16-bit platforms, but continue to give a wrong result. | |
935 | u16 | |
936 | i16 | |
937 | } | |
a7813a04 XL |
938 | |
939 | #[stable(feature = "rust1", since = "1.0.0")] | |
041b39d2 | 940 | impl<A: Step> DoubleEndedIterator for ops::Range<A> { |
a7813a04 XL |
941 | #[inline] |
942 | fn next_back(&mut self) -> Option<A> { | |
17df50a5 | 943 | self.spec_next_back() |
a7813a04 | 944 | } |
dc9dc135 XL |
945 | |
946 | #[inline] | |
947 | fn nth_back(&mut self, n: usize) -> Option<A> { | |
17df50a5 | 948 | self.spec_nth_back(n) |
dc9dc135 | 949 | } |
c295e0f8 XL |
950 | |
951 | #[inline] | |
353b0b11 | 952 | fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> { |
c295e0f8 XL |
953 | self.spec_advance_back_by(n) |
954 | } | |
a7813a04 XL |
955 | } |
956 | ||
17df50a5 XL |
957 | // Safety: |
958 | // The following invariants for `Step::steps_between` exist: | |
959 | // | |
960 | // > * `steps_between(&a, &b) == Some(n)` only if `a <= b` | |
961 | // > * Note that `a <= b` does _not_ imply `steps_between(&a, &b) != None`; | |
962 | // > this is the case when it would require more than `usize::MAX` steps to | |
963 | // > get to `b` | |
964 | // > * `steps_between(&a, &b) == None` if `a > b` | |
965 | // | |
966 | // The first invariant is what is generally required for `TrustedLen` to be | |
967 | // sound. The note addendum satisfies an additional `TrustedLen` invariant. | |
968 | // | |
969 | // > The upper bound must only be `None` if the actual iterator length is larger | |
970 | // > than `usize::MAX` | |
971 | // | |
972 | // The second invariant logically follows the first so long as the `PartialOrd` | |
973 | // implementation is correct; regardless it is explicitly stated. If `a < b` | |
974 | // then `(0, Some(0))` is returned by `ops::Range<A: Step>::size_hint`. As such | |
975 | // the second invariant is upheld. | |
f9f354fc | 976 | #[unstable(feature = "trusted_len", issue = "37572")] |
17df50a5 | 977 | unsafe impl<A: TrustedStep> TrustedLen for ops::Range<A> {} |
f9f354fc | 978 | |
0531ce1d | 979 | #[stable(feature = "fused", since = "1.26.0")] |
041b39d2 | 980 | impl<A: Step> FusedIterator for ops::Range<A> {} |
9e0c209e | 981 | |
a7813a04 | 982 | #[stable(feature = "rust1", since = "1.0.0")] |
041b39d2 | 983 | impl<A: Step> Iterator for ops::RangeFrom<A> { |
a7813a04 XL |
984 | type Item = A; |
985 | ||
986 | #[inline] | |
987 | fn next(&mut self) -> Option<A> { | |
f9f354fc XL |
988 | let n = Step::forward(self.start.clone(), 1); |
989 | Some(mem::replace(&mut self.start, n)) | |
a7813a04 | 990 | } |
7cac9316 XL |
991 | |
992 | #[inline] | |
993 | fn size_hint(&self) -> (usize, Option<usize>) { | |
994 | (usize::MAX, None) | |
995 | } | |
041b39d2 XL |
996 | |
997 | #[inline] | |
998 | fn nth(&mut self, n: usize) -> Option<A> { | |
f9f354fc XL |
999 | let plus_n = Step::forward(self.start.clone(), n); |
1000 | self.start = Step::forward(plus_n.clone(), 1); | |
041b39d2 XL |
1001 | Some(plus_n) |
1002 | } | |
a7813a04 XL |
1003 | } |
1004 | ||
17df50a5 XL |
1005 | // Safety: See above implementation for `ops::Range<A>` |
1006 | #[unstable(feature = "trusted_len", issue = "37572")] | |
1007 | unsafe impl<A: TrustedStep> TrustedLen for ops::RangeFrom<A> {} | |
1008 | ||
0531ce1d | 1009 | #[stable(feature = "fused", since = "1.26.0")] |
041b39d2 | 1010 | impl<A: Step> FusedIterator for ops::RangeFrom<A> {} |
9e0c209e | 1011 | |
17df50a5 XL |
1012 | trait RangeInclusiveIteratorImpl { |
1013 | type Item; | |
2c00a5a8 | 1014 | |
17df50a5 XL |
1015 | // Iterator |
1016 | fn spec_next(&mut self) -> Option<Self::Item>; | |
1017 | fn spec_try_fold<B, F, R>(&mut self, init: B, f: F) -> R | |
1018 | where | |
1019 | Self: Sized, | |
1020 | F: FnMut(B, Self::Item) -> R, | |
1021 | R: Try<Output = B>; | |
1022 | ||
1023 | // DoubleEndedIterator | |
1024 | fn spec_next_back(&mut self) -> Option<Self::Item>; | |
1025 | fn spec_try_rfold<B, F, R>(&mut self, init: B, f: F) -> R | |
1026 | where | |
1027 | Self: Sized, | |
1028 | F: FnMut(B, Self::Item) -> R, | |
1029 | R: Try<Output = B>; | |
1030 | } | |
1031 | ||
1032 | impl<A: Step> RangeInclusiveIteratorImpl for ops::RangeInclusive<A> { | |
a7813a04 XL |
1033 | type Item = A; |
1034 | ||
1035 | #[inline] | |
17df50a5 XL |
1036 | default fn spec_next(&mut self) -> Option<A> { |
1037 | if self.is_empty() { | |
1038 | return None; | |
1039 | } | |
1040 | let is_iterating = self.start < self.end; | |
1041 | Some(if is_iterating { | |
1042 | let n = | |
1043 | Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld"); | |
1044 | mem::replace(&mut self.start, n) | |
1045 | } else { | |
1046 | self.exhausted = true; | |
1047 | self.start.clone() | |
1048 | }) | |
1049 | } | |
1050 | ||
1051 | #[inline] | |
1052 | default fn spec_try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R | |
1053 | where | |
1054 | Self: Sized, | |
1055 | F: FnMut(B, A) -> R, | |
1056 | R: Try<Output = B>, | |
1057 | { | |
1058 | if self.is_empty() { | |
1059 | return try { init }; | |
1060 | } | |
1061 | ||
1062 | let mut accum = init; | |
1063 | ||
1064 | while self.start < self.end { | |
1065 | let n = | |
1066 | Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld"); | |
1067 | let n = mem::replace(&mut self.start, n); | |
1068 | accum = f(accum, n)?; | |
1069 | } | |
1070 | ||
1071 | self.exhausted = true; | |
1072 | ||
1073 | if self.start == self.end { | |
1074 | accum = f(accum, self.start.clone())?; | |
1075 | } | |
1076 | ||
1077 | try { accum } | |
1078 | } | |
1079 | ||
1080 | #[inline] | |
1081 | default fn spec_next_back(&mut self) -> Option<A> { | |
1082 | if self.is_empty() { | |
1083 | return None; | |
1084 | } | |
1085 | let is_iterating = self.start < self.end; | |
1086 | Some(if is_iterating { | |
1087 | let n = | |
1088 | Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld"); | |
1089 | mem::replace(&mut self.end, n) | |
1090 | } else { | |
1091 | self.exhausted = true; | |
1092 | self.end.clone() | |
1093 | }) | |
1094 | } | |
1095 | ||
1096 | #[inline] | |
1097 | default fn spec_try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R | |
1098 | where | |
1099 | Self: Sized, | |
1100 | F: FnMut(B, A) -> R, | |
1101 | R: Try<Output = B>, | |
1102 | { | |
1103 | if self.is_empty() { | |
1104 | return try { init }; | |
1105 | } | |
1106 | ||
1107 | let mut accum = init; | |
1108 | ||
1109 | while self.start < self.end { | |
1110 | let n = | |
1111 | Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld"); | |
1112 | let n = mem::replace(&mut self.end, n); | |
1113 | accum = f(accum, n)?; | |
1114 | } | |
1115 | ||
1116 | self.exhausted = true; | |
1117 | ||
1118 | if self.start == self.end { | |
1119 | accum = f(accum, self.start.clone())?; | |
1120 | } | |
1121 | ||
1122 | try { accum } | |
1123 | } | |
1124 | } | |
1125 | ||
1126 | impl<T: TrustedStep> RangeInclusiveIteratorImpl for ops::RangeInclusive<T> { | |
1127 | #[inline] | |
1128 | fn spec_next(&mut self) -> Option<T> { | |
74b04a01 | 1129 | if self.is_empty() { |
8faf50e0 | 1130 | return None; |
a7813a04 | 1131 | } |
8faf50e0 | 1132 | let is_iterating = self.start < self.end; |
8faf50e0 | 1133 | Some(if is_iterating { |
f9f354fc | 1134 | // SAFETY: just checked precondition |
f9f354fc | 1135 | let n = unsafe { Step::forward_unchecked(self.start.clone(), 1) }; |
8faf50e0 XL |
1136 | mem::replace(&mut self.start, n) |
1137 | } else { | |
74b04a01 | 1138 | self.exhausted = true; |
8faf50e0 XL |
1139 | self.start.clone() |
1140 | }) | |
a7813a04 XL |
1141 | } |
1142 | ||
17df50a5 XL |
1143 | #[inline] |
1144 | fn spec_try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R | |
1145 | where | |
1146 | Self: Sized, | |
1147 | F: FnMut(B, T) -> R, | |
1148 | R: Try<Output = B>, | |
1149 | { | |
1150 | if self.is_empty() { | |
1151 | return try { init }; | |
1152 | } | |
1153 | ||
1154 | let mut accum = init; | |
1155 | ||
1156 | while self.start < self.end { | |
1157 | // SAFETY: just checked precondition | |
1158 | let n = unsafe { Step::forward_unchecked(self.start.clone(), 1) }; | |
1159 | let n = mem::replace(&mut self.start, n); | |
1160 | accum = f(accum, n)?; | |
1161 | } | |
1162 | ||
1163 | self.exhausted = true; | |
1164 | ||
1165 | if self.start == self.end { | |
1166 | accum = f(accum, self.start.clone())?; | |
1167 | } | |
1168 | ||
1169 | try { accum } | |
1170 | } | |
1171 | ||
1172 | #[inline] | |
1173 | fn spec_next_back(&mut self) -> Option<T> { | |
1174 | if self.is_empty() { | |
1175 | return None; | |
1176 | } | |
1177 | let is_iterating = self.start < self.end; | |
1178 | Some(if is_iterating { | |
1179 | // SAFETY: just checked precondition | |
1180 | let n = unsafe { Step::backward_unchecked(self.end.clone(), 1) }; | |
1181 | mem::replace(&mut self.end, n) | |
1182 | } else { | |
1183 | self.exhausted = true; | |
1184 | self.end.clone() | |
1185 | }) | |
1186 | } | |
1187 | ||
1188 | #[inline] | |
1189 | fn spec_try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R | |
1190 | where | |
1191 | Self: Sized, | |
1192 | F: FnMut(B, T) -> R, | |
1193 | R: Try<Output = B>, | |
1194 | { | |
1195 | if self.is_empty() { | |
1196 | return try { init }; | |
1197 | } | |
1198 | ||
1199 | let mut accum = init; | |
1200 | ||
1201 | while self.start < self.end { | |
1202 | // SAFETY: just checked precondition | |
1203 | let n = unsafe { Step::backward_unchecked(self.end.clone(), 1) }; | |
1204 | let n = mem::replace(&mut self.end, n); | |
1205 | accum = f(accum, n)?; | |
1206 | } | |
1207 | ||
1208 | self.exhausted = true; | |
1209 | ||
1210 | if self.start == self.end { | |
1211 | accum = f(accum, self.start.clone())?; | |
1212 | } | |
1213 | ||
1214 | try { accum } | |
1215 | } | |
1216 | } | |
1217 | ||
1218 | #[stable(feature = "inclusive_range", since = "1.26.0")] | |
1219 | impl<A: Step> Iterator for ops::RangeInclusive<A> { | |
1220 | type Item = A; | |
1221 | ||
1222 | #[inline] | |
1223 | fn next(&mut self) -> Option<A> { | |
1224 | self.spec_next() | |
1225 | } | |
1226 | ||
a7813a04 XL |
1227 | #[inline] |
1228 | fn size_hint(&self) -> (usize, Option<usize>) { | |
8faf50e0 | 1229 | if self.is_empty() { |
7cac9316 XL |
1230 | return (0, Some(0)); |
1231 | } | |
a7813a04 | 1232 | |
041b39d2 | 1233 | match Step::steps_between(&self.start, &self.end) { |
7cac9316 | 1234 | Some(hint) => (hint.saturating_add(1), hint.checked_add(1)), |
532ac7d7 | 1235 | None => (usize::MAX, None), |
a7813a04 XL |
1236 | } |
1237 | } | |
041b39d2 | 1238 | |
781aab86 FG |
1239 | #[inline] |
1240 | fn count(self) -> usize { | |
1241 | if self.is_empty() { | |
1242 | return 0; | |
1243 | } | |
1244 | ||
1245 | Step::steps_between(&self.start, &self.end) | |
1246 | .and_then(|steps| steps.checked_add(1)) | |
1247 | .expect("count overflowed usize") | |
1248 | } | |
1249 | ||
041b39d2 XL |
1250 | #[inline] |
1251 | fn nth(&mut self, n: usize) -> Option<A> { | |
74b04a01 | 1252 | if self.is_empty() { |
8faf50e0 XL |
1253 | return None; |
1254 | } | |
1255 | ||
f9f354fc | 1256 | if let Some(plus_n) = Step::forward_checked(self.start.clone(), n) { |
48663c56 | 1257 | use crate::cmp::Ordering::*; |
041b39d2 XL |
1258 | |
1259 | match plus_n.partial_cmp(&self.end) { | |
1260 | Some(Less) => { | |
f9f354fc | 1261 | self.start = Step::forward(plus_n.clone(), 1); |
9fa01778 | 1262 | return Some(plus_n); |
041b39d2 XL |
1263 | } |
1264 | Some(Equal) => { | |
74b04a01 XL |
1265 | self.start = plus_n.clone(); |
1266 | self.exhausted = true; | |
9fa01778 | 1267 | return Some(plus_n); |
041b39d2 XL |
1268 | } |
1269 | _ => {} | |
1270 | } | |
1271 | } | |
1272 | ||
74b04a01 XL |
1273 | self.start = self.end.clone(); |
1274 | self.exhausted = true; | |
041b39d2 XL |
1275 | None |
1276 | } | |
2c00a5a8 | 1277 | |
9fa01778 | 1278 | #[inline] |
17df50a5 | 1279 | fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R |
9fa01778 | 1280 | where |
dfeec247 XL |
1281 | Self: Sized, |
1282 | F: FnMut(B, Self::Item) -> R, | |
17df50a5 | 1283 | R: Try<Output = B>, |
9fa01778 | 1284 | { |
17df50a5 | 1285 | self.spec_try_fold(init, f) |
9fa01778 XL |
1286 | } |
1287 | ||
2b03887a | 1288 | impl_fold_via_try_fold! { fold -> try_fold } |
f9f354fc | 1289 | |
2c00a5a8 XL |
1290 | #[inline] |
1291 | fn last(mut self) -> Option<A> { | |
1292 | self.next_back() | |
1293 | } | |
1294 | ||
1295 | #[inline] | |
49aad941 FG |
1296 | fn min(mut self) -> Option<A> |
1297 | where | |
1298 | A: Ord, | |
1299 | { | |
2c00a5a8 XL |
1300 | self.next() |
1301 | } | |
1302 | ||
1303 | #[inline] | |
49aad941 FG |
1304 | fn max(mut self) -> Option<A> |
1305 | where | |
1306 | A: Ord, | |
1307 | { | |
2c00a5a8 XL |
1308 | self.next_back() |
1309 | } | |
c295e0f8 XL |
1310 | |
1311 | #[inline] | |
1312 | fn is_sorted(self) -> bool { | |
1313 | true | |
1314 | } | |
a7813a04 XL |
1315 | } |
1316 | ||
0531ce1d | 1317 | #[stable(feature = "inclusive_range", since = "1.26.0")] |
041b39d2 | 1318 | impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> { |
a7813a04 XL |
1319 | #[inline] |
1320 | fn next_back(&mut self) -> Option<A> { | |
17df50a5 | 1321 | self.spec_next_back() |
a7813a04 | 1322 | } |
9fa01778 | 1323 | |
dc9dc135 XL |
1324 | #[inline] |
1325 | fn nth_back(&mut self, n: usize) -> Option<A> { | |
74b04a01 | 1326 | if self.is_empty() { |
dc9dc135 XL |
1327 | return None; |
1328 | } | |
1329 | ||
f9f354fc | 1330 | if let Some(minus_n) = Step::backward_checked(self.end.clone(), n) { |
dc9dc135 XL |
1331 | use crate::cmp::Ordering::*; |
1332 | ||
1333 | match minus_n.partial_cmp(&self.start) { | |
1334 | Some(Greater) => { | |
f9f354fc | 1335 | self.end = Step::backward(minus_n.clone(), 1); |
dc9dc135 XL |
1336 | return Some(minus_n); |
1337 | } | |
1338 | Some(Equal) => { | |
74b04a01 XL |
1339 | self.end = minus_n.clone(); |
1340 | self.exhausted = true; | |
dc9dc135 XL |
1341 | return Some(minus_n); |
1342 | } | |
1343 | _ => {} | |
1344 | } | |
1345 | } | |
1346 | ||
74b04a01 XL |
1347 | self.end = self.start.clone(); |
1348 | self.exhausted = true; | |
dc9dc135 XL |
1349 | None |
1350 | } | |
1351 | ||
9fa01778 | 1352 | #[inline] |
17df50a5 | 1353 | fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R |
dfeec247 XL |
1354 | where |
1355 | Self: Sized, | |
1356 | F: FnMut(B, Self::Item) -> R, | |
17df50a5 | 1357 | R: Try<Output = B>, |
9fa01778 | 1358 | { |
17df50a5 | 1359 | self.spec_try_rfold(init, f) |
9fa01778 | 1360 | } |
f9f354fc | 1361 | |
2b03887a | 1362 | impl_fold_via_try_fold! { rfold -> try_rfold } |
a7813a04 XL |
1363 | } |
1364 | ||
17df50a5 | 1365 | // Safety: See above implementation for `ops::Range<A>` |
f9f354fc | 1366 | #[unstable(feature = "trusted_len", issue = "37572")] |
17df50a5 | 1367 | unsafe impl<A: TrustedStep> TrustedLen for ops::RangeInclusive<A> {} |
f9f354fc | 1368 | |
0531ce1d | 1369 | #[stable(feature = "fused", since = "1.26.0")] |
041b39d2 | 1370 | impl<A: Step> FusedIterator for ops::RangeInclusive<A> {} |