Impl LendingIterator for Either

help
1

I am trying to use GATs to write some poor man's lending iterators, and I also need to impl them for Either. The bare bones of the trait is:

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

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

The idea behind implementing LendingIterator for Either is to match the Item between the two iterators, like in the actual impl for Iterator:

impl<A, B> LendingIterator for Either<A, B>
where
    A: LendingIterator,
    B: LendingIterator<Item<'_> = A::Item<'_>>,
{
    type Item<'a>
    where
        Self: 'a,
    = <A as LendingIterator>::Item<'a>;

    fn next(&mut self) -> Option<Self::Item<'_>> {
        match self {
            Either::Left(iter) => iter.next(),
            Either::Right(iter) => iter.next(),
        }
    }
}

Playground

This does not work because B: LendingIterator<Item<'_> = A::Item<'_>> is not valid -- anonymous lifetimes cannot be used in this way. However, if I try to use HRTB it still does not compile:

impl<A, B> LendingIterator for Either<A, B>
where
    A: LendingIterator,
    B: for<'a> LendingIterator<Item<'a> = A::Item<'a>>,
{
    /* ... */
}

I think that the error makes sense, because we should express the fact that A: 'a, or in other words the bound is not valid for every lifetime 'a.

Any ideas?

2

I think the HRTB can't be fulfilled because the Item<'a> is limited to cases where Self: 'a, while the HRTB is unlimited. And due to the issue 87479 lint, you can't make the GAT unlimited. I don't think this particular example is cited yet; probably you could mention it.

The workaround mentioned works on stable. Here's an example that compiles (which I didn't try to utilize or minimize).

1 Like
3

Thank you so much!
The issue with HRTB was exactly the one I was thinking, but I was not aware of the workaround you mentioned. It is a very clever solution! :heart:

4

I feel like the issue here isn’t the Self: 'a bound (that one is actually really useful for a LendingIterator trait) and more the fact that GATs don’t have any syntax for specifying the Item type being equal to something else.

The typical workaround that keeps the Self: 'a bound works, too. Hrtb-based workaround do support such an the kind of equality constraint that GATs don’t have any syntax for. I hope this problem is tracked somewhere already, but I haven’t looked.

Here’s a workaround that keeps the Self: 'a bound: Rust Playground

Using this approach, it should even be possible to write the implementation for the GAT-based trait, by using a helper-trait: Rust Playground

2 Likes
5

For the record, you can also use some custom type-equality trait here: Rust Playground

error[E0582]: binding for associated type `To` references lifetime `'a`, which does not appear in the trait input types
  --> src/lib.rs:16:38
   |
16 |     for<'a> A::Item<'a>: TypeIsEqual<To = B::Item<'a>>,
   |                                      ^^^^^^^^^^^^^^^^

:sweat_smile: ehm… well, that error is certainly really weird, but – I can add an additional but somehow seemingly useless lifetime argument to make this work… Rust Playground

Or actually… a trait synonym fixes the error, too: Rust Playground

See here for some more information about how to use such a type-equality helper trait.

1 Like
6

Thank you so much @steffahn, you are showing very good and intriguing approaches. I surely have to learn a lot from your code :heart:.

7

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.