HRTB bug in streaming iterator

[Stebalien]

Full code playpen

So, I've been working on a hacky streaming iterator library and ran into what looks like a bug in the type checker involving higher ranked trait bounds.

In the code below, I've defined a Stream trait. To implement a stream, one implements Stream on &'a mut MyStream for all lifetimes 'a.

pub trait Stream {
    type Item;
    fn next(self) -> Option<Self::Item>;
}

// Example stream
pub struct Repeat(u64);

impl<'a> Stream for &'a mut Repeat {
    type Item = &'a u64;
    fn next(self) -> Option<Self::Item> {
        Some(&self.0)
    }
}

I then went ahead and implemented adapters for filter and map and an extension trait for applying these adapters:

pub struct Map<S, F> {
    stream: S,
    func: F,
}

impl<'a, A, F, T> Stream for &'a mut Map<A, F>
    where &'a mut A: Stream,
          F: FnMut(<&'a mut A as Stream>::Item) -> T,
{
    type Item = T;
    fn next(self) -> Option<T> {
        match self.stream.next() {
            Some(item) => Some((self.func)(item)),
            None => None,
        }
    }
}

pub struct Filter<S, F> {
    stream: S,
    func: F,
}

impl<'a, A, F, T> Stream for &'a mut Filter<A, F>
    where for<'b> &'b mut A: Stream<Item=T>, // <---- BAD
          F: FnMut(&T) -> bool,
{
    type Item = <&'a mut A as Stream>::Item;
    fn next(self) -> Option<Self::Item> {
        while let Some(item) = self.stream.next() {
            if (self.func)(&item) {
                return Some(item);
            }
        }
        None
    }
}

pub trait StreamExt where for<'b> &'b mut Self: Stream {
    fn map<F>(self, func: F) -> Map<Self, F>
        where Self: Sized,
              for<'a> &'a mut Map<Self, F>: Stream,
    {
        Map {
            func: func,
            stream: self,
        }
    }

    fn filter<F>(self, func: F) -> Filter<Self, F>
        where Self: Sized,
              for<'a> &'a mut Filter<Self, F>: Stream,
    {
        Filter {
            func: func,
            stream: self,
        }
    }

    fn count(mut self) -> usize
        where Self: Sized,
    {
        let mut count = 0;
        while let Some(_) = self.next() {
            count += 1;
        }
        count
    }
}

impl<T> StreamExt for T where for<'a> &'a mut T: Stream { }

The problem is the interaction between the Filter and Map adapters. The following works iff the map adapter appears before the filter adapter.

fn main() {
    let source = Repeat(10);
    let map = source.map(|x: &_| x); // Remove to break.
    let filter = map.filter(|x: &_| true);
    let count = filter.count(); // Assert that we still have a valid stream.
}

However, this should never work due to the for<'b> &'b mut A: Stream<Item=T> constraint on the Filter implementation above (marked BAD). Basically, this constraint should assert the stream's Item is the same independent of 'b which should mean that this item doesn't borrow from it's stream (as a matter of fact, I'm using this exact constraint to implement an adapter for converting streams to iterators). However, items returned by both the map and source streams above do obviously borrow from their streams.

Correct error without map:

test.rs:90:12: 90:32 error: type mismatch resolving `for<'b> <&'b mut Repeat as Stream>::Item == _`:
 expected bound lifetime parameter 'b,
    found concrete lifetime [E0271]
test.rs:90           .filter(|l: &_| true)
                      ^~~~~~~~~~~~~~~~~~~~
test.rs:90:12: 90:32 help: run `rustc --explain E0271` to see a detailed explanation
test.rs:91:12: 91:19 error: no method named `count` found for type `Filter<Repeat, [[email protected]:90:19: 90:31]>` in the current scope
test.rs:91           .count();
                      ^~~~~~~
test.rs:91:12: 91:19 note: the method `count` exists but the following trait bounds were not satisfied: `&'a mut Filter<Repeat, [[email protected]:90:19: 90:31]> : Stream`, `&'a mut &Filter<Repeat, [[email protected]:90:19: 90:31]> : Stream`, `&'a mut &mut Filter<Repeat, [[email protected]:90:19: 90:31]> : Stream`, `Filter<Repeat, [[email protected]:90:19: 90:31]> : core::iter::Iterator`
test.rs:91:12: 91:19 help: items from traits can only be used if the trait is implemented and in scope; the following traits define an item `count`, perhaps you need to implement one of them:
test.rs:91:12: 91:19 help: candidate #1: `StreamExt`
test.rs:91:12: 91:19 help: candidate #2: `core::iter::Iterator`
error: aborting due to 2 previous errors

[pnkfelix]

This is now rejected in both editions on both beta+nightly with the following diagnostic:

error: implementation of `Stream` is not general enough
  --> src/main.rs:90:22
   |
90 |     let map = source.map(|x: &_| x); // Remove to break.
   |                      ^^^
   |
   = note: `Stream` would have to be implemented for the type `&'0 mut Map<Repeat, [closure@src/main.rs:90:26: 90:35]>`, for any lifetime `'0`
   = note: but `Stream` is actually implemented for the type `&'1 mut Map<Repeat, [closure@src/main.rs:90:26: 90:35]>`, for some specific lifetime `'1`

error: aborting due to previous error

Tagging as E-needstest