Peekable's .peek() does not remember seeing a None

[bluss]

If you use iterator.peekable(), call .peek() and see None, peekable does not remember that.

This means that the next call to either .peek() or .next() will query the underlying iterator again, making it easy to create fusing bugs. (A well behaved iterator user should not call .next() on a generic iterator that has already returned None once.)

Example program which ends up being an infinite loop (the while let loop). (playground link)

/// This is an iterator that is in line with the contract
/// of the Iterator trait, but it is not fused.
/// After having returned None once, it will start producing elements
/// if .next() is called again.
pub struct CycleIter<'a, T: 'a> {
    index: usize,
    data: &'a [T],
}

pub fn cycle<T>(data: &[T]) -> CycleIter<T> {
    CycleIter {
        index: 0,
        data: data,
    }
}

impl<'a, T> Iterator for CycleIter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        let elt = self.data.get(self.index);
        self.index += 1;
        self.index %= 1 + self.data.len();
        elt
    }
}

fn main() {
    let data = [1, 2, 3];
    // show that it works like a regular iterator
    for elt in cycle(&data) {
        print!("{}, ", elt);
    }
    println!("");
    
    // Demonstrate that it's easy to create bugs with peekable
    let mut iter = cycle(&data).peekable();
    
    while let Some(elt) = iter.next() {
        let is_the_last = iter.peek().is_none();
        println!("Saw element={}, is the last={:?}", elt, is_the_last);
    }
}

[sfackler]

I'd definitely argue that this is a bug in Peekable.

[ghost]

possible fix: https://is.gd/JOnbyZ

pub struct Peekable<I: Iterator> {
    iter: I,
    peeked: Option<Option<I::Item>>,
}
impl<I: Iterator> Iterator for Peekable<I> {
    type Item = I::Item;

    #[inline]
    fn next(&mut self) -> Option<I::Item> {
        match self.peeked.take() {
            Some(v) => v,
            None => self.iter.next()
        }
    }
}
impl<I: Iterator> Peekable<I> {
    fn peek(&mut self) -> Option<&I::Item> {
        if self.peeked.is_none() {
            self.peeked = Some(self.iter.next());
        }
        match self.peeked {
            Some(Some(ref value)) => Some(value),
            Some(None) => None,
            _ => unreachable!()
        }
    }
}

[Stebalien]

I disagree. Peekable is an iterator adapter like Map, Filter, etc. and none of those remember whether or not the underlying iterator has returned None. Peekable is perfectly well-behaved as long as the underlying generic iterator is.

[bluss]

@Stebalien That depends on what category the .peek method is placed in. If this is fine, then "peek" counts as driving the iterator forward, and the user must take care to not call .next() after None is returned from .peek().

So I think this is about not if the iterator should remember it, but in particular the peek method. In fact, the fix is probably going to leave Peekable unfused still, because if the peek method is not used, the peeking state is unused too.

[Stebalien]

Ah, I see. I agree. Also note, any fix for this could be specialized on the underlying iterator implementing FusedIterator.