Associated type bounds: for the user of for the implementer?

Usually, a bound on a generic type/lifetime/const is something the user must satisfy, and the implementer can reply on.

For instance, in

fn foo<T: Hash>(value: T) { ... }

the T: Hash bound means that the user may only instantiate foo() with types that implement Hash, and the implementer can rely on T implementing Hash.

However, in an associated type in a trait

trait Foo {
    type Bar: Hash;
}

it's the other way around: the trait implementer has to supply a type that implements Hash, and the user, given a T: Foo, can reply on the fact that T::Bar implements Hash.

But now with GATs, it becomes possible to write this:

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

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

note that where Self: 'a bound (whose point is explained here). That bound is for the trait user, not the implementor! It, once again, means that the user can only instantiate <I as LendingIterator>::Item with lifetimes that satisfy the constraint, and the trait implementer can reply on that constraint being satisfied.

So my question now is: how does that work? How do the two mechanisms — bounds for the user and for the implementer — play nice and work consistently with each other? Can I have both?

trait Foo {
    type Bar<'a>: Hash where Self: 'a;
}

what if there's a single bound that cannot be classified as a purely for-user or purely for-implementer bound?

trait Foo {
    type Bar<T> where Spam<Self::Bar<T>>: Baz<T>;
}

Finally, is there a consistent mental model that would help me think about this?


I hope the answer is not ": Trait bounds must be satisfied by the implementer, where bounds must be satisfied by the user"; that would be very inconsistent with the way : Trait bounds are simply a shortcut for an equivalent full where clause in the rest of the language.

1 Like

It's not. They are completely equivalent. (Well, "where" can express more kinds of constraints, technically, but that's not the point.)

Not "usually". That is true when the type is a generic parameter. A generic parameter is an input to a type, therefore any bounds have to be satisfied whoever choses the type, and then the implementor can rely on it being satisfied.

In contrast, an associated type is an output of a generic type. So the implementation can choose the
concrete type, being obliged to uphold any bounds on it, and then whoever uses the type can rely on that.

AssociatedType: [bound] is equivalent to a higher-ranked bound on the trait, but AssociatedType where [bound] is checked upon use.

Edit: Note that the syntax between : or where is not relevant as explained by @H2CO3 below; what is relevant is that

  • AssociatedType: [bound] is a bound on the GAT itself
    • These are "lifted" to be attached to the containing trait
  • AssociatedType where [bound] cannot be; it's a bound on something else (such as Self or a type parameter)
    • These are checked upon use

And also note that

  • AssociatedType<Generic: Bound> is syntactic sugar for AssociatedType<Generic> where Generic: Bound (so is still a where clause and is not a bound on the GAT itself)

The implementer of the trait is usually also a user of the generic associated type, in some sense. They will usually construct concrete types from the generic declaration (aka type constructor) as part of the implementation.

1 Like

Thanks. So it's exactly what I feared; they are not equivalent, contrary to what @H2CO3 has said?

I don't believe that contradicts my statement. In the cited example, the colon-constraints and the where-constraints are applied at two different places. The colon-constraint is applied globally to Self whereas the where-constraint is applied only when declaring (and evaluating) the associated type.

A fair comparison would have been trait Foo: Supertrait vs trait Foo where Self: Supertrait — those are exactly equivalent, so much that in fact the former is syntactic sugar for the latter. Similarly, when declaring a generic function or type, fn foo<T: Bar>() and fn foo<T>() where T: Bar are also exactly equivalent.

It's just that in the cited example, the constraint declared with the associated type is not on the associated type. This means that you can't express it using the colon syntax, you have to use where. So it's merely that where is strictly more general, and any colon-constraint can be transformed to an equivalent where-constraint, but the converse is not true.

Furthermore, even though the difference in the cited example exists, it's not what you were originally concerned about (who needs to satisfy it and who can rely on it). That is captured by the distinction between type parameters and associated types, as mentioned ij my first post.

1 Like

If I'm understanding the part of the RFC that @quinedot has linked right, that is the difference. So if we have

type Foo<'a>: Bar<'a>;

then that is something the implementer has to uphold. But we if instead we write

type Foo<'a> where Self: Bar<'a>;

which appears to be a very similar thing (except in this case the bound is on Self and not Self::Foo), this is now actually a bound that the user has to satisfy when instantiating Self::Foo.

Or am I reading the RFC wrong?

Are we now talking about current, actual behavior of the language or hypothetical, RFC'd behavior? In the stable language, my assertion holds.

Anyway, in that example, the difference is still not only colon-vs-where. type Foo: Bar means type Foo where Self::Foo: Bar (not yet valid syntax, not sure how the RFC would interpret it), which is distinct from type Foo where Self: Bar. The former constrains the associated type, while the latter constrains Self, so they are not equivalent not because you write a colon or where; they are different because the constraints are applied to different types.

1 Like

My original question was specifically about the where syntax for associated types, using which requires feature(generic_associated_types) (and so, nightly) even without any actual GATs.

Here's the part where I talk about this:

The way I think about these things is that bounds always describe the necessary conditions for something to exist. Bounds on a trait definition must be satisfied for the trait implementation to exist at all, and therefore user code can rely on it existing.

When a where clause appears on an item within a trait, it means that the implementor only needs to define the item in situations when the bound is satisfied, even if the rest of the trait is implemented. You see this most often on methods, like fn foo(self) where Self: Sized. This appears to also be the case for the proposed where clause on associated types: The type definition only exists when the bound is satisfied.

The confusing part is that colon bounds on an associated type (which are valid already today) act as bound on the entire trait definition, and not just the associated type declaration:

trait T { type Foo: Bar } 

is equivalent to

trait T where Self::Foo: Bar { type Foo; }

But the proposed

trait T { type Foo where Self: Bar; }

