Implementing trait with GATs for type with lifetime arg

Hello, I'm facing a problem with GATs when implementing a trait for a type that has lifetime arguments. Here is a minimal example where implementing Trait for Easy works well, but implementing Trait for Hard doesn't work:

#![feature(generic_associated_types)]

use std::borrow::Cow;
use std::ops::Deref;

trait Trait {
    type Gat<'a>: Deref<Target = Self>;
    fn func(src: &str) -> Self::Gat<'_>;
}

#[derive(Clone)]
struct Easy(String);

impl Trait for Easy {
    type Gat<'a> = Cow<'a, Self>;
    fn func(src: &str) -> Self::Gat<'_> {
        Cow::Owned(Easy(src.to_owned()))
    }
}

#[derive(Clone)]
struct Hard<'b>(&'b str);

impl<'b> Trait for Hard<'b> {
    type Gat<'a> = Cow<'a, Self>;
    fn func(src: &str) -> Self::Gat<'_> {
        Cow::Owned(Hard(src))
    }
}

(Playground)

Errors:

error[E0477]: the type `Hard<'b>` does not fulfill the required lifetime
  --> src/lib.rs:25:20
   |
25 |     type Gat<'a> = Cow<'a, Self>;
   |                    ^^^^^^^^^^^^^
   |
note: type must outlive the lifetime `'a` as defined here as required by this binding
  --> src/lib.rs:25:14
   |
25 |     type Gat<'a> = Cow<'a, Self>;
   |              ^^

For more information about this error, try `rustc --explain E0477`.

I tried adding where Self: 'a (see also #87479), but without success:

 #![feature(generic_associated_types)]
 
 use std::borrow::Cow;
 use std::ops::Deref;
 
 trait Trait {
-    type Gat<'a>: Deref<Target = Self>;
+    type Gat<'a>: Deref<Target = Self>
+    where
+        Self: 'a;
     fn func(src: &str) -> Self::Gat<'_>;
 }
 
 #[derive(Clone)]
 struct Easy(String);
 
 impl Trait for Easy {
-    type Gat<'a> = Cow<'a, Self>;
+    type Gat<'a> = Cow<'a, Self>
+    where
+        Self: 'a;
     fn func(src: &str) -> Self::Gat<'_> {
         Cow::Owned(Easy(src.to_owned()))
     }
 }
 
 #[derive(Clone)]
 struct Hard<'b>(&'b str);
 
 impl<'b> Trait for Hard<'b> {
-    type Gat<'a> = Cow<'a, Self>;
+    type Gat<'a> = Cow<'a, Self>
+    where
+        Self: 'a;
     fn func(src: &str) -> Self::Gat<'_> {
         Cow::Owned(Hard(src))
     }
 }

This gives the same error.

(Playground)

I even tried something like this:

 #![feature(generic_associated_types)]
 
 use std::borrow::Cow;
 use std::ops::Deref;
 
 trait Trait {
     type Gat<'a>: Deref<Target = Self>
     where
         Self: 'a;
-    fn func(src: &str) -> Self::Gat<'_>;
+    fn func<'a>(src: &'a str) -> Self::Gat<'a>
+    where
+        Self: 'a;
 }
 
 #[derive(Clone)]
 struct Easy(String);
 
 impl Trait for Easy {
     type Gat<'a> = Cow<'a, Self>
     where
         Self: 'a;
-    fn func(src: &str) -> Self::Gat<'_> {
+    fn func<'a>(src: &'a str) -> Self::Gat<'a>
+    where
+        Self: 'a,
+    {
         Cow::Owned(Easy(src.to_owned()))
     }
 }
 
 #[derive(Clone)]
 struct Hard<'b>(&'b str);
 
 impl<'b> Trait for Hard<'b> {
     type Gat<'a> = Cow<'a, Self>
     where
         Self: 'a;
-    fn func(src: &str) -> Self::Gat<'_> {
+    fn func<'a>(src: &'a str) -> Self::Gat<'a>
+    where
+        Self: 'a,
+    {
         Cow::Owned(Hard(src))
     }
 }

But then I get:

error: lifetime may not live long enough
  --> src/lib.rs:41:9
   |
33 | impl<'b> Trait for Hard<'b> {
   |      -- lifetime `'b` defined here
...
37 |     fn func<'a>(src: &'a str) -> Self::Gat<'a>
   |             -- lifetime `'a` defined here
