InterleaveShortest<I, J> is not actually fused

[nox]

I was looking at the code and it turns out that InterleaveShortest<I, J> will resume iterating after a None if one of its iterators is not fused.

use itertools::Itertools;

fn not_fused() -> impl Iterator<Item = bool> {
    let mut last = Some(true);
    std::iter::from_fn(move || {
        match last {
            Some(b) => {
                last = None;
                Some(b)
            },
            None => {
                last = Some(true);
                None
            }
        }
    })
}

fn demonstrate_that_not_fused_is_indeed_not_fused() {
    let mut not_fused = not_fused();
    assert_eq!(not_fused.next(), Some(true));
    assert_eq!(not_fused.next(), None);
    assert_eq!(not_fused.next(), Some(true));
}

fn main() {
    demonstrate_that_not_fused_is_indeed_not_fused();

    let mut interleave_shortest = std::iter::repeat(false).interleave_shortest(not_fused());
    assert_eq!(interleave_shortest.next(), Some(false));
    assert_eq!(interleave_shortest.next(), Some(true));
    assert_eq!(interleave_shortest.next(), Some(false));
    assert_eq!(interleave_shortest.next(), None);

    // This fails, because `InterleaveShortest<I, J>` is not actually fused.
    assert_eq!(interleave_shortest.next(), None);
}

[phimuemue]

This was apparently an intentional decision: beaf395

Not sure what to make of this... We should probably at least update documentation, and check if we behave consistently across itertools resp. the std::iter landscape.

[jswrenn]

InterleaveShortest doesn't implement FusedIterator, so I wouldn't have expected it to be fused.

But, since it already behaves as a fused iterator if its component iterators are fused, I imagine we could just add this impl:

impl<I, J> FusedIterator for InterleaveShortest<I, J>
where
    I: FusedIterator,
    J: FusedIterator
{}

[jswrenn]

Ah, I see, the documentation prose claims it's fused.

Huh, I'm not sure what to make of this either.

[nox]

IMO none of the iterators should be using fused iterators internally, but I concede that would be a breaking change. Why is Interleave<I, J> using Fuse internally for example?

[bluss]

Fuse might be used internally if it's recognized that the implementation would need to keep that kind of state anyway to do its job correctly or efficiently (using fuse and its specialization for that flag then saves space & time). I think fuse has sense sometimes.

I don't exactly remember the details, but if you see a fuse, it's probably because of some internal property of the algorithm, not to as a frivolous addition.