Don't understand template trait ownership in example

I'm going through https://rust-book.cs.brown.edu and I'm having trouble understanding question 5 of Ownership Inventory #4. The question is:

Program 2:

/// Adds a Display-able object into a vector of 
/// Display trait objects
use std::fmt::Display;
fn add_displayable<T: Display>(
    v: &mut Vec<Box<dyn Display>>, 
    t: T
) {
    v.push(Box::new(t));
}

Normally if you try to compile this function, the compiler returns the following error:

error[E0310]: the parameter type `T` may not live long enough
 --> test.rs:6:12
  |
6 |     v.push(Box::new(t));
  |            ^^^^^^^^^^^

Assume that the compiler did NOT reject this function. Which (if any) of the following programs would (1) pass the compiler, and (2) possibly cause undefined behavior if executed? Check each program that satisfies both criteria, OR check "None of these programs" if none are satisfying.

And it says the answer is:

let mut v: Vec<Box<dyn Display>> = Vec::new();
{
    let n = 0;
    add_displayable(&mut v, &n);
}
println!("{}", v[0]);

I don't understand how this would pass the compiler though, since it is passing a reference as t, but the function says t: T, not t: &T. Shouldn't the function take ownership of t? Why are we allowed to pass a reference?

A type variable can stand in for any type. <T> means "any type", not "any type except references".

Just like in algebra, you can denote integers as eg. k and even numbers as 2k. However, this doesn't mean that k can only be an odd number.

5 Likes

The question is terrible "Assume that the compiler did NOT reject this function."
Assume that pigs can fly.

My first though is it is suggesting replace the functions body; do so and all pass compile.
Second thought, lets add to T: 'static. No the answer you post is the one that fails.
So my assumption is their after some inverse. The static case's fail to fly but reference passes and allow undefined behaviour.

OP question is a bit simpler. which @H2C03 answers but might confuse as on the function it is restricted to Display so not every(/any). In such case you look at the documentation to see if the type implements Display.

Well, you have to ask this kind of question if you want to understand why it's not actually accepted in reality.

dyn Trait without any other hint as to the contained lifetime is implicitly dyn Trait + 'static, so if passing a non-'static reference were accepted, it would allow extending an arbitrary lifetime, ultimately leading to unsoundness.

I agree the question is poorly contrived or at least poorly worded. (How am I supposed to check that the code snippets pass some imaginary version of the compiler?) I didn't sign up to see the full context, but assume the real point of the exercise (if not necessarily your direct question) is analogous to one of...


Why doesn't this compile?

fn add_str<'t>(
    v: &mut Vec<&'static str>,
    t: &'t str,
) {
    v.push(t)
}
// argument requires that `'t` must outlive `'static`

And the answer is that the Vec requires &'static str which are valid anywhere (are not a short-term borrow), where as &'t str can be a short term value. It prevents

let mut v: Vec<&'static str> = Vec::new();
{
    let n = "Hello".to_string();
    add_str(&mut v, &*n);
}
println!("{}", v[0]); // Use after free

And by the way, the above snippet is effectively the same as this:

//              V no `'static` lifetime annotation
let mut v: Vec<&str> = Vec::new();
{
    let n = "Hello".to_string();
    add_str(&mut v, &*n);
}
println!("{}", v[0]); // Use after free

Because passing v to add_str is only possible if the elided lifetime annotation is 'static.

All of the above is basically a lifetime-generic version of the type-generic original question.


A follow up question is, why does Vec<Box<dyn Display>> require its contents to be valid everywhere (not contain any short-term borrows), and/or why does the generic T not meet this requirement?

A Box<dyn Display> annotation outside of a function body[1] is actually a Box<dyn Display + 'static>. dyn Traits always have a lifetime parameter, like references do; you can not type it a lot of the time, but it's always there. A dyn Trait + 't is similar to a &'t SomeType in that it's not valid everywhere; it's only valid within some region tracked by that lifetime.