has no equivalent today.


I haven't read the RFC, but I strongly suspect this is equivalent to

trait Foo where for<'a> Self::Bar<'a>: Hash {
    type Bar<'a> where Self: 'a;
}

In other words, Foo::Bar<'a> must be defined whenever Self: 'a, and that definition must ensure that Foo::Bar<'a> unconditionally implements Hash.

2 Likes

First let me say that the phrasing in my original post linking to the RFC was incorrect. As @H2CO3 then explained a couple times, a bound on a type parameter is syntactic sugar for a where bound. Thus the distinction is not between Something: Trait and Something where Bound. Rather, it is between what is bound, or in the terminology I use below, what the bound is on. More concretely, these are the same:

// `Copy` bound on `T` is a `where` clause: must be satisfied upon use
trait Bar { Gat<T: Copy> }
trait Bar { Gat<T> where T: Copy }

In contrast with this:

// `Copy` bound on `Gat<T>` attaches to trait: implementer must satisfy
trait Foo { Gat<T>: Copy }

Where the bound is on the GAT itself.

This is what the RFC text says if you are aware of the syntactical sugar and read carefully enough. (And I'll correct my post above shortly.) However, for a clearer explanation than the RFC text (in my opinion), I suggest reading this RFC comment by Boats and Niko's follow-up.

In the rest of this (perhaps overly long) post, I walk through how things work today and connect it to my understanding of how it will work with GATs, in an attempt to find "a consistent mental model that would help [us] think about this". Here's a playground with the examples in case it's useful.


As @2e71828 said, in stable Rust today, you can already have a generic associated item -- namely, a generic function (or method). Let's take a closer look at how those work.

trait Foo where Self: Sized {
    // A bound attached to the function, not to the trait.
    fn foo<'a, A>(_a: &'a A) where A: Copy {}
    // Same thing as `foo`.  Still not a bound attached to the trait.
    fn bar<'a, A: Copy>(_a: &'a A) {}
}

The Copy bound is "a bound the user has to satisfy". The implementer can't satisfy it: A is an input parameter to the functions; the bound is attached to the functions, and is a bound on A. In contrast, the implementer can and must satisfy Self: Sized, which is a bound attached to the trait.

Here's another example with where clauses that are more general than inline bounds can express.

trait Bar {
    // A bound attached to the function, not the trait.
    fn foo<'a, A>(self, _a: &'a A) where Self: Sized {}
    // A different bound.  Still not a bound attached to the trait.
    fn bar<'a, A>(_a: &'a A) where Self: Copy {}
}

// `Self` is not bound to `Sized` or `Copy` at the trait level.
impl Bar for str {}

There is no error until you try something like <str as Bar>::bar(&0), so it's still "a bound the user has to satisfy". It's a bound attached to the generic fn, not the trait. This is true even though the bound is on Self, just like above, when the bound was on a type parameter, A.

(You can even do this, though it's arguably a bug. You can't call it.)
impl Bar for String {
    fn bar<'a, A>(_a: &'a A) /* where Self: Copy */ {
        println!("Oh really");
    }
}

So the mechanisms/obligations you find surprising in GATs already exist for generic trait fn today. Why do you find them surprising? Because the obligations appear reversed for associated types today -- because an associated type is the output of an implementation. The bounds on associated types can thus be considered bounds attached to the trait, something the implementer must satisfy.

trait Baz { type Quz: Copy; }
// Same thing, works today
trait Baz where <Self as Baz>::Quz: Copy { type Quz; }

Additionally, there are a couple things we can't do today (as far as I know):

  • Express an associated type bound that's not a bound on the type
    • E.g. you cannot put a where clause on an associated type
  • Put a bound directly on a trait function

That is, we have this situation today:

fn type
Bound on trait item n/a attaches to trait itself
Bound on something else attaches to trait item n/a

However, this RFC will fill in the lower right cell with "attaches to trait item", and bounds will be able to attach to the type constructors we call GATs. But bounds on the GAT itself will still attach to the trait.

(One could also argue that the upper-left cell is already filled with things like UnNameableFnItemType: Fn; that attach to the trait.)


So that is a way to think about it. Bounds on the output items -- a non-generic associated type today, or on the (entire) GAT in the future -- are bounds attached to the trait, bounds the implementer must satisfy. Bounds on other things must be satisfied upon use, when normalized. To me personally, this can be somewhat mind bending when the "other thing" is Self, but makes perfect sense when the "other thing" is an input parameter to the GAT (or generic function). It's impossible for the implementer to satisfy those.

I'm comfortable enough with fn foo() where Self: Sized though, so I'll probably just remind myself of that and get used to it over time. Additionally,

type Foo<'a> where Self: 'a

in particular is really a bound on the input parameter 'a; it just happens to be on the right of the :.


I agree with @2e71828's interpretation. (Yes, you can have both.)

Recursive bounds aren't supported, but as this is a bound on Spam<_> I'd expect it to be enforced upon use if it made sense somehow. I was/am actually unclear myself on some related indirect bounds:

// These are `where` clauses but (attempt to) apply to the output type;
// where does the bound attach to?
trait Foo {
    // Overflows
    type Bar<T> where <Self as Foo>::Bar<T>: Baz<T>;

    // error: only lifetime parameters can be used in this context
    // type Bar<T> where for<U> <Self as Foo>::Bar<U>: Baz<U>;

    // Overflows
    type Bar<'a> where <Self as Foo>::Bar<'a>: Baz<'a>;

    // Overflows, as do variations between `'a` and `'b`
    type Bar<'a> where for<'b> <Self as Foo>::Bar<'b>: Baz<'b>;
}

But suspect the answer is "it's moot because they don't make sense / such indirection is not allowed".

4 Likes

Thank you for the detailed reply!

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.