Dynamic trait objects with GAT lifetimes using work-around on stable Rust 1.65

Generic Associated Types (GATs) are coming to stable Rust in version 1.65, but will not support GAT traits with object safety yet at the initial release. However, there has existed a work-around for using generic associated lifetimes (with object safety) on stable Rust for a while.

So I wanted to try and see if the new GAT feature and the generic associated lifetime emulation can be combined on Rust 1.65 (although I tested this on nightly 1.66), but I'm running into some vague error messages that I'm hoping someone knows more about. I also considered posting this as a bug report on Github an on IRLO, but here seemed like the best place (please let me know if it's better to post this somewhere else).

At a very high level, there are 3 traits (Foo, Bar, Baz) which form a chain of nested GATs. The "Baz" trait has a GAT named "Bar" which must implement the "Bar" trait and the "Bar" trait has a GAT named "Foo" which must implement the "Foo" trait. The work-around I came up with seems to work okay, except for the work-around needed in order to make the "Baz" trait object safe. There are some errors that I can't seem to iron out when casting the struct Baz to its dynamic helper trait generic::Baz (from the generic module) into a trait object. The errors happen in 2 specific places, I named them "error site A" and "error site B" in this example code at methods fn main and fn bar, respectively:

use std::marker::PhantomData;

#[derive(Default)]
pub struct Foo<'a>(PhantomData<&'a ()>);
#[derive(Default)]
pub struct Bar<'a>(PhantomData<&'a ()>);
#[derive(Default)]
pub struct Baz;

fn main() {
    let _foo: Box<dyn generic::Foo + Send> = Box::new(Foo::default());
    let _bar: Box<dyn generic::Bar + Send + Sync> = Box::new(Bar::default());
    // Let's call the next line "error site A"
    let _baz: Box<dyn generic::Baz + Send + Sync> = Box::new(Baz::default());
}

mod gat {
    pub trait Foo<'foo> {}
    impl<'foo> Foo<'foo> for super::Foo<'foo> {}

    pub trait Bar<'bar> {
        type Foo<'foo>: Foo<'foo>
        where
            Self: 'foo;
    }
    impl<'bar> Bar<'bar> for super::Bar<'bar> {
        type Foo<'foo> = super::Foo<'foo>
        where
            Self: 'foo;
    }

    pub trait Baz {
        type Bar<'bar>: Bar<'bar>
        where
            Self: 'bar;
        fn bar(&self) -> Self::Bar<'_>;
    }
    impl Baz for super::Baz {
        type Bar<'bar> = super::Bar<'bar>
        where
            Self: 'bar;

        fn bar(&self) -> Self::Bar<'_> {
            super::Bar::default()
        }
    }
}

mod generic {
    // A trait alias for `Foo` which is object safe
    // and can be sent between threads.
    pub trait Foo<'foo>: super::gat::Foo<'foo> + Send {}
    impl<'foo, T> Foo<'foo> for T where T: ?Sized + super::gat::Foo<'foo> + Send {}

    // A trait alias for `Bar` which is object safe
    // and can be sent and shared between threads.
    pub trait Bar<'bar>: Send + Sync {}
    impl<'bar, T> Bar<'bar> for T
    where
        T: super::gat::Bar<'bar> + Send + Sync,
        for<'foo> <T as super::gat::Bar<'bar>>::Foo<'foo>: Send,
        for<'foo> <T as super::gat::Bar<'bar>>::Foo<'foo>: super::generic::Foo<'foo>,
    {
    }

