Stream: t-lang/major changes

Topic: Trait Upcasting lang-team#98


view this post on Zulip triagebot (Jun 15 2021 at 19:44):

A new proposal has been announced: Trait Upcasting #98. It will be announced at the next meeting to try and draw attention to it, but usually MCPs are not discussed during triage meetings. If you think this would benefit from discussion amongst the team, consider proposing a design meeting.

view this post on Zulip Charles Lew (Jun 15 2021 at 19:57):

For background reference, there was an old topic within wg-traits stream: https://rust-lang.zulipchat.com/#narrow/stream/144729-wg-traits/topic/object.20upcasting

view this post on Zulip Connor Horman (Jun 15 2021 at 20:01):

This is &dyn Subtrait => &dyn Supertrait, where trait Subtrait: Supertrait{}, correct?

view this post on Zulip scottmcm (Jun 15 2021 at 20:24):

This is a relatively easy one since the vtable for the supertrait can be a prefix of the vtable of the subtrait, right?

view this post on Zulip Connor Horman (Jun 15 2021 at 20:47):

It would need a vptr stored in the general case. Some cases, like single trait inheritence, should be able to use a prefix, though.

view this post on Zulip Charles Lew (Jun 15 2021 at 20:50):

This is &dyn Subtrait => &dyn Supertrait, where trait Subtrait: Supertrait{}, correct?

Yes!

view this post on Zulip Charles Lew (Jun 15 2021 at 20:51):

This is a relatively easy one since the vtable for the supertrait can be a prefix of the vtable of the subtrait, right?

Most but not always so. I'm planning to change the vtable structure so that supertrait vtable is always a "subslice" of the entire vtable.

view this post on Zulip Charles Lew (Jun 15 2021 at 20:53):

For multiple inheritance and diamond inheritance cases, this will mean some slots in it are duplicated.

view this post on Zulip scottmcm (Jun 15 2021 at 20:59):

Ah, yes, multiple supertraits. Thanks for the reminder.

view this post on Zulip Connor Horman (Jun 15 2021 at 21:00):

Hmm... That's a potentially reasonable setup.
I considered this problem while writing an ABI for use with my (very WIP) implementation of rust, in <https://github.com/LightningCreations/lccc>. The method I chose was simply storing a vptr for each direct upcast trait in the vtable (and then also store the vfns in the table), https://hackmd.io/@wSaA8OrrSQ2SlegMvA6e6A/SJ1TeE0y_#DST-Pointer-Layout (point 2).

view this post on Zulip scottmcm (Jun 15 2021 at 21:00):

Can you elaborate on "subslice"?

view this post on Zulip Connor Horman (Jun 15 2021 at 21:03):

I think I have an idea of what is meant, so I'll attempt to explain.
The layout would be a struct SingleTraitVTable{...}, where SingleTraitVTable is w/e rustc stores in the vtable for a single trait, and none of it's supertraits, and then the actual vtable would be [SingleTraitVTable;N] where N is the total number of vtables that need to be stored, such that upcasting to any trait only requires taking some subrange of that vtable.

view this post on Zulip Connor Horman (Jun 15 2021 at 21:04):

(With potential for optimization in single inheritence cases, where it doesn't duplicate the size/alignment/drop-glue stuff where it doesn't have to)

view this post on Zulip Charles Lew (Jun 15 2021 at 21:04):

On the basis of this, we can optimize for the single inheritance case.

view this post on Zulip Charles Lew (Jun 15 2021 at 21:04):

Yeah

