Merging upstream version 1.73.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 101 insertions, 83 deletions

diff --git a/compiler/rustc_trait_selection/src/traits/vtable.rs b/compiler/rustc_trait_selection/src/traits/vtable.rs
index 1f83f1f44..427ac3684 100644
--- a/compiler/rustc_trait_selection/src/traits/vtable.rs
+++ b/compiler/rustc_trait_selection/src/traits/vtable.rs
@@ -5,8 +5,9 @@ use rustc_hir::lang_items::LangItem;
 use rustc_infer::traits::util::PredicateSet;
 use rustc_infer::traits::ImplSource;
 use rustc_middle::query::Providers;
+use rustc_middle::traits::BuiltinImplSource;
 use rustc_middle::ty::visit::TypeVisitableExt;
-use rustc_middle::ty::InternalSubsts;
+use rustc_middle::ty::GenericArgs;
 use rustc_middle::ty::{self, GenericParamDefKind, ToPredicate, Ty, TyCtxt, VtblEntry};
 use rustc_span::{sym, Span};
 use smallvec::SmallVec;
@@ -24,8 +25,18 @@ pub enum VtblSegment<'tcx> {
 pub fn prepare_vtable_segments<'tcx, T>(
     tcx: TyCtxt<'tcx>,
     trait_ref: ty::PolyTraitRef<'tcx>,