    // A trait alias for `Baz` which is object safe
    // and can be sent and shared between threads.
    pub trait Baz: Send + Sync {
        fn bar<'bar>(&'bar self) -> Box<dyn Send + Sync + Bar<'bar> + 'bar>;
    }
    impl<T> Baz for T
    where
        T: super::gat::Baz + Send + Sync,
        for<'bar> <T as super::gat::Baz>::Bar<'bar>: Send + Sync,
        // From here out it becomes tricky to pick the right impl trait bounds!
        // There are a couple of scenarios that all give slightly different errors.
        // See below for which scenario gives which errors.
        // * Scenario 1): all the following bounds are commented
        // * Scenario 2): only this next line uncommented
        // for<'bar> <T as super::gat::Baz>::Bar<'bar>: super::generic::Bar<'bar>,
        // * Scenario 3): only this next line uncommented
        // for<'foo, 'bar> <<T as super::gat::Baz>::Bar<'bar> as super::gat::Bar<'bar>>::Foo<'foo>: Send,
        // * Scenario 4): only this next line uncommented
        // for<'bar, 'foo> <<T as super::gat::Baz>::Bar<'bar> as super::gat::Bar<'bar>>::Foo<'foo>: Send,
        // * Scenario 5): only this next line uncommented
        // for<'bar> <<T as super::gat::Baz>::Bar<'bar> as super::gat::Bar<'bar>>::Foo<'bar>: Send,
    {
        fn bar<'bar>(&'bar self) -> Box<dyn Send + Sync + Bar<'bar> + 'bar> {
            let bar = <Self as super::gat::Baz>::bar(self);
            // ... and this line is "error site B":
            let bar: Box<dyn Send + Sync + Bar<'bar> + 'bar> = Box::new(bar);
            bar
        }
    }
}

In the code there are a few "scenarios", which you can enable by uncommenting the corresponding line. I collected all the error messages for each scenario here:

Scenario 1)
When all impl trait bounds remain commented, then there is no error at
"error site A" in fn main and the following error shows at error site B
in fn bar. This is as expected, because we did not restrict Foo: Send.

error[E0277]: `<<T as gat::Baz>::Bar<'bar> as gat::Bar<'bar>>::Foo<'foo>` cannot be sent between threads safely
  --> examples/repr3.rs:91:64
   |
91 |             let bar: Box<dyn Send + Sync + Bar<'bar> + 'bar> = Box::new(bar);
   |                                                                ^^^^^^^^^^^^^ `<<T as gat::Baz>::Bar<'bar> as gat::Bar<'bar>>::Foo<'foo>` cannot be sent between threads safely
   |
   = help: the trait `for<'foo> Send` is not implemented for `<<T as gat::Baz>::Bar<'bar> as gat::Bar<'bar>>::Foo<'foo>`
note: required for `<T as gat::Baz>::Bar<'_>` to implement `generic::Bar<'bar>`
  --> examples/repr3.rs:58:19
   |
58 |     impl<'bar, T> Bar<'bar> for T
   |                   ^^^^^^^^^     ^
   = note: required for the cast from `<T as gat::Baz>::Bar<'_>` to the object type `dyn generic::Bar<'bar> + Send + Sync`

Scenario 2)
This time there is only an error at site A in fn main and no error at site B.
Looking at other issues that mention "higher-ranked lifetime error", this seems
to be some kind of compiler limitation? Is there a work-around for this?

error: higher-ranked lifetime error
  --> examples/repr3.rs:14:53
   |
14 |     let _baz: Box<dyn generic::Baz + Send + Sync> = Box::new(Baz::default());
   |                                                     ^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: could not prove `for<'a> Box<Baz>: CoerceUnsized<Box<(dyn generic::Baz + Send + Sync + 'a)>>`

Scenario 3)
This one causes errors at both site A in fn main and in site B in fn bar.
The first one at site A:

error: implementation of `gat::Bar` is not general enough
  --> examples/repr3.rs:14:53
   |
14 |     let _baz: Box<dyn generic::Baz + Send + Sync> = Box::new(Baz::default());
   |                                                     ^^^^^^^^^^^^^^^^^^^^^^^^ implementation of `gat::Bar` is not general enough
   |
   = note: `gat::Bar<'0>` would have to be implemented for the type `Bar<'0>`, for any lifetime `'0`...
   = note: ...but `gat::Bar<'1>` is actually implemented for the type `Bar<'1>`, for some specific lifetime `'1`

