library/core/src/iter/adapters/mod.rs

   1 use crate::iter::{InPlaceIterable, Iterator};
   2 use crate::ops::{ChangeOutputType, ControlFlow, FromResidual, Residual, Try};
   3
   4 mod array_chunks;
   5 mod by_ref_sized;
   6 mod chain;
   7 mod cloned;
   8 mod copied;
   9 mod cycle;
  10 mod enumerate;
  11 mod filter;
  12 mod filter_map;
  13 mod flatten;
  14 mod fuse;
  15 mod inspect;
  16 mod intersperse;
  17 mod map;
  18 mod map_while;
  19 mod peekable;
  20 mod rev;
  21 mod scan;
  22 mod skip;
  23 mod skip_while;
  24 mod step_by;
  25 mod take;
  26 mod take_while;
  27 mod zip;
  28
  29 #[stable(feature = "rust1", since = "1.0.0")]
  30 pub use self::{
  31     chain::Chain, cycle::Cycle, enumerate::Enumerate, filter::Filter, filter_map::FilterMap,
  32     flatten::FlatMap, fuse::Fuse, inspect::Inspect, map::Map, peekable::Peekable, rev::Rev,
  33     scan::Scan, skip::Skip, skip_while::SkipWhile, take::Take, take_while::TakeWhile, zip::Zip,
  34 };
  35
  36 #[unstable(feature = "iter_array_chunks", reason = "recently added", issue = "100450")]
  37 pub use self::array_chunks::ArrayChunks;
  38
  39 #[unstable(feature = "std_internals", issue = "none")]
  40 pub use self::by_ref_sized::ByRefSized;
  41
  42 #[stable(feature = "iter_cloned", since = "1.1.0")]
  43 pub use self::cloned::Cloned;
  44
  45 #[stable(feature = "iterator_step_by", since = "1.28.0")]
  46 pub use self::step_by::StepBy;
  47
  48 #[stable(feature = "iterator_flatten", since = "1.29.0")]
  49 pub use self::flatten::Flatten;
  50
  51 #[stable(feature = "iter_copied", since = "1.36.0")]
  52 pub use self::copied::Copied;
  53
  54 #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
  55 pub use self::intersperse::{Intersperse, IntersperseWith};
  56
  57 #[stable(feature = "iter_map_while", since = "1.57.0")]
  58 pub use self::map_while::MapWhile;
  59
  60 #[unstable(feature = "trusted_random_access", issue = "none")]
  61 pub use self::zip::TrustedRandomAccess;
  62
  63 #[unstable(feature = "trusted_random_access", issue = "none")]
  64 pub use self::zip::TrustedRandomAccessNoCoerce;
  65
  66 #[stable(feature = "iter_zip", since = "1.59.0")]
  67 pub use self::zip::zip;
  68
  69 /// This trait provides transitive access to source-stage in an iterator-adapter pipeline
  70 /// under the conditions that
  71 /// * the iterator source `S` itself implements `SourceIter<Source = S>`
  72 /// * there is a delegating implementation of this trait for each adapter in the pipeline between
  73 ///   the source and the pipeline consumer.
  74 ///
  75 /// When the source is an owning iterator struct (commonly called `IntoIter`) then
  76 /// this can be useful for specializing [`FromIterator`] implementations or recovering the
  77 /// remaining elements after an iterator has been partially exhausted.
  78 ///
  79 /// Note that implementations do not necessarily have to provide access to the inner-most
  80 /// source of a pipeline. A stateful intermediate adapter might eagerly evaluate a part
  81 /// of the pipeline and expose its internal storage as source.
  82 ///
  83 /// The trait is unsafe because implementers must uphold additional safety properties.
  84 /// See [`as_inner`] for details.
  85 ///
  86 /// The primary use of this trait is in-place iteration. Refer to the [`vec::in_place_collect`]
  87 /// module documentation for more information.
  88 ///
  89 /// [`vec::in_place_collect`]: ../../../../alloc/vec/in_place_collect/index.html
  90 ///
  91 /// # Examples
  92 ///
  93 /// Retrieving a partially consumed source:
  94 ///
  95 /// ```
  96 /// # #![feature(inplace_iteration)]
  97 /// # use std::iter::SourceIter;
  98 ///
  99 /// let mut iter = vec![9, 9, 9].into_iter().map(|i| i * i);
 100 /// let _ = iter.next();
 101 /// let mut remainder = std::mem::replace(unsafe { iter.as_inner() }, Vec::new().into_iter());
 102 /// println!("n = {} elements remaining", remainder.len());
 103 /// ```
 104 ///
 105 /// [`FromIterator`]: crate::iter::FromIterator
 106 /// [`as_inner`]: SourceIter::as_inner
 107 #[unstable(issue = "none", feature = "inplace_iteration")]
 108 #[doc(hidden)]
 109 #[rustc_specialization_trait]
 110 pub unsafe trait SourceIter {
 111     /// A source stage in an iterator pipeline.
 112     type Source;
 113
 114     /// Retrieve the source of an iterator pipeline.
 115     ///
 116     /// # Safety
 117     ///
 118     /// Implementations of must return the same mutable reference for their lifetime, unless
 119     /// replaced by a caller.
 120     /// Callers may only replace the reference when they stopped iteration and drop the
 121     /// iterator pipeline after extracting the source.
 122     ///
 123     /// This means iterator adapters can rely on the source not changing during
 124     /// iteration but they cannot rely on it in their Drop implementations.
 125     ///
 126     /// Implementing this method means adapters relinquish private-only access to their
 127     /// source and can only rely on guarantees made based on method receiver types.
 128     /// The lack of restricted access also requires that adapters must uphold the source's
 129     /// public API even when they have access to its internals.
 130     ///
 131     /// Callers in turn must expect the source to be in any state that is consistent with
 132     /// its public API since adapters sitting between it and the source have the same
 133     /// access. In particular an adapter may have consumed more elements than strictly necessary.
 134     ///
 135     /// The overall goal of these requirements is to let the consumer of a pipeline use
 136     /// * whatever remains in the source after iteration has stopped
 137     /// * the memory that has become unused by advancing a consuming iterator
 138     ///
 139     /// [`next()`]: Iterator::next()
 140     unsafe fn as_inner(&mut self) -> &mut Self::Source;
 141 }
 142
 143 /// An iterator adapter that produces output as long as the underlying
 144 /// iterator produces values where `Try::branch` says to `ControlFlow::Continue`.
 145 ///
 146 /// If a `ControlFlow::Break` is encountered, the iterator stops and the
 147 /// residual is stored.
 148 pub(crate) struct GenericShunt<'a, I, R> {
 149     iter: I,
 150     residual: &'a mut Option<R>,
 151 }
 152
 153 /// Process the given iterator as if it yielded a the item's `Try::Output`
 154 /// type instead. Any `Try::Residual`s encountered will stop the inner iterator
 155 /// and be propagated back to the overall result.
 156 pub(crate) fn try_process<I, T, R, F, U>(iter: I, mut f: F) -> ChangeOutputType<I::Item, U>
 157 where
 158     I: Iterator<Item: Try<Output = T, Residual = R>>,
 159     for<'a> F: FnMut(GenericShunt<'a, I, R>) -> U,
 160     R: Residual<U>,
 161 {
 162     let mut residual = None;
 163     let shunt = GenericShunt { iter, residual: &mut residual };
 164     let value = f(shunt);
 165     match residual {
 166         Some(r) => FromResidual::from_residual(r),
 167         None => Try::from_output(value),
 168     }
 169 }
 170
 171 impl<I, R> Iterator for GenericShunt<'_, I, R>
 172 where
 173     I: Iterator<Item: Try<Residual = R>>,
 174 {
 175     type Item = <I::Item as Try>::Output;
 176
 177     fn next(&mut self) -> Option<Self::Item> {
 178         self.try_for_each(ControlFlow::Break).break_value()
 179     }
 180
 181     fn size_hint(&self) -> (usize, Option<usize>) {
 182         if self.residual.is_some() {
 183             (0, Some(0))
 184         } else {
 185             let (_, upper) = self.iter.size_hint();
 186             (0, upper)
 187         }
 188     }
 189
 190     fn try_fold<B, F, T>(&mut self, init: B, mut f: F) -> T
 191     where
 192         F: FnMut(B, Self::Item) -> T,
 193         T: Try<Output = B>,
 194     {
 195         self.iter
 196             .try_fold(init, |acc, x| match Try::branch(x) {
 197                 ControlFlow::Continue(x) => ControlFlow::from_try(f(acc, x)),
 198                 ControlFlow::Break(r) => {
 199                     *self.residual = Some(r);
 200                     ControlFlow::Break(try { acc })
 201                 }
 202             })
 203             .into_try()
 204     }
 205
 206     impl_fold_via_try_fold! { fold -> try_fold }
 207 }
 208
 209 #[unstable(issue = "none", feature = "inplace_iteration")]
 210 unsafe impl<I, R> SourceIter for GenericShunt<'_, I, R>
 211 where
 212     I: SourceIter,
 213 {
 214     type Source = I::Source;
 215
 216     #[inline]
 217     unsafe fn as_inner(&mut self) -> &mut Self::Source {
 218         // SAFETY: unsafe function forwarding to unsafe function with the same requirements
 219         unsafe { SourceIter::as_inner(&mut self.iter) }
 220     }
 221 }
 222
 223 // SAFETY: GenericShunt::next calls `I::try_for_each`, which has to advance `iter`
 224 // in order to return `Some(_)`. Since `iter` has type `I: InPlaceIterable` it's
 225 // guaranteed that at least one item will be moved out from the underlying source.
 226 #[unstable(issue = "none", feature = "inplace_iteration")]
 227 unsafe impl<I, T, R> InPlaceIterable for GenericShunt<'_, I, R> where
 228     I: Iterator<Item: Try<Output = T, Residual = R>> + InPlaceIterable
 229 {
 230 }