GATs: Decide whether to have defaults for `where Self: 'a`

[nikomatsakis]

Coming from the "missing required bounds" error?

The "missing required bounds" error that was emitted is intended to ensure that current code is forwards-compatible with potential future changes. We'll provide a brief summary of the why the bounds are required, the potential future changes, and a workaround if the required bounds are too restrictive. We would appreciate any feedback for this issue.

Why are these bounds required

Let's start by imagining a trait:

trait Iterable {
    type Item<'x>;
    fn iter<'a>(&'a self) -> Self::Item<'a>;
}

As-is, nothing looks wrong about this; without the "missing required bounds" error, this would compile. However, let's try to add an impl:

impl<T> Iterable for T {
    type Item<'a> = &'a T;
    fn iter<'a>(&'a self) -> Self::Item<'a> { self }
}

This definition of Item<'a> = &'a T is invalid, since we don't know that T outlives 'a. So, our first thought might be to modify the definition to add a where Self: 'a clause. This is what we want. However, impls are not allowed to have more where clauses than the trait.

Luckily, we can detect in a trait when this type of problem might occur. To do this, we look at the trait methods that construct the GAT. There, we find the bounds that we know and require that those bounds be written on the GAT itself.

Here, on the Iterable trait, we construct the GAT Self::Item<'a> in the iter method. There, we have an argument &'a self, which allows us to know Self: 'a. Therefore, we require the where Self: 'a bound on the GAT.

Potential future changes

Following the above logic, if we know all the required bounds when the trait is written, why require them at all? In fact, allowed these bounds to be implied is a potential future change. However, to make this change in a backwards-compatible manner, we must require the bounds now that we want to eventually imply. At that time, the written bounds will be redundant and can be removed.

This breaks my code. Workaround?

First, if any code breaks from adding the required bounds, we really want feedback. Second, the workaround is to move the GAT into a super trait. Using the example above, our new code would look like:

trait IterableSuper {
    type Item<'x>;
}
trait Iterable: IterableSuper {
    fn iter<'a>(&'a self) -> Self::Item<'a>;
}

Previous discussion

What is this bug?

We are moving towards stabilizing GATs (tracking issue: #44265) but there is one major ergonomic hurdle that we should decide how to manage before we go forward. In particular, a great many GAT use cases require a surprising where clause to be well-typed; this typically has the form where Self: 'a. It might be useful if we were to create some rules to add this rule by default. Once we stabilize, changing defaults will be more difficult, and could require an edition, therefore it's better to evaluate the rules now.

I have an opinion! What should I do?

To make this decision in an informed way, what we need most are real-world examples and experience reports. If you are experimenting with GATs, for example, how often do you use where Self: 'a and how did you find out that it is necessary? Would the default proposals described below work for you? If not, can you describe the trait so we can understand why they would not work?

Of great use would be example usages that do NOT require where Self: 'a. It'd be good to be able to evaluate the various defaulting schemes and see whether they would interfere with the trait. Knowing the trait and a rough sketch of the impls would be helpful.

Background: what where clause now?

Consider the typical "lending iterator" example. The idea here is to have an iterator that produces values that may have references into the iterator itself (as opposed to references into the collection being iterated over). In other words, given a next method like fn next<'a>(&'a mut self), the returned items have to be able to reference 'a. The typical Iterator trait cannot express that, but GATs can:

trait LendingIterator {
    type Item<'a>;

    fn next<'b>(&'b mut self) -> Self::Item<'b>;
}

Unfortunately, this trait definition turns out to be not quite right in practice. Consider an example like this, an iterator that yields a reference to the same item over and over again (note that it owns the item it is referencing):

struct RefOnce<T> {
    my_data: T    
}

impl<T> LendingIterator for RefOnce<T> {
    type Item<'a> where Self: 'a = &'a T;

    fn next<'b>(&'b mut self) -> Self::Item<'b> {
        &self.my_data
    }
}

Here, the type type Item<'a> = &'a T declaration is actually illegal. Why is that? The assumption when authoring the trait was that 'a would always be the lifetime of the self reference in the next function, of course, but that is not in fact required. People can reference Item with any lifetime they want. For example, what if somebody wrote the type <SomeType<T> as LendingIterator>::Item<'static>? In this case, T: 'static would have to be true, but T may in fact contain borrowed references. This is why the compiler gives you a "T may not outlive 'a" error (playground).

We can encode the constraint that "'a is meant to be the lifetime of the self reference" by adding a where Self: 'a clause to the type Item declaration. This is saying "you can only use a 'a that could be a reference to Self". If you make this change, you'll find that the code compiles (playground):

trait LendingIterator {
    type Item<'a> where Self: 'a;

