`impl FusedIterator for Cycle<I>` is incorrect

[fee1-dead]

I tried this code on playground:

// Cycle implementation
/*
    fn next(&mut self) -> Option<<I as Iterator>::Item> {
        match self.iter.next() {
            None => {
                self.iter = self.orig.clone();
                self.iter.next()
            }
            y => y,
        }
    }
*/
use std::iter::FusedIterator;
use std::rc::Rc;
use std::cell::Cell;

pub struct ErraticIterator(Rc<Cell<usize>>, Option<()>);

impl Clone for ErraticIterator {
    fn clone(&self) -> ErraticIterator {
        self.0.set(self.0.get() + 1);
        
        Self(self.0.clone(), Some(()))
    }
}

impl Iterator for ErraticIterator {
    type Item = ();
    
    // Cycle behavior:
    //
    // Some(())
    // None -> .clone() -> None
    // Some(())
    // None -> .clone() -> None
    // ..
    fn next(&mut self) -> Option<()> {
        if self.0.get() % 2 == 0 {
            self.1.take()
        } else {
            None
        }
    }
}

pub fn fused_iter(it: &mut impl FusedIterator<Item = ()>) {
    it.for_each(|()| {});
    
    assert!(it.next().is_none());
}

fn main() {
    let it = ErraticIterator(Rc::new(Cell::new(0)), Some(()));
    fused_iter(&mut it.cycle())
}

I expected to see this happen: Cycle<ErraticIterator> should not be fuse thus compilation should fail.

Instead, this happened: Cycle implements FusedIterator, so the assertion fails that should always pass for actually fused iterators.

[the8472]

This is an interesting one. None of the iterator marker traits guarantee anything what Clone does. TrustedRandomAccess sort of implies it, but doesn't spell it out exactly either. So technically we can't even rely on where I: Clone + FusedIterator.
On the other hand FusedIterator is a safe trait, so we could allow it to do the wrong thing if a clone implementation does the wrong thing. On the gripping hand, it's a specialization trait...

[cuviper]

The "erratic" input iterator could realistically be something that's influenced by external state, like channels:

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

fn main() {
    let (sender, receiver) = channel();
    let iter = iter::from_fn(|| receiver.try_recv().ok());
    for i in 1..=10 {
        sender.send(i).unwrap();
    }
    run(&sender, iter.cycle());
}

fn run(sender: &Sender<i32>, mut iter: impl FusedIterator<Item = i32>) {
    for x in &mut iter {
        dbg!(x);
    }
    sender.send(42).unwrap();
    assert_eq!(iter.next(), None);
}

It doesn't really make sense to cycle that, but it's possible.

So technically we can't even rely on where I: Clone + FusedIterator.

You could even .fuse() my example before the .cycle(), and it will still fail because self.orig won't get fused. So if we want Cycle to be a FusedIterator, I think it's going to have to track that state explicitly.

[cuviper]

Cycle::try_fold also makes an assumption about clones being identical -- it makes one pass that's careful to guard against empty iterators, then an infinite loop assuming it will never be empty afterward.