src/libcore/iter/range.rs

   1 use convert::TryFrom;
   2 use mem;
   3 use ops::{self, Add, Sub, Try};
   4 use 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 itself.
  24     fn replace_one(&mut self) -> Self;
  25
  26     /// Replaces this step with `0`, returning itself.
  27     fn replace_zero(&mut self) -> Self;
  28
  29     /// Adds one to this step, returning the result.
  30     fn add_one(&self) -> Self;
  31
  32     /// Subtracts one to this step, returning the result.
  33     fn sub_one(&self) -> Self;
  34
  35     /// Adds a `usize`, returning `None` on overflow.
  36     fn add_usize(&self, n: usize) -> Option<Self>;
  37 }
  38
  39 // These are still macro-generated because the integer literals resolve to different types.
  40 macro_rules! step_identical_methods {
  41     () => {
  42         #[inline]
  43         fn replace_one(&mut self) -> Self {
  44             mem::replace(self, 1)
  45         }
  46
  47         #[inline]
  48         fn replace_zero(&mut self) -> Self {
  49             mem::replace(self, 0)
  50         }
  51
  52         #[inline]
  53         fn add_one(&self) -> Self {
  54             Add::add(*self, 1)
  55         }
  56
  57         #[inline]
  58         fn sub_one(&self) -> Self {
  59             Sub::sub(*self, 1)
  60         }
  61     }
  62 }
  63
  64 macro_rules! step_impl_unsigned {
  65     ($($t:ty)*) => ($(
  66         #[unstable(feature = "step_trait",
  67                    reason = "likely to be replaced by finer-grained traits",
  68                    issue = "42168")]
  69         impl Step for $t {
  70             #[inline]
  71             fn steps_between(start: &$t, end: &$t) -> Option<usize> {
  72                 if *start < *end {
  73                     usize::try_from(*end - *start).ok()
  74                 } else {
  75                     Some(0)
  76                 }
  77             }
  78
  79             #[inline]
  80             #[allow(unreachable_patterns)]
  81             fn add_usize(&self, n: usize) -> Option<Self> {
  82                 match <$t>::try_from(n) {
  83                     Ok(n_as_t) => self.checked_add(n_as_t),
  84                     Err(_) => None,
  85                 }
  86             }
  87
  88             step_identical_methods!();
  89         }
  90     )*)
  91 }
  92 macro_rules! step_impl_signed {
  93     ($( [$t:ty : $unsigned:ty] )*) => ($(
  94         #[unstable(feature = "step_trait",
  95                    reason = "likely to be replaced by finer-grained traits",
  96                    issue = "42168")]
  97         impl Step for $t {
  98             #[inline]
  99             fn steps_between(start: &$t, end: &$t) -> Option<usize> {
 100                 if *start < *end {
 101                     // Use .wrapping_sub and cast to unsigned to compute the
 102                     // difference that may not fit inside the range of $t.
 103                     usize::try_from(end.wrapping_sub(*start) as $unsigned).ok()
 104                 } else {
 105                     Some(0)
 106                 }
 107             }
 108
 109             #[inline]
 110             #[allow(unreachable_patterns)]
 111             fn add_usize(&self, n: usize) -> Option<Self> {
 112                 match <$unsigned>::try_from(n) {
 113                     Ok(n_as_unsigned) => {
 114                         // Wrapping in unsigned space handles cases like
 115                         // `-120_i8.add_usize(200) == Some(80_i8)`,
 116                         // even though 200_usize is out of range for i8.
 117                         let wrapped = (*self as $unsigned).wrapping_add(n_as_unsigned) as $t;
 118                         if wrapped >= *self {
 119                             Some(wrapped)
 120                         } else {
 121                             None  // Addition overflowed
 122                         }
 123                     }
 124                     Err(_) => None,
 125                 }
 126             }
 127
 128             step_identical_methods!();
 129         }
 130     )*)
 131 }
 132
 133 step_impl_unsigned!(usize u8 u16 u32 u64 u128);
 134 step_impl_signed!([isize: usize] [i8: u8] [i16: u16]);
 135 step_impl_signed!([i32: u32] [i64: u64] [i128: u128]);
 136
 137 macro_rules! range_exact_iter_impl {
 138     ($($t:ty)*) => ($(
 139         #[stable(feature = "rust1", since = "1.0.0")]
 140         impl ExactSizeIterator for ops::Range<$t> { }
 141     )*)
 142 }
 143
 144 macro_rules! range_incl_exact_iter_impl {
 145     ($($t:ty)*) => ($(
 146         #[stable(feature = "inclusive_range", since = "1.26.0")]
 147         impl ExactSizeIterator for ops::RangeInclusive<$t> { }
 148     )*)
 149 }
 150
 151 macro_rules! range_trusted_len_impl {
 152     ($($t:ty)*) => ($(
 153         #[unstable(feature = "trusted_len", issue = "37572")]
 154         unsafe impl TrustedLen for ops::Range<$t> { }
 155     )*)
 156 }
 157
 158 macro_rules! range_incl_trusted_len_impl {
 159     ($($t:ty)*) => ($(
 160         #[unstable(feature = "trusted_len", issue = "37572")]
 161         unsafe impl TrustedLen for ops::RangeInclusive<$t> { }
 162     )*)
 163 }
 164
 165 #[stable(feature = "rust1", since = "1.0.0")]
 166 impl<A: Step> Iterator for ops::Range<A> {
 167     type Item = A;
 168
 169     #[inline]
 170     fn next(&mut self) -> Option<A> {
 171         if self.start < self.end {
 172             // We check for overflow here, even though it can't actually
 173             // happen. Adding this check does however help llvm vectorize loops
 174             // for some ranges that don't get vectorized otherwise,
 175             // and this won't actually result in an extra check in an optimized build.
 176             if let Some(mut n) = self.start.add_usize(1) {
 177                 mem::swap(&mut n, &mut self.start);
 178                 Some(n)
 179             } else {
 180                 None
 181             }
 182         } else {
 183             None
 184         }
 185     }
 186
 187     #[inline]
 188     fn size_hint(&self) -> (usize, Option<usize>) {
 189         match Step::steps_between(&self.start, &self.end) {
 190             Some(hint) => (hint, Some(hint)),
 191             None => (usize::MAX, None)
 192         }
 193     }
 194
 195     #[inline]
 196     fn nth(&mut self, n: usize) -> Option<A> {
 197         if let Some(plus_n) = self.start.add_usize(n) {
 198             if plus_n < self.end {
 199                 self.start = plus_n.add_one();
 200                 return Some(plus_n)
 201             }
 202         }
 203
 204         self.start = self.end.clone();
 205         None
 206     }
 207
 208     #[inline]
 209     fn last(mut self) -> Option<A> {
 210         self.next_back()
 211     }
 212
 213     #[inline]
 214     fn min(mut self) -> Option<A> {
 215         self.next()
 216     }
 217
 218     #[inline]
 219     fn max(mut self) -> Option<A> {
 220         self.next_back()
 221     }
 222 }
 223
 224 // These macros generate `ExactSizeIterator` impls for various range types.
 225 // Range<{u,i}64> and RangeInclusive<{u,i}{32,64,size}> are excluded
 226 // because they cannot guarantee having a length <= usize::MAX, which is
 227 // required by ExactSizeIterator.
 228 range_exact_iter_impl!(usize u8 u16 u32 isize i8 i16 i32);
 229 range_incl_exact_iter_impl!(u8 u16 i8 i16);
 230
 231 // These macros generate `TrustedLen` impls.
 232 //
 233 // They need to guarantee that .size_hint() is either exact, or that
 234 // the upper bound is None when it does not fit the type limits.
 235 range_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 i64 u64);
 236 range_incl_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 i64 u64);
 237
 238 #[stable(feature = "rust1", since = "1.0.0")]
 239 impl<A: Step> DoubleEndedIterator for ops::Range<A> {
 240     #[inline]
 241     fn next_back(&mut self) -> Option<A> {
 242         if self.start < self.end {
 243             self.end = self.end.sub_one();
 244             Some(self.end.clone())
 245         } else {
 246             None
 247         }
 248     }
 249 }
 250
 251 #[stable(feature = "fused", since = "1.26.0")]
 252 impl<A: Step> FusedIterator for ops::Range<A> {}
 253
 254 #[stable(feature = "rust1", since = "1.0.0")]
 255 impl<A: Step> Iterator for ops::RangeFrom<A> {
 256     type Item = A;
 257
 258     #[inline]
 259     fn next(&mut self) -> Option<A> {
 260         let mut n = self.start.add_one();
 261         mem::swap(&mut n, &mut self.start);
 262         Some(n)
 263     }
 264
 265     #[inline]
 266     fn size_hint(&self) -> (usize, Option<usize>) {
 267         (usize::MAX, None)
 268     }
 269
 270     #[inline]
 271     fn nth(&mut self, n: usize) -> Option<A> {
 272         let plus_n = self.start.add_usize(n).expect("overflow in RangeFrom::nth");
 273         self.start = plus_n.add_one();
 274         Some(plus_n)
 275     }
 276 }
 277
 278 #[stable(feature = "fused", since = "1.26.0")]
 279 impl<A: Step> FusedIterator for ops::RangeFrom<A> {}
 280
 281 #[unstable(feature = "trusted_len", issue = "37572")]
 282 unsafe impl<A: Step> TrustedLen for ops::RangeFrom<A> {}
 283
 284 #[stable(feature = "inclusive_range", since = "1.26.0")]
 285 impl<A: Step> Iterator for ops::RangeInclusive<A> {
 286     type Item = A;
 287
 288     #[inline]
 289     fn next(&mut self) -> Option<A> {
 290         self.compute_is_empty();
 291         if self.is_empty.unwrap_or_default() {
 292             return None;
 293         }
 294         let is_iterating = self.start < self.end;
 295         self.is_empty = Some(!is_iterating);
 296         Some(if is_iterating {
 297             let n = self.start.add_one();
 298             mem::replace(&mut self.start, n)
 299         } else {
 300             self.start.clone()
 301         })
 302     }
 303
 304     #[inline]
 305     fn size_hint(&self) -> (usize, Option<usize>) {
 306         if self.is_empty() {
 307             return (0, Some(0));
 308         }
 309
 310         match Step::steps_between(&self.start, &self.end) {
 311             Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
 312             None => (usize::MAX, None),
 313         }
 314     }
 315
 316     #[inline]
 317     fn nth(&mut self, n: usize) -> Option<A> {
 318         self.compute_is_empty();
 319         if self.is_empty.unwrap_or_default() {
 320             return None;
 321         }
 322
 323         if let Some(plus_n) = self.start.add_usize(n) {
 324             use cmp::Ordering::*;
 325
 326             match plus_n.partial_cmp(&self.end) {
 327                 Some(Less) => {
 328                     self.is_empty = Some(false);
 329                     self.start = plus_n.add_one();
 330                     return Some(plus_n);
 331                 }
 332                 Some(Equal) => {
 333                     self.is_empty = Some(true);
 334                     return Some(plus_n);
 335                 }
 336                 _ => {}
 337             }
 338         }
 339
 340         self.is_empty = Some(true);
 341         None
 342     }
 343
 344     #[inline]
 345     fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
 346     where
 347         Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
 348     {
 349         self.compute_is_empty();
 350
 351         if self.is_empty() {
 352             return Try::from_ok(init);
 353         }
 354
 355         let mut accum = init;
 356
 357         while self.start < self.end {
 358             let n = self.start.add_one();
 359             let n = mem::replace(&mut self.start, n);
 360             accum = f(accum, n)?;
 361         }
 362
 363         self.is_empty = Some(true);
 364
 365         if self.start == self.end {
 366             accum = f(accum, self.start.clone())?;
 367         }
 368
 369         Try::from_ok(accum)
 370     }
 371
 372     #[inline]
 373     fn last(mut self) -> Option<A> {
 374         self.next_back()
 375     }
 376
 377     #[inline]
 378     fn min(mut self) -> Option<A> {
 379         self.next()
 380     }
 381
 382     #[inline]
 383     fn max(mut self) -> Option<A> {
 384         self.next_back()
 385     }
 386 }
 387
 388 #[stable(feature = "inclusive_range", since = "1.26.0")]
 389 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
 390     #[inline]
 391     fn next_back(&mut self) -> Option<A> {
 392         self.compute_is_empty();
 393         if self.is_empty.unwrap_or_default() {
 394             return None;
 395         }
 396         let is_iterating = self.start < self.end;
 397         self.is_empty = Some(!is_iterating);
 398         Some(if is_iterating {
 399             let n = self.end.sub_one();
 400             mem::replace(&mut self.end, n)
 401         } else {
 402             self.end.clone()
 403         })
 404     }
 405
 406     #[inline]
 407     fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
 408         Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
 409     {
 410         self.compute_is_empty();
 411
 412         if self.is_empty() {
 413             return Try::from_ok(init);
 414         }
 415
 416         let mut accum = init;
 417
 418         while self.start < self.end {
 419             let n = self.end.sub_one();
 420             let n = mem::replace(&mut self.end, n);
 421             accum = f(accum, n)?;
 422         }
 423
 424         self.is_empty = Some(true);
 425
 426         if self.start == self.end {
 427             accum = f(accum, self.start.clone())?;
 428         }
 429
 430         Try::from_ok(accum)
 431     }
 432 }
 433
 434 #[stable(feature = "fused", since = "1.26.0")]
 435 impl<A: Step> FusedIterator for ops::RangeInclusive<A> {}