It has to be this way in order to soundly type erase (coerce to dyn Trait + '_) things that are or contain short-term borrows.

So if you want to type-erase and put something in a Box<dyn Display /* + 'static */>, it must also support a 'static bound -- in generic terms, T: 'static. add_displayable doesn't have this bound on T, so it would be unsound to allow the coercion from T to Box<dyn Display + 'static>.


Finally, a possible confusion is -- why doesn't the T implicitly satisfy a 'static bound? Isn't it an "owned type" that's valid everywhere?

And as @H2CO3 has already covered, it is not -- T can be any type including references. Your misconception is a common one, however.

Incidentally, reference aren't the only types that don't satisfy a 'static bound. We already talked about another, actually -- dyn Trait + 't[2] where 't is not 'static. But there are Cow<'_, B>, Ref<'_, T>, and so on -- and these aren't magical compiler types either, you can easily build your own.

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

A generic T could be any of these, as well.


  1. like in the signature of add_displayable ↩︎

  2. and Box<dyn Trait + 't> ↩︎

2 Likes

A type variable can stand in for any type. <T> means "any type", not "any type except references".

But then we don't know whether the function takes ownership at compile time? How does that work, I thought the ownership stuff happens at compile time, doesn't the compiler need to know whether it takes ownership? Or are trait template arguments always references?

Also what if I want to take ownership of it. Would I have to use Box<dyn Display>?

Edit: Actually no, Box<dyn Display> wouldn't take ownership either then... so how would I take ownership of a trait argument?

But then we don't know whether the function takes ownership at compile time?

A function always takes ownership of its argument(s). If some argument is a reference, then the function takes ownership of the reference — not the referent of the reference, whose ownership is unchanged.

3 Likes

T may represent a type with ownership, it may represent &T, or it may represent &mut T. These three are included in each other.

The syntactic construct you're looking for is <T: 'static>. That is how you say "any type except references, except those that live forever". Box<dyn Display> being short for Box<dyn Display + 'static> is aforementioned, and it's a similar thing.

Even though <T> is a value of "any type" that may or may not contain a reference, this doesn't pose problems to the compiler. The caller chooses what type they pass into a generic function. Thus, on any individual call-site, the compiler knows whether it passed an owned value, and it can check if the following code is trying to use a moved value.

There's some conflation going on with the terminology from another language, and I'm not sure where it's coming from (your own experience or the guide you're working through).

Rust has generics, not templates. Things like T are generic type parameters, not template arguments.

Type parameters are not always references either. And what a reference is in Rust may not correspond to what references are in other languages, as well. Rust references are fully realized types that are somewhat like C pointers with more guarantees (non-null, always point at a valid value, compile-time borrow checking...)

So maybe T = String, or maybe T = &String. Both can happen and they're not the same thing, because String and &String are not the same type.

Also take care not to conflate the liveness scope of values with the Rust terminology around "lifetimes". The T: 'static bound means "T doesn't have any (non-'static) borrows." It does not mean "values of type T are never dropped."

String: 'static for example, but Strings get drop and deallocate their memory, etc.

Types can also not satisfy a 'static bound but still have destructors that run when dropped.


The term "owned type" can be confusing because it is sometimes meant as "a type that satisfies a 'static bound", or sometimes even just "not a reference". But "ownership" is also used to mean "you're responsible for dropping the object"; a type "owning" another can mean the other type is a field of the "owning type", and so on.

It's hard to talk about what takes ownership and what owns what without some agreement on the terms being used. I'm going to use the concept of "those responsible for dropping are the owners".

Let's consider a concrete example:

fn foo<'g>(guard: MutexGuard<'g, String>) {}

What does foo "take ownership" of? Unless it passes it somewhere else, it takes ownership of the MutexGuard. At the end of foo, the guard will be dropped which will release a lock on the borrowed Mutex. But note that the MutexGuard doesn't satisfy a 'static bound -- it contains a borrow of the underlying Mutex, which is how it is able to unlock it when dropped.

