Rollup merge of #114355 - compiler-errors:resolve_vars_early, r=lcnr

resolve before canonicalization in new solver, ICE if unresolved

Fold the values with a resolver before canonicalization instead of making it happen within canonicalization.

This allows us to filter trivial region constraints from the external constraints.

r? ``@lcnr``

6 files changed, 154 insertions, 106 deletions

diff --git a/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs b/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs
index 54d901f20da..9d7a9fefd08 100644
--- a/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs
+++ b/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs
@@ -562,15 +562,9 @@ impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> {
         V: TypeFoldable<TyCtxt<'tcx>>,
     {
         let needs_canonical_flags = if canonicalize_region_mode.any() {
-            TypeFlags::HAS_INFER |
-            TypeFlags::HAS_FREE_REGIONS | // `HAS_RE_PLACEHOLDER` implies `HAS_FREE_REGIONS`
-            TypeFlags::HAS_TY_PLACEHOLDER |
-            TypeFlags::HAS_CT_PLACEHOLDER
+            TypeFlags::HAS_INFER | TypeFlags::HAS_PLACEHOLDER | TypeFlags::HAS_FREE_REGIONS
         } else {
-            TypeFlags::HAS_INFER
-                | TypeFlags::HAS_RE_PLACEHOLDER
-                | TypeFlags::HAS_TY_PLACEHOLDER
-                | TypeFlags::HAS_CT_PLACEHOLDER
+            TypeFlags::HAS_INFER | TypeFlags::HAS_PLACEHOLDER
         };
 
         // Fast path: nothing that needs to be canonicalized.
diff --git a/compiler/rustc_middle/src/traits/solve.rs b/compiler/rustc_middle/src/traits/solve.rs
index b21a00e4122..90139f925ed 100644
--- a/compiler/rustc_middle/src/traits/solve.rs
+++ b/compiler/rustc_middle/src/traits/solve.rs
@@ -147,7 +147,7 @@ impl<'tcx> std::ops::Deref for ExternalConstraints<'tcx> {
 }
 
 /// Additional constraints returned on success.
-#[derive(Debug, PartialEq, Eq, Clone, Hash, HashStable, Default)]
+#[derive(Debug, PartialEq, Eq, Clone, Hash, HashStable, Default, TypeVisitable, TypeFoldable)]
 pub struct ExternalConstraintsData<'tcx> {
     // FIXME: implement this.
     pub region_constraints: QueryRegionConstraints<'tcx>,
diff --git a/compiler/rustc_middle/src/ty/visit.rs b/compiler/rustc_middle/src/ty/visit.rs
index 520bb55e031..156eda477ad 100644
--- a/compiler/rustc_middle/src/ty/visit.rs
+++ b/compiler/rustc_middle/src/ty/visit.rs
@@ -88,14 +88,10 @@ pub trait TypeVisitableExt<'tcx>: TypeVisitable<TyCtxt<'tcx>> {
         self.has_type_flags(TypeFlags::HAS_INFER)
     }
     fn has_placeholders(&self) -> bool {
-        self.has_type_flags(
-            TypeFlags::HAS_RE_PLACEHOLDER
-                | TypeFlags::HAS_TY_PLACEHOLDER
-                | TypeFlags::HAS_CT_PLACEHOLDER,
-        )
+        self.has_type_flags(TypeFlags::HAS_PLACEHOLDER)
     }
     fn has_non_region_placeholders(&self) -> bool {
-        self.has_type_flags(TypeFlags::HAS_TY_PLACEHOLDER | TypeFlags::HAS_CT_PLACEHOLDER)
+        self.has_type_flags(TypeFlags::HAS_PLACEHOLDER - TypeFlags::HAS_RE_PLACEHOLDER)
     }
     fn has_param(&self) -> bool {
         self.has_type_flags(TypeFlags::HAS_PARAM)
diff --git a/compiler/rustc_trait_selection/src/solve/canonicalize.rs b/compiler/rustc_trait_selection/src/solve/canonicalize.rs
index 88771f90756..a9d182abfb7 100644
--- a/compiler/rustc_trait_selection/src/solve/canonicalize.rs
+++ b/compiler/rustc_trait_selection/src/solve/canonicalize.rs
@@ -207,23 +207,18 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> {
         t
     }
 
-    fn fold_region(&mut self, mut r: ty::Region<'tcx>) -> ty::Region<'tcx> {
-        match self.canonicalize_mode {
-            CanonicalizeMode::Input => {
-                // Don't resolve infer vars in input, since it affects
-                // caching and may cause trait selection bugs which rely
-                // on regions to be equal.
-            }
-            CanonicalizeMode::Response { .. } => {
-                if let ty::ReVar(vid) = *r {
-                    r = self
-                        .infcx
-                        .inner
-                        .borrow_mut()
-                        .unwrap_region_constraints()
-                        .opportunistic_resolve_var(self.infcx.tcx, vid);
-                }
-            }
+    fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
+        if let ty::ReVar(vid) = *r {
+            let resolved_region = self
+                .infcx
+                .inner
+                .borrow_mut()
+                .unwrap_region_constraints()
+                .opportunistic_resolve_var(self.infcx.tcx, vid);
+            assert_eq!(
+                r, resolved_region,
+                "region var should have been resolved, {r} -> {resolved_region}"
+            );
         }
 
         let kind = match *r {
@@ -278,38 +273,22 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> {
         ty::Region::new_late_bound(self.interner(), self.binder_index, br)
     }
 
-    fn fold_ty(&mut self, mut t: Ty<'tcx>) -> Ty<'tcx> {
+    fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
         let kind = match *t.kind() {
-            ty::Infer(ty::TyVar(mut vid)) => {
-                // We need to canonicalize the *root* of our ty var.
-                // This is so that our canonical response correctly reflects
-                // any equated inference vars correctly!
-                let root_vid = self.infcx.root_var(vid);
-                if root_vid != vid {
-                    t = Ty::new_var(self.infcx.tcx, root_vid);
-                    vid = root_vid;
-                }
-
-                match self.infcx.probe_ty_var(vid) {
-                    Ok(t) => return self.fold_ty(t),
-                    Err(ui) => CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)),
-                }
+            ty::Infer(ty::TyVar(vid)) => {
+                assert_eq!(self.infcx.root_var(vid), vid, "ty vid should have been resolved");
+                let Err(ui) = self.infcx.probe_ty_var(vid) else {
+                    bug!("ty var should have been resolved: {t}");
+                };
+                CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui))
             }
             ty::Infer(ty::IntVar(vid)) => {
-                let nt = self.infcx.opportunistic_resolve_int_var(vid);
-                if nt != t {
-                    return self.fold_ty(nt);
-                } else {
-                    CanonicalVarKind::Ty(CanonicalTyVarKind::Int)
-                }
+                assert_eq!(self.infcx.opportunistic_resolve_int_var(vid), t);
+                CanonicalVarKind::Ty(CanonicalTyVarKind::Int)
             }
             ty::Infer(ty::FloatVar(vid)) => {
-                let nt = self.infcx.opportunistic_resolve_float_var(vid);
-                if nt != t {
-                    return self.fold_ty(nt);
-                } else {
-                    CanonicalVarKind::Ty(CanonicalTyVarKind::Float)
-                }
+                assert_eq!(self.infcx.opportunistic_resolve_float_var(vid), t);
+                CanonicalVarKind::Ty(CanonicalTyVarKind::Float)
             }
             ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
                 bug!("fresh var during canonicalization: {t:?}")
@@ -372,22 +351,19 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> {
         Ty::new_bound(self.infcx.tcx, self.binder_index, bt)
     }
 
-    fn fold_const(&mut self, mut c: ty::Const<'tcx>) -> ty::Const<'tcx> {
+    fn fold_const(&mut self, c: ty::Const<'tcx>) -> ty::Const<'tcx> {
         let kind = match c.kind() {
-            ty::ConstKind::Infer(ty::InferConst::Var(mut vid)) => {
-                // We need to canonicalize the *root* of our const var.
-                // This is so that our canonical response correctly reflects
-                // any equated inference vars correctly!
-                let root_vid = self.infcx.root_const_var(vid);
-                if root_vid != vid {
-                    c = ty::Const::new_var(self.infcx.tcx, root_vid, c.ty());
-                    vid = root_vid;
-                }
-
-                match self.infcx.probe_const_var(vid) {
-                    Ok(c) => return self.fold_const(c),
-                    Err(universe) => CanonicalVarKind::Const(universe, c.ty()),
-                }
+            ty::ConstKind::Infer(ty::InferConst::Var(vid)) => {
+                assert_eq!(
+                    self.infcx.root_const_var(vid),
+                    vid,
+                    "const var should have been resolved"
+                );
+                let Err(ui) = self.infcx.probe_const_var(vid) else {
+                    bug!("const var should have been resolved");
+                };
+                // FIXME: we should fold this ty eventually
+                CanonicalVarKind::Const(ui, c.ty())
             }
             ty::ConstKind::Infer(ty::InferConst::Fresh(_)) => {
                 bug!("fresh var during canonicalization: {c:?}")
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs
index 7323b98b8ce..0a54b1c6433 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs
@@ -16,11 +16,15 @@ use rustc_index::IndexVec;
 use rustc_infer::infer::canonical::query_response::make_query_region_constraints;
 use rustc_infer::infer::canonical::CanonicalVarValues;
 use rustc_infer::infer::canonical::{CanonicalExt, QueryRegionConstraints};
+use rustc_infer::infer::InferCtxt;
 use rustc_middle::traits::query::NoSolution;
 use rustc_middle::traits::solve::{
-    ExternalConstraints, ExternalConstraintsData, MaybeCause, PredefinedOpaquesData, QueryInput,
+    ExternalConstraintsData, MaybeCause, PredefinedOpaquesData, QueryInput,
+};
+use rustc_middle::ty::{
+    self, BoundVar, GenericArgKind, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable,
+    TypeVisitableExt,
 };
-use rustc_middle::ty::{self, BoundVar, GenericArgKind, Ty, TyCtxt, TypeFoldable};
 use rustc_span::DUMMY_SP;
 use std::iter;
 use std::ops::Deref;
@@ -32,6 +36,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         &self,
         goal: Goal<'tcx, T>,
     ) -> (Vec<ty::GenericArg<'tcx>>, CanonicalInput<'tcx, T>) {
+        let opaque_types = self.infcx.clone_opaque_types_for_query_response();
+        let (goal, opaque_types) =
+            (goal, opaque_types).fold_with(&mut EagerResolver { infcx: self.infcx });
+
         let mut orig_values = Default::default();
         let canonical_goal = Canonicalizer::canonicalize(
             self.infcx,
@@ -40,11 +48,9 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             QueryInput {
                 goal,
                 anchor: self.infcx.defining_use_anchor,
-                predefined_opaques_in_body: self.tcx().mk_predefined_opaques_in_body(
-                    PredefinedOpaquesData {
-                        opaque_types: self.infcx.clone_opaque_types_for_query_response(),
-                    },
-                ),
+                predefined_opaques_in_body: self
+                    .tcx()
+                    .mk_predefined_opaques_in_body(PredefinedOpaquesData { opaque_types }),
             },
         );
         (orig_values, canonical_goal)
@@ -70,34 +76,43 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         );
 
         let certainty = certainty.unify_with(goals_certainty);
+        if let Certainty::OVERFLOW = certainty {
+            // If we have overflow, it's probable that we're substituting a type
+            // into itself infinitely and any partial substitutions in the query
+            // response are probably not useful anyways, so just return an empty
+            // query response.
+            //
+            // This may prevent us from potentially useful inference, e.g.
+            // 2 candidates, one ambiguous and one overflow, which both
+            // have the same inference constraints.
+            //
+            // Changing this to retain some constraints in the future
+            // won't be a breaking change, so this is good enough for now.
+            return Ok(self.make_ambiguous_response_no_constraints(MaybeCause::Overflow));
+        }
 
-        let response = match certainty {
-            Certainty::Yes | Certainty::Maybe(MaybeCause::Ambiguity) => {
-                let external_constraints = self.compute_external_query_constraints()?;
-                Response { var_values: self.var_values, external_constraints, certainty }
-            }
-            Certainty::Maybe(MaybeCause::Overflow) => {
-                // If we have overflow, it's probable that we're substituting a type
-                // into itself infinitely and any partial substitutions in the query
-                // response are probably not useful anyways, so just return an empty
-                // query response.
-                //
-                // This may prevent us from potentially useful inference, e.g.
-                // 2 candidates, one ambiguous and one overflow, which both
-                // have the same inference constraints.
-                //
-                // Changing this to retain some constraints in the future
-                // won't be a breaking change, so this is good enough for now.
-                return Ok(self.make_ambiguous_response_no_constraints(MaybeCause::Overflow));
-            }
-        };
+        let var_values = self.var_values;
+        let external_constraints = self.compute_external_query_constraints()?;
+
+        let (var_values, mut external_constraints) =
+            (var_values, external_constraints).fold_with(&mut EagerResolver { infcx: self.infcx });
+        // Remove any trivial region constraints once we've resolved regions
+        external_constraints
+            .region_constraints
+            .outlives
+            .retain(|(outlives, _)| outlives.0.as_region().map_or(true, |re| re != outlives.1));
 
         let canonical = Canonicalizer::canonicalize(
             self.infcx,
             CanonicalizeMode::Response { max_input_universe: self.max_input_universe },
             &mut Default::default(),
-            response,
+            Response {
+                var_values,
+                certainty,
+                external_constraints: self.tcx().mk_external_constraints(external_constraints),
+            },
         );
+
         Ok(canonical)
     }
 
@@ -143,7 +158,9 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
     /// further constrained by inference, that will be passed back in the var
     /// values.
     #[instrument(level = "debug", skip(self), ret)]
-    fn compute_external_query_constraints(&self) -> Result<ExternalConstraints<'tcx>, NoSolution> {
+    fn compute_external_query_constraints(
+        &self,
+    ) -> Result<ExternalConstraintsData<'tcx>, NoSolution> {
         // We only check for leaks from universes which were entered inside
         // of the query.
         self.infcx.leak_check(self.max_input_universe, None).map_err(|e| {
@@ -173,9 +190,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             self.predefined_opaques_in_body.opaque_types.iter().all(|(pa, _)| pa != a)
         });
 
-        Ok(self
-            .tcx()
-            .mk_external_constraints(ExternalConstraintsData { region_constraints, opaque_types }))
+        Ok(ExternalConstraintsData { region_constraints, opaque_types })
     }
 
     /// After calling a canonical query, we apply the constraints returned
@@ -333,3 +348,65 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         Ok(())
     }
 }
+
+/// Resolves ty, region, and const vars to their inferred values or their root vars.
+struct EagerResolver<'a, 'tcx> {
+    infcx: &'a InferCtxt<'tcx>,
+}
+
+impl<'tcx> TypeFolder<TyCtxt<'tcx>> for EagerResolver<'_, 'tcx> {
+    fn interner(&self) -> TyCtxt<'tcx> {
+        self.infcx.tcx
+    }
+
+    fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
+        match *t.kind() {
+            ty::Infer(ty::TyVar(vid)) => match self.infcx.probe_ty_var(vid) {
+                Ok(t) => t.fold_with(self),
+                Err(_) => Ty::new_var(self.infcx.tcx, self.infcx.root_var(vid)),
+            },
+            ty::Infer(ty::IntVar(vid)) => self.infcx.opportunistic_resolve_int_var(vid),
+            ty::Infer(ty::FloatVar(vid)) => self.infcx.opportunistic_resolve_float_var(vid),
+            _ => {
+                if t.has_infer() {
+                    t.super_fold_with(self)
+                } else {
+                    t
+                }
+            }
+        }
+    }
+
+    fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
+        match *r {
+            ty::ReVar(vid) => self
+                .infcx
+                .inner
+                .borrow_mut()
+                .unwrap_region_constraints()
+                .opportunistic_resolve_var(self.infcx.tcx, vid),
+            _ => r,
+        }
+    }
+
+    fn fold_const(&mut self, c: ty::Const<'tcx>) -> ty::Const<'tcx> {
+        match c.kind() {
+            ty::ConstKind::Infer(ty::InferConst::Var(vid)) => {
+                // FIXME: we need to fold the ty too, I think.
+                match self.infcx.probe_const_var(vid) {
+                    Ok(c) => c.fold_with(self),
+                    Err(_) => {
+                        ty::Const::new_var(self.infcx.tcx, self.infcx.root_const_var(vid), c.ty())
+                    }
+                }
+            }
+            _ => {
+                if c.has_infer() {
+                    c.super_fold_with(self)
+                } else {
+                    c
+                }
+            }
+        }
+    }
+}
diff --git a/compiler/rustc_type_ir/src/lib.rs b/compiler/rustc_type_ir/src/lib.rs
index 1a6a253f360..b0f8ea7a05d 100644
--- a/compiler/rustc_type_ir/src/lib.rs
+++ b/compiler/rustc_type_ir/src/lib.rs
@@ -216,6 +216,11 @@ bitflags! {
         /// Does this have `ConstKind::Placeholder`?
         const HAS_CT_PLACEHOLDER          = 1 << 8;
 
+        /// Does this have placeholders?
+        const HAS_PLACEHOLDER           = TypeFlags::HAS_TY_PLACEHOLDER.bits
+                                          | TypeFlags::HAS_RE_PLACEHOLDER.bits
+                                          | TypeFlags::HAS_CT_PLACEHOLDER.bits;
+
         /// `true` if there are "names" of regions and so forth
         /// that are local to a particular fn/inferctxt
         const HAS_FREE_LOCAL_REGIONS      = 1 << 9;