Improve documentation on what len() on ExactSizeIterator means

[the8472]

If the wrapped iterator implements ExactSizeIterator then Fuse blindly delegates len() to it. The underlying iterator may know its exact size but return spurious None results anyway, on which Fuse will stop iterating even though the source knows that there are elements left to iterate, meaning Fuse will indicate that there are elements left but never return them.

The behavior was introduced in #37944 but didn't see any discussion.

Playground demo

struct Alternate {
    state: i32,
}

impl Iterator for Alternate {
    type Item = i32;

    fn next(&mut self) -> Option<i32> {
        let val = self.state;
        self.state = self.state + 1;
        
        if val % 2 == 0 && val <= 4 {
            Some(val)
        } else {
            None
        }
    }
}

impl ExactSizeIterator for Alternate {
    // We can easily calculate the remaining number of iterations.
    fn len(&self) -> usize {
        std::cmp::max(0, 3 - (self.state + 1)  / 2)  as usize
    }
}



fn main() {
    eprintln!("### regular");
    let mut iter = Alternate { state: 0 };
    dbg!(iter.len(), iter.next());
    dbg!(iter.len(), iter.next());
    dbg!(iter.len(), iter.next());
    dbg!(iter.len(), iter.next());
    dbg!(iter.len(), iter.next());
    dbg!(iter.len(), iter.next());
    eprintln!("### fused");
    let mut iter = Alternate { state: 0 }.fuse();
    dbg!(iter.len(), iter.next());
    dbg!(iter.len(), iter.next());
    dbg!(iter.len(), iter.next());
}

[nagisa]

Implementations of ExactSizeIterator have soundness implications, thus marking as I-unsound.

That being said, the documentation for Iterator::next is fairly exact in its wording that the first None means "end of iteration".

[Mark-Simulacrum]

Hm, seeing as ExactSizeIterator is not an unsafe trait, I would not expect code to be able to rely on it for soundness? Maybe we do so internally for std types though...

[sfackler]

Unsafe code can't rely on ExactSizeIterator correctness (there's TrustedLen for that).

The length of an iterator is defined as the number of items yielded before it returns None, so Fuse's implementation is correct.

[nagisa]

Oh my bad, I was confusing it with TrustedLen.

[the8472]

The length of an iterator is defined as the number of items yielded before it returns None, so Fuse's implementation is correct.

Ok, makes sense. But I will be pedantic here since I prefer documentation to have slightly more formal flavor.

len() docs:

Returns the exact number of times the iterator will iterate.

The std::iter module documentation:

An iterator has a method, next, which when called, returns an Option. next will return Some(Item) as long as there are elements, and once they've all been exhausted, will return None to indicate that iteration is finished. Individual iterators may choose to resume iteration, and so calling next again may or may not eventually start returning Some(Item) again at some point.

Now resume can be interpreted as continuing the the previous iteration instead of starting a new iteration (conceptually a new iteration would require a new iterator then). Under this interpretation len() should report the complete length of all iteration including possible resumptions which must be known when claiming exact sizing knowledge.

The documentation could use a more precise definition of what an iteration is and that resumption is really considered a new iteration.