Auto merge of #140375 - lcnr:subrelations-infcx, r=BoxyUwU

eagerly compute `sub_unification_table` again

Previously called `sub_relations`. We still only using them for diagnostics right now. This mostly reverts rust-lang/rust#119989. Necessary for type inference guidance due to not-yet defined opaque types, cc https://github.com/rust-lang/trait-system-refactor-initiative/issues/182.

We could use them for cycle detection in generalization and it seems desirable to do so in the future. However, this is unsound with the old trait solver as its cache does not track these `sub_unification_table` in any way.

We now properly track the `sub_unification_table` when canonicalizing so using them in the new solver is totally sound and the performance impact is far more manageable than I thought back in rust-lang/rust#119989.

r? `@compiler-errors`

7 files changed, 13 insertions, 103 deletions

diff --git a/compiler/rustc_trait_selection/src/error_reporting/infer/mod.rs b/compiler/rustc_trait_selection/src/error_reporting/infer/mod.rs
index 812e20e4338..d3a17232a40 100644
--- a/compiler/rustc_trait_selection/src/error_reporting/infer/mod.rs
+++ b/compiler/rustc_trait_selection/src/error_reporting/infer/mod.rs
@@ -91,7 +91,6 @@ mod suggest;
 pub mod need_type_info;
 pub mod nice_region_error;
 pub mod region;
-pub mod sub_relations;
 
 /// Makes a valid string literal from a string by escaping special characters (" and \),
 /// unless they are already escaped.