...
41 |         Cow::Owned(Hard(src))
   |         ^^^^^^^^^^^^^^^^^^^^^ associated function was supposed to return data with lifetime `'b` but it is returning data with lifetime `'a`
   |
   = help: consider adding the following bound: `'a: 'b`
   = note: requirement occurs because of the type `Cow<'_, Hard<'_>>`, which makes the generic argument `Hard<'_>` invariant
   = note: the enum `Cow<'a, B>` is invariant over the parameter `B`
   = help: see <https://doc.rust-lang.org/nomicon/subtyping.html> for more information about variance

(Playground)

Simply adding 'a: 'b as the compiler suggested gives me error[E0276]: impl has stricter requirements than trait, of course.

My question is: Can I implement Trait for Hard<'_> and how can I do it? Maybe I'm just misunderstanding how lifetimes work in this case? Or is this something where the compiler doesn't work properly (yet)?

In the trait impl, Cow<'a, Self> is Cow<'a, Hard<'b>>.

The ToOwned impl at play here comes from Clone; the Cow<'a, Hard<'b>> is thus

  • either a Cow::Owned(Hard<'b>)
  • or a Cow::Borrowed(&'a Hard<'b>)

The type &'a Hard<'b> is only valid if Hard<'b>: 'a, i.e. if 'b: 'a, that’s why the Self: 'a bound helps a bit, otherwise you can’t define the GAT like that in the first place.

With the Self: 'a bound on the GAT, you can only use that type if 'b: 'a.

The fn func(src: &str) -> Self::Gat<'_> function, aka fn func<'a>(src: &'a str) -> Hard<'b>::Gat<'a> does not come with any 'a: 'b or 'b: 'a bounds, even implicit ones; so the type Hard<'b>::Gat<'a> which requires 'b: 'a to be valid to use, is problematic, unless you also put the Self: 'a on there, too.

But then… the implementation. As mentioned above, the owned variant is Cow::Owned(Hard<'b>), which you can only construct from a &'b str, not a &'a str, unless 'a is longer than 'b, i.e. 'a: 'b.


So AFAICT, the compiler works properly in all these cases.

Regarding how to “make it work”, well, hard to say without knowing the practical use-case. Maybe you don’t need a GAT at all? A trait with lifetime arguments might work well, if the lifetime argument (or perhaps one of multiple lifetime arguments) is the lifetime of the &str argument of func. I can’t really suggest any good concrete best approach without knowing how you intend to be able to use these trait implementations.

3 Likes

I think I can follow. Going through your answer and my example, I managed to get a version that seems to compile:

#![feature(generic_associated_types)]

use std::borrow::Cow;
use std::ops::Deref;

trait Trait<'c> {
    type Gat<'a>: Deref<Target = Self>
    where
        Self: 'a,
        'a: 'c;
    fn func<'a>(src: &'a str) -> Self::Gat<'a>
    where
        Self: 'a,
        'a: 'c;
}

#[derive(Clone)]
struct Easy(String);

impl<'c> Trait<'c> for Easy {
    type Gat<'a> = Cow<'a, Self>
    where
        Self: 'a,
        'a: 'c;
    fn func<'a>(src: &'a str) -> Self::Gat<'a>
    where
        Self: 'a,
        'a: 'c,
    {
        Cow::Owned(Easy(src.to_owned()))
    }
}

#[derive(Clone)]
struct Hard<'b>(&'b str);

impl<'b, 'c> Trait<'c> for Hard<'b>
where
    'c: 'b,
{
    type Gat<'a> = Cow<'a, Self>
    where
        Self: 'a,
        'a: 'c;
    fn func<'a>(src: &'a str) -> Self::Gat<'a>
    where
        Self: 'a,
        'a: 'c,
    {
        Cow::Owned(Hard(src))
    }
}

(Playground)

Maybe it can be simplified further, I didn't try hard yet.

What I dislike about this "solution", is that I have to add a lifetime argument to Trait, which isn't needed at all for the Easy case. This would bloat up my code significantly, and it seems to be there for syntactical reasons of the Hard case only. (But not sure if it's correct at all.)

The Trait is mmtkvdb::storable::Storable and the GAT is Storable::AlignedRef.

Here is my use case:

[dependencies]
mmtkvdb = "0.8.0"
serde_json = "1"

Using:

My code looks as follows (so far):

#![feature(generic_associated_types)]

use mmtkvdb::{self as kv, GenericCow, Owned, Txn as _};
use serde_json as json;

use std::borrow::Cow;
use std::cmp;
use std::str;

#[derive(Clone)]
struct JsonDoc<'a> {
    repr: Cow<'a, str>,
    data: json::Value,
}

