Trait objects, auto trait subtyping?

Is there any reason against making dyn Trait + Foo + Bar a subtype of dyn Trait + Foo (for auto-traits Foo and Bar) or has something like this just never been implemented? E.g. the following coercion would succeed

trait Trait {}
fn coerce(x: Box<Box<dyn Trait + Send>>) -> Box<Box<dyn Trait>> { x }

For comparison, other trait objects already have subtyping relationships, e.g. dyn Trait + 'a is a subtype of dyn Trait + 'b when 'a: 'b, or dyn for<'c> Trait_<'c> is a subtype of dyn Trait_<'b>. (playground)

4 Likes

Following Rust philosophy, this should not be covered by subtyping, instead, by coercions. Currently Unsize trait covers this: i.e dyn Trait + Foo + Bar: Unsize<dyn Trait + Foo>, as one specific kind of coercion.

Unsize impls are compiler generated impls following rules, and they're meant to be used together with CoerceUnsized (as bounds) to guide the smarter pointer for DST type coercions.

Unfortunately, current std impls only covers one-level redirections here. It's this impl: impl<T: ?Sized + Unsize<U>, U: ?Sized, A: Allocator> CoerceUnsized<Box<U, A>> for Box<T, A>{...} This did not cover your two-level redirection case, so your code couldn't compiles.

The design of CoerceUnsized in its current status is quite incomplete, and cannot be fixed to cover your case easily. So maybe serious rethinking might be needed here before doing something.

2 Likes

W.r.t. unsize coercions, note that he examples of dyn Trait + 'a to dyn Trait + 'b and dyn for<'c> Trait<'c> to dyn Trait<'b> conversion are interesting they’re also supporting unsize coercion, but subtyping coercions as well. (You can see this by the fact that e.g. &'r mut dyn for<'c> Trait<'c> coerces to &'r mut dyn Trait<'b>; this case can’t be supported by subtyping alone since &mut T is invariant in T.)

I also know about CoerceUnsized; as far as I know it’s supposed to be a cheap operation, hence it currently only supports one level of indirection. You cannot turn Box<Box<T>> into Box<Box<dyn Trait>> when T: Trait because Box<T> and Box<dyn Trait> have different representations at run-time and implicitly re-allocating the outer Box in the CoerceUnsized coercion is out of the question.

The important point is that Box<dyn Trait + Send> and Box<dyn Trait> have identical run-time representation (AFAIK), hence subtyping should be technically possible; it’s a different situation than what’s allowed for unsized coercion in general. What “Rust philosophy” are you referring to? What are the reasons why this “should not be covered by subtyping”? After all, all that subtyping does is provide a set of coercions (subtyping coercion), and a set of rules to determine subtyping relationships recursively (i.e. variance rules). If a system that can offer things like Box<Box<dyn Trait + Send>> to Box<Box<dyn Trait>> coercion should not be subtyping, i.e. a separate (more restricted?) thing, in what way should the rules for determining the set of allowed coercions under this system differ from the variance rules of subtyping? And what’s the significant “philosophical” difference between dyn Trait + Send --> dyn Trait vs. dyn for<'c> Trait<'c> --> dyn Trait<'a> anyway?

1 Like

Is this really part of rust's philosophy? I thought it used coercions more than subtyping only because it had to.

The core question here has been how to represent the necessary vtables as the number of traits grows. One way is to just have super-fat pointers, so &dyn Foo1 + Foo2 + ... + FooN is (N+1)-usizes big, with one vtable metadata per trait.

With just one vtable pointer, note that subtyping generally can't work, as changing the type might mean changing that vtable pointer to point to a different vtable or different part of the mega-vtable. (You'll see this in C++ as well, for example, where static_cast and reinterpret_cast can give different results depending on exactly which pointer types you're casting between.)

I’m explicitly only addressing the case where all the additional traits are auto-traits, e.g. cases like dyn TraitFoo + Send, dyn TraitBar + Unpin or dyn TraitBaz + Send + Sync. The vtable should be identical for these trait objects with or without the additional + Send, + Unpin or + Send + Sync.

