]>
Commit | Line | Data |
---|---|---|
48663c56 XL |
1 | use crate::convert::TryFrom; |
2 | use crate::mem; | |
3 | use crate::ops::{self, Add, Sub, Try}; | |
4 | use crate::usize; | |
a7813a04 | 5 | |
c30ab7b3 | 6 | use super::{FusedIterator, TrustedLen}; |
a7813a04 XL |
7 | |
8 | /// Objects that can be stepped over in both directions. | |
9 | /// | |
10 | /// The `steps_between` function provides a way to efficiently compare | |
11 | /// two `Step` objects. | |
dfeec247 XL |
12 | #[unstable( |
13 | feature = "step_trait", | |
14 | reason = "likely to be replaced by finer-grained traits", | |
15 | issue = "42168" | |
16 | )] | |
041b39d2 | 17 | pub trait Step: Clone + PartialOrd + Sized { |
a7813a04 XL |
18 | /// Returns the number of steps between two step objects. The count is |
19 | /// inclusive of `start` and exclusive of `end`. | |
20 | /// | |
21 | /// Returns `None` if it is not possible to calculate `steps_between` | |
22 | /// without overflow. | |
041b39d2 | 23 | fn steps_between(start: &Self, end: &Self) -> Option<usize>; |
3157f602 | 24 | |
60c5eb7d XL |
25 | /// Replaces this step with `1`, returning a clone of itself. |
26 | /// | |
27 | /// The output of this method should always be greater than the output of replace_zero. | |
3157f602 XL |
28 | fn replace_one(&mut self) -> Self; |
29 | ||
60c5eb7d XL |
30 | /// Replaces this step with `0`, returning a clone of itself. |
31 | /// | |
32 | /// The output of this method should always be less than the output of replace_one. | |
3157f602 XL |
33 | fn replace_zero(&mut self) -> Self; |
34 | ||
9fa01778 | 35 | /// Adds one to this step, returning the result. |
3157f602 XL |
36 | fn add_one(&self) -> Self; |
37 | ||
9fa01778 | 38 | /// Subtracts one to this step, returning the result. |
3157f602 | 39 | fn sub_one(&self) -> Self; |
041b39d2 | 40 | |
9fa01778 | 41 | /// Adds a `usize`, returning `None` on overflow. |
041b39d2 | 42 | fn add_usize(&self, n: usize) -> Option<Self>; |
dc9dc135 XL |
43 | |
44 | /// Subtracts a `usize`, returning `None` on underflow. | |
45 | fn sub_usize(&self, n: usize) -> Option<Self> { | |
46 | // this default implementation makes the addition of `sub_usize` a non-breaking change | |
47 | let _ = n; | |
48 | unimplemented!() | |
49 | } | |
041b39d2 XL |
50 | } |
51 | ||
52 | // These are still macro-generated because the integer literals resolve to different types. | |
53 | macro_rules! step_identical_methods { | |
54 | () => { | |
55 | #[inline] | |
56 | fn replace_one(&mut self) -> Self { | |
57 | mem::replace(self, 1) | |
58 | } | |
59 | ||
60 | #[inline] | |
61 | fn replace_zero(&mut self) -> Self { | |
62 | mem::replace(self, 0) | |
63 | } | |
64 | ||
65 | #[inline] | |
66 | fn add_one(&self) -> Self { | |
67 | Add::add(*self, 1) | |
68 | } | |
69 | ||
70 | #[inline] | |
71 | fn sub_one(&self) -> Self { | |
72 | Sub::sub(*self, 1) | |
73 | } | |
74 | } | |
a7813a04 XL |
75 | } |
76 | ||
77 | macro_rules! step_impl_unsigned { | |
78 | ($($t:ty)*) => ($( | |
79 | #[unstable(feature = "step_trait", | |
80 | reason = "likely to be replaced by finer-grained traits", | |
7cac9316 | 81 | issue = "42168")] |
a7813a04 | 82 | impl Step for $t { |
a7813a04 | 83 | #[inline] |
041b39d2 | 84 | fn steps_between(start: &$t, end: &$t) -> Option<usize> { |
a7813a04 | 85 | if *start < *end { |
532ac7d7 | 86 | usize::try_from(*end - *start).ok() |
a7813a04 XL |
87 | } else { |
88 | Some(0) | |
89 | } | |
90 | } | |
3157f602 XL |
91 | |
92 | #[inline] | |
ea8adc8c | 93 | #[allow(unreachable_patterns)] |
041b39d2 | 94 | fn add_usize(&self, n: usize) -> Option<Self> { |
8faf50e0 | 95 | match <$t>::try_from(n) { |
041b39d2 XL |
96 | Ok(n_as_t) => self.checked_add(n_as_t), |
97 | Err(_) => None, | |
98 | } | |
3157f602 XL |
99 | } |
100 | ||
dc9dc135 XL |
101 | #[inline] |
102 | #[allow(unreachable_patterns)] | |
103 | fn sub_usize(&self, n: usize) -> Option<Self> { | |
104 | match <$t>::try_from(n) { | |
105 | Ok(n_as_t) => self.checked_sub(n_as_t), | |
106 | Err(_) => None, | |
107 | } | |
108 | } | |
109 | ||
041b39d2 | 110 | step_identical_methods!(); |
a7813a04 XL |
111 | } |
112 | )*) | |
113 | } | |
114 | macro_rules! step_impl_signed { | |
041b39d2 | 115 | ($( [$t:ty : $unsigned:ty] )*) => ($( |
a7813a04 XL |
116 | #[unstable(feature = "step_trait", |
117 | reason = "likely to be replaced by finer-grained traits", | |
7cac9316 | 118 | issue = "42168")] |
a7813a04 | 119 | impl Step for $t { |
a7813a04 | 120 | #[inline] |
041b39d2 XL |
121 | fn steps_between(start: &$t, end: &$t) -> Option<usize> { |
122 | if *start < *end { | |
532ac7d7 XL |
123 | // Use .wrapping_sub and cast to unsigned to compute the |
124 | // difference that may not fit inside the range of $t. | |
125 | usize::try_from(end.wrapping_sub(*start) as $unsigned).ok() | |
a7813a04 | 126 | } else { |
041b39d2 | 127 | Some(0) |
a7813a04 XL |
128 | } |
129 | } | |
3157f602 XL |
130 | |
131 | #[inline] | |
ea8adc8c | 132 | #[allow(unreachable_patterns)] |
041b39d2 | 133 | fn add_usize(&self, n: usize) -> Option<Self> { |
8faf50e0 | 134 | match <$unsigned>::try_from(n) { |
041b39d2 XL |
135 | Ok(n_as_unsigned) => { |
136 | // Wrapping in unsigned space handles cases like | |
137 | // `-120_i8.add_usize(200) == Some(80_i8)`, | |
138 | // even though 200_usize is out of range for i8. | |
139 | let wrapped = (*self as $unsigned).wrapping_add(n_as_unsigned) as $t; | |
140 | if wrapped >= *self { | |
141 | Some(wrapped) | |
142 | } else { | |
143 | None // Addition overflowed | |
144 | } | |
145 | } | |
146 | Err(_) => None, | |
147 | } | |
3157f602 XL |
148 | } |
149 | ||
dc9dc135 XL |
150 | #[inline] |
151 | #[allow(unreachable_patterns)] | |
152 | fn sub_usize(&self, n: usize) -> Option<Self> { | |
153 | match <$unsigned>::try_from(n) { | |
154 | Ok(n_as_unsigned) => { | |
155 | // Wrapping in unsigned space handles cases like | |
156 | // `80_i8.sub_usize(200) == Some(-120_i8)`, | |
157 | // even though 200_usize is out of range for i8. | |
158 | let wrapped = (*self as $unsigned).wrapping_sub(n_as_unsigned) as $t; | |
159 | if wrapped <= *self { | |
160 | Some(wrapped) | |
161 | } else { | |
162 | None // Subtraction underflowed | |
163 | } | |
164 | } | |
165 | Err(_) => None, | |
166 | } | |
167 | } | |
168 | ||
041b39d2 | 169 | step_identical_methods!(); |
a7813a04 XL |
170 | } |
171 | )*) | |
172 | } | |
173 | ||
532ac7d7 | 174 | step_impl_unsigned!(usize u8 u16 u32 u64 u128); |
dfeec247 XL |
175 | step_impl_signed!([isize: usize][i8: u8][i16: u16]); |
176 | step_impl_signed!([i32: u32][i64: u64][i128: u128]); | |
a7813a04 | 177 | |
a7813a04 XL |
178 | macro_rules! range_exact_iter_impl { |
179 | ($($t:ty)*) => ($( | |
180 | #[stable(feature = "rust1", since = "1.0.0")] | |
181 | impl ExactSizeIterator for ops::Range<$t> { } | |
c30ab7b3 SL |
182 | )*) |
183 | } | |
a7813a04 | 184 | |
c30ab7b3 SL |
185 | macro_rules! range_incl_exact_iter_impl { |
186 | ($($t:ty)*) => ($( | |
0531ce1d | 187 | #[stable(feature = "inclusive_range", since = "1.26.0")] |
a7813a04 XL |
188 | impl ExactSizeIterator for ops::RangeInclusive<$t> { } |
189 | )*) | |
190 | } | |
191 | ||
c30ab7b3 SL |
192 | macro_rules! range_trusted_len_impl { |
193 | ($($t:ty)*) => ($( | |
194 | #[unstable(feature = "trusted_len", issue = "37572")] | |
195 | unsafe impl TrustedLen for ops::Range<$t> { } | |
196 | )*) | |
197 | } | |
198 | ||
199 | macro_rules! range_incl_trusted_len_impl { | |
200 | ($($t:ty)*) => ($( | |
83c7162d | 201 | #[unstable(feature = "trusted_len", issue = "37572")] |
c30ab7b3 SL |
202 | unsafe impl TrustedLen for ops::RangeInclusive<$t> { } |
203 | )*) | |
204 | } | |
205 | ||
a7813a04 | 206 | #[stable(feature = "rust1", since = "1.0.0")] |
041b39d2 | 207 | impl<A: Step> Iterator for ops::Range<A> { |
a7813a04 XL |
208 | type Item = A; |
209 | ||
210 | #[inline] | |
211 | fn next(&mut self) -> Option<A> { | |
212 | if self.start < self.end { | |
3b2f2976 XL |
213 | // We check for overflow here, even though it can't actually |
214 | // happen. Adding this check does however help llvm vectorize loops | |
215 | // for some ranges that don't get vectorized otherwise, | |
216 | // and this won't actually result in an extra check in an optimized build. | |
217 | if let Some(mut n) = self.start.add_usize(1) { | |
218 | mem::swap(&mut n, &mut self.start); | |
219 | Some(n) | |
220 | } else { | |
221 | None | |
222 | } | |
a7813a04 XL |
223 | } else { |
224 | None | |
225 | } | |
226 | } | |
227 | ||
228 | #[inline] | |
229 | fn size_hint(&self) -> (usize, Option<usize>) { | |
041b39d2 | 230 | match Step::steps_between(&self.start, &self.end) { |
a7813a04 | 231 | Some(hint) => (hint, Some(hint)), |
dfeec247 | 232 | None => (usize::MAX, None), |
a7813a04 XL |
233 | } |
234 | } | |
041b39d2 XL |
235 | |
236 | #[inline] | |
237 | fn nth(&mut self, n: usize) -> Option<A> { | |
238 | if let Some(plus_n) = self.start.add_usize(n) { | |
239 | if plus_n < self.end { | |
240 | self.start = plus_n.add_one(); | |
dfeec247 | 241 | return Some(plus_n); |
041b39d2 XL |
242 | } |
243 | } | |
244 | ||
245 | self.start = self.end.clone(); | |
246 | None | |
247 | } | |
2c00a5a8 XL |
248 | |
249 | #[inline] | |
250 | fn last(mut self) -> Option<A> { | |
251 | self.next_back() | |
252 | } | |
253 | ||
254 | #[inline] | |
255 | fn min(mut self) -> Option<A> { | |
256 | self.next() | |
257 | } | |
258 | ||
259 | #[inline] | |
260 | fn max(mut self) -> Option<A> { | |
261 | self.next_back() | |
262 | } | |
a7813a04 XL |
263 | } |
264 | ||
c30ab7b3 SL |
265 | // These macros generate `ExactSizeIterator` impls for various range types. |
266 | // Range<{u,i}64> and RangeInclusive<{u,i}{32,64,size}> are excluded | |
267 | // because they cannot guarantee having a length <= usize::MAX, which is | |
268 | // required by ExactSizeIterator. | |
a7813a04 | 269 | range_exact_iter_impl!(usize u8 u16 u32 isize i8 i16 i32); |
c30ab7b3 SL |
270 | range_incl_exact_iter_impl!(u8 u16 i8 i16); |
271 | ||
272 | // These macros generate `TrustedLen` impls. | |
273 | // | |
274 | // They need to guarantee that .size_hint() is either exact, or that | |
275 | // the upper bound is None when it does not fit the type limits. | |
532ac7d7 XL |
276 | range_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 u64 i64 u128 i128); |
277 | range_incl_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 u64 i64 u128 i128); | |
a7813a04 XL |
278 | |
279 | #[stable(feature = "rust1", since = "1.0.0")] | |
041b39d2 | 280 | impl<A: Step> DoubleEndedIterator for ops::Range<A> { |
a7813a04 XL |
281 | #[inline] |
282 | fn next_back(&mut self) -> Option<A> { | |
283 | if self.start < self.end { | |
3157f602 | 284 | self.end = self.end.sub_one(); |
a7813a04 XL |
285 | Some(self.end.clone()) |
286 | } else { | |
287 | None | |
288 | } | |
289 | } | |
dc9dc135 XL |
290 | |
291 | #[inline] | |
292 | fn nth_back(&mut self, n: usize) -> Option<A> { | |
293 | if let Some(minus_n) = self.end.sub_usize(n) { | |
294 | if minus_n > self.start { | |
295 | self.end = minus_n.sub_one(); | |
dfeec247 | 296 | return Some(self.end.clone()); |
dc9dc135 XL |
297 | } |
298 | } | |
299 | ||
300 | self.end = self.start.clone(); | |
301 | None | |
302 | } | |
a7813a04 XL |
303 | } |
304 | ||
0531ce1d | 305 | #[stable(feature = "fused", since = "1.26.0")] |
041b39d2 | 306 | impl<A: Step> FusedIterator for ops::Range<A> {} |
9e0c209e | 307 | |
a7813a04 | 308 | #[stable(feature = "rust1", since = "1.0.0")] |
041b39d2 | 309 | impl<A: Step> Iterator for ops::RangeFrom<A> { |
a7813a04 XL |
310 | type Item = A; |
311 | ||
312 | #[inline] | |
313 | fn next(&mut self) -> Option<A> { | |
3157f602 | 314 | let mut n = self.start.add_one(); |
a7813a04 XL |
315 | mem::swap(&mut n, &mut self.start); |
316 | Some(n) | |
317 | } | |
7cac9316 XL |
318 | |
319 | #[inline] | |
320 | fn size_hint(&self) -> (usize, Option<usize>) { | |
321 | (usize::MAX, None) | |
322 | } | |
041b39d2 XL |
323 | |
324 | #[inline] | |
325 | fn nth(&mut self, n: usize) -> Option<A> { | |
326 | let plus_n = self.start.add_usize(n).expect("overflow in RangeFrom::nth"); | |
327 | self.start = plus_n.add_one(); | |
328 | Some(plus_n) | |
329 | } | |
a7813a04 XL |
330 | } |
331 | ||
0531ce1d | 332 | #[stable(feature = "fused", since = "1.26.0")] |
041b39d2 | 333 | impl<A: Step> FusedIterator for ops::RangeFrom<A> {} |
9e0c209e | 334 | |
2c00a5a8 XL |
335 | #[unstable(feature = "trusted_len", issue = "37572")] |
336 | unsafe impl<A: Step> TrustedLen for ops::RangeFrom<A> {} | |
337 | ||
0531ce1d | 338 | #[stable(feature = "inclusive_range", since = "1.26.0")] |
041b39d2 | 339 | impl<A: Step> Iterator for ops::RangeInclusive<A> { |
a7813a04 XL |
340 | type Item = A; |
341 | ||
342 | #[inline] | |
343 | fn next(&mut self) -> Option<A> { | |
8faf50e0 XL |
344 | self.compute_is_empty(); |
345 | if self.is_empty.unwrap_or_default() { | |
346 | return None; | |
a7813a04 | 347 | } |
8faf50e0 XL |
348 | let is_iterating = self.start < self.end; |
349 | self.is_empty = Some(!is_iterating); | |
350 | Some(if is_iterating { | |
351 | let n = self.start.add_one(); | |
352 | mem::replace(&mut self.start, n) | |
353 | } else { | |
354 | self.start.clone() | |
355 | }) | |
a7813a04 XL |
356 | } |
357 | ||
358 | #[inline] | |
359 | fn size_hint(&self) -> (usize, Option<usize>) { | |
8faf50e0 | 360 | if self.is_empty() { |
7cac9316 XL |
361 | return (0, Some(0)); |
362 | } | |
a7813a04 | 363 | |
041b39d2 | 364 | match Step::steps_between(&self.start, &self.end) { |
7cac9316 | 365 | Some(hint) => (hint.saturating_add(1), hint.checked_add(1)), |
532ac7d7 | 366 | None => (usize::MAX, None), |
a7813a04 XL |
367 | } |
368 | } | |
041b39d2 XL |
369 | |
370 | #[inline] | |
371 | fn nth(&mut self, n: usize) -> Option<A> { | |
8faf50e0 XL |
372 | self.compute_is_empty(); |
373 | if self.is_empty.unwrap_or_default() { | |
374 | return None; | |
375 | } | |
376 | ||
041b39d2 | 377 | if let Some(plus_n) = self.start.add_usize(n) { |
48663c56 | 378 | use crate::cmp::Ordering::*; |
041b39d2 XL |
379 | |
380 | match plus_n.partial_cmp(&self.end) { | |
381 | Some(Less) => { | |
8faf50e0 | 382 | self.is_empty = Some(false); |
041b39d2 | 383 | self.start = plus_n.add_one(); |
9fa01778 | 384 | return Some(plus_n); |
041b39d2 XL |
385 | } |
386 | Some(Equal) => { | |
8faf50e0 | 387 | self.is_empty = Some(true); |
9fa01778 | 388 | return Some(plus_n); |
041b39d2 XL |
389 | } |
390 | _ => {} | |
391 | } | |
392 | } | |
393 | ||
8faf50e0 | 394 | self.is_empty = Some(true); |
041b39d2 XL |
395 | None |
396 | } | |
2c00a5a8 | 397 | |
9fa01778 XL |
398 | #[inline] |
399 | fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R | |
400 | where | |
dfeec247 XL |
401 | Self: Sized, |
402 | F: FnMut(B, Self::Item) -> R, | |
403 | R: Try<Ok = B>, | |
9fa01778 XL |
404 | { |
405 | self.compute_is_empty(); | |
406 | ||
407 | if self.is_empty() { | |
408 | return Try::from_ok(init); | |
409 | } | |
410 | ||
411 | let mut accum = init; | |
412 | ||
413 | while self.start < self.end { | |
414 | let n = self.start.add_one(); | |
415 | let n = mem::replace(&mut self.start, n); | |
416 | accum = f(accum, n)?; | |
417 | } | |
418 | ||
419 | self.is_empty = Some(true); | |
420 | ||
421 | if self.start == self.end { | |
422 | accum = f(accum, self.start.clone())?; | |
423 | } | |
424 | ||
425 | Try::from_ok(accum) | |
426 | } | |
427 | ||
2c00a5a8 XL |
428 | #[inline] |
429 | fn last(mut self) -> Option<A> { | |
430 | self.next_back() | |
431 | } | |
432 | ||
433 | #[inline] | |
434 | fn min(mut self) -> Option<A> { | |
435 | self.next() | |
436 | } | |
437 | ||
438 | #[inline] | |
439 | fn max(mut self) -> Option<A> { | |
440 | self.next_back() | |
441 | } | |
a7813a04 XL |
442 | } |
443 | ||
0531ce1d | 444 | #[stable(feature = "inclusive_range", since = "1.26.0")] |
041b39d2 | 445 | impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> { |
a7813a04 XL |
446 | #[inline] |
447 | fn next_back(&mut self) -> Option<A> { | |
8faf50e0 XL |
448 | self.compute_is_empty(); |
449 | if self.is_empty.unwrap_or_default() { | |
450 | return None; | |
2c00a5a8 | 451 | } |
8faf50e0 XL |
452 | let is_iterating = self.start < self.end; |
453 | self.is_empty = Some(!is_iterating); | |
454 | Some(if is_iterating { | |
455 | let n = self.end.sub_one(); | |
456 | mem::replace(&mut self.end, n) | |
457 | } else { | |
458 | self.end.clone() | |
459 | }) | |
a7813a04 | 460 | } |
9fa01778 | 461 | |
dc9dc135 XL |
462 | #[inline] |
463 | fn nth_back(&mut self, n: usize) -> Option<A> { | |
464 | self.compute_is_empty(); | |
465 | if self.is_empty.unwrap_or_default() { | |
466 | return None; | |
467 | } | |
468 | ||
469 | if let Some(minus_n) = self.end.sub_usize(n) { | |
470 | use crate::cmp::Ordering::*; | |
471 | ||
472 | match minus_n.partial_cmp(&self.start) { | |
473 | Some(Greater) => { | |
474 | self.is_empty = Some(false); | |
475 | self.end = minus_n.sub_one(); | |
476 | return Some(minus_n); | |
477 | } | |
478 | Some(Equal) => { | |
479 | self.is_empty = Some(true); | |
480 | return Some(minus_n); | |
481 | } | |
482 | _ => {} | |
483 | } | |
484 | } | |
485 | ||
486 | self.is_empty = Some(true); | |
487 | None | |
488 | } | |
489 | ||
9fa01778 | 490 | #[inline] |
dfeec247 XL |
491 | fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R |
492 | where | |
493 | Self: Sized, | |
494 | F: FnMut(B, Self::Item) -> R, | |
495 | R: Try<Ok = B>, | |
9fa01778 XL |
496 | { |
497 | self.compute_is_empty(); | |
498 | ||
499 | if self.is_empty() { | |
500 | return Try::from_ok(init); | |
501 | } | |
502 | ||
503 | let mut accum = init; | |
504 | ||
505 | while self.start < self.end { | |
506 | let n = self.end.sub_one(); | |
507 | let n = mem::replace(&mut self.end, n); | |
508 | accum = f(accum, n)?; | |
509 | } | |
510 | ||
511 | self.is_empty = Some(true); | |
512 | ||
513 | if self.start == self.end { | |
514 | accum = f(accum, self.start.clone())?; | |
515 | } | |
516 | ||
517 | Try::from_ok(accum) | |
518 | } | |
a7813a04 XL |
519 | } |
520 | ||
0531ce1d | 521 | #[stable(feature = "fused", since = "1.26.0")] |
041b39d2 | 522 | impl<A: Step> FusedIterator for ops::RangeInclusive<A> {} |