unsafe impl<'a> kv::Storable for JsonDoc<'a> {
    const CONST_BYTES_LEN: bool = false;
    const TRIVIAL_CMP: bool = true;
    type BytesRef<'b> = &'b [u8]
    where
        Self: 'b;
    type AlignedRef<'b> = Owned<Self>;
    fn to_bytes(&self) -> Self::BytesRef<'_> {
        self.repr.as_bytes()
    }
    unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
        let repr = str::from_utf8_unchecked(bytes);
        Owned(JsonDoc {
            repr: Cow::Borrowed(repr),
            data: json::from_str(repr).unwrap(),
        })
    }
    unsafe fn cmp_bytes_unchecked(a: &[u8], b: &[u8]) -> cmp::Ordering {
        a.cmp(b)
    }
}

And I got this error:

error: lifetime may not live long enough
  --> src/lib.rs:28:9
   |
16 |   unsafe impl<'a> kv::Storable for JsonDoc<'a> {
   |               -- lifetime `'a` defined here
...
26 |       unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
   |                                             - let's call the lifetime of this reference `'1`
27 |           let repr = str::from_utf8_unchecked(bytes);
28 | /         Owned(JsonDoc {
29 | |             repr: Cow::Borrowed(repr),
30 | |             data: json::from_str(repr).unwrap(),
31 | |         })
   | |__________^ associated function was supposed to return data with lifetime `'a` but it is returning data with lifetime `'1`
   |
   = note: requirement occurs because of the type `mmtkvdb::Owned<JsonDoc<'_>>`, which makes the generic argument `JsonDoc<'_>` invariant
   = note: the struct `mmtkvdb::Owned<B>` is invariant over the parameter `B`
   = help: see <https://doc.rust-lang.org/nomicon/subtyping.html> for more information about variance

I could replace the GAT with Cow<'_, Self> in mmtkvdb, but that might impose runtime overhead [1] in other use-cases of mmtkvdb. The actual runtime overhead might be very very small, but I also wanted to experiment with GenericCow here (or GATs in that matter).

So if I understand it right, I would need to add a lifetime argument to Storable in order to solve what I'm trying to achieve? (I remember another case where I had to add a seemingly unused lifetime argument to a trait, sandkiste::Machine, see also this post; but maybe these two cases are entirely unrelated).

But what does this lifetime argument ('c in the Playground) mean? It seems to be there because I cannot otherwise express 'a: 'b but being otherwise superfluous.


  1. In case of the current implementation of Storable for basic data types from std in mmtkvdb::storable (see source, always copying types which might be unaligned and never copying types which do not have alignment requirement), it is always known at compile-time whether the database interface returns an owned value (where re-alignment is needed) or a reference (where re-alignment isn't needed). I would lose that knowledge at compile time if I replace the GAT with Cow. ↩︎

@steffahn's point was that the implementation can only work for a single lifetime. That is, given an attempt at

// Desugared form of your GAT method, minus bounds
fn func<'a, 'b>(s: &'a str) -> Cow<'a, Hard<'b>>  { Cow::Owned(Hard(s)) }

We have

'a: 'b // due to `s` needing to be a subtype of `Hard<'b>::0`
'b: 'a // due to `Cow::<'a, Hard<'b>>::Borrowed(&'a Hard<'b>`)
       // AKA `Self = Hard<'b>: 'a`

So it can only work for 'a == 'b and cannot satisfy your OP GAT:

fn func<'a>(s: &'a str) -> Cow<'a, Hard<'a>>  { Cow::Owned(Hard(s)) }

Similarly in your new version you have

impl<'b, 'c> Trait<'c> for Hard<'b>
where
    'c: 'b,
{
    type Gat<'a> = Cow<'a, Self>
    where
        Self: 'a,
        'a: 'c;

And since Self = Hard<'b>: 'a, and given the bounds on the impl, the bounds on Gat can be expanded to

Self: 'b: 'a: 'c: 'b
// and so
'b >= 'a >= 'c >= 'b
// and so
'b == 'a == 'c == 'b

And thus the simplification is

trait Trait<'c> {
    type NeedNoGat: Deref<Target = Self>;
    fn func(src: &'c str) -> Self::NeedNoGat;
}

impl<'c> Trait<'c> for Easy {
    type NeedNoGat = Cow<'c, Self>;
    fn func(src: &'c str) -> Self::NeedNoGat {
        Cow::Owned(Easy(src.to_owned()))
    }
}

impl<'c> Trait<'c> for Hard<'c> {
    type NeedNoGat = Cow<'c, Self>;
    fn func(src: &'c str) -> Self::NeedNoGat {
        Cow::Owned(Hard(src))
    }
}

