Flatten and FlatMap have incorrect bounds for their FusedIterator impls

[SkiFire13]

I would expect the following code to either not compile (because iter shouldn't implement FusedIterator) or to not panic (because it does, so its contract should guarantee that calling next after the first None will always return None), however it compiles and panics:

use core::iter::FusedIterator;

fn check_is_fused<T, I: Iterator<Item = T> + FusedIterator>(mut i: I) {
    while let Some(_) = i.next() {}
    assert!(i.next().is_none());
}

struct NonFusedIter(bool);

impl Iterator for NonFusedIter {
    type Item = ();
    fn next(&mut self) -> Option<Self::Item> {
        self.0 = !self.0;
        Some(()).filter(|_| !self.0)
    }
}

impl DoubleEndedIterator for NonFusedIter {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.0 = !self.0;
        Some(()).filter(|_| !self.0)
    }
}

fn main() {
    let mut iter = vec![NonFusedIter(true)].into_iter().flatten();
    iter.next_back();
    check_is_fused(iter);
}

Playground example

This is caused by the fact that the impl of FusedIterator for Flatten only requires the outer iterator to implement FusedIterator, not the inner one, however the implementation doesn't actually fuse backiter, which is what causes the assert to fail. The same problem is present for FlatMap.

Possible solutions:

• Change how FlattenCompat is implemented to guarantee it to be fused even if the inner iterators are not fused. This would silently change its behavior, however it wouldn't be a breaking change.
• Change the bounds for those impls. This would be a (minor?) breaking change.

Additionally I don't think there's anything that requires the outer iterator to always be manually fused in FlattenCompat. Should we also change it in the process?

See also https://users.rust-lang.org/t/why-doesn-t-std-flatten-implement-std-fusediterator-regardless-if-the-outer-or-inner-iterators-do/54477

[cuviper]

Change how FlattenCompat is implemented to guarantee it to be fused even if the inner iterators are not fused. This would silently change its behavior, however it wouldn't be a breaking change.

I think this is the best choice. They're already semi-fused in an unspecified manner, so I'm not concerned about the behavior change of going all the way.

That's not to say the front/back should be Fuse<U> though, because that has some potential performance impacts for the specialized U: FusedIterator -- we'd end up calling those no-ops repeatedly before moving to the other parts. That's already true for the iter: Fuse<I>, but I think a more limited impact.

Additionally I don't think there's anything that requires the outer iterator to always be manually fused in FlattenCompat. Should we also change it in the process?

That's a relatively recent feature of #68915. We could decide to commit unconditional FusedIterator after fixing this bug.