src/libcore/iter/mod.rs

   1 //! Composable external iteration.
   2 //!
   3 //! If you've found yourself with a collection of some kind, and needed to
   4 //! perform an operation on the elements of said collection, you'll quickly run
   5 //! into 'iterators'. Iterators are heavily used in idiomatic Rust code, so
   6 //! it's worth becoming familiar with them.
   7 //!
   8 //! Before explaining more, let's talk about how this module is structured:
   9 //!
  10 //! # Organization
  11 //!
  12 //! This module is largely organized by type:
  13 //!
  14 //! * [Traits] are the core portion: these traits define what kind of iterators
  15 //!   exist and what you can do with them. The methods of these traits are worth
  16 //!   putting some extra study time into.
  17 //! * [Functions] provide some helpful ways to create some basic iterators.
  18 //! * [Structs] are often the return types of the various methods on this
  19 //!   module's traits. You'll usually want to look at the method that creates
  20 //!   the `struct`, rather than the `struct` itself. For more detail about why,
  21 //!   see '[Implementing Iterator](#implementing-iterator)'.
  22 //!
  23 //! [Traits]: #traits
  24 //! [Functions]: #functions
  25 //! [Structs]: #structs
  26 //!
  27 //! That's it! Let's dig into iterators.
  28 //!
  29 //! # Iterator
  30 //!
  31 //! The heart and soul of this module is the [`Iterator`] trait. The core of
  32 //! [`Iterator`] looks like this:
  33 //!
  34 //! ```
  35 //! trait Iterator {
  36 //!     type Item;
  37 //!     fn next(&mut self) -> Option<Self::Item>;
  38 //! }
  39 //! ```
  40 //!
  41 //! An iterator has a method, [`next`], which when called, returns an
  42 //! [`Option`]`<Item>`. [`next`] will return `Some(Item)` as long as there
  43 //! are elements, and once they've all been exhausted, will return `None` to
  44 //! indicate that iteration is finished. Individual iterators may choose to
  45 //! resume iteration, and so calling [`next`] again may or may not eventually
  46 //! start returning `Some(Item)` again at some point (for example, see [`TryIter`]).
  47 //!
  48 //! [`Iterator`]'s full definition includes a number of other methods as well,
  49 //! but they are default methods, built on top of [`next`], and so you get
  50 //! them for free.
  51 //!
  52 //! Iterators are also composable, and it's common to chain them together to do
  53 //! more complex forms of processing. See the [Adapters](#adapters) section
  54 //! below for more details.
  55 //!
  56 //! [`Iterator`]: trait.Iterator.html
  57 //! [`next`]: trait.Iterator.html#tymethod.next
  58 //! [`Option`]: ../../std/option/enum.Option.html
  59 //! [`TryIter`]: ../../std/sync/mpsc/struct.TryIter.html
  60 //!
  61 //! # The three forms of iteration
  62 //!
  63 //! There are three common methods which can create iterators from a collection:
  64 //!
  65 //! * `iter()`, which iterates over `&T`.
  66 //! * `iter_mut()`, which iterates over `&mut T`.
  67 //! * `into_iter()`, which iterates over `T`.
  68 //!
  69 //! Various things in the standard library may implement one or more of the
  70 //! three, where appropriate.
  71 //!
  72 //! # Implementing Iterator
  73 //!
  74 //! Creating an iterator of your own involves two steps: creating a `struct` to
  75 //! hold the iterator's state, and then `impl`ementing [`Iterator`] for that
  76 //! `struct`. This is why there are so many `struct`s in this module: there is
  77 //! one for each iterator and iterator adapter.
  78 //!
  79 //! Let's make an iterator named `Counter` which counts from `1` to `5`:
  80 //!
  81 //! ```
  82 //! // First, the struct:
  83 //!
  84 //! /// An iterator which counts from one to five
  85 //! struct Counter {
  86 //!     count: usize,
  87 //! }
  88 //!
  89 //! // we want our count to start at one, so let's add a new() method to help.
  90 //! // This isn't strictly necessary, but is convenient. Note that we start
  91 //! // `count` at zero, we'll see why in `next()`'s implementation below.
  92 //! impl Counter {
  93 //!     fn new() -> Counter {
  94 //!         Counter { count: 0 }
  95 //!     }
  96 //! }
  97 //!
  98 //! // Then, we implement `Iterator` for our `Counter`:
  99 //!
 100 //! impl Iterator for Counter {
 101 //!     // we will be counting with usize
 102 //!     type Item = usize;
 103 //!
 104 //!     // next() is the only required method
 105 //!     fn next(&mut self) -> Option<Self::Item> {
 106 //!         // Increment our count. This is why we started at zero.
 107 //!         self.count += 1;
 108 //!
 109 //!         // Check to see if we've finished counting or not.
 110 //!         if self.count < 6 {
 111 //!             Some(self.count)
 112 //!         } else {
 113 //!             None
 114 //!         }
 115 //!     }
 116 //! }
 117 //!
 118 //! // And now we can use it!
 119 //!
 120 //! let mut counter = Counter::new();
 121 //!
 122 //! assert_eq!(counter.next(), Some(1));
 123 //! assert_eq!(counter.next(), Some(2));
 124 //! assert_eq!(counter.next(), Some(3));
 125 //! assert_eq!(counter.next(), Some(4));
 126 //! assert_eq!(counter.next(), Some(5));
 127 //! assert_eq!(counter.next(), None);
 128 //! ```
 129 //!
 130 //! Calling [`next`] this way gets repetitive. Rust has a construct which can
 131 //! call [`next`] on your iterator, until it reaches `None`. Let's go over that
 132 //! next.
 133 //!
 134 //! Also note that `Iterator` provides a default implementation of methods such as `nth` and `fold`
 135 //! which call `next` internally. However, it is also possible to write a custom implementation of
 136 //! methods like `nth` and `fold` if an iterator can compute them more efficiently without calling
 137 //! `next`.
 138 //!
 139 //! # for Loops and IntoIterator
 140 //!
 141 //! Rust's `for` loop syntax is actually sugar for iterators. Here's a basic
 142 //! example of `for`:
 143 //!
 144 //! ```
 145 //! let values = vec![1, 2, 3, 4, 5];
 146 //!
 147 //! for x in values {
 148 //!     println!("{}", x);
 149 //! }
 150 //! ```
 151 //!
 152 //! This will print the numbers one through five, each on their own line. But
 153 //! you'll notice something here: we never called anything on our vector to
 154 //! produce an iterator. What gives?
 155 //!
 156 //! There's a trait in the standard library for converting something into an
 157 //! iterator: [`IntoIterator`]. This trait has one method, [`into_iter`],
 158 //! which converts the thing implementing [`IntoIterator`] into an iterator.
 159 //! Let's take a look at that `for` loop again, and what the compiler converts
 160 //! it into:
 161 //!
 162 //! [`IntoIterator`]: trait.IntoIterator.html
 163 //! [`into_iter`]: trait.IntoIterator.html#tymethod.into_iter
 164 //!
 165 //! ```
 166 //! let values = vec![1, 2, 3, 4, 5];
 167 //!
 168 //! for x in values {
 169 //!     println!("{}", x);
 170 //! }
 171 //! ```
 172 //!
 173 //! Rust de-sugars this into:
 174 //!
 175 //! ```
 176 //! let values = vec![1, 2, 3, 4, 5];
 177 //! {
 178 //!     let result = match IntoIterator::into_iter(values) {
 179 //!         mut iter => loop {
 180 //!             let next;
 181 //!             match iter.next() {
 182 //!                 Some(val) => next = val,
 183 //!                 None => break,
 184 //!             };
 185 //!             let x = next;
 186 //!             let () = { println!("{}", x); };
 187 //!         },
 188 //!     };
 189 //!     result
 190 //! }
 191 //! ```
 192 //!
 193 //! First, we call `into_iter()` on the value. Then, we match on the iterator
 194 //! that returns, calling [`next`] over and over until we see a `None`. At
 195 //! that point, we `break` out of the loop, and we're done iterating.
 196 //!
 197 //! There's one more subtle bit here: the standard library contains an
 198 //! interesting implementation of [`IntoIterator`]:
 199 //!
 200 //! ```ignore (only-for-syntax-highlight)
 201 //! impl<I: Iterator> IntoIterator for I
 202 //! ```
 203 //!
 204 //! In other words, all [`Iterator`]s implement [`IntoIterator`], by just
 205 //! returning themselves. This means two things:
 206 //!
 207 //! 1. If you're writing an [`Iterator`], you can use it with a `for` loop.
 208 //! 2. If you're creating a collection, implementing [`IntoIterator`] for it
 209 //!    will allow your collection to be used with the `for` loop.
 210 //!
 211 //! # Adapters
 212 //!
 213 //! Functions which take an [`Iterator`] and return another [`Iterator`] are
 214 //! often called 'iterator adapters', as they're a form of the 'adapter
 215 //! pattern'.
 216 //!
 217 //! Common iterator adapters include [`map`], [`take`], and [`filter`].
 218 //! For more, see their documentation.
 219 //!
 220 //! If an iterator adapter panics, the iterator will be in an unspecified (but
 221 //! memory safe) state.  This state is also not guaranteed to stay the same
 222 //! across versions of Rust, so you should avoid relying on the exact values
 223 //! returned by an iterator which panicked.
 224 //!
 225 //! [`map`]: trait.Iterator.html#method.map
 226 //! [`take`]: trait.Iterator.html#method.take
 227 //! [`filter`]: trait.Iterator.html#method.filter
 228 //!
 229 //! # Laziness
 230 //!
 231 //! Iterators (and iterator [adapters](#adapters)) are *lazy*. This means that
 232 //! just creating an iterator doesn't _do_ a whole lot. Nothing really happens
 233 //! until you call [`next`]. This is sometimes a source of confusion when
 234 //! creating an iterator solely for its side effects. For example, the [`map`]
 235 //! method calls a closure on each element it iterates over:
 236 //!
 237 //! ```
 238 //! # #![allow(unused_must_use)]
 239 //! let v = vec![1, 2, 3, 4, 5];
 240 //! v.iter().map(|x| println!("{}", x));
 241 //! ```
 242 //!
 243 //! This will not print any values, as we only created an iterator, rather than
 244 //! using it. The compiler will warn us about this kind of behavior:
 245 //!
 246 //! ```text
 247 //! warning: unused result that must be used: iterators are lazy and
 248 //! do nothing unless consumed
 249 //! ```
 250 //!
 251 //! The idiomatic way to write a [`map`] for its side effects is to use a
 252 //! `for` loop or call the [`for_each`] method:
 253 //!
 254 //! ```
 255 //! let v = vec![1, 2, 3, 4, 5];
 256 //!
 257 //! v.iter().for_each(|x| println!("{}", x));
 258 //! // or
 259 //! for x in &v {
 260 //!     println!("{}", x);
 261 //! }
 262 //! ```
 263 //!
 264 //! [`map`]: trait.Iterator.html#method.map
 265 //! [`for_each`]: trait.Iterator.html#method.for_each
 266 //!
 267 //! Another common way to evaluate an iterator is to use the [`collect`]
 268 //! method to produce a new collection.
 269 //!
 270 //! [`collect`]: trait.Iterator.html#method.collect
 271 //!
 272 //! # Infinity
 273 //!
 274 //! Iterators do not have to be finite. As an example, an open-ended range is
 275 //! an infinite iterator:
 276 //!
 277 //! ```
 278 //! let numbers = 0..;
 279 //! ```
 280 //!
 281 //! It is common to use the [`take`] iterator adapter to turn an infinite
 282 //! iterator into a finite one:
 283 //!
 284 //! ```
 285 //! let numbers = 0..;
 286 //! let five_numbers = numbers.take(5);
 287 //!
 288 //! for number in five_numbers {
 289 //!     println!("{}", number);
 290 //! }
 291 //! ```
 292 //!
 293 //! This will print the numbers `0` through `4`, each on their own line.
 294 //!
 295 //! Bear in mind that methods on infinite iterators, even those for which a
 296 //! result can be determined mathematically in finite time, may not terminate.
 297 //! Specifically, methods such as [`min`], which in the general case require
 298 //! traversing every element in the iterator, are likely not to return
 299 //! successfully for any infinite iterators.
 300 //!
 301 //! ```no_run
 302 //! let ones = std::iter::repeat(1);
 303 //! let least = ones.min().unwrap(); // Oh no! An infinite loop!
 304 //! // `ones.min()` causes an infinite loop, so we won't reach this point!
 305 //! println!("The smallest number one is {}.", least);
 306 //! ```
 307 //!
 308 //! [`take`]: trait.Iterator.html#method.take
 309 //! [`min`]: trait.Iterator.html#method.min
 310
 311 #![stable(feature = "rust1", since = "1.0.0")]
 312
 313 use crate::ops::Try;
 314
 315 #[stable(feature = "rust1", since = "1.0.0")]
 316 pub use self::traits::Iterator;
 317
 318 #[unstable(
 319     feature = "step_trait",
 320     reason = "likely to be replaced by finer-grained traits",
 321     issue = "42168"
 322 )]
 323 pub use self::range::Step;
 324
 325 #[stable(feature = "iter_empty", since = "1.2.0")]
 326 pub use self::sources::{empty, Empty};
 327 #[stable(feature = "iter_from_fn", since = "1.34.0")]
 328 pub use self::sources::{from_fn, FromFn};
 329 #[stable(feature = "iter_once", since = "1.2.0")]
 330 pub use self::sources::{once, Once};
 331 #[stable(feature = "iter_once_with", since = "1.43.0")]
 332 pub use self::sources::{once_with, OnceWith};
 333 #[stable(feature = "rust1", since = "1.0.0")]
 334 pub use self::sources::{repeat, Repeat};
 335 #[stable(feature = "iterator_repeat_with", since = "1.28.0")]
 336 pub use self::sources::{repeat_with, RepeatWith};
 337 #[stable(feature = "iter_successors", since = "1.34.0")]
 338 pub use self::sources::{successors, Successors};
 339
 340 #[stable(feature = "fused", since = "1.26.0")]
 341 pub use self::traits::FusedIterator;
 342 #[unstable(feature = "trusted_len", issue = "37572")]
 343 pub use self::traits::TrustedLen;
 344 #[stable(feature = "rust1", since = "1.0.0")]
 345 pub use self::traits::{DoubleEndedIterator, Extend, FromIterator, IntoIterator};
 346 #[stable(feature = "rust1", since = "1.0.0")]
 347 pub use self::traits::{ExactSizeIterator, Product, Sum};
 348
 349 #[stable(feature = "iter_cloned", since = "1.1.0")]
 350 pub use self::adapters::Cloned;
 351 #[stable(feature = "iter_copied", since = "1.36.0")]
 352 pub use self::adapters::Copied;
 353 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 354 pub use self::adapters::Flatten;
 355 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
 356 pub use self::adapters::MapWhile;
 357 #[stable(feature = "iterator_step_by", since = "1.28.0")]
 358 pub use self::adapters::StepBy;
 359 #[stable(feature = "rust1", since = "1.0.0")]
 360 pub use self::adapters::{Chain, Cycle, Enumerate, Filter, FilterMap, Map, Rev, Zip};
 361 #[stable(feature = "rust1", since = "1.0.0")]
 362 pub use self::adapters::{FlatMap, Peekable, Scan, Skip, SkipWhile, Take, TakeWhile};
 363 #[stable(feature = "rust1", since = "1.0.0")]
 364 pub use self::adapters::{Fuse, Inspect};
 365
 366 pub(crate) use self::adapters::{process_results, TrustedRandomAccess};
 367
 368 mod adapters;
 369 mod range;
 370 mod sources;
 371 mod traits;
 372
 373 /// Used to make try_fold closures more like normal loops
 374 #[derive(PartialEq)]
 375 enum LoopState<C, B> {
 376     Continue(C),
 377     Break(B),
 378 }
 379
 380 impl<C, B> Try for LoopState<C, B> {
 381     type Ok = C;
 382     type Error = B;
 383     #[inline]
 384     fn into_result(self) -> Result<Self::Ok, Self::Error> {
 385         match self {
 386             LoopState::Continue(y) => Ok(y),
 387             LoopState::Break(x) => Err(x),
 388         }
 389     }
 390     #[inline]
 391     fn from_error(v: Self::Error) -> Self {
 392         LoopState::Break(v)
 393     }
 394     #[inline]
 395     fn from_ok(v: Self::Ok) -> Self {
 396         LoopState::Continue(v)
 397     }
 398 }
 399
 400 impl<C, B> LoopState<C, B> {
 401     #[inline]
 402     fn break_value(self) -> Option<B> {
 403         match self {
 404             LoopState::Continue(..) => None,
 405             LoopState::Break(x) => Some(x),
 406         }
 407     }
 408 }
 409
 410 impl<R: Try> LoopState<R::Ok, R> {
 411     #[inline]
 412     fn from_try(r: R) -> Self {
 413         match Try::into_result(r) {
 414             Ok(v) => LoopState::Continue(v),
 415             Err(v) => LoopState::Break(Try::from_error(v)),
 416         }
 417     }
 418     #[inline]
 419     fn into_try(self) -> R {
 420         match self {
 421             LoopState::Continue(v) => Try::from_ok(v),
 422             LoopState::Break(v) => v,
 423         }
 424     }
 425 }