Stream: general

Topic: dynamic dispatch - supporting more receiver types


mikeyhew (Apr 25 2019 at 21:45, on Zulip):

Hey @eddyb

So I thought we should talk again about making dynamic dispatch on trait objects more general, supporting receiver types with arbitrary extra fields instead of just newtyped pointers. I'm going to try to summarize the problem as I understand it so far, please correct me if I got anything wrong.

One of the things we need to do during dynamic dispatch is coerce the "fat" receiver, where Self = dyn Trait, to the "thin" version without the vtable, so it can be passed as an argument to the function that we looked up in the vtable. The tricky thing is, we don't know what the type of Self is, and part of doing the coercion and passing the coerced receiver to the function call is that we need to compute the layout of that type. We need the layout so that we can tell llvm the FnType of the function we're calling, and the layout (and abi) of the function's argument; not to mention it would probably be useful to know the layout when implementing the actual coercion. But to compute the layout of a type, we need an actual type to use.

So the question is, what type do we use for Self once we've removed the vtable? This is what we need to talk about. A couple ideas have been thrown around:
- using ()
- adding a new variant to TyVariants. One thing I was thinking of was a companion to Dynamic, which takes the same arguments (existential predicates and a lifetime), and implements all the same traits, plus Sized. Except it doesn't really implement those traits, because you couldn't actually call any methods or functions on it. :confused:
- you mentioned something about using the type parameter from the DispatchFromDyn impl. Feel free to expand on that if you think it's something worth pursuing

eddyb (Apr 26 2019 at 06:52, on Zulip):

so, () is outright incorrect (because the type might have bounds on that) and a new variant of Ty is not necessary

eddyb (Apr 26 2019 at 06:53, on Zulip):

my idea with the DispatchFromDyn impl was that we could "run it in reverse", to get the e.g. Rc<T>, but we keep the T unsubstituted

eddyb (Apr 26 2019 at 06:53, on Zulip):

so it's as if we're doing polymorphic compilation w/o monomorphization

eddyb (Apr 26 2019 at 06:53, on Zulip):

alternatively, we could use some of the Chalk infra

eddyb (Apr 26 2019 at 06:53, on Zulip):

"canonicalization"

eddyb (Apr 26 2019 at 06:54, on Zulip):

I don't think general is the correct place for this though, but cc @nikomatsakis

RalfJ (Apr 26 2019 at 08:35, on Zulip):

no matter what you end up doing, I'd appreciate help realizing this not just in the LLVM backend but also in Miri :D

RalfJ (Apr 26 2019 at 08:35, on Zulip):

getting "by-value" receivers to work was already lots of guesswork, no idea if I did that right

eddyb (Apr 26 2019 at 08:36, on Zulip):

it might be simpler than the hack we do right now

eddyb (Apr 26 2019 at 08:36, on Zulip):

I just didn't think we could get it to work, because I think we came up with it before DispatchFromDyn was settled

RalfJ (Apr 26 2019 at 08:38, on Zulip):

