Closure type problem in LendingIterator::map

Hi, I am trying to implement the LendingIterator by GAT. However, when I am trying to deal with map method I got problem. Definitely, the closure must be applied with generic associated type with lifetime parameter, so it must use HRTB. But it seems like not be able to inference the literal closuer as below. Is there any way to complete this code? Hope for your reply, thanks.

#![feature(generic_associated_types)]

#[derive(Debug)]
pub struct Iter<'cx, Cx, I> {
    inner: I,
    context: &'cx mut Cx,
}

#[derive(Debug)]
struct Map<I, F> {
    iter: I,
    f: F,
}

impl<I, F> Map<I, F>
where
    I: LendingIterator,
{
    fn new(iter: I, f: F) -> Self {
        Map { iter, f }
    }
}

trait LendingIterator {
    type Item<'s>: 's
    where
        Self: 's;

    type Context<'cx>: 'cx
    where
        Self: 'cx;

    fn next<'s, 'cx>(&'s mut self) -> Option<(Self::Context<'cx>, Self::Item<'s>)>
    where
        's: 'cx;

    fn map<'s, 'cx, F, B>(self, f: F) -> Map<Self, F>
    where
        Self: Sized,
        Self: 'cx,
        Self: 's,
    {
        Map::new(self, f)
    }
}

impl<Cx, I> LendingIterator for Iter<'_, Cx, I>
where
    I: Iterator,
{
    type Item<'s> = I::Item
    where
        Self: 's;

    type Context<'cx> = &'cx mut Cx
    where
        Self: 'cx;

    fn next<'s, 'cx>(&'s mut self) -> Option<(Self::Context<'cx>, Self::Item<'s>)>
    where
        's: 'cx,
    {
        self.inner.next().map(|item| (&mut *self.context, item))
    }
}

impl<I, F, B> LendingIterator for Map<I, F>
where
    I: LendingIterator,
    B: Send + 'static,
    for<'s, 'cx> F: FnMut(&mut I::Context<'cx>, I::Item<'s>) -> B,
{
    type Item<'s> = B
    where
        Self: 's;

    type Context<'cx> = I::Context<'cx>
    where
        Self: 'cx;

    fn next<'s, 'cx>(&'s mut self) -> Option<(Self::Context<'cx>, Self::Item<'s>)>
    where
        's: 'cx,
    {
        while let Some((mut context, item)) = self.iter.next() {
            let item = (self.f)(&mut context, item);
            return Some((context, item));
        }
        None
    }
}

fn main() {
    let v: Vec<i32> = vec![1, 2, 3];
    let mut c = ();
    let mut i = Iter {
        inner: v.iter(),
        context: &mut c,
    }
    .map(|context, item| item + 1);
    while let Some(item) = i.next() {
        println!("{:?}", item);
    }
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0599]: the method `next` exists for struct `Map<Iter<'_, (), std::slice::Iter<'_, i32>>, [closure@src/main.rs:100:10: 100:25]>`, but its trait bounds were not satisfied
   --> src/main.rs:101:30
    |
10  | struct Map<I, F> {
    | ----------------
    | |
    | method `next` not found for this struct
    | doesn't satisfy `_: LendingIterator`
...
100 |     .map(|context, item| item + 1);
    |          ---------------
    |          |
    |          doesn't satisfy `<_ as FnOnce<(&mut &'cx mut (), &i32)>>::Output = _`
    |          doesn't satisfy `_: FnMut<(&mut &'cx mut (), &i32)>`
101 |     while let Some(item) = i.next() {
    |                              ^^^^ method cannot be called on `Map<Iter<'_, (), std::slice::Iter<'_, i32>>, [closure@src/main.rs:100:10: 100:25]>` due to unsatisfied trait bounds
    |
note: trait bound `[closure@src/main.rs:100:10: 100:25]: FnMut<(&mut &'cx mut (), &i32)>` was not satisfied
   --> src/main.rs:71:21
    |
67  | impl<I, F, B> LendingIterator for Map<I, F>
    |               ---------------     ---------
...
71  |     for<'s, 'cx> F: FnMut(&mut I::Context<'cx>, I::Item<'s>) -> B,
    |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ unsatisfied trait bound introduced here
note: trait bound `<[closure@src/main.rs:100:10: 100:25] as FnOnce<(&mut &'cx mut (), &i32)>>::Output = _` was not satisfied
   --> src/main.rs:71:65
    |
67  | impl<I, F, B> LendingIterator for Map<I, F>
    |               ---------------     ---------
...
71  |     for<'s, 'cx> F: FnMut(&mut I::Context<'cx>, I::Item<'s>) -> B,
    |                                                                 ^ unsatisfied trait bound introduced here

For more information about this error, try `rustc --explain E0599`.
error: could not compile `playground` due to previous error

I played with it a little but didn't really make progress. More generally, GATs are pretty broken when it comes to higher-ranked bounds and things like iterator adapters in general:

My first guess was that the compiler isn't smart enough to reconcile the single-type parameter B with the associated type constructor Item<'_> as it goes through the higher-ranked trait bound of F. However, you can't do

for<'s, 'cx> F: FnMut(&mut I::Context<'cx>, I::Item<'s>) 
  -> <Self as LendingIterator>::Item<'s>,

and I'm not sure I'd expect that to work in this case anyway, as this higher-ranked bound doesn't account for the Self: 's requirement. But it's worse than that; even after falling back to explicit function pointers and getting rid of B, the compiler doesn't see through the GAT projection for the arguments, either.

Consider filing another issue for this use-case.


The 's: 'ctx bound on next seems fishy to me too -- added to satisfy the invariance challenges of the Iter<'_, _, _> implementation? However, changing the signature to

    fn next(&mut self) -> Option<(Self::Context<'_>, Self::Item<'_>)>

didn't help with the error being shown as far as I could tell.

1 Like

Lifetime GATs (like those required for LendingIterator) can be emulated on stable, so I decided to give it a go here. After going a little ways, we can see the variance problem a bit more clearly. You can only pull a &'short mut T from a &'short mut &'long mut T; you can't get a &'long mut T out. The compiler suggests adding a bound: 'short: 'long. But as we have a &'short mut &'long mut T, there's already an implied restriction that 'long: 'short. Taken together, this means that 'long and 'short must be the same.

(The unconstrained lifetime on next is probably another sign -- with the framework that 'cx should be an internal lifetime, it should probably be something like

fn<'x, 'cx: 'x>(&'x mut self) -> Option<LigOutput<'x, 'cx, Self>>

but if having two distinct lifetimes can't work for your use case I don't know that there's any reason to puruse that line.)


If we then simplify the trait to have a single lifetime, everything in the example can be made to work. One interesting thing here is that I actually needed the LendingIterator bound here:

    fn map<F>(self, f: F) -> Map<Self, F>
    where
        Self: Sized,
        Map<Self, F>: LendingIterator,

Otherwise, the compiler doesn't infer that the closure needs to be higher-ranked in a particular way. Putting the requirement on map allows it to see the requirement at the inference site. There are other ways around that common closure shortcoming, but this seems pretty clean relative to those.


Here's an article on the topic that has more detail and goes further.

2 Likes

Thank you, your exploration helps me a lot, it give me more information about the essence of this problem, my origin version error message does not makes any sense. the final version which bases on stable compiler is very interesting, I need more time to research and understand it. Thanks again.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.