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//! <code>[Option]\<Item></code>. Calling [`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//! [`Some(Item)`]: Some
57//! [`next`]: Iterator::next
58//! [`TryIter`]: ../../std/sync/mpsc/struct.TryIter.html
59//!
60//! # The three forms of iteration
61//!
62//! There are three common methods which can create iterators from a collection:
63//!
64//! * `iter()`, which iterates over `&T`.
65//! * `iter_mut()`, which iterates over `&mut T`.
66//! * `into_iter()`, which iterates over `T`.
67//!
68//! Various things in the standard library may implement one or more of the
69//! three, where appropriate.
70//!
71//! # Implementing Iterator
72//!
73//! Creating an iterator of your own involves two steps: creating a `struct` to
74//! hold the iterator's state, and then implementing [`Iterator`] for that `struct`.
75//! This is why there are so many `struct`s in this module: there is one for
76//! each iterator and iterator adapter.
77//!
78//! Let's make an iterator named `Counter` which counts from `1` to `5`:
79//!
80//! ```
81//! // First, the struct:
82//!
83//! /// An iterator which counts from one to five
84//! struct Counter {
85//! count: usize,
86//! }
87//!
88//! // we want our count to start at one, so let's add a new() method to help.
89//! // This isn't strictly necessary, but is convenient. Note that we start
90//! // `count` at zero, we'll see why in `next()`'s implementation below.
91//! impl Counter {
92//! fn new() -> Counter {
93//! Counter { count: 0 }
94//! }
95//! }
96//!
97//! // Then, we implement `Iterator` for our `Counter`:
98//!
99//! impl Iterator for Counter {
100//! // we will be counting with usize
101//! type Item = usize;
102//!
103//! // next() is the only required method
104//! fn next(&mut self) -> Option<Self::Item> {
105//! // Increment our count. This is why we started at zero.
106//! self.count += 1;
107//!
108//! // Check to see if we've finished counting or not.
109//! if self.count < 6 {
110//! Some(self.count)
111//! } else {
112//! None
113//! }
114//! }
115//! }
116//!
117//! // And now we can use it!
118//!
119//! let mut counter = Counter::new();
120//!
121//! assert_eq!(counter.next(), Some(1));
122//! assert_eq!(counter.next(), Some(2));
123//! assert_eq!(counter.next(), Some(3));
124//! assert_eq!(counter.next(), Some(4));
125//! assert_eq!(counter.next(), Some(5));
126//! assert_eq!(counter.next(), None);
127//! ```
128//!
129//! Calling [`next`] this way gets repetitive. Rust has a construct which can
130//! call [`next`] on your iterator, until it reaches `None`. Let's go over that
131//! next.
132//!
133//! Also note that `Iterator` provides a default implementation of methods such as `nth` and `fold`
134//! which call `next` internally. However, it is also possible to write a custom implementation of
135//! methods like `nth` and `fold` if an iterator can compute them more efficiently without calling
136//! `next`.
137//!
138//! # `for` loops and `IntoIterator`
139//!
140//! Rust's `for` loop syntax is actually sugar for iterators. Here's a basic
141//! example of `for`:
142//!
143//! ```
144//! let values = vec![1, 2, 3, 4, 5];
145//!
146//! for x in values {
147//! println!("{x}");
148//! }
149//! ```
150//!
151//! This will print the numbers one through five, each on their own line. But
152//! you'll notice something here: we never called anything on our vector to
153//! produce an iterator. What gives?
154//!
155//! There's a trait in the standard library for converting something into an
156//! iterator: [`IntoIterator`]. This trait has one method, [`into_iter`],
157//! which converts the thing implementing [`IntoIterator`] into an iterator.
158//! Let's take a look at that `for` loop again, and what the compiler converts
159//! it into:
160//!
161//! [`into_iter`]: IntoIterator::into_iter
162//!
163//! ```
164//! let values = vec![1, 2, 3, 4, 5];
165//!
166//! for x in values {
167//! println!("{x}");
168//! }
169//! ```
170//!
171//! Rust de-sugars this into:
172//!
173//! ```
174//! let values = vec![1, 2, 3, 4, 5];
175//! {
176//! let result = match IntoIterator::into_iter(values) {
177//! mut iter => loop {
178//! let next;
179//! match iter.next() {
180//! Some(val) => next = val,
181//! None => break,
182//! };
183//! let x = next;
184//! let () = { println!("{x}"); };
185//! },
186//! };
187//! result
188//! }
189//! ```
190//!
191//! First, we call `into_iter()` on the value. Then, we match on the iterator
192//! that returns, calling [`next`] over and over until we see a `None`. At
193//! that point, we `break` out of the loop, and we're done iterating.
194//!
195//! There's one more subtle bit here: the standard library contains an
196//! interesting implementation of [`IntoIterator`]:
197//!
198//! ```ignore (only-for-syntax-highlight)
199//! impl<I: Iterator> IntoIterator for I
200//! ```
201//!
202//! In other words, all [`Iterator`]s implement [`IntoIterator`], by just
203//! returning themselves. This means two things:
204//!
205//! 1. If you're writing an [`Iterator`], you can use it with a `for` loop.
206//! 2. If you're creating a collection, implementing [`IntoIterator`] for it
207//! will allow your collection to be used with the `for` loop.
208//!
209//! # Iterating by reference
210//!
211//! Since [`into_iter()`] takes `self` by value, using a `for` loop to iterate
212//! over a collection consumes that collection. Often, you may want to iterate
213//! over a collection without consuming it. Many collections offer methods that
214//! provide iterators over references, conventionally called `iter()` and
215//! `iter_mut()` respectively:
216//!
217//! ```
218//! let mut values = vec![41];
219//! for x in values.iter_mut() {
220//! *x += 1;
221//! }
222//! for x in values.iter() {
223//! assert_eq!(*x, 42);
224//! }
225//! assert_eq!(values.len(), 1); // `values` is still owned by this function.
226//! ```
227//!
228//! If a collection type `C` provides `iter()`, it usually also implements
229//! `IntoIterator` for `&C`, with an implementation that just calls `iter()`.
230//! Likewise, a collection `C` that provides `iter_mut()` generally implements
231//! `IntoIterator` for `&mut C` by delegating to `iter_mut()`. This enables a
232//! convenient shorthand:
233//!
234//! ```
235//! let mut values = vec![41];
236//! for x in &mut values { // same as `values.iter_mut()`
237//! *x += 1;
238//! }
239//! for x in &values { // same as `values.iter()`
240//! assert_eq!(*x, 42);
241//! }
242//! assert_eq!(values.len(), 1);
243//! ```
244//!
245//! While many collections offer `iter()`, not all offer `iter_mut()`. For
246//! example, mutating the keys of a [`HashSet<T>`] could put the collection
247//! into an inconsistent state if the key hashes change, so this collection
248//! only offers `iter()`.
249//!
250//! [`into_iter()`]: IntoIterator::into_iter
251//! [`HashSet<T>`]: ../../std/collections/struct.HashSet.html
252//!
253//! # Adapters
254//!
255//! Functions which take an [`Iterator`] and return another [`Iterator`] are
256//! often called 'iterator adapters', as they're a form of the 'adapter
257//! pattern'.
258//!
259//! Common iterator adapters include [`map`], [`take`], and [`filter`].
260//! For more, see their documentation.
261//!
262//! If an iterator adapter panics, the iterator will be in an unspecified (but
263//! memory safe) state. This state is also not guaranteed to stay the same
264//! across versions of Rust, so you should avoid relying on the exact values
265//! returned by an iterator which panicked.
266//!
267//! [`map`]: Iterator::map
268//! [`take`]: Iterator::take
269//! [`filter`]: Iterator::filter
270//!
271//! # Laziness
272//!
273//! Iterators (and iterator [adapters](#adapters)) are *lazy*. This means that
274//! just creating an iterator doesn't _do_ a whole lot. Nothing really happens
275//! until you call [`next`]. This is sometimes a source of confusion when
276//! creating an iterator solely for its side effects. For example, the [`map`]
277//! method calls a closure on each element it iterates over:
278//!
279//! ```
280//! # #![allow(unused_must_use)]
281//! # #![allow(map_unit_fn)]
282//! let v = vec![1, 2, 3, 4, 5];
283//! v.iter().map(|x| println!("{x}"));
284//! ```
285//!
286//! This will not print any values, as we only created an iterator, rather than
287//! using it. The compiler will warn us about this kind of behavior:
288//!
289//! ```text
290//! warning: unused result that must be used: iterators are lazy and
291//! do nothing unless consumed
292//! ```
293//!
294//! The idiomatic way to write a [`map`] for its side effects is to use a
295//! `for` loop or call the [`for_each`] method:
296//!
297//! ```
298//! let v = vec![1, 2, 3, 4, 5];
299//!
300//! v.iter().for_each(|x| println!("{x}"));
301//! // or
302//! for x in &v {
303//! println!("{x}");
304//! }
305//! ```
306//!
307//! [`map`]: Iterator::map
308//! [`for_each`]: Iterator::for_each
309//!
310//! Another common way to evaluate an iterator is to use the [`collect`]
311//! method to produce a new collection.
312//!
313//! [`collect`]: Iterator::collect
314//!
315//! # Infinity
316//!
317//! Iterators do not have to be finite. As an example, an open-ended range is
318//! an infinite iterator:
319//!
320//! ```
321//! let numbers = 0..;
322//! ```
323//!
324//! It is common to use the [`take`] iterator adapter to turn an infinite
325//! iterator into a finite one:
326//!
327//! ```
328//! let numbers = 0..;
329//! let five_numbers = numbers.take(5);
330//!
331//! for number in five_numbers {
332//! println!("{number}");
333//! }
334//! ```
335//!
336//! This will print the numbers `0` through `4`, each on their own line.
337//!
338//! Bear in mind that methods on infinite iterators, even those for which a
339//! result can be determined mathematically in finite time, might not terminate.
340//! Specifically, methods such as [`min`], which in the general case require
341//! traversing every element in the iterator, are likely not to return
342//! successfully for any infinite iterators.
343//!
344//! ```no_run
345//! let ones = std::iter::repeat(1);
346//! let least = ones.min().unwrap(); // Oh no! An infinite loop!
347//! // `ones.min()` causes an infinite loop, so we won't reach this point!
348//! println!("The smallest number one is {least}.");
349//! ```
350//!
351//! [`take`]: Iterator::take
352//! [`min`]: Iterator::min
353
354#![stable(feature = "rust1", since = "1.0.0")]
355
356// This needs to be up here in order to be usable in the child modules
357macro_rules! impl_fold_via_try_fold {
358 (fold -> try_fold) => {
359 impl_fold_via_try_fold! { @internal fold -> try_fold }
360 };
361 (rfold -> try_rfold) => {
362 impl_fold_via_try_fold! { @internal rfold -> try_rfold }
363 };
364 (spec_fold -> spec_try_fold) => {
365 impl_fold_via_try_fold! { @internal spec_fold -> spec_try_fold }
366 };
367 (spec_rfold -> spec_try_rfold) => {
368 impl_fold_via_try_fold! { @internal spec_rfold -> spec_try_rfold }
369 };
370 (@internal $fold:ident -> $try_fold:ident) => {
371 #[inline]
372 fn $fold<AAA, FFF>(mut self, init: AAA, fold: FFF) -> AAA
373 where
374 FFF: FnMut(AAA, Self::Item) -> AAA,
375 {
376 use crate::ops::NeverShortCircuit;
377
378 self.$try_fold(init, NeverShortCircuit::wrap_mut_2(fold)).0
379 }
380 };
381}
382
383#[stable(feature = "rust1", since = "1.0.0")]
384pub use self::traits::Iterator;
385
386#[unstable(
387 feature = "step_trait",
388 reason = "likely to be replaced by finer-grained traits",
389 issue = "42168"
390)]
391pub use self::range::Step;
392
393#[unstable(
394 feature = "iter_from_coroutine",
395 issue = "43122",
396 reason = "coroutines are unstable"
397)]
398pub use self::sources::from_coroutine;
399#[stable(feature = "iter_empty", since = "1.2.0")]
400pub use self::sources::{empty, Empty};
401#[stable(feature = "iter_from_fn", since = "1.34.0")]
402pub use self::sources::{from_fn, FromFn};
403#[stable(feature = "iter_once", since = "1.2.0")]
404pub use self::sources::{once, Once};
405#[stable(feature = "iter_once_with", since = "1.43.0")]
406pub use self::sources::{once_with, OnceWith};
407#[stable(feature = "rust1", since = "1.0.0")]
408pub use self::sources::{repeat, Repeat};
409#[unstable(feature = "iter_repeat_n", issue = "104434")]
410pub use self::sources::{repeat_n, RepeatN};
411#[stable(feature = "iterator_repeat_with", since = "1.28.0")]
412pub use self::sources::{repeat_with, RepeatWith};
413#[stable(feature = "iter_successors", since = "1.34.0")]
414pub use self::sources::{successors, Successors};
415
416#[stable(feature = "fused", since = "1.26.0")]
417pub use self::traits::FusedIterator;
418#[unstable(issue = "none", feature = "inplace_iteration")]
419pub use self::traits::InPlaceIterable;
420#[unstable(issue = "none", feature = "trusted_fused")]
421pub use self::traits::TrustedFused;
422#[unstable(feature = "trusted_len", issue = "37572")]
423pub use self::traits::TrustedLen;
424#[unstable(feature = "trusted_step", issue = "85731")]
425pub use self::traits::TrustedStep;
426#[stable(feature = "rust1", since = "1.0.0")]
427pub use self::traits::{
428 DoubleEndedIterator, ExactSizeIterator, Extend, FromIterator, IntoIterator, Product, Sum,
429};
430
431#[stable(feature = "iter_zip", since = "1.59.0")]
432pub use self::adapters::zip;
433#[unstable(feature = "iter_array_chunks", reason = "recently added", issue = "100450")]
434pub use self::adapters::ArrayChunks;
435#[unstable(feature = "std_internals", issue = "none")]
436pub use self::adapters::ByRefSized;
437#[stable(feature = "iter_cloned", since = "1.1.0")]
438pub use self::adapters::Cloned;
439#[stable(feature = "iter_copied", since = "1.36.0")]
440pub use self::adapters::Copied;
441#[stable(feature = "iterator_flatten", since = "1.29.0")]
442pub use self::adapters::Flatten;
443#[stable(feature = "iter_map_while", since = "1.57.0")]
444pub use self::adapters::MapWhile;
445#[unstable(feature = "iter_map_windows", reason = "recently added", issue = "87155")]
446pub use self::adapters::MapWindows;
447#[unstable(feature = "inplace_iteration", issue = "none")]
448pub use self::adapters::SourceIter;
449#[stable(feature = "iterator_step_by", since = "1.28.0")]
450pub use self::adapters::StepBy;
451#[unstable(feature = "trusted_random_access", issue = "none")]
452pub use self::adapters::TrustedRandomAccess;
453#[unstable(feature = "trusted_random_access", issue = "none")]
454pub use self::adapters::TrustedRandomAccessNoCoerce;
455#[stable(feature = "rust1", since = "1.0.0")]
456pub use self::adapters::{
457 Chain, Cycle, Enumerate, Filter, FilterMap, FlatMap, Fuse, Inspect, Map, Peekable, Rev, Scan,
458 Skip, SkipWhile, Take, TakeWhile, Zip,
459};
460#[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
461pub use self::adapters::{Intersperse, IntersperseWith};
462
463pub(crate) use self::adapters::try_process;
464pub(crate) use self::traits::UncheckedIterator;
465
466mod adapters;
467mod range;
468mod sources;
469mod traits;
470