Trait with lifetime with method returning the same struct with different lifetime

help
1

I want to define a trait which allows interning combined with bumpalo allocator.

struct Bump;

trait View<'a> {
    fn intern_key(&self) -> &'a str;

    // ERROR!
    fn intern<'arena>(&self, arena: &'arena Bump) -> (&'arena str, Self<'arena>);
}

struct Interner<'arena, T> {
  items: HashMap<&'arena str, T>,
  arena: &'arena Bump,
}

impl<'arena, T: View<'arena> + Copy> {
  fn add<'a>(&mut self, obj: View<'a>) {
    let (key, interned) = obj.intern();
    self.items.insert(key, interned);
  }

  fn get(&self, key: &str) -> Option<T> {
    self.items.get(key).copied()
  }
}

FYI i'm using Bump as I don't want to give Interner lifetime bounded T in get method.

The problem is, this code won't compile as trait cannot say Self<'a>, it must be Self.

2

rust does not have proper higher kinded types, you'll need to "emulate" some of the behavior, e.g. with GAT, but it's not real HKT, so it depends on the use cases.

for this example, I think you can try something like this:

trait View<'a> {
    type Interned<'b>;
    fn intern_key(&self) -> &'a str;
    fn intern<'arena>(&self, arena: &'arena Bump) -> (&'arena str, Self::Interned<'arena>);
}

because it's not real HKT, you cannot ensure Self::Interned and Self is the same type (constructor), so you'll have to rely on the implementor being cooperative.

it can be used like this:

struct Interner<'arena, T: View<'arena>> {
    items: HashMap<&'arena str, <T as View<'arena>>::Interned<'arena>>,
    arena: &'arena Bump,
}

impl<'arena, T> Interner<'arena, T>
where
    T: View<'arena>,
    <T as View<'arena>>::Interned<'arena>: Copy,
{
    fn add<'a>(&mut self, obj: T) {
        let (key, interned) = obj.intern(&self.arena);
        self.items.insert(key, interned);
    }

    fn get(&self, key: &str) -> Option<T::Interned<'arena>> {
        self.items.get(key).copied()
    }
}

some of the <T as View<'arena>>::Interned<'arena> can be shortened as T::Interned<'arena>, but you can also make an alias for convenienct, e.g.:

type ArenaInterned<'a, T> = <T as View<'a>>::Interned<'a>;

if such workaround is insufficient for you use case, check out the higher-kinded-types crate, which provides a more sophisticated solution, you just use ForLt as super trait of View, and replace <T as View<'a>>::Interned<'b>> with <T as ForLt>::Of<'b>, or T::Of<'b> for short. something like:

use higher_kinded_types::ForLt;

trait View<'a>: ForLt {
    fn intern_key(&self) -> &'a str;
    fn intern<'arena>(&self, arena: &'arena Bump) -> (&'arena str, Self::Of<'arena>);
}

but still, it's not real hkt, so you may encounter some limitations. see the documentation of higher-kinded-types for more information.

1 Like
3

Maybe?

trait Helper {}

impl<'a, T: for<'b> View<'b>> Helper for (&'a str, T) {}

trait View<'a> {
    fn intern_key(&self) -> &'a str;

    fn intern<'arena>(&self, arena: &'arena Bump) -> impl Helper; // + implicit '+ use<'arena>'
}
4

Thank you for the idea! I made a minor twist to help unnecessary lifetime bound code,
so to

trait Keyed<'a> {
    fn intern_key(&self) -> &'a str;
}

trait Interned<'a> {
    type View<'b>: Keyed<'b>;

    fn intern_from<'b>(arena: &'a Bump, value: Self::View<'b>) -> (&'a str, Self);
}

This way insert() returns 'arena bounded type.