1 Like

Note that @steffahn is talking about auto-traits specifically (though "solutions should be general, not targeted" is a common viewpoint).

I think there's some things to think out around negative trait markers and if auto-traits will always be subtype-like unidirectionally.

I’m not quite sure what you’re hinting at here. Could you be more specific? Also… even if there’ll ever be more, somehow different, auto-traits; or more kinds of bounds being introduced, those won’t necessarily have to support subtyping, too, so I don’t really see the problem.

Ah, sorry, I'd missed that.

Yes, I think it would make sense for subtyping in that case -- also with #[marker] traits -- since there's no monomorphization difference.

It would make it normative that an auto-trait always adds capability. Perhaps this is fine, but I haven't taken to the time to think it through.

What's the future outlook for negative impls, and may they be part of dyn Trait for either auto-traits or any trait some day? What are the implications to subtyping?

I don't have any particular objections, they're just considerations to be hashed out which came to mind.

(I do generally feel that the future need be considered and not dismissed as "the future can do whatever", as that leads to a language with a lot of corner cases. Let's ensure future compatibility.)

After all, all that subtyping does is provide a set of coercions (subtyping coercion)

Not really. Subtypings and coercions are very different from type inference perspective. Rust coercions happen at language-specified coercions sites. We don't say "subtyping coercion“ at all in Rust.

Basically coercions means that there're (at least) two difference type variables and coercion rule relationship be established between them, and subtyping means that the same type variable needs to be able to be "interpreted" as different types (with variance and maybe other aspects). So you can see it's very obvious that huge complexity resides within the later approach. Basically in Rust from my understanding subtypings are only used on lifetime-related things. (And from implementation perspective, the fact that lifetime subtyping inference system (a.k.a borrow checker) is separate is already source of many historic bugs (even unsoundness issues) within rustc.)

I'm not saying the issue in OP isn't worth solving. In fact i think it is, and i think it's best solved with carefully redesigned coercion rules. This might imply some tweaking around the existing CoerceUnsized-centered coercion rules.

3 Likes

Okay, thanks for the info pointing out that there’s suppositely a difference between subtyping and coercions. I guess issues like

are relevant here, too; dyn Tr<'static> and dyn for<'a> Tr<'a> aren’t really supposed to be completely different types (even though they do have different TypeIds).

In fact I am only interested in ordinary coercion here, so nothing that wouldn’t happen at ordinary coercion sites. I haven’t found any example where dyn for<'a> Tr<'a> can turn into dyn Tr<'static> without it being an ordinary coercion (feel free to point out any examples if you know them!!); but if there are any such cases, I suppose I wouldn’t require those to work for my proposed dyn Trait + Send to dyn Trait conversion.

I do still believe that even so, it’s still similar enough to subtyping that it’s questionable to explain it as anything significantly different, except perhaps in a really detailled reference-level explanation.

To be clear, I would propose that. For any trait Trait and auto-trait Foo, for any type Ty<T> that’s covariant in T, the type Ty<dyn Trait + Foo> can coerce into Ty<dyn Trait>. Similarly for multiple auto-traits; and of course conversion the other way should be permitted if Ty<T> is contravariant in T.

Ty<T> can be arbitrarily complex, e.g. it could be Ty<T> = Box<fn(fn(Option<T>) -> i32) or stuff like that. Of course, this should also combine transitively with certain other coercions, in particular with other coercions of the same kind or coercions due to subtyping.

Due to the interaction with the variance/covariance of subtyping, I’d say that these coercion should still count as a version of subtyping coercion.


I don’t know how up-to-date 0401-coercions - The Rust RFC Book is supposed to be, it’s a source that explains differences between subtyping and other coercions; but I don’t like the quote

Subtyping is implicit and can occur at any stage in type checking or inference. Subtyping in Rust is very restricted and occurs only due to variance with respect to lifetimes and between types with higher ranked lifetimes. If we were to erase lifetimes from types, then the only subtyping would be due to type equality.

It accurately mentions higher-ranked lifetimes, but the assumption that subtyping turns entirely into type equality under lifetime erasure seems wrong, given that e.g. dyn Tr<'static> and dyn for<'a> Tr<'a> are still in many ways two distinct T: 'static types with distinct TypeId at run-time, etc.

To be clear, for example take

trait Tr<'a> {}

type Foo1 = &'static dyn Tr<'static>;
type Bar1 = &'static dyn for<'a> Tr<'a>;

and

struct FooStruct;
struct BarStruct;

use std::ops::Deref;
impl Deref for BarStruct {
    type Target = FooStruct;
    fn deref(&self) -> &Self::Target {
        &FooStruct
    } 
}

type Foo2 = &'static FooStruct;
type Bar2 = &'static BarStruct;

Both types Foo1-Bar1 and Foo2-Bar2 can coerce, e.g.

fn coerce1(x: Bar1) -> Foo1 {
    x
}

fn coerce2(x: Bar2) -> Foo2 {
    x
}

Now the RFC quoted in my previous answer says

Subtyping is implicit and can occur at any stage in type checking or inference.

and

A coercion can only occur at certain coercion sites in a program, these are typically places where the desired type is explicit or can be derived by propagation from explicit types (without type inference).

Above, Bar1 is a subtype of Foo1, while Bar2 can only be coerced into Foo1. Now, I’d love to see a concrete code example where Bar1 can turn into Foo1, but the equivalent code for Bar2 and Foo2 wouldn’t work. Of course this must not be a case where Bar1/Foo1 is used as the parameter to a covariant type and that type is then coerced, because of course then the equivalent for Bar2/Foo2 wouldn’t work since coercions can’t proagate through covariant type constructors.

The MCP cited in the most recent comment of that thread implies the opposite, yes?

I’m not too familiar with the discussion taking place there; I’m just noticing that in the current compiler, with types

trait Tr<'a> {}

type Foo = dyn Tr<'static>;
type Bar = dyn for<'a> Tr<'a>;

code like

impl Foo {
    fn f(&self) {}
}
impl Bar {
    fn f(&self) {}
}

fails to compile, and code like

trait X {
    fn f(&self);
}
impl X for Foo {
    fn f(&self) {}
}
impl X for  Bar {
    fn f(&self) {}
}

produces a warning.

(playground)

Both the error and the warning link to the issue I linked above.

You say

Which I took to mean, you're okay with it being a coercion and not a subtype, but ask for any counter-examples. However, you then qualify the request for examples with

But that's exactly what your OP is -- your Bar2/Foo2 won't work here:

trait Trait {}
fn coerce(x: Box<Box<dyn Trait + Send>>) -> Box<Box<dyn Trait>> { x }

So am I missing something?


Perhaps the future is still unclear with exactly how "differently" you can treat super- and sub-types. And, I guess, if the MCP only applies to higher-ranked subtyping (I suspect that's the case).

If super and subtypes cannot have separate impls generally, making any pair of existing types have a super/sub relationship is a breaking change, as you can write this today:

trait Tr {}
impl dyn Tr { fn f() {} }
impl dyn Tr + Send { fn f() {} }

But I have no idea how common these are.

Yes, what I’m after is any difference between A is a subtype of B vs. all covariant types Ty<T> have a coercion Ty<A> to Ty<B> and all contravariant types Ty<T> have a coervion Ty<B> to Ty<A>.

The latter is of course not the case for A == Bar2 and B == Foo2; only the trivial case of Ty<T> == T supports that coercion.

The context being my claim / my initial intuition that

which @crlf0710 claimed was wrong – probably rightfully so, considering the RFC 0401 that I’ve linked. It appears to be the case that conversions via subtyping can happen in some cases where coercion can’t happen (because it’s not a coercion site).

Also the remark

suggests that subtyping can do more than what “just a set of coercions” could achieve. I’m curious about any example code that demonstrates a capability of subtyping that isn’t just the effect that some type can coerce into another; and to be more precise, I’m interested in seeing an example of such a difference for the HRTB-subtyping, i.e. for a pair of types such as Foo1 and Bar1 I defined above.


Let me be more clear about this. I’d be okay with a relationship between types such as dyn Trait + Send to dyn Trait that comes as “a set of coercions, and a set of rules to determine this set of coercions recursively (akin to subtyping’s variance rules)”. But I’m also not fully concinved that there’s anything more to subtyping than just that; I would love to be fully convinced by seeing some example of what subtyping can do beyond that, so that I’d have a reason to change my proposal of “make dyn Trait + Send a subtype of dyn Trait” to “introduce rules for a new type of coercion with similar effect as making dyn Trait + Send a subtype of dyn Trait”.

1 Like

suggests that subtyping can do more than what “just a set of coercions” could achieve

No, i'm suggesting subtyping and coercions are very different in rust. Not "one more the other less", but fundamentally different. The areas where they overlap is very very small.

so that I’d have a reason to change my proposal

Well, the realistic reason is that, there's not precedence and infrastructure within Rust language for adding such subtypings.

Motivation: Unclear. Coercions are designed exactly for this sort of things.

Price: Rewriting a whole lot of rustc type inference code, taking a few years.

So what for?

If there's such a big difference, you certainly could demonstrate some piece of code that shows how the fact that dyn for<'a> Tr<'a> is a subtype of dyn Tr<'static> makes any difference (e. g. in terms of what code compiles and/or doesn't compile), compared to what would happen if it just gives rise to a set of allowed coercions, right? I haven't been able to make out any effects of a special treatment of dyn for<'a> Tr<'a> and dyn Tr<'static> in type inference myself, I'm really interested in learning more.

My motivation, as mentioned above: I wouldn't want to not describe it as subtyping in case it wouldn't make a difference.

the fact that dyn for<'a> Tr<'a> is a subtype of dyn Tr<'static>

Sorry i don't really know much when it comes to lifetimes. Most of my understanding of Rust comes from the Rust Reference and it says very little about lifetimes. In fact i myself cannot validate the correctness of the above sentense your quoted lol.

My motivation, as mentioned above: I wouldn't want to not describe it as subtyping in case it wouldn't make a difference.

Now i understood your position: Caring about user-face outcome. But i must say it's not a "orphan decision". In fact it's definitely possible to use subtyping to reach the same user-facing result (maybe there would be difference in corner cases).

Let me try my best to give an imaginary world trying to add such subtyping rules naively. (There might be error in my reasoning, please double-check with others)

Currently this code compiles:

trait Foo {}

fn foo1() -> &'static (dyn Foo + Send + Sync) {
    todo!();
}

fn main() {
    let x = foo1();
    let y = x;
}

Currently this code compiles:

trait Foo {}

fn foo1() -> &'static (dyn Foo + Send + Sync) {
    todo!();
}

fn main() {
    let mut f;
    f = foo1();
    f = foo1();
}

Currently this code doesn't compile:

trait Foo {}

fn foo1() -> &'static (dyn Foo + Send + Sync) {
    todo!();
}

fn foo2() -> &'static dyn Foo {
    todo!();
}

fn main () {
    let mut f;
    f = foo1();
    f = foo2();
}

With the subtyping added, the first example y type becomes ambiguous. Obviously we don't want to emit an error here (or the language becomes unusable), so we add new rules, allow it to "fallback" to &'static (dyn Foo + Send + Sync)

Now we come to the second example, the f type is still ambiguous. We realized we're now at a position where type-inference almost never works. And what's worse, we cannot even do fallback now. Because both assignments are coercions sites, we cannot really decide how we choose f type.

Even if we somehow supported this case. The third case is even worser. Basically we claimed the total failure of our existing type inference system.