The other error at site B complains about 'static lifetime. However,
I'm not sure where this 'static lifetime comes from, as the 'bar
lifetime is hard-coded everywhere (possibly due to for<'foo, 'bar>?):

error: lifetime may not live long enough
  --> examples/repr3.rs:92:64
   |
88 |         fn bar<'bar>(&'bar self) -> Box<dyn Send + Sync + Bar<'bar> + 'bar> {
   |                ---- lifetime `'bar` defined here
...
91 |             let bar: Box<dyn Send + Sync + Bar<'bar> + 'bar> = Box::new(bar);
   |                                                                ^^^^^^^^^^^^^ cast requires that `'bar` must outlive `'static`                                                      ^^^^^^^^^^^^^ cast requires that `'1` must outlive `'static`

Scenario 4)
This scenario shows exactly the same errors as in scenario 3
(only the quantified lifetimes in the trait bound are now swapped,
just in case it would have mattered, but it doesn't).

Scenario 5)
Here we get the exact same errors as in scenario 1, because the
trait bounds only say something about 'bar', but not about
the lifetime 'foo.

Help
To end with some questions which I have about the above:

  • Now that GATs are being stabilized, is such a work-around intended to be working from its first release?
  • If not, does there exists a work-around for these errors or is there another way to achieve the same result?
  • What is the cause of the error in scenario 2? Intuitively, I would expect that this would be the most straight-forward way to enforce the Foo: Send bound on generic::Bar<'bar>:::Foo<'foo>, but the "higher-ranked lifetime error" suggests otherwise and I don't know how to work-around this one.

p.s. I am currently on rustc 1.66.0-nightly (0ca356586 2022-10-06)

GAT is known to have a lot of issues around normalization, higher-ranked bounds, inference, et cetera, but they decided to stabilize now anyway. I expect a lot of these kinds of difficulties to persist for quite some time (years).

I'm still getting my GAT legs, but I'll poke at it. Here's a playground link for convenience.

It compiles without the unnecessary (to the example) where Self: 'a bounds. I take it those are actually required in practice?

1 Like

Wow thanks! When I apply your trick to my actual use case (not shown in the "minimized" example I posted), it complains about the missing where Self: 'a bounds:

error: missing required bound on `Bar`
   | help: add the required where clause: `where Self: 'bar`
   = note: this bound is currently required to ensure that impls have maximum flexibility
   = note: we are soliciting feedback, see issue #87479 <https://github.com/rust-lang/rust/issues/87479> for more information

But I'm happy to omit the where bounds if that is somehow possible, I just put those there because the compiler told me, my use case does not rely on it. What makes it that in some cases it's allowed to omit the where clause on a GAT, when other times it's mandatory to include it?

If it's telling you need them, you usually do want them. There are ways to disable that lint, but generally this just pushes errors down the road. (Cleaning up that lint is another thing they punted on, which we may all come to regret later.)

As for what they are about, if you have something like

    type Gat<'a>;
    fn foo<'a>(&'a self) -> Self::Gat<'a>;

You're probably intending for Gat<'_> to be some sort of borrow from within &self. And if Self is also lifetime-bound, say Self = Bar<'x>, you might have an attempted implementation like

impl<'x> Trait for Bar<'x> {
    type Gat<'a> = &'a Quz<'x>;
    fn foo<'a>(&'a self) -> Self::Gat<'a> {
        &self.quz
    }
}

And the problem is that without the Self: 'a bound, we have to define the Gat for all possible lifetimes -- but when 'a is longer than 'x, &'a Quz<'x> is invalid. So it's impossible to write this implementation.

Example.

