Objects should be upcastable to supertraits

[jdm]

trait T {
    fn foo(@mut self);
}

struct S {
    unused: int
}

impl T for S {
    fn foo(@mut self) {
    }
}

fn main() {
    let s = @S { unused: 0 };
    let s2 = s as @T;
    let s3 = s2 as @T;
}

error: failed to find an implementation of trait @T for T

[catamorphism]

Reproduced with 64963d6. Nominating for milestone 5, production-ready

[cmr]

The error as of 6c2dc3c is:

foo.rs:17:13: 17:21 error: can only cast an @-pointer to an @-object, not a trait T
foo.rs:17     let s3 = s2 as @T;
                       ^~~~~~~~
error: aborting due to previous error

which is a bit weird, why shouldn't you be able to cast a trait object to the same trait object?

[glaebhoerl]

IINM there's two ways you could interpret this: one is that it's the identity function (casting something to its own type), the other is that you're looking for an impl T for @T, and trying to make a new @T with that as the vtable, and with s2 as the "hidden object". Last I checked trait objects don't automatically implement their trait (because e.g. with Self it can be impossible), #5087.

[cmr]

I would have assumed it's the identity function

[nikomatsakis]

Updating title to reflect the larger issue (casting from @T to @T is a special case)

[graydon]

accepted for feature-complete milestone

[bblum]

This doesn't seem like the identity function to me, as the vtables can be subsets of each other in weird ways (e.g. with multiple supertraits). Doing this properly will require new codegen.

[kvark]

A simpler testcase:

trait U {}
trait V : U {}
fn foo<'a>(a : &'a V)-> &'a U   {
    a as &U
}

[pnkfelix]

this need not block 1.0. Assigning P-high as it is important for some use cases.

[nikomatsakis]

To be clear: this is not a subtyping rule but a coercion one. As @bblum says, it may require substituting a new vtable.

[alexcrichton]

This is on the 1.0 milestone currently, due to @pnkfelix's comment above, I'm removing the milestone assuming that it was an accident.

[little-arhat]

I'm curious, how we could call supertrait method on subtrait object [1], without being able to upcast such object to supertrait? Does vtable of subtrait include all methods from supertrait? Or how does it work?

[1] — https://github.com/rust-lang/rust/blob/41a79104a412989b802852f9ee6e589b06391d61/src/test/run-pass/trait-inheritance-cast.rs

[little-arhat]

Is there any way to work around this issue in current rust? transmute can not help here: it seems that transmute messes up with vtables:

trait Foo {
    fn f(&self) -> int;
}

trait Bar : Foo {
    fn g(&self) -> int;
}

struct A {
    x: int
}

impl Foo for A {
    fn f(&self) -> int { 10 }
}

impl Bar for A {
    fn g(&self) -> int { 20 }
}

fn to_foo(x:&Bar) -> &Foo {
    unsafe { std::mem::transmute(x) }
}