And just as Easy can satisfy the OP GAT trait and Hard cannot, Easy can satisfy for<'x> Trait<'x> while Hard<'_> cannot -- any given Hard<'concrete> can only satisfy Trait<'concrete>.


Note that your Easy implementations work in a higher-ranked context not because you can somehow extend the lifetime of src itself, but because the ToOwned implementations results in a 'static type (String). The ToOwned implementation of a &'x T, in contrast, results in a type with lifetime 'x.

You could have some sort of higher-rankedness if you rigged a 'c: Self bound (not a valid syntax), but this is probably the opposite of what you want. In terms of the above, it would be something like this implementation:

impl<'c: 'short, 'short> Trait<'c> for Hard<'short> {
    type NeedNoGat = Cow<'short, Self>;
    fn func(src: &'c str) -> Self::NeedNoGat {
        Cow::Owned(Hard(src))
    }
}

It won't really help in practice I imagine, because with the single-lifetime version, covariance on src will achieve the same thing. A 'c bound on NeedNoGat (or Trait<'c>) would also force everything back down to a single lifetime, ala a Self: 'a bound on the Gat version.


I haven't looked at your actual use-case, but maybe custom DSTs is a better fit. Note that every std implementation of ToOwned outside of T: Clone is of the form

impl ToOwned for UnsizedTypeWithNoLifetimeParameter { // e.g. str, [T]
    type Owned = SizedTypeWithNoLifetimeParameter; // e.g. String, Vec<T>
    // ...
}

(And note how the implementation in the last playground link goes to the borrowed version of the Cow, ala the implementation of From<&'a str> for Cow<'a, str>.)

2 Likes

Thank you very much for the explanations. I guess my Storable (Trait) needs a lifetime argument then. When I create it from a reference to a string or byte slice of an arbitrary lifetime 'a, it will (or must) be "infected" with that lifetime 'a. If I omit the lifetime in the trait, then I can only handle static types types whose lifetime does not depend on the lifetime of the input when reading the value from a &str or &[u8]). Interesting (and I hope I got it right).

I wonder if that's the same reason why serde has a 'de lifetime argument in serde::Deserialize<'de> and related traits.

Oh, I didn't know that custom DSTs can be used already. I read the section on DSTs in the Nomicon a while ago:

Structs can actually store a single DST directly as their last field, but this makes them a DST as well: […] Although such a type is largely useless without a way to construct it. Currently the only properly supported way to create a custom DST is by making your type generic and performing an unsizing coercion: […]

That left me with the impression that this is still work-in-progress, and I see your Playground uses #![feature(ptr_metadata)]. Not per-se a problem for me, I use Nightly, and I will try to understand your example.

In my use-case, I want to parse the stored JSON document while maintaining a reference to the original formatting of it:

#[derive(Clone)]
struct JsonDoc<'a> {
    repr: Cow<'a, str>,
    data: serde_json::Value,
}

Since the reference will point to a memory-mapped file, and there's additional data (serde_json::Value) that's to be generated when retrieving the JsonDoc structure, I think a custom DST might not work for me (but I understand too little of that yet to be sure). All this is still work-in-progress for me, too, and I will play a bit and check how things behave if I add the lifetime argument to Storable and make Storable::AlignedRef a non-GAT.

Side note: I believe Storable::BytesRef<'a>, which is used for Storable::to_bytes, still needs to be a GAT. Here, the compiler also requested me to add a Self: 'a bound (unlike AlignedRef).


Seems to be tricker than I thought because the database handle (mmtkvdb::Db) takes type arguments K and V to determine the type for the keys and values, for example. I guess if Storable had a lifetime argument, then K and V in Db<K: ?Sized, V: ?Sized, C> would need to be type-constructors [1] rather than types. The same might apply to other places where I have type arguments.

I don't know if I understand things correctly, but I feel like adding a lifetime argument to Storable would make things very very complicated.


  1. Something that I have previously (half jokingly) described as being of kind ' -> *. ↩︎

