add a Vtable kind of symbolic allocations

11 files changed, 106 insertions, 15 deletions

diff --git a/compiler/rustc_codegen_cranelift/src/constant.rs b/compiler/rustc_codegen_cranelift/src/constant.rs
index 48972321a9f..389ff7231b0 100644
--- a/compiler/rustc_codegen_cranelift/src/constant.rs
+++ b/compiler/rustc_codegen_cranelift/src/constant.rs
@@ -195,9 +195,13 @@ pub(crate) fn codegen_const_value<'tcx>(
             }
             Scalar::Ptr(ptr, _size) => {
                 let (alloc_id, offset) = ptr.into_parts(); // we know the `offset` is relative
-                let alloc_kind = fx.tcx.get_global_alloc(alloc_id);
-                let base_addr = match alloc_kind {
-                    Some(GlobalAlloc::Memory(alloc)) => {
+                // For vtables, get the underlying data allocation.
+                let alloc_id = match fx.tcx.global_alloc(alloc_id) {
+                    GlobalAlloc::Vtable(ty, trait_ref) => fx.tcx.vtable_allocation((ty, trait_ref)),
+                    _ => alloc_id,
+                };
+                let base_addr = match fx.tcx.global_alloc(alloc_id) {
+                    GlobalAlloc::Memory(alloc) => {
                         let data_id = data_id_for_alloc_id(
                             &mut fx.constants_cx,
                             fx.module,
@@ -211,13 +215,14 @@ pub(crate) fn codegen_const_value<'tcx>(
                         }
                         fx.bcx.ins().global_value(fx.pointer_type, local_data_id)
                     }
-                    Some(GlobalAlloc::Function(instance)) => {
+                    GlobalAlloc::Function(instance) => {
                         let func_id = crate::abi::import_function(fx.tcx, fx.module, instance);
                         let local_func_id =
                             fx.module.declare_func_in_func(func_id, &mut fx.bcx.func);
                         fx.bcx.ins().func_addr(fx.pointer_type, local_func_id)
                     }
-                    Some(GlobalAlloc::Static(def_id)) => {
+                    GlobalAlloc::Vtable(..) => bug!("vtables are already handled"),
+                    GlobalAlloc::Static(def_id) => {
                         assert!(fx.tcx.is_static(def_id));
                         let data_id = data_id_for_static(fx.tcx, fx.module, def_id, false);
                         let local_data_id =
@@ -227,7 +232,6 @@ pub(crate) fn codegen_const_value<'tcx>(
                         }
                         fx.bcx.ins().global_value(fx.pointer_type, local_data_id)
                     }
-                    None => bug!("missing allocation {:?}", alloc_id),
                 };
                 let val = if offset.bytes() != 0 {
                     fx.bcx.ins().iadd_imm(base_addr, i64::try_from(offset.bytes()).unwrap())
@@ -360,7 +364,9 @@ fn define_all_allocs(tcx: TyCtxt<'_>, module: &mut dyn Module, cx: &mut Constant
                 //println!("alloc_id {}", alloc_id);
                 let alloc = match tcx.get_global_alloc(alloc_id).unwrap() {
                     GlobalAlloc::Memory(alloc) => alloc,
-                    GlobalAlloc::Function(_) | GlobalAlloc::Static(_) => unreachable!(),
+                    GlobalAlloc::Function(_) | GlobalAlloc::Static(_) | GlobalAlloc::Vtable(..) => {
+                        unreachable!()
+                    }
                 };
                 let data_id = *cx.anon_allocs.entry(alloc_id).or_insert_with(|| {
                     module
@@ -424,7 +430,7 @@ fn define_all_allocs(tcx: TyCtxt<'_>, module: &mut dyn Module, cx: &mut Constant
                 read_target_uint(endianness, bytes).unwrap()
             };
 
-            let reloc_target_alloc = tcx.get_global_alloc(alloc_id).unwrap();
+            let reloc_target_alloc = tcx.global_alloc(alloc_id);
             let data_id = match reloc_target_alloc {
                 GlobalAlloc::Function(instance) => {
                     assert_eq!(addend, 0);
@@ -436,6 +442,10 @@ fn define_all_allocs(tcx: TyCtxt<'_>, module: &mut dyn Module, cx: &mut Constant
                 GlobalAlloc::Memory(target_alloc) => {
                     data_id_for_alloc_id(cx, module, alloc_id, target_alloc.inner().mutability)
                 }
+                GlobalAlloc::Vtable(ty, trait_ref) => {
+                    let alloc_id = tcx.vtable_allocation((ty, trait_ref));
+                    data_id_for_alloc_id(cx, module, alloc_id, Mutability::Not)
+                }
                 GlobalAlloc::Static(def_id) => {
                     if tcx.codegen_fn_attrs(def_id).flags.contains(CodegenFnAttrFlags::THREAD_LOCAL)
                     {
diff --git a/compiler/rustc_codegen_gcc/src/common.rs b/compiler/rustc_codegen_gcc/src/common.rs
index fc391f53f18..3868f2f7a49 100644
--- a/compiler/rustc_codegen_gcc/src/common.rs
+++ b/compiler/rustc_codegen_gcc/src/common.rs
@@ -183,6 +183,13 @@ impl<'gcc, 'tcx> ConstMethods<'tcx> for CodegenCx<'gcc, 'tcx> {
             }
             Scalar::Ptr(ptr, _size) => {
                 let (alloc_id, offset) = ptr.into_parts();
+                // For vtables, get the underlying data allocation.
+                let alloc_id = match self.tcx.global_alloc(alloc_id) {
+                    GlobalAlloc::Vtable(ty, trait_ref) => {
+                        self.tcx.vtable_allocation((ty, trait_ref))
+                    }
+                    _ => alloc_id,
+                };
                 let base_addr =
                     match self.tcx.global_alloc(alloc_id) {
                         GlobalAlloc::Memory(alloc) => {
@@ -201,6 +208,7 @@ impl<'gcc, 'tcx> ConstMethods<'tcx> for CodegenCx<'gcc, 'tcx> {
                         GlobalAlloc::Function(fn_instance) => {
                             self.get_fn_addr(fn_instance)
                         },
+                        GlobalAlloc::Vtable(..) => panic!("vtables are already handled"),
                         GlobalAlloc::Static(def_id) => {
                             assert!(self.tcx.is_static(def_id));
                             self.get_static(def_id).get_address(None)
diff --git a/compiler/rustc_codegen_llvm/src/common.rs b/compiler/rustc_codegen_llvm/src/common.rs
index 77cbbf4c6ca..b465f65fcab 100644
--- a/compiler/rustc_codegen_llvm/src/common.rs
+++ b/compiler/rustc_codegen_llvm/src/common.rs
@@ -240,6 +240,13 @@ impl<'ll, 'tcx> ConstMethods<'tcx> for CodegenCx<'ll, 'tcx> {
             }
             Scalar::Ptr(ptr, _size) => {
                 let (alloc_id, offset) = ptr.into_parts();
+                // For vtables, get the underlying data allocation.
+                let alloc_id = match self.tcx.global_alloc(alloc_id) {
+                    GlobalAlloc::Vtable(ty, trait_ref) => {
+                        self.tcx.vtable_allocation((ty, trait_ref))
+                    }
+                    _ => alloc_id,
+                };
                 let (base_addr, base_addr_space) = match self.tcx.global_alloc(alloc_id) {
                     GlobalAlloc::Memory(alloc) => {
                         let init = const_alloc_to_llvm(self, alloc);
@@ -257,6 +264,7 @@ impl<'ll, 'tcx> ConstMethods<'tcx> for CodegenCx<'ll, 'tcx> {
                         self.get_fn_addr(fn_instance.polymorphize(self.tcx)),
                         self.data_layout().instruction_address_space,
                     ),
+                    GlobalAlloc::Vtable(..) => bug!("vtables are already handled"),
                     GlobalAlloc::Static(def_id) => {
                         assert!(self.tcx.is_static(def_id));
                         assert!(!self.tcx.is_thread_local_static(def_id));
diff --git a/compiler/rustc_codegen_llvm/src/consts.rs b/compiler/rustc_codegen_llvm/src/consts.rs
index 2b16ae1a88d..1fef22796dd 100644
--- a/compiler/rustc_codegen_llvm/src/consts.rs
+++ b/compiler/rustc_codegen_llvm/src/consts.rs
@@ -101,7 +101,9 @@ pub fn const_alloc_to_llvm<'ll>(cx: &CodegenCx<'ll, '_>, alloc: ConstAllocation<
 
         let address_space = match cx.tcx.global_alloc(alloc_id) {
             GlobalAlloc::Function(..) => cx.data_layout().instruction_address_space,
-            GlobalAlloc::Static(..) | GlobalAlloc::Memory(..) => AddressSpace::DATA,
+            GlobalAlloc::Static(..) | GlobalAlloc::Memory(..) | GlobalAlloc::Vtable(..) => {
+                AddressSpace::DATA
+            }
         };
 
         llvals.push(cx.scalar_to_backend(
diff --git a/compiler/rustc_const_eval/src/interpret/memory.rs b/compiler/rustc_const_eval/src/interpret/memory.rs
index b665b210960..5d6620d8782 100644
--- a/compiler/rustc_const_eval/src/interpret/memory.rs
+++ b/compiler/rustc_const_eval/src/interpret/memory.rs
@@ -62,6 +62,8 @@ pub enum AllocKind {
     LiveData,
     /// A function allocation (that fn ptrs point to).
     Function,
+    /// A (symbolic) vtable allocation.
+    Vtable,
     /// A dead allocation.
     Dead,
 }
@@ -291,6 +293,9 @@ impl<'mir, 'tcx: 'mir, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> {
                 Some(GlobalAlloc::Function(..)) => {
                     err_ub_format!("deallocating {alloc_id:?}, which is a function")
                 }
+                Some(GlobalAlloc::Vtable(..)) => {
+                    err_ub_format!("deallocating {alloc_id:?}, which is a vtable")
+                }
                 Some(GlobalAlloc::Static(..) | GlobalAlloc::Memory(..)) => {
                     err_ub_format!("deallocating {alloc_id:?}, which is static memory")
                 }
@@ -479,6 +484,7 @@ impl<'mir, 'tcx: 'mir, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> {
                 (mem, None)
             }
             Some(GlobalAlloc::Function(..)) => throw_ub!(DerefFunctionPointer(id)),
+            Some(GlobalAlloc::Vtable(..)) => throw_ub!(DerefVtablePointer(id)),
             None => throw_ub!(PointerUseAfterFree(id)),
             Some(GlobalAlloc::Static(def_id)) => {
                 assert!(self.tcx.is_static(def_id));
@@ -678,6 +684,10 @@ impl<'mir, 'tcx: 'mir, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> {
                 (alloc.size(), alloc.align, AllocKind::LiveData)
             }
             Some(GlobalAlloc::Function(_)) => bug!("We already checked function pointers above"),
+            Some(GlobalAlloc::Vtable(..)) => {
+                // No data to be accessed here.
+                return (Size::ZERO, Align::ONE, AllocKind::Vtable);
+            }
             // The rest must be dead.
             None => {
                 // Deallocated pointers are allowed, we should be able to find
@@ -840,7 +850,13 @@ impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> std::fmt::Debug for DumpAllocs<'a,
                             )?;
                         }
                         Some(GlobalAlloc::Function(func)) => {
-                            write!(fmt, " (fn: {})", func)?;
+                            write!(fmt, " (fn: {func})")?;
+                        }
+                        Some(GlobalAlloc::Vtable(ty, Some(trait_ref))) => {
+                            write!(fmt, " (vtable: impl {trait_ref} for {ty})")?;
+                        }
+                        Some(GlobalAlloc::Vtable(ty, None)) => {
+                            write!(fmt, " (vtable: impl ? for {ty})")?;
                         }
                         Some(GlobalAlloc::Static(did)) => {
                             write!(fmt, " (static: {})", self.ecx.tcx.def_path_str(did))?;
diff --git a/compiler/rustc_middle/src/mir/interpret/error.rs b/compiler/rustc_middle/src/mir/interpret/error.rs
index 795f23edb31..68559ae2249 100644
--- a/compiler/rustc_middle/src/mir/interpret/error.rs
+++ b/compiler/rustc_middle/src/mir/interpret/error.rs
@@ -271,6 +271,8 @@ pub enum UndefinedBehaviorInfo<'tcx> {
     WriteToReadOnly(AllocId),
     // Trying to access the data behind a function pointer.
     DerefFunctionPointer(AllocId),
+    // Trying to access the data behind a vtable pointer.
+    DerefVtablePointer(AllocId),
     /// The value validity check found a problem.
     /// Should only be thrown by `validity.rs` and always point out which part of the value
     /// is the problem.
@@ -359,6 +361,7 @@ impl fmt::Display for UndefinedBehaviorInfo<'_> {
             ),
             WriteToReadOnly(a) => write!(f, "writing to {a:?} which is read-only"),
             DerefFunctionPointer(a) => write!(f, "accessing {a:?} which contains a function"),
+            DerefVtablePointer(a) => write!(f, "accessing {a:?} which contains a vtable"),
             ValidationFailure { path: None, msg } => {
                 write!(f, "constructing invalid value: {msg}")
             }
diff --git a/compiler/rustc_middle/src/mir/interpret/mod.rs b/compiler/rustc_middle/src/mir/interpret/mod.rs
index 698024b2330..d1039ed30b0 100644
--- a/compiler/rustc_middle/src/mir/interpret/mod.rs
+++ b/compiler/rustc_middle/src/mir/interpret/mod.rs
@@ -196,6 +196,7 @@ impl fmt::Debug for AllocId {
 enum AllocDiscriminant {
     Alloc,
     Fn,
+    Vtable,
     Static,
 }
 
@@ -215,6 +216,12 @@ pub fn specialized_encode_alloc_id<'tcx, E: TyEncoder<I = TyCtxt<'tcx>>>(
             AllocDiscriminant::Fn.encode(encoder);
             fn_instance.encode(encoder);
         }
+        GlobalAlloc::Vtable(ty, poly_trait_ref) => {
+            trace!("encoding {:?} with {ty:#?}, {poly_trait_ref:#?}", alloc_id);
+            AllocDiscriminant::Vtable.encode(encoder);
+            ty.encode(encoder);
+            poly_trait_ref.encode(encoder);
+        }
         GlobalAlloc::Static(did) => {
             assert!(!tcx.is_thread_local_static(did));
             // References to statics doesn't need to know about their allocations,
@@ -305,7 +312,7 @@ impl<'s> AllocDecodingSession<'s> {
                                 State::InProgress(TinyList::new_single(self.session_id), alloc_id);
                             Some(alloc_id)
                         }
-                        AllocDiscriminant::Fn | AllocDiscriminant::Static => {
+                        AllocDiscriminant::Fn | AllocDiscriminant::Static | AllocDiscriminant::Vtable => {
                             // Fns and statics cannot be cyclic, and their `AllocId`
                             // is determined later by interning.
                             *entry =
@@ -355,6 +362,15 @@ impl<'s> AllocDecodingSession<'s> {
                     let alloc_id = decoder.interner().create_fn_alloc(instance);
                     alloc_id
                 }
+                AllocDiscriminant::Vtable => {
+                    assert!(alloc_id.is_none());
+                    trace!("creating static alloc ID");
+                    let ty = <Ty<'_> as Decodable<D>>::decode(decoder);
+                    let poly_trait_ref = <Option<ty::PolyExistentialTraitRef<'_>> as Decodable<D>>::decode(decoder);
+                    trace!("decoded vtable alloc instance: {ty:?}, {poly_trait_ref:?}");
+                    let alloc_id = decoder.interner().create_vtable_alloc(ty, poly_trait_ref);
+                    alloc_id
+                }
                 AllocDiscriminant::Static => {
                     assert!(alloc_id.is_none());
                     trace!("creating extern static alloc ID");
@@ -380,6 +396,8 @@ impl<'s> AllocDecodingSession<'s> {
 pub enum GlobalAlloc<'tcx> {
     /// The alloc ID is used as a function pointer.
     Function(Instance<'tcx>),
+    /// This alloc ID points to a symbolic (not-reified) vtable.
+    Vtable(Ty<'tcx>, Option<ty::PolyExistentialTraitRef<'tcx>>),
     /// The alloc ID points to a "lazy" static variable that did not get computed (yet).
     /// This is also used to break the cycle in recursive statics.
     Static(DefId),
@@ -407,6 +425,16 @@ impl<'tcx> GlobalAlloc<'tcx> {
             _ => bug!("expected function, got {:?}", self),
         }
     }
+
+    /// Panics if the `GlobalAlloc` is not `GlobalAlloc::Vtable`
+    #[track_caller]
+    #[inline]
+    pub fn unwrap_vtable(&self) -> (Ty<'tcx>, Option<ty::PolyExistentialTraitRef<'tcx>>) {
+        match *self {
+            GlobalAlloc::Vtable(ty, poly_trait_ref) => (ty, poly_trait_ref),
+            _ => bug!("expected vtable, got {:?}", self),
+        }
+    }
 }
 
 pub(crate) struct AllocMap<'tcx> {
@@ -454,12 +482,12 @@ impl<'tcx> TyCtxt<'tcx> {
     }
 
     /// Reserves a new ID *if* this allocation has not been dedup-reserved before.
-    /// Should only be used for function pointers and statics, we don't want
-    /// to dedup IDs for "real" memory!
+    /// Should only be used for "symbolic" allocations (function pointers, vtables, statics), we
+    /// don't want to dedup IDs for "real" memory!
     fn reserve_and_set_dedup(self, alloc: GlobalAlloc<'tcx>) -> AllocId {
         let mut alloc_map = self.alloc_map.lock();
         match alloc {
-            GlobalAlloc::Function(..) | GlobalAlloc::Static(..) => {}
+            GlobalAlloc::Function(..) | GlobalAlloc::Static(..) | GlobalAlloc::Vtable(..) => {}
             GlobalAlloc::Memory(..) => bug!("Trying to dedup-reserve memory with real data!"),
         }
         if let Some(&alloc_id) = alloc_map.dedup.get(&alloc) {
@@ -504,6 +532,11 @@ impl<'tcx> TyCtxt<'tcx> {
         }
     }
 
+    /// Generates an `AllocId` for a (symbolic, not-reified) vtable.  Will get deduplicated.
+    pub fn create_vtable_alloc(self, ty: Ty<'tcx>, poly_trait_ref: Option<ty::PolyExistentialTraitRef<'tcx>>) -> AllocId {
+        self.reserve_and_set_dedup(GlobalAlloc::Vtable(ty, poly_trait_ref))
+    }
+
     /// Interns the `Allocation` and return a new `AllocId`, even if there's already an identical
     /// `Allocation` with a different `AllocId`.
     /// Statics with identical content will still point to the same `Allocation`, i.e.,
diff --git a/compiler/rustc_middle/src/mir/pretty.rs b/compiler/rustc_middle/src/mir/pretty.rs
index 437776ad765..120dfb5a361 100644
--- a/compiler/rustc_middle/src/mir/pretty.rs
+++ b/compiler/rustc_middle/src/mir/pretty.rs
@@ -725,6 +725,8 @@ pub fn write_allocations<'tcx>(
             // gracefully handle it and allow buggy rustc to be debugged via allocation printing.
             None => write!(w, " (deallocated)")?,
             Some(GlobalAlloc::Function(inst)) => write!(w, " (fn: {inst})")?,
+            Some(GlobalAlloc::Vtable(ty, Some(trait_ref))) => write!(w, " (vtable: impl {trait_ref} for {ty})")?,
+            Some(GlobalAlloc::Vtable(ty, None)) => write!(w, " (vtable: impl ? for {ty})")?,
             Some(GlobalAlloc::Static(did)) if !tcx.is_foreign_item(did) => {
                 match tcx.eval_static_initializer(did) {
                     Ok(alloc) => {
diff --git a/compiler/rustc_middle/src/ty/codec.rs b/compiler/rustc_middle/src/ty/codec.rs
index e6ea3d88853..51137c52659 100644
--- a/compiler/rustc_middle/src/ty/codec.rs
+++ b/compiler/rustc_middle/src/ty/codec.rs
@@ -523,4 +523,5 @@ impl_binder_encode_decode! {
     ty::ExistentialPredicate<'tcx>,
     ty::TraitRef<'tcx>,
     Vec<ty::GeneratorInteriorTypeCause<'tcx>>,
+    ty::ExistentialTraitRef<'tcx>,
 }
diff --git a/compiler/rustc_middle/src/ty/print/pretty.rs b/compiler/rustc_middle/src/ty/print/pretty.rs
index da9394128ac..d46e9ae949d 100644
--- a/compiler/rustc_middle/src/ty/print/pretty.rs
+++ b/compiler/rustc_middle/src/ty/print/pretty.rs
@@ -1282,11 +1282,12 @@ pub trait PrettyPrinter<'tcx>:
                                         p!("<too short allocation>")
                                     }
                                 }
-                                // FIXME: for statics and functions, we could in principle print more detail.
+                                // FIXME: for statics, vtables, and functions, we could in principle print more detail.
                                 Some(GlobalAlloc::Static(def_id)) => {
                                     p!(write("<static({:?})>", def_id))
                                 }
                                 Some(GlobalAlloc::Function(_)) => p!("<function>"),
+                                Some(GlobalAlloc::Vtable(..)) => p!("<vtable>"),
                                 None => p!("<dangling pointer>"),
                             }
                             return Ok(self);
diff --git a/compiler/rustc_monomorphize/src/collector.rs b/compiler/rustc_monomorphize/src/collector.rs
index e3cfb034e40..3cee9a460c1 100644
--- a/compiler/rustc_monomorphize/src/collector.rs
+++ b/compiler/rustc_monomorphize/src/collector.rs
@@ -1427,6 +1427,13 @@ fn collect_miri<'tcx>(tcx: TyCtxt<'tcx>, alloc_id: AllocId, output: &mut MonoIte
                 output.push(create_fn_mono_item(tcx, fn_instance, DUMMY_SP));
             }
         }
+        GlobalAlloc::Vtable(ty, trait_ref) => {
+            // FIXME(RJ) no ideas if this is correct. There is this nice
+            // `create_mono_items_for_vtable_methods` method but I wouldn't know how to call it from
+            // here. So instead we just generate the actual vtable and recurse.
+            let alloc_id = tcx.vtable_allocation((ty, trait_ref));
+            collect_miri(tcx, alloc_id, output)
+        }
     }
 }