Support subtyping where coercion is a no-op?

I wonder if trait upcasting from &dyn (A + B) to &dyn A is a no-op? (Edit: where B is a marker trait, otherwise it's not currently supported)

Maybe the real question should be: Is trait upcasting from &dyn C to &dyn A (where C: A + B) a no-op? (But not for upcasting to &dyn B)

If so, can we make dyn C a subtype of dyn A so that we can, for example, directly assign a variable of type [&dyn C] to a variable of type [&dyn A], among other coercions that are made possible?

(Same goes for dyn (A + B) and dyn A where B is a marker trait)

First of all, we don't support &dyn (A + B) where neither A or B is marker trait. So I will assume you meant &dyn C where trait C: A + B {} instead.

No, it's not guaranteed no-op. It's unspecified. And I think we definitely don't want to discriminate A + B and B + A.

Ah, I missed it. I've updated the original post.

&dyn C I suppose?

Is it worth it to specify it and introduce subtyping relationship between them?

Otherwise people might still want to use unsafe transmute to avoid explicit conversions which might not be optimized away, thus relying on unspecified compiler implementation details.

Or they might have to create there own vtable implementations like in anyhow::Error and bytes::Bytes (though in these two cases, adding a simple rule might not cover all the use cases).

I'd like to think of it in this way:

C++ has multiple inheritance. Languages like Java / C# abandoned multiple inheritance, but supported single class inheritance and multiple interface implementation.

The Java / C# guys think inheritance can be useful, but multiple inheritance introduce too much of a mess. So they "discriminated" what could be modeled as multiple base classes, and make those base types interfaces, leaving one class to have the "base class privilege".

So the question would be: Is subtyping relationship between dyn trait objects useful enough in Rust? If so, we might still give the first supertrait some privilege since we can't make all supertraits equal if we want zero (run-time) cost.

I know rustaceans generally prefer static dispatch because of superior performance (more optimization opportunities), and that's what makes Rust shine.

But software design can still make use of the type erasure (dynamic dispatch) approach. Subtyping between trait object types enables polymorphism without needing to write generic-aware code. Performance would be lower, but it makes the design more flexible handling different concrete types.

Personally I think we should improve the experience of developing software models with runtime polymorphism. Currently without variance powered by subtyping, dynamic dispatching in Rust is mostly just used when we explicitly want to handle different concrete types implementing the same trait, but we don't get the convenience of a generic-polymorphism[1] mixture provided via subtyping & variance in languages like C#.


A demo I wrote long ago to show the mess:

Without dyn trait upcasting (Rust Playground):

fn main() {
    let mut pointer_to_f_parent: fn(_) -> _ = f_parent;
    const pointer_to_f_child: fn(Box<dyn Animal>) -> Box<dyn Animal> = f_child;
    pointer_to_f_parent = |v| pointer_to_f_child(v.into());
    // pointer_to_f_parent = pointer_to_f_child;   // illegal
}

fn f_child(v: Box<dyn Animal>) -> Box<dyn Animal> {
    unimplemented!()
}

fn f_parent(v: Box<dyn Cat>) -> Box<dyn Animal> {
    unimplemented!()
}

trait Animal: IntoBoxedAnimal {
    fn f1(&self) {}
}

trait IntoBoxedAnimal {
    fn into_boxed_animal(self: Box<Self>) -> Box<dyn Animal>;
}

impl<T: Animal + 'static> IntoBoxedAnimal for T {
    fn into_boxed_animal(self: Box<Self>) -> Box<dyn Animal> {
        self
    }
}

trait Cat: Animal {
    fn f2(&self) {}
}

struct S;

impl Animal for S {}

impl Cat for S {}

impl From<Box<dyn Cat>> for Box<dyn Animal> {
    fn from(cat: Box<dyn Cat>) -> Self {
        cat.into_boxed_animal()
    }
}

With dyn trait upcasting, but without subtyping (Rust Playground):

fn main() {
    let _: Box<dyn Animal> = Box::new(S) as Box<dyn Cat>;

    let mut pointer_to_f_parent: fn(_) -> _ = f_parent;
    const pointer_to_f_child: fn(Box<dyn Animal>) -> Box<dyn Animal> = f_child;
    pointer_to_f_parent = |v| pointer_to_f_child(v);
    // pointer_to_f_parent = pointer_to_f_child;   // illegal
}

fn f_child(v: Box<dyn Animal>) -> Box<dyn Animal> {
    v
}

fn f_parent(v: Box<dyn Cat>) -> Box<dyn Animal> {
    v
}

trait Animal {
    fn f1(&self) {}
}

trait Cat: Animal {
    fn f2(&self) {}
}

struct S;

impl Animal for S {}

impl Cat for S {}

  1. I know we can use something like dyn AsRef<dyn A> / dyn AsMut<dyn A>, but that's limited to borrowing the supertrait object. If we want to gain ownership, things would become really awful because of so many smart pointer types out there, and that's where we really need covariance. ↩ī¸Ž

As I understand it, most of the runtime cost of multiple inheritance in C++ is thunking calls to adjust the self pointer after accessing the vtable through it. Since Rust has fat pointers, it doesn't need this fix, and every other adjustment would be a fixed vtable adjustment on converting to a subtrait of it wasn't first in the vtable, if Rust supported it.

In other words, I'm guessing it's more type system /other languages design issues than performance stopping Rust supporting multiple traits?

2 Likes

Rust dyn trait objects are fat pointers, but with C: A + B, you cannot make both upcasting from &dyn C to &dyn A and upcasting from &dyn C to &dyn B no-ops - the metadata part of &dyn A and &dyn B must point to different locations in the vtable since A and B are not supertraits to each other.

And I'm not bringing up multiple inheritance in C++ as a technical reference. I'm just saying "what was thought to be equal and not to be discriminated might not be treated equally after all, as we have to compromise things for some principles (no multiple inherited implementations in Java/C#'s case, and no implicit extra runtime cost that could magnify for generic containers in Rust's case)

Note that C++'s multiple inheritance has the same problem as in Rust, that is converting a Subclass* to a Superclass* is a coercion and might change the pointer. Thus, converting from a Subclass** to a Superclass** is invalid, just like in Rust it's invalid to convert a &&dyn Subtrait to a &&dyn Supertrait.

While C# and Java make a compromise that you can't have multiple inheritance with classes, they still allow multiple classes to implement interfaces, and that also creates problems. In particular in Java (and in some way in C# too) calling a method on an interface requires looping through a list of itables, one for each interface that the actual class implements, looking for the itable for the interface we want to call the method of. This is obviously terribly inefficient to do for each call, which is why usually JIT techniques like inline caching are used to speed up this process for subsequent calls with objects of the same class. Unfortunately Rust is designed for AOT compilation, not JIT, so it can't use this technique.

2 Likes

That's why I propose only subtyping for cases where coercion is no-op, not for every case where coercion is valid.