Associated Type with a 'static Bound in a Trait with Lifetime Parameters

help
1

I've defined the following traits:

trait Param {
    type State: 'static; // The 'static bound on State is not relevant to this question.
    type Worlds<'w>: FromIds<'w>;

    fn init<'w>(worlds: Self::Worlds<'w>) -> Self::State;
}

and

trait FromIds<'w>: 'w {
    type Ids: 'static;
    fn from_ids(worlds: &'w Worlds, ids: &Self::Ids) -> Self;
}

My intention is to fetch Worlds from Worlds based on Ids, where Ids represents a nested tuple of WorldId.
Param::Worlds is structured as a nested tuple with the same hierarchy as that of the WorldId nested tuple.

I want to store Ids in a struct:

struct System<P: Param> {
    state: Option<P::State>,
	// I believe that ideally the 'static lifetime wouldn't need to be explicitly specified here,
	// but without it, the compiler complains.
    ids: <P::Worlds<'static> as FromIds<'static>>::Ids,
}

Then, I attempted to implement an initialization function for System:

impl<P: Param> System<P> {
    fn init<'w>(&mut self, worlds: &'w Worlds) {
        let worlds = <P::Worlds<'w> as FromIds<'w>>::from_ids(worlds, &self.ids); // ERROR: mismatched types - expected P::Worlds<'w>::Ids but found P::Worlds<'static>::Ids
        self.state = Some(P::init(worlds));
    }
}

Given that Ids is bounded by 'static, I expected this code to work. However, I encounter a type error due to the mismatch between P::Worlds<'w> and P::Worlds<'static>.

I also tried approaches such as implementing a shrink function within FromIds or removing the lifetime parameter from it, but none of these attempts succeeded.

How can I resolve the type mismatch in this scenario? Any help or suggestions would be greatly appreciated.

2

I've simplified my example (the previous examples were more complicated than necessary):

trait A<'a> {
  type B: 'static;
}

trait C {
  type D<'a>: A<'a>;
}

I want to store C::D::B in a struct without having to worry about lifetimes:

struct E<T: C> {
  b: <T::D as A>::B, // Actually, I need to specify the lifetime for A and D.
}

I believe this should be possible somehow because B is bounded by 'static.

Thank you!

3

As I see it, the problem is that in principle, B is allowed to be a different type depending on the lifetime 'a, while still meeting a 'static bound. There’s no way to make that happen in current Rust, and there probably never will be, but there’s also no rule that says it will never happen, which is what the compiler would need to accept your code.

Going back to your original example, it seems like things might work better if you flipped around FromId to instead be a trait implemented on the ID type:

trait GetWorld {
    type World<'w>;
    fn get_world_from<'w>(&self, worlds: &'w Worlds) -> Self::World<'w>;
}
impl GetWorld for WorldId { ... }

As a general rule, problems are simpler when lifetime parameters have a narrower scope (function instead of trait).

1 Like
4

Encode your expectation that all FromIds<'a>::Ids correspond to a single type in a way the trait system understands:

trait Param {
    type State: 'static;
    //                           vvvvvvvvvvvvvvvvvvvvv
    type Worlds<'w>: FromIds<'w, Ids = Self::WorldsIds>;
    type WorldsIds: 'static;
    fn init<'w>(worlds: Self::Worlds<'w>) -> Self::State;
}

struct System<P: Param> {
    state: Option<P::State>,
    //   vvvvvvvvvvvv
    ids: P::WorldsIds,
}

This is a slight burden on implementors, but there's also a way to avoid that I believe. In both your examples, there are no bounds on your GATs, meaning they must be defined for all lifetimes. If that's your actual use case, you should be able to use HRTBs[1] without running into limiting interactions. Which means you could put the extra associated type into a subtrait with a blanket implementation:

trait ParamId
where
    Self: for<'a> Param<Worlds<'a>: FromIds<'a, Ids = Self::WorldsIds>>
{
    type WorldsIds;
}

impl<T, Id> ParamId for T
where
    T: ?Sized + for<'a> Param<Worlds<'a>: FromIds<'a, Ids = Id>>
{
    type WorldsIds = Id;
}

Then use this subtrait instead.

struct System<P: ParamId> {
    state: Option<P::State>,
    ids: P::WorldsIds,
}

impl<P: ParamId> System<P> {
    fn init<'w>(&mut self, worlds: &'w Worlds) {
        // ...

  1. where for<'a> ... ↩︎

2 Likes
5

Fascinating!

In the following snippet, does it mean that the Id parameter is "inferred" from the associated type of FromIds implementation?

impl<T, Id> ParamId for T
where
    T: ?Sized + for<'a> Param<Worlds<'a>: FromIds<'a, Ids = Id>>
{
    type WorldsIds = Id;
}

In your last Playground snippet, the Words type was fixed in some places, but it was also an associated type. This bothered me, so I tried to make it fully generic, but not sure if it means the same thing:

@@ -22,7 +20,7 @@

 trait FromIds<'w>: 'w {
     type Ids: 'static;
-    fn from_ids(worlds: &'w Worlds, ids: &Self::Ids) -> Self;
+    fn from_ids(worlds: &'w Self, ids: &Self::Ids) -> Self;
 }

 struct System<P: ParamId> {
@@ -31,7 +29,7 @@
 }

 impl<P: ParamId> System<P> {
-    fn init<'w>(&mut self, worlds: &'w Worlds) {
+    fn init<'w>(&mut self, worlds: &'w <P as Param>::Worlds<'w>) {
         let worlds = <P::Worlds<'w> as FromIds<'w>>::from_ids(worlds, &self.ids);
         self.state = Some(P::init(worlds));
     }

This topic (how the type system works) is very interesting to me, but it doesn't appear to be well covered.
Would you be able to recommend any reading material on the subject?

6

I added the Worlds unit type because when I pasted your OP snippets into a playground, it told me that type didn't exist. You'd know better than I what the intent is :slight_smile:.

Well, it means the implementation only applies if there's a single type that can unify with all the FromIds::<'a>::Id. We know that this will always be the case when T: Param,[1] but as the type system apparently does not assume or infer this currently, it presumably will check that this is possible whenever it needs to prove T: ParamId.

The dev guide is one place I've learned from. It's more of an "under the hood" perspective though. As far as practical maneuvers like the ones in my playgrounds go, I have mostly learned those from other people's code and articles, or through my own experimentation/problem solving (as opposed to a centralized source I can cite).

  1. in current Rust anyway, as discussed above ↩︎

1 Like
7

Thank you very much for your help! Since there was no issue with changing Worlds to Ids, I implemented your solution and have marked it accordingly.

8

Not only did these suggestions solve my problem, but they also deepened my understanding of HRTBs. Thank you very much for your help.
I will carefully read the website you linked to right away.

@undefined.behavior
Yes, having Worlds share the same name as the associated type Worlds in Param is indeed confusing.

In my code, Worlds (which is not an associated type) is defined as a Vec of World instances, while Ids is a nested tuple such as (0, 1, (2, 1)). The from_ids function fetches World values from the Vec in Worlds by index and returns a nested tuple of Worldinstances—for example, (Worlds[0], Worlds[1], (Worlds[2], Worlds[1])). This nested tuple corresponds to the associated type Worlds in Param.

I thought that explaining all the details might be too complicated, but it appears my previous explanation may have led to some confusion…