    fn next<'b>(&'b mut self) -> Self::Item<'b>;
}

When would you NOT want the where clause Self: 'a?

If the associated type cannot refer to data that comes from the Self type, then the where Self: 'a is unnecessary, and is in fact somewhat constraining. As an example, consider:

XXX finish this

What could we do about it?

There are a few options. Here is the list of ideas we've had so far.

1. Status quo: require that people add the where Self: 'a bounds, and try to do better with diagnostics.
2. Simple, limited default: If a GAT has exactly one lifetime parameter 'a, add where Self: 'a to both traits and impls. Need some way to opt out.
3. More extensive defaults: e.g., for every lifetime parameter 'a to a GAT, add where Self: 'a, and maybe where T: 'a for type parameters too. Need some way to opt out.
4. Add a syntactic sugar for this common case, e.g. type Foo<'self>. This could be added later.
5. self-oriented defaults: Given some GAT Foo<'a>, if each use Self::Foo<'b> within the trait methods references a 'b that is the lifetime parameter for self, then add where Self: 'b. While kind of complex to explain, this captures the intuition that 'a is meant to be the "lifetime of the self reference" in practice. We probably still want a way to opt out (though maybe not; maybe that way is "don't use &'a self notation").
6. Even smarter defaults A: Look at the method signatures in the trait. If we find that each use of Self::Item<'b> is associated with a lifetime 'b where Self: 'b is implied by the method arguments, then infer that where Self: 'b. This is a more extensive, general version of self-oriented defaults. We probably still want a way to opt out (though maybe not).

In general, once we stabilize GATs, we likely cannot add defaults, except via an edition -- although we may be able to get away with it in this instance if the defaults are smart enough.

[nikomatsakis]

cc @rust-lang/lang

[cramertj]

Of great use would be example usages that do NOT require where Self: 'a. It'd be good to be able to evaluate the various defaulting schemes and see whether they would interfere with the trait. Knowing the trait and a rough sketch of the impls would be helpful.

One of the ones that seems most obvious to me is when the output borrows not from self, but from a parameter to the method, such as in the case of a parser:

trait Parser {
    type Output<'a>;
    fn parse<'a>(&mut self, data: &'a [u8]) -> Self::Output<'a>;
}

Parser output wouldn't usually reference state internal to the parser, but it very well may reference the input data. In practice, you can express this instead with for<'a> Parser<'a>, but it's often the case that lifetime-only GATs can be replaced with HRTB-based solutions. I think it might be a goal of ours to allow people to avoid HRTBs for these types of things-- if it is, then this use-case is worth considering.

[jplatte]

For another example where Self: 'a would be wrong, in Ruma we have a trait IncomingRequest that I've long wanted to use GATs for, which would be another example of this. Simplified:

// Every endpoint in the Matrix REST API has two request and response types in Ruma, one Incoming
// (used for deserialization) and out Outgoing (used for serialization). To avoid annoying clones when
// sending a request, most non-copy fields in the outgoing structs are references.
//
// The request traits have an associated type for the corresponding response type so things can be
// matched up properly.
pub trait IncomingRequest: Sized {
    // This is the current definition of the associated type I'd like to make generic.
    type OutgoingResponse: OutgoingResponse;
    // AFAICT adding a lifetime parameter is all I need.
    type OutgoingResponse<'a>: OutgoingResponse;

    // Other trait members... (not using Self::OutgoingResponse)
}

(full definition here if sbd. is curious)

My 2c regardingthe potential solutions: type Foo<'self> looks really nice.

[ShadowJonathan]

I'm also in favour of keeping status quo and adding the implicit 'self lifetime, it balances the need for being explicit with DRY, is easy to hint at by the compiler (for one scenario or another), and easy to reference by the book & other resources.

In general I think the compiler shouldn't try to be "smart" about this, I'm still a learning rustacean, but having the compiler try to infer multiple lifetimes by default, and implicitly, seems confusing and footgun-y to me.

[ammkrn]

I have a use case of the kind @cramertj referenced that I ended up working around with macros, but I would like to try and remove them when GATs are available. Also for cramertj, I couldn't figure out how to implement your example with HRTBs, so if you can actually do that I'd be interested to learn how it's done.

My specific use case is a little more complex, but I think the idea is relevant to many applications of indirect data structures. I have tree structures that are managed with type/memory safe integer pointers:

struct Ptr<'a, A> {
  id: usize,
  marker: PhantomData<&'a A>

The backing storage struct looks like:

struct Store<'a> {
  a_set: IndexSet<ThingA<'a>>,
  b_set: IndexSet<ThingB<'a>>,
  ..
  n_set: IndexSet<ThingN<'a>>,
}

