Referring to a GAT

[vigna]

This code won't compile:

#[::nougat::gat]
impl<I: GraphIterator> LendingIterator for Adapter<I> {
    type Item<'a> = (usize, <I as GraphIterator>::Successors<'a>)
    where Self: 'a;

    fn next(&mut self) -> Option<Self::Item<'_>> {
        self.0.next_inner()
    }
}

The problem is that apparently the macro fiddles also with ::Sucessors, while it should just leave it alone. How can we achieve that?

(I realize it is not a compilable snippet, but I think the problem we have is clear—I can produce a compilable example if you need it.)

[danielhenrymantilla]

Thanks for the report! While I think about a fix or re-design[^1] to palliate this issue, FWIW, you should be able to work around the issue by defining a helper type alias:

type GraphIteratorSuccessors<'next, I> = <I as GraphIterator>::Successors<'next>;

#[::nougat::gat]
impl<I : GraphIterator> LendingIterator for Adapter<I> {
    type Item<'next> = (usize, GraphIteratorSuccessors<'next, I>)
    where
        Self : 'next,
    ;

    fn next(&mut self) -> Option<Self::Item<'_>> {
        self.0.next_inner()
    }
}

[^1]: I'd like for the next release of lending-iterator not to need nougat

[vigna]

Thanks for the answer! Next question :), how do I make this work:

pub fn extend<'a, 'b, I: Iterator<Item = usize>, L: LendingIterator<Item<'b> = (usize, I)>>(
&mut self,
        iter_nodes: &'b mut L,
    ){}

