What does it mean to implement Trait for Trait?

[Jarvi-Izana]

overview

The discussion involves:

• impl Trait for Trait
• Trait (type) vs dyn Trait (trait object type) vs &dyn Trait (trait object)

question

I read this related answer for implement trait for trait but I'm still confused.

1. How do you interpret impl B for dyn A {}?

    trait A {
        fn method_a(&self) {
            println!("a");
        }
    }
    
    trait B {
        fn method_b(&self) {
            println!("b")
        }
    }
    
    impl B for dyn A {}
    
    impl A for i32 {}
    
    fn main() {
        let x: &dyn A = &10;
        x.method_b();
    }
   

   Playground

   I can understand impl A for i32 {} because i32 is a concrete type. dyn A is not a concrete type (unsized, can't pass by value), and you cannot declare a dyn A but you can only declare a &dyn A. Should I interpret

    // x.method_b();
    (*x).method_b();
   

   as *x is dyn A? *x is the invalid syntax to get dyn A, isn't it?

2. I can also declare impl B for &dyn A {}, so why I need impl B for dyn A {}? What's the use case?

3. Follow up: If I modify the code

    fn main() {
        let x: &dyn A = &10;
        // have a B trait object over dyn A since
        // dyn A implements B
        let y: &dyn B = x;  
    }
   

   It will fail and complain &dyn A is not &dyn B. I understand this is a reasonable complaint but I provide the option for compiler to use impl B for dyn A {}. Apparently, the compiler doesn't consider that's an option.

Originally posted in StackOverflow. I think it's better to post it here since it has more active Rustaceans here.

solution

the second part of the solution!

What does it mean to implement Trait for Trait?

dyn Foo is, as you said, a transient thing - it doesn't really exist by itself. It's a non-Sized value which stores part of itself in whatever its being stored behind. In my mental model, I think of dyn Foo as the data half of the trait object + an obligation on whatever is storing it. The first part of dyn Foo is thing at the end of the *mut () in the code you posted. The second is an abstract concept of "whatever is storing me stores a vtable too". Yes, it pattern matches first. However af…

Thanks @daboross! Fantastic and excellent answer!!!!

[daboross]

@Jarvi-Izana

I can understand impl A for i32 {} because i32 is a concrete type. dyn A is not a concrete type (unsized, can't pass by value), and you cannot declare a dyn A but you can only declare a &dyn A . Should I interpret

 // x.method_b();
 (*x).method_b();

as *x is dyn A ?

Yes, this is what's happening.

@Jarvi-Izana

*x is the invalid syntax to get dyn A , isn't it?

Note that this isn't invalid syntax. If you write

    (*x).method_b();

It works fine, and has identical behavior to your code.

@Jarvi-Izana

I can also declare impl B for &dyn A {} , so why I need impl B for dyn A {} ? What's the use case?

If you impl for dyn A, then it also counts for other types which dereference into dyn A, such as Box<dyn A>, Arc<dyn A>, &mut dyn A, etc.

If you implement it for &dyn A, then you'll get an implementation for &dyn A, but not any of the others.

@Jarvi-Izana

I understand this is a reasonable complaint but I provide the option for compiler to use impl B for dyn A {} . Apparently, the compiler doesn't consider that's an option.

This fails because only Sized things can be cast to dyn Trait. This is a limitation, but one which requires a bit of background knowledge to understand.

The limitation stems from rust's implementation of &dyn Trait. Specifically, to use a dyn Trait value, you need two pieces of information: where the data is, and what vtable the trait uses. The data is just the data for whatever is implementing Trait. The vtable is what the compiler uses to find the method implementations: the vtable is essentially a big array of pointers to one function for each of the trait's methods.

In rust, these two pieces of data are stored in fat pointers. Whereas &i32 is 64 bits and just contains a pointer to the i32 data, &dyn Trait is 128 bits and contains two pointers: one to the data (of whatever was cast into this pointer), and the other to the trait's vtable. dyn Trait itself is just the data behind the trait - it's only have the data. The other half gets stuck into whatever the dyn Trait is behind. This is the same as other unsized things, such as [T] slices, which stick their length into whatever pointer they're behind.

When you try to cast &dyn A into &dyn B, the compiler runs into a problem: in order to run the methods for impl B for dyn A, it needs a dyn A value. So it needs to have the vtable for A somewhere, as well as the data. But where can it store that data?

&dyn B is already a fat pointer: the extra 64 bits stores the vtable for impl B for dyn A. There's nowhere in there to stick the vtable for impl A for i32. This is why the cast is disallowed.

I don't know of any good beginner material which covers this (if anyone knows of some, I'd love to hear it!). However, the nomicon has a chapter with some more details: Exotically Sized Types - The Rustonomicon

[Jarvi-Izana]

Much appreciated for the detailed answer! Supper great!

@daboross

Yes, this is what's happening.

@Jarvi-Izana

*x is the invalid syntax to get dyn A , isn't it?

Note that this isn't invalid syntax. If you write

    (*x).method_b();

It works fine, and has identical behavior to your code.

Do you mean dyn A is transient and it's only known to the compiler?

let y = *x;

is invalid but &*x is valid?

[daboross]

Sure! Yeah, I think that's a good way to put it.

In some ways it does exist, like dyn A is really a thing inside Box<dyn A> and &dyn A. It is a type. But it can't exist by itself on the stack.

Worth noting that this restriction might be lifted in the future if/when unsized locals are implemented & stabilized.

[Jarvi-Izana]

@daboross

In rust, these two pieces of data are stored in fat pointers. Whereas &i32 is 64 bits and just contains a pointer to the i32 data, &dyn Trait is 128 bits and contains two pointers: one to the data (of whatever was cast into this pointer), and the other to the trait's vtable. dyn Trait itself is just the data behind the trait - it only has the data. The other half gets stuck into whatever the dyn Trait is behind. This is the same as other unsized things, such as [T] slices, which stick their length into whatever pointer they're behind.

Follow this model, cited from here.

// for example, the vtables for i32 and Vec<i32>
static VTABLE_FOO_FOR_I32: VTableFoo = VTableFoo { ... };

pub struct TraitObjectFoo {
    data: *mut (),
    vtable_ptr: &VTableFoo,
}

// let x: &dyn Foo = &10;
let x = TraitObjectFoo{ &10, &Vtable..}; 

1. if I understand correctly &dyn Foo is the real fat pointer, then what about dyn Foo?

Back to our example:

fn main() {
     // let x: &dyn A = &10;
     let x = TraitObjectA{ &10, &VTableAForI32 };
     // have a B trait object over dyn A since
     // dyn A implements B
     let y: &dyn B = x;
 }

2. what happens to let y: &dyn B = x;? Does it first do pattern match? &dynB match with type &dyn A, and then the compiler checks whether dyn B is implemented for dyn A (find whether the vtable is existent)?

if so, I think you are right!! Follow the above model, it should be

// let y: &dyn B = x;
// pattern match: remove the &dyn: B matches with A 
// assigning a pointer to a fat pointer which is not allowed.
y.data = x; // &dyn A
y.vtable = &VTableBForDynA;

In this way, &dyn B must construct from sized data. Not sure if my understanding is correct.

[daboross]

@Jarvi-Izana

if I understand correctly &dyn Foo is the real fat pointer, then what about dyn Foo ?

dyn Foo is, as you said, a transient thing - it doesn't really exist by itself. It's a non-Sized value which stores part of itself in whatever its being stored behind.

In my mental model, I think of dyn Foo as the data half of the trait object + an obligation on whatever is storing it. The first part of dyn Foo is thing at the end of the *mut () in the code you posted. The second is an abstract concept of "whatever is storing me stores a vtable too".

@Jarvi-Izana

what happens to let y: &dyn B = x; ? Does it first do pattern match ? &dynB match with type &dyn A , and then the compiler checks whether dyn B is implemented for dyn A (find whether the vtable is existent)?

Yes, it pattern matches first. However after that, I would change two things.

First, it won't match the dyn on both sides, because A isn't a type. It'll only do pattern matching up to types, so it will match the & on the left and the right, but then it ends up with dyn B on the left and dyn A on the right.

I say this because pattern matching the dyn away wouldn't really mean anything. A is a trait, not a type - dyn A has values, but A only has a set of types which implement it. When matching the left and right hand side, the compiler is thinking of types and values, and thus it'll only unwrap to dyn A (and dyn B). A and B only exists as types with the dyn.

Second, I would use a different word for the next part. After it finds dyn B on the left and something of type dyn A on the right, it checks whether dyn A can be coerced into dyn A.

I'm being a bit pedantic: in practice, checking for coercion into a dyn Trait does check whether the right hand side implements that trait. But it also checks other things to ensure the coercion can happen, such as the right-hand-side being Sized.

The other reason I'd say it checks for coercion is that there are other things, besides casting into a dyn Trait, which the coercion check enables. For instance, this piece of code works on the same basis:

let owned = String::from("hi");
let a: &String = &owned;
let b: &str = &a;

String doesn't somehow implements str, but rather that String can coerce into str, the same way i32 can coerce into dyn A. In this case, the coercion is done through deref coercions.

@Jarvi-Izana

In this way, &dyn B must construct from sized data. Not sure if my understanding is correct.

I think you're definitely on the right track! You've got the end result down, I think there are just a few things in the middle where the compiler works slightly differently from what you've said.

[Jarvi-Izana]

Fantastic on the coercion part! Much appreciated! You should definitely post you answer to SO to let more people learn from your clear answer!

@daboross

dyn Foo is, as you said, a transient thing - it doesn't really exist by itself. It's a non- Sized value which stores part of itself in whatever its being stored behind.

In my mental model, I think of dyn Foo as the data half of the trait object + an obligation on whatever is storing it. The first part of dyn Foo is thing at the end of the *mut () in the code you posted. The second is an abstract concept of "whatever is storing me stores a vtable too".

I want to have a further discussion around dyn Foo and &dyn Foo. In this answer, dyn Foo is called Trait type (not a real thing) and &dyn Foo is a fat pointer, backed by some materializable data structure. It seems a little bit of conflict with yours.

---

update:

I think dyn Foo probably has no memory model.

there's no such a thing to dereference a fat pointer, e.g., no meaning for *&dyn Foo.

[daboross]

@Jarvi-Izana

Fantastic on the coercion part! Much appreciated! You should definitely post you answer to SO to let more people learn from your clear answer!

Thanks! If I have time, I'll try to stick something coherent together.

In general, I usually stick to forums since it's easier to answer. I find that on stackexchange, an answer is expected to address all people who might ask the same general question, and that requires a bit more thought & editing. But on the forums, I can pay more attention to peoples' particular backgrounds. Writing a targeted answer which includes only necessary details is easier than something fully thought out which anyone can read and understand

@Jarvi-Izana

I want to have a further discussion around dyn Foo and &dyn Foo . In this answer, dyn Foo is called Trait type (not a real thing) and &dyn Foo is a fat pointer, backed by some materializable data structure. It seems a little bit of conflict with yours.

I think if you look at it the same way, they should be in sync?

In particular, I didn't find "Trait type" in the answer. But they did talk about "trait object type"s.

The proper name for dyn Trait is a trait object, and since it is a type, I think dyn Trait could definitely be called a trait object type.

Earlier, I said that Trait isn't a type. But the dyn here is key: dyn Trait is a type, and so calling it a trait object type is accurate. The distinction is that Trait itself isn't a type, but dyn Trait is one.

Separately, it's true that Trait in type position used to be the syntax for dyn Trait. But as this was deprecated in Rust 2018 edition, I'd chose to just disregard that syntax entirely.

@Jarvi-Izana

I think dyn Foo probably has no memory model.

there's no such a thing to dereference a fat pointer, e.g., no meaning for *&dyn Foo .

This is probably fair!

Though perhaps interestingly, you can dereference fat pointers, you just have to immediately re-reference them

For instance, in this code:

let y: &dyn A = &*x;

Or, perhaps more usefully,

let x: Box<dyn std::fmt::Display> = Box::new("hi!");
let y: &dyn std::fmt::Display = &*x;

It's just that the dereference always has to be re-referenced, and compiler magic connects the two.

[alice]

There was also a discussion on this on reddit.

[daboross]

Interesting!

It feels like there have been a lot of discussions recently about trait objects and the limitations of unsized types in these forums. I guess that's been happening on reddit's /r/rust as well?

I wonder if it'd be possible to add more content to the book or reference which could preemptive clear things up, or at least gather more knowledge together. There are some good resources, like the The Sized Trait | Huon on the internet series, Dynamically Sized Types - The Rust Reference, and Using Trait Objects That Allow for Values of Different Types - The Rust Programming Language, but the only one which fully covers trait objects is from before the dyn Trait syntax was introduced, and all the others are non-comprehensive.

[Jarvi-Izana]

diverge

@daboross

In general, I usually stick to forums since it's easier to answer. I find that on stackexchange, an answer is expected to address all people who might ask the same general question, and that requires a bit more thought & editing. But on the forums, I can pay more attention to peoples' particular backgrounds. Writing a targeted answer which includes only necessary details is easier than something fully thought out which anyone can read and understand

That's really considerate! Thanks! Well, I think the reason to post in SO to raise more visibility is that SO seems to have a better SEO than Rust forum. When I search rust related questions, SO's results pop at the very front of the search, in most cases.

---

back to the discussion

@daboross

@Jarvi-Izana

I think dyn Foo probably has no memory model.

there's no such a thing to dereference a fat pointer, e.g., no meaning for *&dyn Foo .

This is probably fair!

Though perhaps interestingly, you can dereference fat pointers, you just have to immediately re-reference them

It's just that the dereference always has to be re-referenced, and compiler magic connects the two.

I'm thinking about this. I think I have a strong stereotype from C/C++ that every type must comply with

1. not only defines the properties (from OOP)
2. but also defines how the compiler should store it in memory, i.e.,. sized.

When you use type, it's a matter of whether you can use it to declare value (not reference or pointer) or not (abstract or pure virtual). But abstract class still has a clear memory size (point 2) from compiler perspective. The greatest example is C++ incomplete type,

struct Node {
     Node m_node; // recursive declare, infinite size
    // Node* m_node; // makes compiler happy. size_of Node is 8 bytes on 64bits
};

But for Rust, it's a different concept. A type doesn't have to obey all of above 2 requirements.

A type can have 1, 2 at the same time (sized), or only 1 without 2 being satisfied (unsized).

@daboross

dyn Foo is, as you said, a transient thing - it doesn't really exist by itself. It's a non- Sized value which stores part of itself in whatever its being stored behind.

In my mental model, I think of dyn Foo as the data half of the trait object + an obligation on whatever is storing it. The first part of dyn Foo is thing at the end of the *mut () in the code you posted. The second is an abstract concept of "whatever is storing me stores a vtable too".

Now I understand what you mentioned earlier. dyn Foo is an API obligation (protocol) not the storage schema.

dyn Foo can be viewed as *&dyn Foo, further [*data, *vtable], which refers to an object of Sized type that can be stored in memory (meet requirement 1 and 2) + the vtable object (also stored in memory). But you don't what's the sized type object. Therefore, it's unsized.

I think it's better for Rust to clarify the type can be sized (1, 2) or unsized (1). Probably DST already mentions it but that's confusing because people may think DST under the old C/C++ type model.

[Jarvi-Izana]

@alice

There was also a discussion on this on reddit .

Wow! I posted it there . Because I infer the layout of fat pointer from assembly code (here is the link if interested).

    // let foo = test_dyn_ret(&y);
    call    example::test_dyn_ret
    mov     qword ptr [rsp + 16], rax // vpointer in caller stack
    mov     qword ptr [rsp + 8], rdx  // self in caller stack

But I can't find the source code for dyn Foo. I'm curious about how dyn Foo or trait object type is implemented. My guess is similar to trait tag in C++, that dyn Trait will be tagged as ?Sized and the compiler will check that thing.

struct sized_tag {};
struct unsized_tag: sized_tag {};

struct a_sized_type {
      typedef sized_tag size_category;
}

template<class T>
void do_check(T&& a) {
      do_some_check(a, a::size_category());
}

template<class T>
void do_some_check(T&& a, sized_tag);

template<class T>
void do_some_check(T&& a, unsized_tag);

Probably it's better to start a new question to discuss this.