bendns' repos / rust-analyzer
Unnamed repository; edit this file 'description' to name the repository.
Diffstat
-rw-r--r--Cargo.lock45
-rw-r--r--Cargo.toml16
-rw-r--r--crates/hir-ty/src/next_solver/infer/canonical/canonicalizer.rs41
-rw-r--r--crates/hir-ty/src/next_solver/infer/canonical/mod.rs59
-rw-r--r--crates/hir-ty/src/next_solver/infer/context.rs8
-rw-r--r--crates/hir-ty/src/next_solver/infer/mod.rs8
-rw-r--r--crates/hir-ty/src/next_solver/infer/snapshot/undo_log.rs4
-rw-r--r--crates/hir-ty/src/next_solver/infer/type_variable.rs117
-rw-r--r--crates/hir-ty/src/next_solver/infer/unify_key.rs3
-rw-r--r--crates/hir-ty/src/next_solver/mapping.rs42
-rw-r--r--crates/hir-ty/src/next_solver/solver.rs12
-rw-r--r--crates/hir-ty/src/next_solver/util.rs17
12 files changed, 256 insertions, 116 deletions
diff --git a/Cargo.lock b/Cargo.lock
index 344e6d101f..b70b89ea54 100644
--- a/Cargo.lock
+++ b/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/Cargo.toml b/Cargo.toml
index f325027ee5..c5ffad544a 100644
--- a/Cargo.toml
+++ b/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/crates/hir-ty/src/next_solver/infer/canonical/canonicalizer.rs b/crates/hir-ty/src/next_solver/infer/canonical/canonicalizer.rs
index 5d11525cd1..ffb9c076fa 100644
--- a/crates/hir-ty/src/next_solver/infer/canonical/canonicalizer.rs
+++ b/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/crates/hir-ty/src/next_solver/infer/canonical/mod.rs b/crates/hir-ty/src/next_solver/infer/canonical/mod.rs
index ec41111ed8..8db4320acc 100644
--- a/crates/hir-ty/src/next_solver/infer/canonical/mod.rs
+++ b/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/crates/hir-ty/src/next_solver/infer/context.rs b/crates/hir-ty/src/next_solver/infer/context.rs
index 93fd6eeab3..45ce7e6f6c 100644
--- a/crates/hir-ty/src/next_solver/infer/context.rs
+++ b/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/crates/hir-ty/src/next_solver/infer/mod.rs b/crates/hir-ty/src/next_solver/infer/mod.rs
index 2630f2a8cc..ce6c941287 100644
--- a/crates/hir-ty/src/next_solver/infer/mod.rs
+++ b/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/crates/hir-ty/src/next_solver/infer/snapshot/undo_log.rs b/crates/hir-ty/src/next_solver/infer/snapshot/undo_log.rs
index 0fa6421f51..28ae56f4ee 100644
--- a/crates/hir-ty/src/next_solver/infer/snapshot/undo_log.rs
+++ b/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/crates/hir-ty/src/next_solver/infer/type_variable.rs b/crates/hir-ty/src/next_solver/infer/type_variable.rs
index 5217308af4..b640039af6 100644
--- a/crates/hir-ty/src/next_solver/infer/type_variable.rs
+++ b/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/crates/hir-ty/src/next_solver/infer/unify_key.rs b/crates/hir-ty/src/next_solver/infer/unify_key.rs
index b9afb45ba8..dc913b262a 100644
--- a/crates/hir-ty/src/next_solver/infer/unify_key.rs
+++ b/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/crates/hir-ty/src/next_solver/mapping.rs b/crates/hir-ty/src/next_solver/mapping.rs
index f66b8dace3..11bc6e6abe 100644
--- a/crates/hir-ty/src/next_solver/mapping.rs
+++ b/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/crates/hir-ty/src/next_solver/solver.rs b/crates/hir-ty/src/next_solver/solver.rs
index 385149d784..dc5073305c 100644
--- a/crates/hir-ty/src/next_solver/solver.rs
+++ b/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/crates/hir-ty/src/next_solver/util.rs b/crates/hir-ty/src/next_solver/util.rs
index 50b96a160e..97d3ea72c9 100644
--- a/crates/hir-ty/src/next_solver/util.rs
+++ b/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)