From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- .../rust/fallible-streaming-iterator/src/lib.rs | 899 +++++++++++++++++++++ 1 file changed, 899 insertions(+) create mode 100644 third_party/rust/fallible-streaming-iterator/src/lib.rs (limited to 'third_party/rust/fallible-streaming-iterator/src/lib.rs') diff --git a/third_party/rust/fallible-streaming-iterator/src/lib.rs b/third_party/rust/fallible-streaming-iterator/src/lib.rs new file mode 100644 index 0000000000..69262d6aef --- /dev/null +++ b/third_party/rust/fallible-streaming-iterator/src/lib.rs @@ -0,0 +1,899 @@ +//! 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 +//! } +//! ``` +#![doc(html_root_url = "https://docs.rs/fallible-streaming-iterator/0.1")] +#![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, 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) { + (0, None) + } + + /// Determines if all elements of the iterator satisfy a predicate. + #[inline] + fn all(&mut self, mut f: F) -> Result + 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(&mut self, mut f: F) -> Result + 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 + 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(self, f: F) -> Filter + 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(&mut self, mut f: F) -> Result, 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(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 + where + Self: Sized, + { + Fuse { + it: self, + state: FuseState::Start, + } + } + + /// Returns an iterator which applies a transform to elements. + #[inline] + fn map(self, f: F) -> Map + 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(self, f: F) -> MapRef + 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(self, f: F) -> MapErr + 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, 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(&mut self, mut f: F) -> Result, 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 + 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(self, f: F) -> SkipWhile + 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 + 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(self, f: F) -> TakeWhile + 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, 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) { + (**self).size_hint() + } + + #[inline] + fn next(&mut self) -> Result, I::Error> { + (**self).next() + } +} + +#[cfg(feature = "std")] +impl FallibleStreamingIterator for Box +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) { + (**self).size_hint() + } + + #[inline] + fn next(&mut self) -> Result, 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>, +{ + 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>, +{ + 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) { + self.it.size_hint() + } +} + +impl<'a, I, T, E> DoubleEndedFallibleStreamingIterator for Convert<'a, I, T> +where + I: DoubleEndedIterator>, +{ + #[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() -> Empty { + Empty(PhantomData) +} + +/// An iterator over no items. +pub struct Empty(PhantomData<(T, E)>); + +impl FallibleStreamingIterator for Empty { + 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) { + (0, Some(0)) + } +} + +impl DoubleEndedFallibleStreamingIterator for Empty { + #[inline] + fn advance_back(&mut self) -> Result<(), E> { + Ok(()) + } +} + +/// An iterator which filters elements with a predicate. +pub struct Filter { + it: I, + f: F, +} + +impl FallibleStreamingIterator for Filter +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) { + (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 { + it: I, + state: FuseState, +} + +impl FallibleStreamingIterator for Fuse +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) { + self.it.size_hint() + } + + #[inline] + fn next(&mut self) -> Result, 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 { + it: I, + f: F, + value: Option, +} + +impl FallibleStreamingIterator for Map +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) { + self.it.size_hint() + } +} + +impl DoubleEndedFallibleStreamingIterator for Map +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 { + it: I, + f: F, +} + +impl FallibleStreamingIterator for MapRef +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) { + self.it.size_hint() + } +} + +impl DoubleEndedFallibleStreamingIterator for MapRef +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 { + it: I, + f: F, +} + +impl FallibleStreamingIterator for MapErr +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, B> { + self.it.next().map_err(&mut self.f) + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + self.it.size_hint() + } +} + +impl DoubleEndedFallibleStreamingIterator for MapErr +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, B> { + self.it.next_back().map_err(&mut self.f) + } +} + +/// An iterator which skips a number of initial elements. +pub struct Skip { + it: I, + n: usize, +} + +impl FallibleStreamingIterator for Skip +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) { + 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 { + it: I, + f: F, + done: bool, +} + +impl FallibleStreamingIterator for SkipWhile +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) { + 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 { + it: I, + n: usize, + done: bool, +} + +impl FallibleStreamingIterator for Take +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) { + 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 { + it: I, + f: F, + done: bool, +} + +impl FallibleStreamingIterator for TakeWhile +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) { + if self.done { + (0, Some(0)) + } else { + (0, self.it.size_hint().1) + } + } +} + +#[cfg(test)] +mod test { + use super::*; + + fn _is_object_safe(_: &FallibleStreamingIterator) {} + fn _is_object_safe_double(_: &DoubleEndedFallibleStreamingIterator) {} +} -- cgit v1.2.3