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.
12 #[unstable(feature = "step_trait",
13 reason = "likely to be replaced by finer-grained traits",
15 pub trait Step: Clone + PartialOrd + Sized {
16 /// Returns the number of steps between two step objects. The count is
17 /// inclusive of `start` and exclusive of `end`.
19 /// Returns `None` if it is not possible to calculate `steps_between`
21 fn steps_between(start: &Self, end: &Self) -> Option<usize>;
23 /// Replaces this step with `1`, returning a clone of itself.
25 /// The output of this method should always be greater than the output of replace_zero.
26 fn replace_one(&mut self) -> Self;
28 /// Replaces this step with `0`, returning a clone of itself.
30 /// The output of this method should always be less than the output of replace_one.
31 fn replace_zero(&mut self) -> Self;
33 /// Adds one to this step, returning the result.
34 fn add_one(&self) -> Self;
36 /// Subtracts one to this step, returning the result.
37 fn sub_one(&self) -> Self;
39 /// Adds a `usize`, returning `None` on overflow.
40 fn add_usize(&self, n: usize) -> Option<Self>;
42 /// Subtracts a `usize`, returning `None` on underflow.
43 fn sub_usize(&self, n: usize) -> Option<Self> {
44 // this default implementation makes the addition of `sub_usize` a non-breaking change
50 // These are still macro-generated because the integer literals resolve to different types.
51 macro_rules! step_identical_methods {
54 fn replace_one(&mut self) -> Self {
59 fn replace_zero(&mut self) -> Self {
64 fn add_one(&self) -> Self {
69 fn sub_one(&self) -> Self {
75 macro_rules! step_impl_unsigned {
77 #[unstable(feature = "step_trait",
78 reason = "likely to be replaced by finer-grained traits",
82 fn steps_between(start: &$t, end: &$t) -> Option<usize> {
84 usize::try_from(*end - *start).ok()
91 #[allow(unreachable_patterns)]
92 fn add_usize(&self, n: usize) -> Option<Self> {
93 match <$t>::try_from(n) {
94 Ok(n_as_t) => self.checked_add(n_as_t),
100 #[allow(unreachable_patterns)]
101 fn sub_usize(&self, n: usize) -> Option<Self> {
102 match <$t>::try_from(n) {
103 Ok(n_as_t) => self.checked_sub(n_as_t),
108 step_identical_methods!();
112 macro_rules! step_impl_signed {
113 ($( [$t:ty : $unsigned:ty] )*) => ($(
114 #[unstable(feature = "step_trait",
115 reason = "likely to be replaced by finer-grained traits",
119 fn steps_between(start: &$t, end: &$t) -> Option<usize> {
121 // Use .wrapping_sub and cast to unsigned to compute the
122 // difference that may not fit inside the range of $t.
123 usize::try_from(end.wrapping_sub(*start) as $unsigned).ok()
130 #[allow(unreachable_patterns)]
131 fn add_usize(&self, n: usize) -> Option<Self> {
132 match <$unsigned>::try_from(n) {
133 Ok(n_as_unsigned) => {
134 // Wrapping in unsigned space handles cases like
135 // `-120_i8.add_usize(200) == Some(80_i8)`,
136 // even though 200_usize is out of range for i8.
137 let wrapped = (*self as $unsigned).wrapping_add(n_as_unsigned) as $t;
138 if wrapped >= *self {
141 None // Addition overflowed
149 #[allow(unreachable_patterns)]
150 fn sub_usize(&self, n: usize) -> Option<Self> {
151 match <$unsigned>::try_from(n) {
152 Ok(n_as_unsigned) => {
153 // Wrapping in unsigned space handles cases like
154 // `80_i8.sub_usize(200) == Some(-120_i8)`,
155 // even though 200_usize is out of range for i8.
156 let wrapped = (*self as $unsigned).wrapping_sub(n_as_unsigned) as $t;
157 if wrapped <= *self {
160 None // Subtraction underflowed
167 step_identical_methods!();
172 step_impl_unsigned!(usize u8 u16 u32 u64 u128);
173 step_impl_signed!([isize: usize] [i8: u8] [i16: u16]);
174 step_impl_signed!([i32: u32] [i64: u64] [i128: u128]);
176 macro_rules! range_exact_iter_impl {
178 #[stable(feature = "rust1", since = "1.0.0")]
179 impl ExactSizeIterator for ops::Range<$t> { }
183 macro_rules! range_incl_exact_iter_impl {
185 #[stable(feature = "inclusive_range", since = "1.26.0")]
186 impl ExactSizeIterator for ops::RangeInclusive<$t> { }
190 macro_rules! range_trusted_len_impl {
192 #[unstable(feature = "trusted_len", issue = "37572")]
193 unsafe impl TrustedLen for ops::Range<$t> { }
197 macro_rules! range_incl_trusted_len_impl {
199 #[unstable(feature = "trusted_len", issue = "37572")]
200 unsafe impl TrustedLen for ops::RangeInclusive<$t> { }
204 #[stable(feature = "rust1", since = "1.0.0")]
205 impl<A: Step> Iterator for ops::Range<A> {
209 fn next(&mut self) -> Option<A> {
210 if self.start < self.end {
211 // We check for overflow here, even though it can't actually
212 // happen. Adding this check does however help llvm vectorize loops
213 // for some ranges that don't get vectorized otherwise,
214 // and this won't actually result in an extra check in an optimized build.
215 if let Some(mut n) = self.start.add_usize(1) {
216 mem::swap(&mut n, &mut self.start);
227 fn size_hint(&self) -> (usize, Option<usize>) {
228 match Step::steps_between(&self.start, &self.end) {
229 Some(hint) => (hint, Some(hint)),
230 None => (usize::MAX, None)
235 fn nth(&mut self, n: usize) -> Option<A> {
236 if let Some(plus_n) = self.start.add_usize(n) {
237 if plus_n < self.end {
238 self.start = plus_n.add_one();
243 self.start = self.end.clone();
248 fn last(mut self) -> Option<A> {
253 fn min(mut self) -> Option<A> {
258 fn max(mut self) -> Option<A> {
263 // These macros generate `ExactSizeIterator` impls for various range types.
264 // Range<{u,i}64> and RangeInclusive<{u,i}{32,64,size}> are excluded
265 // because they cannot guarantee having a length <= usize::MAX, which is
266 // required by ExactSizeIterator.
267 range_exact_iter_impl!(usize u8 u16 u32 isize i8 i16 i32);
268 range_incl_exact_iter_impl!(u8 u16 i8 i16);
270 // These macros generate `TrustedLen` impls.
272 // They need to guarantee that .size_hint() is either exact, or that
273 // the upper bound is None when it does not fit the type limits.
274 range_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 u64 i64 u128 i128);
275 range_incl_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 u64 i64 u128 i128);
277 #[stable(feature = "rust1", since = "1.0.0")]
278 impl<A: Step> DoubleEndedIterator for ops::Range<A> {
280 fn next_back(&mut self) -> Option<A> {
281 if self.start < self.end {
282 self.end = self.end.sub_one();
283 Some(self.end.clone())
290 fn nth_back(&mut self, n: usize) -> Option<A> {
291 if let Some(minus_n) = self.end.sub_usize(n) {
292 if minus_n > self.start {
293 self.end = minus_n.sub_one();
294 return Some(self.end.clone())
298 self.end = self.start.clone();
303 #[stable(feature = "fused", since = "1.26.0")]
304 impl<A: Step> FusedIterator for ops::Range<A> {}
306 #[stable(feature = "rust1", since = "1.0.0")]
307 impl<A: Step> Iterator for ops::RangeFrom<A> {
311 fn next(&mut self) -> Option<A> {
312 let mut n = self.start.add_one();
313 mem::swap(&mut n, &mut self.start);
318 fn size_hint(&self) -> (usize, Option<usize>) {
323 fn nth(&mut self, n: usize) -> Option<A> {
324 let plus_n = self.start.add_usize(n).expect("overflow in RangeFrom::nth");
325 self.start = plus_n.add_one();
330 #[stable(feature = "fused", since = "1.26.0")]
331 impl<A: Step> FusedIterator for ops::RangeFrom<A> {}
333 #[unstable(feature = "trusted_len", issue = "37572")]
334 unsafe impl<A: Step> TrustedLen for ops::RangeFrom<A> {}
336 #[stable(feature = "inclusive_range", since = "1.26.0")]
337 impl<A: Step> Iterator for ops::RangeInclusive<A> {
341 fn next(&mut self) -> Option<A> {
342 self.compute_is_empty();
343 if self.is_empty.unwrap_or_default() {
346 let is_iterating = self.start < self.end;
347 self.is_empty = Some(!is_iterating);
348 Some(if is_iterating {
349 let n = self.start.add_one();
350 mem::replace(&mut self.start, n)
357 fn size_hint(&self) -> (usize, Option<usize>) {
362 match Step::steps_between(&self.start, &self.end) {
363 Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
364 None => (usize::MAX, None),
369 fn nth(&mut self, n: usize) -> Option<A> {
370 self.compute_is_empty();
371 if self.is_empty.unwrap_or_default() {
375 if let Some(plus_n) = self.start.add_usize(n) {
376 use crate::cmp::Ordering::*;
378 match plus_n.partial_cmp(&self.end) {
380 self.is_empty = Some(false);
381 self.start = plus_n.add_one();
385 self.is_empty = Some(true);
392 self.is_empty = Some(true);
397 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
399 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
401 self.compute_is_empty();
404 return Try::from_ok(init);
407 let mut accum = init;
409 while self.start < self.end {
410 let n = self.start.add_one();
411 let n = mem::replace(&mut self.start, n);
412 accum = f(accum, n)?;
415 self.is_empty = Some(true);
417 if self.start == self.end {
418 accum = f(accum, self.start.clone())?;
425 fn last(mut self) -> Option<A> {
430 fn min(mut self) -> Option<A> {
435 fn max(mut self) -> Option<A> {
440 #[stable(feature = "inclusive_range", since = "1.26.0")]
441 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
443 fn next_back(&mut self) -> Option<A> {
444 self.compute_is_empty();
445 if self.is_empty.unwrap_or_default() {
448 let is_iterating = self.start < self.end;
449 self.is_empty = Some(!is_iterating);
450 Some(if is_iterating {
451 let n = self.end.sub_one();
452 mem::replace(&mut self.end, n)
459 fn nth_back(&mut self, n: usize) -> Option<A> {
460 self.compute_is_empty();
461 if self.is_empty.unwrap_or_default() {
465 if let Some(minus_n) = self.end.sub_usize(n) {
466 use crate::cmp::Ordering::*;
468 match minus_n.partial_cmp(&self.start) {
470 self.is_empty = Some(false);
471 self.end = minus_n.sub_one();
472 return Some(minus_n);
475 self.is_empty = Some(true);
476 return Some(minus_n);
482 self.is_empty = Some(true);
487 fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
488 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
490 self.compute_is_empty();
493 return Try::from_ok(init);
496 let mut accum = init;
498 while self.start < self.end {
499 let n = self.end.sub_one();
500 let n = mem::replace(&mut self.end, n);
501 accum = f(accum, n)?;
504 self.is_empty = Some(true);
506 if self.start == self.end {
507 accum = f(accum, self.start.clone())?;
514 #[stable(feature = "fused", since = "1.26.0")]
515 impl<A: Step> FusedIterator for ops::RangeInclusive<A> {}