Build `UserTypeProjections` lazily when visiting bindings

3 files changed, 179 insertions, 112 deletions

diff --git a/compiler/rustc_middle/src/mir/mod.rs b/compiler/rustc_middle/src/mir/mod.rs
index 7090e93549e..4dfb362f3a2 100644
--- a/compiler/rustc_middle/src/mir/mod.rs
+++ b/compiler/rustc_middle/src/mir/mod.rs
@@ -33,8 +33,8 @@ use crate::mir::interpret::{AllocRange, Scalar};
 use crate::ty::codec::{TyDecoder, TyEncoder};
 use crate::ty::print::{FmtPrinter, Printer, pretty_print_const, with_no_trimmed_paths};
 use crate::ty::{
-    self, AdtDef, GenericArg, GenericArgsRef, Instance, InstanceKind, List, Ty, TyCtxt,
-    TypeVisitableExt, TypingEnv, UserTypeAnnotationIndex,
+    self, GenericArg, GenericArgsRef, Instance, InstanceKind, List, Ty, TyCtxt, TypeVisitableExt,
+    TypingEnv, UserTypeAnnotationIndex,
 };
 
 mod basic_blocks;
@@ -1482,53 +1482,10 @@ pub struct UserTypeProjections {
     pub contents: Vec<UserTypeProjection>,
 }
 
-impl<'tcx> UserTypeProjections {
-    pub fn none() -> Self {
-        UserTypeProjections { contents: vec![] }
-    }
-
-    pub fn is_empty(&self) -> bool {
-        self.contents.is_empty()
-    }
-
+impl UserTypeProjections {
     pub fn projections(&self) -> impl Iterator<Item = &UserTypeProjection> + ExactSizeIterator {
         self.contents.iter()
     }
-
-    pub fn push_user_type(mut self, base_user_type: UserTypeAnnotationIndex) -> Self {
-        self.contents.push(UserTypeProjection { base: base_user_type, projs: vec![] });
-        self
-    }
-
-    fn map_projections(mut self, f: impl FnMut(UserTypeProjection) -> UserTypeProjection) -> Self {
-        self.contents = self.contents.into_iter().map(f).collect();
-        self
-    }
-
-    pub fn index(self) -> Self {
-        self.map_projections(|pat_ty_proj| pat_ty_proj.index())
-    }
-
-    pub fn subslice(self, from: u64, to: u64) -> Self {
-        self.map_projections(|pat_ty_proj| pat_ty_proj.subslice(from, to))
-    }
-
-    pub fn deref(self) -> Self {
-        self.map_projections(|pat_ty_proj| pat_ty_proj.deref())
-    }
-
-    pub fn leaf(self, field: FieldIdx) -> Self {
-        self.map_projections(|pat_ty_proj| pat_ty_proj.leaf(field))
-    }
-
-    pub fn variant(
-        self,
-        adt_def: AdtDef<'tcx>,
-        variant_index: VariantIdx,
-        field_index: FieldIdx,
-    ) -> Self {
-        self.map_projections(|pat_ty_proj| pat_ty_proj.variant(adt_def, variant_index, field_index))
-    }
 }
 
 /// Encodes the effect of a user-supplied type annotation on the
@@ -1553,42 +1510,6 @@ pub struct UserTypeProjection {
     pub projs: Vec<ProjectionKind>,
 }
 
