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 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     /// 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
  41         let _ = n;
  42         unimplemented!()
  43     }
  44 }
  45
  46 // These are still macro-generated because the integer literals resolve to different types.
  47 macro_rules! step_identical_methods {
  48     () => {
  49         #[inline]
  50         fn replace_one(&mut self) -> Self {
  51             mem::replace(self, 1)
  52         }
  53
  54         #[inline]
  55         fn replace_zero(&mut self) -> Self {
  56             mem::replace(self, 0)
  57         }
  58
  59         #[inline]
  60         fn add_one(&self) -> Self {
  61             Add::add(*self, 1)
  62         }
  63
  64         #[inline]
  65         fn sub_one(&self) -> Self {
  66             Sub::sub(*self, 1)
  67         }
  68     }
  69 }
  70
  71 macro_rules! step_impl_unsigned {
  72     ($($t:ty)*) => ($(
  73         #[unstable(feature = "step_trait",
  74                    reason = "likely to be replaced by finer-grained traits",
  75                    issue = "42168")]
  76         impl Step for $t {
  77             #[inline]
  78             fn steps_between(start: &$t, end: &$t) -> Option<usize> {
  79                 if *start < *end {
  80                     usize::try_from(*end - *start).ok()
  81                 } else {
  82                     Some(0)
  83                 }
  84             }
  85
  86             #[inline]
  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),
  91                     Err(_) => None,
  92                 }
  93             }
  94
  95             #[inline]
  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),
 100                     Err(_) => None,
 101                 }
 102             }
 103
 104             step_identical_methods!();
 105         }
 106     )*)
 107 }
 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",
 112                    issue = "42168")]
 113         impl Step for $t {
 114             #[inline]
 115             fn steps_between(start: &$t, end: &$t) -> Option<usize> {
 116                 if *start < *end {
 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()
 120                 } else {
 121                     Some(0)
 122                 }
 123             }
 124
 125             #[inline]
 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 {
 135                             Some(wrapped)
 136                         } else {
 137                             None  // Addition overflowed
 138                         }
 139                     }
 140                     Err(_) => None,
 141                 }
 142             }
 143
 144             #[inline]
 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 {
 154                             Some(wrapped)
 155                         } else {
 156                             None  // Subtraction underflowed
 157                         }
 158                     }
 159                     Err(_) => None,
 160                 }
 161             }
 162
 163             step_identical_methods!();
 164         }
 165     )*)
 166 }
 167
 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]);
 171
 172 macro_rules! range_exact_iter_impl {
 173     ($($t:ty)*) => ($(
 174         #[stable(feature = "rust1", since = "1.0.0")]
 175         impl ExactSizeIterator for ops::Range<$t> { }
 176     )*)
 177 }
 178
 179 macro_rules! range_incl_exact_iter_impl {
 180     ($($t:ty)*) => ($(
 181         #[stable(feature = "inclusive_range", since = "1.26.0")]
 182         impl ExactSizeIterator for ops::RangeInclusive<$t> { }
 183     )*)
 184 }
 185
 186 macro_rules! range_trusted_len_impl {
 187     ($($t:ty)*) => ($(
 188         #[unstable(feature = "trusted_len", issue = "37572")]
 189         unsafe impl TrustedLen for ops::Range<$t> { }
 190     )*)
 191 }
 192
 193 macro_rules! range_incl_trusted_len_impl {
 194     ($($t:ty)*) => ($(
 195         #[unstable(feature = "trusted_len", issue = "37572")]
 196         unsafe impl TrustedLen for ops::RangeInclusive<$t> { }
 197     )*)
 198 }
 199
 200 #[stable(feature = "rust1", since = "1.0.0")]
 201 impl<A: Step> Iterator for ops::Range<A> {
 202     type Item = A;
 203
 204     #[inline]
 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);
 213                 Some(n)
 214             } else {
 215                 None
 216             }
 217         } else {
 218             None
 219         }
 220     }
 221
 222     #[inline]
 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)
 227         }
 228     }
 229
 230     #[inline]
 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();
 235                 return Some(plus_n)
 236             }
 237         }
 238
 239         self.start = self.end.clone();
 240         None
 241     }
 242
 243     #[inline]
 244     fn last(mut self) -> Option<A> {
 245         self.next_back()
 246     }
 247
 248     #[inline]
 249     fn min(mut self) -> Option<A> {
 250         self.next()
 251     }
 252
 253     #[inline]
 254     fn max(mut self) -> Option<A> {
 255         self.next_back()
 256     }
 257 }
 258
 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);
 265
 266 // These macros generate `TrustedLen` impls.
 267 //
 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);
 272
 273 #[stable(feature = "rust1", since = "1.0.0")]
 274 impl<A: Step> DoubleEndedIterator for ops::Range<A> {
 275     #[inline]
 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())
 280         } else {
 281             None
 282         }
 283     }
 284
 285     #[inline]
 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())
 291             }
 292         }
 293
 294         self.end = self.start.clone();
 295         None
 296     }
 297 }
 298
 299 #[stable(feature = "fused", since = "1.26.0")]
 300 impl<A: Step> FusedIterator for ops::Range<A> {}
 301
 302 #[stable(feature = "rust1", since = "1.0.0")]
 303 impl<A: Step> Iterator for ops::RangeFrom<A> {
 304     type Item = A;
 305
 306     #[inline]
 307     fn next(&mut self) -> Option<A> {
 308         let mut n = self.start.add_one();
 309         mem::swap(&mut n, &mut self.start);
 310         Some(n)
 311     }
 312
 313     #[inline]
 314     fn size_hint(&self) -> (usize, Option<usize>) {
 315         (usize::MAX, None)
 316     }
 317
 318     #[inline]
 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();
 322         Some(plus_n)
 323     }
 324 }
 325
 326 #[stable(feature = "fused", since = "1.26.0")]
 327 impl<A: Step> FusedIterator for ops::RangeFrom<A> {}
 328
 329 #[unstable(feature = "trusted_len", issue = "37572")]
 330 unsafe impl<A: Step> TrustedLen for ops::RangeFrom<A> {}
 331
 332 #[stable(feature = "inclusive_range", since = "1.26.0")]
 333 impl<A: Step> Iterator for ops::RangeInclusive<A> {
 334     type Item = A;
 335
 336     #[inline]
 337     fn next(&mut self) -> Option<A> {
 338         self.compute_is_empty();
 339         if self.is_empty.unwrap_or_default() {
 340             return None;
 341         }
 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)
 347         } else {
 348             self.start.clone()
 349         })
 350     }
 351
 352     #[inline]
 353     fn size_hint(&self) -> (usize, Option<usize>) {
 354         if self.is_empty() {
 355             return (0, Some(0));
 356         }
 357
 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),
 361         }
 362     }
 363
 364     #[inline]
 365     fn nth(&mut self, n: usize) -> Option<A> {
 366         self.compute_is_empty();
 367         if self.is_empty.unwrap_or_default() {
 368             return None;
 369         }
 370
 371         if let Some(plus_n) = self.start.add_usize(n) {
 372             use crate::cmp::Ordering::*;
 373
 374             match plus_n.partial_cmp(&self.end) {
 375                 Some(Less) => {
 376                     self.is_empty = Some(false);
 377                     self.start = plus_n.add_one();
 378                     return Some(plus_n);
 379                 }
 380                 Some(Equal) => {
 381                     self.is_empty = Some(true);
 382                     return Some(plus_n);
 383                 }
 384                 _ => {}
 385             }
 386         }
 387
 388         self.is_empty = Some(true);
 389         None
 390     }
 391
 392     #[inline]
 393     fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
 394     where
 395         Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
 396     {
 397         self.compute_is_empty();
 398
 399         if self.is_empty() {
 400             return Try::from_ok(init);
 401         }
 402
 403         let mut accum = init;
 404
 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)?;
 409         }
 410
 411         self.is_empty = Some(true);
 412
 413         if self.start == self.end {
 414             accum = f(accum, self.start.clone())?;
 415         }
 416
 417         Try::from_ok(accum)
 418     }
 419
 420     #[inline]
 421     fn last(mut self) -> Option<A> {
 422         self.next_back()
 423     }
 424
 425     #[inline]
 426     fn min(mut self) -> Option<A> {
 427         self.next()
 428     }
 429
 430     #[inline]
 431     fn max(mut self) -> Option<A> {
 432         self.next_back()
 433     }
 434 }
 435
 436 #[stable(feature = "inclusive_range", since = "1.26.0")]
 437 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
 438     #[inline]
 439     fn next_back(&mut self) -> Option<A> {
 440         self.compute_is_empty();
 441         if self.is_empty.unwrap_or_default() {
 442             return None;
 443         }
 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)
 449         } else {
 450             self.end.clone()
 451         })
 452     }
 453
 454     #[inline]
 455     fn nth_back(&mut self, n: usize) -> Option<A> {
 456         self.compute_is_empty();
 457         if self.is_empty.unwrap_or_default() {
 458             return None;
 459         }
 460
 461         if let Some(minus_n) = self.end.sub_usize(n) {
 462             use crate::cmp::Ordering::*;
 463
 464             match minus_n.partial_cmp(&self.start) {
 465                 Some(Greater) => {
 466                     self.is_empty = Some(false);
 467                     self.end = minus_n.sub_one();
 468                     return Some(minus_n);
 469                 }
 470                 Some(Equal) => {
 471                     self.is_empty = Some(true);
 472                     return Some(minus_n);
 473                 }
 474                 _ => {}
 475             }
 476         }
 477
 478         self.is_empty = Some(true);
 479         None
 480     }
 481
 482     #[inline]
 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>
 485     {
 486         self.compute_is_empty();
 487
 488         if self.is_empty() {
 489             return Try::from_ok(init);
 490         }
 491
 492         let mut accum = init;
 493
 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)?;
 498         }
 499
 500         self.is_empty = Some(true);
 501
 502         if self.start == self.end {
 503             accum = f(accum, self.start.clone())?;
 504         }
 505
 506         Try::from_ok(accum)
 507     }
 508 }
 509
 510 #[stable(feature = "fused", since = "1.26.0")]
 511 impl<A: Step> FusedIterator for ops::RangeInclusive<A> {}