view this post on Zulip Charles Lew (Jun 15 2021 at 21:04):

    // When we create vtable, we want to ensure that each supertrait's vtable
    // is a subslice of this vtable.

    // For a single inheritance relationsihp like this,
    //   D -- C -- B -- A - DSA
    // The resulting vtable will consists of these segments:
    //  DSA, A, B, C, D

    // For a more complex inheritance relationship like this:
    //   O -- G -- C -- A - DSA
    //     \    \    \- B - DSA
    //     |    |- F -- D - DSA
    //     |         \- E - DSA
    //     |- N -- J -- H - DSA
    //          \    \- I - DSA
    //          |- M -- K - DSA
    //               \- L - DSA
    // The resulting vtable will consists of these segments:
    //  DSA, A, DSA, B, C, DSA, D, DSA E, F, G,
    //  DSA, H, DSA, I, J, DSA, K, DSA L, M, N, O

view this post on Zulip Charles Lew (Jun 15 2021 at 21:05):

This is some of the comments in my upcoming pr.

view this post on Zulip Charles Lew (Jun 15 2021 at 21:05):

DSA means destructor + size + alignment

view this post on Zulip Charles Lew (Jun 15 2021 at 21:06):

So for the single inheritance case, nothing is changed, it is exactly what it is today.

view this post on Zulip Charles Lew (Jun 15 2021 at 21:09):

For the multiple inheritance cases, DSA are duplicated, so that upcasting to any trait only requires taking some subrange of that vtable. Actually for code generation we only care about the starting point. It is adding an offset to the pointer metadata.

view this post on Zulip Charles Lew (Jun 15 2021 at 21:11):

When upcasting to A, C, G, O, the offset will be 0, while upcasting to B, the offset will be 2. upcasting to D, F, the offset will be 5.

view this post on Zulip Connor Horman (Jun 15 2021 at 21:11):

Hmmm... This actually seems like a good idea.

view this post on Zulip Charles Lew (Jun 15 2021 at 21:11):

times pointer_size ( i got the above offset numbers slightly wrong because dsa is three words, but you got the idea )

view this post on Zulip Charles Lew (Jun 15 2021 at 21:12):

I took this idea from previous discussions.

view this post on Zulip Connor Horman (Jun 15 2021 at 21:12):

Mind if I steal make use of this layout. This seems a lot more efficient then storing parent vptrs in the vtable

view this post on Zulip Charles Lew (Jun 15 2021 at 21:17):

just do whatever you want with it lol. advices welcome!

view this post on Zulip Connor Horman (Jun 15 2021 at 21:22):

Only potential issue: This wouldn't implementation wouldn't likely admit vtable unification. So there will likely be distinct (though equivalent) vtables for &T => &dyn Super directly, and &T => &dyn Sub => &dyn Super.

view this post on Zulip scottmcm (Jun 15 2021 at 21:49):

Ah, got it. Thanks! That chart helps.

Charles Lew said:

For the multiple inheritance cases, DSA are duplicated.

I guess today they're already duplicated per trait vtable, so this could even result in smaller overall vtable data?

view this post on Zulip Mario Carneiro (Jun 16 2021 at 00:40):

If there is a lot of diamond inheritance that could result in exponential blowup of the vtable

view this post on Zulip Mario Carneiro (Jun 16 2021 at 00:40):

for example, trait A(n+1): Bn + Cn {}, trait Bn: An { fn bn(&self); }, trait Cn: An { fn cn(&self); }

view this post on Zulip Mario Carneiro (Jun 16 2021 at 00:41):

the vtable for An will contain 2^n DSAs

view this post on Zulip Connor Horman (Jun 16 2021 at 00:54):

I mean, yes, but that would be unavoidable. In the alternative, you'd have 2^n vtables, and n levels of indirection

view this post on Zulip Mario Carneiro (Jun 16 2021 at 02:55):

No; if all traits have their own separate vtables then there are only 3n of them, each with size ~2n

view this post on Zulip Mario Carneiro (Jun 16 2021 at 02:56):

even if you embedded all links to supertraits in the vtables that would still only be quadratic

view this post on Zulip Charles Lew (Jun 16 2021 at 10:40):

@Mario Carneiro I'm not sure i understood your proposal. Would you mind saying more about it?

