The iterator documentation lacks guidance for implementers of iterators with side-effects

[nagisa]

Today the standard library implementation of the defaulted iterator methods as well as various transformers are developed under an assumption that there are basically two kinds of valid iterators:

1. Side-effect free iterators (these are very nice and easy to optimize 🥳 🎉);
2. Iterators with side effects where all the side effects will be observed no matter how you combine it (e.g. (0..10).map(|_| println!("banana")).skip(10).next() will still print out a 🍌 10 times.

However, nothing in the documentation we have appears to inform of this. And so people implementing the Iterator trait may be inclined to optimize their side-effect-ful Iterators to omit some side effects when they deem it possible. I was presented “debug logs” as an example of what definitely doesn't feel like a side-effect even though it definitely is, but even things like database or filesystem access could be suspect here.

So, consider the following Up To No Good code as an example:

struct MyIterator {
    current: usize,
}

impl Iterator for MyIterator {
    type Item = usize;
    fn next(&mut self) -> Option<usize> {
        self.nth(0)
    }
    
    fn nth(&mut self, count: usize) -> Option<usize> {
        let result = self.current + count;
        self.current = result + 1;
        println!("will yield {}", result);
        Some(result)
    }
}

Seems very justified in isolation. However in the presence of such an implementation we also start leaking implementation details of the standard library left and right:

fn main() {
    let mut iterator = MyIterator { current: 0 };
    iterator.nth(10);
    iterator.nth(10);
    let mut skipped_once = MyIterator { current: 0 }.skip(10);
    skipped_once.next();
    let mut skipped_twice = MyIterator { current: 0 }.skip(10).skip(10);
    skipped_twice.next();
}

prints out:

will yield 10
will yield 21
will yield 9
will yield 10
will yield 9
will yield 19
will yield 20

The intuition I have as somebody working on Rust is that implementing skip(10) by calling next() 10 times, or by calling nth only once for each next() ought to be a valid implementation. However any change to implementation of skip suddenly becomes a potentially breaking change in presence of such an iterator implementation.

All that is to say that we definitely should document what a correct implementation of the overriden default Iterator methods should look like and what are the consequences of not following the guidance.

[the8472]

All that is to say that we definitely should document what a correct implementation of the overriden default Iterator methods should look like [...]

Do you mean we should give a naive implementation for each defaulted method in terms of next() and say that overridden impls should be ~equivalent to it?

And so people implementing the Iterator trait may be inclined to optimize their side-effect-ful Iterators to omit some side effects when they deem it possible.

😙 ♬♪♫

[nagisa]

Do you mean we should give a naive implementation for each defaulted method in terms of next() and say that overridden impls should be ~equivalent to it?

I don't have a strong opinion as to what the default implementation looks like. I think it is perfectly fine for libstd to have specializations when it knows iterators don't have side-effects for example (e.g. much like what it does with TrustedRandomAccess today.) However we definitely should be documenting how the overriden methods should behave, so that there isn't any gray areas when we do actually work on improving the iterator implementations in libstd.

[hkBst]

I don't think it is a good design to do your side effects inside Iterators. You should instead have your iterators produce value that describe the side effects that you want and only execute those effects after they have been yielded from the iterator. Perhaps that should be documented if it isn't already.