-impl UserTypeProjection {
-    pub(crate) fn index(mut self) -> Self {
-        self.projs.push(ProjectionElem::Index(()));
-        self
-    }
-
-    pub(crate) fn subslice(mut self, from: u64, to: u64) -> Self {
-        self.projs.push(ProjectionElem::Subslice { from, to, from_end: true });
-        self
-    }
-
-    pub(crate) fn deref(mut self) -> Self {
-        self.projs.push(ProjectionElem::Deref);
-        self
-    }
-
-    pub(crate) fn leaf(mut self, field: FieldIdx) -> Self {
-        self.projs.push(ProjectionElem::Field(field, ()));
-        self
-    }
-
-    pub(crate) fn variant(
-        mut self,
-        adt_def: AdtDef<'_>,
-        variant_index: VariantIdx,
-        field_index: FieldIdx,
-    ) -> Self {
-        self.projs.push(ProjectionElem::Downcast(
-            Some(adt_def.variant(variant_index).name),
-            variant_index,
-        ));
-        self.projs.push(ProjectionElem::Field(field_index, ()));
-        self
-    }
-}
-
 rustc_index::newtype_index! {
     #[derive(HashStable)]
     #[encodable]
diff --git a/compiler/rustc_mir_build/src/builder/matches/mod.rs b/compiler/rustc_mir_build/src/builder/matches/mod.rs
index 60cd8a2c89c..ea341b604e0 100644
--- a/compiler/rustc_mir_build/src/builder/matches/mod.rs
+++ b/compiler/rustc_mir_build/src/builder/matches/mod.rs
@@ -5,6 +5,11 @@
 //! This also includes code for pattern bindings in `let` statements and
 //! function parameters.
 
+use std::assert_matches::assert_matches;
+use std::borrow::Borrow;
+use std::mem;
+use std::sync::Arc;
+
 use rustc_abi::VariantIdx;
 use rustc_data_structures::fx::FxIndexMap;
 use rustc_data_structures::stack::ensure_sufficient_stack;
@@ -19,6 +24,7 @@ use tracing::{debug, instrument};
 
 use crate::builder::ForGuard::{self, OutsideGuard, RefWithinGuard};
 use crate::builder::expr::as_place::PlaceBuilder;
+use crate::builder::matches::user_ty::ProjectedUserTypesNode;
 use crate::builder::scope::DropKind;
 use crate::builder::{
     BlockAnd, BlockAndExtension, Builder, GuardFrame, GuardFrameLocal, LocalsForNode,
@@ -27,13 +33,9 @@ use crate::builder::{
 // helper functions, broken out by category:
 mod match_pair;
 mod test;
+mod user_ty;
 mod util;
 
-use std::assert_matches::assert_matches;
-use std::borrow::Borrow;
-use std::mem;
-use std::sync::Arc;
-
 /// Arguments to [`Builder::then_else_break_inner`] that are usually forwarded
 /// to recursive invocations.
 #[derive(Clone, Copy)]
@@ -757,11 +759,12 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
     ) -> Option<SourceScope> {
         self.visit_primary_bindings_special(
             pattern,
-            UserTypeProjections::none(),
-            &mut |this, name, mode, var, span, ty, user_ty| {
+            &ProjectedUserTypesNode::None,
+            &mut |this, name, mode, var, span, ty, user_tys| {
                 let vis_scope = *visibility_scope
                     .get_or_insert_with(|| this.new_source_scope(scope_span, LintLevel::Inherited));
                 let source_info = SourceInfo { span, scope: this.source_scope };
+                let user_tys = user_tys.build_user_type_projections();
 
                 this.declare_binding(
                     source_info,
@@ -770,7 +773,7 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
                     mode,
                     var,
                     ty,
-                    user_ty,
+                    user_tys,
                     ArmHasGuard(guard.is_some()),
                     opt_match_place.map(|(x, y)| (x.cloned(), y)),
                     pattern.span,
@@ -874,7 +877,7 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
     fn visit_primary_bindings_special(
         &mut self,
         pattern: &Pat<'tcx>,
-        pattern_user_ty: UserTypeProjections,
+        user_tys: &ProjectedUserTypesNode<'_>,
         f: &mut impl FnMut(
             &mut Self,
             Symbol,
@@ -882,21 +885,21 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
             LocalVarId,
             Span,
             Ty<'tcx>,
-            UserTypeProjections,
+            &ProjectedUserTypesNode<'_>,
         ),
     ) {
         // Avoid having to write the full method name at each recursive call.
-        let visit_subpat = |this: &mut Self, subpat, user_tys, f: &mut _| {
+        let visit_subpat = |this: &mut Self, subpat, user_tys: &_, f: &mut _| {
             this.visit_primary_bindings_special(subpat, user_tys, f)
         };
 
         match pattern.kind {
             PatKind::Binding { name, mode, var, ty, ref subpattern, is_primary, .. } => {
                 if is_primary {
-                    f(self, name, mode, var, pattern.span, ty, pattern_user_ty.clone());
+                    f(self, name, mode, var, pattern.span, ty, user_tys);
                 }
                 if let Some(subpattern) = subpattern.as_ref() {
-                    visit_subpat(self, subpattern, pattern_user_ty, f);
+                    visit_subpat(self, subpattern, user_tys, f);
                 }
             }
 
@@ -905,13 +908,13 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
                 let from = u64::try_from(prefix.len()).unwrap();
                 let to = u64::try_from(suffix.len()).unwrap();
                 for subpattern in prefix.iter() {
-                    visit_subpat(self, subpattern, pattern_user_ty.clone().index(), f);
+                    visit_subpat(self, subpattern, &user_tys.index(), f);
                 }
                 if let Some(subpattern) = slice {
-                    visit_subpat(self, subpattern, pattern_user_ty.clone().subslice(from, to), f);
+                    visit_subpat(self, subpattern, &user_tys.subslice(from, to), f);
                 }
                 for subpattern in suffix.iter() {
-                    visit_subpat(self, subpattern, pattern_user_ty.clone().index(), f);
+                    visit_subpat(self, subpattern, &user_tys.index(), f);
                 }
             }
 
@@ -922,11 +925,11 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
             | PatKind::Error(_) => {}
 
             PatKind::Deref { ref subpattern } => {
-                visit_subpat(self, subpattern, pattern_user_ty.deref(), f);
+                visit_subpat(self, subpattern, &user_tys.deref(), f);
             }
 
             PatKind::DerefPattern { ref subpattern, .. } => {
-                visit_subpat(self, subpattern, UserTypeProjections::none(), f);
+                visit_subpat(self, subpattern, &ProjectedUserTypesNode::None, f);
             }
 
             PatKind::AscribeUserType {
@@ -942,28 +945,31 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
                 // Note that the variance doesn't apply here, as we are tracking the effect
                 // of `user_ty` on any bindings contained with subpattern.
 
+                // Caution: Pushing this user type here is load-bearing even for
+                // patterns containing no bindings, to ensure that the type ends
+                // up represented in MIR _somewhere_.
                 let base_user_ty = self.canonical_user_type_annotations.push(annotation.clone());
-                let subpattern_user_ty = pattern_user_ty.push_user_type(base_user_ty);
-                visit_subpat(self, subpattern, subpattern_user_ty, f)
+                let subpattern_user_tys = user_tys.push_user_type(base_user_ty);
+                visit_subpat(self, subpattern, &subpattern_user_tys, f)
             }
 
             PatKind::ExpandedConstant { ref subpattern, .. } => {
-                visit_subpat(self, subpattern, pattern_user_ty, f)
+                visit_subpat(self, subpattern, user_tys, f)
             }
 
             PatKind::Leaf { ref subpatterns } => {
                 for subpattern in subpatterns {
-                    let subpattern_user_ty = pattern_user_ty.clone().leaf(subpattern.field);
-                    debug!("visit_primary_bindings: subpattern_user_ty={:?}", subpattern_user_ty);
-                    visit_subpat(self, &subpattern.pattern, subpattern_user_ty, f);
+                    let subpattern_user_tys = user_tys.leaf(subpattern.field);
+                    debug!("visit_primary_bindings: subpattern_user_tys={subpattern_user_tys:?}");
+                    visit_subpat(self, &subpattern.pattern, &subpattern_user_tys, f);
                 }
             }
 
             PatKind::Variant { adt_def, args: _, variant_index, ref subpatterns } => {
                 for subpattern in subpatterns {
-                    let subpattern_user_ty =
-                        pattern_user_ty.clone().variant(adt_def, variant_index, subpattern.field);
-                    visit_subpat(self, &subpattern.pattern, subpattern_user_ty, f);
+                    let subpattern_user_tys =
+                        user_tys.variant(adt_def, variant_index, subpattern.field);
+                    visit_subpat(self, &subpattern.pattern, &subpattern_user_tys, f);
                 }
             }
             PatKind::Or { ref pats } => {
@@ -972,7 +978,7 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
                 // `let (x | y) = ...`, the primary binding of `y` occurs in
                 // the right subpattern
                 for subpattern in pats.iter() {
-                    visit_subpat(self, subpattern, pattern_user_ty.clone(), f);
+                    visit_subpat(self, subpattern, user_tys, f);
                 }
             }
         }
@@ -2764,7 +2770,7 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
         mode: BindingMode,
         var_id: LocalVarId,
         var_ty: Ty<'tcx>,
-        user_ty: UserTypeProjections,
+        user_ty: Option<Box<UserTypeProjections>>,
         has_guard: ArmHasGuard,
         opt_match_place: Option<(Option<Place<'tcx>>, Span)>,
         pat_span: Span,
@@ -2774,7 +2780,7 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
         let local = LocalDecl {
             mutability: mode.1,
             ty: var_ty,
-            user_ty: if user_ty.is_empty() { None } else { Some(Box::new(user_ty)) },
+            user_ty,
             source_info,
             local_info: ClearCrossCrate::Set(Box::new(LocalInfo::User(BindingForm::Var(
                 VarBindingForm {
diff --git a/compiler/rustc_mir_build/src/builder/matches/user_ty.rs b/compiler/rustc_mir_build/src/builder/matches/user_ty.rs
new file mode 100644
index 00000000000..df9f93ac328
--- /dev/null
+++ b/compiler/rustc_mir_build/src/builder/matches/user_ty.rs
@@ -0,0 +1,140 @@
+//! Helper code for building a linked list of user-type projections on the
+//! stack while visiting a THIR pattern.
+//!
+//! This avoids having to repeatedly clone a partly-built [`UserTypeProjections`]
+//! at every step of the traversal, which is what the previous code was doing.
+
+use std::assert_matches::assert_matches;
+use std::iter;
+
+use rustc_abi::{FieldIdx, VariantIdx};
+use rustc_middle::mir::{ProjectionElem, UserTypeProjection, UserTypeProjections};
+use rustc_middle::ty::{AdtDef, UserTypeAnnotationIndex};
+use rustc_span::Symbol;
+
+/// One of a list of "operations" that can be used to lazily build projections
+/// of user-specified types.
+#[derive(Clone, Debug)]
+pub(crate) enum ProjectedUserTypesOp {
+    PushUserType { base: UserTypeAnnotationIndex },
+
+    Index,
+    Subslice { from: u64, to: u64 },
+    Deref,
+    Leaf { field: FieldIdx },
+    Variant { name: Symbol, variant: VariantIdx, field: FieldIdx },
+}
+
+#[derive(Debug)]
+pub(crate) enum ProjectedUserTypesNode<'a> {
+    None,
+    Chain { parent: &'a Self, op: ProjectedUserTypesOp },
+}
+
+impl<'a> ProjectedUserTypesNode<'a> {
+    pub(crate) fn push_user_type(&'a self, base: UserTypeAnnotationIndex) -> Self {
+        // Pushing a base user type always causes the chain to become non-empty.
+        Self::Chain { parent: self, op: ProjectedUserTypesOp::PushUserType { base } }
+    }
+
+    /// Push another projection op onto the chain, but only if it is already non-empty.
+    fn maybe_push(&'a self, op_fn: impl FnOnce() -> ProjectedUserTypesOp) -> Self {
+        match self {
+            Self::None => Self::None,
+            Self::Chain { .. } => Self::Chain { parent: self, op: op_fn() },
+        }
+    }
+
+    pub(crate) fn index(&'a self) -> Self {
+        self.maybe_push(|| ProjectedUserTypesOp::Index)
+    }
+
+    pub(crate) fn subslice(&'a self, from: u64, to: u64) -> Self {
+        self.maybe_push(|| ProjectedUserTypesOp::Subslice { from, to })
+    }
+
+    pub(crate) fn deref(&'a self) -> Self {
+        self.maybe_push(|| ProjectedUserTypesOp::Deref)
+    }
+
+    pub(crate) fn leaf(&'a self, field: FieldIdx) -> Self {
+        self.maybe_push(|| ProjectedUserTypesOp::Leaf { field })
+    }
+
+    pub(crate) fn variant(
+        &'a self,
+        adt_def: AdtDef<'_>,
+        variant: VariantIdx,
+        field: FieldIdx,
+    ) -> Self {
+        self.maybe_push(|| {
+            let name = adt_def.variant(variant).name;
+            ProjectedUserTypesOp::Variant { name, variant, field }
+        })
+    }
+
+    /// Traverses the chain of nodes to yield each op in the chain.
+    /// Because this walks from child node to parent node, the ops are
+    /// naturally yielded in "reverse" order.
+    fn iter_ops_reversed(&'a self) -> impl Iterator<Item = &'a ProjectedUserTypesOp> {
+        let mut next = self;
+        iter::from_fn(move || match next {
+            Self::None => None,
+            Self::Chain { parent, op } => {
+                next = parent;
+                Some(op)
+            }
+        })
+    }
+
+    /// Assembles this chain of user-type projections into a proper data structure.
+    pub(crate) fn build_user_type_projections(&self) -> Option<Box<UserTypeProjections>> {
+        // If we know there's nothing to do, just return None immediately.
+        if matches!(self, Self::None) {
+            return None;
+        }
+
+        let ops_reversed = self.iter_ops_reversed().cloned().collect::<Vec<_>>();
+        // The "first" op should always be `PushUserType`.
+        // Other projections are only added if there is at least one user type.
+        assert_matches!(ops_reversed.last(), Some(ProjectedUserTypesOp::PushUserType { .. }));
+
+        let mut projections = vec![];
+        for op in ops_reversed.into_iter().rev() {
+            match op {
+                ProjectedUserTypesOp::PushUserType { base } => {
+                    projections.push(UserTypeProjection { base, projs: vec![] })
+                }
+
+                ProjectedUserTypesOp::Index => {
+                    for p in &mut projections {
+                        p.projs.push(ProjectionElem::Index(()))
+                    }
+                }
+                ProjectedUserTypesOp::Subslice { from, to } => {
+                    for p in &mut projections {
+                        p.projs.push(ProjectionElem::Subslice { from, to, from_end: true })
+                    }
+                }
+                ProjectedUserTypesOp::Deref => {
+                    for p in &mut projections {
+                        p.projs.push(ProjectionElem::Deref)
+                    }
+                }
+                ProjectedUserTypesOp::Leaf { field } => {
+                    for p in &mut projections {
+                        p.projs.push(ProjectionElem::Field(field, ()))
+                    }
+                }
+                ProjectedUserTypesOp::Variant { name, variant, field } => {
+                    for p in &mut projections {
+                        p.projs.push(ProjectionElem::Downcast(Some(name), variant));
+                        p.projs.push(ProjectionElem::Field(field, ()));
+                    }
+                }
+            }
+        }
+
+        Some(Box::new(UserTypeProjections { contents: projections }))
+    }
+}