1 use crate::errors
::DumpVTableEntries
;
2 use crate::traits
::{impossible_predicates, is_vtable_safe_method}
;
3 use rustc_hir
::def_id
::DefId
;
4 use rustc_hir
::lang_items
::LangItem
;
5 use rustc_infer
::traits
::util
::PredicateSet
;
6 use rustc_infer
::traits
::ImplSource
;
7 use rustc_middle
::query
::Providers
;
8 use rustc_middle
::traits
::BuiltinImplSource
;
9 use rustc_middle
::ty
::visit
::TypeVisitableExt
;
10 use rustc_middle
::ty
::GenericArgs
;
11 use rustc_middle
::ty
::{self, GenericParamDefKind, ToPredicate, Ty, TyCtxt, VtblEntry}
;
12 use rustc_span
::{sym, Span}
;
13 use smallvec
::SmallVec
;
16 use std
::ops
::ControlFlow
;
18 #[derive(Clone, Debug)]
19 pub enum VtblSegment
<'tcx
> {
21 TraitOwnEntries { trait_ref: ty::PolyTraitRef<'tcx>, emit_vptr: bool }
,
24 /// Prepare the segments for a vtable
25 pub fn prepare_vtable_segments
<'tcx
, T
>(
27 trait_ref
: ty
::PolyTraitRef
<'tcx
>,
28 segment_visitor
: impl FnMut(VtblSegment
<'tcx
>) -> ControlFlow
<T
>,
30 prepare_vtable_segments_inner(tcx
, trait_ref
, segment_visitor
).break_value()
33 /// Helper for [`prepare_vtable_segments`] that returns `ControlFlow`,
34 /// such that we can use `?` in the body.
35 fn prepare_vtable_segments_inner
<'tcx
, T
>(
37 trait_ref
: ty
::PolyTraitRef
<'tcx
>,
38 mut segment_visitor
: impl FnMut(VtblSegment
<'tcx
>) -> ControlFlow
<T
>,
40 // The following constraints holds for the final arrangement.
41 // 1. The whole virtual table of the first direct super trait is included as the
42 // the prefix. If this trait doesn't have any super traits, then this step
43 // consists of the dsa metadata.
44 // 2. Then comes the proper pointer metadata(vptr) and all own methods for all
45 // other super traits except those already included as part of the first
46 // direct super trait virtual table.
47 // 3. finally, the own methods of this trait.
49 // This has the advantage that trait upcasting to the first direct super trait on each level
50 // is zero cost, and to another trait includes only replacing the pointer with one level indirection,
51 // while not using too much extra memory.
53 // For a single inheritance relationship like this,
54 // D --> C --> B --> A
55 // The resulting vtable will consists of these segments:
58 // For a multiple inheritance relationship like this,
61 // The resulting vtable will consists of these segments:
62 // DSA, A, B, B-vptr, C, D
64 // For a diamond inheritance relationship like this,
67 // The resulting vtable will consists of these segments:
68 // DSA, A, B, C, C-vptr, D
70 // For a more complex inheritance relationship like this:
71 // O --> G --> C --> A
79 // The resulting vtable will consists of these segments:
80 // DSA, A, B, B-vptr, C, D, D-vptr, E, E-vptr, F, F-vptr, G,
81 // H, H-vptr, I, I-vptr, J, J-vptr, K, K-vptr, L, L-vptr, M, M-vptr,
84 // emit dsa segment first.
85 segment_visitor(VtblSegment
::MetadataDSA
)?
;
87 let mut emit_vptr_on_new_entry
= false;
88 let mut visited
= PredicateSet
::new(tcx
);
89 let predicate
= trait_ref
.to_predicate(tcx
);
90 let mut stack
: SmallVec
<[(ty
::PolyTraitRef
<'tcx
>, _
, _
); 5]> =
91 smallvec
![(trait_ref
, emit_vptr_on_new_entry
, maybe_iter(None
))];
92 visited
.insert(predicate
);
94 // the main traversal loop:
95 // basically we want to cut the inheritance directed graph into a few non-overlapping slices of nodes
96 // such that each node is emitted after all its descendants have been emitted.
97 // so we convert the directed graph into a tree by skipping all previously visited nodes using a visited set.
98 // this is done on the fly.
99 // Each loop run emits a slice - it starts by find a "childless" unvisited node, backtracking upwards, and it
100 // stops after it finds a node that has a next-sibling node.
101 // This next-sibling node will used as the starting point of next slice.
104 // For a diamond inheritance relationship like this,
105 // D#1 --> B#0 --> A#0
108 // Starting point 0 stack [D]
109 // Loop run #0: Stack after diving in is [D B A], A is "childless"
110 // after this point, all newly visited nodes won't have a vtable that equals to a prefix of this one.
111 // Loop run #0: Emitting the slice [B A] (in reverse order), B has a next-sibling node, so this slice stops here.
112 // Loop run #0: Stack after exiting out is [D C], C is the next starting point.
113 // Loop run #1: Stack after diving in is [D C], C is "childless", since its child A is skipped(already emitted).
114 // Loop run #1: Emitting the slice [D C] (in reverse order). No one has a next-sibling node.
115 // Loop run #1: Stack after exiting out is []. Now the function exits.
118 // dive deeper into the stack, recording the path
120 let &(inner_most_trait_ref
, _
, _
) = stack
.last().unwrap();
122 let mut direct_super_traits_iter
= tcx
123 .super_predicates_of(inner_most_trait_ref
.def_id())
126 .filter_map(move |(pred
, _
)| {
127 pred
.subst_supertrait(tcx
, &inner_most_trait_ref
).as_trait_clause()
130 // Find an unvisited supertrait
131 match direct_super_traits_iter
132 .find(|&super_trait
| visited
.insert(super_trait
.to_predicate(tcx
)))
134 // Push it to the stack for the next iteration of 'diving_in to pick up
135 Some(unvisited_super_trait
) => {
136 // We're throwing away potential constness of super traits here.
137 // FIXME: handle ~const super traits
138 let next_super_trait
= unvisited_super_trait
.map_bound(|t
| t
.trait_ref
);
141 emit_vptr_on_new_entry
,
142 maybe_iter(Some(direct_super_traits_iter
)),
146 // There are no more unvisited direct super traits, dive-in finished
147 None
=> break 'diving_in
,
151 // emit innermost item, move to next sibling and stop there if possible, otherwise jump to outer level.
152 while let Some((inner_most_trait_ref
, emit_vptr
, mut siblings
)) = stack
.pop() {
153 segment_visitor(VtblSegment
::TraitOwnEntries
{
154 trait_ref
: inner_most_trait_ref
,
155 emit_vptr
: emit_vptr
&& !tcx
.sess
.opts
.unstable_opts
.no_trait_vptr
,
158 // If we've emitted (fed to `segment_visitor`) a trait that has methods present in the vtable,
159 // we'll need to emit vptrs from now on.
160 if !emit_vptr_on_new_entry
161 && has_own_existential_vtable_entries(tcx
, inner_most_trait_ref
.def_id())
163 emit_vptr_on_new_entry
= true;
166 if let Some(next_inner_most_trait_ref
) =
167 siblings
.find(|&sibling
| visited
.insert(sibling
.to_predicate(tcx
)))
169 // We're throwing away potential constness of super traits here.
170 // FIXME: handle ~const super traits
171 let next_inner_most_trait_ref
=
172 next_inner_most_trait_ref
.map_bound(|t
| t
.trait_ref
);
174 stack
.push((next_inner_most_trait_ref
, emit_vptr_on_new_entry
, siblings
));
176 // just pushed a new trait onto the stack, so we need to go through its super traits
181 // the stack is empty, all done
182 return ControlFlow
::Continue(());
186 /// Turns option of iterator into an iterator (this is just flatten)
187 fn maybe_iter
<I
: Iterator
>(i
: Option
<I
>) -> impl Iterator
<Item
= I
::Item
> {
188 // Flatten is bad perf-vise, we could probably implement a special case here that is better
189 i
.into_iter().flatten()
192 fn dump_vtable_entries
<'tcx
>(
195 trait_ref
: ty
::PolyTraitRef
<'tcx
>,
196 entries
: &[VtblEntry
<'tcx
>],
198 tcx
.sess
.emit_err(DumpVTableEntries { span: sp, trait_ref, entries: format!("{entries:#?}
") });
201 fn has_own_existential_vtable_entries(tcx: TyCtxt<'_>, trait_def_id: DefId) -> bool {
202 own_existential_vtable_entries_iter(tcx, trait_def_id).next().is_some()
205 fn own_existential_vtable_entries(tcx: TyCtxt<'_>, trait_def_id: DefId) -> &[DefId] {
206 tcx.arena.alloc_from_iter(own_existential_vtable_entries_iter(tcx, trait_def_id))
209 fn own_existential_vtable_entries_iter(
212 ) -> impl Iterator<Item = DefId> + '_ {
213 let trait_methods = tcx
214 .associated_items(trait_def_id)
215 .in_definition_order()
216 .filter(|item| item.kind == ty::AssocKind::Fn);
218 // Now list each method's DefId (for within its trait).
219 let own_entries = trait_methods.filter_map(move |&trait_method| {
220 debug!("own_existential_vtable_entry
: trait_method
={:?}
", trait_method);
221 let def_id = trait_method.def_id;
223 // Some methods cannot be called on an object; skip those.
224 if !is_vtable_safe_method(tcx, trait_def_id, trait_method) {
225 debug!("own_existential_vtable_entry
: not vtable safe
");
235 /// Given a trait `trait_ref`, iterates the vtable entries
236 /// that come from `trait_ref`, including its supertraits.
237 fn vtable_entries<'tcx>(
239 trait_ref: ty::PolyTraitRef<'tcx>,
240 ) -> &'tcx [VtblEntry<'tcx>] {
241 debug!("vtable_entries({:?}
)", trait_ref);
243 let mut entries = vec![];
245 let vtable_segment_callback = |segment| -> ControlFlow<()> {
247 VtblSegment::MetadataDSA => {
248 entries.extend(TyCtxt::COMMON_VTABLE_ENTRIES);
250 VtblSegment::TraitOwnEntries { trait_ref, emit_vptr } => {
251 let existential_trait_ref = trait_ref
252 .map_bound(|trait_ref| ty::ExistentialTraitRef::erase_self_ty(tcx, trait_ref));
254 // Lookup the shape of vtable for the trait.
255 let own_existential_entries =
256 tcx.own_existential_vtable_entries(existential_trait_ref.def_id());
258 let own_entries = own_existential_entries.iter().copied().map(|def_id| {
259 debug!("vtable_entries
: trait_method
={:?}
", def_id);
261 // The method may have some early-bound lifetimes; add regions for those.
262 let args = trait_ref.map_bound(|trait_ref| {
263 GenericArgs::for_item(tcx, def_id, |param, _| match param.kind {
264 GenericParamDefKind::Lifetime => tcx.lifetimes.re_erased.into(),
265 GenericParamDefKind::Type { .. }
266 | GenericParamDefKind::Const { .. } => {
267 trait_ref.args[param.index as usize]
272 // The trait type may have higher-ranked lifetimes in it;
273 // erase them if they appear, so that we get the type
274 // at some particular call site.
276 tcx.normalize_erasing_late_bound_regions(ty::ParamEnv::reveal_all(), args);
278 // It's possible that the method relies on where-clauses that
279 // do not hold for this particular set of type parameters.
280 // Note that this method could then never be called, so we
281 // do not want to try and codegen it, in that case (see #23435).
282 let predicates = tcx.predicates_of(def_id).instantiate_own(tcx, args);
283 if impossible_predicates(
285 predicates.map(|(predicate, _)| predicate).collect(),
287 debug!("vtable_entries
: predicates
do not hold
");
288 return VtblEntry::Vacant;
291 let instance = ty::Instance::resolve_for_vtable(
293 ty::ParamEnv::reveal_all(),
297 .expect("resolution failed during building vtable representation
");
298 VtblEntry::Method(instance)
301 entries.extend(own_entries);
304 entries.push(VtblEntry::TraitVPtr(trait_ref));
309 ControlFlow::Continue(())
312 let _ = prepare_vtable_segments(tcx, trait_ref, vtable_segment_callback);
314 if tcx.has_attr(trait_ref.def_id(), sym::rustc_dump_vtable) {
315 let sp = tcx.def_span(trait_ref.def_id());
316 dump_vtable_entries(tcx, sp, trait_ref, &entries);
319 tcx.arena.alloc_from_iter(entries.into_iter())
322 /// Find slot base for trait methods within vtable entries of another trait
323 pub(super) fn vtable_trait_first_method_offset<'tcx>(
326 ty::PolyTraitRef<'tcx>, // trait_to_be_found
327 ty::PolyTraitRef<'tcx>, // trait_owning_vtable
330 let (trait_to_be_found, trait_owning_vtable) = key;
333 let trait_to_be_found_erased = tcx.erase_regions(trait_to_be_found);
335 let vtable_segment_callback = {
336 let mut vtable_base = 0;
340 VtblSegment::MetadataDSA => {
341 vtable_base += TyCtxt::COMMON_VTABLE_ENTRIES.len();
343 VtblSegment::TraitOwnEntries { trait_ref, emit_vptr } => {
344 if tcx.erase_regions(trait_ref) == trait_to_be_found_erased {
345 return ControlFlow::Break(vtable_base);
347 vtable_base += count_own_vtable_entries(tcx, trait_ref);
353 ControlFlow::Continue(())
357 if let Some(vtable_base) =
358 prepare_vtable_segments(tcx, trait_owning_vtable, vtable_segment_callback)
362 bug!("Failed to find info
for expected
trait in vtable
");
366 /// Find slot offset for trait vptr within vtable entries of another trait
367 pub(crate) fn vtable_trait_upcasting_coercion_new_vptr_slot<'tcx>(
370 Ty<'tcx>, // trait object type whose trait owning vtable
371 Ty<'tcx>, // trait object for supertrait
374 let (source, target) = key;
375 assert!(matches!(&source.kind(), &ty::Dynamic(..)) && !source.has_infer());
376 assert!(matches!(&target.kind(), &ty::Dynamic(..)) && !target.has_infer());
378 // this has been typecked-before, so diagnostics is not really needed.
379 let unsize_trait_did = tcx.require_lang_item(LangItem::Unsize, None);
381 let trait_ref = ty::TraitRef::new(tcx, unsize_trait_did, [source, target]);
383 match tcx.codegen_select_candidate((ty::ParamEnv::reveal_all(), trait_ref)) {
384 Ok(ImplSource::Builtin(BuiltinImplSource::TraitUpcasting { vtable_vptr_slot }, _)) => {
387 otherwise => bug!("expected TraitUpcasting candidate
, got {otherwise:?}
"),
391 /// Given a trait `trait_ref`, returns the number of vtable entries
392 /// that come from `trait_ref`, excluding its supertraits. Used in
393 /// computing the vtable base for an upcast trait of a trait object.
394 pub(crate) fn count_own_vtable_entries<'tcx>(
396 trait_ref: ty::PolyTraitRef<'tcx>,
398 tcx.own_existential_vtable_entries(trait_ref.def_id()).len()
401 pub(super) fn provide(providers: &mut Providers) {
402 *providers = Providers {
403 own_existential_vtable_entries,
405 vtable_trait_upcasting_coercion_new_vptr_slot,