Support Trait+Foo for arbitrary traits

[bstrie]

@nikomatsakis has mentioned wanting to write a complete RFC for this. He has also mentioned that a weaker form of this proposal might be easier to produce, where instead of supporting Trait+Foo for any arbitrary trait we support it only for "marker traits", i.e. traits without methods.

Blocking rust-lang/rust#28326

[munael]

A bit more detail? I don't get at all what feature discussions you're referring to.

[eefriedman]

Simple example of what we could support:

trait Foo { fn foo(&self) {} }
trait Bar { fn bar(&self) {} }
fn f(p: &(Foo + Bar)) {
    // Call functions on p.
    p.foo();
    p.bar();

    // Conversions on p.
    let p2: &Foo = p;
    let p3: &Bar = p;
}

Some possible subsets: we might not support the full set of possible conversions. We might restrict what traits this is allowed with. (Special-casing traits without methods is a little dubious: our current API stability rules suggest that you're allowed to add methods with default implementations to existing traits.)

Note that this is mostly just syntactic sugar: equivalent example to the above written in stable Rust:

trait Foo { fn foo(&self) {} }
trait Bar { fn bar(&self) {} }
trait Baz: Foo + Bar {
    fn to_foo(&self) -> &Foo; 
    fn to_bar(&self) -> &Bar;
}
impl<T> Baz for T where T: Foo + Bar {
    fn to_foo(&self) -> &Foo { self }
    fn to_bar(&self) -> &Bar { self }
}
fn f(p: &Baz) {
    // Call functions on p.
    p.foo();
    p.bar();

    // Conversions on p.
    let p2: &Foo = p.to_foo();
    let p3: &Bar = p.to_bar();
}

[ticki]

👍

[munael]

👍*2

[withoutboats]

Foo+Bar wouldn't exactly be sugar for the code above, would it? I would expect it to combine the methods of both traits into a single vtable, rather than defining an anonymous trait objects with methods to construct other trait objects. This is why allowing marker traits as an intermediate step was suggested.

[nikomatsakis]

I have been thinking that Foo+Bar would likely have two vtables. If you
do otherwise, you cannot easily make arbitrary subsets, and hence the order
becomes significant. That seems unfortunate.

On Wed, Sep 23, 2015 at 8:49 PM, withoutboats notifications@github.com
wrote:

Foo+Bar wouldn't exactly be sugar for the code above, would it? I would
expect it to combine the methods of both traits into a single vtable,
rather than defining an anonymous trait objects with methods to construct
other trait objects.

—
Reply to this email directly or view it on GitHub
#1277 (comment).

[Kimundi]

I'd think that whatever change we get to support upcasting would also enable the subset-taking for a single-vtable Foo+Bar

[nikomatsakis]

@Kimundi We can support arbitrary subset-taking without using multiple
vtables, but we will have to prepare combination vtables for all possible
subsets, which is exponential (I think) in the number of traits. I guess
though that the number of traits is expected to be quite small, so maybe
that's not a big deal. That is, if you do for example A+B+C+D, we'd have
to have statically prepared vtables for all of the following:

A+B+C+D
A+B+C
A+B
A
B+C+D
B+C
B
C+D
C
D

The same is basically true for upcasting. That is, if you have:

trait X: A+B+C+D

and you want to allow X to be upcast to any subset of {A,B,C,D}, then
you have to either support multiple vtables, or else have all the
combinations on hand so you can pick the appropriate one when the upcast
occurs.

On Thu, Oct 1, 2015 at 6:23 AM, Marvin Löbel notifications@github.com
wrote:

I'd think that whatever change we get to support upcasting would also
enable the subset-taking for a single-vtable Foo+Bar

—
Reply to this email directly or view it on GitHub
#1277 (comment).

[glaebhoerl]

@nikomatsakis (Just thinking aloud) if the vtable for A+B+C+D is laid out as (VA, VB, VC, VD), then you can get the vtable for any individual trait, or any in-order subset of them, by just taking an offset... you need separate vtables for the cases where some number in the middle are "skipped". In this case I think that's just: A+B+D, A+C+D, and A+D (where the first two again get you B+D and A+C by offset-taking). I'm not sure what this means for the scaling formula in the general case...

(You can make sure it's order independent i.e. A+B+C+D and D+C+B+A are the same by just normalizing so that they're sorted according to some compiler-defined order.)

The same is basically true for upcasting.

How would multiple vtables work here? Would &X then contain 4-5 additional pointers? (Multiple vtables also seems more appealing to me at the moment based on the "how far can we uniformly generalize DST" stuff I've been thinking about, but trait inheritance is the big question mark... presuming A+B+C+D should mean the same thing in both places.)

[nikomatsakis]

@glaebhoerl

if the vtable for A+B+C+D is laid out as (VA, VB, VC, VD), then you can get the vtable for any individual trait, or any in-order subset of them, by just taking an offset

yeah, you're right that we can get some reduction this way. But bottom line is it is still a "lot" of vtables. :)

How would multiple vtables work here? Would &X then contain 4-5 additional pointers?

I think that the vtable for the trait X would contain 4-5 additional pointers, not the &X reference. A vtable would basically be something like:

[type hash]
[...vtables for supertraits...]
[...method pointers...]

[glaebhoerl]

Oh, hmm... that's the other option I was thinking about but couldn't immediately figure out how that would allow subset-taking - but I guess you'd just read out the supertrait vtable pointers from the subtrait vtable and make the fat pointer using them?

The other objection I had in mind was that this would make method calls require as many indirections as the inheritance hierarchy is deep, which doesn't seem like it would be in the spirit of Rust's performance philosophy, but I guess you could solve that as well by in addition also embedding the supertrait vtables directly into the subtrait vtable? Though in that case, you don't even need the extra vtable-pointers any more... even with (VA, VB, VC, VD), if you know the offsets, you can synthesize all the pointers you want.

[nikomatsakis]

@glaebhoerl

The other objection I had in mind was that this would make method calls require as many indirections as the inheritance hierarchy is deep, which doesn't seem like it would be in the spirit of Rust's performance philosophy, but I guess you could solve that as well by in addition also embedding the supertrait vtables directly into the subtrait vtable?

Yes, which is what we do today. And yes, you may be able to make some of the vtables subsets of one another, just as you observed for the A+B+C+D example. But you'll still have to have SOME amount of branching. There's many C++ papers on this -- basically the optimal layout for vtables for multiple inheritance (which naturally encounters the same problem).

EDIT: Well, more-or-less the same problem. C++ isn't trying to have types like Foo+Bar, so they don't try to select arbitrary subsets, but I think you can create similar problems via multiple inheritance where you have arbitrary DAGs, and you have to sometimes duplicate parts of your vtable. (I'm ignoring the question of field layout, which is also interesting!)

[glaebhoerl]

To be clear, what I was trying to say is that you could have it so that:

• The vtable for trait X: A+B+C+D is struct VX(VA, VB, VC, VD, VX_methods)
• The representation of &X is (&(), &VX)
• The representation of &(A+D) (for instance) is (&(), &VA, &VD)
• Upcasting &X to &(A+D) happens by deriving &VA and &VD from &VX. In this case since you have multiple pointers to single vtables, instead of a single pointer to multiple-vtables-in-one, there's no combinatorial explosion of necessary vtables -- there's no "vtable for A+D". EDIT: Or you could just use the original vtables for A and D instead of the ones duplicated in VX (both locations should be equally-well statically known)... I guess this matters if you want to do crazy fat pointer comparisony stuff. EDIT actually no I confused myself (you could only know that if you also statically knew the type the traits are implemented for, which of course for trait objects, per the whole point of trait objects, you don't)

[nikomatsakis]

Ah. This is basically precisely what I had in mind, yes, when I proposed
"obese pointers" (multiple vtables).

On Thu, Oct 1, 2015 at 5:10 PM, Gábor Lehel notifications@github.com
wrote:

To be clear, what I was saying is that you could have it so that:

The vtable for trait X: A+B+C+D is struct VX(VA, VB, VC, VD,
VX_methods)

The representation of &X is (&(), &VX)

The representation of &(A+D) (for instance) is (&(), &VA, &VD)

Upcasting &X to &(A+D) happens by deriving &VA and &VD from &VX. In
this case since you have multiple pointers to single vtables, instead of a
single pointer to multiple-vtables-in-one, there's no combinatorial
explosion of necessary vtables -- there's no "vtable for A+D".

—
Reply to this email directly or view it on GitHub
#1277 (comment).

[Kimundi]

True, if we are talking about arbitrary susbsets you get some exponential blowup if you want to generate a vtable for each subset.

Just another idea, but one possible way to mitigate that could be to create a single big vtable that is the merge of all Foo+Bar combinations in a compilation unit, and simply translate method calls for arbitrary subsets as using that same vtable. That way, you only get vtable duplications on cross-crate boundaries.

However, the multiple-vtable-pointer approach is certainly the simplest, and I'd like to see it implemented simply because it would set the precedence of &DST pointers with different sized metadata payloads.

---

As an aside, I'm also wondering wether any of these approaches would prevent upcastability from &Foo to &(A+B) where Foo: A + B.

[nikomatsakis]

@Kimundi

However, the multiple-vtable-pointer approach is certainly the simplest,
and I'd like to see it implemented simply because it would set the
precedence of &DST pointers with different sized metadata payloads.

Yeah. I'm not sure what else we might use that concept for, but at minimum
thin traits seem to be an instance of that (where the number of pointers is
0, not 1). I'd love it if we could also support crazy things like &[[u8]]
(2-d array where the width/height are unknown) though I'm not sure if that
really works out, since the existential quantifiers end up in the wrong
places. i.e., that's sort &(exists N. [exists M. [u8; M]; N]), whereas we
want &exists N,M. [[u8; M]; N], but maybe we can make it work somehow
with not too much special casing. :)

As an aside, I'm also wondering whether any of these approaches would
prevent upcastability from &Foo to &(A+B) where Foo: A + B.

I think it should be fine, as Gábor described.

On Fri, Oct 2, 2015 at 5:28 AM, Marvin Löbel notifications@github.com
wrote:

True, if we are talking about arbitrary susbsets you get some exponential
blowup if you want to generate a vtable for each subset.

Just another idea, but one possible way to mitigate that could be to
create a single big vtable that is the merge of all Foo+Bar combinations
in a compilation unit, and simply translate method calls for arbitrary
subsets as using that same vtable. That way, you only get vtable
duplications on cross-crate boundaries.

However, the multiple-vtable-pointer approach is certainly the simplest,
and I'd like to see it implemented simply because it would set the

precedence of &DST pointers with different sized metadata payloads.

As an aside, I'm also wondering wether any of these approaches would
prevent upcastability from &Foo to &(A+B) where Foo: A + B.

—
Reply to this email directly or view it on GitHub
#1277 (comment).

[Kimundi]

Some additional examples that come to mind:

• More complex kinds of slices, say for arbitrary rectangular areas of a 2D-array, or custom string slices that also carry a encoding tag.
• Trait object optimizations / wrappers where certain pointers from the vtable are carried directly next to it, rather on the inside. Say to have a closure trait object without double indirection to get the the function pointer.

[withoutboats]

sort of unformed ideas for how to implement this:

• Every vtable includes the typeid as its last member, trait objects now always know their type (modulo lifetimes of course, which are erased).
• For every cast from trait object type A to trait object type B, we generate a lookup table from type id to vtable. The cast generates a lookup to replace the vtable pointer.
  • (We optimize this away for marker traits, as is the case today).

probably there is prior art for this.

But I'm unhappy with solutions that take advantage of the knowledge that A + B + C has a particular ordering. I think A + B should unify with B + A. Instead, I think the vtables should be ordered in a consistent way regardless of the declaration order of their traits.

[Centril]

Closing in favor of #2035.