Why are trait methods with generic type parameters object-unsafe?

Question

To quote the Book (emphasis mine),

The same is true of generic type parameters that are filled in with concrete type parameters when the trait is used: the concrete types become part of the type that implements the trait. When the type is forgotten through the use of a trait object, there is no way to know what types to fill in the generic type parameters with.

I cannot understand the rationale. For a concrete example, consider the following

pub trait Echoer {
    fn echo<T>(&self, v: T) -> T;
}

pub struct Foo { }

impl Echoer for Foo {
    fn echo<T>(&self, v: T) -> T {
        println!("v = {}", v);
        return v;
    }
}

pub fn passthrough<T>(e: Box<dyn Echoer>, v: T) {
    return e.echo(v);
}

fn main() {
    let foo = Foo { };
    passthrough(foo, 42);
}

The result is, of course, an error

$ cargo run
   Compiling gui v0.1.0 (/tmp/gui)
error[E0038]: the trait `Echoer` cannot be made into an object
  --> src/main.rs:14:27
   |
14 | pub fn passthrough<T>(e: Box<dyn Echoer>, v: T) {
   |                           ^^^^^^^^^^^^^^^ `Echoer` cannot be made into an object
   |
   = help: consider moving `echo` to another trait
note: for a trait to be "object safe" it needs to allow building a vtable to allow the call to be resolvable dynamically; for more information visit <https://doc.rust-lang.org/reference/items/traits.html#object-safety>
  --> src/main.rs:2:8
   |
1  | pub trait Echoer {
   |           ------ this trait cannot be made into an object...
2  |     fn echo<T>(&self, v: T) -> T;
   |        ^^^^ ...because method `echo` has generic type parameters

error: aborting due to previous error

For more information about this error, try `rustc --explain E0038`.
error: could not compile `gui`

To learn more, run the command again with --verbose.

From my understanding, even though e forgets about its concrete type when being cast into a trait object, it can still infer that it needs to fill the generic type parameter of echo<T> with i32, since it's called inside passthrough<T>, which is monomorphized to passthrough<i32> at compile time.

What does "the concrete types become part of the type that implements the trait" mean? Why can't trait methods fill their generic type parameters at compile time, e.g. just call echo<i32>?

Warwick

Are you familiar with vtables and dynamic dispatch (which are how Rust implements trait objects)? – Fistulous

@Fistulous I'm not familiar with vtables, but I know Python and its duck typing mechanism, which I assume is conceptually close to dynamic dispatch. I mean, why can't vtables in trait objects (however they are implemented) store a pointer to a concrete method like echo<i32> (after compile time type inference)? – Warwick

Does this answer your question? Why does a generic method inside a trait require trait object to be sized? – Fistulous

echo can accept any T, so the vtable would have to potentially contain infinitely many possible functions, which isn't possible. Your code may only use i32, but that doesn't affect the generation of the vtable. – Fistulous

@Fistulous Thanks for the pointer. The linked question is related but doesn't fully answer my question. The accepted answer in that thread says a function/method cannot be both static- and dynamic- dispatched, but why not? At each invocation of a trait method, the concrete type is known at compile time, so the vtable only needs to store the pointers to "relevant" methods, e.g. Foo::echo<i32> and Bar::echo<i32>. (I'm assuming Rust generates a vtable for each invocation of passthrough, when concrete types are cast into trait objects) – Warwick

"cannot be both" I don't see that in there? "At each invocation of a trait method" That would require Rust to be fully aware of every callsite for a given trait object ahead of time, and to generate vtables based on the usage of the trait, rather than based on the trait definition itself. While maybe that's technically possible, that is not what Rust does, and that would preclude Rust from every distributing precompiled libraries that implement a trait of this form, since the vtable would be generated when the library was compiled, not when it was used. – Fistulous

@Fistulous Okay, that makes sense now! To clarify, you mean Rust generates a vtable for each implementation block such as impl Echoer for Boo/Bar/Baz, each vtable contains pointers to all trait methods (even though some are not called throughout the program), and is shared among all invocations of functions with an argument of Box<dyn Echoer>? – Warwick

@Fistulous Regarding "cannot be both" I don't see that in there?, the accepted answer says "These two models are incompatible: you can't have a function pointer which works with different types." – Warwick

Answer 1

This is similar to Why does a generic method inside a trait require trait object to be sized? but I'll spell out the details here.

Rust trait objects are fat pointers implemented using a vtable.

When Rust compiles code such as

pub fn passthrough<T>(e: Box<dyn Echoer>, v: T) {
    return e.echo(v);
}

it needs to decide what echo function to call. A Box is basically a pointer to value, and in the case of your code, a Foo will be stored on the heap, and a Box<Foo> would be a pointer to a Foo. If you then converted that into a Box<dyn Echoer>, the new Box actually contains two pointers, one to the Foo on the heap, and one to a vtable. This vtable is what allows Rust to know what to do when it sees the e.echo(v). The compiled output for your e.echo(v) call will look at the vtable to find the echo implementation for whatever type e points to, and then call it, in this case passing the Foo pointer for &self.

That part is easy in the case of a simple function, but the complexity and issues here comes in due to the <T> part of fn echo<T>(&self, v: T) -> T;. Template functions by their nature are aimed at declaring many functions using a single definition, but if a vtable is needed, what should it contain? If your trait contains a method that has a type parameter like <T>, where are an unknown number of T types that could be needed. That means Rust needs to either disallow vtables that reference functions with type parameters, or else it it needs to predict ahead of time every possible T type that could be needed, and include that in the vtable. Rust follows the first option and throws compiler errors like those you are seeing.

While knowing the full set of T types ahead of time may be possible in some cases, and may seem clear to a programmer working in a small codebase, it would be quite complicated and potentially make very large vtables in any non-trivial case. It would also require Rust to have full knowledge of your entire application in other to properly compile things. That could hugely slow down compile times, at a minimum.

Consider for instance that Rust generally compiles dependencies separately from your main code, and does not need to recompile your dependencies when you edit your own project's code. If you need to know all T types ahead of time to generate a vtable, you need to process all dependencies and all of your own code before deciding which T values are used and only then compile the function templates. Similarly, say that dependency contained code like the example in your question, every time you changed your own project, Rust would then have to check if your changes introduced a dynamic call to a function with a type parameter that wasn't used before, then it would also need to go recompile the dependency in order to create a new vtable with the newly referenced function as well.

At a minimum, it would introduce a ton of additional complexity.

Fistulous

At the risk of getting off-topic: The Book asserts that Trait objects must be object safe because once you’ve used a trait object, Rust no longer knows the concrete type that’s implementing that trait., but if a trait object still points to the original object in one of its two pointers, why can't I return self: Self from a trait method? – Warwick

Having a pointer to some memory is not the same as knowing specific information about the type of data being pointed at. vtables are a means of representing type-related data for use at runtime. In the case of returning Self, your call to echo() allocates space on the stack for the return value of the function, before the funciton is called, and that size is determined at compile time, not at run time. Variable size stack allocations are pretty rare, and having to look at a vtable to decide how much stack size to allocate would also be a lot of additional complexity, and slow things down. – Fistulous

Answer 2

trait object are basically a fat pointer that contain two pointers one point to the object and the other point to a vtable that contains all method, so calling a echo method from trait object is like

trait_object.vtable.echo(trait_object.obj, "hello")

imagine that echo can be generic, then when build vtable on the trait object, there might be echo_string, echo_uint, etc, all possible type must be enumerated. and when dispatch the method, it has to check the type of the argument and find the actual method from vtable, like

trait_object.vtable.echo_string(trait_object.obj, "hello")

there might be infinite combination of the method. and when dispatch method it should find the correct method from all the possible method from vtable based on the concrete type of T

Shama

At the risk of getting off-topic: The Book asserts that Trait objects must be object safe because once you’ve used a trait object, Rust no longer knows the concrete type that’s implementing that trait., but if a trait object still points to the original object in one of its two pointers, why can't I return self: Self from a trait method? – Warwick

@Warwick consider this situation you have a method on the trait object that return a new object which is type of Self, the return type of Self only mean the type is Self, but it can be another new object – Shama

Sorry, I don't follow: why is returning a value of type Self in a trait method disallowed, now that the trait object has a pointer to the original object (and thus the concrete type of Self)? – Warwick