The program is a type checker, so there may be multiple stores alive with lifetimes 'a > 'b > .. 'n, but they nest, so we're always dealing with the "outermost" one (with the shortest lifetime). The guarantees I'm currently able to enforce within Rust's type system are that a Ptr<'a, A> can't outlive its backing Store<'a>, and that you can only create a Ptr<'a, A> if you actually have a Store<A>. The macro-based solution runs really well, but GATs would be much more satisfying. The GAT solution I originally wanted was to have a trait for the stored types so that the output's lifetime was dependent on the lifetime of the backing store that was passed as an argument. As long as the underlying data is alive at least as long as the backing store I've been passed, I can both read a Ptr<'a, A> -> A and allocate an A -> Ptr<'a, A>.

trait IsStored<'x>: Sized {
    type Carrier<'a>;
    fn read<'a, S: Store<'a>>(self, storage: &mut S) -> Self::Carrier<'a>
    where 'x: 'a ;
    fn alloc<'a, S: Store<'a>>(self, storage: &mut S) -> Ptr<'a, Self::Carrier<'a>>
    where 'x: 'a;
}

In this case, it seems like type Carrier<'a> where Self: 'a would be incorrect, but I wrote up a basic implementation of it with the syntax proposed here and it seems to compile on nightly, I guess because the actual self lifetime is longer than the 'a bound, though I'm sure there are programs that would benefit from similar indirect structures in which that wouldn't always be the case.

Also I have no idea if this is possible, but in playing around with this feature with the thought of making stuff generic over lifetimes, it would be cool if there was a way to add sugar or something to enable this:

trait Thing {
    fn f<'a>(self, ctx: &'a Ctx) -> Self<'a>;
}

// Desugars to something like:
impl<'x> Thing for A<'x> {
  type Assoc<'a> = A<'a>;
  fn f<'a>(self, ctx: &'a Ctx) -> Self::Assoc<'a> { .. }
}

[P-E-Meunier]

GATs are probably the only feature I've been missing in Rust since 1.0, I'm delighted to see progress on that.

@nikomatsakis, I do have an example where Self: 'a isn't always the case: in Sanakirja, an on-disk key-value store I wrote, memory management is a bit messy. I'd also like to extend it by implementing other transactional datastructures in the future.

Since I don't know the kind of details yous need, here is a quick summary of how Sanakirja works:

• There is a number of memory-mapped files, of exponentially-increasing size (db0 is of some size given by the user, then when we run out of space in the middle of a transaction we start db(n+1), which is twice the size of db(n)). This trick allows us to never unmap the file in the middle of a transaction. Some of the pointers (explained below) may still be valid after an increase.
• A fixed-size cyclic array of memory pages at the beginning of db0 (of a size set when creating the database) is dedicated to independent versions of the database, and only the latest version is writable, and writable by a single (mutable) transaction. The only concurrency control is a simple read-write lock on each of these memory pages.
• Pages are allocated and freed by maintaining two distinct extra B trees: one for free pages (edits in that tree are done by allocating new pages at the end of the file), and another one to store reference counts of pages referenced at least twice. The pointer to the root of these trees is stored in the transactions' pages in the initial cyclic array.
• Another thing stored in the cyclic array is a number of "roots", which are pointers to some pages in the file. I do abuse these pages sometimes as well to write other things, even though that is probably fairly unsafe if you don't know how things work.

Now, there's a choice about the lifetime of values retrieved from the database: we may choose to have them borrow the transactions, or to have them borrow individual tables. In the former case, a GAT may look like:

trait TableIterator {
  type Iter<'txn, K, V>: Iterator<(&'txn K, &'txn V)>;
  fn iter(&'txn self, db: &'txn Db<K, V>) -> Self::Iter<'txn, K, V>;
}

In the latter case, we'll have the following instead:

trait TableIterator {
  type Iter<'db, K, V>: Iterator<(&'db K, &'db V)>;
  fn iter(&'txn self, db: &'db Db<K, V>) -> Self::Iter<'db, K, V>;
}

This could work with an extra mechanism to make sure Db isn't alive after the end of a transaction, for example.

As a conclusion, I don't have a strong opinion about what the default should be, since I understand this is a rather niche use case. I haven't actually tried to implement these using nightly + GAT, but I could try if yous need more feedback.

[eira-fransham]