(FWIW, the current thing is at https://github.com/rust-lang/rust/blob/master/src/librustc_mir/interpret/terminator.rs#L409 )

eddyb (Apr 26 2019 at 08:38, on Zulip):

@mikeyhew ugh, ty::Param is suboptimal because you could have Foo<T, X> and X could be unmonomorphized or w/e (maybe in miri, or maybe in codegen, in the future)

eddyb (Apr 26 2019 at 08:39, on Zulip):

so we'll probably have to use ty::Bound

eddyb (Apr 26 2019 at 08:39, on Zulip):

which is an universal/existential (not sure) bound variable from Chalk

mikeyhew (Apr 26 2019 at 08:47, on Zulip):

@eddyb what would using ty::Bound look like?

eddyb (Apr 26 2019 at 08:48, on Zulip):

@mikeyhew you substitute the T in the DispatchFromDyn impl with a ty::Bound

eddyb (Apr 26 2019 at 08:49, on Zulip):

well, hmpf. we'd need more analyses on the DispatchFromDyn impl to determine what the type should even look like

eddyb (Apr 26 2019 at 08:49, on Zulip):

it's, like,

eddyb (Apr 26 2019 at 08:49, on Zulip):

we have impl<...> DispatchFromDyn<Foo<A, B>> for Foo<X, Y>

mikeyhew (Apr 26 2019 at 08:50, on Zulip):

OK, so let's say we have

impl<T: ?Sized, U: ?Sized, A> DispatchFromDyn<Box<U, A>> for Box<T, A>
where
    T: Unsize<U>
{}
eddyb (Apr 26 2019 at 08:50, on Zulip):

the impl type parameters used in Self (so in Foo<X, Y>), but not in the trait's parameter (Foo<A, B>)

eddyb (Apr 26 2019 at 08:50, on Zulip):

are the ones you need to "instantiate" when you want to dispatch

eddyb (Apr 26 2019 at 08:50, on Zulip):

uhmmm

eddyb (Apr 26 2019 at 08:50, on Zulip):

T: ?Sized is wrong

eddyb (Apr 26 2019 at 08:50, on Zulip):

if you allow that today, something is broken somewhere

mikeyhew (Apr 26 2019 at 08:51, on Zulip):

details

eddyb (Apr 26 2019 at 08:51, on Zulip):

the reason Unsize allows it is Box<dyn Trait+Send> -> Box<dyn Trait> is a coercion

eddyb (Apr 26 2019 at 08:51, on Zulip):

nope!

eddyb (Apr 26 2019 at 08:51, on Zulip):

without the Sized bound on T in the ParamEnv, none of this can ever work!

mikeyhew (Apr 26 2019 at 08:51, on Zulip):

Ok, you're right

eddyb (Apr 26 2019 at 08:51, on Zulip):

a Sized bound "in scope" means *mut T has a known layout without knowing T

mikeyhew (Apr 26 2019 at 08:52, on Zulip):

So anyway, assuming we can figure out that T/U is type that changes...

eddyb (Apr 26 2019 at 08:52, on Zulip):

and I think we can instantiate all the parameters I was talking about (i.e. T in this case) with ty::Bound (talk to @nikomatsakis maybe? not sure how those work, but they could be like type parameters, just simpler)

eddyb (Apr 26 2019 at 08:54, on Zulip):

you don't need to know anything about the U, just be able to find that impl and get a Box<T, MyAlloc> from a Box<Whatever, MyAlloc>

eddyb (Apr 26 2019 at 08:56, on Zulip):

I guess by using the trait system and asking for X and Y in Box<X, Y> where Box<X, Y>: DispatchFromDyn<Box<Whatever, MyAlloc>>

eddyb (Apr 26 2019 at 08:56, on Zulip):

wait

mikeyhew (Apr 26 2019 at 08:56, on Zulip):

"replace it with ty::Bound" sounds nice, but I have no idea what that really means - can you elaborate on how to do that? ty::Bound has arguments

eddyb (Apr 26 2019 at 08:56, on Zulip):

ugh, the direction of this might be hard to do trait dispatch with

eddyb (Apr 26 2019 at 08:56, on Zulip):

oh, you'd just use whatever works for those :P

mikeyhew (Apr 26 2019 at 08:57, on Zulip):
/// Bound type variable, used only when preparing a trait query.
    Bound(ty::DebruijnIndex, BoundTy),
eddyb (Apr 26 2019 at 08:57, on Zulip):

maybe Bound is wrong and I mean Placeholder?

eddyb (Apr 26 2019 at 08:57, on Zulip):

some of this is a bit weird

mikeyhew (Apr 26 2019 at 08:58, on Zulip):
/// A placeholder type - universally quantified higher-ranked type.
    Placeholder(ty::PlaceholderType),
eddyb (Apr 26 2019 at 08:58, on Zulip):

but you can just use debruijin index 0 and BoundVar index 0

eddyb (Apr 26 2019 at 08:58, on Zulip):

and BoundTyKind::Anon

eddyb (Apr 26 2019 at 08:59, on Zulip):

it really doesn't matter, beyond two very important things:

eddyb (Apr 26 2019 at 09:00, on Zulip):

(if you need multiple, you can use further BoundVar indices)

mikeyhew (Apr 26 2019 at 09:08, on Zulip):

Grepping through the rust-lang/rust source, I don't see ty::Bound being used in a way that I can learn from. If there's a solution involving it, I'd love to hear about it, but I'd need someone to explain to me how it works before I can implement anything with it

eddyb (Apr 26 2019 at 09:17, on Zulip):

@mikeyhew you just use it like you might use, idk, ty::Err

eddyb (Apr 26 2019 at 09:18, on Zulip):

you just put it where the unknown is

eddyb (Apr 26 2019 at 09:18, on Zulip):

@mikeyhew I guess a better analogy is an inference variable, but this sort of thing is not restricted from appearing in a global tcx

eddyb (Apr 26 2019 at 09:19, on Zulip):

and it seems reasonable to allow layout to handle it

eddyb (Apr 26 2019 at 09:19, on Zulip):

you could use ty::Param directly, from the impl, I'm just worried about bad interactions in the future

eddyb (Apr 26 2019 at 09:22, on Zulip):

again, it doesn't matter what you use, but you need something like Rc<StrangeThing>, where if you have StrangeThing: Trait in ParamEnv, the trait system will actually consider that

eddyb (Apr 26 2019 at 09:23, on Zulip):

because the impl has a T: Sized bound in its ParamEnv so when you substitute [T -> StrangeThing], you'll get StrangeThing: Sized, which is important for ensuring *mut RcBox<StrangeThing> is actually a thin pointer

Last update: Nov 20 2019 at 12:45UTC