`core::iter::Fuse` Does Not Fuse Iterators

[asquared31415]

This is acknowledged in Iterator::fuse with

fuse() may therefore behave incorrectly if the FusedIterator trait is improperly implemented.

But I believe this should not be the case. Fuse still incurs a memory overhead for all iterators, whether or not it specializes, and it's useless because it currently doesn't actually do anything in the general case.

Example code:

struct UwU<'a>(&'a (), bool);

impl<'a> Iterator for UwU<'a> {
    type Item = bool;
    fn next(&mut self) -> Option<Self::Item> {
        self.1 = !self.1;
        match self.1 {
            true => Some(true),
            false => None,
        }
    }
}

impl<'a> std::iter::FusedIterator for UwU<'a> { }

fn main() {
    let a = ();
    let mut owo = UwU(&a, true).fuse();
    assert_eq!(owo.next(), None);

    // this should ideally hold because we called `fuse`, and 
    // the first call was `None` but it returns `Some`
    assert_eq!(owo.next(), None);
}

It fails with

thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `Some(true)`,
 right: `None`', /app/example.rs:23:5

Since rustc 1.26.0, when this type was added, through current nightly (2022-08-13).

[scottmcm]

and it's useless because it currently doesn't actually do anything in the general case.

This is a massive overstatement. Agreed, you can't depend on it for the soundness of your unsafe { code }.

But that's normal. You can't depend on Eq for the soundness of your unsafe { code } either, but that doesn't make Eq useless. See this IRLO thread for a recent discussion: https://internals.rust-lang.org/t/documentation-must-vs-should/16967?u=scottmcm

And, practically, I don't think copy-pasting a big "you can't rely on this for soundness" section onto every single non-unsafe trait is productive. That's a general rule of Rust, so it belongs in the book or similar, not on every trait definition.

[asquared31415]

This issue is specifically about the type core::iter::Fuse not behaving as it claims it does in its docs:

An iterator that yields None forever after the underlying iterator yields None once.

It would be like if Vec::push didn't actually push sometimes for certain T, or Rc not properly decrementing the reference count sometimes. These types would not be behaving as documented, and that's clearly a bug either in the docs or the implementation.

The only reason the FusedIterator trait comes up is because Fuse specializes on it, and when it does, it loses all guarantees about behavior.

[the8472]

That simply means Fuse relies on/delegates to the API contract of FusedIterator in some cases. APIs build on each other all the time.

It would be like if Vec::push didn't actually push sometimes for certain T

I mean if you have a Vec<T, A> with a magic allocator that returns FUSE-backed memory-mapped memory that occasionally makes your values vanish (i.e. breaks the Alloc API contract), then yeah Vec will misbehave.

and it's useless because it currently doesn't actually do anything in the general case.

Fuse is useful because it gives generic code that needs a fused iterator to take an iterator that already is self-fusing or fuse it through that API. It glues FusedIterator behavior onto the iterator. With the same guarantees you always (or never) had from FusedIterator in the first place.

[asquared31415]

Fuse is useful because it gives generic code that needs a fused iterator to take an iterator that already is self-fusing or fuse it through that API.

This is not true, the API doesn't actually do anything for generic code that needs a fused iterator, despite Fuse being a std type that claims it does. The best case is when an iterator does not implement FusedIterator or is a cooperative impl, when it actually fuses, but the worst case is that it doesn't fuse at all when FusedIterator is implemented when it does not hold.

The fact that not implementing the marker trait can be more useful than implementing it badly is a bug, is extremely unintuitive behavior, and because generic code needs to be able to handle the worst case always, makes this type useless.

I don't see why Fuse can't be changed to actually work 100% of the time, like it's docs say? Surely that makes it actually useful, since it's always a memory overhead, but as is it can't work for generic code.

The main problem is that Fuse does not behave as its docs claim. Either the docs are incorrect, and they need to say "do not use Fuse if you actually need a fused iterator in generic code", or the implementation needs to be fixed.

[the8472]

This is not true, the API doesn't actually do anything for generic code that needs a fused iterator,

