src/libcore/iter/range.rs

   1 use crate::convert::TryFrom;
   2 use crate::mem;
   3 use crate::ops::{self, Add, Sub, Try};
   4 use crate::usize;
   5
   6 use super::{FusedIterator, TrustedLen};
   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.
  12 #[unstable(feature = "step_trait",
  13            reason = "likely to be replaced by finer-grained traits",
  14            issue = "42168")]
  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`.
  18     ///
  19     /// Returns `None` if it is not possible to calculate `steps_between`
  20     /// without overflow.
  21     fn steps_between(start: &Self, end: &Self) -> Option<usize>;
  22
  23     /// Replaces this step with `1`, returning a clone of itself.
  24     ///
  25     /// The output of this method should always be greater than the output of replace_zero.
  26     fn replace_one(&mut self) -> Self;
  27
  28     /// Replaces this step with `0`, returning a clone of itself.
  29     ///
  30     /// The output of this method should always be less than the output of replace_one.
  31     fn replace_zero(&mut self) -> Self;
  32
  33     /// Adds one to this step, returning the result.
  34     fn add_one(&self) -> Self;
  35
  36     /// Subtracts one to this step, returning the result.
  37     fn sub_one(&self) -> Self;
  38
  39     /// Adds a `usize`, returning `None` on overflow.
  40     fn add_usize(&self, n: usize) -> Option<Self>;
  41
  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
  45         let _ = n;
  46         unimplemented!()
  47     }
  48 }
  49
  50 // These are still macro-generated because the integer literals resolve to different types.
  51 macro_rules! step_identical_methods {
  52     () => {
  53         #[inline]
  54         fn replace_one(&mut self) -> Self {
  55             mem::replace(self, 1)
  56         }
  57
  58         #[inline]
  59         fn replace_zero(&mut self) -> Self {
  60             mem::replace(self, 0)
  61         }
  62
  63         #[inline]
  64         fn add_one(&self) -> Self {
  65             Add::add(*self, 1)
  66         }
  67
  68         #[inline]
  69         fn sub_one(&self) -> Self {
  70             Sub::sub(*self, 1)
  71         }
  72     }
  73 }
  74
  75 macro_rules! step_impl_unsigned {
  76     ($($t:ty)*) => ($(
  77         #[unstable(feature = "step_trait",
  78                    reason = "likely to be replaced by finer-grained traits",
  79                    issue = "42168")]
  80         impl Step for $t {
  81             #[inline]
  82             fn steps_between(start: &$t, end: &$t) -> Option<usize> {
  83                 if *start < *end {
  84                     usize::try_from(*end - *start).ok()
  85                 } else {
  86                     Some(0)
  87                 }
  88             }
  89
  90             #[inline]
  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),
  95                     Err(_) => None,
  96                 }
  97             }
  98
  99             #[inline]
 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),
 104                     Err(_) => None,
 105                 }
 106             }
 107
 108             step_identical_methods!();
 109         }
 110     )*)
 111 }
 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",
 116                    issue = "42168")]
 117         impl Step for $t {
 118             #[inline]
 119             fn steps_between(start: &$t, end: &$t) -> Option<usize> {
 120                 if *start < *end {
 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()
 124                 } else {
 125                     Some(0)
 126                 }
 127             }
 128
 129             #[inline]
 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 {
 139                             Some(wrapped)
 140                         } else {
 141                             None  // Addition overflowed
 142                         }
 143                     }
 144                     Err(_) => None,
 145                 }
 146             }
 147
 148             #[inline]
 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 {
 158                             Some(wrapped)
 159                         } else {
 160                             None  // Subtraction underflowed
 161                         }
 162                     }
 163                     Err(_) => None,
 164                 }
 165             }
 166
 167             step_identical_methods!();
 168         }
 169     )*)
 170 }
 171
 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]);
 175
 176 macro_rules! range_exact_iter_impl {
 177     ($($t:ty)*) => ($(
 178         #[stable(feature = "rust1", since = "1.0.0")]
 179         impl ExactSizeIterator for ops::Range<$t> { }
 180     )*)
 181 }
 182
 183 macro_rules! range_incl_exact_iter_impl {
 184     ($($t:ty)*) => ($(
 185         #[stable(feature = "inclusive_range", since = "1.26.0")]
 186         impl ExactSizeIterator for ops::RangeInclusive<$t> { }
 187     )*)
 188 }
 189
 190 macro_rules! range_trusted_len_impl {
 191     ($($t:ty)*) => ($(
 192         #[unstable(feature = "trusted_len", issue = "37572")]
 193         unsafe impl TrustedLen for ops::Range<$t> { }
 194     )*)
 195 }
 196
 197 macro_rules! range_incl_trusted_len_impl {
 198     ($($t:ty)*) => ($(
 199         #[unstable(feature = "trusted_len", issue = "37572")]
 200         unsafe impl TrustedLen for ops::RangeInclusive<$t> { }
 201     )*)
 202 }
 203
 204 #[stable(feature = "rust1", since = "1.0.0")]
 205 impl<A: Step> Iterator for ops::Range<A> {
 206     type Item = A;
 207
 208     #[inline]
 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);
 217                 Some(n)
 218             } else {
 219                 None
 220             }
 221         } else {
 222             None
 223         }
 224     }
 225
 226     #[inline]
 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)
 231         }
 232     }
 233
 234     #[inline]
 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();
 239                 return Some(plus_n)
 240             }
 241         }
 242
 243         self.start = self.end.clone();
 244         None
 245     }
 246
 247     #[inline]
 248     fn last(mut self) -> Option<A> {
 249         self.next_back()
 250     }
 251
 252     #[inline]
 253     fn min(mut self) -> Option<A> {
 254         self.next()
 255     }
 256
 257     #[inline]
 258     fn max(mut self) -> Option<A> {
 259         self.next_back()
 260     }
 261 }
 262
 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);
 269
 270 // These macros generate `TrustedLen` impls.
 271 //
 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);
 276
 277 #[stable(feature = "rust1", since = "1.0.0")]
 278 impl<A: Step> DoubleEndedIterator for ops::Range<A> {
 279     #[inline]
 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())
 284         } else {
 285             None
 286         }
 287     }
 288
 289     #[inline]
 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())
 295             }
 296         }
 297
 298         self.end = self.start.clone();
 299         None
 300     }
 301 }
 302
 303 #[stable(feature = "fused", since = "1.26.0")]
 304 impl<A: Step> FusedIterator for ops::Range<A> {}
 305
 306 #[stable(feature = "rust1", since = "1.0.0")]
 307 impl<A: Step> Iterator for ops::RangeFrom<A> {
 308     type Item = A;
 309
 310     #[inline]
 311     fn next(&mut self) -> Option<A> {
 312         let mut n = self.start.add_one();
 313         mem::swap(&mut n, &mut self.start);
 314         Some(n)
 315     }
 316
 317     #[inline]
 318     fn size_hint(&self) -> (usize, Option<usize>) {
 319         (usize::MAX, None)
 320     }
 321
 322     #[inline]
 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();
 326         Some(plus_n)
 327     }
 328 }
 329
 330 #[stable(feature = "fused", since = "1.26.0")]
 331 impl<A: Step> FusedIterator for ops::RangeFrom<A> {}
 332
 333 #[unstable(feature = "trusted_len", issue = "37572")]
 334 unsafe impl<A: Step> TrustedLen for ops::RangeFrom<A> {}
 335
 336 #[stable(feature = "inclusive_range", since = "1.26.0")]
 337 impl<A: Step> Iterator for ops::RangeInclusive<A> {
 338     type Item = A;
 339
 340     #[inline]
 341     fn next(&mut self) -> Option<A> {
 342         self.compute_is_empty();
 343         if self.is_empty.unwrap_or_default() {
 344             return None;
 345         }
 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)
 351         } else {
 352             self.start.clone()
 353         })
 354     }
 355
 356     #[inline]
 357     fn size_hint(&self) -> (usize, Option<usize>) {
 358         if self.is_empty() {
 359             return (0, Some(0));
 360         }
 361
 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),
 365         }
 366     }
 367
 368     #[inline]
 369     fn nth(&mut self, n: usize) -> Option<A> {
 370         self.compute_is_empty();
 371         if self.is_empty.unwrap_or_default() {
 372             return None;
 373         }
 374
 375         if let Some(plus_n) = self.start.add_usize(n) {
 376             use crate::cmp::Ordering::*;
 377
 378             match plus_n.partial_cmp(&self.end) {
 379                 Some(Less) => {
 380                     self.is_empty = Some(false);
 381                     self.start = plus_n.add_one();
 382                     return Some(plus_n);
 383                 }
 384                 Some(Equal) => {
 385                     self.is_empty = Some(true);
 386                     return Some(plus_n);
 387                 }
 388                 _ => {}
 389             }
 390         }
 391
 392         self.is_empty = Some(true);
 393         None
 394     }
 395
 396     #[inline]
 397     fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
 398     where
 399         Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
 400     {
 401         self.compute_is_empty();
 402
 403         if self.is_empty() {
 404             return Try::from_ok(init);
 405         }
 406
 407         let mut accum = init;
 408
 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)?;
 413         }
 414
 415         self.is_empty = Some(true);
 416
 417         if self.start == self.end {
 418             accum = f(accum, self.start.clone())?;
 419         }
 420
 421         Try::from_ok(accum)
 422     }
 423
 424     #[inline]
 425     fn last(mut self) -> Option<A> {
 426         self.next_back()
 427     }
 428
 429     #[inline]
 430     fn min(mut self) -> Option<A> {
 431         self.next()
 432     }
 433
 434     #[inline]
 435     fn max(mut self) -> Option<A> {
 436         self.next_back()
 437     }
 438 }
 439
 440 #[stable(feature = "inclusive_range", since = "1.26.0")]
 441 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
 442     #[inline]
 443     fn next_back(&mut self) -> Option<A> {
 444         self.compute_is_empty();
 445         if self.is_empty.unwrap_or_default() {
 446             return None;
 447         }
 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)
 453         } else {
 454             self.end.clone()
 455         })
 456     }
 457
 458     #[inline]
 459     fn nth_back(&mut self, n: usize) -> Option<A> {
 460         self.compute_is_empty();
 461         if self.is_empty.unwrap_or_default() {
 462             return None;
 463         }
 464
 465         if let Some(minus_n) = self.end.sub_usize(n) {
 466             use crate::cmp::Ordering::*;
 467
 468             match minus_n.partial_cmp(&self.start) {
 469                 Some(Greater) => {
 470                     self.is_empty = Some(false);
 471                     self.end = minus_n.sub_one();
 472                     return Some(minus_n);
 473                 }
 474                 Some(Equal) => {
 475                     self.is_empty = Some(true);
 476                     return Some(minus_n);
 477                 }
 478                 _ => {}
 479             }
 480         }
 481
 482         self.is_empty = Some(true);
 483         None
 484     }
 485
 486     #[inline]
 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>
 489     {
 490         self.compute_is_empty();
 491
 492         if self.is_empty() {
 493             return Try::from_ok(init);
 494         }
 495
 496         let mut accum = init;
 497
 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)?;
 502         }
 503
 504         self.is_empty = Some(true);
 505
 506         if self.start == self.end {
 507             accum = f(accum, self.start.clone())?;
 508         }
 509
 510         Try::from_ok(accum)
 511     }
 512 }
 513
 514 #[stable(feature = "fused", since = "1.26.0")]
 515 impl<A: Step> FusedIterator for ops::RangeInclusive<A> {}