diff options
Diffstat (limited to 'src')
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) |