I feel like you're always going to want to allow where Self: 'a even if you don't always require it, so why not stabilise it with the requirement that you must always annotate and add elision later as a separate RFC? That's what we did for lifetime elision in impl specs (e.g. impl Trait for &'_ Foo). This is now, as far as I know, the only remaining blocker for GATs being stabilised so it seems silly to hold that up while we bikeshed this considering that there exists a MVP solution that would be trivial to improve on later in a backwards-compatible way.

[nikomatsakis]

Hi all! I'm reading these responses and trying to summarize.

@P-E-Meunier what would be useful is to see not only the trait definition, but prospective impl definitions

@ammkrn the same! What does an impl for the trait IsStored look like? You mentioned that you prototyped your setup on nightly, can you link to that on the Rust playground perhaps?

[ammkrn]

@nikomatsakis

I put it in a gat_nightly branch, here are the impls for one base type and its pointer.
https://github.com/ammkrn/nanoda_lib/blob/4c46ec08cb80e12de1cf5a312f17c3fd67feb228/src/utils.rs#L370
https://github.com/ammkrn/nanoda_lib/blob/4c46ec08cb80e12de1cf5a312f17c3fd67feb228/src/utils.rs#L409

This application's state management is somewhat involved for performance reasons, but I think this issue boils down to what I believe is a GAT use case that's been discussed quite a bit, which is generalizing over the lifetime of a container.

ctx is the telescope of stores,'a is the lifetime of the outermost/shortest-lived backing store, and the one we have mutable access to. 'x is any lifetime equal to or longer than 'a. The two ideas are: "given a pointer to an object known to live at least as long as the shortest-lived store, I can return the pointed-to data, though I can only guarantee it lives as long as the shortest-lived store", and "given some data, I can allocate it and return a pointer, but I can only promise the pointer is good for the lifetime of the shortest-lived store".

or:
read: ∀ 'x >= 'a, (Ptr<'x>, Store<'a>) -> Data<'a>
alloc: ∀ 'x >= 'a, (Data<'x>, Store<'a>) -> Ptr<'a>

[jgarvin]

I ran into a simple case using GATs where I didn't need the clause. I have a trait representing mutable pointers so that I can write generic functions that work both with regular pointers and compressed pointers. Since it's for pointers, there are no lifetimes.

pub trait MutPointer<T>:
{
    type Cast<U>: MutPointer<U>;

    fn cast<U>(self) -> Self::Cast<U>;

    // ... other less relevant methods
}

This is analogous in C++ to std::static_pointer_cast and related functions which work both on regular pointers and smart pointers like shared_ptr and unique_ptr. One problem that still exists with this is that MutPointer<U> could still be some other smart pointer type when it should really be the same generic with a different type plugged in (in other words you shouldn't be able to implement the trait such that shared_ptr<T> is castable to unique_ptr<U>, only shared_ptr<U>). I think doing it right might require HKTs. Something like:

pub trait MutPointer<P<T>>:
{
    fn cast<U>(self) -> P<U>;
}

[dbdeviant]

I recently came across a scenario where I didn't need the clause. The library performs async serialization for any given user provided format (basically async serde). In my case, only the serializer trait needed the Self lifetime annotation, as the returned future from the method holds on to a reference to the data until complete. The deserializer owns its own internal buffers, and as such just defines an associated function for which no Self reference is needed.

In this case, it would seem that option 6 would be necessary to properly infer the type. (Full disclosure: new rustacean here, so there might be a better way to do this.)

My type definitions:

/// Serialize a data structure asynchronously.
pub trait AsyncSerialize: Encodable
{
    /// The concrete [future](Future) returned by the `serialize` method.
    type Future<'w, F, W>: Future<Output=Result<(), F::Error>> + Unpin
    where
        Self: 'w,
        F: 'w + FormatSerialize,
        W: 'w + AsyncWrite + Unpin,
    ;

    /// Attempt to serialize the type asynchronously for the indicated [format](Format)
    /// via the provided [asynchronous writer](AsyncWrite).
    fn serialize<'w, F, W>(&'w self, format: &'w F, writer: &'w mut W) -> Self::Future<'w, F, W>
    where
        F: FormatSerialize,
        W: AsyncWrite + Unpin,
    ;
}

/// Deserialize a data structure asynchronously.
pub trait AsyncDeserialize: Decodable
{
    /// The concrete [future](Future) returned by the `deserialize` method.
    type Future<'r, F, R>: Future<Output=Result<Self, F::Error>> + Unpin
    where
        F: 'r + FormatDeserialize,
        R: 'r + AsyncRead + AsyncBufRead + Unpin,
    ;

    /// Attempt to deserialize the type asynchronously for the indicated [format](Format)
    /// via the provided [asynchronous reader](AsyncRead).
    fn deserialize<'r, F, R>(format: &'r F, reader: &'r mut R) -> Self::Future<'r, F, R>
    where
        F: FormatDeserialize,
        R: AsyncRead + AsyncBufRead + Unpin,
    ;
}