Revision control
Copy as Markdown
Other Tools
//! Fallible, streaming iteration.
//!
//! `FallibleStreamingIterator` differs from the standard library's `Iterator` trait in two ways:
//! iteration can fail, resulting in an error, and only one element of the iteration is available at
//! any time.
//!
//! While these iterators cannot be used with Rust `for` loops, `while let` loops offer a similar
//! level of ergonomics:
//!
//! ```ignore
//! while let Some(value) = it.next()? {
//! // use value
//! }
//! ```
#![warn(missing_docs)]
#![cfg_attr(not(feature = "std"), no_std)]
#[cfg(feature = "std")]
extern crate core;
use core::cmp;
use core::marker::PhantomData;
/// A fallible, streaming iterator.
pub trait FallibleStreamingIterator {
/// The type being iterated over.
type Item: ?Sized;
/// The error type of iteration.
type Error;
/// Advances the iterator to the next position.
///
/// Iterators start just before the first item, so this method should be called before `get`
/// when iterating.
///
/// The behavior of calling this method after `get` has returned `None`, or after this method
/// has returned an error is unspecified.
fn advance(&mut self) -> Result<(), Self::Error>;
/// Returns the current element.
///
/// The behavior of calling this method before any calls to `advance` is unspecified.
fn get(&self) -> Option<&Self::Item>;
/// Advances the iterator, returning the next element.
///
/// The default implementation simply calls `advance` followed by `get`.
#[inline]
fn next(&mut self) -> Result<Option<&Self::Item>, Self::Error> {
self.advance()?;
Ok((*self).get())
}
/// Returns bounds on the number of remaining elements in the iterator.
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(0, None)
}
/// Determines if all elements of the iterator satisfy a predicate.
#[inline]
fn all<F>(&mut self, mut f: F) -> Result<bool, Self::Error>
where
Self: Sized,
F: FnMut(&Self::Item) -> bool,
{
while let Some(e) = self.next()? {
if !f(e) {
return Ok(false);
}
}
Ok(true)
}
/// Determines if any elements of the iterator satisfy a predicate.
#[inline]
fn any<F>(&mut self, mut f: F) -> Result<bool, Self::Error>
where
Self: Sized,
F: FnMut(&Self::Item) -> bool,
{
self.all(|e| !f(e)).map(|r| !r)
}
/// Borrows an iterator, rather than consuming it.
///
/// This is useful to allow the application of iterator adaptors while still retaining ownership
/// of the original adaptor.
#[inline]
fn by_ref(&mut self) -> &mut Self
where
Self: Sized,
{
self
}
/// Returns the number of remaining elements in the iterator.
#[inline]
fn count(mut self) -> Result<usize, Self::Error>
where
Self: Sized,
{
let mut count = 0;
while let Some(_) = self.next()? {
count += 1;
}
Ok(count)
}
/// Returns an iterator which filters elements by a predicate.
#[inline]
fn filter<F>(self, f: F) -> Filter<Self, F>
where
Self: Sized,
F: FnMut(&Self::Item) -> bool,
{
Filter { it: self, f: f }
}
/// Returns the first element of the iterator which satisfies a predicate.
#[inline]
fn find<F>(&mut self, mut f: F) -> Result<Option<&Self::Item>, Self::Error>
where
Self: Sized,
F: FnMut(&Self::Item) -> bool,
{
loop {
self.advance()?;
match self.get() {
Some(v) => {
if f(v) {
break;
}
}
None => break,
}
}
Ok((*self).get())
}
/// Calls a closure on each element of an iterator.
#[inline]
fn for_each<F>(mut self, mut f: F) -> Result<(), Self::Error>
where
Self: Sized,
F: FnMut(&Self::Item),
{
while let Some(value) = self.next()? {
f(value);
}
Ok(())
}
/// Returns an iterator which is well-behaved at the beginning and end of iteration.
#[inline]
fn fuse(self) -> Fuse<Self>
where
Self: Sized,
{
Fuse {
it: self,
state: FuseState::Start,
}
}
/// Returns an iterator which applies a transform to elements.
#[inline]
fn map<F, B>(self, f: F) -> Map<Self, F, B>
where
Self: Sized,
F: FnMut(&Self::Item) -> B,
{
Map {
it: self,
f: f,
value: None,
}
}
/// Returns an iterator which applies a transform to elements.
///
/// Unlike `map`, the the closure provided to this method returns a reference into the original
/// value.
#[inline]
fn map_ref<F, B: ?Sized>(self, f: F) -> MapRef<Self, F>
where
Self: Sized,
F: Fn(&Self::Item) -> &B,
{
MapRef { it: self, f: f }
}
/// Returns an iterator that applies a transform to errors.
#[inline]
fn map_err<F, B>(self, f: F) -> MapErr<Self, F>
where
Self: Sized,
F: Fn(Self::Error) -> B,
{
MapErr { it: self, f: f }
}
/// Returns the `nth` element of the iterator.
#[inline]
fn nth(&mut self, n: usize) -> Result<Option<&Self::Item>, Self::Error> {
for _ in 0..n {
self.advance()?;
if let None = self.get() {
return Ok(None);
}
}
self.next()
}
/// Returns the position of the first element matching a predicate.
#[inline]
fn position<F>(&mut self, mut f: F) -> Result<Option<usize>, Self::Error>
where
Self: Sized,
F: FnMut(&Self::Item) -> bool,
{
let mut pos = 0;
while let Some(v) = self.next()? {
if f(v) {
return Ok(Some(pos));
}
pos += 1;
}
Ok(None)
}
/// Returns an iterator which skips the first `n` elements.
#[inline]
fn skip(self, n: usize) -> Skip<Self>
where
Self: Sized,
{
Skip { it: self, n: n }
}
/// Returns an iterator which skips the first sequence of elements matching a predicate.
#[inline]
fn skip_while<F>(self, f: F) -> SkipWhile<Self, F>
where
Self: Sized,
F: FnMut(&Self::Item) -> bool,
{
SkipWhile {
it: self,
f: f,
done: false,
}
}
/// Returns an iterator which only returns the first `n` elements.
#[inline]
fn take(self, n: usize) -> Take<Self>
where
Self: Sized,
{
Take {
it: self,
n: n,
done: false,
}
}
/// Returns an iterator which only returns the first sequence of elements matching a predicate.
#[inline]
fn take_while<F>(self, f: F) -> TakeWhile<Self, F>
where
Self: Sized,
F: FnMut(&Self::Item) -> bool,
{
TakeWhile {
it: self,
f: f,
done: false,
}
}
}
/// A fallible, streaming iterator which can be advanced from either end.
pub trait DoubleEndedFallibleStreamingIterator: FallibleStreamingIterator {
/// Advances the state of the iterator to the next item from the end.
///
/// Iterators start just after the last item, so this method should be called before `get`
/// when iterating.
///
/// The behavior of calling this method after `get` has returned `None`, or after this method
/// or `advance` has returned an error is unspecified.
fn advance_back(&mut self) -> Result<(), Self::Error>;
/// Advances the back of the iterator, returning the last element.
///
/// The default implementation simply calls `advance_back` followed by `get`.
#[inline]
fn next_back(&mut self) -> Result<Option<&Self::Item>, Self::Error> {
self.advance_back()?;
Ok((*self).get())
}
}
impl<'a, I: ?Sized> FallibleStreamingIterator for &'a mut I
where
I: FallibleStreamingIterator,
{
type Item = I::Item;
type Error = I::Error;
#[inline]
fn advance(&mut self) -> Result<(), I::Error> {
(**self).advance()
}
#[inline]
fn get(&self) -> Option<&I::Item> {
(**self).get()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(**self).size_hint()
}
#[inline]
fn next(&mut self) -> Result<Option<&I::Item>, I::Error> {
(**self).next()
}
}
#[cfg(feature = "std")]
impl<I: ?Sized> FallibleStreamingIterator for Box<I>
where
I: FallibleStreamingIterator,
{
type Item = I::Item;
type Error = I::Error;
#[inline]
fn advance(&mut self) -> Result<(), I::Error> {
(**self).advance()
}
#[inline]
fn get(&self) -> Option<&I::Item> {
(**self).get()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(**self).size_hint()
}
#[inline]
fn next(&mut self) -> Result<Option<&I::Item>, I::Error> {
(**self).next()
}
}
/// Converts a normal `Iterator` over `Results` of references into a
/// `FallibleStreamingIterator`.
pub fn convert<'a, I, T, E>(it: I) -> Convert<'a, I, T>
where
I: Iterator<Item = Result<&'a T, E>>,
{
Convert { it: it, item: None }
}
/// An iterator which wraps a normal `Iterator`.
pub struct Convert<'a, I, T: 'a> {
it: I,
item: Option<&'a T>,
}
impl<'a, I, T, E> FallibleStreamingIterator for Convert<'a, I, T>
where
I: Iterator<Item = Result<&'a T, E>>,
{
type Item = T;
type Error = E;
#[inline]
fn advance(&mut self) -> Result<(), E> {
self.item = match self.it.next() {
Some(Ok(v)) => Some(v),
Some(Err(e)) => return Err(e),
None => None,
};
Ok(())
}
#[inline]
fn get(&self) -> Option<&T> {
self.item
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.it.size_hint()
}
}
impl<'a, I, T, E> DoubleEndedFallibleStreamingIterator for Convert<'a, I, T>
where
I: DoubleEndedIterator<Item = Result<&'a T, E>>,
{
#[inline]
fn advance_back(&mut self) -> Result<(), E> {
self.item = match self.it.next_back() {
Some(Ok(v)) => Some(v),
Some(Err(e)) => return Err(e),
None => None,
};
Ok(())
}
}
/// Returns an iterator over no items.
pub fn empty<T, E>() -> Empty<T, E> {
Empty(PhantomData)
}
/// An iterator over no items.
pub struct Empty<T, E>(PhantomData<(T, E)>);
impl<T, E> FallibleStreamingIterator for Empty<T, E> {
type Item = T;
type Error = E;
#[inline]
fn advance(&mut self) -> Result<(), E> {
Ok(())
}
#[inline]
fn get(&self) -> Option<&T> {
None
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(0, Some(0))
}
}
impl<T, E> DoubleEndedFallibleStreamingIterator for Empty<T, E> {
#[inline]
fn advance_back(&mut self) -> Result<(), E> {
Ok(())
}
}
/// An iterator which filters elements with a predicate.
pub struct Filter<I, F> {
it: I,
f: F,
}
impl<I, F> FallibleStreamingIterator for Filter<I, F>
where
I: FallibleStreamingIterator,
F: FnMut(&I::Item) -> bool,
{
type Item = I::Item;
type Error = I::Error;
#[inline]
fn advance(&mut self) -> Result<(), I::Error> {
while let Some(i) = self.it.next()? {
if (self.f)(i) {
break;
}
}
Ok(())
}
#[inline]
fn get(&self) -> Option<&I::Item> {
self.it.get()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(0, self.it.size_hint().1)
}
}
#[derive(Copy, Clone)]
enum FuseState {
Start,
Middle,
End,
}
/// An iterator which is well-behaved at the beginning and end of iteration.
pub struct Fuse<I> {
it: I,
state: FuseState,
}
impl<I> FallibleStreamingIterator for Fuse<I>
where
I: FallibleStreamingIterator,
{
type Item = I::Item;
type Error = I::Error;
#[inline]
fn advance(&mut self) -> Result<(), I::Error> {
match self.state {
FuseState::Start => {
match self.it.next() {
Ok(Some(_)) => self.state = FuseState::Middle,
Ok(None) => self.state = FuseState::End,
Err(e) => {
self.state = FuseState::End;
return Err(e);
}
};
}
FuseState::Middle => match self.it.next() {
Ok(Some(_)) => {}
Ok(None) => self.state = FuseState::End,
Err(e) => {
self.state = FuseState::End;
return Err(e);
}
},
FuseState::End => {}
}
Ok(())
}
#[inline]
fn get(&self) -> Option<&I::Item> {
match self.state {
FuseState::Middle => self.it.get(),
FuseState::Start | FuseState::End => None,
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.it.size_hint()
}
#[inline]
fn next(&mut self) -> Result<Option<&I::Item>, I::Error> {
match self.state {
FuseState::Start => match self.it.next() {
Ok(Some(v)) => {
self.state = FuseState::Middle;
Ok(Some(v))
}
Ok(None) => {
self.state = FuseState::End;
Ok(None)
}
Err(e) => {
self.state = FuseState::End;
Err(e)
}
},
FuseState::Middle => match self.it.next() {
Ok(Some(v)) => Ok(Some(v)),
Ok(None) => {
self.state = FuseState::End;
Ok(None)
}
Err(e) => {
self.state = FuseState::End;
Err(e)
}
},
FuseState::End => Ok(None),
}
}
}
/// An iterator which applies a transform to elements.
pub struct Map<I, F, B> {
it: I,
f: F,
value: Option<B>,
}
impl<I, F, B> FallibleStreamingIterator for Map<I, F, B>
where
I: FallibleStreamingIterator,
F: FnMut(&I::Item) -> B,
{
type Item = B;
type Error = I::Error;
#[inline]
fn advance(&mut self) -> Result<(), I::Error> {
self.value = self.it.next()?.map(&mut self.f);
Ok(())
}
#[inline]
fn get(&self) -> Option<&B> {
self.value.as_ref()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.it.size_hint()
}
}
impl<I, F, B> DoubleEndedFallibleStreamingIterator for Map<I, F, B>
where
I: DoubleEndedFallibleStreamingIterator,
F: FnMut(&I::Item) -> B,
{
#[inline]
fn advance_back(&mut self) -> Result<(), I::Error> {
self.value = self.it.next_back()?.map(&mut self.f);
Ok(())
}
}
/// An iterator which applies a transform to elements.
pub struct MapRef<I, F> {
it: I,
f: F,
}
impl<I, F, B: ?Sized> FallibleStreamingIterator for MapRef<I, F>
where
I: FallibleStreamingIterator,
F: Fn(&I::Item) -> &B,
{
type Item = B;
type Error = I::Error;
#[inline]
fn advance(&mut self) -> Result<(), I::Error> {
self.it.advance()
}
#[inline]
fn get(&self) -> Option<&B> {
self.it.get().map(&self.f)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.it.size_hint()
}
}
impl<I, F, B: ?Sized> DoubleEndedFallibleStreamingIterator for MapRef<I, F>
where
I: DoubleEndedFallibleStreamingIterator,
F: Fn(&I::Item) -> &B,
{
#[inline]
fn advance_back(&mut self) -> Result<(), I::Error> {
self.it.advance_back()
}
}
/// An iterator which applies a transform to errors.
pub struct MapErr<I, F> {
it: I,
f: F,
}
impl<I, F, B> FallibleStreamingIterator for MapErr<I, F>
where
I: FallibleStreamingIterator,
F: Fn(I::Error) -> B,
{
type Item = I::Item;
type Error = B;
#[inline]
fn advance(&mut self) -> Result<(), B> {
self.it.advance().map_err(&mut self.f)
}
#[inline]
fn get(&self) -> Option<&I::Item> {
self.it.get()
}
#[inline]
fn next(&mut self) -> Result<Option<&I::Item>, B> {
self.it.next().map_err(&mut self.f)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.it.size_hint()
}
}
impl<I, F, B> DoubleEndedFallibleStreamingIterator for MapErr<I, F>
where
I: DoubleEndedFallibleStreamingIterator,
F: Fn(I::Error) -> B,
{
#[inline]
fn advance_back(&mut self) -> Result<(), B> {
self.it.advance_back().map_err(&mut self.f)
}
#[inline]
fn next_back(&mut self) -> Result<Option<&I::Item>, B> {
self.it.next_back().map_err(&mut self.f)
}
}
/// An iterator which skips a number of initial elements.
pub struct Skip<I> {
it: I,
n: usize,
}
impl<I> FallibleStreamingIterator for Skip<I>
where
I: FallibleStreamingIterator,
{
type Item = I::Item;
type Error = I::Error;
#[inline]
fn advance(&mut self) -> Result<(), I::Error> {
for _ in 0..self.n {
if let None = self.it.next()? {
return Ok(());
}
}
self.n = 0;
self.advance()
}
#[inline]
fn get(&self) -> Option<&I::Item> {
self.it.get()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let hint = self.it.size_hint();
(
hint.0.saturating_sub(self.n),
hint.1.map(|h| h.saturating_sub(self.n)),
)
}
}
/// An iterator which skips initial elements matching a predicate.
pub struct SkipWhile<I, F> {
it: I,
f: F,
done: bool,
}
impl<I, F> FallibleStreamingIterator for SkipWhile<I, F>
where
I: FallibleStreamingIterator,
F: FnMut(&I::Item) -> bool,
{
type Item = I::Item;
type Error = I::Error;
#[inline]
fn advance(&mut self) -> Result<(), I::Error> {
if !self.done {
self.done = true;
let f = &mut self.f;
self.it.find(|i| !f(i)).map(|_| ())
} else {
self.it.advance()
}
}
#[inline]
fn get(&self) -> Option<&I::Item> {
self.it.get()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let hint = self.it.size_hint();
if self.done {
hint
} else {
(0, hint.1)
}
}
}
/// An iterator which only returns a number of initial elements.
pub struct Take<I> {
it: I,
n: usize,
done: bool,
}
impl<I> FallibleStreamingIterator for Take<I>
where
I: FallibleStreamingIterator,
{
type Item = I::Item;
type Error = I::Error;
#[inline]
fn advance(&mut self) -> Result<(), I::Error> {
if self.n != 0 {
self.it.advance()?;
self.n -= 1;
} else {
self.done = true;
}
Ok(())
}
#[inline]
fn get(&self) -> Option<&I::Item> {
if self.done {
None
} else {
self.it.get()
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let (lower, upper) = self.it.size_hint();
let lower = cmp::min(lower, self.n);
let upper = match upper {
Some(x) if x < self.n => Some(x),
_ => Some(self.n)
};
(lower, upper)
}
}
/// An iterator which only returns initial elements matching a predicate.
pub struct TakeWhile<I, F> {
it: I,
f: F,
done: bool,
}
impl<I, F> FallibleStreamingIterator for TakeWhile<I, F>
where
I: FallibleStreamingIterator,
F: FnMut(&I::Item) -> bool,
{
type Item = I::Item;
type Error = I::Error;
#[inline]
fn advance(&mut self) -> Result<(), I::Error> {
if let Some(v) = self.it.next()? {
if !(self.f)(v) {
self.done = true;
}
}
Ok(())
}
#[inline]
fn get(&self) -> Option<&I::Item> {
if self.done {
None
} else {
self.it.get()
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
if self.done {
(0, Some(0))
} else {
(0, self.it.size_hint().1)
}
}
}
#[cfg(test)]
mod test {
use super::*;
fn _is_object_safe(_: &FallibleStreamingIterator<Item = (), Error = ()>) {}
fn _is_object_safe_double(_: &DoubleEndedFallibleStreamingIterator<Item = (), Error = ()>) {}
}