No ownership of a Mutex or String was passed, though.

Where things drop is tracked at compile time to some extent, but it's an undecidable problem generally, so there are also some runtime flags.

fn foo<'g>(guard: MutexGuard<'g, String>) {
    if some_runtime_condition(&guard) {
       drop(guard);
    }
    do_a_bunch_of_other_stuff();
    // `guard` will drop here... unless it was already dropped above
}

In contrast, lifetimes are used for compile time analysis only, and don't change how code compiles (just what code can compile).


How about here?

fn bar<'s>(s: &'s mut String) {}

bar wasn't passed ownship of a String, but it was passed ownership of a &mut String. Dropping an exclusive reference is a no-op however, and references (shared (&) or exclusive (&mut)) are the foundation of borrowing things in Rust, so it wouldn't be surprising for someone to say "bar doesn't take ownership". Implicit in that phrasing is that the String is the important part, and that it's not important that bar takes ownership of a &mut String.

But it can be a bit fuzzier with generics. Consider here:

fn takes_t<T>(t: T) {}
fn takes_ref_to_t<T>(t: &T) {}

We could say "takes_t takes ownership (of T) and takes_ref_to_t doesn't take ownership (of T)". But it's still the case that takes_ref_to_t "takes ownership of a &T".

...and then if we make some calls like so...

let s = String::new();
takes_t(&s);
takes_t(s);

In the first call, we have T = &String, and takes_t takes ownership of the &String (but not a String).

In the second call, we have T = String and takes_t takes ownership of the String.


A Box has exclusive ownership of what is inside, so if you coerce something into a Box<dyn Display> by putting it in a Box and type erasing it, the Box will own the dyn Display (which is the type-erased version of the original value). When the Box drops, it will drop the dyn Display, which will recursively drop the type-erased value.[1]

This is true for a Box<dyn Display + 'static> but also for any other lifetime. It's true for values you erase that have destructors, but also true for those which do not, like references.

You can create a Box<dyn Display + 'static by boxing up a String, and dropping the Box will drop the String, for example.

Or you can create a Box<dyn Display + '_> by boxing up a &String and dropping the Box will drop the &String -- which a no-op, but that's fine.


  1. The vtables of all dyn Trait include an entry for the erased type's destructor. ↩︎

3 Likes

Ah yeah I meant generics. I must be confusing it with C++

So if I want to take ownership then I should do dyn Display + 'static

No, the lifetime doesn't matter with regard to ownership. Do dyn Display + 'static if you can't or don't want to deal with short-lived borrows.

2 Likes

It takes ownership of whatever you pass. If you pass a reference, then it takes ownership of the reference.

References are not magic or special in this sense. They are a regular, first-class parametric type, just like an array or a Vec or a HashMap. A reference is a type constructor, so for any type U there's a corresponding type &U [1] that you obtain by taking the address of a place of type U – as simple as that. Types are treated uniformly by the compiler, and you can move values of any type, references included.

There is no "passing by reference" in Rust as a separate concept, because it's unnecessary. There is only "passing by value", and you can pass anything by value, including references.

Just like it doesn't make sense to ask how the compiler knows whether you are "passing by vector" when T = Vec<U>, it doesn't make sense to ask how the compiler knows that you are "passing by reference" when T = &U. It doesn't know, and that's the whole point. The compiler makes you write generic code in a way that your function remains correct, no matter what type you substitute for the type parameters. This is the very reason why the compiler (and you) need to worry about lifetimes – they have to be constrained and taken into account, just in case the type variable gets substituted by a type that has a lifetime (eg. a reference or a wrapper around a reference).

No, of course not. If your argument has type T, and you pass a value of type U, then the generic gets instantiated with T = U. No magic, no hidden references, no nothing. This language is simple and logical by design.

No, this is moot in the light of the above explanation. Just accept a T. No need for dynamic dispatch or boxing whatsoever.