There might be a better way, i.e. maybe you can straight-up implement CoerceUnsize and avoid the unsafe. (I haven't played with custom DSTs really.)

In Rust this would mean that the database handle mmtkvdb::Db as well as some builder types like mmtkvdb::DbOptions and basically the whole interface including the mmtkvdb::Txn::get method would not get the key type and value type of keys/values written to or retrieved from the database as arguments, but instead type-constructors (technically implemented through a type with a GAT in Rust), which can map a lifetime to a type.

Following this idea and applying it to the Playground example, the Trait, would need an additional GAT like this:

trait Trait {
    // constructs supertype, e.g. one with shorter lifetime arg:
    type WithLt<'a>;
    /* … */
}

Unfortunately, I don't think I can add a bound that requires Trait::WithLt<'a> to be a supertype of Trait. (edit: Probably not needed, because Trait::WithLt<'a> would be known to be a supertype of Trait::WithLt<'static>). I could, however, demand that there exists a function to manually cast from a subtype to the supertype (which might be necessary for generic code):

trait Trait {
    /* … */
    // cast from subtype to supertype
    fn cast_lt<'a>(this: Self) -> Self::WithLt<'a>;
    /* … */

When func of my original Playground example is called, it would not give a reference-like type to Self, but to Self with the corresponding lifetime:

trait Trait {
    /* … */
    // return type of `func`
    type Gat<'a>: Deref<Target = Self::WithLt<'a>>;
    // function that returns reference-like type `Gat<'a>`
    fn func(src: &str) -> Self::Gat<'_>;
    /* … */
}

In fact, Hard in my original Playground is a type-constructor already (it receives a lifetime argument and returns a type). But we cannot implement a trait for a type-constructor. Thus we use a 'static (dummy) lifetime:

impl Trait for Hard<'static> {
    type WithLt<'a> = Hard<'a>;
    fn cast_lt<'a>(this: Self) -> Self::WithLt<'a> {
        this
    }
    type Gat<'a> = Cow<'a, Hard<'a>>;
    fn func(src: &str) -> Self::Gat<'_> {
        Cow::Owned(Hard(src))
    }
}

Then we can later do things like this:

trait Txn<T: ?Sized + Trait> {
    fn get(&self) -> T::Gat<'_>;
    fn put<'a, U>(&mut self, value: &'a T::WithLt<'a>);
}

struct DummyTxn<'a>(&'a str);

impl<'b> Txn<Hard<'static>> for DummyTxn<'b> {
    fn get(&self) -> <Hard<'static> as Trait>::Gat<'_> {
        /* … */
    }
    fn put<'a, U>(
        &mut self,
        value: &'a <Hard<'static> as Trait>::WithLt<'a>,
    ) {
        /* … */
    }

}

Here a small example of how I picture it: Playground.

I wrote this down mostly of curiosity. I doubt it's feasible in practice, because syntax will get even more complex than it already is. But not sure yet.

A database that stores integers as keys and JsonDoc's as values could then be described like:

mmtkvdb::Db<i32, JsonDoc<'static>>

where JsonDoc<'static> is in fact used as a type-constructor that can convert a lifetime 'a to a type JsonDoc<'a>.


Or not:

I see there has been a discussion on IRLO about this: Variance of lifetime arguments in GATs.


  1. Something that I have previously (half jokingly) described as being of kind ' -> *. ↩︎

I'm slowly trying to understand custom DSTs better, and based on your example, I made myself a minimal example to understand how they generally work:

#![feature(ptr_metadata)]

use std::ptr::from_raw_parts;

#[repr(transparent)]
struct Json(str);

impl Json {
    fn new_ref(s: &str) -> &Self {
        let (data, meta) = (s as *const str).to_raw_parts();
        let this: *const Json = from_raw_parts(data, meta);
        unsafe { &*this }
    }
}

fn main() {
    let s = "Hello";
    let j: &Json = Json::new_ref(s);
    drop(j);
}

(Playground)

So that's the newtype pattern, but on a type that is !Sized (str in this case). Perhaps that can help me to indicate that the stored string is indeed a valid JSON document.


I wonder if it's possible to do that (simple example) without unsafe.


Maybe it could be encapsulated by a macro like this:

macro_rules! unsized_newtype {
    { $(#[$meta:meta])* $vis:vis struct $outer:ident($inner:ty); } => {
        $(#[$meta])*
        #[repr(transparent)]
        $vis struct $outer(pub $inner);
        impl ::core::convert::AsRef<$outer> for $outer {
            fn as_ref(&self) -> &Self {
                self
            }
        }
        impl ::core::convert::AsRef<$outer> for $inner {
            fn as_ref(&self) -> &$outer {
                let (data, meta) = (self as *const Self).to_raw_parts();
                let r = ::core::ptr::from_raw_parts::<$outer>(data, meta);
                unsafe { &*r }
            }
        }
        impl ::core::convert::AsRef<$inner> for $outer {
            fn as_ref(&self) -> &$inner {
                let (data, meta) = (self as *const Self).to_raw_parts();
                let r = ::core::ptr::from_raw_parts::<$inner>(data, meta);
                unsafe { &*r }
            }
        }
    }
}

(Playground)