src/libcore/iter/range.rs

   1 // Copyright 2013-2016 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use convert::TryFrom;
  12 use mem;
  13 use ops::{self, Add, Sub, Try};
  14 use usize;
  15
  16 use super::{FusedIterator, TrustedLen};
  17
  18 /// Objects that can be stepped over in both directions.
  19 ///
  20 /// The `steps_between` function provides a way to efficiently compare
  21 /// two `Step` objects.
  22 #[unstable(feature = "step_trait",
  23            reason = "likely to be replaced by finer-grained traits",
  24            issue = "42168")]
  25 pub trait Step: Clone + PartialOrd + Sized {
  26     /// Returns the number of steps between two step objects. The count is
  27     /// inclusive of `start` and exclusive of `end`.
  28     ///
  29     /// Returns `None` if it is not possible to calculate `steps_between`
  30     /// without overflow.
  31     fn steps_between(start: &Self, end: &Self) -> Option<usize>;
  32
  33     /// Replaces this step with `1`, returning itself
  34     fn replace_one(&mut self) -> Self;
  35
  36     /// Replaces this step with `0`, returning itself
  37     fn replace_zero(&mut self) -> Self;
  38
  39     /// Adds one to this step, returning the result
  40     fn add_one(&self) -> Self;
  41
  42     /// Subtracts one to this step, returning the result
  43     fn sub_one(&self) -> Self;
  44
  45     /// Add an usize, returning None on overflow
  46     fn add_usize(&self, n: usize) -> Option<Self>;
  47 }
  48
  49 // These are still macro-generated because the integer literals resolve to different types.
  50 macro_rules! step_identical_methods {
  51     () => {
  52         #[inline]
  53         fn replace_one(&mut self) -> Self {
  54             mem::replace(self, 1)
  55         }
  56
  57         #[inline]
  58         fn replace_zero(&mut self) -> Self {
  59             mem::replace(self, 0)
  60         }
  61
  62         #[inline]
  63         fn add_one(&self) -> Self {
  64             Add::add(*self, 1)
  65         }
  66
  67         #[inline]
  68         fn sub_one(&self) -> Self {
  69             Sub::sub(*self, 1)
  70         }
  71     }
  72 }
  73
  74 macro_rules! step_impl_unsigned {
  75     ($($t:ty)*) => ($(
  76         #[unstable(feature = "step_trait",
  77                    reason = "likely to be replaced by finer-grained traits",
  78                    issue = "42168")]
  79         impl Step for $t {
  80             #[inline]
  81             #[allow(trivial_numeric_casts)]
  82             fn steps_between(start: &$t, end: &$t) -> Option<usize> {
  83                 if *start < *end {
  84                     // Note: We assume $t <= usize here
  85                     Some((*end - *start) as usize)
  86                 } else {
  87                     Some(0)
  88                 }
  89             }
  90
  91             #[inline]
  92             #[allow(unreachable_patterns)]
  93             fn add_usize(&self, n: usize) -> Option<Self> {
  94                 match <$t>::private_try_from(n) {
  95                     Ok(n_as_t) => self.checked_add(n_as_t),
  96                     Err(_) => None,
  97                 }
  98             }
  99
 100             step_identical_methods!();
 101         }
 102     )*)
 103 }
 104 macro_rules! step_impl_signed {
 105     ($( [$t:ty : $unsigned:ty] )*) => ($(
 106         #[unstable(feature = "step_trait",
 107                    reason = "likely to be replaced by finer-grained traits",
 108                    issue = "42168")]
 109         impl Step for $t {
 110             #[inline]
 111             #[allow(trivial_numeric_casts)]
 112             fn steps_between(start: &$t, end: &$t) -> Option<usize> {
 113                 if *start < *end {
 114                     // Note: We assume $t <= isize here
 115                     // Use .wrapping_sub and cast to usize to compute the
 116                     // difference that may not fit inside the range of isize.
 117                     Some((*end as isize).wrapping_sub(*start as isize) as usize)
 118                 } else {
 119                     Some(0)
 120                 }
 121             }
 122
 123             #[inline]
 124             #[allow(unreachable_patterns)]
 125             fn add_usize(&self, n: usize) -> Option<Self> {
 126                 match <$unsigned>::private_try_from(n) {
 127                     Ok(n_as_unsigned) => {
 128                         // Wrapping in unsigned space handles cases like
 129                         // `-120_i8.add_usize(200) == Some(80_i8)`,
 130                         // even though 200_usize is out of range for i8.
 131                         let wrapped = (*self as $unsigned).wrapping_add(n_as_unsigned) as $t;
 132                         if wrapped >= *self {
 133                             Some(wrapped)
 134                         } else {
 135                             None  // Addition overflowed
 136                         }
 137                     }
 138                     Err(_) => None,
 139                 }
 140             }
 141
 142             step_identical_methods!();
 143         }
 144     )*)
 145 }
 146
 147 macro_rules! step_impl_no_between {
 148     ($($t:ty)*) => ($(
 149         #[unstable(feature = "step_trait",
 150                    reason = "likely to be replaced by finer-grained traits",
 151                    issue = "42168")]
 152         impl Step for $t {
 153             #[inline]
 154             fn steps_between(_start: &Self, _end: &Self) -> Option<usize> {
 155                 None
 156             }
 157
 158             #[inline]
 159             fn add_usize(&self, n: usize) -> Option<Self> {
 160                 self.checked_add(n as $t)
 161             }
 162
 163             step_identical_methods!();
 164         }
 165     )*)
 166 }
 167
 168 step_impl_unsigned!(usize u8 u16 u32);
 169 step_impl_signed!([isize: usize] [i8: u8] [i16: u16] [i32: u32]);
 170 #[cfg(target_pointer_width = "64")]
 171 step_impl_unsigned!(u64);
 172 #[cfg(target_pointer_width = "64")]
 173 step_impl_signed!([i64: u64]);
 174 // If the target pointer width is not 64-bits, we
 175 // assume here that it is less than 64-bits.
 176 #[cfg(not(target_pointer_width = "64"))]
 177 step_impl_no_between!(u64 i64);
 178 step_impl_no_between!(u128 i128);
 179
 180 macro_rules! range_exact_iter_impl {
 181     ($($t:ty)*) => ($(
 182         #[stable(feature = "rust1", since = "1.0.0")]
 183         impl ExactSizeIterator for ops::Range<$t> { }
 184     )*)
 185 }
 186
 187 macro_rules! range_incl_exact_iter_impl {
 188     ($($t:ty)*) => ($(
 189         #[stable(feature = "inclusive_range", since = "1.26.0")]
 190         impl ExactSizeIterator for ops::RangeInclusive<$t> { }
 191     )*)
 192 }
 193
 194 macro_rules! range_trusted_len_impl {
 195     ($($t:ty)*) => ($(
 196         #[unstable(feature = "trusted_len", issue = "37572")]
 197         unsafe impl TrustedLen for ops::Range<$t> { }
 198     )*)
 199 }
 200
 201 macro_rules! range_incl_trusted_len_impl {
 202     ($($t:ty)*) => ($(
 203         #[stable(feature = "inclusive_range", since = "1.26.0")]
 204         unsafe impl TrustedLen for ops::RangeInclusive<$t> { }
 205     )*)
 206 }
 207
 208 #[stable(feature = "rust1", since = "1.0.0")]
 209 impl<A: Step> Iterator for ops::Range<A> {
 210     type Item = A;
 211
 212     #[inline]
 213     fn next(&mut self) -> Option<A> {
 214         if self.start < self.end {
 215             // We check for overflow here, even though it can't actually
 216             // happen. Adding this check does however help llvm vectorize loops
 217             // for some ranges that don't get vectorized otherwise,
 218             // and this won't actually result in an extra check in an optimized build.
 219             if let Some(mut n) = self.start.add_usize(1) {
 220                 mem::swap(&mut n, &mut self.start);
 221                 Some(n)
 222             } else {
 223                 None
 224             }
 225         } else {
 226             None
 227         }
 228     }
 229
 230     #[inline]
 231     fn size_hint(&self) -> (usize, Option<usize>) {
 232         match Step::steps_between(&self.start, &self.end) {
 233             Some(hint) => (hint, Some(hint)),
 234             None => (0, None)
 235         }
 236     }
 237
 238     #[inline]
 239     fn nth(&mut self, n: usize) -> Option<A> {
 240         if let Some(plus_n) = self.start.add_usize(n) {
 241             if plus_n < self.end {
 242                 self.start = plus_n.add_one();
 243                 return Some(plus_n)
 244             }
 245         }
 246
 247         self.start = self.end.clone();
 248         None
 249     }
 250
 251     #[inline]
 252     fn last(mut self) -> Option<A> {
 253         self.next_back()
 254     }
 255
 256     #[inline]
 257     fn min(mut self) -> Option<A> {
 258         self.next()
 259     }
 260
 261     #[inline]
 262     fn max(mut self) -> Option<A> {
 263         self.next_back()
 264     }
 265 }
 266
 267 // These macros generate `ExactSizeIterator` impls for various range types.
 268 // Range<{u,i}64> and RangeInclusive<{u,i}{32,64,size}> are excluded
 269 // because they cannot guarantee having a length <= usize::MAX, which is
 270 // required by ExactSizeIterator.
 271 range_exact_iter_impl!(usize u8 u16 u32 isize i8 i16 i32);
 272 range_incl_exact_iter_impl!(u8 u16 i8 i16);
 273
 274 // These macros generate `TrustedLen` impls.
 275 //
 276 // They need to guarantee that .size_hint() is either exact, or that
 277 // the upper bound is None when it does not fit the type limits.
 278 range_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 i64 u64);
 279 range_incl_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 i64 u64);
 280
 281 #[stable(feature = "rust1", since = "1.0.0")]
 282 impl<A: Step> DoubleEndedIterator for ops::Range<A> {
 283     #[inline]
 284     fn next_back(&mut self) -> Option<A> {
 285         if self.start < self.end {
 286             self.end = self.end.sub_one();
 287             Some(self.end.clone())
 288         } else {
 289             None
 290         }
 291     }
 292 }
 293
 294 #[stable(feature = "fused", since = "1.26.0")]
 295 impl<A: Step> FusedIterator for ops::Range<A> {}
 296
 297 #[stable(feature = "rust1", since = "1.0.0")]
 298 impl<A: Step> Iterator for ops::RangeFrom<A> {
 299     type Item = A;
 300
 301     #[inline]
 302     fn next(&mut self) -> Option<A> {
 303         let mut n = self.start.add_one();
 304         mem::swap(&mut n, &mut self.start);
 305         Some(n)
 306     }
 307
 308     #[inline]
 309     fn size_hint(&self) -> (usize, Option<usize>) {
 310         (usize::MAX, None)
 311     }
 312
 313     #[inline]
 314     fn nth(&mut self, n: usize) -> Option<A> {
 315         let plus_n = self.start.add_usize(n).expect("overflow in RangeFrom::nth");
 316         self.start = plus_n.add_one();
 317         Some(plus_n)
 318     }
 319 }
 320
 321 #[stable(feature = "fused", since = "1.26.0")]
 322 impl<A: Step> FusedIterator for ops::RangeFrom<A> {}
 323
 324 #[unstable(feature = "trusted_len", issue = "37572")]
 325 unsafe impl<A: Step> TrustedLen for ops::RangeFrom<A> {}
 326
 327 #[stable(feature = "inclusive_range", since = "1.26.0")]
 328 impl<A: Step> Iterator for ops::RangeInclusive<A> {
 329     type Item = A;
 330
 331     #[inline]
 332     fn next(&mut self) -> Option<A> {
 333         if self.start <= self.end {
 334             if self.start < self.end {
 335                 let n = self.start.add_one();
 336                 Some(mem::replace(&mut self.start, n))
 337             } else {
 338                 let last = self.start.replace_one();
 339                 self.end.replace_zero();
 340                 Some(last)
 341             }
 342         } else {
 343             None
 344         }
 345     }
 346
 347     #[inline]
 348     fn size_hint(&self) -> (usize, Option<usize>) {
 349         if !(self.start <= self.end) {
 350             return (0, Some(0));
 351         }
 352
 353         match Step::steps_between(&self.start, &self.end) {
 354             Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
 355             None => (0, None),
 356         }
 357     }
 358
 359     #[inline]
 360     fn nth(&mut self, n: usize) -> Option<A> {
 361         if let Some(plus_n) = self.start.add_usize(n) {
 362             use cmp::Ordering::*;
 363
 364             match plus_n.partial_cmp(&self.end) {
 365                 Some(Less) => {
 366                     self.start = plus_n.add_one();
 367                     return Some(plus_n)
 368                 }
 369                 Some(Equal) => {
 370                     self.start.replace_one();
 371                     self.end.replace_zero();
 372                     return Some(plus_n)
 373                 }
 374                 _ => {}
 375             }
 376         }
 377
 378         self.start.replace_one();
 379         self.end.replace_zero();
 380         None
 381     }
 382
 383     #[inline]
 384     fn last(mut self) -> Option<A> {
 385         self.next_back()
 386     }
 387
 388     #[inline]
 389     fn min(mut self) -> Option<A> {
 390         self.next()
 391     }
 392
 393     #[inline]
 394     fn max(mut self) -> Option<A> {
 395         self.next_back()
 396     }
 397
 398     #[inline]
 399     fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
 400         Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
 401     {
 402         let mut accum = init;
 403         if self.start <= self.end {
 404             loop {
 405                 let (x, done) =
 406                     if self.start < self.end {
 407                         let n = self.start.add_one();
 408                         (mem::replace(&mut self.start, n), false)
 409                     } else {
 410                         self.end.replace_zero();
 411                         (self.start.replace_one(), true)
 412                     };
 413                 accum = f(accum, x)?;
 414                 if done { break }
 415             }
 416         }
 417         Try::from_ok(accum)
 418     }
 419 }
 420
 421 #[stable(feature = "inclusive_range", since = "1.26.0")]
 422 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
 423     #[inline]
 424     fn next_back(&mut self) -> Option<A> {
 425         if self.start <= self.end {
 426             if self.start < self.end {
 427                 let n = self.end.sub_one();
 428                 Some(mem::replace(&mut self.end, n))
 429             } else {
 430                 let last = self.end.replace_zero();
 431                 self.start.replace_one();
 432                 Some(last)
 433             }
 434         } else {
 435             None
 436         }
 437     }
 438
 439     #[inline]
 440     fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
 441         Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
 442     {
 443         let mut accum = init;
 444         if self.start <= self.end {
 445             loop {
 446                 let (x, done) =
 447                     if self.start < self.end {
 448                         let n = self.end.sub_one();
 449                         (mem::replace(&mut self.end, n), false)
 450                     } else {
 451                         self.start.replace_one();
 452                         (self.end.replace_zero(), true)
 453                     };
 454                 accum = f(accum, x)?;
 455                 if done { break }
 456             }
 457         }
 458         Try::from_ok(accum)
 459     }
 460 }
 461
 462 #[stable(feature = "fused", since = "1.26.0")]
 463 impl<A: Step> FusedIterator for ops::RangeInclusive<A> {}
 464
 465 /// Compensate removal of some impls per
 466 /// https://github.com/rust-lang/rust/pull/49305#issuecomment-376293243
 467 trait PrivateTryFromUsize: Sized {
 468     fn private_try_from(n: usize) -> Result<Self, ()>;
 469 }
 470
 471 impl<T> PrivateTryFromUsize for T where T: TryFrom<usize> {
 472     #[inline]
 473     fn private_try_from(n: usize) -> Result<Self, ()> {
 474         T::try_from(n).map_err(|_| ())
 475     }
 476 }
 477
 478 // no possible bounds violation
 479 macro_rules! try_from_unbounded {
 480     ($($target:ty),*) => {$(
 481         impl PrivateTryFromUsize for $target {
 482             #[inline]
 483             fn private_try_from(value: usize) -> Result<Self, ()> {
 484                 Ok(value as $target)
 485             }
 486         }
 487     )*}
 488 }
 489
 490 // unsigned to signed (only positive bound)
 491 macro_rules! try_from_upper_bounded {
 492     ($($target:ty),*) => {$(
 493         impl PrivateTryFromUsize for $target {
 494             #[inline]
 495             fn private_try_from(u: usize) -> Result<$target, ()> {
 496                 if u > (<$target>::max_value() as usize) {
 497                     Err(())
 498                 } else {
 499                     Ok(u as $target)
 500                 }
 501             }
 502         }
 503     )*}
 504 }
 505
 506
 507 #[cfg(target_pointer_width = "16")]
 508 mod ptr_try_from_impls {
 509     use super::PrivateTryFromUsize;
 510
 511     try_from_unbounded!(u16, u32, u64, u128);
 512     try_from_unbounded!(i32, i64, i128);
 513 }
 514
 515 #[cfg(target_pointer_width = "32")]
 516 mod ptr_try_from_impls {
 517     use super::PrivateTryFromUsize;
 518
 519     try_from_upper_bounded!(u16);
 520     try_from_unbounded!(u32, u64, u128);
 521     try_from_upper_bounded!(i32);
 522     try_from_unbounded!(i64, i128);
 523 }
 524
 525 #[cfg(target_pointer_width = "64")]
 526 mod ptr_try_from_impls {
 527     use super::PrivateTryFromUsize;
 528
 529     try_from_upper_bounded!(u16, u32);
 530     try_from_unbounded!(u64, u128);
 531     try_from_upper_bounded!(i32, i64);
 532     try_from_unbounded!(i128);
 533 }