Upgrade rustc crates and handle changes to canonicalization

They have to do with diagnostics, we could probably not support them but we will also someday want good diagnostics.

The code is mostly copied from rustc.

12 files changed, 256 insertions, 116 deletions

diff --git a/src/tools/rust-analyzer/Cargo.lock b/src/tools/rust-analyzer/Cargo.lock
index 344e6d101fe..b70b89ea543 100644
--- a/src/tools/rust-analyzer/Cargo.lock
+++ b/src/tools/rust-analyzer/Cargo.lock
@@ -1863,9 +1863,9 @@ dependencies = [
 
 [[package]]
 name = "ra-ap-rustc_abi"
-version = "0.126.0"
+version = "0.128.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "0c6789d94fb3e6e30d62f55e99a321ba63484a8bb3b4ead338687c9ddc282d28"
+checksum = "8da95e732b424802b1f043ab4007c78a0fc515ab249587abbea4634bf5fdce9a"
 dependencies = [
  "bitflags 2.9.1",
  "ra-ap-rustc_hashes",
@@ -1875,24 +1875,24 @@ dependencies = [
 
 [[package]]
 name = "ra-ap-rustc_ast_ir"
-version = "0.126.0"
+version = "0.128.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "aaab80bda0f05e9842e3afb7779b0bad0a4b54e0f7ba6deb5705dcf86482811d"
+checksum = "3838d9d7a3a5cdc511cfb6ad78740ce532f75a2366d3fc3b9853ea1b5c872779"
 
 [[package]]
 name = "ra-ap-rustc_hashes"
-version = "0.126.0"
+version = "0.128.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "64bd405e538102b5f699241794b2eefee39d5414c0e4bc72435e91430c51f905"
+checksum = "bdc8995d268d3bb4ece910f575ea5a063d6003e193ec155d15703b65882d53fb"
 dependencies = [
  "rustc-stable-hash",
 ]
 
 [[package]]
 name = "ra-ap-rustc_index"
-version = "0.126.0"
+version = "0.128.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "521621e271aa03b8433dad5981838278d6cfd7d2d8c9f4eb6d427f1d671f90fc"
+checksum = "ed0ccdf6e5627c6c3e54e571e52ce0bc8b94d5f0b94b7460269ca68a4706be69"
 dependencies = [
  "ra-ap-rustc_index_macros",
  "smallvec",
@@ -1900,9 +1900,9 @@ dependencies = [
 
 [[package]]
 name = "ra-ap-rustc_index_macros"
-version = "0.126.0"
+version = "0.128.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "245e30f2e1fef258913cc548b36f575549c8af31cbc4649929d21deda96ceeb7"
+checksum = "bd28f42362b5c9fb9b8766c3189df02a402b13363600c6885e11027889f03ee6"
 dependencies = [
  "proc-macro2",
  "quote",
@@ -1911,9 +1911,9 @@ dependencies = [
 
 [[package]]
 name = "ra-ap-rustc_lexer"
-version = "0.126.0"
+version = "0.128.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "a82681f924500e888c860e60ed99e9bf702a219a69374f59116c4261525a2157"
+checksum = "f1c31a82f091b910a27ee53a86a9af28a2df10c3484e2f1bbfe70633aa84dee9"
 dependencies = [
  "memchr",
  "unicode-properties",
@@ -1922,9 +1922,9 @@ dependencies = [
 
 [[package]]
 name = "ra-ap-rustc_next_trait_solver"
-version = "0.126.0"
+version = "0.128.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "0c9ce51f2431fbdc7fabd2d957522b6e27f41f68ec2af74b52a6f4116352ce1a"
+checksum = "f8cac6c2b5a8924209d4ca682cbc507252c58a664911e0ef463c112882ba6f72"
 dependencies = [
  "derive-where",
  "ra-ap-rustc_index",
@@ -1935,9 +1935,9 @@ dependencies = [
 
 [[package]]
 name = "ra-ap-rustc_parse_format"
-version = "0.126.0"
+version = "0.128.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "adc85ef3fdb6c084bde84857d8948dc66b752129dc8417a8614ce490e99a143f"
+checksum = "a085a1cf902dcca8abbc537faaef154bbccbbb51850f779ce5484ae3782b5d8f"
 dependencies = [
  "ra-ap-rustc_lexer",
  "rustc-literal-escaper 0.0.5",
@@ -1945,9 +1945,9 @@ dependencies = [
 
 [[package]]
 name = "ra-ap-rustc_pattern_analysis"
-version = "0.126.0"
+version = "0.128.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "3cd81eccf33d9528905d4e5abaa254b3129a6405d6c5f123fed9b73a3d217f35"
+checksum = "8ba32e3985367bc34856b41c7604133649d4a367eb5d7bdf50623025731459d8"
 dependencies = [
  "ra-ap-rustc_index",
  "rustc-hash 2.1.1",
@@ -1958,10 +1958,11 @@ dependencies = [
 
 [[package]]
 name = "ra-ap-rustc_type_ir"
-version = "0.126.0"
+version = "0.128.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "11cb0da02853698d9c89e1d1c01657b9969752befd56365e8899d4310e52b373"
+checksum = "9c9911d72f75d85d21fe88374d7bcec94f2200feffb7234108a24cc3da7c3591"
 dependencies = [
+ "arrayvec",
  "bitflags 2.9.1",
  "derive-where",
  "ena",
@@ -1977,9 +1978,9 @@ dependencies = [
 
 [[package]]
 name = "ra-ap-rustc_type_ir_macros"
-version = "0.126.0"
+version = "0.128.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "ffc93adeb52c483ede13bee6680466458218243ab479c04fb71bb53925a6e0ff"
+checksum = "22f539b87991683ce17cc52e62600fdf2b4a8af43952db30387edc1a576d3b43"
 dependencies = [
  "proc-macro2",
  "quote",
diff --git a/src/tools/rust-analyzer/Cargo.toml b/src/tools/rust-analyzer/Cargo.toml
index f325027ee58..c5ffad544a6 100644
--- a/src/tools/rust-analyzer/Cargo.toml
+++ b/src/tools/rust-analyzer/Cargo.toml
@@ -89,14 +89,14 @@ vfs-notify = { path = "./crates/vfs-notify", version = "0.0.0" }
 vfs = { path = "./crates/vfs", version = "0.0.0" }
 edition = { path = "./crates/edition", version = "0.0.0" }
 
-ra-ap-rustc_lexer = { version = "0.126", default-features = false }
-ra-ap-rustc_parse_format = { version = "0.126", default-features = false }
-ra-ap-rustc_index = { version = "0.126", default-features = false }
-ra-ap-rustc_abi = { version = "0.126", default-features = false }
-ra-ap-rustc_pattern_analysis = { version = "0.126", default-features = false }
-ra-ap-rustc_ast_ir = { version = "0.126", default-features = false }
-ra-ap-rustc_type_ir = { version = "0.126", default-features = false }
-ra-ap-rustc_next_trait_solver = { version = "0.126", default-features = false }
+ra-ap-rustc_lexer = { version = "0.128", default-features = false }
+ra-ap-rustc_parse_format = { version = "0.128", default-features = false }
+ra-ap-rustc_index = { version = "0.128", default-features = false }
+ra-ap-rustc_abi = { version = "0.128", default-features = false }
+ra-ap-rustc_pattern_analysis = { version = "0.128", default-features = false }
+ra-ap-rustc_ast_ir = { version = "0.128", default-features = false }
+ra-ap-rustc_type_ir = { version = "0.128", default-features = false }
+ra-ap-rustc_next_trait_solver = { version = "0.128", default-features = false }
 
 # local crates that aren't published to crates.io. These should not have versions.
 
diff --git a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/canonical/canonicalizer.rs b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/canonical/canonicalizer.rs
index 5d11525cd19..ffb9c076fa0 100644
--- a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/canonical/canonicalizer.rs
+++ b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/canonical/canonicalizer.rs
@@ -10,9 +10,8 @@ use rustc_index::Idx;
 use rustc_type_ir::InferTy::{self, FloatVar, IntVar, TyVar};
 use rustc_type_ir::inherent::{Const as _, IntoKind as _, Region as _, SliceLike, Ty as _};
 use rustc_type_ir::{
-    BoundVar, CanonicalQueryInput, CanonicalTyVarKind, DebruijnIndex, Flags, InferConst,
-    RegionKind, TypeFlags, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt,
-    UniverseIndex,
+    BoundVar, CanonicalQueryInput, DebruijnIndex, Flags, InferConst, RegionKind, TyVid, TypeFlags,
+    TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt, UniverseIndex,
 };
 use smallvec::SmallVec;
 use tracing::debug;
@@ -316,6 +315,13 @@ struct Canonicalizer<'cx, 'db> {
     // Note that indices is only used once `var_values` is big enough to be
     // heap-allocated.
     indices: FxHashMap<GenericArg<'db>, BoundVar>,
+    /// Maps each `sub_unification_table_root_var` to the index of the first
+    /// variable which used it.
+    ///
+    /// This means in case two type variables have the same sub relations root,
+    /// we set the `sub_root` of the second variable to the position of the first.
+    /// Otherwise the `sub_root` of each type variable is just its own position.
+    sub_root_lookup_table: FxHashMap<TyVid, usize>,
     canonicalize_mode: &'cx dyn CanonicalizeMode,
     needs_canonical_flags: TypeFlags,
 
@@ -384,10 +390,9 @@ impl<'cx, 'db> TypeFolder<DbInterner<'db>> for Canonicalizer<'cx, 'db> {
                             // FIXME: perf problem described in #55921.
                             ui = UniverseIndex::ROOT;
                         }
-                        self.canonicalize_ty_var(
-                            CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)),
-                            t,
-                        )
+
+                        let sub_root = self.get_or_insert_sub_root(vid);
+                        self.canonicalize_ty_var(CanonicalVarKind::Ty { ui, sub_root }, t)
                     }
                 }
             }
@@ -395,17 +400,17 @@ impl<'cx, 'db> TypeFolder<DbInterner<'db>> for Canonicalizer<'cx, 'db> {
             TyKind::Infer(IntVar(vid)) => {
                 let nt = self.infcx.opportunistic_resolve_int_var(vid);
                 if nt != t {
-                    self.fold_ty(nt)
+                    return self.fold_ty(nt);
                 } else {
-                    self.canonicalize_ty_var(CanonicalVarKind::Ty(CanonicalTyVarKind::Int), t)
+                    self.canonicalize_ty_var(CanonicalVarKind::Int, t)
                 }
             }
             TyKind::Infer(FloatVar(vid)) => {
                 let nt = self.infcx.opportunistic_resolve_float_var(vid);
                 if nt != t {
-                    self.fold_ty(nt)
+                    return self.fold_ty(nt);
                 } else {
-                    self.canonicalize_ty_var(CanonicalVarKind::Ty(CanonicalTyVarKind::Float), t)
+                    self.canonicalize_ty_var(CanonicalVarKind::Float, t)
                 }
             }
 
@@ -579,6 +584,7 @@ impl<'cx, 'db> Canonicalizer<'cx, 'db> {
             variables: SmallVec::from_slice(base.variables.as_slice()),
             query_state,
             indices: FxHashMap::default(),
+            sub_root_lookup_table: Default::default(),
             binder_index: DebruijnIndex::ZERO,
         };
         if canonicalizer.query_state.var_values.spilled() {
@@ -673,6 +679,13 @@ impl<'cx, 'db> Canonicalizer<'cx, 'db> {
         }
     }
 
+    fn get_or_insert_sub_root(&mut self, vid: TyVid) -> BoundVar {
+        let root_vid = self.infcx.sub_unification_table_root_var(vid);
+        let idx =
+            *self.sub_root_lookup_table.entry(root_vid).or_insert_with(|| self.variables.len());
+        BoundVar::from(idx)
+    }
+
     /// Replaces the universe indexes used in `var_values` with their index in
     /// `query_state.universe_map`. This minimizes the maximum universe used in
     /// the canonicalized value.
@@ -692,9 +705,9 @@ impl<'cx, 'db> Canonicalizer<'cx, 'db> {
         self.variables
             .iter()
             .map(|v| match *v {
-                CanonicalVarKind::Ty(CanonicalTyVarKind::Int | CanonicalTyVarKind::Float) => *v,
-                CanonicalVarKind::Ty(CanonicalTyVarKind::General(u)) => {
-                    CanonicalVarKind::Ty(CanonicalTyVarKind::General(reverse_universe_map[&u]))
+                CanonicalVarKind::Int | CanonicalVarKind::Float => *v,
+                CanonicalVarKind::Ty { ui, sub_root } => {
+                    CanonicalVarKind::Ty { ui: reverse_universe_map[&ui], sub_root }
                 }
                 CanonicalVarKind::Region(u) => CanonicalVarKind::Region(reverse_universe_map[&u]),
                 CanonicalVarKind::Const(u) => CanonicalVarKind::Const(reverse_universe_map[&u]),
diff --git a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/canonical/mod.rs b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/canonical/mod.rs
index ec41111ed81..8db4320acc9 100644
--- a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/canonical/mod.rs
+++ b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/canonical/mod.rs
@@ -32,9 +32,10 @@ use crate::next_solver::{
 };
 use instantiate::CanonicalExt;
 use rustc_index::IndexVec;
+use rustc_type_ir::inherent::IntoKind;
 use rustc_type_ir::{
-    AliasRelationDirection, AliasTyKind, CanonicalTyVarKind, CanonicalVarKind, InferTy,
-    TypeFoldable, UniverseIndex, Upcast, Variance,
+    AliasRelationDirection, AliasTyKind, CanonicalVarKind, InferTy, TypeFoldable, UniverseIndex,
+    Upcast, Variance,
     inherent::{SliceLike, Ty as _},
     relate::{
         Relate, TypeRelation, VarianceDiagInfo,
@@ -78,27 +79,15 @@ impl<'db> InferCtxt<'db> {
             .chain((1..=canonical.max_universe.as_u32()).map(|_| self.create_next_universe()))
             .collect();
 
-        let canonical_inference_vars =
-            self.instantiate_canonical_vars(canonical.variables, |ui| universes[ui]);
-        let result = canonical.instantiate(self.interner, &canonical_inference_vars);
-        (result, canonical_inference_vars)
-    }
-
-    /// Given the "infos" about the canonical variables from some
-    /// canonical, creates fresh variables with the same
-    /// characteristics (see `instantiate_canonical_var` for
-    /// details). You can then use `instantiate` to instantiate the
-    /// canonical variable with these inference variables.
-    fn instantiate_canonical_vars(
-        &self,
-        variables: CanonicalVars<'db>,
-        universe_map: impl Fn(UniverseIndex) -> UniverseIndex,
-    ) -> CanonicalVarValues<'db> {
-        CanonicalVarValues {
-            var_values: self.interner.mk_args_from_iter(
-                variables.iter().map(|info| self.instantiate_canonical_var(info, &universe_map)),
-            ),
-        }
+        let var_values = CanonicalVarValues::instantiate(
+            self.interner,
+            canonical.variables,
+            |var_values, info| {
+                self.instantiate_canonical_var(info, &var_values, |ui| universes[ui])
+            },
+        );
+        let result = canonical.instantiate(self.interner, &var_values);
+        (result, var_values)
     }
 
     /// Given the "info" about a canonical variable, creates a fresh
@@ -112,21 +101,27 @@ impl<'db> InferCtxt<'db> {
     pub fn instantiate_canonical_var(
         &self,
         cv_info: CanonicalVarKind<DbInterner<'db>>,
+        previous_var_values: &[GenericArg<'db>],
         universe_map: impl Fn(UniverseIndex) -> UniverseIndex,
     ) -> GenericArg<'db> {
         match cv_info {
-            CanonicalVarKind::Ty(ty_kind) => {
-                let ty = match ty_kind {
-                    CanonicalTyVarKind::General(ui) => {
-                        self.next_ty_var_in_universe(universe_map(ui))
+            CanonicalVarKind::Ty { ui, sub_root } => {
+                let vid = self.next_ty_var_id_in_universe(universe_map(ui));
+                // If this inference variable is related to an earlier variable
+                // via subtyping, we need to add that info to the inference context.
+                if let Some(prev) = previous_var_values.get(sub_root.as_usize()) {
+                    if let TyKind::Infer(InferTy::TyVar(sub_root)) = prev.expect_ty().kind() {
+                        self.sub_unify_ty_vids_raw(vid, sub_root);
+                    } else {
+                        unreachable!()
                     }
+                }
+                Ty::new_var(self.interner, vid).into()
+            }
 
-                    CanonicalTyVarKind::Int => self.next_int_var(),
+            CanonicalVarKind::Int => self.next_int_var().into(),
 
-                    CanonicalTyVarKind::Float => self.next_float_var(),
-                };
-                ty.into()
-            }
+            CanonicalVarKind::Float => self.next_float_var().into(),
 
             CanonicalVarKind::PlaceholderTy(PlaceholderTy { universe, bound }) => {
                 let universe_mapped = universe_map(universe);
diff --git a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/context.rs b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/context.rs
index 93fd6eeab34..45ce7e6f6cc 100644
--- a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/context.rs
+++ b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/context.rs
@@ -313,4 +313,12 @@ impl<'db> rustc_type_ir::InferCtxtLike for InferCtxt<'db> {
     fn reset_opaque_types(&self) {
         let _ = self.take_opaque_types();
     }
+
+    fn sub_unification_table_root_var(&self, var: rustc_type_ir::TyVid) -> rustc_type_ir::TyVid {
+        self.sub_unification_table_root_var(var)
+    }
+
+    fn sub_unify_ty_vids_raw(&self, a: rustc_type_ir::TyVid, b: rustc_type_ir::TyVid) {
+        self.sub_unify_ty_vids_raw(a, b);
+    }
 }
diff --git a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/mod.rs b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/mod.rs
index 2630f2a8cc4..ce6c9412873 100644
--- a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/mod.rs
+++ b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/mod.rs
@@ -1019,6 +1019,14 @@ impl<'db> InferCtxt<'db> {
             }
         }
     }
+
+    fn sub_unification_table_root_var(&self, var: rustc_type_ir::TyVid) -> rustc_type_ir::TyVid {
+        self.inner.borrow_mut().type_variables().sub_unification_table_root_var(var)
+    }
+
+    fn sub_unify_ty_vids_raw(&self, a: rustc_type_ir::TyVid, b: rustc_type_ir::TyVid) {
+        self.inner.borrow_mut().type_variables().sub_unify(a, b);
+    }
 }
 
 /// Helper for [InferCtxt::ty_or_const_infer_var_changed] (see comment on that), currently
diff --git a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/snapshot/undo_log.rs b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/snapshot/undo_log.rs
index 0fa6421f517..28ae56f4ee7 100644
--- a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/snapshot/undo_log.rs
+++ b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/snapshot/undo_log.rs
@@ -25,7 +25,7 @@ pub struct Snapshot {
 pub(crate) enum UndoLog<'db> {
     DuplicateOpaqueType,
     OpaqueTypes(OpaqueTypeKey<'db>, Option<OpaqueHiddenType<'db>>),
-    TypeVariables(sv::UndoLog<ut::Delegate<type_variable::TyVidEqKey<'db>>>),
+    TypeVariables(type_variable::UndoLog<'db>),
     ConstUnificationTable(sv::UndoLog<ut::Delegate<ConstVidKey<'db>>>),
     IntUnificationTable(sv::UndoLog<ut::Delegate<IntVid>>),
     FloatUnificationTable(sv::UndoLog<ut::Delegate<FloatVid>>),
@@ -51,6 +51,8 @@ impl_from! {
     RegionConstraintCollector(region_constraints::UndoLog<'db>),
 
     TypeVariables(sv::UndoLog<ut::Delegate<type_variable::TyVidEqKey<'db>>>),
+    TypeVariables(sv::UndoLog<ut::Delegate<type_variable::TyVidSubKey>>),
+    TypeVariables(type_variable::UndoLog<'db>),
     IntUnificationTable(sv::UndoLog<ut::Delegate<IntVid>>),
     FloatUnificationTable(sv::UndoLog<ut::Delegate<FloatVid>>),
 
diff --git a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/type_variable.rs b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/type_variable.rs
index 5217308af47..b640039af62 100644
--- a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/type_variable.rs
+++ b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/type_variable.rs
@@ -17,12 +17,48 @@ use crate::next_solver::SolverDefId;
 use crate::next_solver::Ty;
 use crate::next_solver::infer::InferCtxtUndoLogs;
 
+/// Represents a single undo-able action that affects a type inference variable.
+#[derive(Clone)]
+pub(crate) enum UndoLog<'tcx> {
+    EqRelation(sv::UndoLog<ut::Delegate<TyVidEqKey<'tcx>>>),
+    SubRelation(sv::UndoLog<ut::Delegate<TyVidSubKey>>),
+}
+
+/// Convert from a specific kind of undo to the more general UndoLog
+impl<'db> From<sv::UndoLog<ut::Delegate<TyVidEqKey<'db>>>> for UndoLog<'db> {
+    fn from(l: sv::UndoLog<ut::Delegate<TyVidEqKey<'db>>>) -> Self {
+        UndoLog::EqRelation(l)
+    }
+}
+
+/// Convert from a specific kind of undo to the more general UndoLog
+impl<'db> From<sv::UndoLog<ut::Delegate<TyVidSubKey>>> for UndoLog<'db> {
+    fn from(l: sv::UndoLog<ut::Delegate<TyVidSubKey>>) -> Self {
+        UndoLog::SubRelation(l)
+    }
+}
+
 impl<'db> Rollback<sv::UndoLog<ut::Delegate<TyVidEqKey<'db>>>> for TypeVariableStorage<'db> {
     fn reverse(&mut self, undo: sv::UndoLog<ut::Delegate<TyVidEqKey<'db>>>) {
         self.eq_relations.reverse(undo)
     }
 }
 
+impl<'tcx> Rollback<sv::UndoLog<ut::Delegate<TyVidSubKey>>> for TypeVariableStorage<'tcx> {
+    fn reverse(&mut self, undo: sv::UndoLog<ut::Delegate<TyVidSubKey>>) {
+        self.sub_unification_table.reverse(undo)
+    }
+}
+
+impl<'tcx> Rollback<UndoLog<'tcx>> for TypeVariableStorage<'tcx> {
+    fn reverse(&mut self, undo: UndoLog<'tcx>) {
+        match undo {
+            UndoLog::EqRelation(undo) => self.eq_relations.reverse(undo),
+            UndoLog::SubRelation(undo) => self.sub_unification_table.reverse(undo),
+        }
+    }
+}
+
 #[derive(Clone, Default)]
 pub(crate) struct TypeVariableStorage<'db> {
     /// The origins of each type variable.
@@ -31,6 +67,25 @@ pub(crate) struct TypeVariableStorage<'db> {
     /// constraint `?X == ?Y`. This table also stores, for each key,
     /// the known value.
     eq_relations: ut::UnificationTableStorage<TyVidEqKey<'db>>,
+    /// Only used by `-Znext-solver` and for diagnostics. Tracks whether
+    /// type variables are related via subtyping at all, ignoring which of
+    /// the two is the subtype.
+    ///
+    /// 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.
+    sub_unification_table: ut::UnificationTableStorage<TyVidSubKey>,
 }
 
 pub(crate) struct TypeVariableTable<'a, 'db> {
@@ -112,6 +167,17 @@ impl<'db> TypeVariableTable<'_, 'db> {
         debug_assert!(self.probe(a).is_unknown());
         debug_assert!(self.probe(b).is_unknown());
         self.eq_relations().union(a, b);
+        self.sub_unification_table().union(a, b);
+    }
+
+    /// Records that `a` and `b` are related via subtyping. We don't track
+    /// which of the two is the subtype.
+    ///
+    /// Precondition: neither `a` nor `b` are known.
+    pub(crate) fn sub_unify(&mut self, a: TyVid, b: TyVid) {
+        debug_assert!(self.probe(a).is_unknown());
+        debug_assert!(self.probe(b).is_unknown());
+        self.sub_unification_table().union(a, b);
     }
 
     /// Instantiates `vid` with the type `ty`.
@@ -141,6 +207,10 @@ impl<'db> TypeVariableTable<'_, 'db> {
     ///   for improving error messages.
     pub(crate) fn new_var(&mut self, universe: UniverseIndex, origin: TypeVariableOrigin) -> TyVid {
         let eq_key = self.eq_relations().new_key(TypeVariableValue::Unknown { universe });
+
+        let sub_key = self.sub_unification_table().new_key(());
+        debug_assert_eq!(eq_key.vid, sub_key.vid);
+
         let index = self.storage.values.push(TypeVariableData { origin });
         debug_assert_eq!(eq_key.vid, index);
 
@@ -163,6 +233,18 @@ impl<'db> TypeVariableTable<'_, 'db> {
         self.eq_relations().find(vid).vid
     }
 
+    /// Returns the "root" variable of `vid` in the `sub_unification_table`
+    /// equivalence table. All type variables that have been are related via
+    /// equality or subtyping will yield the same root variable (per the
+    /// union-find algorithm), so `sub_unification_table_root_var(a)
+    /// == sub_unification_table_root_var(b)` implies that:
+    /// ```text
+    /// exists X. (a <: X || X <: a) && (b <: X || X <: b)
+    /// ```
+    pub(crate) fn sub_unification_table_root_var(&mut self, vid: TyVid) -> TyVid {
+        self.sub_unification_table().find(vid).vid
+    }
+
     /// Retrieves the type to which `vid` has been instantiated, if
     /// any.
     pub(crate) fn probe(&mut self, vid: TyVid) -> TypeVariableValue<'db> {
@@ -180,6 +262,11 @@ impl<'db> TypeVariableTable<'_, 'db> {
         self.storage.eq_relations.with_log(self.undo_log)
     }
 
+    #[inline]
+    fn sub_unification_table(&mut self) -> super::UnificationTable<'_, 'db, TyVidSubKey> {
+        self.storage.sub_unification_table.with_log(self.undo_log)
+    }
+
     /// Returns indices of all variables that are not yet
     /// instantiated.
     pub(crate) fn unresolved_variables(&mut self) -> Vec<TyVid> {
@@ -228,6 +315,36 @@ impl<'db> ut::UnifyKey for TyVidEqKey<'db> {
     fn tag() -> &'static str {
         "TyVidEqKey"
     }
+    fn order_roots(a: Self, _: &Self::Value, b: Self, _: &Self::Value) -> Option<(Self, Self)> {
+        if a.vid.as_u32() < b.vid.as_u32() { Some((a, b)) } else { Some((b, a)) }
+    }
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+pub(crate) struct TyVidSubKey {
+    vid: TyVid,
+}
+
+impl From<TyVid> for TyVidSubKey {
+    #[inline] // make this function eligible for inlining - it is quite hot.
+    fn from(vid: TyVid) -> Self {
+        TyVidSubKey { vid }
+    }
+}
+
+impl ut::UnifyKey for TyVidSubKey {
+    type Value = ();
+    #[inline]
+    fn index(&self) -> u32 {
+        self.vid.as_u32()
+    }
+    #[inline]
+    fn from_index(i: u32) -> TyVidSubKey {
+        TyVidSubKey { vid: TyVid::from_u32(i) }
+    }
+    fn tag() -> &'static str {
+        "TyVidSubKey"
+    }
 }
 
 impl<'db> ut::UnifyValue for TypeVariableValue<'db> {
diff --git a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/unify_key.rs b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/unify_key.rs
index b9afb45ba89..dc913b262a7 100644
--- a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/unify_key.rs
+++ b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/infer/unify_key.rs
@@ -139,6 +139,9 @@ impl<'db> UnifyKey for ConstVidKey<'db> {
     fn tag() -> &'static str {
         "ConstVidKey"
     }
+    fn order_roots(a: Self, _: &Self::Value, b: Self, _: &Self::Value) -> Option<(Self, Self)> {
+        if a.vid.as_u32() < b.vid.as_u32() { Some((a, b)) } else { Some((b, a)) }
+    }
 }
 
 impl<'db> UnifyValue for ConstVariableValue<'db> {
diff --git a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/mapping.rs b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/mapping.rs
index f66b8dace30..11bc6e6abe9 100644
--- a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/mapping.rs
+++ b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/mapping.rs
@@ -734,15 +734,13 @@ impl<'db, T: HasInterner<Interner = Interner> + ChalkToNextSolver<'db, U>, U>
             interner,
             self.binders.iter(Interner).map(|k| match &k.kind {
                 chalk_ir::VariableKind::Ty(ty_variable_kind) => match ty_variable_kind {
-                    TyVariableKind::General => rustc_type_ir::CanonicalVarKind::Ty(
-                        rustc_type_ir::CanonicalTyVarKind::General(UniverseIndex::ROOT),
-                    ),
-                    TyVariableKind::Integer => {
-                        rustc_type_ir::CanonicalVarKind::Ty(rustc_type_ir::CanonicalTyVarKind::Int)
-                    }
-                    TyVariableKind::Float => rustc_type_ir::CanonicalVarKind::Ty(
-                        rustc_type_ir::CanonicalTyVarKind::Float,
-                    ),
+                    // FIXME(next-solver): the info is incorrect, but we have no way to store the information in Chalk.
+                    TyVariableKind::General => rustc_type_ir::CanonicalVarKind::Ty {
+                        ui: UniverseIndex::ROOT,
+                        sub_root: BoundVar::from_u32(0),
+                    },
+                    TyVariableKind::Integer => rustc_type_ir::CanonicalVarKind::Int,
+                    TyVariableKind::Float => rustc_type_ir::CanonicalVarKind::Float,
                 },
                 chalk_ir::VariableKind::Lifetime => {
                     rustc_type_ir::CanonicalVarKind::Region(UniverseIndex::ROOT)
@@ -767,24 +765,20 @@ impl<'db, T: NextSolverToChalk<'db, U>, U: HasInterner<Interner = Interner>>
         let binders = chalk_ir::CanonicalVarKinds::from_iter(
             Interner,
             self.variables.iter().map(|v| match v {
-                rustc_type_ir::CanonicalVarKind::Ty(
-                    rustc_type_ir::CanonicalTyVarKind::General(ui),
-                ) => chalk_ir::CanonicalVarKind::new(
-                    chalk_ir::VariableKind::Ty(TyVariableKind::General),
-                    chalk_ir::UniverseIndex { counter: ui.as_usize() },
-                ),
-                rustc_type_ir::CanonicalVarKind::Ty(rustc_type_ir::CanonicalTyVarKind::Int) => {
+                rustc_type_ir::CanonicalVarKind::Ty { ui, sub_root: _ } => {
                     chalk_ir::CanonicalVarKind::new(
-                        chalk_ir::VariableKind::Ty(TyVariableKind::Integer),
-                        chalk_ir::UniverseIndex::root(),
-                    )
-                }
-                rustc_type_ir::CanonicalVarKind::Ty(rustc_type_ir::CanonicalTyVarKind::Float) => {
-                    chalk_ir::CanonicalVarKind::new(
-                        chalk_ir::VariableKind::Ty(TyVariableKind::Float),
-                        chalk_ir::UniverseIndex::root(),
+                        chalk_ir::VariableKind::Ty(TyVariableKind::General),
+                        chalk_ir::UniverseIndex { counter: ui.as_usize() },
                     )
                 }
+                rustc_type_ir::CanonicalVarKind::Int => chalk_ir::CanonicalVarKind::new(
+                    chalk_ir::VariableKind::Ty(TyVariableKind::Integer),
+                    chalk_ir::UniverseIndex::root(),
+                ),
+                rustc_type_ir::CanonicalVarKind::Float => chalk_ir::CanonicalVarKind::new(
+                    chalk_ir::VariableKind::Ty(TyVariableKind::Float),
+                    chalk_ir::UniverseIndex::root(),
+                ),
                 rustc_type_ir::CanonicalVarKind::Region(ui) => chalk_ir::CanonicalVarKind::new(
                     chalk_ir::VariableKind::Lifetime,
                     chalk_ir::UniverseIndex { counter: ui.as_usize() },
diff --git a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/solver.rs b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/solver.rs
index 385149d7843..dc5073305c8 100644
--- a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/solver.rs
+++ b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/solver.rs
@@ -9,6 +9,7 @@ use rustc_type_ir::{
     solve::{Certainty, NoSolution},
 };
 
+use crate::next_solver::CanonicalVarKind;
 use crate::next_solver::mapping::NextSolverToChalk;
 use crate::{
     TraitRefExt,
@@ -117,13 +118,14 @@ impl<'db> SolverDelegate for SolverContext<'db> {
         canonical.instantiate(self.cx(), &values)
     }
 
-    fn instantiate_canonical_var_with_infer(
+    fn instantiate_canonical_var(
         &self,
-        cv_info: rustc_type_ir::CanonicalVarKind<Self::Interner>,
-        _span: <Self::Interner as rustc_type_ir::Interner>::Span,
+        kind: CanonicalVarKind<'db>,
+        span: <Self::Interner as Interner>::Span,
+        var_values: &[GenericArg<'db>],
         universe_map: impl Fn(rustc_type_ir::UniverseIndex) -> rustc_type_ir::UniverseIndex,
-    ) -> <Self::Interner as rustc_type_ir::Interner>::GenericArg {
-        self.0.instantiate_canonical_var(cv_info, universe_map)
+    ) -> GenericArg<'db> {
+        self.0.instantiate_canonical_var(kind, var_values, universe_map)
     }
 
     fn add_item_bounds_for_hidden_type(
diff --git a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/util.rs b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/util.rs
index 50b96a160ed..97d3ea72c93 100644
--- a/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/util.rs
+++ b/src/tools/rust-analyzer/crates/hir-ty/src/next_solver/util.rs
@@ -532,17 +532,14 @@ pub(crate) fn mini_canonicalize<'db, T: TypeFoldable<DbInterner<'db>>>(
         max_universe: UniverseIndex::from_u32(1),
         variables: CanonicalVars::new_from_iter(
             context.cx(),
-            vars.iter().map(|(k, v)| match (*k).kind() {
+            vars.iter().enumerate().map(|(idx, (k, v))| match (*k).kind() {
                 GenericArgKind::Type(ty) => match ty.kind() {
-                    TyKind::Int(..) | TyKind::Uint(..) => {
-                        rustc_type_ir::CanonicalVarKind::Ty(rustc_type_ir::CanonicalTyVarKind::Int)
-                    }
-                    TyKind::Float(..) => rustc_type_ir::CanonicalVarKind::Ty(
-                        rustc_type_ir::CanonicalTyVarKind::Float,
-                    ),
-                    _ => rustc_type_ir::CanonicalVarKind::Ty(
-                        rustc_type_ir::CanonicalTyVarKind::General(UniverseIndex::ZERO),
-                    ),
+                    TyKind::Int(..) | TyKind::Uint(..) => rustc_type_ir::CanonicalVarKind::Int,
+                    TyKind::Float(..) => rustc_type_ir::CanonicalVarKind::Float,
+                    _ => rustc_type_ir::CanonicalVarKind::Ty {
+                        ui: UniverseIndex::ZERO,
+                        sub_root: BoundVar::from_usize(idx),
+                    },
                 },
                 GenericArgKind::Lifetime(_) => {
                     rustc_type_ir::CanonicalVarKind::Region(UniverseIndex::ZERO)