Should fused fallible iterators/lenders be fused on errors, too?

1

This is a very general design question. "Fused", in Rust, for iterators, means that they are idempotent on None: once they return none, they always return None.

Now, fallible iterators (like in the fallible-iterator crate, or in the fallible version of lenders return a Result. Certainly we want such iterators to be idempotent on Ok(None). That's what fallible-iterator does in the fused case.

But while working on fallible lenders it came to my mind that, maybe, it would be sensible to be idempotent on a returned error, too. In general, the approach to after-error method call is "unpredictable" (as after None in an iterator). So it would make sense that fusing a fallible iterator or lender would make the returned error idempotent, too.

That has a cost, of course, as it implies additional state, tests, etc. And maybe it doesn't make much sense because usually an error unleashes some kind of recovery path that will not insist on calling next.

But I'd love to hear what people think of the issue.

2

Arguably, it’s kinda annoying – though that doesn’t answer your question here – that the “what happens after None” question even exists in Rust; even though enums (Option in particular) have so nicely solved the problem you see in Iterator-like abstractions in some other languages such as Java where you’ll meet separate methods like hasNext (returning a bool), and then a next method (returning the item type directly) that would need to e.g. throw an exception when called unexpectedly. It’s like… the more capable algebraic types have solved half of the problem (the user can’t force the Iterator to give an item when none is present), but it’s not perfect yet (the iterator can still offer non-None values after it arguably “was done”; but also, the user can still repeatedly ask the iterator in the first place, so to be more “well-behaved”, certain iterators would need to add overhead of sorts).

Now actually talking about your question (and kinda detached from my previous paragraph)…

…what exactly do you mean by “idempotent”? Keep returning the same error again? That would meen needing to Clone the error though, that doesn’t sound ideal… or what did you have in mind? Perhaps that it just ends? Another approach could even be to take inspiration from APIs like Future and to embrace the “if you call this method after we’re done we can just panic” approach – the fused version of the thing may then perhaps offer an additional method to determine the state? IDK maybe that’s making the whole API worse though.

One fun case to think about through such invariants/properties is going to be Zip. I haven’t thought through your particular idea(s), but if one of the iterators has an Err, and you considered Err something “like an item” though [and upstream of a fallible map operation it may actually have been an item], it brings the two halves of the Zip out of sync, which is arguably then just inviting buggy behavior if you don’t think about such cases, right? (For instance, this also makes it rather asymmetric between the two sides.)

Ah, and now I’m noticing the current docs do answer my first question (perhaps?) in that they state it’s asking for consistent Ok(None) after an Err(_) encounter.

And now I got distracted looking at the list of FusedLender impls by an urge to question the validity of claiming fusedness on Cycle

impl<L> FusedLender for Cycle<L>
where
    L: Clone + FusedLender,

because arguably, it reasons about the behavior of clones of a lender, even though there aren’t any documented restrictions on their behavior, AFAICT. Though … interestingly, it looks like std’s normal Iterator is even more lax here and even provides:

impl<I> FusedIterator for Cycle<I>
where
    I: Clone + Iterator,

with a mere I: Iterator bound. Which would be fine if there was any promise (even on a “logic error” level) that cloning an iterator produces something that has the same values.

Which… can be broken rather easily, e.g. here:

use std::iter::{self, FusedIterator};
use std::sync::mpsc;

fn main() {
    let (tx, rx) = mpsc::channel::<()>();

    let it = iter::from_fn(|| rx.try_recv().ok());
    let it = it.cycle();
    test_fused(it, || _ = tx.send(()));
}

fn test_fused(mut i: impl FusedIterator, cb: impl FnOnce()) {
    if i.next().is_none() {
        cb();
        assert!(i.next().is_none());
    }
}

^ this assertion totally fails :sweat_smile: (playground)

Edit: Turns out the issue is known (`impl FusedIterator for Cycle<I>` is incorrect · Issue #90085 · rust-lang/rust · GitHub)

3

But, you didn't tell me your opinion which was what I needed :joy:.

BTW, having implementation-dependent behavior after None is one of the best ideas in Rust. I implemented millions of strictly lazy iterators, wrote papers on them, and all the logic is so much better if you don't have to take care of idempotence.

Anyway: the present implementation is a contribution and I'm trying to get possible alternative ideas. Yes, iterating on the error would require cloning. But, for a fused fallible lender we might stipulate that after the first error the lender must return a marker error from the crate, meaning "there was an error". I think the repeating Ok(None) is not a good idea. fallible-iterator has no discernible choice I can see.

1 Like
4

This could technically be done if Iterator::next was not impl Fn(&mut self) -> Option<Self::Item>, but impl Fn(self) -> (Option<Self>, Self::Item). This, though, would obviously be less ergonomic and would probably incur some overhead for pre-checking for the existence of next item.

5

Then impl Fn(self) -> Option<(Self::Item, Self)> perhaps?

6

If a fallible iterator returns a Result<Option> (rather than the transpose), and the semantics are short-circuiting (ie. it never helps to retry in case of an error), I’d expect to get either Err(Some(e)) indefinitely or Err(None) after the first error. The latter has the benefit if not having to store and clone the error, plus it feels semantically correct ("this iterator is finished due to an error condition", as opposed to Ok(None) meaning "finished normally").

Result<Option> has the problem that it’s possible to return a Err(None) without first returning Err(Some(e)) which would be a logic error, but I guess that’s just one of those things you have to live with unless you have a dependent type system.

7

One minor/annoying nit is the use of the word "indempotent". While that word is overloaded, all uses of that word I'm familiar with imply that state is not changed . While I imagine it's uncommon, it's perfectly acceptable for a FusedIterator to mutate itself when next is called after returning None so long as None is still returned.

8

For reference: that’s exactly what FusedFuture does.

I have no comment on whether it’s a good idea — I’ve never personally needed to write any code that depends on fusedness of anything.

9

Also possible, yes. The idea is "consume the iterator, advance it, return it if it can be advanced further".

10

Iterators have to return Result, otherwise you can't differentiate None elements and reaching the end of the iteration. But sure, errors do not mean explicitly the end of the iteration. We already discussed that for web elements, as none element, an empty element, an element with not proper value.

11

No, fallible iterators and lenders return Result<Option<Self::Item>, Self::Error>, so I don't understand your comment.

12

I think this depends on the circumstances. You may want to stop processing at the first error you encounter, in which case what you want kinda makes sense, but you may also want to perform N distinct operations and gather all the errors that happen.

13

Yeah, ignore me. I don't know what I was thinking about :smiley:

14

That's subtle. For example, imagine an iterator/lender reading and parsing lines from a file. Now, an I/O error, means you have clearly to stop. But a parsing error, that means handle it and go on, or stop if you don't want errors.

So, yes, I think you're right, and I think this means the current FalliableFusedLender implementation is not good (as it forces Ok(None)) after the first error.