(The compiler can't just throw out the invalid cases for a given implementation as that would be less general than the trait, and elsewhere you could still try to use <Bar<'short> as Trait>::Gat<'static> for example, which the trait says you have to define.)


The exact rules of that lint are, uh... as far as I know, also still not actually written down. Another thing they have punted on (and the project tends to be dismal at documenting the language :angry:). Here's my best guess as of May.

1 Like

Ah, maybe this is what is causing the error in scenario #2 then, because of this impl trait bound:

for<'bar> <T as super::gat::Baz>::Bar<'bar>: super::generic::Bar<'bar>,

because <T as super::gat::Baz>::Bar<'bar> itself is explicitly outlived by Self, this is not general enough to be matched against the trait bound :frowning:

That's true! AFAIK there is no way to quantify over lifetimes that might be restricted by Self, right? Issue #82921 seems related because of the similar error message.

Might you know of any tricks that work-around the where Self: '_ limitation, while keeping where Self: '_ in place for future compatibility, but then "escape" it somehow afterwards in order to satisfy the lifetime quantifier in the impl bounds of generic::Foo? The trait in the gat module with the where Self: '_ GAT bounds is the one that will be exposed to consumers of the API, so ideally I can just let them code stuff that is forward compatible and hide the whole generic module from the end-users :slight_smile:

Here is an updated playground which also includes the methods to reproduce the compiler error I was seeing on my end: Rust Playground

There is a way! But, it is also pretty convoluted.

When Rust sees something like &'a Foo<'b> in certain positions, such as a parameter type to a function, it automatically assumes some implied bounds such as 'b: 'a. The idea is that one can never construct a non-well-formed &'a Foo<'b> where this bound isn't true, so the function can just assume that it's true -- can assume that its inputs are well-formed. (If an input is not well-formed, we're already into Undefined Behavior anyway.)

So the way you can emulate some sort of for<'a where 'b: 'a> bound is to have some sort of "witness" in the context of the bound that implies 'b: 'a, like a [&'a &'b (); 0] or something. Here's a walkthrough of the idea.


Using such a witness gets rid of one error in your latest playground, but we're still stuck with the vague higher-ranked error.

I think what is actually needed is someway to introduce such a witness into your trait implementation bounds, and not just a particular method. Unfortunately I'm not sure how to do that off the top of my head (but I'm still poking).

(For example, even though the error went away on that method implementation, the trait bounds on the implementation itself don't impose any cap on for<'foo>. Probably the implementation just won't be applicable where it counts.)

Putting lifetimes bounds on the generic::{Foo, Bar} traits itself gets rid of the method error as well (though I'm not sure the bounds are actually desired). Here I've also added a boxed method that shifts what the vague higher-ranked lifetime error complains about.

3 Likes

Is there any technical difficulty on implementing this? I think I have encountered this problem quite a few times already.

There exists an open RFC for this syntax, which hasn't moved much since it was first created. A comment there suggests that the current direction is to modify the implied-bounds rules so that for<where> bounds should be necessary very rarely, if at all.

On this topic, I'll just repeat myself from elsewhere:

The comment is a bit disheartening; I'm of the view that as much things as possible which are implicit should have an explicit form (preferably with a 1-to-1 desugaring).

Only being able to rely on inference, i.e. having no way to override it, never works all the time and eventually leads to additions that should have existed in the first place for the severely common cases.

(Needing a hack to disable the lint / eventual implied GAT bounds?? is another example. Just let me cleanly override the default inference when you get it wrong, which you sometimes will, dang it.)

I'm 99% sure I've seen Niko comment that Chalk could handle for<'a where ...>, but I don't have a citation on hand. How many years until we get Chalk, I have no idea.

3 Likes

This is close, but still has a for< ... where ...> problem. Here:

    impl<'bar, T> BazBar<'bar> for T

You need this:

    where
        T: 'bar + super::gat::Baz + Send + Sync,
        // ^^^^

So that the GAT can be used here:

        <T as super::gat::Baz>::Bar<'bar>: Bar<'bar>,

But then above we have:

    impl<T> Baz for T
    where
        T: Send + Sync + for<'bar> BazBar<'bar>

Which is where we would like for<where>, but we don't have that. So instead we need some sort of implied bounds in BazBar that says Self: 'bar. The way I'm used to doing this would be something like:

    pub trait BazBar<'bar, _Witness = &'bar Self> {

But that makes the trait non-dyn-safe.

I'm going to pause now; probably the next thing I'll do is re-read Sabrina's article and see if it handles this case.

1 Like

@quinedot Thank you so much for listing all this info and for all the examples! I spent the entire day playing around with it, but alas I could not find a work-around for escaping the where Self: 'foo clause on the Bar::Foo<'foo> GAT. As soon as this extra where clause is there, this seems to render any technique depending on implicit lifetime bounds inert :frowning: (Rust then complains with the same errors as either scenario 2 or 3: we get a "higher-ranked lifetime error" or a complaint about the Bar helper trait not being general enough).

The only way I know of getitng rid of this is using the super trait work-around, because then we can omit the where Self: 'foo GAT bounds in the Bar trait. However, I'm still hoping there exists a way without the super trait, so make the API for end-users more ergonomic by steering them towards the stabilized GATs (the generic module will then take care of object safety for them, so the end-users should not be bothered too much by the current GAT limitations). I'm going to keep poking some more, but this might be a GAT limitation that can't be worked around for the time being. Thanks again for all the good tips, I enjoyed learning more about this topic a great deal :slight_smile:

@quinedot I was able to find a way! See this solution on Rust Playground

I had to forego HRTB altogether, but managed with some very specific bounds on the Bar trait and Bar::Foo<'_> GAT:

pub trait Bar<'bar>: 'bar {
        /// Safety: we need both the GAT bound `'bar: 'foo` and the
        /// trait bound `Self: 'bar` for soundness, because without
        /// the "Self outlives 'bar and 'bar outlives 'foo" criteria,
        /// implementers of this trait would be able to put an invariant
        /// or contravariant type into [Bar::Foo<'_>]. With these
        /// extra bounds, the compiler will now rightfully complain
        /// about concrete types returned by implementations for
        /// [Bar::foo] which are not covariant; and this is what
        /// we base our safety invariant on in the [wrapper] module!
        /// Alternatively, we can also put the trait bound `Self: 'bar`
        /// on the GAT instead, but this way it is less code to type
        /// when implementing the [Bar] trait, so it's more ergonomic.
        type Foo<'foo>: Foo<'foo>
        where
            'bar: 'foo;

        fn foo(&self) -> Self::Foo<'_>;
    }

The covariance is not enforced in that trait itself, but it is enforced by the compiler for implementations of the trait (specifically when implementing the fn foo() method). Then for the object safe generic::{Bar, Baz} traits I use the following trait implementation bounds:

impl<'bar, T> Bar<'bar> for T
where
   T: Send + Sync + super::Bar<'bar> + 'bar,
   <T as super::Bar<'bar>>::Foo<'bar>: Send,
{ ... }

impl<'baz, T> Baz for T
where
    T: Send + Sync + super::Baz + 'baz,
    <T as super::Baz>::Bar<'baz>: Send + Sync,
    <<T as super::Baz>::Bar<'baz> as super::Bar<'baz>>::Foo<'baz>: Send,
{ ... }

and then sprinkle a little unsafe code into an (unsafe and private) wrapper struct that unconditionally implements the required Send/Sync trait bounds for all lifetimes (see the gat::wrapper module from the playground link). This is sound due to exploiting the forced covariance of the trait implementations for Bar. All the way at the bottom is also an example that makes the compiler complain about missing Send/Sync bounds when coercing concrete types into dynamic trait objects which don't implement the correct Send/Sync bounds :slight_smile: See the documentation of gat::{DynFoo, DynBar, DynBaz} for extra details.

p.s. It's a good thing that the wrapper and generic modules are private modules, the code needed for the work-around is not something I would feel comfortable exposing to my end-users :sweat_smile: In the end I think I found solution which requires no boiler-plate code or macros for the end-user, while keeping all the benefits of GATs on stable Rust. I'm looking very much forward to when chalk is ready and Rust adds object safety for GAT traits :smiley:

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.