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