Chain has an incorrect implementation of DoubleEndedIterator

[eefriedman]

Testcase:

struct CrazyIterator(bool);
impl CrazyIterator { fn new() -> CrazyIterator { CrazyIterator(false) } }
impl Iterator for CrazyIterator {
    type Item = i32;
    fn next(&mut self) -> Option<i32> {
        if self.0 { Some(1) } else { self.0 = true; None }
    }
}
impl DoubleEndedIterator for CrazyIterator {
    fn next_back(&mut self) -> Option<i32> {
        self.next()
    }
}

fn main() {
    println!("{}", CrazyIterator::new().chain(0..10).rev().any(|i| i > 10i32));
    println!("{}", (0..10).chain(CrazyIterator::new()).rev().any(|i| i > 10i32));
}

gives:

false
playpen: timeout triggered!

I'm pretty sure CrazyIterator isn't a legitimate implementation of DoubleEndedIterator, but the documentation doesn't say that explicitly, and it explicitly states that this is a legitimate implementation of Iterator. (If this is supposed to be allowed, std::iter::Chain has a bug.)

[steveklabnik]

next_back(), the only required method, does say "returning None if the range is empty."

[Gankra]

Specifically for any Iterator, you can call next, next, next, ... next k times until you see None, at which point unspecified behaviour occurs when you call next again. Replace any number of those next's with next_back and this also holds true for a DoubleEndedIterator.

Nothing else is guaranteed.

Chain is incorrectly implemented as:

impl<A, B> DoubleEndedIterator for Chain<A, B> where
    A: DoubleEndedIterator,
    B: DoubleEndedIterator<Item=A::Item>,
{
    #[inline]
    fn next_back(&mut self) -> Option<A::Item> {
        match self.b.next_back() {
            Some(x) => Some(x),
            None => self.a.next_back()
        }
    }
}

It should use the same strategy as next and use a boolean flag to avoid calling next_back after b has yielded None. I suggest a custom enum of BothAreFull | AIsEmpty | BIsEmpty | BothAreEmpty (which is necessary and sufficient to capture the correct semantics).

[bluss]

Just using .fuse() on both a and b should be enough, the logic is simpler that way.

Of course, putting the flags inside the chain struct itself is an optimization (packs the members better).

[Gankra]

This is true (spoil-sport! :P)