Add a marker trait Fused to std::iter and implement it on Fuse<I> and applicable iterators and adapters. By implementing Fused, an iterator promises to behave as if Iterator::fuse() had been called on it (i.e. return None forever after returning None once).
Motivation
Currently, there’s no way to say “I want an iterator that returns None forever after returning None once”. This means that, to be safe, API’s need to manually call fuse() on their iterators if they intend to rely on this behavior. However, many iterators already behave this way so having a way to mark them would be really nice.
Drawbacks
Yet another special iterator trait.
This won’t be fully useful until we get some form of specialization.
Can you please add some background or what this actually does? I am fairly confused by this proposal because there is no explanation, only motivation...
Currently, there's no way to say "I want an iterator that returns None forever after returning None once".
Libstd had some adaptors with fusing bugs (Chain) and itertools too (several).
Since it’s a huge task I used quickcheck to test some fusing properties by using a “misbehaving” iterator as input and checking the length of the output when using different adaptors, that successfully found some bugs. We should expand this to test all the libstd adaptors too.
I think the effort to fix these bugs is needed, and maybe improve upon documentation too.
I’m not sure the marker trait is useful before specialization, as you note, what would be even more useful would be a different one, but I don’t think we can realize it either: IntoFused. It returns Self if you are already a fused iterator, otherwise it wraps it to produce Fuse<Self>.
I do like documenting which iterators are Fused or not, but I’m not sure a trait is necessary. Have you measured a perf hit using fuse on any already-Fused iterators (I wouldn’t be surprised, I think it would be quite clever analysis to strip the flag/check)?
That benchmark result and another test I did with Itertools::step (which also needs to use Fuse), reveals some very big gains that could be made if we could conditionally skip the Fuse adaptor for certain well behaved iterators.
For an adaptor like step the difference can be 50% reduction of the runtime if fusing isn’t needed.
I’ve implemented a version of this using specialization that makes Fuse<I> a no-op when I implements FusedIterator. This appears to fix the performance issues noted above. That is:
use std::iter::Fuse;
trait FusedIterator: Iterator {}
impl<I: Iterator> FusedIterator for Fuse<I> {}
impl<A> FusedIterator for Range<A> {}
// etc...
// Specialize Fuse...
impl<I> Iterator for Fuse<I> where I: FusedIterator {
type Item = I::Item;
fn next(&mut self) -> Self::Item {
self.0.next() // pass through.
}
}
That looks like it works very well. I think .fuse() hasn’t been used that much, but with an improvement like this it can maybe be used more.
It is a very minor extra iterator trait, but it’s really low complexity in a number of ways. Not implementing it degrades gracefully, implementing it incorrectly only leads to fusing bugs, nothing else.