The generic code takes any iter: impl Iterator and then calls iter.fuse(). It now has an iterator that implements FusedIterator. That is all it does. You get the FusedIterator guarantees. And those guarantees always come with the caveat "well, someone might have implemented this incorrectly". We call those bugs and they need to be fixed. This caveat also applies to unsafe traits.

safe trait: someone implements this incorrectly -> it'll OOM, make your rockets explode mid-flight, irradiate people, drain your bank account or make planes fall out of the sky
unsafe trait: someone implements this incorrectly -> it'll OOM, make your rockets explode mid-flight, irradiate people, drain your bank account, make planes fall out of the sky, cause miscompilations or memory corruption

API contract violations are forbidden. The only difference is which sets of consequences a violation may have if someone does the forbidden thing.

[asquared31415]

The return type is a core::iter::Fuse, which claims it properly fuses, not an opaque impl FusedIterator. Fuse has additional logic to not actually fuse when the wrapped type implements FusedIterator. Fuse is the std type that is behaving incorrectly, because it does not require FusedIterator nor does it say that it "might sometimes fuse", it says

An iterator that yields None forever after the underlying iterator yields None once.

which is strictly not true. No caveats for bad impls are talked about, no exceptions are made, it is not a generic API taking FusedIterator it is a concrete type that behaves poorly. There is no API contract on Fuse for user code to violate, it claims to always work.

[asquared31415]

I mean if you have a Vec<T, A> with a magic allocator that returns FUSE-backed memory-mapped memory that occasionally makes your values vanish (i.e. breaks the Alloc API contract), then yeah Vec will misbehave.

Additionally this example does not apply, because there is a contract on the allocator for Vec, violating that would be wrong, obviously. But there's no such contract for Fuse, no generic traits in its API, nothing. It's a direct result of specialization that is hidden from the user.

[asquared31415]

Also even if Fuse is technically correct, why would we want it to be intentionally malicious? As far as I am aware, it very well could be correct always, and it would be a simpler implementation, and incur no major additional costs. Being as well behaved as possible under sub-optimal circumstances is a positive. There's many places library types or the compiler could do a lot more, but choose to be benevolent because why would a user want code to actively fight them for at best a minor improvement.

[the8472]

No caveats for bad impls are talked about

APIs are not required to state "does misbehave if traits aren't upheld". Adding those notes is a courtesy, usually added when multiple people tripped over a requirement. The absence of such statements is not a guarantee in itself. Otherwise we would be forced to document implementation details (this calls X, Y and Z and relies on their behavior) on even the most trivial things.

E.g. iterator adapters don't tell you either which methods they forward. The default behavior is phrased in terms of next but often fold uses the inner's fold. So even if the inner's next is correct but the fold is buggy then so will be the outer fold. But we don't document the exact behavior because that might change.

If something is buggy somewhere then bugs will cascade until it hits something that is more defensive than whatever they cascaded through. GIGO, garbage in - garbage out.

why would we want it to be intentionally malicious?

Why are you assuming malice? This is a performance optimization that eliminates a branch inside loops which in turn can be vital for auto-vectorization.

The return type is a core::iter::Fuse, which claims it properly fuses, not an opaque impl FusedIterator.

They offer the same guarantees, so one can be substituted for the other.

[asquared31415]

They offer the same guarantees, so one can be substituted for the other.

If they offer the same guarantees, at least one has incorrect docs, because a safe marker trait offers no guarantees, but Fuse's docs claim to have some specified behavior.

[asquared31415]

Additionally, after some (admittedly limited) testing, I have not found a case where the specialization on FusedIterator improved codegen. It either was equivalent when the iterator was actually fused, or regressed codegen because it did not actually fuse.

[the8472]

std::iter::FusedIterator
An iterator that always continues to yield None when exhausted.

fn fuse(self) -> Fuseⓘ
Creates an iterator which ends after the first None.

Struct std::iter::Fuse
An iterator that yields None forever after the underlying iterator yields None once.

They all promise the same thing, phrased slightly differently.

[the8472]

Ah, I realize I was arguing from the perspective of safe code. For unsafe code the situation changes somewhat. At least the standard library knows its own implementation and so knows which safe parts unsafe code can trust. The situation is less clear for 3rd party unsafe code because it's not allowed to rely on implementation details.