diff --git a/compiler/rustc_trait_selection/src/error_reporting/infer/need_type_info.rs b/compiler/rustc_trait_selection/src/error_reporting/infer/need_type_info.rs
index ec2287ed516..edab530590b 100644
--- a/compiler/rustc_trait_selection/src/error_reporting/infer/need_type_info.rs
+++ b/compiler/rustc_trait_selection/src/error_reporting/infer/need_type_info.rs
@@ -894,7 +894,8 @@ impl<'a, 'tcx> FindInferSourceVisitor<'a, 'tcx> {
                 use ty::{Infer, TyVar};
                 match (inner_ty.kind(), target_ty.kind()) {
                     (&Infer(TyVar(a_vid)), &Infer(TyVar(b_vid))) => {
-                        self.tecx.sub_relations.borrow_mut().unified(self.tecx, a_vid, b_vid)
+                        self.tecx.sub_unification_table_root_var(a_vid)
+                            == self.tecx.sub_unification_table_root_var(b_vid)
                     }
                     _ => false,
                 }
diff --git a/compiler/rustc_trait_selection/src/error_reporting/infer/sub_relations.rs b/compiler/rustc_trait_selection/src/error_reporting/infer/sub_relations.rs
deleted file mode 100644
index ef26a8ff7b8..00000000000
--- a/compiler/rustc_trait_selection/src/error_reporting/infer/sub_relations.rs
+++ /dev/null
@@ -1,81 +0,0 @@
-use rustc_data_structures::fx::FxHashMap;
-use rustc_data_structures::undo_log::NoUndo;
-use rustc_data_structures::unify as ut;
-use rustc_middle::ty;
-
-use crate::infer::InferCtxt;
-
-#[derive(Debug, Copy, Clone, PartialEq)]
-struct SubId(u32);
-impl ut::UnifyKey for SubId {
-    type Value = ();
-    #[inline]
-    fn index(&self) -> u32 {
-        self.0
-    }
-    #[inline]
-    fn from_index(i: u32) -> SubId {
-        SubId(i)
-    }
-    fn tag() -> &'static str {
-        "SubId"
-    }
-}
-
-/// When reporting ambiguity errors, we sometimes want to
-/// treat all inference vars which are subtypes of each
-/// others as if they are equal. For this case we compute
-/// the transitive closure of our subtype obligations here.
-///
-/// E.g. when encountering ambiguity errors, we want to suggest
-/// specifying some method argument or to add a type annotation
-/// to a local variable. Because subtyping cannot change the
-/// shape of a type, it's fine if the cause of the ambiguity error
-/// is only related to the suggested variable via subtyping.
-///
-/// Even for something like `let x = returns_arg(); x.method();` the
-/// type of `x` is only a supertype of the argument of `returns_arg`. We
-/// still want to suggest specifying the type of the argument.
-#[derive(Default)]
-pub struct SubRelations {
-    map: FxHashMap<ty::TyVid, SubId>,
-    table: ut::UnificationTableStorage<SubId>,
-}
-
-impl SubRelations {
-    fn get_id<'tcx>(&mut self, infcx: &InferCtxt<'tcx>, vid: ty::TyVid) -> SubId {
-        let root_vid = infcx.root_var(vid);
-        *self.map.entry(root_vid).or_insert_with(|| self.table.with_log(&mut NoUndo).new_key(()))
-    }
-
-    pub fn add_constraints<'tcx>(
-        &mut self,
-        infcx: &InferCtxt<'tcx>,
-        obls: impl IntoIterator<Item = ty::Predicate<'tcx>>,
-    ) {
-        for p in obls {
-            let (a, b) = match p.kind().skip_binder() {
-                ty::PredicateKind::Subtype(ty::SubtypePredicate { a_is_expected: _, a, b }) => {
-                    (a, b)
-                }
-                ty::PredicateKind::Coerce(ty::CoercePredicate { a, b }) => (a, b),
-                _ => continue,
-            };
-
-            match (a.kind(), b.kind()) {
-                (&ty::Infer(ty::TyVar(a_vid)), &ty::Infer(ty::TyVar(b_vid))) => {
-                    let a = self.get_id(infcx, a_vid);
-                    let b = self.get_id(infcx, b_vid);
-                    self.table.with_log(&mut NoUndo).unify_var_var(a, b).unwrap();
-                }
-                _ => continue,
-            }
-        }
-    }
-
-    pub fn unified<'tcx>(&mut self, infcx: &InferCtxt<'tcx>, a: ty::TyVid, b: ty::TyVid) -> bool {
-        let a = self.get_id(infcx, a);
-        let b = self.get_id(infcx, b);
-        self.table.with_log(&mut NoUndo).unioned(a, b)
-    }
-}
diff --git a/compiler/rustc_trait_selection/src/error_reporting/mod.rs b/compiler/rustc_trait_selection/src/error_reporting/mod.rs
index 82695688ae8..cce20b05c79 100644
--- a/compiler/rustc_trait_selection/src/error_reporting/mod.rs
+++ b/compiler/rustc_trait_selection/src/error_reporting/mod.rs
@@ -7,8 +7,6 @@ use rustc_macros::extension;
 use rustc_middle::bug;
 use rustc_middle::ty::{self, Ty};
 
-use crate::error_reporting::infer::sub_relations;
-
 pub mod infer;
 pub mod traits;
 