as the compiler complains that Item is not an associated type. I've read your note about using Item<'_,I> but I need to constrain the type of the returned item instead (note that the answer might obvious, I've been programming Rust since just six months).

[danielhenrymantilla]

So, the main solution here is to be using #[apply(Gat)] on the fn. The issue, then, is that LendingIterator (and nougat) involve for<'next> kind of bounds, and your 'b-specific extra bound then makes it run into a limitation of Rust.

There are then two workarounds:

• either you write the bound as valid for all lifetimes (while this seems nice, in practice, it will only be usable if the LendingIterator isn't truly lending / if I does not depend on 'c)
• to use a trait "type eq" bound rather than a direct = bound, since this allows using an extra line/clause.

#[apply(Gat!)]
pub fn extend<'a, 'b, I, L>(
    &mut self,
    iter_nodes: &'b mut L,
)
where
    I : Iterator<Item = usize>,
    L : for<'c> LendingIterator<Item<'c> = (usize, I)>,
{
    let it: (usize, I) = iter_nodes.next().unwrap();
}

#[apply(Gat!)]
pub fn extend2<'a, 'b, I, L>(
    &mut self,
    iter_nodes: &'b mut L,
)
where
    I : Iterator<Item = usize>,
    L : LendingIterator,
 // <L as LendingIterator>::Item<'b>           = (usize, I) ,
    <L as LendingIterator>::Item<'b> : Is<EqTo = (usize, I)>,
{
    let it: (usize, I) = Is::eq_to(iter_nodes.next().unwrap());
}

• trait Is helper

  ```rust trait Is { type EqTo; fn eq_to(this: Self) -> Self::EqTo; } impl Is for T { type EqTo = Self; fn eq_to(this: Self) -> Self::EqTo { this } } ```

• Playground

[vigna]

That's definitely type magick. I understand that Is::eq_to() will extract the type, but I can't see how to write a while let Some((x,i)) = iter.next() {}. I mean, I tried, but...

Playground

[danielhenrymantilla]

Yeah, this is a bit subtle to explain; do you happen to be on Discord or some other instant messaging platform? It may be easier to work with there than over here 🙂

1. The Rust Community Discord server: https://discord.gg/rust-lang-community

2. You can then create a post over #rust-help-forum

3. You can then ping me when doing so: @yandros

---

Otherwise, the TL,DR, if we remove usize from the situation to simplify things, what you have is (ignoring nougat syntax sugar/hacks, imagining full GATs all the way):

```rs … where for<'c> ::Item<'c> : Iterator , ``` _i.e._, ```rs where for<'c> exists I<'c> : Iterator where L : LendingIterator = I<'c>> , ``` (in pseudo-code). But when we write: ```rs where for<'c> L : LendingIterator = I> , ``` Notice how we are expressing that the lended item does not depend on the `'c = 'next` lending-lifetime of `fn next(&'c mut self)`! So that boils down to defeating the very purpose of `LendingIterator`s to begin with! Hence my: > either you write the bound as valid for all lifetimes (while this seems nice, in practice, **it will only be usable if the `LendingIterator` isn't truly lending / if `I` does not depend on `'c`**) Now, when we do write: ```rs ::Item<'b>: Is ``` what we are saying is no longer a `for<'c>`-quantified clause, but, instead, a "punctual" statement/contraint/clause, stating that when the input `'c` happens to be exactly equal to `'b`, we are getting this outer/fixed `I` iterator. - This has the advantage of not _eagerly_ restricting the `for<'c> …::Item<'c>` to be some `'c`-independent fixed iterator `I`, as we've just seen in the previous part; - But it does restrict the `.next()` call(s) able to yield this known `I` to be of this fixed `'b` lifetime. In Rust, generic lifetime parameters (thus provided by the _caller_), necessarily span beyond the internal body of the callee's function: ```rust iterator.next() // ---- start of borrow ---+ // | // | // | } // <----------- 'fn body --------------------| // ⋮ caller leeway in their choice of `'b` // <--------------- end of 'b -----------------+ ``` But, if you want to call `.next()` multiple times inside that _callee_ function, you need the borrow of each `.next()` call (but for the last one) to be shorter than `'fn`: ```rs iterator.next() // ---- start of borrow ---+ // | // | // <-- first borrow must have ended here --+ iterator.next() // - start of new borrow --+ // | // | // <--- snd borrow must have ended here ---+ // etc. } // <----------- 'fn body --------------------| ``` Hence the problem. So, back to my `exists I<'c>` pseudo-code, what we wanted to express was: ```rs where for<'c> exists I<'c> : Iterator where L : LendingIterator = I<'c>> , ``` Which, alas, is not something directly expressible in Rust. What we do, in these cases, is just to skip this `I<'c>` "alias", and always refer to `L::Item<'c>`: ```rs where L : LendingIterator, for<'c> Item<'c, L> : Iterator , ``` Now, the problem is that in your case you had `(usize, I<'c>)` rather than just `I<'c>`. This is where the current expressibility of Rust really runs into limitations. 1. Since in this form we can only write trait bounds for `L::Item<'c>`, 1. but since trait bounds allow introducing new associated items, 1. then the solution would be to "trait-ify" being a `(T, U)` 2-tuple: ```rs trait Tuple2 { type _0; type _1; fn is_tuple(self) -> (Self::_0, Self::_1); } impl Tuple2 for (T, U) { type _0 = T; type _1 = U; fn is_tuple(self) -> (Self::_0, Self::_1) { self } } ``` 1. And from there: ```rs #[apply(Gat!)] pub fn extend(&mut self, iter_nodes: &mut L) where L : LendingIterator, for<'c> Item<'c, L> : Tuple2<_0 = usize> , for<'c> as Tuple2>::_1 : Iterator , { while let Some((idx, iter)) = iter_nodes.next().map(|it| it.is_tuple()) { for n in iter { let _: usize = n; } } } ``` [Playground](https://www.rustexplorer.com/b#LyoKW2RlcGVuZGVuY2llc10KbGVuZGluZy1pdGVyYXRvci52ZXJzaW9uID0gIjAuMS43IgojIG5vdWdhdC52ZXJzaW9uID0gIjAuMi40IgoqLwpmbiBtYWluKCkge30KCnVzZSA6OmxlbmRpbmdfaXRlcmF0b3I6OnByZWx1ZGU6Oio7CgpzdHJ1Y3QgRm9vOwoKdHJhaXQgSXMgewogICAgdHlwZSBFcVRvOwoKICAgIGZuIGVxX3RvKHRoaXM6IFNlbGYpIC0+IFNlbGY6OkVxVG87Cn0KCmltcGw8VD4gSXMgZm9yIFQgewogICAgdHlwZSBFcVRvID0gU2VsZjsKCiAgICBmbiBlcV90byh0aGlzOiBTZWxmKSAtPiBTZWxmOjpFcVRvIHsKICAgICAgICB0aGlzCiAgICB9Cn0KCnRyYWl0IFR1cGxlMiB7CiAgICB0eXBlIF8wOwogICAgdHlwZSBfMTsKCiAgICBmbiBpc190dXBsZShzZWxmKSAtPiAoU2VsZjo6XzAsIFNlbGY6Ol8xKTsKfQoKaW1wbDxULCBVPiBUdXBsZTIgZm9yIChULCBVKSB7CiAgICB0eXBlIF8wID0gVDsKICAgIHR5cGUgXzEgPSBVOwoKICAgIGZuIGlzX3R1cGxlKHNlbGYpIC0+IChTZWxmOjpfMCwgU2VsZjo6XzEpIHsKICAgICAgICBzZWxmCiAgICB9Cn0KCmltcGwgRm9vIHsKICAgICNbYXBwbHkoR2F0ISldCiAgICBwdWIgZm4gZXh0ZW5kPEw+KCZtdXQgc2VsZiwgaXRlcl9ub2RlczogJm11dCBMKQogICAgd2hlcmUKICAgICAgICBMIDogTGVuZGluZ0l0ZXJhdG9yLAogICAgICAgIGZvcjwnYz4KICAgICAgICAgICAgPEwgYXMgTGVuZGluZ0l0ZXJhdG9yPjo6SXRlbTwnYz4gOiBUdXBsZTI8XzAgPSB1c2l6ZT4KICAgICAgICAsCiAgICAgICAgZm9yPCdjPgogICAgICAgICAgICA8PEwgYXMgTGVuZGluZ0l0ZXJhdG9yPjo6SXRlbTwnYz4gYXMgVHVwbGUyPjo6XzEgOiBJdGVyYXRvcjxJdGVtID0gdXNpemU+CiAgICAgICAgLAogICAgewogICAgICAgIHdoaWxlIGxldCBTb21lKChpZHgsIGl0ZXIpKSA9IGl0ZXJfbm9kZXMubmV4dCgpLm1hcCh8aXR8IGl0LmlzX3R1cGxlKCkpIHsKICAgICAgICAgICAgZm9yIG4gaW4gaXRlciB7CiAgICAgICAgICAgICAgICBsZXQgXzogdXNpemUgPSBuOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9Cg==) FWIW, there is kind of a trick/hack in rust wherein you can use _nested_ `impl Trait`, but only when within the initial `<….>` generics rather than `where` clauses. This can be used here to alleviate a bit the syntax: - EDIT: ⚠️ beware of this hack ⚠️ The nested `impl Trait` syntax seems to introduce an anonymous _but `for<>`-lifetime-agnostic_ parameter to describe it, thereby introducing fixed lifetime constraints which can lead to `higher rank lifetime error`s ```rs #[apply(Gat!)] pub fn extend< L : for<'c> LendingIterator< // this would be our `(usize, I<'c>)` Item<'c> = impl Tuple2< // ( _0 = usize, // usize, _1 = impl Iterator, // I<'c>, >, // ) >, >( &mut self, iter_nodes: &mut L, ) { while let Some((idx, iter)) = iter_nodes.next().map(|it| it.is_tuple()) { for n in iter { let _: usize = n; } } } ``` - [Playground](https://www.rustexplorer.com/b#LyoKW2RlcGVuZGVuY2llc10KbGVuZGluZy1pdGVyYXRvci52ZXJzaW9uID0gIjAuMS43IgojIG5vdWdhdC52ZXJzaW9uID0gIjAuMi40IgoqLwpmbiBtYWluKCkge30KCnVzZSA6OmxlbmRpbmdfaXRlcmF0b3I6OnByZWx1ZGU6Oio7CgpzdHJ1Y3QgRm9vOwoKdHJhaXQgSXMgewogICAgdHlwZSBFcVRvOwoKICAgIGZuIGVxX3RvKHRoaXM6IFNlbGYpIC0+IFNlbGY6OkVxVG87Cn0KCmltcGw8VD4gSXMgZm9yIFQgewogICAgdHlwZSBFcVRvID0gU2VsZjsKCiAgICBmbiBlcV90byh0aGlzOiBTZWxmKSAtPiBTZWxmOjpFcVRvIHsKICAgICAgICB0aGlzCiAgICB9Cn0KCnRyYWl0IFR1cGxlMiB7CiAgICB0eXBlIF8wOwogICAgdHlwZSBfMTsKCiAgICBmbiBpc190dXBsZShzZWxmKSAtPiAoU2VsZjo6XzAsIFNlbGY6Ol8xKTsKfQoKaW1wbDxULCBVPiBUdXBsZTIgZm9yIChULCBVKSB7CiAgICB0eXBlIF8wID0gVDsKICAgIHR5cGUgXzEgPSBVOwoKICAgIGZuIGlzX3R1cGxlKHNlbGYpIC0+IChTZWxmOjpfMCwgU2VsZjo6XzEpIHsKICAgICAgICBzZWxmCiAgICB9Cn0KCmltcGwgRm9vIHsKICAgICNbYXBwbHkoR2F0ISldCiAgICBwdWIgZm4gZXh0ZW5kPAogICAgICAgIEwgOiBmb3I8J2M+IExlbmRpbmdJdGVyYXRvcjwKICAgICAgICAgICAgLy8gdGhpcyB3b3VsZCBiZSBvdXIgYCh1c2l6ZSwgSTwnYz4pYAogICAgICAgICAgICBJdGVtPCdjPiA9IGltcGwgVHVwbGUyPCAgICAgICAgICAgICAgIC8vICgKICAgICAgICAgICAgICAgIF8wID0gdXNpemUsICAgICAgICAgICAgICAgICAgICAgICAvLyAgICAgdXNpemUsCiAgICAgICAgICAgICAgICBfMSA9IGltcGwgSXRlcmF0b3I8SXRlbSA9IHVzaXplPiwgLy8gICAgIEk8J2M+LAogICAgICAgICAgICA+LCAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vICkKICAgICAgICA+LAogICAgPigKICAgICAgICAmbXV0IHNlbGYsCiAgICAgICAgaXRlcl9ub2RlczogJm11dCBMLAogICAgKQogICAgewogICAgICAgIHdoaWxlIGxldCBTb21lKChpZHgsIGl0ZXIpKSA9IGl0ZXJfbm9kZXMubmV4dCgpLm1hcCh8aXR8IGl0LmlzX3R1cGxlKCkpIHsKICAgICAgICAgICAgZm9yIG4gaW4gaXRlciB7CiAgICAgICAgICAgICAgICBsZXQgXzogdXNpemUgPSBuOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9Cg==)

[vigna]

Yeah, this is a bit subtle to explain; do you happen to be on Discord or some other instant messaging platform? It may be easier to work with there than over here 🙂

I think I'm bothering you more than enough here!

So, thank you a lot for the explanation: turns out I was desperately trying to do what you suggest, but I was looking for Rust syntax that would make it possible to extract the type of a component of a tuple, and I couldn't find any. I didn't think about the trait—that's a bit too far for me.

I've implemented the idea and it seems to work even with actual GATs (using gat_lending_iterator), except that when I try to call a function with the multi-line parameter declaration above using a LendingIterator<Item<'a> = (usize, Self::Successors<'a>)> I get

the trait bound `for<'c> <_ as gat_lending_iterator::LendingIterator>::Item<'c>: traits::graph::Tuple2` is not satisfied
the trait `traits::graph::Tuple2` is implemented for `(T, U)`

which puzzles me because the item is a 2-tuple. That might be a limitation of the compiler that does not apply to your HKT implementation, but it seems to be something else. I tried to reproduce the situation using your library but I got stuck trying to set the Item type to a pair (possibly I misunderstood the Item<'_,L> syntax).

Basically, I need to return a LendingIterator<Item<'a> = (usize, Self::Successors<'a>)> from a function and pass it to another. With the complex signature you propose the function finally compiles, but then it doesn't accept what I would expect as a possible argument with the error above.

If you can share some more wisdom I would be immensely grateful!

[vigna]

And, I was able to make this into a playground.

[danielhenrymantilla]

The following playground compiles

[vigna]

I see—you really need a different definition of lending iterator to make this work.

I realize it is similar to the type structure of your library, so probably the LendingIterator definition we were using was wrong from the start. Thank you again, I think we'll be able to work out this idea.

[vigna]

So, in the end this was the idea we were looking for. With a bit of 'static we have been able to make everything work as we were expecting. I credited your contribution in the docs.