Yes it would. Box owns its referent. It looks like you are confusing ownership with indirection.


  1. Actually, it's a family of types, because you also need to take lifetimes into account – strictly speaking, &U is still not a type but a type constructor, only &'lt U for some lifetime 'lt is a type.) ↩︎

4 Likes

No, to be 100% clear: it is not possible to use generics for restricting to a set of types that is "anything except references". If that's what you are trying to do, then you are holding it wrong. Instead of worrying about what specific types your generics will be used with, you should write them in a way that it doesn't matter. I mean, they are called generics and not specifics for a reason…

2 Likes

What a great question and discussion! I consider myself an experienced Rust developer, and still find great information in this forum. As a consequence of some limited previous experience with C++ and Java, when talking about generics, borrowing and traits in general my mind has tended to go towards familiar terms like "interface", "abstract class", "references", "templates" Found some very nice clarifying explanations here.

I wanted to ask a follow up question on how exactly the for <'a> falls into all of these definitions. Let me list a few:


trait SomeTrait<'s> {
}

fn run_1<A>(item: A) 
    where
    // type A such that it implements SomeTrait for any lifetime 's
    A: for<'s> SomeTrait<'s>
{
}
fn run_2<A>(item: A) 
    where
    // I am not super clear on the difference in scope.
    // I know that I can still add the A: 's constraint
    // and since I didn't, what does this change from above?
    for<'s> A: SomeTrait<'s>
{
}
fn run_3<A>(item: A) 
    where
    // what is the correct way to interpret this?
    for<'s> A: SomeTrait<'s> + 's
{
}

My recommendation: considering this is an experiment (that is very cool, by the way), I recommend you place a bug comment in the quiz in question, as recommended in the very start of the experiment introduction, giving a reference to this forum question in the comment.

A: for<'s> SomeTrait<'s>,
for<'s> A: SomeTrait<'s>,

These are entirely equivalent; however, if A was instead SomeType<'s, A> then you'd need to put the for<'s> before it: for<'s> SomeType<'s, A>: SomeTrait<'s>. Think of it exactly like a regular variable, which you must declare before you use, but can declare further back than that:

foo();
let s = 1;
bar(s);

// is the same as
let s = 1;
foo();
bar(s);

// but this would be an error
foo(s);
let s = 1;
bar(s);

    // what is the correct way to interpret this?
    for<'s> A: SomeTrait<'s> + 's

We can skip the SomeTrait part and just read for<'s> A: 's. In general, T: 'lt is an “outlives” bound; it means that values of the type T won't be invalidated by dangling references until 'lt ends, so an owner of a T can hold onto it until at least the end of 'lt, but not longer.

In this case, since we're saying A is valid for all lifetimes, that works out to being equivalent to the longest lifetime: A: 'static, which can be understood to mean “values of type A contain no non-'static references” (or more precisely, the type A contains no non-'static lifetimes; it's possible to have a lifetime but no actual references).

1 Like

Oh hey, you've hit on one of the parts of the reference which has annoyed me for years! :sweat_smile:

Higher-ranked lifetimes may also be specified just before the trait: the only difference is the scope of the lifetime parameter, which extends only to the end of the following trait instead of the whole bound. This function is equivalent to the last one.

Thanks a lot! But how about an example that illustrates the difference, huh?


Anyway, I guess I've built enough experience to actually understand and explain what that means since last time I read it.

// This compiles
fn foo<F>()
where
    for<'a> F: 'a + Fn(&'a str) + AsRef<&'a i32>
    //         ^^ also `for<'a> 'a + ...` is not allowed for some reason
{}

// This does not, because `'a` is out of scope after the `Fn(...) bound
fn bar<F>()
where
    F: for<'a> Fn(&'a str) + AsRef<&'a i32>
{}

// Similarly does not compile
fn quz<F>()
where
    F: for<'a> Fn(&'a str) + 'a,
{}