Auto merge of #54383 - mikeyhew:custom-receivers-object-safety, r=nikomatsakis

Take 2: Implement object-safety and dynamic dispatch for arbitrary_self_types

This replaces #50173. Over the months that that PR was open, we made a lot of changes to the way this was going to be implemented, and the long, meandering comment thread and commit history would have been confusing to people reading it in the future. So I decided to package everything up with new, straighforward commits and open a new PR.

Here are the main points. Please read the commit messages for details.

- To simplify codegen, we only support receivers that have the ABI of a pointer. That means they are builtin pointer types, or newtypes thereof.
- We introduce a new trait: `DispatchFromDyn<T>`, similar to `CoerceUnsized<T>`. `DispatchFromDyn` has extra requirements that `CoerceUnsized` does not: when you implement `DispatchFromDyn` for a struct, there cannot be any extra fields besides the field being coerced and `PhantomData` fields. This ensures that the struct's ABI is the same as a pointer.
- For a method's receiver (e.g. `self: Rc<Self>`) to be object-safe, it needs to have the following property:
    - let `DynReceiver` be the receiver when `Self = dyn Trait`
    - let `ConcreteReceiver` be the receiver when `Self = T`, where `T` is some unknown `Sized` type that implements `Trait`, and is the erased type of the trait object.
    - `ConcreteReceiver` must implement `DispatchFromDyn<DynReceiver>`

In the case of `Rc<Self>`, this requires `Rc<T>: DispatchFromDyn<Rc<dyn Trait>>`

These rules are explained more thoroughly in the doc comment on `receiver_is_dispatchable` in object_safety.rs.

r? @nikomatsakis and @eddyb

cc @arielb1 @cramertj @withoutboats

Special thanks to @nikomatsakis for getting me un-stuck when implementing the object-safety checks, and @eddyb for helping with the codegen parts.

EDIT 2018-11-01: updated because CoerceSized has been replaced with DispatchFromDyn

2 files changed, 79 insertions, 19 deletions

diff --git a/src/librustc_codegen_llvm/abi.rs b/src/librustc_codegen_llvm/abi.rs
index 7c7662a88de..e50534a4e1d 100644
--- a/src/librustc_codegen_llvm/abi.rs
+++ b/src/librustc_codegen_llvm/abi.rs
@@ -19,7 +19,7 @@ use type_::Type;
 use type_of::{LayoutLlvmExt, PointerKind};
 use value::Value;
 
-use rustc_target::abi::{LayoutOf, Size, TyLayout};
+use rustc_target::abi::{LayoutOf, Size, TyLayout, Abi as LayoutAbi};
 use rustc::ty::{self, Ty};
 use rustc::ty::layout;
 