@@ -21,7 +19,6 @@ pub mod traits;
 /// methods which should not be used during the happy path.
 pub struct TypeErrCtxt<'a, 'tcx> {
     pub infcx: &'a InferCtxt<'tcx>,
-    pub sub_relations: std::cell::RefCell<sub_relations::SubRelations>,
 
     pub typeck_results: Option<std::cell::Ref<'a, ty::TypeckResults<'tcx>>>,
     pub fallback_has_occurred: bool,
@@ -38,7 +35,6 @@ impl<'tcx> InferCtxt<'tcx> {
     fn err_ctxt(&self) -> TypeErrCtxt<'_, 'tcx> {
         TypeErrCtxt {
             infcx: self,
-            sub_relations: Default::default(),
             typeck_results: None,
             fallback_has_occurred: false,
             normalize_fn_sig: Box::new(|fn_sig| fn_sig),
diff --git a/compiler/rustc_trait_selection/src/error_reporting/traits/mod.rs b/compiler/rustc_trait_selection/src/error_reporting/traits/mod.rs
index c8500b2d9d4..f794ff632c5 100644
--- a/compiler/rustc_trait_selection/src/error_reporting/traits/mod.rs
+++ b/compiler/rustc_trait_selection/src/error_reporting/traits/mod.rs
@@ -139,10 +139,6 @@ impl<'a, 'tcx> TypeErrCtxt<'a, 'tcx> {
         &self,
         mut errors: Vec<FulfillmentError<'tcx>>,
     ) -> ErrorGuaranteed {
-        self.sub_relations
-            .borrow_mut()
-            .add_constraints(self, errors.iter().map(|e| e.obligation.predicate));
-
         #[derive(Debug)]
         struct ErrorDescriptor<'tcx> {
             goal: Goal<'tcx, ty::Predicate<'tcx>>,
diff --git a/compiler/rustc_trait_selection/src/infer.rs b/compiler/rustc_trait_selection/src/infer.rs
index 7c6b7b14ecb..4c50c44b841 100644
--- a/compiler/rustc_trait_selection/src/infer.rs
+++ b/compiler/rustc_trait_selection/src/infer.rs
@@ -184,10 +184,9 @@ impl<'tcx> InferCtxtBuilder<'tcx> {
         R: Debug + TypeFoldable<TyCtxt<'tcx>>,
         Canonical<'tcx, QueryResponse<'tcx, R>>: ArenaAllocatable<'tcx>,
     {
-        let (infcx, key, canonical_inference_vars) =
-            self.build_with_canonical(DUMMY_SP, canonical_key);
+        let (infcx, key, var_values) = self.build_with_canonical(DUMMY_SP, canonical_key);
         let ocx = ObligationCtxt::new(&infcx);
         let value = operation(&ocx, key)?;
-        ocx.make_canonicalized_query_response(canonical_inference_vars, value)
+        ocx.make_canonicalized_query_response(var_values, value)
     }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/delegate.rs b/compiler/rustc_trait_selection/src/solve/delegate.rs
index e6a2761db5a..16f444486a6 100644
--- a/compiler/rustc_trait_selection/src/solve/delegate.rs
+++ b/compiler/rustc_trait_selection/src/solve/delegate.rs
@@ -126,13 +126,12 @@ impl<'tcx> rustc_next_trait_solver::delegate::SolverDelegate for SolverDelegate<
             }
             ty::PredicateKind::Subtype(ty::SubtypePredicate { a, b, .. })
             | ty::PredicateKind::Coerce(ty::CoercePredicate { a, b }) => {
-                if self.shallow_resolve(a).is_ty_var() && self.shallow_resolve(b).is_ty_var() {
-                    // FIXME: We also need to register a subtype relation between these vars
-                    // when those are added, and if they aren't in the same sub root then
-                    // we should mark this goal as `has_changed`.
-                    Some(Certainty::AMBIGUOUS)
-                } else {
-                    None
+                match (self.shallow_resolve(a).kind(), self.shallow_resolve(b).kind()) {
+                    (&ty::Infer(ty::TyVar(a_vid)), &ty::Infer(ty::TyVar(b_vid))) => {
+                        self.sub_unify_ty_vids_raw(a_vid, b_vid);
+                        Some(Certainty::AMBIGUOUS)
+                    }
+                    _ => None,
                 }
             }
             ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(ct, _)) => {
@@ -238,13 +237,14 @@ impl<'tcx> rustc_next_trait_solver::delegate::SolverDelegate for SolverDelegate<
         canonical.instantiate(self.tcx, &values)
     }
 
-    fn instantiate_canonical_var_with_infer(
+    fn instantiate_canonical_var(
         &self,
         kind: CanonicalVarKind<'tcx>,
         span: Span,
+        var_values: &[ty::GenericArg<'tcx>],
         universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
     ) -> ty::GenericArg<'tcx> {
-        self.0.instantiate_canonical_var(span, kind, universe_map)
+        self.0.instantiate_canonical_var(span, kind, var_values, universe_map)
     }
 
     fn add_item_bounds_for_hidden_type(