view this post on Zulip Charles Lew (Jun 16 2021 at 10:55):

Did you mean appending the supertraits vtable pointers to the existing vtable?

view this post on Zulip Mario Carneiro (Jun 16 2021 at 12:58):

Suppose that the vtable for An is bn, cn, ..., b1, c1, DST and similarly for Bn and Cn. The vtables are completely unshared. There are 3n vtables, and each one has size 2n. If we need to include pointers to each supertrait vtable in the vtable An would look like bn, cn, ..., b1, c1, DST, &dyn Bn, &dyn Cn, ..., &dyn B1, &dyn C1, &dyn A1, which is still only of size 5n, so quadratic, not exponential

view this post on Zulip Mario Carneiro (Jun 16 2021 at 13:02):

Probably you want to use a hybrid of this approach and the exponential one, where some supertraits can be encoded with slices and others need a separate vtable. The ones that get slices should be a spanning tree of the supertrait DAG

view this post on Zulip Mario Carneiro (Jun 16 2021 at 13:02):

...is it even a DAG? Nothing in rust ever seems to be well ordered (in the mathematical sense)

view this post on Zulip Charles Lew (Jun 16 2021 at 13:38):

@Mario Carneiro Yes, this hybrid approach sounds good! I think i'll just give up the idea of non-zero offsets, using zero offsets as much as possible, and supply vtable pointers for all the non-zero-offset cases. It will take the advantage of both.

I wonder if this a little complexity is acceptable from language perspective? If it's fine i'll create a prototype implementation.

view this post on Zulip Mario Carneiro (Jun 16 2021 at 13:40):

from a language perspective it's all unobservable, right? I don't think any of the vtable details are public or stable

view this post on Zulip Charles Lew (Jun 16 2021 at 13:42):

It is not observable, for now. But there was a saying something like "any implementation detail will be relied on by someone, eventually" or something.

view this post on Zulip Charles Lew (Jun 16 2021 at 13:43):

In C++ the implementation detail of vtable is already relied on by technologies like microsoft COM, etc...

view this post on Zulip Connor Horman (Jun 16 2021 at 14:06):

Charles Lew said:

In C++ the implementation detail of vtable is already relied on by technologies like microsoft COM, etc...

Indeed, though those are also under the control of specific implementations. An implementation can choose to promise more than the language does, but it's never a requirement to promise something the language itself doesn't promise.

view this post on Zulip triagebot (Jun 22 2021 at 17:14):

@T-lang: Proposal #98 has been seconded, and will be approved in 10 days if no objections are raised.

view this post on Zulip pnkfelix (Jun 22 2021 at 17:18):

This presentation has some typos. (E.g. the roles of Foo and Bar switch inexplicably.)

More importantly, I think it would benefit from spelling out a few more cases. E.g. a trait can have multiple super-traits. I assume upcasts will be supported even in that case.

(I need to review the thread here; maybe I can suggest a revision to the description after doing so.)

view this post on Zulip Josh Triplett (Jun 22 2021 at 17:48):

:+1:

view this post on Zulip Kimundi (Jun 24 2021 at 20:11):

Just for reference, the same "exponential blowup" vs "additional pointer indirection" standoff had also been discussed in 2015: https://github.com/rust-lang/rfcs/issues/1277

view this post on Zulip nikomatsakis (Jun 25 2021 at 09:01):

Yes...it's sort of fundamental :)

view this post on Zulip Charles Lew (Jul 03 2021 at 07:28):

The progress of this mcp is tracked in https://rust-lang.zulipchat.com/#narrow/stream/144729-wg-traits/topic/object.20upcasting . Made some progress recently: 2 prs merged, 1 in flight, and 1 in preparation.

view this post on Zulip Charles Lew (Jul 25 2021 at 15:04):

Recent progress after last update:
1 pr merged, 1 pr ready, and 1 in preparation.


Last updated: Dec 07 2021 at 14:33 UTC