1 use crate::convert::TryFrom;
3 use crate::ops::{self, Add, Sub, Try};
6 use super::{FusedIterator, TrustedLen};
8 /// Objects that can be stepped over in both directions.
10 /// The `steps_between` function provides a way to efficiently compare
11 /// two `Step` objects.
13 feature = "step_trait",
14 reason = "likely to be replaced by finer-grained traits",
17 pub trait Step: Clone + PartialOrd + Sized {
18 /// Returns the number of steps between two step objects. The count is
19 /// inclusive of `start` and exclusive of `end`.
21 /// Returns `None` if it is not possible to calculate `steps_between`
23 fn steps_between(start: &Self, end: &Self) -> Option<usize>;
25 /// Replaces this step with `1`, returning a clone of itself.
27 /// The output of this method should always be greater than the output of replace_zero.
28 fn replace_one(&mut self) -> Self;
30 /// Replaces this step with `0`, returning a clone of itself.
32 /// The output of this method should always be less than the output of replace_one.
33 fn replace_zero(&mut self) -> Self;
35 /// Adds one to this step, returning the result.
36 fn add_one(&self) -> Self;
38 /// Subtracts one to this step, returning the result.
39 fn sub_one(&self) -> Self;
41 /// Adds a `usize`, returning `None` on overflow.
42 fn add_usize(&self, n: usize) -> Option<Self>;
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
52 // These are still macro-generated because the integer literals resolve to different types.
53 macro_rules! step_identical_methods {
56 fn replace_one(&mut self) -> Self {
61 fn replace_zero(&mut self) -> Self {
66 fn add_one(&self) -> Self {
71 fn sub_one(&self) -> Self {
77 macro_rules! step_impl_unsigned {
79 #[unstable(feature = "step_trait",
80 reason = "likely to be replaced by finer-grained traits",
84 fn steps_between(start: &$t, end: &$t) -> Option<usize> {
86 usize::try_from(*end - *start).ok()
93 #[allow(unreachable_patterns)]
94 fn add_usize(&self, n: usize) -> Option<Self> {
95 match <$t>::try_from(n) {
96 Ok(n_as_t) => self.checked_add(n_as_t),
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),
110 step_identical_methods!();
114 macro_rules! step_impl_signed {
115 ($( [$t:ty : $unsigned:ty] )*) => ($(
116 #[unstable(feature = "step_trait",
117 reason = "likely to be replaced by finer-grained traits",
121 fn steps_between(start: &$t, end: &$t) -> Option<usize> {
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()
132 #[allow(unreachable_patterns)]
133 fn add_usize(&self, n: usize) -> Option<Self> {
134 match <$unsigned>::try_from(n) {
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 {
143 None // Addition overflowed
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 {
162 None // Subtraction underflowed
169 step_identical_methods!();
174 step_impl_unsigned!(usize u8 u16 u32 u64 u128);
175 step_impl_signed!([isize: usize][i8: u8][i16: u16]);
176 step_impl_signed!([i32: u32][i64: u64][i128: u128]);
178 macro_rules! range_exact_iter_impl {
180 #[stable(feature = "rust1", since = "1.0.0")]
181 impl ExactSizeIterator for ops::Range<$t> { }
185 macro_rules! range_incl_exact_iter_impl {
187 #[stable(feature = "inclusive_range", since = "1.26.0")]
188 impl ExactSizeIterator for ops::RangeInclusive<$t> { }
192 macro_rules! range_trusted_len_impl {
194 #[unstable(feature = "trusted_len", issue = "37572")]
195 unsafe impl TrustedLen for ops::Range<$t> { }
199 macro_rules! range_incl_trusted_len_impl {
201 #[unstable(feature = "trusted_len", issue = "37572")]
202 unsafe impl TrustedLen for ops::RangeInclusive<$t> { }
206 #[stable(feature = "rust1", since = "1.0.0")]
207 impl<A: Step> Iterator for ops::Range<A> {
211 fn next(&mut self) -> Option<A> {
212 if self.start < self.end {
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);
229 fn size_hint(&self) -> (usize, Option<usize>) {
230 match Step::steps_between(&self.start, &self.end) {
231 Some(hint) => (hint, Some(hint)),
232 None => (usize::MAX, None),
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();
245 self.start = self.end.clone();
250 fn last(mut self) -> Option<A> {
255 fn min(mut self) -> Option<A> {
260 fn max(mut self) -> Option<A> {
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.
269 range_exact_iter_impl!(usize u8 u16 u32 isize i8 i16 i32);
270 range_incl_exact_iter_impl!(u8 u16 i8 i16);
272 // These macros generate `TrustedLen` impls.
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.
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);
279 #[stable(feature = "rust1", since = "1.0.0")]
280 impl<A: Step> DoubleEndedIterator for ops::Range<A> {
282 fn next_back(&mut self) -> Option<A> {
283 if self.start < self.end {
284 self.end = self.end.sub_one();
285 Some(self.end.clone())
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();
296 return Some(self.end.clone());
300 self.end = self.start.clone();
305 #[stable(feature = "fused", since = "1.26.0")]
306 impl<A: Step> FusedIterator for ops::Range<A> {}
308 #[stable(feature = "rust1", since = "1.0.0")]
309 impl<A: Step> Iterator for ops::RangeFrom<A> {
313 fn next(&mut self) -> Option<A> {
314 let mut n = self.start.add_one();
315 mem::swap(&mut n, &mut self.start);
320 fn size_hint(&self) -> (usize, Option<usize>) {
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();
332 #[stable(feature = "fused", since = "1.26.0")]
333 impl<A: Step> FusedIterator for ops::RangeFrom<A> {}
335 #[unstable(feature = "trusted_len", issue = "37572")]
336 unsafe impl<A: Step> TrustedLen for ops::RangeFrom<A> {}
338 #[stable(feature = "inclusive_range", since = "1.26.0")]
339 impl<A: Step> Iterator for ops::RangeInclusive<A> {
343 fn next(&mut self) -> Option<A> {
344 self.compute_is_empty();
345 if self.is_empty.unwrap_or_default() {
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)
359 fn size_hint(&self) -> (usize, Option<usize>) {
364 match Step::steps_between(&self.start, &self.end) {
365 Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
366 None => (usize::MAX, None),
371 fn nth(&mut self, n: usize) -> Option<A> {
372 self.compute_is_empty();
373 if self.is_empty.unwrap_or_default() {
377 if let Some(plus_n) = self.start.add_usize(n) {
378 use crate::cmp::Ordering::*;
380 match plus_n.partial_cmp(&self.end) {
382 self.is_empty = Some(false);
383 self.start = plus_n.add_one();
387 self.is_empty = Some(true);
394 self.is_empty = Some(true);
399 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
402 F: FnMut(B, Self::Item) -> R,
405 self.compute_is_empty();
408 return Try::from_ok(init);
411 let mut accum = init;
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)?;
419 self.is_empty = Some(true);
421 if self.start == self.end {
422 accum = f(accum, self.start.clone())?;
429 fn last(mut self) -> Option<A> {
434 fn min(mut self) -> Option<A> {
439 fn max(mut self) -> Option<A> {
444 #[stable(feature = "inclusive_range", since = "1.26.0")]
445 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
447 fn next_back(&mut self) -> Option<A> {
448 self.compute_is_empty();
449 if self.is_empty.unwrap_or_default() {
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)
463 fn nth_back(&mut self, n: usize) -> Option<A> {
464 self.compute_is_empty();
465 if self.is_empty.unwrap_or_default() {
469 if let Some(minus_n) = self.end.sub_usize(n) {
470 use crate::cmp::Ordering::*;
472 match minus_n.partial_cmp(&self.start) {
474 self.is_empty = Some(false);
475 self.end = minus_n.sub_one();
476 return Some(minus_n);
479 self.is_empty = Some(true);
480 return Some(minus_n);
486 self.is_empty = Some(true);
491 fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
494 F: FnMut(B, Self::Item) -> R,
497 self.compute_is_empty();
500 return Try::from_ok(init);
503 let mut accum = init;
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)?;
511 self.is_empty = Some(true);
513 if self.start == self.end {
514 accum = f(accum, self.start.clone())?;
521 #[stable(feature = "fused", since = "1.26.0")]
522 impl<A: Step> FusedIterator for ops::RangeInclusive<A> {}