fallible_streaming_iterator/
lib.rs

1//! Fallible, streaming iteration.
2//!
3//! `FallibleStreamingIterator` differs from the standard library's `Iterator` trait in two ways:
4//! iteration can fail, resulting in an error, and only one element of the iteration is available at
5//! any time.
6//!
7//! While these iterators cannot be used with Rust `for` loops, `while let` loops offer a similar
8//! level of ergonomics:
9//!
10//! ```ignore
11//! while let Some(value) = it.next()? {
12//!     // use value
13//! }
14//! ```
15#![doc(html_root_url = "https://docs.rs/fallible-streaming-iterator/0.1")]
16#![warn(missing_docs)]
17#![cfg_attr(not(feature = "std"), no_std)]
18
19#[cfg(feature = "std")]
20extern crate core;
21
22use core::cmp;
23use core::marker::PhantomData;
24
25/// A fallible, streaming iterator.
26pub trait FallibleStreamingIterator {
27    /// The type being iterated over.
28    type Item: ?Sized;
29
30    /// The error type of iteration.
31    type Error;
32
33    /// Advances the iterator to the next position.
34    ///
35    /// Iterators start just before the first item, so this method should be called before `get`
36    /// when iterating.
37    ///
38    /// The behavior of calling this method after `get` has returned `None`, or after this method
39    /// has returned an error is unspecified.
40    fn advance(&mut self) -> Result<(), Self::Error>;
41
42    /// Returns the current element.
43    ///
44    /// The behavior of calling this method before any calls to `advance` is unspecified.
45    fn get(&self) -> Option<&Self::Item>;
46
47    /// Advances the iterator, returning the next element.
48    ///
49    /// The default implementation simply calls `advance` followed by `get`.
50    #[inline]
51    fn next(&mut self) -> Result<Option<&Self::Item>, Self::Error> {
52        self.advance()?;
53        Ok((*self).get())
54    }
55
56    /// Returns bounds on the number of remaining elements in the iterator.
57    #[inline]
58    fn size_hint(&self) -> (usize, Option<usize>) {
59        (0, None)
60    }
61
62    /// Determines if all elements of the iterator satisfy a predicate.
63    #[inline]
64    fn all<F>(&mut self, mut f: F) -> Result<bool, Self::Error>
65    where
66        Self: Sized,
67        F: FnMut(&Self::Item) -> bool,
68    {
69        while let Some(e) = self.next()? {
70            if !f(e) {
71                return Ok(false);
72            }
73        }
74        Ok(true)
75    }
76
77    /// Determines if any elements of the iterator satisfy a predicate.
78    #[inline]
79    fn any<F>(&mut self, mut f: F) -> Result<bool, Self::Error>
80    where
81        Self: Sized,
82        F: FnMut(&Self::Item) -> bool,
83    {
84        self.all(|e| !f(e)).map(|r| !r)
85    }
86
87    /// Borrows an iterator, rather than consuming it.
88    ///
89    /// This is useful to allow the application of iterator adaptors while still retaining ownership
90    /// of the original adaptor.
91    #[inline]
92    fn by_ref(&mut self) -> &mut Self
93    where
94        Self: Sized,
95    {
96        self
97    }
98
99    /// Returns the number of remaining elements in the iterator.
100    #[inline]
101    fn count(mut self) -> Result<usize, Self::Error>
102    where
103        Self: Sized,
104    {
105        let mut count = 0;
106        while let Some(_) = self.next()? {
107            count += 1;
108        }
109        Ok(count)
110    }
111
112    /// Returns an iterator which filters elements by a predicate.
113    #[inline]
114    fn filter<F>(self, f: F) -> Filter<Self, F>
115    where
116        Self: Sized,
117        F: FnMut(&Self::Item) -> bool,
118    {
119        Filter { it: self, f: f }
120    }
121
122    /// Returns the first element of the iterator which satisfies a predicate.
123    #[inline]
124    fn find<F>(&mut self, mut f: F) -> Result<Option<&Self::Item>, Self::Error>
125    where
126        Self: Sized,
127        F: FnMut(&Self::Item) -> bool,
128    {
129        loop {
130            self.advance()?;
131            match self.get() {
132                Some(v) => {
133                    if f(v) {
134                        break;
135                    }
136                }
137                None => break,
138            }
139        }
140        Ok((*self).get())
141    }
142
143    /// Calls a closure on each element of an iterator.
144    #[inline]
145    fn for_each<F>(mut self, mut f: F) -> Result<(), Self::Error>
146    where
147        Self: Sized,
148        F: FnMut(&Self::Item),
149    {
150        while let Some(value) = self.next()? {
151            f(value);
152        }
153        Ok(())
154    }
155
156    /// Returns an iterator which is well-behaved at the beginning and end of iteration.
157    #[inline]
158    fn fuse(self) -> Fuse<Self>
159    where
160        Self: Sized,
161    {
162        Fuse {
163            it: self,
164            state: FuseState::Start,
165        }
166    }
167
168    /// Returns an iterator which applies a transform to elements.
169    #[inline]
170    fn map<F, B>(self, f: F) -> Map<Self, F, B>
171    where
172        Self: Sized,
173        F: FnMut(&Self::Item) -> B,
174    {
175        Map {
176            it: self,
177            f: f,
178            value: None,
179        }
180    }
181
182    /// Returns an iterator which applies a transform to elements.
183    ///
184    /// Unlike `map`, the the closure provided to this method returns a reference into the original
185    /// value.
186    #[inline]
187    fn map_ref<F, B: ?Sized>(self, f: F) -> MapRef<Self, F>
188    where
189        Self: Sized,
190        F: Fn(&Self::Item) -> &B,
191    {
192        MapRef { it: self, f: f }
193    }
194
195    /// Returns an iterator that applies a transform to errors.
196    #[inline]
197    fn map_err<F, B>(self, f: F) -> MapErr<Self, F>
198    where
199        Self: Sized,
200        F: Fn(Self::Error) -> B,
201    {
202        MapErr { it: self, f: f }
203    }
204
205    /// Returns the `nth` element of the iterator.
206    #[inline]
207    fn nth(&mut self, n: usize) -> Result<Option<&Self::Item>, Self::Error> {
208        for _ in 0..n {
209            self.advance()?;
210            if let None = self.get() {
211                return Ok(None);
212            }
213        }
214        self.next()
215    }
216
217    /// Returns the position of the first element matching a predicate.
218    #[inline]
219    fn position<F>(&mut self, mut f: F) -> Result<Option<usize>, Self::Error>
220    where
221        Self: Sized,
222        F: FnMut(&Self::Item) -> bool,
223    {
224        let mut pos = 0;
225        while let Some(v) = self.next()? {
226            if f(v) {
227                return Ok(Some(pos));
228            }
229            pos += 1;
230        }
231        Ok(None)
232    }
233
234    /// Returns an iterator which skips the first `n` elements.
235    #[inline]
236    fn skip(self, n: usize) -> Skip<Self>
237    where
238        Self: Sized,
239    {
240        Skip { it: self, n: n }
241    }
242
243    /// Returns an iterator which skips the first sequence of elements matching a predicate.
244    #[inline]
245    fn skip_while<F>(self, f: F) -> SkipWhile<Self, F>
246    where
247        Self: Sized,
248        F: FnMut(&Self::Item) -> bool,
249    {
250        SkipWhile {
251            it: self,
252            f: f,
253            done: false,
254        }
255    }
256
257    /// Returns an iterator which only returns the first `n` elements.
258    #[inline]
259    fn take(self, n: usize) -> Take<Self>
260    where
261        Self: Sized,
262    {
263        Take {
264            it: self,
265            n: n,
266            done: false,
267        }
268    }
269
270    /// Returns an iterator which only returns the first sequence of elements matching a predicate.
271    #[inline]
272    fn take_while<F>(self, f: F) -> TakeWhile<Self, F>
273    where
274        Self: Sized,
275        F: FnMut(&Self::Item) -> bool,
276    {
277        TakeWhile {
278            it: self,
279            f: f,
280            done: false,
281        }
282    }
283}
284
285/// A fallible, streaming iterator which can be advanced from either end.
286pub trait DoubleEndedFallibleStreamingIterator: FallibleStreamingIterator {
287    /// Advances the state of the iterator to the next item from the end.
288    ///
289    /// Iterators start just after the last item, so this method should be called before `get`
290    /// when iterating.
291    ///
292    /// The behavior of calling this method after `get` has returned `None`, or after this method
293    /// or `advance` has returned an error is unspecified.
294    fn advance_back(&mut self) -> Result<(), Self::Error>;
295
296    /// Advances the back of the iterator, returning the last element.
297    ///
298    /// The default implementation simply calls `advance_back` followed by `get`.
299    #[inline]
300    fn next_back(&mut self) -> Result<Option<&Self::Item>, Self::Error> {
301        self.advance_back()?;
302        Ok((*self).get())
303    }
304}
305
306impl<'a, I: ?Sized> FallibleStreamingIterator for &'a mut I
307where
308    I: FallibleStreamingIterator,
309{
310    type Item = I::Item;
311    type Error = I::Error;
312
313    #[inline]
314    fn advance(&mut self) -> Result<(), I::Error> {
315        (**self).advance()
316    }
317
318    #[inline]
319    fn get(&self) -> Option<&I::Item> {
320        (**self).get()
321    }
322
323    #[inline]
324    fn size_hint(&self) -> (usize, Option<usize>) {
325        (**self).size_hint()
326    }
327
328    #[inline]
329    fn next(&mut self) -> Result<Option<&I::Item>, I::Error> {
330        (**self).next()
331    }
332}
333
334#[cfg(feature = "std")]
335impl<I: ?Sized> FallibleStreamingIterator for Box<I>
336where
337    I: FallibleStreamingIterator,
338{
339    type Item = I::Item;
340    type Error = I::Error;
341
342    #[inline]
343    fn advance(&mut self) -> Result<(), I::Error> {
344        (**self).advance()
345    }
346
347    #[inline]
348    fn get(&self) -> Option<&I::Item> {
349        (**self).get()
350    }
351
352    #[inline]
353    fn size_hint(&self) -> (usize, Option<usize>) {
354        (**self).size_hint()
355    }
356
357    #[inline]
358    fn next(&mut self) -> Result<Option<&I::Item>, I::Error> {
359        (**self).next()
360    }
361}
362
363/// Converts a normal `Iterator` over `Results` of references into a
364/// `FallibleStreamingIterator`.
365pub fn convert<'a, I, T, E>(it: I) -> Convert<'a, I, T>
366where
367    I: Iterator<Item = Result<&'a T, E>>,
368{
369    Convert { it: it, item: None }
370}
371
372/// An iterator which wraps a normal `Iterator`.
373pub struct Convert<'a, I, T: 'a> {
374    it: I,
375    item: Option<&'a T>,
376}
377
378impl<'a, I, T, E> FallibleStreamingIterator for Convert<'a, I, T>
379where
380    I: Iterator<Item = Result<&'a T, E>>,
381{
382    type Item = T;
383    type Error = E;
384
385    #[inline]
386    fn advance(&mut self) -> Result<(), E> {
387        self.item = match self.it.next() {
388            Some(Ok(v)) => Some(v),
389            Some(Err(e)) => return Err(e),
390            None => None,
391        };
392        Ok(())
393    }
394
395    #[inline]
396    fn get(&self) -> Option<&T> {
397        self.item
398    }
399
400    #[inline]
401    fn size_hint(&self) -> (usize, Option<usize>) {
402        self.it.size_hint()
403    }
404}
405
406impl<'a, I, T, E> DoubleEndedFallibleStreamingIterator for Convert<'a, I, T>
407where
408    I: DoubleEndedIterator<Item = Result<&'a T, E>>,
409{
410    #[inline]
411    fn advance_back(&mut self) -> Result<(), E> {
412        self.item = match self.it.next_back() {
413            Some(Ok(v)) => Some(v),
414            Some(Err(e)) => return Err(e),
415            None => None,
416        };
417        Ok(())
418    }
419}
420
421/// Returns an iterator over no items.
422pub fn empty<T, E>() -> Empty<T, E> {
423    Empty(PhantomData)
424}
425
426/// An iterator over no items.
427pub struct Empty<T, E>(PhantomData<(T, E)>);
428
429impl<T, E> FallibleStreamingIterator for Empty<T, E> {
430    type Item = T;
431    type Error = E;
432
433    #[inline]
434    fn advance(&mut self) -> Result<(), E> {
435        Ok(())
436    }
437
438    #[inline]
439    fn get(&self) -> Option<&T> {
440        None
441    }
442
443    #[inline]
444    fn size_hint(&self) -> (usize, Option<usize>) {
445        (0, Some(0))
446    }
447}
448
449impl<T, E> DoubleEndedFallibleStreamingIterator for Empty<T, E> {
450    #[inline]
451    fn advance_back(&mut self) -> Result<(), E> {
452        Ok(())
453    }
454}
455
456/// An iterator which filters elements with a predicate.
457pub struct Filter<I, F> {
458    it: I,
459    f: F,
460}
461
462impl<I, F> FallibleStreamingIterator for Filter<I, F>
463where
464    I: FallibleStreamingIterator,
465    F: FnMut(&I::Item) -> bool,
466{
467    type Item = I::Item;
468    type Error = I::Error;
469
470    #[inline]
471    fn advance(&mut self) -> Result<(), I::Error> {
472        while let Some(i) = self.it.next()? {
473            if (self.f)(i) {
474                break;
475            }
476        }
477        Ok(())
478    }
479
480    #[inline]
481    fn get(&self) -> Option<&I::Item> {
482        self.it.get()
483    }
484
485    #[inline]
486    fn size_hint(&self) -> (usize, Option<usize>) {
487        (0, self.it.size_hint().1)
488    }
489}
490
491#[derive(Copy, Clone)]
492enum FuseState {
493    Start,
494    Middle,
495    End,
496}
497
498/// An iterator which is well-behaved at the beginning and end of iteration.
499pub struct Fuse<I> {
500    it: I,
501    state: FuseState,
502}
503
504impl<I> FallibleStreamingIterator for Fuse<I>
505where
506    I: FallibleStreamingIterator,
507{
508    type Item = I::Item;
509    type Error = I::Error;
510
511    #[inline]
512    fn advance(&mut self) -> Result<(), I::Error> {
513        match self.state {
514            FuseState::Start => {
515                match self.it.next() {
516                    Ok(Some(_)) => self.state = FuseState::Middle,
517                    Ok(None) => self.state = FuseState::End,
518                    Err(e) => {
519                        self.state = FuseState::End;
520                        return Err(e);
521                    }
522                };
523            }
524            FuseState::Middle => match self.it.next() {
525                Ok(Some(_)) => {}
526                Ok(None) => self.state = FuseState::End,
527                Err(e) => {
528                    self.state = FuseState::End;
529                    return Err(e);
530                }
531            },
532            FuseState::End => {}
533        }
534        Ok(())
535    }
536
537    #[inline]
538    fn get(&self) -> Option<&I::Item> {
539        match self.state {
540            FuseState::Middle => self.it.get(),
541            FuseState::Start | FuseState::End => None,
542        }
543    }
544
545    #[inline]
546    fn size_hint(&self) -> (usize, Option<usize>) {
547        self.it.size_hint()
548    }
549
550    #[inline]
551    fn next(&mut self) -> Result<Option<&I::Item>, I::Error> {
552        match self.state {
553            FuseState::Start => match self.it.next() {
554                Ok(Some(v)) => {
555                    self.state = FuseState::Middle;
556                    Ok(Some(v))
557                }
558                Ok(None) => {
559                    self.state = FuseState::End;
560                    Ok(None)
561                }
562                Err(e) => {
563                    self.state = FuseState::End;
564                    Err(e)
565                }
566            },
567            FuseState::Middle => match self.it.next() {
568                Ok(Some(v)) => Ok(Some(v)),
569                Ok(None) => {
570                    self.state = FuseState::End;
571                    Ok(None)
572                }
573                Err(e) => {
574                    self.state = FuseState::End;
575                    Err(e)
576                }
577            },
578            FuseState::End => Ok(None),
579        }
580    }
581}
582
583/// An iterator which applies a transform to elements.
584pub struct Map<I, F, B> {
585    it: I,
586    f: F,
587    value: Option<B>,
588}
589
590impl<I, F, B> FallibleStreamingIterator for Map<I, F, B>
591where
592    I: FallibleStreamingIterator,
593    F: FnMut(&I::Item) -> B,
594{
595    type Item = B;
596    type Error = I::Error;
597
598    #[inline]
599    fn advance(&mut self) -> Result<(), I::Error> {
600        self.value = self.it.next()?.map(&mut self.f);
601        Ok(())
602    }
603
604    #[inline]
605    fn get(&self) -> Option<&B> {
606        self.value.as_ref()
607    }
608
609    #[inline]
610    fn size_hint(&self) -> (usize, Option<usize>) {
611        self.it.size_hint()
612    }
613}
614
615impl<I, F, B> DoubleEndedFallibleStreamingIterator for Map<I, F, B>
616where
617    I: DoubleEndedFallibleStreamingIterator,
618    F: FnMut(&I::Item) -> B,
619{
620    #[inline]
621    fn advance_back(&mut self) -> Result<(), I::Error> {
622        self.value = self.it.next_back()?.map(&mut self.f);
623        Ok(())
624    }
625}
626
627/// An iterator which applies a transform to elements.
628pub struct MapRef<I, F> {
629    it: I,
630    f: F,
631}
632
633impl<I, F, B: ?Sized> FallibleStreamingIterator for MapRef<I, F>
634where
635    I: FallibleStreamingIterator,
636    F: Fn(&I::Item) -> &B,
637{
638    type Item = B;
639    type Error = I::Error;
640
641    #[inline]
642    fn advance(&mut self) -> Result<(), I::Error> {
643        self.it.advance()
644    }
645
646    #[inline]
647    fn get(&self) -> Option<&B> {
648        self.it.get().map(&self.f)
649    }
650
651    #[inline]
652    fn size_hint(&self) -> (usize, Option<usize>) {
653        self.it.size_hint()
654    }
655}
656
657impl<I, F, B: ?Sized> DoubleEndedFallibleStreamingIterator for MapRef<I, F>
658where
659    I: DoubleEndedFallibleStreamingIterator,
660    F: Fn(&I::Item) -> &B,
661{
662    #[inline]
663    fn advance_back(&mut self) -> Result<(), I::Error> {
664        self.it.advance_back()
665    }
666}
667
668/// An iterator which applies a transform to errors.
669pub struct MapErr<I, F> {
670    it: I,
671    f: F,
672}
673
674impl<I, F, B> FallibleStreamingIterator for MapErr<I, F>
675where
676    I: FallibleStreamingIterator,
677    F: Fn(I::Error) -> B,
678{
679    type Item = I::Item;
680    type Error = B;
681
682    #[inline]
683    fn advance(&mut self) -> Result<(), B> {
684        self.it.advance().map_err(&mut self.f)
685    }
686
687    #[inline]
688    fn get(&self) -> Option<&I::Item> {
689        self.it.get()
690    }
691
692    #[inline]
693    fn next(&mut self) -> Result<Option<&I::Item>, B> {
694        self.it.next().map_err(&mut self.f)
695    }
696
697    #[inline]
698    fn size_hint(&self) -> (usize, Option<usize>) {
699        self.it.size_hint()
700    }
701}
702
703impl<I, F, B> DoubleEndedFallibleStreamingIterator for MapErr<I, F>
704where
705    I: DoubleEndedFallibleStreamingIterator,
706    F: Fn(I::Error) -> B,
707{
708    #[inline]
709    fn advance_back(&mut self) -> Result<(), B> {
710        self.it.advance_back().map_err(&mut self.f)
711    }
712
713    #[inline]
714    fn next_back(&mut self) -> Result<Option<&I::Item>, B> {
715        self.it.next_back().map_err(&mut self.f)
716    }
717}
718
719/// An iterator which skips a number of initial elements.
720pub struct Skip<I> {
721    it: I,
722    n: usize,
723}
724
725impl<I> FallibleStreamingIterator for Skip<I>
726where
727    I: FallibleStreamingIterator,
728{
729    type Item = I::Item;
730    type Error = I::Error;
731
732    #[inline]
733    fn advance(&mut self) -> Result<(), I::Error> {
734        for _ in 0..self.n {
735            if let None = self.it.next()? {
736                return Ok(());
737            }
738        }
739        self.n = 0;
740        self.advance()
741    }
742
743    #[inline]
744    fn get(&self) -> Option<&I::Item> {
745        self.it.get()
746    }
747
748    #[inline]
749    fn size_hint(&self) -> (usize, Option<usize>) {
750        let hint = self.it.size_hint();
751        (
752            hint.0.saturating_sub(self.n),
753            hint.1.map(|h| h.saturating_sub(self.n)),
754        )
755    }
756}
757
758/// An iterator which skips initial elements matching a predicate.
759pub struct SkipWhile<I, F> {
760    it: I,
761    f: F,
762    done: bool,
763}
764
765impl<I, F> FallibleStreamingIterator for SkipWhile<I, F>
766where
767    I: FallibleStreamingIterator,
768    F: FnMut(&I::Item) -> bool,
769{
770    type Item = I::Item;
771    type Error = I::Error;
772
773    #[inline]
774    fn advance(&mut self) -> Result<(), I::Error> {
775        if !self.done {
776            self.done = true;
777            let f = &mut self.f;
778            self.it.find(|i| !f(i)).map(|_| ())
779        } else {
780            self.it.advance()
781        }
782    }
783
784    #[inline]
785    fn get(&self) -> Option<&I::Item> {
786        self.it.get()
787    }
788
789    #[inline]
790    fn size_hint(&self) -> (usize, Option<usize>) {
791        let hint = self.it.size_hint();
792        if self.done {
793            hint
794        } else {
795            (0, hint.1)
796        }
797    }
798}
799
800/// An iterator which only returns a number of initial elements.
801pub struct Take<I> {
802    it: I,
803    n: usize,
804    done: bool,
805}
806
807impl<I> FallibleStreamingIterator for Take<I>
808where
809    I: FallibleStreamingIterator,
810{
811    type Item = I::Item;
812    type Error = I::Error;
813
814    #[inline]
815    fn advance(&mut self) -> Result<(), I::Error> {
816        if self.n != 0 {
817            self.it.advance()?;
818            self.n -= 1;
819        } else {
820            self.done = true;
821        }
822        Ok(())
823    }
824
825    #[inline]
826    fn get(&self) -> Option<&I::Item> {
827        if self.done {
828            None
829        } else {
830            self.it.get()
831        }
832    }
833
834    #[inline]
835    fn size_hint(&self) -> (usize, Option<usize>) {
836        let (lower, upper) = self.it.size_hint();
837
838        let lower = cmp::min(lower, self.n);
839
840        let upper = match upper {
841            Some(x) if x < self.n => Some(x),
842            _ => Some(self.n)
843        };
844
845        (lower, upper)
846    }
847}
848
849/// An iterator which only returns initial elements matching a predicate.
850pub struct TakeWhile<I, F> {
851    it: I,
852    f: F,
853    done: bool,
854}
855
856impl<I, F> FallibleStreamingIterator for TakeWhile<I, F>
857where
858    I: FallibleStreamingIterator,
859    F: FnMut(&I::Item) -> bool,
860{
861    type Item = I::Item;
862    type Error = I::Error;
863
864    #[inline]
865    fn advance(&mut self) -> Result<(), I::Error> {
866        if let Some(v) = self.it.next()? {
867            if !(self.f)(v) {
868                self.done = true;
869            }
870        }
871        Ok(())
872    }
873
874    #[inline]
875    fn get(&self) -> Option<&I::Item> {
876        if self.done {
877            None
878        } else {
879            self.it.get()
880        }
881    }
882
883    #[inline]
884    fn size_hint(&self) -> (usize, Option<usize>) {
885        if self.done {
886            (0, Some(0))
887        } else {
888            (0, self.it.size_hint().1)
889        }
890    }
891}
892
893#[cfg(test)]
894mod test {
895    use super::*;
896
897    fn _is_object_safe(_: &FallibleStreamingIterator<Item = (), Error = ()>) {}
898    fn _is_object_safe_double(_: &DoubleEndedFallibleStreamingIterator<Item = (), Error = ()>) {}
899}
fallible_streaming_iterator/lib.rs

fallible_streaming_iterator/
lib.rs