pub fn main() {
    let a = &A { x: 3 };
    let abar = a as &Bar;
    let abarasafoo = to_foo(abar);

    assert_eq!(abarasafoo.f(), 20); // g is called 
    assert_eq!(abarasafoo.f(), 10); // g is called

What is layout of trait objects? I think it should be possible to "upcast" subtrait object to supertrait with unsafe manipulation of vtables.

[little-arhat]

For future references: https://github.com/rust-lang/rust/blob/master/src/librustc/driver/pretty.rs#L137 — here is workaround for this issue.

[arthurprs]

Sub.

[kFYatek]

My workaround: http://stackoverflow.com/a/28664881/403742

[steveklabnik]

Triage: #5665 (comment) seems to be a decent test-case, and this is still a non-scalar cast today.

[typelist]

I've started looking at this. I figured I'd try to clear up the design first. Here's my understanding:

Basics

Trait objects (spelled as &Trait) should be upcastable to trait objects of supertraits (&Supertrait) in as expressions, with lifetime and mutability rules behaving similarly to reference casting.

Smart pointers

Similar conversions should probably be possible for Box<Trait> to Box<SuperTrait>, Rc<Trait> to Rc<Supertrait>, and for other smart pointers. If this can (or needs to) be dealt with separately, I'll defer it for now and maybe create a separate issue, but it seems like the issues around upcasting are the same.

Implementation

Trait objects consist of a vptr and a self-pointer. The vptr points to a vtable, which contains a static array of function addresses. Each method is associated with a statically known offset in that table. To call a method on a trait object, add the offset to the vptr and call the function whose address is stored in that slot, passing the self-pointer as the first argument.

(The vtable also stores some metadata, which currently includes size, alignment, and the address of the destructor. The destructor is treated specially, presumably because any concrete type may implement Drop, and Box<Trait> needs to be able to run the destructor without Trait explicitly inheriting Drop.)

Currently, there is one vtable for each impl of an object-safe trait. There is no particular relationship between different vtables for a type that implements multiple traits. Supertrait method addresses are, however, duplicated into the subtrait's vtable.

To support upcasting, we need a way to get from the subtrait's vtable to the supertrait's vtable. I'm planning on storing supertrait vtables next to subtraits vtables, in a recursive pattern. This would let us use statically known offsets for upcasting, because the offsets are the same for every subtrait impl. The drawback is that superclass vtables would need to be duplicated in a 'diamond' inheritance situation.

(Another consequence is that two trait objects of the same trait could have different vptrs even if they were created from the same concrete type, depending on what path they took up the inheritance chain. This shouldn't matter in practice, since we don't make any guarantees about trait object equivalence.)

An alternative solution would be to store offsets next to each method list, one for each supertrait we can upcast to. This representation is more compact, but I expect it would be slower because of the dependent read.

Questions

• Should trait object upcasts be explicit (require an as expression) or implicit?
• Is it OK to duplicate supertrait vtables like I described above?
• I believe this issue predates the RFC process. Should I file one about any part of this?

[typelist]

Looks like RFC 401 answered my first question: this is supposed to be an implicit coercion. See also: #18469, the tracking issue for RFC 401, and #18600, which deals with subtrait coercions and therefore may be a duplicate of this issue.

RFC 982 (DST coercions) also looks to be related. Tracking issue is #18598.

[typelist]

RFC pull request 250 (postponed) dealt with this, but alongside proposals for associated fields on traits, opt-in internal vtables, and other features. The upcasting section of that proposal is basically what I had in mind.

[nikomatsakis]

@typelist sorry for not getting back to you sooner! I have some thoughts about how this should work, but I think the problem can also be subdivided. Likely we should start by writing up an RFC, perhaps just for a subset of the total problem. Let me just leave various notes and let's try to sort it out a bit.

Multiple traits, multiple vtables

First of all, this is related to the topic of supporting trait objects of multiple traits. For example, I would like to support &(Foo + Bar) as a trait object, where Foo and Bar are any two object-safe traits. We already support this is in a very limited way with &(Foo + Send), but that is special-cased because Send does not require a vtable. One would be able to upcast to any subset of those traits. For example, you could upcast from &(Foo + Bar) to &Foo just by dropping one of the vtables.

This is orthogonal from supertrait upcasting, just wanted to throw it out there. In particular, if you have trait Foo: FooBase, then one can imagine permitting an upcast from &(Foo+Bar) to &(FooBase+Bar) and so forth. Similarly, if you had trait Foo: FooBase1 + FooBase2, then you could cast &Foo to &(FooBase1 + FooBase2).

I bring it up though because the implementation strategy here may want to be shared with other trait combinations. Originally, the way I had thought to support this was to have a trait object potentially have >1 vtable (i.e., one for Foo, one for Bar). But of course this is not the only implementation strategy. You could create a "composed" vtable (on the fly) representing Foo+Bar. (These would have to be coallesced across compilation units, like other monomorphizations.) However, to permit upcasts, you would then have to make "subtables" for every supertrait combo -- e.g., the Foo+Bar vtable would also have to have a Foo and a Bar vtable contained within. As the number of traits grows (Foo+Bar+Baz) you wind up with N! vtables for N composed traits. This seemed suboptimal to me now, though I suppose that realistically N will always be pretty darn small.

Note that if we adopted the strategy of making one coallesced vtable, this will affect how supertraits are stored in vtables. If we said that &(FooBase1 + FooBase2) uses two vtables, then the vtable for Foo can just have an embedded vtable for each supertrait. Otherwise, we need to store embedded vtables for all possible combinations (leading again to N! size).

Supertrait upcasting

OK, so, with that out of the way, I think it makes sense to focus squarely on the case of supertrait upcasting where exactly one vtable is needed. We can then extend (orthogonally) to the idea of multiple vtables. So in that case I think the basic strategy you outlined makes sense. You already cited this, but I think that the strategy outlined by @kimundi and @eddyb in RFC 250 is basically correct.

Interaction with the unsize coercion

You are also already onto this one, but yes this is clearly related to the idea of coercing a &T to a &Trait (where T: Trait), which is part of the "unsize coercion". My view is that this is basically added another case to that coercion -- that of supporting &Trait1 to &Trait2 where Trait1: Trait2. And the idea would be to manipulate the vtable(s) from the source reference in such a way as to produce the vtable(s) of the target reference.

Because the vtable must be adjusted, it's clear that this has to be a coercion and not an extension of subtyping, since subtyping would require that there are no repesentation changes. Moreover, by attaching it to the existing unsizing coercion, we don't have to address questions about just when it triggers -- same time as unsizing triggers.

Do we need an RFC to go forward here?

It seems like it can't hurt, but I'd basically just extract the relevant text from RFC 250, which I think was essentially correct. If we're just sticking to supporting single trait object to other trait object, seems harmless enough, and I can't imagine many objections. I would be very happy to work with you and draft it together!

[typelist]

Thanks for the response! I started drafting an RFC based on part of RFC 250. Comments or revisions welcome. (Should we keep communicating through this issue, or some other way?)

For the multi-trait case, increasing the size of the trait object does seem like the path of least resistance. It certainly makes partial upcasts (and upcasts like &Subtrait to &(Supertrait1 + Supertrait2)) straightforward.

[nikomatsakis]

@typelist this RFC looks great! I appreciate that you took the time to talk about the motivation, alternatives and downsides.

(We can keep talking over the issue, or feel free to e-mail me or ping me on IRC. I try to keep up with GH notifications, but it can be challenging.)

[qnighy]

@typelist @nikomatsakis Any updates on this? I'd like to push this forward.

I took a stat of vtable usage in rustc. Perhaps it is useful when predicting code-size/performance effects of upcasting support. https://gist.github.com/qnighy/20184bd34d8b4c70a302fac86c7bde91

[ctaggart]

If this was implemented, would this compile? If so, this would be extremely helpful. For example, with TypeScript interop, I could avoid all the ugly Box::from calls.

trait Statement {}

trait IfStatement: Statement {}

struct IfStatementImpl;
impl Statement for IfStatementImpl {}
impl IfStatement for IfStatementImpl {}

fn print_statement(_statement: &Statement){
    println!("print_statement");
}

fn print_if_statement(_if_statement: &IfStatement){
    println!("print_if_statement");
}

fn main() {
    // How come this compiles?
    let ref a = IfStatementImpl {};
    print_statement(a);
    print_if_statement(a);

    // but this does not?
    let ref b: IfStatement = IfStatementImpl {};
    print_statement(b);
    print_if_statement(b);
}

[qnighy]

@ctaggart I think 50% yes. let ref b: IfStatement = IfStatementImpl {}; won't yet compile (because it tries to coerce IfStatementImpl into IfStatement and then take a reference of it), but if you change it to let b: &IfStatement = &IfStatementImpl {}; (take a reference and then coerce &IfStatementImpl into &IfStatement), then sub-trait coercion would allow it to compile.

[bstrie]

@rust-lang/lang, IRC suggests that this is something that should be closed or moved to the RFCs repo.