-    mut segment_visitor: impl FnMut(VtblSegment<'tcx>) -> ControlFlow<T>,
+    segment_visitor: impl FnMut(VtblSegment<'tcx>) -> ControlFlow<T>,
 ) -> Option<T> {
+    prepare_vtable_segments_inner(tcx, trait_ref, segment_visitor).break_value()
+}
+
+/// Helper for [`prepare_vtable_segments`] that returns `ControlFlow`,
+/// such that we can use `?` in the body.
+fn prepare_vtable_segments_inner<'tcx, T>(
+    tcx: TyCtxt<'tcx>,
+    trait_ref: ty::PolyTraitRef<'tcx>,
+    mut segment_visitor: impl FnMut(VtblSegment<'tcx>) -> ControlFlow<T>,
+) -> ControlFlow<T> {
     // The following constraints holds for the final arrangement.
     // 1. The whole virtual table of the first direct super trait is included as the
     //    the prefix. If this trait doesn't have any super traits, then this step
@@ -71,20 +82,18 @@ pub fn prepare_vtable_segments<'tcx, T>(
     //  N, N-vptr, O
 
     // emit dsa segment first.
-    if let ControlFlow::Break(v) = (segment_visitor)(VtblSegment::MetadataDSA) {
-        return Some(v);
-    }
+    segment_visitor(VtblSegment::MetadataDSA)?;
 
     let mut emit_vptr_on_new_entry = false;
     let mut visited = PredicateSet::new(tcx);
-    let predicate = trait_ref.without_const().to_predicate(tcx);
+    let predicate = trait_ref.to_predicate(tcx);
     let mut stack: SmallVec<[(ty::PolyTraitRef<'tcx>, _, _); 5]> =
-        smallvec![(trait_ref, emit_vptr_on_new_entry, None)];
+        smallvec![(trait_ref, emit_vptr_on_new_entry, maybe_iter(None))];
     visited.insert(predicate);
 
     // the main traversal loop:
     // basically we want to cut the inheritance directed graph into a few non-overlapping slices of nodes
-    // that each node is emitted after all its descendents have been emitted.
+    // such that each node is emitted after all its descendants have been emitted.
     // so we convert the directed graph into a tree by skipping all previously visited nodes using a visited set.
     // this is done on the fly.
     // Each loop run emits a slice - it starts by find a "childless" unvisited node, backtracking upwards, and it
@@ -105,98 +114,107 @@ pub fn prepare_vtable_segments<'tcx, T>(
     // Loop run #1: Emitting the slice [D C] (in reverse order). No one has a next-sibling node.
     // Loop run #1: Stack after exiting out is []. Now the function exits.
 
-    loop {
+    'outer: loop {
         // dive deeper into the stack, recording the path
         'diving_in: loop {
-            if let Some((inner_most_trait_ref, _, _)) = stack.last() {
-                let inner_most_trait_ref = *inner_most_trait_ref;
-                let mut direct_super_traits_iter = tcx
-                    .super_predicates_of(inner_most_trait_ref.def_id())
-                    .predicates
-                    .into_iter()
-                    .filter_map(move |(pred, _)| {
-                        pred.subst_supertrait(tcx, &inner_most_trait_ref).as_trait_clause()
-                    });
+            let &(inner_most_trait_ref, _, _) = stack.last().unwrap();
+
+            let mut direct_super_traits_iter = tcx
+                .super_predicates_of(inner_most_trait_ref.def_id())
+                .predicates
+                .into_iter()
+                .filter_map(move |(pred, _)| {
+                    pred.subst_supertrait(tcx, &inner_most_trait_ref).as_trait_clause()
+                });
 
-                'diving_in_skip_visited_traits: loop {
-                    if let Some(next_super_trait) = direct_super_traits_iter.next() {
-                        if visited.insert(next_super_trait.to_predicate(tcx)) {
-                            // We're throwing away potential constness of super traits here.
-                            // FIXME: handle ~const super traits
-                            let next_super_trait = next_super_trait.map_bound(|t| t.trait_ref);
-                            stack.push((
-                                next_super_trait,
-                                emit_vptr_on_new_entry,
-                                Some(direct_super_traits_iter),
-                            ));
-                            break 'diving_in_skip_visited_traits;
-                        } else {
-                            continue 'diving_in_skip_visited_traits;
-                        }
-                    } else {
-                        break 'diving_in;
-                    }
+            // Find an unvisited supertrait
+            match direct_super_traits_iter
+                .find(|&super_trait| visited.insert(super_trait.to_predicate(tcx)))
+            {
+                // Push it to the stack for the next iteration of 'diving_in to pick up
+                Some(unvisited_super_trait) => {
+                    // We're throwing away potential constness of super traits here.
+                    // FIXME: handle ~const super traits
+                    let next_super_trait = unvisited_super_trait.map_bound(|t| t.trait_ref);
+                    stack.push((
+                        next_super_trait,
+                        emit_vptr_on_new_entry,
+                        maybe_iter(Some(direct_super_traits_iter)),
+                    ))
                 }
+
+                // There are no more unvisited direct super traits, dive-in finished
+                None => break 'diving_in,
             }
         }
 
-        // Other than the left-most path, vptr should be emitted for each trait.
-        emit_vptr_on_new_entry = true;
-
         // emit innermost item, move to next sibling and stop there if possible, otherwise jump to outer level.
-        'exiting_out: loop {
-            if let Some((inner_most_trait_ref, emit_vptr, siblings_opt)) = stack.last_mut() {
-                if let ControlFlow::Break(v) = (segment_visitor)(VtblSegment::TraitOwnEntries {
-                    trait_ref: *inner_most_trait_ref,
-                    emit_vptr: *emit_vptr,
-                }) {
-                    return Some(v);
-                }
+        while let Some((inner_most_trait_ref, emit_vptr, mut siblings)) = stack.pop() {
+            segment_visitor(VtblSegment::TraitOwnEntries {
+                trait_ref: inner_most_trait_ref,
+                emit_vptr,
+            })?;
+
+            // If we've emitted (fed to `segment_visitor`) a trait that has methods present in the vtable,
+            // we'll need to emit vptrs from now on.
+            if !emit_vptr_on_new_entry
+                && has_own_existential_vtable_entries(tcx, inner_most_trait_ref.def_id())
+            {
+                emit_vptr_on_new_entry = true;
+            }
 
-                'exiting_out_skip_visited_traits: loop {
-                    if let Some(siblings) = siblings_opt {
-                        if let Some(next_inner_most_trait_ref) = siblings.next() {
-                            if visited.insert(next_inner_most_trait_ref.to_predicate(tcx)) {
-                                // We're throwing away potential constness of super traits here.
-                                // FIXME: handle ~const super traits
-                                let next_inner_most_trait_ref =
-                                    next_inner_most_trait_ref.map_bound(|t| t.trait_ref);
-                                *inner_most_trait_ref = next_inner_most_trait_ref;
-                                *emit_vptr = emit_vptr_on_new_entry;
-                                break 'exiting_out;
-                            } else {
-                                continue 'exiting_out_skip_visited_traits;
-                            }
-                        }
-                    }
-                    stack.pop();
-                    continue 'exiting_out;
-                }
+            if let Some(next_inner_most_trait_ref) =
+                siblings.find(|&sibling| visited.insert(sibling.to_predicate(tcx)))
+            {
+                // We're throwing away potential constness of super traits here.
+                // FIXME: handle ~const super traits
+                let next_inner_most_trait_ref =
+                    next_inner_most_trait_ref.map_bound(|t| t.trait_ref);
+
+                stack.push((next_inner_most_trait_ref, emit_vptr_on_new_entry, siblings));
+
+                // just pushed a new trait onto the stack, so we need to go through its super traits
+                continue 'outer;
             }
-            // all done
-            return None;
         }
+
+        // the stack is empty, all done
+        return ControlFlow::Continue(());
     }
 }
 
+/// Turns option of iterator into an iterator (this is just flatten)
+fn maybe_iter<I: Iterator>(i: Option<I>) -> impl Iterator<Item = I::Item> {
+    // Flatten is bad perf-vise, we could probably implement a special case here that is better
+    i.into_iter().flatten()
+}
+
 fn dump_vtable_entries<'tcx>(
     tcx: TyCtxt<'tcx>,
     sp: Span,
     trait_ref: ty::PolyTraitRef<'tcx>,
     entries: &[VtblEntry<'tcx>],
 ) {
-    tcx.sess.emit_err(DumpVTableEntries {
-        span: sp,
-        trait_ref,
-        entries: format!("{:#?}", entries),
-    });
+    tcx.sess.emit_err(DumpVTableEntries { span: sp, trait_ref, entries: format!("{entries:#?}") });
+}
+
+fn has_own_existential_vtable_entries(tcx: TyCtxt<'_>, trait_def_id: DefId) -> bool {
+    own_existential_vtable_entries_iter(tcx, trait_def_id).next().is_some()
 }
 
 fn own_existential_vtable_entries(tcx: TyCtxt<'_>, trait_def_id: DefId) -> &[DefId] {
+    tcx.arena.alloc_from_iter(own_existential_vtable_entries_iter(tcx, trait_def_id))
+}
+
+fn own_existential_vtable_entries_iter(
+    tcx: TyCtxt<'_>,
+    trait_def_id: DefId,
+) -> impl Iterator<Item = DefId> + '_ {
     let trait_methods = tcx
         .associated_items(trait_def_id)
         .in_definition_order()
         .filter(|item| item.kind == ty::AssocKind::Fn);
+
     // Now list each method's DefId (for within its trait).
     let own_entries = trait_methods.filter_map(move |&trait_method| {
         debug!("own_existential_vtable_entry: trait_method={:?}", trait_method);
@@ -211,7 +229,7 @@ fn own_existential_vtable_entries(tcx: TyCtxt<'_>, trait_def_id: DefId) -> &[Def
         Some(def_id)
     });
 
-    tcx.arena.alloc_from_iter(own_entries.into_iter())
+    own_entries
 }
 
 /// Given a trait `trait_ref`, iterates the vtable entries
@@ -241,12 +259,12 @@ fn vtable_entries<'tcx>(
                     debug!("vtable_entries: trait_method={:?}", def_id);
 
                     // The method may have some early-bound lifetimes; add regions for those.
-                    let substs = trait_ref.map_bound(|trait_ref| {
-                        InternalSubsts::for_item(tcx, def_id, |param, _| match param.kind {
+                    let args = trait_ref.map_bound(|trait_ref| {
+                        GenericArgs::for_item(tcx, def_id, |param, _| match param.kind {
                             GenericParamDefKind::Lifetime => tcx.lifetimes.re_erased.into(),
                             GenericParamDefKind::Type { .. }
                             | GenericParamDefKind::Const { .. } => {
-                                trait_ref.substs[param.index as usize]
+                                trait_ref.args[param.index as usize]
                             }
                         })
                     });
@@ -254,14 +272,14 @@ fn vtable_entries<'tcx>(
                     // The trait type may have higher-ranked lifetimes in it;
                     // erase them if they appear, so that we get the type
                     // at some particular call site.
-                    let substs = tcx
-                        .normalize_erasing_late_bound_regions(ty::ParamEnv::reveal_all(), substs);
+                    let args =
+                        tcx.normalize_erasing_late_bound_regions(ty::ParamEnv::reveal_all(), args);
 
                     // It's possible that the method relies on where-clauses that
                     // do not hold for this particular set of type parameters.
                     // Note that this method could then never be called, so we
                     // do not want to try and codegen it, in that case (see #23435).
-                    let predicates = tcx.predicates_of(def_id).instantiate_own(tcx, substs);
+                    let predicates = tcx.predicates_of(def_id).instantiate_own(tcx, args);
                     if impossible_predicates(
                         tcx,
                         predicates.map(|(predicate, _)| predicate).collect(),
@@ -274,7 +292,7 @@ fn vtable_entries<'tcx>(
                         tcx,
                         ty::ParamEnv::reveal_all(),
                         def_id,
-                        substs,
+                        args,
                     )
                     .expect("resolution failed during building vtable representation");
                     VtblEntry::Method(instance)
@@ -363,8 +381,8 @@ pub(crate) fn vtable_trait_upcasting_coercion_new_vptr_slot<'tcx>(
     let trait_ref = ty::TraitRef::new(tcx, unsize_trait_did, [source, target]);
 
     match tcx.codegen_select_candidate((ty::ParamEnv::reveal_all(), trait_ref)) {
-        Ok(ImplSource::TraitUpcasting(implsrc_traitcasting)) => {
-            implsrc_traitcasting.vtable_vptr_slot
+        Ok(ImplSource::Builtin(BuiltinImplSource::TraitUpcasting { vtable_vptr_slot }, _)) => {
+            *vtable_vptr_slot
         }
         otherwise => bug!("expected TraitUpcasting candidate, got {otherwise:?}"),
     }