@@ -302,21 +302,49 @@ impl<'tcx> FnTypeExt<'tcx> for FnType<'tcx, Ty<'tcx>> {
         FnType::new_internal(cx, sig, extra_args, |ty, arg_idx| {
             let mut layout = cx.layout_of(ty);
             // Don't pass the vtable, it's not an argument of the virtual fn.
-            // Instead, pass just the (thin pointer) first field of `*dyn Trait`.
+            // Instead, pass just the data pointer, but give it the type `*const/mut dyn Trait`
+            // or `&/&mut dyn Trait` because this is special-cased elsewhere in codegen
             if arg_idx == Some(0) {
-                // FIXME(eddyb) `layout.field(cx, 0)` is not enough because e.g.
-                // `Box<dyn Trait>` has a few newtype wrappers around the raw
-                // pointer, so we'd have to "dig down" to find `*dyn Trait`.
-                let pointee = if layout.is_unsized() {
-                    layout.ty
+                let fat_pointer_ty = if layout.is_unsized() {
+                    // unsized `self` is passed as a pointer to `self`
+                    // FIXME (mikeyhew) change this to use &own if it is ever added to the language
+                    cx.tcx.mk_mut_ptr(layout.ty)
                 } else {
-                    layout.ty.builtin_deref(true)
-                        .unwrap_or_else(|| {
-                            bug!("FnType::new_vtable: non-pointer self {:?}", layout)
-                        }).ty
+                    match layout.abi {
+                        LayoutAbi::ScalarPair(..) => (),
+                        _ => bug!("receiver type has unsupported layout: {:?}", layout)
+                    }
+
+                    // In the case of Rc<Self>, we need to explicitly pass a *mut RcBox<Self>
+                    // with a Scalar (not ScalarPair) ABI. This is a hack that is understood
+                    // elsewhere in the compiler as a method on a `dyn Trait`.
+                    // To get the type `*mut RcBox<Self>`, we just keep unwrapping newtypes until we
+                    // get a built-in pointer type
+                    let mut fat_pointer_layout = layout;
+                    'descend_newtypes: while !fat_pointer_layout.ty.is_unsafe_ptr()
+                        && !fat_pointer_layout.ty.is_region_ptr()
+                    {
+                        'iter_fields: for i in 0..fat_pointer_layout.fields.count() {
+                            let field_layout = fat_pointer_layout.field(cx, i);
+
+                            if !field_layout.is_zst() {
+                                fat_pointer_layout = field_layout;
+                                continue 'descend_newtypes
+                            }
+                        }
+
+                        bug!("receiver has no non-zero-sized fields {:?}", fat_pointer_layout);
+                    }
+
+                    fat_pointer_layout.ty
                 };
-                let fat_ptr_ty = cx.tcx.mk_mut_ptr(pointee);
-                layout = cx.layout_of(fat_ptr_ty).field(cx, 0);
+
+                // we now have a type like `*mut RcBox<dyn Trait>`
+                // change its layout to that of `*mut ()`, a thin pointer, but keep the same type
+                // this is understood as a special case elsewhere in the compiler
+                let unit_pointer_ty = cx.tcx.mk_mut_ptr(cx.tcx.mk_unit());
+                layout = cx.layout_of(unit_pointer_ty);
+                layout.ty = fat_pointer_ty;
             }
             ArgType::new(layout)
         })
diff --git a/src/librustc_codegen_llvm/mir/block.rs b/src/librustc_codegen_llvm/mir/block.rs
index d98b7869ae9..a7f4c48c89b 100644
--- a/src/librustc_codegen_llvm/mir/block.rs
+++ b/src/librustc_codegen_llvm/mir/block.rs
@@ -642,14 +642,46 @@ impl FunctionCx<'a, 'll, 'tcx> {
                     (&args[..], None)
                 };
 
-                for (i, arg) in first_args.iter().enumerate() {
+                'make_args: for (i, arg) in first_args.iter().enumerate() {
                     let mut op = self.codegen_operand(&bx, arg);
+
                     if let (0, Some(ty::InstanceDef::Virtual(_, idx))) = (i, def) {
-                        if let Pair(data_ptr, meta) = op.val {
-                            llfn = Some(meth::VirtualIndex::from_index(idx)
-                                .get_fn(&bx, meta, &fn_ty));
-                            llargs.push(data_ptr);
-                            continue;
+                        if let Pair(..) = op.val {
+                            // In the case of Rc<Self>, we need to explicitly pass a
+                            // *mut RcBox<Self> with a Scalar (not ScalarPair) ABI. This is a hack
+                            // that is understood elsewhere in the compiler as a method on
+                            // `dyn Trait`.
+                            // To get a `*mut RcBox<Self>`, we just keep unwrapping newtypes until
+                            // we get a value of a built-in pointer type
+                            'descend_newtypes: while !op.layout.ty.is_unsafe_ptr()
+                                            && !op.layout.ty.is_region_ptr()
+                            {
+                                'iter_fields: for i in 0..op.layout.fields.count() {
+                                    let field = op.extract_field(&bx, i);
+                                    if !field.layout.is_zst() {
+                                        // we found the one non-zero-sized field that is allowed
+                                        // now find *its* non-zero-sized field, or stop if it's a
+                                        // pointer
+                                        op = field;
+                                        continue 'descend_newtypes
+                                    }
+                                }
+
+                                span_bug!(span, "receiver has no non-zero-sized fields {:?}", op);
+                            }
+
+                            // now that we have `*dyn Trait` or `&dyn Trait`, split it up into its
+                            // data pointer and vtable. Look up the method in the vtable, and pass
+                            // the data pointer as the first argument
+                            match op.val {
+                                Pair(data_ptr, meta) => {
+                                    llfn = Some(meth::VirtualIndex::from_index(idx)
+                                        .get_fn(&bx, meta, &fn_ty));
+                                    llargs.push(data_ptr);
+                                    continue 'make_args
+                                }
+                                other => bug!("expected a Pair, got {:?}", other)
+                            }
                         } else if let Ref(data_ptr, Some(meta), _) = op.val {
                             // by-value dynamic dispatch
                             llfn = Some(meth::VirtualIndex::from_index(idx)