GATs and HRTB confusion

[MSR]

I was playing around with GATs and was surprised by the following.

Say I use GATs to define an iterable:

pub trait Iterable {
    type Iter<'a>: Iterator<Item = Self::Item<'a>>
    where
        Self: 'a;
    type Item<'a>
    where
        Self: 'a;

    fn iter(&self) -> Self::Iter<'_>;
}

Now with associated types, I can use a HRTB to constrain the Iterable::Item like the following, which seems to work fine:

trait Foo {
    type FooType: for<'a> Iterable<Item<'a> = Self::FooItem<'a>>;
    type FooItem<'a>;
}

However, it seems I'm unable to do the same in a where clause. For example,

trait Bar {
    type BarType;
    type BarItem<'a>;
}

trait SuperBar: Bar
where
    Self::BarType: for<'a> Iterable<Item<'a> = Self::BarItem<'a>>,
{
}

fails to compile with the below error message.

Error message

error[E0311]: the associated type `<Self as Bar>::BarType` may not live long enough
  --> src/lib.rs:24:1
   |
24 | / trait SuperBar: Bar
25 | | where
26 | |     Self::BarType: for<'a> Iterable<Item<'a> = Self::BarItem<'a>>,
27 | | {
28 | | }
   | |_^
   |
   = help: consider adding an explicit lifetime bound `<Self as Bar>::BarType: 'a`...
   = note: ...so that the type `<Self as Bar>::BarType` will meet its required lifetime bounds...
note: ...that is required by this bound
  --> src/lib.rs:26:37
   |
26 |     Self::BarType: for<'a> Iterable<Item<'a> = Self::BarItem<'a>>,
   |                                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^

(Playground.)

This leaves me with two questions:

1. Can I solve this situation? I could maybe give SuperBar its own associated type with the bound that I know how to write, but suppose I'd like to avoid that. The compiler suggestions don't quite make sense to me, and blindly following seem to lead to more problems.
2. Why are the associated type bound and the where clause bound different? In my apparently oversimplified mental model, the two bounds say exactly the same, but I guess that can't quite be right, seeing as only one compiles.

[H2CO3]

Is this related to HRTB bounds not resolving correctly (take 2) · Issue #89196 · rust-lang/rust · GitHub?

[MSR]

That seems possible, especially this linked issue looks similar, but I don't understand the discussion well enough to be sure.

[Yandros]

Yeah, it's a bit weird: it's interpreting the Self : 'a as a post-checked bound, after the introduction of the universal (forall) 'a parameter, which leads the trait solver having to prove that Self::BarType : 'a for that arbitrary / universal 'a,

where
    for<'a>
        Self::BarType : 'a // + Iterable<…>
    ,

which of course does not hold.

What the trait solver should have done is to, instead, interpret Self : 'a as an implicit / prior-to-universal-'a-introduction / universal-restricting bound:

where
    for<'a where Self::BarType : 'a>
        Self::BarType : // …
    ,

An example of the latter can be achieved by replacing the Iterable definition with the non-GAT polyfill:

#![feature(generic_associated_types)]

/// Trait alias: `Iterable = for<'a> Iterable_<'a>`
pub trait Iterable // where Self
    : for<'a> Iterable_<'a>
{}
impl<T : ?Sized> Iterable for T where Self
    : for<'a> Iterable_<'a>
{}

#[allow(nonstandard_style)]
pub trait Iterable_<'a, __HACK__where_Self_a = &'a Self> {
    type Iter: Iterator<Item = Self::Item>;
    type Item;

    fn iter(&'a self) -> Self::Iter;
}


trait Foo {
    type FooType: for<'a> Iterable_<'a, Item = Self::FooItem<'a>>;
    type FooItem<'a>;
}

trait Bar {
    type BarType;
    type BarItem<'a>;
}

trait SubBar: Bar
where
    Self::BarType: for<'a> Iterable_<'a, Item = Self::BarItem<'a>>,
{}

1. Iterable_<'a> is a "single-lifetime frame / instance" of your Iterable GAT trait, and we go back to your multi-lifetime GAT trait thanks to a Iterable = for<'a> Iterable_<'a> trait alias.

   • So that for<'a> gat::Iterable<Item<'a> = …>
     becomes for<'a> Iterable_<'a, Item = …>,

     and <T as gat::Iterable>::Item<'a>
     becomes <T as Iterable_<'a>>::Item

2. Finally, we need to reproduce the where Self : 'a bounds on the GATs. We do this with the __HACK___where_Self_a = &'a Self, which is a hacky way to feature a hidden mention of the &'a Self type, whose mention / existence, in turn, yields an implicit bound of Self : 'a.

The key thing here is that with this implementation, we have an implicit bound of Self : 'a which is able to "retroact" on the for<'a> universally quantified lifetime introduction, resulting in the desired semantics.

• As to why GATs don't behave like this, I don't know; it does look like a bug (albeit one that looks different than the one feature in the posted issue, I'd say).

As you can see, with this implementation the code does compile fine.

---

In practice, you can throw a : 'static bound onto the Self::BarType and you should be fine; I'm not even sure it's gonna be more restrictive than without it when implementing the traits, since so many lifetimes are involved that the trait solver has trouble keeping up

[MSR]

Thank you very much for the comprehensive answer.

I had figured I needed something like for<'a where Self::BarType : 'a>, but I couldn't figure out how to encode it. The Iterable_<'a, __HACK__where_Self_a = &'a Self> idea is very nice, I hadn't seen that before!

It's still a bit puzzling to me that the associated type bound solves this differently from the where clause bound, but at least I understand you as saying that my idea that the two should be the same is generally valid. Perhaps I'll open a rust issue on this to see if it's a duplicate of the other issue.

---

EDIT: I opened an issue, if people are interested in following along.