How feasible would multiple inheritance be? Or: A modest addition to Thin Pointers


#1

I think I read Nikos write somewhere that there was some interest floating around the Servo developers regarding multiple inheritance as something that would have positive effects on the design and implementation of the DOM. I can’t really find this anymore (although I didn’t look very hard, so if someone knows what I’m talking about, I would very much like a link to that post). I wouldn’t know, so more qualified people should make that kind of value statement. I will say, though, that my experience with Common Lisp and C++ has taught me that, sometimes, you really would like to “mix-in” a lot of different implementations and gain access to that behavior. Scala developers also currently enjoy their version of traits.

Currently I think it’s fairly common for some people to write their own HasSuper trait and pass around trait objects. We’ve all probably written this at least once:

trait HasA {
    fn getA(&self) -> &A;
}

impl HasA for B {
    fn getA(&self) -> &A {
        &self.a
    }
}

And of course this is more flexible than single inheritance anyway. But the price is that we have to pay for fat pointers, and dynamic dispatch, even if we didn’t want either. The appeal of aturon’s Thin Pointers proposal is that we get cheap implementation inheritance with cheap static dispatch, integrating quite nicely with the existing trait system in a way that is intuitive and unintrusive.

I thought it was pretty clever to be able to pass around thin, well typed pointers because of requiring a prefix to the datatype, and I was wondering what it would take to support multiple inheritance. Obviously you just need an offset as well as the pointer, sort of like what the representation is for slices currently, which is when I remembered reading Nikos write that while loading a dynamic offset plus executing a static dispatch isn’t as fast as just a static dispatch, it was definitely faster than dynamic dispatch and would be welcomed in some scenarios (especially if the only other option was dynamic dispatch; I also can’t remember where I read this but I believe it was on a Github issue related to inheritance ideas, and aturon briefly mentioned it in the Specialize to Reuse proposal). So because of this, and the fact that even when people don’t have inheritance many often will pass around HasSuper trait objects (i.e. for heterogeneous lists), wouldn’t it be possible to just formalize what people are doing anyway and make it much faster?

My idea is just to add a new special built-in trait to the language Has<T>. The trait, if it were defined in real Rust, would just look like:

trait Has<T> {
    get(&self) -> &T;
    get_mut(&mut self) -> &mut T;
    // And perhaps there are other useful methods people can think of.
    // I avoided a by-value method to discourage slicing, but some may want that.
}

This trait cannot be implemented by the user. Rather, it is implemented with the same syntax for Thin Pointers. Specifically, if you write:

struct A { a: i32, b: i32 }
struct B: A { c: i32 }

Then this does what everyone here would expect (adds a prefix of A to B), but additionally one can inherit from as many unique types as one wants by using comma separation.

struct Z: X, Y {
     ...
}

will add prefixes of X and Y to Z, either in the order specified or perhaps in whatever order the compiler wants (since currently layout is undefined; I am purposefully leaving this open). There is nothing surprising here; any struct Z now has access to any of the fields and methods defined on any of its supertypes.

What may be surprising, though, is that this trait would have a different representation as a trait object. When constructing a trait object, e.g. as Box<Has<A>>, rather than being represented as a pointer to the implementing struct and a pointer to the vtable of method implementations, one simply gets a pointer to the datatype and a usize that represents the offset from the pointer to get to the A. Thus, one gets the afore mentioned static dispatch after a dynamically loaded offset.

The only thing I can’t really get figure out is diamond inheritance. I had initially wanted to do this as Common Lisp does it, which is merge redundant superclasses so that one simply has a unique set of superclasses, rather than the C++ way which is to add a copy of every superclass. While cognitively simpler, reordering fields willy-nilly means that if you have some A that is a supertype of B and C, and D inherits from both, then taking a &Has<C> over D means that you cannot simply load an offset (as C's A might have been removed in favor of B's). You could do this the C++ way, but then C++ has a lot of very ad-hoc rules for the way things might get resolved, and I think Rust was designed explicitly to have a lot of simple concepts without confusing, arbitrary conflict resolution rules. Thus I’m not especially convinced either is a good solution, but of course one cannot expect anything to be perfect.

I know other people have investigated this before so my two questions are:

  • Is this a possibly “good” extension to Thin Pointers, and
  • Has this design space previously been explored? What did people come up with?

The above was just a small excursion into the territory of dynamically loaded offsets and mixing-in multiple structs. It didn’t discuss virtual methods, overriding, or making an object out of multiple Has impls. But answering those questions isn’t really useful unless there’s actually a demonstrable desire for multiple struct inheritance in the first place. And if there is, what kinds of problems do people believe it’s useful for?


#2

You might be interested in my own forrays in polymorphism: rust-poly (explanations in the doc folder).

If you look at the StructInfo struct, which for some reason I am not managing to reproduce formatted here, you’ll notice a offsets_getter: fn (StructId) -> &'static [isize] field which would return the index of every single “base class” of the type asked for.

That is, no diamond for me. Just a tree.


#3

C# and Java community certainly dont miss it ( no diamonds , no fragile base classes ) and rust with where clauses / bounds even improves this since you only couple/ request what you need . .

Having different behavior for trait and trait objects is also IMHO bad .

There are very good reasons why java and C# have moved to interface heavy designs and injecting common behavior rather then inheritance over the last year even though both languages support inheritance. . In fact everything inheritance can do you can with an interface and injecting the common behavior without the limitations (at the cost of a virt call.) .

Id much rather the effort be spent on. eg

  1. Make trait objects easier/better. They are still clumsy to use maybe some sugar around heaped trait objects.
  2. Specialization and better yet HKT.
  3. thin traits and extended enums http://smallcultfollowing.com/babysteps/blog/2015/10/08/virtual-structs-part-4-extended-enums-and-thin-traits/
  4. Constructors… There are some nice life time guarantees that can be inferred which could help with memory management.
  5. Issues with mut borrows.
  6. Better SIMD