Why does the Fuse iterator adapter not work as expected?

Question

I'm experimenting with the Fuse iterator adapter and am getting unexpected results (Playground link):

fn main() {
    let mut i1 = (1..3).scan(1, |_, x| {
        if x < 2 { None } else { Some(x) }
    });
    println!("{:?}", i1.next());
    println!("{:?}", i1.next());
    println!("{:?}", i1.next());
    println!("");

    let mut i2 = (1..3).scan(1, |_, x| {
        if x < 2 { None } else { Some(x) }
    }).fuse();
    println!("{:?}", i2.next());
    println!("{:?}", i2.next()); // This should print None
    println!("{:?}", i2.next());
    println!("");
}

Which prints:

None
Some(2)
None

None
Some(2)
None

Iterator i1 is returning what I expect. It returns None, then Some(2), then None. i2 is the same iterator adapted with fuse(). Fuse should make it return None after the first None, and since the first value it returns is None that should be the only value it returns. However, it behaves the same as i1. What am I doing wrong?

Answer 1

TL;DR Summary: This was a bug and is fixed in Rust 1.19 and newer.

I'm pretty sure you are doing nothing wrong. This appears to be either a bug (my guess) or a very confusing interaction. Check out this expanded example:

#![feature(fused)]

fn dump<I: Iterator<Item = i32>>(label: &str, mut iter: I) {
    println!("= Running: {}", label);
    for _ in 0..10 {
        println!("{:?}", iter.next());
    }
    println!("");
}

fn boxed_internal_fuse() -> Box<Iterator<Item = i32>> {
    Box::new((1..3)
        .scan(1, |_, x| if x < 2 { None } else { Some(x) })
        .fuse())
}

fn boxed_no_fuse() -> Box<Iterator<Item = i32>> {
    Box::new((1..3)
        .scan(1, |_, x| if x < 2 { None } else { Some(x) }))
}

use std::iter::FusedIterator;
fn boxed_no_fuse_but_fused() -> Box<FusedIterator<Item = i32>> {
    Box::new((1..3)
        .scan(1, |_, x| if x < 2 { None } else { Some(x) }))
}

fn main() {
    let i1 = (1..3)
        .scan(1, |_, x| if x < 2 { None } else { Some(x) });
    dump("Scan", i1);
    
    let i2 = (1..3)
        .scan(1, |_, x| if x < 2 { None } else { Some(x) })
        .fuse();
    dump("Fuse<Scan>", i2);
    
    dump("Box<Fuse<Scan>>", boxed_internal_fuse());
    dump("Fuse<Box<Iterator>>", boxed_no_fuse().fuse()); // All `None`s
    dump("Fuse<Box<FusedIterator>>", boxed_no_fuse_but_fused().fuse());
}

The trick is that FusedIterator is a unstable trait that is aimed at improving the efficiency. It lets Iterator::fuse know that it's a no-op.

However, in this case, the conditions are necessary but not sufficient:

impl<B, I, St, F> FusedIterator for Scan<I, St, F>
    where I: FusedIterator, F: FnMut(&mut St, I::Item) -> Option<B> {}

It's true that if the underlying iterator is FusedIterator and starts returning None, scan will keep returning None. However, that's not the only way to get None — the closure can also return None!