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 itself.
24 fn replace_one(&mut self) -> Self;
26 /// Replaces this step with `0`, returning itself.
27 fn replace_zero(&mut self) -> Self;
29 /// Adds one to this step, returning the result.
30 fn add_one(&self) -> Self;
32 /// Subtracts one to this step, returning the result.
33 fn sub_one(&self) -> Self;
35 /// Adds a `usize`, returning `None` on overflow.
36 fn add_usize(&self, n: usize) -> Option<Self>;
38 /// Subtracts a `usize`, returning `None` on underflow.
39 fn sub_usize(&self, n: usize) -> Option<Self> {
40 // this default implementation makes the addition of `sub_usize` a non-breaking change
46 // These are still macro-generated because the integer literals resolve to different types.
47 macro_rules! step_identical_methods {
50 fn replace_one(&mut self) -> Self {
55 fn replace_zero(&mut self) -> Self {
60 fn add_one(&self) -> Self {
65 fn sub_one(&self) -> Self {
71 macro_rules! step_impl_unsigned {
73 #[unstable(feature = "step_trait",
74 reason = "likely to be replaced by finer-grained traits",
78 fn steps_between(start: &$t, end: &$t) -> Option<usize> {
80 usize::try_from(*end - *start).ok()
87 #[allow(unreachable_patterns)]
88 fn add_usize(&self, n: usize) -> Option<Self> {
89 match <$t>::try_from(n) {
90 Ok(n_as_t) => self.checked_add(n_as_t),
96 #[allow(unreachable_patterns)]
97 fn sub_usize(&self, n: usize) -> Option<Self> {
98 match <$t>::try_from(n) {
99 Ok(n_as_t) => self.checked_sub(n_as_t),
104 step_identical_methods!();
108 macro_rules! step_impl_signed {
109 ($( [$t:ty : $unsigned:ty] )*) => ($(
110 #[unstable(feature = "step_trait",
111 reason = "likely to be replaced by finer-grained traits",
115 fn steps_between(start: &$t, end: &$t) -> Option<usize> {
117 // Use .wrapping_sub and cast to unsigned to compute the
118 // difference that may not fit inside the range of $t.
119 usize::try_from(end.wrapping_sub(*start) as $unsigned).ok()
126 #[allow(unreachable_patterns)]
127 fn add_usize(&self, n: usize) -> Option<Self> {
128 match <$unsigned>::try_from(n) {
129 Ok(n_as_unsigned) => {
130 // Wrapping in unsigned space handles cases like
131 // `-120_i8.add_usize(200) == Some(80_i8)`,
132 // even though 200_usize is out of range for i8.
133 let wrapped = (*self as $unsigned).wrapping_add(n_as_unsigned) as $t;
134 if wrapped >= *self {
137 None // Addition overflowed
145 #[allow(unreachable_patterns)]
146 fn sub_usize(&self, n: usize) -> Option<Self> {
147 match <$unsigned>::try_from(n) {
148 Ok(n_as_unsigned) => {
149 // Wrapping in unsigned space handles cases like
150 // `80_i8.sub_usize(200) == Some(-120_i8)`,
151 // even though 200_usize is out of range for i8.
152 let wrapped = (*self as $unsigned).wrapping_sub(n_as_unsigned) as $t;
153 if wrapped <= *self {
156 None // Subtraction underflowed
163 step_identical_methods!();
168 step_impl_unsigned!(usize u8 u16 u32 u64 u128);
169 step_impl_signed!([isize: usize] [i8: u8] [i16: u16]);
170 step_impl_signed!([i32: u32] [i64: u64] [i128: u128]);
172 macro_rules! range_exact_iter_impl {
174 #[stable(feature = "rust1", since = "1.0.0")]
175 impl ExactSizeIterator for ops::Range<$t> { }
179 macro_rules! range_incl_exact_iter_impl {
181 #[stable(feature = "inclusive_range", since = "1.26.0")]
182 impl ExactSizeIterator for ops::RangeInclusive<$t> { }
186 macro_rules! range_trusted_len_impl {
188 #[unstable(feature = "trusted_len", issue = "37572")]
189 unsafe impl TrustedLen for ops::Range<$t> { }
193 macro_rules! range_incl_trusted_len_impl {
195 #[unstable(feature = "trusted_len", issue = "37572")]
196 unsafe impl TrustedLen for ops::RangeInclusive<$t> { }
200 #[stable(feature = "rust1", since = "1.0.0")]
201 impl<A: Step> Iterator for ops::Range<A> {
205 fn next(&mut self) -> Option<A> {
206 if self.start < self.end {
207 // We check for overflow here, even though it can't actually
208 // happen. Adding this check does however help llvm vectorize loops
209 // for some ranges that don't get vectorized otherwise,
210 // and this won't actually result in an extra check in an optimized build.
211 if let Some(mut n) = self.start.add_usize(1) {
212 mem::swap(&mut n, &mut self.start);
223 fn size_hint(&self) -> (usize, Option<usize>) {
224 match Step::steps_between(&self.start, &self.end) {
225 Some(hint) => (hint, Some(hint)),
226 None => (usize::MAX, None)
231 fn nth(&mut self, n: usize) -> Option<A> {
232 if let Some(plus_n) = self.start.add_usize(n) {
233 if plus_n < self.end {
234 self.start = plus_n.add_one();
239 self.start = self.end.clone();
244 fn last(mut self) -> Option<A> {
249 fn min(mut self) -> Option<A> {
254 fn max(mut self) -> Option<A> {
259 // These macros generate `ExactSizeIterator` impls for various range types.
260 // Range<{u,i}64> and RangeInclusive<{u,i}{32,64,size}> are excluded
261 // because they cannot guarantee having a length <= usize::MAX, which is
262 // required by ExactSizeIterator.
263 range_exact_iter_impl!(usize u8 u16 u32 isize i8 i16 i32);
264 range_incl_exact_iter_impl!(u8 u16 i8 i16);
266 // These macros generate `TrustedLen` impls.
268 // They need to guarantee that .size_hint() is either exact, or that
269 // the upper bound is None when it does not fit the type limits.
270 range_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 u64 i64 u128 i128);
271 range_incl_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 u64 i64 u128 i128);
273 #[stable(feature = "rust1", since = "1.0.0")]
274 impl<A: Step> DoubleEndedIterator for ops::Range<A> {
276 fn next_back(&mut self) -> Option<A> {
277 if self.start < self.end {
278 self.end = self.end.sub_one();
279 Some(self.end.clone())
286 fn nth_back(&mut self, n: usize) -> Option<A> {
287 if let Some(minus_n) = self.end.sub_usize(n) {
288 if minus_n > self.start {
289 self.end = minus_n.sub_one();
290 return Some(self.end.clone())
294 self.end = self.start.clone();
299 #[stable(feature = "fused", since = "1.26.0")]
300 impl<A: Step> FusedIterator for ops::Range<A> {}
302 #[stable(feature = "rust1", since = "1.0.0")]
303 impl<A: Step> Iterator for ops::RangeFrom<A> {
307 fn next(&mut self) -> Option<A> {
308 let mut n = self.start.add_one();
309 mem::swap(&mut n, &mut self.start);
314 fn size_hint(&self) -> (usize, Option<usize>) {
319 fn nth(&mut self, n: usize) -> Option<A> {
320 let plus_n = self.start.add_usize(n).expect("overflow in RangeFrom::nth");
321 self.start = plus_n.add_one();
326 #[stable(feature = "fused", since = "1.26.0")]
327 impl<A: Step> FusedIterator for ops::RangeFrom<A> {}
329 #[unstable(feature = "trusted_len", issue = "37572")]
330 unsafe impl<A: Step> TrustedLen for ops::RangeFrom<A> {}
332 #[stable(feature = "inclusive_range", since = "1.26.0")]
333 impl<A: Step> Iterator for ops::RangeInclusive<A> {
337 fn next(&mut self) -> Option<A> {
338 self.compute_is_empty();
339 if self.is_empty.unwrap_or_default() {
342 let is_iterating = self.start < self.end;
343 self.is_empty = Some(!is_iterating);
344 Some(if is_iterating {
345 let n = self.start.add_one();
346 mem::replace(&mut self.start, n)
353 fn size_hint(&self) -> (usize, Option<usize>) {
358 match Step::steps_between(&self.start, &self.end) {
359 Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
360 None => (usize::MAX, None),
365 fn nth(&mut self, n: usize) -> Option<A> {
366 self.compute_is_empty();
367 if self.is_empty.unwrap_or_default() {
371 if let Some(plus_n) = self.start.add_usize(n) {
372 use crate::cmp::Ordering::*;
374 match plus_n.partial_cmp(&self.end) {
376 self.is_empty = Some(false);
377 self.start = plus_n.add_one();
381 self.is_empty = Some(true);
388 self.is_empty = Some(true);
393 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
395 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
397 self.compute_is_empty();
400 return Try::from_ok(init);
403 let mut accum = init;
405 while self.start < self.end {
406 let n = self.start.add_one();
407 let n = mem::replace(&mut self.start, n);
408 accum = f(accum, n)?;
411 self.is_empty = Some(true);
413 if self.start == self.end {
414 accum = f(accum, self.start.clone())?;
421 fn last(mut self) -> Option<A> {
426 fn min(mut self) -> Option<A> {
431 fn max(mut self) -> Option<A> {
436 #[stable(feature = "inclusive_range", since = "1.26.0")]
437 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
439 fn next_back(&mut self) -> Option<A> {
440 self.compute_is_empty();
441 if self.is_empty.unwrap_or_default() {
444 let is_iterating = self.start < self.end;
445 self.is_empty = Some(!is_iterating);
446 Some(if is_iterating {
447 let n = self.end.sub_one();
448 mem::replace(&mut self.end, n)
455 fn nth_back(&mut self, n: usize) -> Option<A> {
456 self.compute_is_empty();
457 if self.is_empty.unwrap_or_default() {
461 if let Some(minus_n) = self.end.sub_usize(n) {
462 use crate::cmp::Ordering::*;
464 match minus_n.partial_cmp(&self.start) {
466 self.is_empty = Some(false);
467 self.end = minus_n.sub_one();
468 return Some(minus_n);
471 self.is_empty = Some(true);
472 return Some(minus_n);
478 self.is_empty = Some(true);
483 fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
484 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
486 self.compute_is_empty();
489 return Try::from_ok(init);
492 let mut accum = init;
494 while self.start < self.end {
495 let n = self.end.sub_one();
496 let n = mem::replace(&mut self.end, n);
497 accum = f(accum, n)?;
500 self.is_empty = Some(true);
502 if self.start == self.end {
503 accum = f(accum, self.start.clone())?;
510 #[stable(feature = "fused", since = "1.26.0")]
511 impl<A: Step> FusedIterator for ops::RangeInclusive<A> {}