aboutsummaryrefslogtreecommitdiff
path: root/crates/hir_ty
diff options
context:
space:
mode:
Diffstat (limited to 'crates/hir_ty')
-rw-r--r--crates/hir_ty/src/autoderef.rs6
-rw-r--r--crates/hir_ty/src/builder.rs4
-rw-r--r--crates/hir_ty/src/db.rs2
-rw-r--r--crates/hir_ty/src/display.rs20
-rw-r--r--crates/hir_ty/src/infer.rs4
-rw-r--r--crates/hir_ty/src/infer/coerce.rs2
-rw-r--r--crates/hir_ty/src/infer/expr.rs12
-rw-r--r--crates/hir_ty/src/infer/pat.rs4
-rw-r--r--crates/hir_ty/src/infer/path.rs2
-rw-r--r--crates/hir_ty/src/infer/unify.rs2
-rw-r--r--crates/hir_ty/src/lib.rs697
-rw-r--r--crates/hir_ty/src/method_resolution.rs2
-rw-r--r--crates/hir_ty/src/traits.rs88
-rw-r--r--crates/hir_ty/src/traits/chalk/mapping.rs18
-rw-r--r--crates/hir_ty/src/types.rs416
-rw-r--r--crates/hir_ty/src/walk.rs381
16 files changed, 850 insertions, 810 deletions
diff --git a/crates/hir_ty/src/autoderef.rs b/crates/hir_ty/src/autoderef.rs
index 70c56cc45..7ca4af80e 100644
--- a/crates/hir_ty/src/autoderef.rs
+++ b/crates/hir_ty/src/autoderef.rs
@@ -12,10 +12,8 @@ use hir_expand::name::name;
12use log::{info, warn}; 12use log::{info, warn};
13 13
14use crate::{ 14use crate::{
15 db::HirDatabase, 15 db::HirDatabase, AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, DebruijnIndex,
16 traits::{InEnvironment, Solution}, 16 InEnvironment, Interner, Solution, Ty, TyBuilder, TyKind,
17 AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, DebruijnIndex, Interner, Ty,
18 TyBuilder, TyKind,
19}; 17};
20 18
21const AUTODEREF_RECURSION_LIMIT: usize = 10; 19const AUTODEREF_RECURSION_LIMIT: usize = 10;
diff --git a/crates/hir_ty/src/builder.rs b/crates/hir_ty/src/builder.rs
index 4a9a8058f..0bac31e4c 100644
--- a/crates/hir_ty/src/builder.rs
+++ b/crates/hir_ty/src/builder.rs
@@ -33,7 +33,7 @@ impl<D> TyBuilder<D> {
33 fn build_internal(self) -> (D, Substitution) { 33 fn build_internal(self) -> (D, Substitution) {
34 assert_eq!(self.vec.len(), self.param_count); 34 assert_eq!(self.vec.len(), self.param_count);
35 // FIXME: would be good to have a way to construct a chalk_ir::Substitution from the interned form 35 // FIXME: would be good to have a way to construct a chalk_ir::Substitution from the interned form
36 let subst = Substitution(self.vec); 36 let subst = Substitution::intern(self.vec);
37 (self.data, subst) 37 (self.data, subst)
38 } 38 }
39 39
@@ -138,7 +138,7 @@ impl TyBuilder<hir_def::AdtId> {
138 self.vec.push(fallback().cast(&Interner)); 138 self.vec.push(fallback().cast(&Interner));
139 } else { 139 } else {
140 // each default can depend on the previous parameters 140 // each default can depend on the previous parameters
141 let subst_so_far = Substitution(self.vec.clone()); 141 let subst_so_far = Substitution::intern(self.vec.clone());
142 self.vec.push(default_ty.clone().subst(&subst_so_far).cast(&Interner)); 142 self.vec.push(default_ty.clone().subst(&subst_so_far).cast(&Interner));
143 } 143 }
144 } 144 }
diff --git a/crates/hir_ty/src/db.rs b/crates/hir_ty/src/db.rs
index 58e4247c6..4300680d9 100644
--- a/crates/hir_ty/src/db.rs
+++ b/crates/hir_ty/src/db.rs
@@ -123,7 +123,7 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
123 &self, 123 &self,
124 krate: CrateId, 124 krate: CrateId,
125 goal: crate::Canonical<crate::InEnvironment<crate::DomainGoal>>, 125 goal: crate::Canonical<crate::InEnvironment<crate::DomainGoal>>,
126 ) -> Option<crate::traits::Solution>; 126 ) -> Option<crate::Solution>;
127 127
128 #[salsa::invoke(crate::traits::chalk::program_clauses_for_chalk_env_query)] 128 #[salsa::invoke(crate::traits::chalk::program_clauses_for_chalk_env_query)]
129 fn program_clauses_for_chalk_env( 129 fn program_clauses_for_chalk_env(
diff --git a/crates/hir_ty/src/display.rs b/crates/hir_ty/src/display.rs
index 385bd9405..148eb7506 100644
--- a/crates/hir_ty/src/display.rs
+++ b/crates/hir_ty/src/display.rs
@@ -260,7 +260,7 @@ impl HirDisplay for ProjectionTy {
260 write!(f, "<{} as {}", first_parameter, trait_.name)?; 260 write!(f, "<{} as {}", first_parameter, trait_.name)?;
261 if self.substitution.len(&Interner) > 1 { 261 if self.substitution.len(&Interner) > 1 {
262 write!(f, "<")?; 262 write!(f, "<")?;
263 f.write_joined(&self.substitution.interned(&Interner)[1..], ", ")?; 263 f.write_joined(&self.substitution.interned()[1..], ", ")?;
264 write!(f, ">")?; 264 write!(f, ">")?;
265 } 265 }
266 write!(f, ">::{}", f.db.type_alias_data(from_assoc_type_id(self.associated_ty_id)).name)?; 266 write!(f, ">::{}", f.db.type_alias_data(from_assoc_type_id(self.associated_ty_id)).name)?;
@@ -387,7 +387,7 @@ impl HirDisplay for Ty {
387 write!(f, ",)")?; 387 write!(f, ",)")?;
388 } else { 388 } else {
389 write!(f, "(")?; 389 write!(f, "(")?;
390 f.write_joined(&*substs.0, ", ")?; 390 f.write_joined(&*substs.interned(), ", ")?;
391 write!(f, ")")?; 391 write!(f, ")")?;
392 } 392 }
393 } 393 }
@@ -415,7 +415,7 @@ impl HirDisplay for Ty {
415 // We print all params except implicit impl Trait params. Still a bit weird; should we leave out parent and self? 415 // We print all params except implicit impl Trait params. Still a bit weird; should we leave out parent and self?
416 if total_len > 0 { 416 if total_len > 0 {
417 write!(f, "<")?; 417 write!(f, "<")?;
418 f.write_joined(&parameters.0[..total_len], ", ")?; 418 f.write_joined(&parameters.interned()[..total_len], ", ")?;
419 write!(f, ">")?; 419 write!(f, ">")?;
420 } 420 }
421 } 421 }
@@ -468,7 +468,7 @@ impl HirDisplay for Ty {
468 .map(|generic_def_id| f.db.generic_defaults(generic_def_id)) 468 .map(|generic_def_id| f.db.generic_defaults(generic_def_id))
469 .filter(|defaults| !defaults.is_empty()) 469 .filter(|defaults| !defaults.is_empty())
470 { 470 {
471 None => parameters.0.as_ref(), 471 None => parameters.interned().as_ref(),
472 Some(default_parameters) => { 472 Some(default_parameters) => {
473 let mut default_from = 0; 473 let mut default_from = 0;
474 for (i, parameter) in parameters.iter(&Interner).enumerate() { 474 for (i, parameter) in parameters.iter(&Interner).enumerate() {
@@ -490,11 +490,11 @@ impl HirDisplay for Ty {
490 } 490 }
491 } 491 }
492 } 492 }
493 &parameters.0[0..default_from] 493 &parameters.interned()[0..default_from]
494 } 494 }
495 } 495 }
496 } else { 496 } else {
497 parameters.0.as_ref() 497 parameters.interned().as_ref()
498 }; 498 };
499 if !parameters_to_write.is_empty() { 499 if !parameters_to_write.is_empty() {
500 write!(f, "<")?; 500 write!(f, "<")?;
@@ -517,7 +517,7 @@ impl HirDisplay for Ty {
517 write!(f, "{}::{}", trait_.name, type_alias_data.name)?; 517 write!(f, "{}::{}", trait_.name, type_alias_data.name)?;
518 if parameters.len(&Interner) > 0 { 518 if parameters.len(&Interner) > 0 {
519 write!(f, "<")?; 519 write!(f, "<")?;
520 f.write_joined(&*parameters.0, ", ")?; 520 f.write_joined(&*parameters.interned(), ", ")?;
521 write!(f, ">")?; 521 write!(f, ">")?;
522 } 522 }
523 } else { 523 } else {
@@ -727,13 +727,13 @@ fn write_bounds_like_dyn_trait(
727 // existential) here, which is the only thing that's 727 // existential) here, which is the only thing that's
728 // possible in actual Rust, and hence don't print it 728 // possible in actual Rust, and hence don't print it
729 write!(f, "{}", f.db.trait_data(trait_).name)?; 729 write!(f, "{}", f.db.trait_data(trait_).name)?;
730 if let [_, params @ ..] = &*trait_ref.substitution.0 { 730 if let [_, params @ ..] = &*trait_ref.substitution.interned() {
731 if is_fn_trait { 731 if is_fn_trait {
732 if let Some(args) = 732 if let Some(args) =
733 params.first().and_then(|it| it.assert_ty_ref(&Interner).as_tuple()) 733 params.first().and_then(|it| it.assert_ty_ref(&Interner).as_tuple())
734 { 734 {
735 write!(f, "(")?; 735 write!(f, "(")?;
736 f.write_joined(&*args.0, ", ")?; 736 f.write_joined(&*args.interned(), ", ")?;
737 write!(f, ")")?; 737 write!(f, ")")?;
738 } 738 }
739 } else if !params.is_empty() { 739 } else if !params.is_empty() {
@@ -789,7 +789,7 @@ impl TraitRef {
789 write!(f, "{}", f.db.trait_data(self.hir_trait_id()).name)?; 789 write!(f, "{}", f.db.trait_data(self.hir_trait_id()).name)?;
790 if self.substitution.len(&Interner) > 1 { 790 if self.substitution.len(&Interner) > 1 {
791 write!(f, "<")?; 791 write!(f, "<")?;
792 f.write_joined(&self.substitution.interned(&Interner)[1..], ", ")?; 792 f.write_joined(&self.substitution.interned()[1..], ", ")?;
793 write!(f, ">")?; 793 write!(f, ">")?;
794 } 794 }
795 Ok(()) 795 Ok(())
diff --git a/crates/hir_ty/src/infer.rs b/crates/hir_ty/src/infer.rs
index 1b1d4458c..bb885db35 100644
--- a/crates/hir_ty/src/infer.rs
+++ b/crates/hir_ty/src/infer.rs
@@ -37,8 +37,8 @@ use stdx::impl_from;
37use syntax::SmolStr; 37use syntax::SmolStr;
38 38
39use super::{ 39use super::{
40 traits::{DomainGoal, Guidance, Solution}, 40 DomainGoal, Guidance, InEnvironment, ProjectionTy, Solution, TraitEnvironment, TraitRef, Ty,
41 InEnvironment, ProjectionTy, TraitEnvironment, TraitRef, Ty, TypeWalk, 41 TypeWalk,
42}; 42};
43use crate::{ 43use crate::{
44 db::HirDatabase, infer::diagnostics::InferenceDiagnostic, lower::ImplTraitLoweringMode, 44 db::HirDatabase, infer::diagnostics::InferenceDiagnostic, lower::ImplTraitLoweringMode,
diff --git a/crates/hir_ty/src/infer/coerce.rs b/crates/hir_ty/src/infer/coerce.rs
index 028a4d568..32c273afc 100644
--- a/crates/hir_ty/src/infer/coerce.rs
+++ b/crates/hir_ty/src/infer/coerce.rs
@@ -7,7 +7,7 @@
7use chalk_ir::{cast::Cast, Mutability, TyVariableKind}; 7use chalk_ir::{cast::Cast, Mutability, TyVariableKind};
8use hir_def::lang_item::LangItemTarget; 8use hir_def::lang_item::LangItemTarget;
9 9
10use crate::{autoderef, traits::Solution, Interner, Ty, TyBuilder, TyKind}; 10use crate::{autoderef, Interner, Solution, Ty, TyBuilder, TyKind};
11 11
12use super::{InEnvironment, InferenceContext}; 12use super::{InEnvironment, InferenceContext};
13 13
diff --git a/crates/hir_ty/src/infer/expr.rs b/crates/hir_ty/src/infer/expr.rs
index c584a2c08..ccaae53e9 100644
--- a/crates/hir_ty/src/infer/expr.rs
+++ b/crates/hir_ty/src/infer/expr.rs
@@ -20,10 +20,10 @@ use crate::{
20 method_resolution, op, 20 method_resolution, op,
21 primitive::{self, UintTy}, 21 primitive::{self, UintTy},
22 to_chalk_trait_id, 22 to_chalk_trait_id,
23 traits::{chalk::from_chalk, FnTrait, InEnvironment}, 23 traits::{chalk::from_chalk, FnTrait},
24 utils::{generics, variant_data, Generics}, 24 utils::{generics, variant_data, Generics},
25 AdtId, Binders, CallableDefId, FnPointer, FnSig, Interner, Rawness, Scalar, Substitution, 25 AdtId, Binders, CallableDefId, FnPointer, FnSig, InEnvironment, Interner, Rawness, Scalar,
26 TraitRef, Ty, TyBuilder, TyKind, 26 Substitution, TraitRef, Ty, TyBuilder, TyKind,
27}; 27};
28 28
29use super::{ 29use super::{
@@ -452,11 +452,7 @@ impl<'a> InferenceContext<'a> {
452 }; 452 };
453 match canonicalized.decanonicalize_ty(derefed_ty.value).kind(&Interner) { 453 match canonicalized.decanonicalize_ty(derefed_ty.value).kind(&Interner) {
454 TyKind::Tuple(_, substs) => name.as_tuple_index().and_then(|idx| { 454 TyKind::Tuple(_, substs) => name.as_tuple_index().and_then(|idx| {
455 substs 455 substs.interned().get(idx).map(|a| a.assert_ty_ref(&Interner)).cloned()
456 .interned(&Interner)
457 .get(idx)
458 .map(|a| a.assert_ty_ref(&Interner))
459 .cloned()
460 }), 456 }),
461 TyKind::Adt(AdtId(hir_def::AdtId::StructId(s)), parameters) => { 457 TyKind::Adt(AdtId(hir_def::AdtId::StructId(s)), parameters) => {
462 let local_id = self.db.struct_data(*s).variant_data.field(name)?; 458 let local_id = self.db.struct_data(*s).variant_data.field(name)?;
diff --git a/crates/hir_ty/src/infer/pat.rs b/crates/hir_ty/src/infer/pat.rs
index 5b70d5e5a..469f37dd9 100644
--- a/crates/hir_ty/src/infer/pat.rs
+++ b/crates/hir_ty/src/infer/pat.rs
@@ -123,7 +123,7 @@ impl<'a> InferenceContext<'a> {
123 let ty = match &body[pat] { 123 let ty = match &body[pat] {
124 &Pat::Tuple { ref args, ellipsis } => { 124 &Pat::Tuple { ref args, ellipsis } => {
125 let expectations = match expected.as_tuple() { 125 let expectations = match expected.as_tuple() {
126 Some(parameters) => &*parameters.0, 126 Some(parameters) => &*parameters.interned(),
127 _ => &[], 127 _ => &[],
128 }; 128 };
129 129
@@ -239,7 +239,7 @@ impl<'a> InferenceContext<'a> {
239 let (inner_ty, alloc_ty) = match expected.as_adt() { 239 let (inner_ty, alloc_ty) = match expected.as_adt() {
240 Some((adt, subst)) if adt == box_adt => ( 240 Some((adt, subst)) if adt == box_adt => (
241 subst.at(&Interner, 0).assert_ty_ref(&Interner).clone(), 241 subst.at(&Interner, 0).assert_ty_ref(&Interner).clone(),
242 subst.interned(&Interner).get(1).and_then(|a| a.ty(&Interner).cloned()), 242 subst.interned().get(1).and_then(|a| a.ty(&Interner).cloned()),
243 ), 243 ),
244 _ => (self.result.standard_types.unknown.clone(), None), 244 _ => (self.result.standard_types.unknown.clone(), None),
245 }; 245 };
diff --git a/crates/hir_ty/src/infer/path.rs b/crates/hir_ty/src/infer/path.rs
index 671ea355f..637341b53 100644
--- a/crates/hir_ty/src/infer/path.rs
+++ b/crates/hir_ty/src/infer/path.rs
@@ -98,7 +98,7 @@ impl<'a> InferenceContext<'a> {
98 let substs = ctx.substs_from_path(path, typable, true); 98 let substs = ctx.substs_from_path(path, typable, true);
99 let ty = TyBuilder::value_ty(self.db, typable) 99 let ty = TyBuilder::value_ty(self.db, typable)
100 .use_parent_substs(&parent_substs) 100 .use_parent_substs(&parent_substs)
101 .fill(substs.interned(&Interner)[parent_substs.len(&Interner)..].iter().cloned()) 101 .fill(substs.interned()[parent_substs.len(&Interner)..].iter().cloned())
102 .build(); 102 .build();
103 Some(ty) 103 Some(ty)
104 } 104 }
diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs
index a04b935ef..b7bc48569 100644
--- a/crates/hir_ty/src/infer/unify.rs
+++ b/crates/hir_ty/src/infer/unify.rs
@@ -284,7 +284,7 @@ impl InferenceTable {
284 substs2: &Substitution, 284 substs2: &Substitution,
285 depth: usize, 285 depth: usize,
286 ) -> bool { 286 ) -> bool {
287 substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| { 287 substs1.iter(&Interner).zip(substs2.iter(&Interner)).all(|(t1, t2)| {
288 self.unify_inner(t1.assert_ty_ref(&Interner), t2.assert_ty_ref(&Interner), depth) 288 self.unify_inner(t1.assert_ty_ref(&Interner), t2.assert_ty_ref(&Interner), depth)
289 }) 289 })
290 } 290 }
diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs
index a8c87eadf..76609e2df 100644
--- a/crates/hir_ty/src/lib.rs
+++ b/crates/hir_ty/src/lib.rs
@@ -16,6 +16,8 @@ pub(crate) mod utils;
16mod chalk_cast; 16mod chalk_cast;
17mod chalk_ext; 17mod chalk_ext;
18mod builder; 18mod builder;
19mod walk;
20mod types;
19 21
20pub mod display; 22pub mod display;
21pub mod db; 23pub mod db;
@@ -26,23 +28,18 @@ mod tests;
26#[cfg(test)] 28#[cfg(test)]
27mod test_db; 29mod test_db;
28 30
29use std::{mem, sync::Arc}; 31use std::sync::Arc;
30 32
31use chalk_ir::cast::{CastTo, Caster};
32use itertools::Itertools; 33use itertools::Itertools;
33use smallvec::SmallVec; 34use smallvec::SmallVec;
34 35
35use base_db::salsa; 36use base_db::salsa;
36use hir_def::{ 37use hir_def::{
37 expr::ExprId, type_ref::Rawness, AssocContainerId, FunctionId, GenericDefId, HasModule, 38 expr::ExprId, type_ref::Rawness, AssocContainerId, FunctionId, GenericDefId, HasModule, Lookup,
38 LifetimeParamId, Lookup, TraitId, TypeAliasId, TypeParamId, 39 TraitId, TypeAliasId, TypeParamId,
39}; 40};
40 41
41use crate::{ 42use crate::{db::HirDatabase, display::HirDisplay, utils::generics};
42 db::HirDatabase,
43 display::HirDisplay,
44 utils::{generics, make_mut_slice},
45};
46 43
47pub use autoderef::autoderef; 44pub use autoderef::autoderef;
48pub use builder::TyBuilder; 45pub use builder::TyBuilder;
@@ -52,7 +49,9 @@ pub use lower::{
52 associated_type_shorthand_candidates, callable_item_sig, CallableDefId, ImplTraitLoweringMode, 49 associated_type_shorthand_candidates, callable_item_sig, CallableDefId, ImplTraitLoweringMode,
53 TyDefId, TyLoweringContext, ValueTyDefId, 50 TyDefId, TyLoweringContext, ValueTyDefId,
54}; 51};
55pub use traits::{AliasEq, DomainGoal, InEnvironment, TraitEnvironment}; 52pub use traits::TraitEnvironment;
53pub use types::*;
54pub use walk::TypeWalk;
56 55
57pub use chalk_ir::{ 56pub use chalk_ir::{
58 cast::Cast, AdtId, BoundVar, DebruijnIndex, Mutability, Safety, Scalar, TyVariableKind, 57 cast::Cast, AdtId, BoundVar, DebruijnIndex, Mutability, Safety, Scalar, TyVariableKind,
@@ -71,41 +70,6 @@ pub type CanonicalVarKinds = chalk_ir::CanonicalVarKinds<Interner>;
71 70
72pub type ChalkTraitId = chalk_ir::TraitId<Interner>; 71pub type ChalkTraitId = chalk_ir::TraitId<Interner>;
73 72
74#[derive(Clone, PartialEq, Eq, Debug, Hash)]
75pub enum Lifetime {
76 Parameter(LifetimeParamId),
77 Static,
78}
79
80#[derive(Clone, PartialEq, Eq, Debug, Hash)]
81pub struct OpaqueTy {
82 pub opaque_ty_id: OpaqueTyId,
83 pub substitution: Substitution,
84}
85
86impl TypeWalk for OpaqueTy {
87 fn walk(&self, f: &mut impl FnMut(&Ty)) {
88 self.substitution.walk(f);
89 }
90
91 fn walk_mut_binders(
92 &mut self,
93 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
94 binders: DebruijnIndex,
95 ) {
96 self.substitution.walk_mut_binders(f, binders);
97 }
98}
99
100/// A "projection" type corresponds to an (unnormalized)
101/// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
102/// trait and all its parameters are fully known.
103#[derive(Clone, PartialEq, Eq, Debug, Hash)]
104pub struct ProjectionTy {
105 pub associated_ty_id: AssocTypeId,
106 pub substitution: Substitution,
107}
108
109impl ProjectionTy { 73impl ProjectionTy {
110 pub fn trait_ref(&self, db: &dyn HirDatabase) -> TraitRef { 74 pub fn trait_ref(&self, db: &dyn HirDatabase) -> TraitRef {
111 TraitRef { 75 TraitRef {
@@ -115,7 +79,7 @@ impl ProjectionTy {
115 } 79 }
116 80
117 pub fn self_type_parameter(&self) -> &Ty { 81 pub fn self_type_parameter(&self) -> &Ty {
118 &self.substitution.interned(&Interner)[0].assert_ty_ref(&Interner) 82 &self.substitution.interned()[0].assert_ty_ref(&Interner)
119 } 83 }
120 84
121 fn trait_(&self, db: &dyn HirDatabase) -> TraitId { 85 fn trait_(&self, db: &dyn HirDatabase) -> TraitId {
@@ -126,322 +90,11 @@ impl ProjectionTy {
126 } 90 }
127} 91}
128 92
129impl TypeWalk for ProjectionTy {
130 fn walk(&self, f: &mut impl FnMut(&Ty)) {
131 self.substitution.walk(f);
132 }
133
134 fn walk_mut_binders(
135 &mut self,
136 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
137 binders: DebruijnIndex,
138 ) {
139 self.substitution.walk_mut_binders(f, binders);
140 }
141}
142
143#[derive(Clone, PartialEq, Eq, Debug, Hash)]
144pub struct DynTy {
145 /// The unknown self type.
146 pub bounds: Binders<QuantifiedWhereClauses>,
147}
148
149pub type FnSig = chalk_ir::FnSig<Interner>; 93pub type FnSig = chalk_ir::FnSig<Interner>;
150 94
151#[derive(Clone, PartialEq, Eq, Debug, Hash)]
152pub struct FnPointer {
153 pub num_args: usize,
154 pub sig: FnSig,
155 pub substs: Substitution,
156}
157
158#[derive(Clone, PartialEq, Eq, Debug, Hash)]
159pub enum AliasTy {
160 /// A "projection" type corresponds to an (unnormalized)
161 /// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
162 /// trait and all its parameters are fully known.
163 Projection(ProjectionTy),
164 /// An opaque type (`impl Trait`).
165 ///
166 /// This is currently only used for return type impl trait; each instance of
167 /// `impl Trait` in a return type gets its own ID.
168 Opaque(OpaqueTy),
169}
170
171impl TypeWalk for AliasTy {
172 fn walk(&self, f: &mut impl FnMut(&Ty)) {
173 match self {
174 AliasTy::Projection(it) => it.walk(f),
175 AliasTy::Opaque(it) => it.walk(f),
176 }
177 }
178
179 fn walk_mut_binders(
180 &mut self,
181 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
182 binders: DebruijnIndex,
183 ) {
184 match self {
185 AliasTy::Projection(it) => it.walk_mut_binders(f, binders),
186 AliasTy::Opaque(it) => it.walk_mut_binders(f, binders),
187 }
188 }
189}
190/// A type.
191///
192/// See also the `TyKind` enum in rustc (librustc/ty/sty.rs), which represents
193/// the same thing (but in a different way).
194///
195/// This should be cheap to clone.
196#[derive(Clone, PartialEq, Eq, Debug, Hash)]
197pub enum TyKind {
198 /// Structures, enumerations and unions.
199 Adt(AdtId<Interner>, Substitution),
200
201 /// Represents an associated item like `Iterator::Item`. This is used
202 /// when we have tried to normalize a projection like `T::Item` but
203 /// couldn't find a better representation. In that case, we generate
204 /// an **application type** like `(Iterator::Item)<T>`.
205 AssociatedType(AssocTypeId, Substitution),
206
207 /// a scalar type like `bool` or `u32`
208 Scalar(Scalar),
209
210 /// A tuple type. For example, `(i32, bool)`.
211 Tuple(usize, Substitution),
212
213 /// An array with the given length. Written as `[T; n]`.
214 Array(Ty),
215
216 /// The pointee of an array slice. Written as `[T]`.
217 Slice(Ty),
218
219 /// A raw pointer. Written as `*mut T` or `*const T`
220 Raw(Mutability, Ty),
221
222 /// A reference; a pointer with an associated lifetime. Written as
223 /// `&'a mut T` or `&'a T`.
224 Ref(Mutability, Ty),
225
226 /// This represents a placeholder for an opaque type in situations where we
227 /// don't know the hidden type (i.e. currently almost always). This is
228 /// analogous to the `AssociatedType` type constructor.
229 /// It is also used as the type of async block, with one type parameter
230 /// representing the Future::Output type.
231 OpaqueType(OpaqueTyId, Substitution),
232
233 /// The anonymous type of a function declaration/definition. Each
234 /// function has a unique type, which is output (for a function
235 /// named `foo` returning an `i32`) as `fn() -> i32 {foo}`.
236 ///
237 /// This includes tuple struct / enum variant constructors as well.
238 ///
239 /// For example the type of `bar` here:
240 ///
241 /// ```
242 /// fn foo() -> i32 { 1 }
243 /// let bar = foo; // bar: fn() -> i32 {foo}
244 /// ```
245 FnDef(FnDefId, Substitution),
246
247 /// The pointee of a string slice. Written as `str`.
248 Str,
249
250 /// The never type `!`.
251 Never,
252
253 /// The type of a specific closure.
254 ///
255 /// The closure signature is stored in a `FnPtr` type in the first type
256 /// parameter.
257 Closure(ClosureId, Substitution),
258
259 /// Represents a foreign type declared in external blocks.
260 ForeignType(ForeignDefId),
261
262 /// A pointer to a function. Written as `fn() -> i32`.
263 ///
264 /// For example the type of `bar` here:
265 ///
266 /// ```
267 /// fn foo() -> i32 { 1 }
268 /// let bar: fn() -> i32 = foo;
269 /// ```
270 Function(FnPointer),
271
272 /// An "alias" type represents some form of type alias, such as:
273 /// - An associated type projection like `<T as Iterator>::Item`
274 /// - `impl Trait` types
275 /// - Named type aliases like `type Foo<X> = Vec<X>`
276 Alias(AliasTy),
277
278 /// A placeholder for a type parameter; for example, `T` in `fn f<T>(x: T)
279 /// {}` when we're type-checking the body of that function. In this
280 /// situation, we know this stands for *some* type, but don't know the exact
281 /// type.
282 Placeholder(PlaceholderIndex),
283
284 /// A bound type variable. This is used in various places: when representing
285 /// some polymorphic type like the type of function `fn f<T>`, the type
286 /// parameters get turned into variables; during trait resolution, inference
287 /// variables get turned into bound variables and back; and in `Dyn` the
288 /// `Self` type is represented with a bound variable as well.
289 BoundVar(BoundVar),
290
291 /// A type variable used during type checking.
292 InferenceVar(InferenceVar, TyVariableKind),
293
294 /// A trait object (`dyn Trait` or bare `Trait` in pre-2018 Rust).
295 ///
296 /// The predicates are quantified over the `Self` type, i.e. `Ty::Bound(0)`
297 /// represents the `Self` type inside the bounds. This is currently
298 /// implicit; Chalk has the `Binders` struct to make it explicit, but it
299 /// didn't seem worth the overhead yet.
300 Dyn(DynTy),
301
302 /// A placeholder for a type which could not be computed; this is propagated
303 /// to avoid useless error messages. Doubles as a placeholder where type
304 /// variables are inserted before type checking, since we want to try to
305 /// infer a better type here anyway -- for the IDE use case, we want to try
306 /// to infer as much as possible even in the presence of type errors.
307 Unknown,
308}
309
310#[derive(Clone, PartialEq, Eq, Debug, Hash)]
311pub struct Ty(Arc<TyKind>);
312
313impl TyKind {
314 pub fn intern(self, _interner: &Interner) -> Ty {
315 Ty(Arc::new(self))
316 }
317}
318
319impl Ty {
320 pub fn kind(&self, _interner: &Interner) -> &TyKind {
321 &self.0
322 }
323
324 pub fn interned_mut(&mut self) -> &mut TyKind {
325 Arc::make_mut(&mut self.0)
326 }
327
328 pub fn into_inner(self) -> TyKind {
329 Arc::try_unwrap(self.0).unwrap_or_else(|a| (*a).clone())
330 }
331}
332
333#[derive(Clone, PartialEq, Eq, Debug, Hash)]
334pub struct GenericArg {
335 interned: GenericArgData,
336}
337
338#[derive(Clone, PartialEq, Eq, Debug, Hash)]
339pub enum GenericArgData {
340 Ty(Ty),
341}
342
343impl GenericArg {
344 /// Constructs a generic argument using `GenericArgData`.
345 pub fn new(_interner: &Interner, data: GenericArgData) -> Self {
346 GenericArg { interned: data }
347 }
348
349 /// Gets the interned value.
350 pub fn interned(&self) -> &GenericArgData {
351 &self.interned
352 }
353
354 /// Asserts that this is a type argument.
355 pub fn assert_ty_ref(&self, interner: &Interner) -> &Ty {
356 self.ty(interner).unwrap()
357 }
358
359 /// Checks whether the generic argument is a type.
360 pub fn is_ty(&self, _interner: &Interner) -> bool {
361 match self.interned() {
362 GenericArgData::Ty(_) => true,
363 }
364 }
365
366 /// Returns the type if it is one, `None` otherwise.
367 pub fn ty(&self, _interner: &Interner) -> Option<&Ty> {
368 match self.interned() {
369 GenericArgData::Ty(t) => Some(t),
370 }
371 }
372}
373
374impl TypeWalk for GenericArg {
375 fn walk(&self, f: &mut impl FnMut(&Ty)) {
376 match &self.interned {
377 GenericArgData::Ty(ty) => {
378 ty.walk(f);
379 }
380 }
381 }
382
383 fn walk_mut_binders(
384 &mut self,
385 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
386 binders: DebruijnIndex,
387 ) {
388 match &mut self.interned {
389 GenericArgData::Ty(ty) => {
390 ty.walk_mut_binders(f, binders);
391 }
392 }
393 }
394}
395
396/// A list of substitutions for generic parameters.
397#[derive(Clone, PartialEq, Eq, Debug, Hash)]
398pub struct Substitution(SmallVec<[GenericArg; 2]>);
399
400impl TypeWalk for Substitution {
401 fn walk(&self, f: &mut impl FnMut(&Ty)) {
402 for t in self.0.iter() {
403 t.walk(f);
404 }
405 }
406
407 fn walk_mut_binders(
408 &mut self,
409 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
410 binders: DebruijnIndex,
411 ) {
412 for t in &mut self.0 {
413 t.walk_mut_binders(f, binders);
414 }
415 }
416}
417
418impl Substitution { 95impl Substitution {
419 pub fn interned(&self, _: &Interner) -> &[GenericArg] {
420 &self.0
421 }
422
423 pub fn len(&self, _: &Interner) -> usize {
424 self.0.len()
425 }
426
427 pub fn is_empty(&self, _: &Interner) -> bool {
428 self.0.is_empty()
429 }
430
431 pub fn at(&self, _: &Interner, i: usize) -> &GenericArg {
432 &self.0[i]
433 }
434
435 pub fn empty(_: &Interner) -> Substitution {
436 Substitution(SmallVec::new())
437 }
438
439 pub fn iter(&self, _: &Interner) -> std::slice::Iter<'_, GenericArg> {
440 self.0.iter()
441 }
442
443 pub fn single(ty: Ty) -> Substitution { 96 pub fn single(ty: Ty) -> Substitution {
444 Substitution({ 97 Substitution::intern({
445 let mut v = SmallVec::new(); 98 let mut v = SmallVec::new();
446 v.push(ty.cast(&Interner)); 99 v.push(ty.cast(&Interner));
447 v 100 v
@@ -449,18 +102,13 @@ impl Substitution {
449 } 102 }
450 103
451 pub fn prefix(&self, n: usize) -> Substitution { 104 pub fn prefix(&self, n: usize) -> Substitution {
452 Substitution(self.0[..std::cmp::min(self.0.len(), n)].into()) 105 Substitution::intern(self.interned()[..std::cmp::min(self.len(&Interner), n)].into())
453 } 106 }
454 107
455 pub fn suffix(&self, n: usize) -> Substitution { 108 pub fn suffix(&self, n: usize) -> Substitution {
456 Substitution(self.0[self.0.len() - std::cmp::min(self.0.len(), n)..].into()) 109 Substitution::intern(
457 } 110 self.interned()[self.len(&Interner) - std::cmp::min(self.len(&Interner), n)..].into(),
458 111 )
459 pub fn from_iter(
460 interner: &Interner,
461 elements: impl IntoIterator<Item = impl CastTo<GenericArg>>,
462 ) -> Self {
463 Substitution(elements.into_iter().casted(interner).collect())
464 } 112 }
465} 113}
466 114
@@ -469,12 +117,6 @@ pub fn param_idx(db: &dyn HirDatabase, id: TypeParamId) -> Option<usize> {
469 generics(db.upcast(), id.parent).param_idx(id) 117 generics(db.upcast(), id.parent).param_idx(id)
470} 118}
471 119
472#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
473pub struct Binders<T> {
474 pub num_binders: usize,
475 pub value: T,
476}
477
478impl<T> Binders<T> { 120impl<T> Binders<T> {
479 pub fn new(num_binders: usize, value: T) -> Self { 121 pub fn new(num_binders: usize, value: T) -> Self {
480 Self { num_binders, value } 122 Self { num_binders, value }
@@ -522,27 +164,6 @@ impl<T: TypeWalk> Binders<T> {
522 } 164 }
523} 165}
524 166
525impl<T: TypeWalk> TypeWalk for Binders<T> {
526 fn walk(&self, f: &mut impl FnMut(&Ty)) {
527 self.value.walk(f);
528 }
529
530 fn walk_mut_binders(
531 &mut self,
532 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
533 binders: DebruijnIndex,
534 ) {
535 self.value.walk_mut_binders(f, binders.shifted_in())
536 }
537}
538
539/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait.
540#[derive(Clone, PartialEq, Eq, Debug, Hash)]
541pub struct TraitRef {
542 pub trait_id: ChalkTraitId,
543 pub substitution: Substitution,
544}
545
546impl TraitRef { 167impl TraitRef {
547 pub fn self_type_parameter(&self) -> &Ty { 168 pub fn self_type_parameter(&self) -> &Ty {
548 &self.substitution.at(&Interner, 0).assert_ty_ref(&Interner) 169 &self.substitution.at(&Interner, 0).assert_ty_ref(&Interner)
@@ -553,30 +174,6 @@ impl TraitRef {
553 } 174 }
554} 175}
555 176
556impl TypeWalk for TraitRef {
557 fn walk(&self, f: &mut impl FnMut(&Ty)) {
558 self.substitution.walk(f);
559 }
560
561 fn walk_mut_binders(
562 &mut self,
563 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
564 binders: DebruijnIndex,
565 ) {
566 self.substitution.walk_mut_binders(f, binders);
567 }
568}
569
570/// Like `generics::WherePredicate`, but with resolved types: A condition on the
571/// parameters of a generic item.
572#[derive(Debug, Clone, PartialEq, Eq, Hash)]
573pub enum WhereClause {
574 /// The given trait needs to be implemented for its type parameters.
575 Implemented(TraitRef),
576 /// An associated type bindings like in `Iterator<Item = T>`.
577 AliasEq(AliasEq),
578}
579
580impl WhereClause { 177impl WhereClause {
581 pub fn is_implemented(&self) -> bool { 178 pub fn is_implemented(&self) -> bool {
582 matches!(self, WhereClause::Implemented(_)) 179 matches!(self, WhereClause::Implemented(_))
@@ -593,56 +190,6 @@ impl WhereClause {
593 } 190 }
594} 191}
595 192
596impl TypeWalk for WhereClause {
597 fn walk(&self, f: &mut impl FnMut(&Ty)) {
598 match self {
599 WhereClause::Implemented(trait_ref) => trait_ref.walk(f),
600 WhereClause::AliasEq(alias_eq) => alias_eq.walk(f),
601 }
602 }
603
604 fn walk_mut_binders(
605 &mut self,
606 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
607 binders: DebruijnIndex,
608 ) {
609 match self {
610 WhereClause::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders),
611 WhereClause::AliasEq(alias_eq) => alias_eq.walk_mut_binders(f, binders),
612 }
613 }
614}
615
616pub type QuantifiedWhereClause = Binders<WhereClause>;
617
618#[derive(Debug, Clone, PartialEq, Eq, Hash)]
619pub struct QuantifiedWhereClauses(Arc<[QuantifiedWhereClause]>);
620
621impl QuantifiedWhereClauses {
622 pub fn from_iter(
623 _interner: &Interner,
624 elements: impl IntoIterator<Item = QuantifiedWhereClause>,
625 ) -> Self {
626 QuantifiedWhereClauses(elements.into_iter().collect())
627 }
628
629 pub fn interned(&self) -> &Arc<[QuantifiedWhereClause]> {
630 &self.0
631 }
632}
633
634/// Basically a claim (currently not validated / checked) that the contained
635/// type / trait ref contains no inference variables; any inference variables it
636/// contained have been replaced by bound variables, and `kinds` tells us how
637/// many there are and whether they were normal or float/int variables. This is
638/// used to erase irrelevant differences between types before using them in
639/// queries.
640#[derive(Debug, Clone, PartialEq, Eq, Hash)]
641pub struct Canonical<T> {
642 pub value: T,
643 pub binders: CanonicalVarKinds,
644}
645
646impl<T> Canonical<T> { 193impl<T> Canonical<T> {
647 pub fn new(value: T, kinds: impl IntoIterator<Item = TyVariableKind>) -> Self { 194 pub fn new(value: T, kinds: impl IntoIterator<Item = TyVariableKind>) -> Self {
648 let kinds = kinds.into_iter().map(|tk| { 195 let kinds = kinds.into_iter().map(|tk| {
@@ -679,7 +226,7 @@ impl CallableSig {
679 .substs 226 .substs
680 .clone() 227 .clone()
681 .shift_bound_vars_out(DebruijnIndex::ONE) 228 .shift_bound_vars_out(DebruijnIndex::ONE)
682 .interned(&Interner) 229 .interned()
683 .iter() 230 .iter()
684 .map(|arg| arg.assert_ty_ref(&Interner).clone()) 231 .map(|arg| arg.assert_ty_ref(&Interner).clone())
685 .collect(), 232 .collect(),
@@ -696,24 +243,6 @@ impl CallableSig {
696 } 243 }
697} 244}
698 245
699impl TypeWalk for CallableSig {
700 fn walk(&self, f: &mut impl FnMut(&Ty)) {
701 for t in self.params_and_return.iter() {
702 t.walk(f);
703 }
704 }
705
706 fn walk_mut_binders(
707 &mut self,
708 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
709 binders: DebruijnIndex,
710 ) {
711 for t in make_mut_slice(&mut self.params_and_return) {
712 t.walk_mut_binders(f, binders);
713 }
714 }
715}
716
717impl Ty { 246impl Ty {
718 pub fn as_reference(&self) -> Option<(&Ty, Mutability)> { 247 pub fn as_reference(&self) -> Option<(&Ty, Mutability)> {
719 match self.kind(&Interner) { 248 match self.kind(&Interner) {
@@ -984,200 +513,6 @@ impl Ty {
984 } 513 }
985} 514}
986 515
987/// This allows walking structures that contain types to do something with those
988/// types, similar to Chalk's `Fold` trait.
989pub trait TypeWalk {
990 fn walk(&self, f: &mut impl FnMut(&Ty));
991 fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
992 self.walk_mut_binders(&mut |ty, _binders| f(ty), DebruijnIndex::INNERMOST);
993 }
994 /// Walk the type, counting entered binders.
995 ///
996 /// `TyKind::Bound` variables use DeBruijn indexing, which means that 0 refers
997 /// to the innermost binder, 1 to the next, etc.. So when we want to
998 /// substitute a certain bound variable, we can't just walk the whole type
999 /// and blindly replace each instance of a certain index; when we 'enter'
1000 /// things that introduce new bound variables, we have to keep track of
1001 /// that. Currently, the only thing that introduces bound variables on our
1002 /// side are `TyKind::Dyn` and `TyKind::Opaque`, which each introduce a bound
1003 /// variable for the self type.
1004 fn walk_mut_binders(
1005 &mut self,
1006 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
1007 binders: DebruijnIndex,
1008 );
1009
1010 fn fold_binders(
1011 mut self,
1012 f: &mut impl FnMut(Ty, DebruijnIndex) -> Ty,
1013 binders: DebruijnIndex,
1014 ) -> Self
1015 where
1016 Self: Sized,
1017 {
1018 self.walk_mut_binders(
1019 &mut |ty_mut, binders| {
1020 let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner));
1021 *ty_mut = f(ty, binders);
1022 },
1023 binders,
1024 );
1025 self
1026 }
1027
1028 fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self
1029 where
1030 Self: Sized,
1031 {
1032 self.walk_mut(&mut |ty_mut| {
1033 let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner));
1034 *ty_mut = f(ty);
1035 });
1036 self
1037 }
1038
1039 /// Substitutes `TyKind::Bound` vars with the given substitution.
1040 fn subst_bound_vars(self, substs: &Substitution) -> Self
1041 where
1042 Self: Sized,
1043 {
1044 self.subst_bound_vars_at_depth(substs, DebruijnIndex::INNERMOST)
1045 }
1046
1047 /// Substitutes `TyKind::Bound` vars with the given substitution.
1048 fn subst_bound_vars_at_depth(mut self, substs: &Substitution, depth: DebruijnIndex) -> Self
1049 where
1050 Self: Sized,
1051 {
1052 self.walk_mut_binders(
1053 &mut |ty, binders| {
1054 if let &mut TyKind::BoundVar(bound) = ty.interned_mut() {
1055 if bound.debruijn >= binders {
1056 *ty = substs.0[bound.index]
1057 .assert_ty_ref(&Interner)
1058 .clone()
1059 .shift_bound_vars(binders);
1060 }
1061 }
1062 },
1063 depth,
1064 );
1065 self
1066 }
1067
1068 /// Shifts up debruijn indices of `TyKind::Bound` vars by `n`.
1069 fn shift_bound_vars(self, n: DebruijnIndex) -> Self
1070 where
1071 Self: Sized,
1072 {
1073 self.fold_binders(
1074 &mut |ty, binders| match ty.kind(&Interner) {
1075 TyKind::BoundVar(bound) if bound.debruijn >= binders => {
1076 TyKind::BoundVar(bound.shifted_in_from(n)).intern(&Interner)
1077 }
1078 _ => ty,
1079 },
1080 DebruijnIndex::INNERMOST,
1081 )
1082 }
1083
1084 /// Shifts debruijn indices of `TyKind::Bound` vars out (down) by `n`.
1085 fn shift_bound_vars_out(self, n: DebruijnIndex) -> Self
1086 where
1087 Self: Sized + std::fmt::Debug,
1088 {
1089 self.fold_binders(
1090 &mut |ty, binders| match ty.kind(&Interner) {
1091 TyKind::BoundVar(bound) if bound.debruijn >= binders => {
1092 TyKind::BoundVar(bound.shifted_out_to(n).unwrap_or(bound.clone()))
1093 .intern(&Interner)
1094 }
1095 _ => ty,
1096 },
1097 DebruijnIndex::INNERMOST,
1098 )
1099 }
1100}
1101
1102impl TypeWalk for Ty {
1103 fn walk(&self, f: &mut impl FnMut(&Ty)) {
1104 match self.kind(&Interner) {
1105 TyKind::Alias(AliasTy::Projection(p_ty)) => {
1106 for t in p_ty.substitution.iter(&Interner) {
1107 t.walk(f);
1108 }
1109 }
1110 TyKind::Alias(AliasTy::Opaque(o_ty)) => {
1111 for t in o_ty.substitution.iter(&Interner) {
1112 t.walk(f);
1113 }
1114 }
1115 TyKind::Dyn(dyn_ty) => {
1116 for p in dyn_ty.bounds.value.interned().iter() {
1117 p.walk(f);
1118 }
1119 }
1120 TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => {
1121 ty.walk(f);
1122 }
1123 _ => {
1124 if let Some(substs) = self.substs() {
1125 for t in substs.iter(&Interner) {
1126 t.walk(f);
1127 }
1128 }
1129 }
1130 }
1131 f(self);
1132 }
1133
1134 fn walk_mut_binders(
1135 &mut self,
1136 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
1137 binders: DebruijnIndex,
1138 ) {
1139 match self.interned_mut() {
1140 TyKind::Alias(AliasTy::Projection(p_ty)) => {
1141 p_ty.substitution.walk_mut_binders(f, binders);
1142 }
1143 TyKind::Dyn(dyn_ty) => {
1144 for p in make_mut_slice(&mut dyn_ty.bounds.value.0) {
1145 p.walk_mut_binders(f, binders.shifted_in());
1146 }
1147 }
1148 TyKind::Alias(AliasTy::Opaque(o_ty)) => {
1149 o_ty.substitution.walk_mut_binders(f, binders);
1150 }
1151 TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => {
1152 ty.walk_mut_binders(f, binders);
1153 }
1154 _ => {
1155 if let Some(substs) = self.substs_mut() {
1156 substs.walk_mut_binders(f, binders);
1157 }
1158 }
1159 }
1160 f(self, binders);
1161 }
1162}
1163
1164impl<T: TypeWalk> TypeWalk for Vec<T> {
1165 fn walk(&self, f: &mut impl FnMut(&Ty)) {
1166 for t in self {
1167 t.walk(f);
1168 }
1169 }
1170 fn walk_mut_binders(
1171 &mut self,
1172 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
1173 binders: DebruijnIndex,
1174 ) {
1175 for t in self {
1176 t.walk_mut_binders(f, binders);
1177 }
1178 }
1179}
1180
1181#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)] 516#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
1182pub enum ImplTraitId { 517pub enum ImplTraitId {
1183 ReturnTypeImplTrait(hir_def::FunctionId, u16), 518 ReturnTypeImplTrait(hir_def::FunctionId, u16),
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs
index a76586f0c..0e4a620b6 100644
--- a/crates/hir_ty/src/method_resolution.rs
+++ b/crates/hir_ty/src/method_resolution.rs
@@ -800,7 +800,7 @@ pub fn implements_trait_unique(
800 let goal = generic_implements_goal(db, env, trait_, ty.clone()); 800 let goal = generic_implements_goal(db, env, trait_, ty.clone());
801 let solution = db.trait_solve(krate, goal); 801 let solution = db.trait_solve(krate, goal);
802 802
803 matches!(solution, Some(crate::traits::Solution::Unique(_))) 803 matches!(solution, Some(crate::Solution::Unique(_)))
804} 804}
805 805
806/// This creates Substs for a trait with the given Self type and type variables 806/// This creates Substs for a trait with the given Self type and type variables
diff --git a/crates/hir_ty/src/traits.rs b/crates/hir_ty/src/traits.rs
index e5e8cff33..66d600bfc 100644
--- a/crates/hir_ty/src/traits.rs
+++ b/crates/hir_ty/src/traits.rs
@@ -8,8 +8,8 @@ use hir_def::{lang_item::LangItemTarget, TraitId};
8use stdx::panic_context; 8use stdx::panic_context;
9 9
10use crate::{ 10use crate::{
11 db::HirDatabase, AliasTy, Canonical, DebruijnIndex, HirDisplay, Substitution, Ty, TyKind, 11 db::HirDatabase, AliasEq, AliasTy, Canonical, DomainGoal, Guidance, HirDisplay, InEnvironment,
12 TypeWalk, WhereClause, 12 Solution, SolutionVariables, Ty, TyKind, WhereClause,
13}; 13};
14 14
15use self::chalk::{from_chalk, Interner, ToChalk}; 15use self::chalk::{from_chalk, Interner, ToChalk};
@@ -70,55 +70,6 @@ impl Default for TraitEnvironment {
70 } 70 }
71} 71}
72 72
73/// Something (usually a goal), along with an environment.
74#[derive(Clone, Debug, PartialEq, Eq, Hash)]
75pub struct InEnvironment<T> {
76 pub environment: chalk_ir::Environment<Interner>,
77 pub goal: T,
78}
79
80impl<T> InEnvironment<T> {
81 pub fn new(environment: chalk_ir::Environment<Interner>, value: T) -> InEnvironment<T> {
82 InEnvironment { environment, goal: value }
83 }
84}
85
86/// Something that needs to be proven (by Chalk) during type checking, e.g. that
87/// a certain type implements a certain trait. Proving the Obligation might
88/// result in additional information about inference variables.
89#[derive(Clone, Debug, PartialEq, Eq, Hash)]
90pub enum DomainGoal {
91 Holds(WhereClause),
92}
93
94#[derive(Clone, Debug, PartialEq, Eq, Hash)]
95pub struct AliasEq {
96 pub alias: AliasTy,
97 pub ty: Ty,
98}
99
100impl TypeWalk for AliasEq {
101 fn walk(&self, f: &mut impl FnMut(&Ty)) {
102 self.ty.walk(f);
103 match &self.alias {
104 AliasTy::Projection(projection_ty) => projection_ty.walk(f),
105 AliasTy::Opaque(opaque) => opaque.walk(f),
106 }
107 }
108
109 fn walk_mut_binders(
110 &mut self,
111 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
112 binders: DebruijnIndex,
113 ) {
114 self.ty.walk_mut_binders(f, binders);
115 match &mut self.alias {
116 AliasTy::Projection(projection_ty) => projection_ty.walk_mut_binders(f, binders),
117 AliasTy::Opaque(opaque) => opaque.walk_mut_binders(f, binders),
118 }
119 }
120}
121
122/// Solve a trait goal using Chalk. 73/// Solve a trait goal using Chalk.
123pub(crate) fn trait_solve_query( 74pub(crate) fn trait_solve_query(
124 db: &dyn HirDatabase, 75 db: &dyn HirDatabase,
@@ -246,41 +197,6 @@ fn solution_from_chalk(
246 } 197 }
247} 198}
248 199
249#[derive(Clone, Debug, PartialEq, Eq)]
250pub struct SolutionVariables(pub Canonical<Substitution>);
251
252#[derive(Clone, Debug, PartialEq, Eq)]
253/// A (possible) solution for a proposed goal.
254pub enum Solution {
255 /// The goal indeed holds, and there is a unique value for all existential
256 /// variables.
257 Unique(SolutionVariables),
258
259 /// The goal may be provable in multiple ways, but regardless we may have some guidance
260 /// for type inference. In this case, we don't return any lifetime
261 /// constraints, since we have not "committed" to any particular solution
262 /// yet.
263 Ambig(Guidance),
264}
265
266#[derive(Clone, Debug, PartialEq, Eq)]
267/// When a goal holds ambiguously (e.g., because there are multiple possible
268/// solutions), we issue a set of *guidance* back to type inference.
269pub enum Guidance {
270 /// The existential variables *must* have the given values if the goal is
271 /// ever to hold, but that alone isn't enough to guarantee the goal will
272 /// actually hold.
273 Definite(SolutionVariables),
274
275 /// There are multiple plausible values for the existentials, but the ones
276 /// here are suggested as the preferred choice heuristically. These should
277 /// be used for inference fallback only.
278 Suggested(SolutionVariables),
279
280 /// There's no useful information to feed back to type inference
281 Unknown,
282}
283
284#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] 200#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
285pub enum FnTrait { 201pub enum FnTrait {
286 FnOnce, 202 FnOnce,
diff --git a/crates/hir_ty/src/traits/chalk/mapping.rs b/crates/hir_ty/src/traits/chalk/mapping.rs
index 452b357e8..5e4f97a46 100644
--- a/crates/hir_ty/src/traits/chalk/mapping.rs
+++ b/crates/hir_ty/src/traits/chalk/mapping.rs
@@ -10,11 +10,9 @@ use base_db::salsa::InternKey;
10use hir_def::{GenericDefId, TypeAliasId}; 10use hir_def::{GenericDefId, TypeAliasId};
11 11
12use crate::{ 12use crate::{
13 db::HirDatabase, 13 db::HirDatabase, primitive::UintTy, AliasTy, CallableDefId, Canonical, DomainGoal, FnPointer,
14 primitive::UintTy, 14 GenericArg, InEnvironment, OpaqueTy, ProjectionTy, QuantifiedWhereClause, Scalar, Substitution,
15 traits::{Canonical, DomainGoal}, 15 TraitRef, Ty, TypeWalk, WhereClause,
16 AliasTy, CallableDefId, FnPointer, GenericArg, InEnvironment, OpaqueTy, ProjectionTy,
17 QuantifiedWhereClause, Scalar, Substitution, TraitRef, Ty, TypeWalk, WhereClause,
18}; 16};
19 17
20use super::interner::*; 18use super::interner::*;
@@ -220,8 +218,8 @@ impl ToChalk for GenericArg {
220 type Chalk = chalk_ir::GenericArg<Interner>; 218 type Chalk = chalk_ir::GenericArg<Interner>;
221 219
222 fn to_chalk(self, db: &dyn HirDatabase) -> Self::Chalk { 220 fn to_chalk(self, db: &dyn HirDatabase) -> Self::Chalk {
223 match self.interned { 221 match self.interned() {
224 crate::GenericArgData::Ty(ty) => ty.to_chalk(db).cast(&Interner), 222 crate::GenericArgData::Ty(ty) => ty.clone().to_chalk(db).cast(&Interner),
225 } 223 }
226 } 224 }
227 225
@@ -249,7 +247,7 @@ impl ToChalk for Substitution {
249 parameters: chalk_ir::Substitution<Interner>, 247 parameters: chalk_ir::Substitution<Interner>,
250 ) -> Substitution { 248 ) -> Substitution {
251 let tys = parameters.iter(&Interner).map(|p| from_chalk(db, p.clone())).collect(); 249 let tys = parameters.iter(&Interner).map(|p| from_chalk(db, p.clone())).collect();
252 Substitution(tys) 250 Substitution::intern(tys)
253 } 251 }
254} 252}
255 253
@@ -546,7 +544,7 @@ pub(super) fn generic_predicate_to_inline_bound(
546 // have the expected self type 544 // have the expected self type
547 return None; 545 return None;
548 } 546 }
549 let args_no_self = trait_ref.substitution.interned(&Interner)[1..] 547 let args_no_self = trait_ref.substitution.interned()[1..]
550 .iter() 548 .iter()
551 .map(|ty| ty.clone().to_chalk(db).cast(&Interner)) 549 .map(|ty| ty.clone().to_chalk(db).cast(&Interner))
552 .collect(); 550 .collect();
@@ -558,7 +556,7 @@ pub(super) fn generic_predicate_to_inline_bound(
558 return None; 556 return None;
559 } 557 }
560 let trait_ = projection_ty.trait_(db); 558 let trait_ = projection_ty.trait_(db);
561 let args_no_self = projection_ty.substitution.interned(&Interner)[1..] 559 let args_no_self = projection_ty.substitution.interned()[1..]
562 .iter() 560 .iter()
563 .map(|ty| ty.clone().to_chalk(db).cast(&Interner)) 561 .map(|ty| ty.clone().to_chalk(db).cast(&Interner))
564 .collect(); 562 .collect();
diff --git a/crates/hir_ty/src/types.rs b/crates/hir_ty/src/types.rs
new file mode 100644
index 000000000..53662fcdc
--- /dev/null
+++ b/crates/hir_ty/src/types.rs
@@ -0,0 +1,416 @@
1//! This is the home of `Ty` etc. until they get replaced by their chalk_ir
2//! equivalents.
3
4use std::sync::Arc;
5
6use chalk_ir::{
7 cast::{CastTo, Caster},
8 BoundVar, Mutability, Scalar, TyVariableKind,
9};
10use hir_def::LifetimeParamId;
11use smallvec::SmallVec;
12
13use crate::{
14 AssocTypeId, CanonicalVarKinds, ChalkTraitId, ClosureId, FnDefId, FnSig, ForeignDefId,
15 InferenceVar, Interner, OpaqueTyId, PlaceholderIndex,
16};
17
18#[derive(Clone, PartialEq, Eq, Debug, Hash)]
19pub enum Lifetime {
20 Parameter(LifetimeParamId),
21 Static,
22}
23
24#[derive(Clone, PartialEq, Eq, Debug, Hash)]
25pub struct OpaqueTy {
26 pub opaque_ty_id: OpaqueTyId,
27 pub substitution: Substitution,
28}
29
30/// A "projection" type corresponds to an (unnormalized)
31/// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
32/// trait and all its parameters are fully known.
33#[derive(Clone, PartialEq, Eq, Debug, Hash)]
34pub struct ProjectionTy {
35 pub associated_ty_id: AssocTypeId,
36 pub substitution: Substitution,
37}
38
39#[derive(Clone, PartialEq, Eq, Debug, Hash)]
40pub struct DynTy {
41 /// The unknown self type.
42 pub bounds: Binders<QuantifiedWhereClauses>,
43}
44
45#[derive(Clone, PartialEq, Eq, Debug, Hash)]
46pub struct FnPointer {
47 pub num_args: usize,
48 pub sig: FnSig,
49 pub substs: Substitution,
50}
51
52#[derive(Clone, PartialEq, Eq, Debug, Hash)]
53pub enum AliasTy {
54 /// A "projection" type corresponds to an (unnormalized)
55 /// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
56 /// trait and all its parameters are fully known.
57 Projection(ProjectionTy),
58 /// An opaque type (`impl Trait`).
59 ///
60 /// This is currently only used for return type impl trait; each instance of
61 /// `impl Trait` in a return type gets its own ID.
62 Opaque(OpaqueTy),
63}
64
65/// A type.
66///
67/// See also the `TyKind` enum in rustc (librustc/ty/sty.rs), which represents
68/// the same thing (but in a different way).
69///
70/// This should be cheap to clone.
71#[derive(Clone, PartialEq, Eq, Debug, Hash)]
72pub enum TyKind {
73 /// Structures, enumerations and unions.
74 Adt(chalk_ir::AdtId<Interner>, Substitution),
75
76 /// Represents an associated item like `Iterator::Item`. This is used
77 /// when we have tried to normalize a projection like `T::Item` but
78 /// couldn't find a better representation. In that case, we generate
79 /// an **application type** like `(Iterator::Item)<T>`.
80 AssociatedType(AssocTypeId, Substitution),
81
82 /// a scalar type like `bool` or `u32`
83 Scalar(Scalar),
84
85 /// A tuple type. For example, `(i32, bool)`.
86 Tuple(usize, Substitution),
87
88 /// An array with the given length. Written as `[T; n]`.
89 Array(Ty),
90
91 /// The pointee of an array slice. Written as `[T]`.
92 Slice(Ty),
93
94 /// A raw pointer. Written as `*mut T` or `*const T`
95 Raw(Mutability, Ty),
96
97 /// A reference; a pointer with an associated lifetime. Written as
98 /// `&'a mut T` or `&'a T`.
99 Ref(Mutability, Ty),
100
101 /// This represents a placeholder for an opaque type in situations where we
102 /// don't know the hidden type (i.e. currently almost always). This is
103 /// analogous to the `AssociatedType` type constructor.
104 /// It is also used as the type of async block, with one type parameter
105 /// representing the Future::Output type.
106 OpaqueType(OpaqueTyId, Substitution),
107
108 /// The anonymous type of a function declaration/definition. Each
109 /// function has a unique type, which is output (for a function
110 /// named `foo` returning an `i32`) as `fn() -> i32 {foo}`.
111 ///
112 /// This includes tuple struct / enum variant constructors as well.
113 ///
114 /// For example the type of `bar` here:
115 ///
116 /// ```
117 /// fn foo() -> i32 { 1 }
118 /// let bar = foo; // bar: fn() -> i32 {foo}
119 /// ```
120 FnDef(FnDefId, Substitution),
121
122 /// The pointee of a string slice. Written as `str`.
123 Str,
124
125 /// The never type `!`.
126 Never,
127
128 /// The type of a specific closure.
129 ///
130 /// The closure signature is stored in a `FnPtr` type in the first type
131 /// parameter.
132 Closure(ClosureId, Substitution),
133
134 /// Represents a foreign type declared in external blocks.
135 ForeignType(ForeignDefId),
136
137 /// A pointer to a function. Written as `fn() -> i32`.
138 ///
139 /// For example the type of `bar` here:
140 ///
141 /// ```
142 /// fn foo() -> i32 { 1 }
143 /// let bar: fn() -> i32 = foo;
144 /// ```
145 Function(FnPointer),
146
147 /// An "alias" type represents some form of type alias, such as:
148 /// - An associated type projection like `<T as Iterator>::Item`
149 /// - `impl Trait` types
150 /// - Named type aliases like `type Foo<X> = Vec<X>`
151 Alias(AliasTy),
152
153 /// A placeholder for a type parameter; for example, `T` in `fn f<T>(x: T)
154 /// {}` when we're type-checking the body of that function. In this
155 /// situation, we know this stands for *some* type, but don't know the exact
156 /// type.
157 Placeholder(PlaceholderIndex),
158
159 /// A bound type variable. This is used in various places: when representing
160 /// some polymorphic type like the type of function `fn f<T>`, the type
161 /// parameters get turned into variables; during trait resolution, inference
162 /// variables get turned into bound variables and back; and in `Dyn` the
163 /// `Self` type is represented with a bound variable as well.
164 BoundVar(BoundVar),
165
166 /// A type variable used during type checking.
167 InferenceVar(InferenceVar, TyVariableKind),
168
169 /// A trait object (`dyn Trait` or bare `Trait` in pre-2018 Rust).
170 ///
171 /// The predicates are quantified over the `Self` type, i.e. `Ty::Bound(0)`
172 /// represents the `Self` type inside the bounds. This is currently
173 /// implicit; Chalk has the `Binders` struct to make it explicit, but it
174 /// didn't seem worth the overhead yet.
175 Dyn(DynTy),
176
177 /// A placeholder for a type which could not be computed; this is propagated
178 /// to avoid useless error messages. Doubles as a placeholder where type
179 /// variables are inserted before type checking, since we want to try to
180 /// infer a better type here anyway -- for the IDE use case, we want to try
181 /// to infer as much as possible even in the presence of type errors.
182 Unknown,
183}
184
185#[derive(Clone, PartialEq, Eq, Debug, Hash)]
186pub struct Ty(Arc<TyKind>);
187
188impl TyKind {
189 pub fn intern(self, _interner: &Interner) -> Ty {
190 Ty(Arc::new(self))
191 }
192}
193
194impl Ty {
195 pub fn kind(&self, _interner: &Interner) -> &TyKind {
196 &self.0
197 }
198
199 pub fn interned_mut(&mut self) -> &mut TyKind {
200 Arc::make_mut(&mut self.0)
201 }
202
203 pub fn into_inner(self) -> TyKind {
204 Arc::try_unwrap(self.0).unwrap_or_else(|a| (*a).clone())
205 }
206}
207
208#[derive(Clone, PartialEq, Eq, Debug, Hash)]
209pub struct GenericArg {
210 interned: GenericArgData,
211}
212
213#[derive(Clone, PartialEq, Eq, Debug, Hash)]
214pub enum GenericArgData {
215 Ty(Ty),
216}
217
218impl GenericArg {
219 /// Constructs a generic argument using `GenericArgData`.
220 pub fn new(_interner: &Interner, data: GenericArgData) -> Self {
221 GenericArg { interned: data }
222 }
223
224 /// Gets the interned value.
225 pub fn interned(&self) -> &GenericArgData {
226 &self.interned
227 }
228
229 /// Asserts that this is a type argument.
230 pub fn assert_ty_ref(&self, interner: &Interner) -> &Ty {
231 self.ty(interner).unwrap()
232 }
233
234 /// Checks whether the generic argument is a type.
235 pub fn is_ty(&self, _interner: &Interner) -> bool {
236 match self.interned() {
237 GenericArgData::Ty(_) => true,
238 }
239 }
240
241 /// Returns the type if it is one, `None` otherwise.
242 pub fn ty(&self, _interner: &Interner) -> Option<&Ty> {
243 match self.interned() {
244 GenericArgData::Ty(t) => Some(t),
245 }
246 }
247
248 pub fn interned_mut(&mut self) -> &mut GenericArgData {
249 &mut self.interned
250 }
251}
252
253/// A list of substitutions for generic parameters.
254#[derive(Clone, PartialEq, Eq, Debug, Hash)]
255pub struct Substitution(SmallVec<[GenericArg; 2]>);
256
257impl Substitution {
258 pub fn interned(&self) -> &[GenericArg] {
259 &self.0
260 }
261
262 pub fn len(&self, _: &Interner) -> usize {
263 self.0.len()
264 }
265
266 pub fn is_empty(&self, _: &Interner) -> bool {
267 self.0.is_empty()
268 }
269
270 pub fn at(&self, _: &Interner, i: usize) -> &GenericArg {
271 &self.0[i]
272 }
273
274 pub fn empty(_: &Interner) -> Substitution {
275 Substitution(SmallVec::new())
276 }
277
278 pub fn iter(&self, _: &Interner) -> std::slice::Iter<'_, GenericArg> {
279 self.0.iter()
280 }
281
282 pub fn from_iter(
283 interner: &Interner,
284 elements: impl IntoIterator<Item = impl CastTo<GenericArg>>,
285 ) -> Self {
286 Substitution(elements.into_iter().casted(interner).collect())
287 }
288
289 // We can hopefully add this to Chalk
290 pub fn intern(interned: SmallVec<[GenericArg; 2]>) -> Substitution {
291 Substitution(interned)
292 }
293
294 pub fn interned_mut(&mut self) -> &mut SmallVec<[GenericArg; 2]> {
295 &mut self.0
296 }
297}
298
299#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
300pub struct Binders<T> {
301 pub num_binders: usize,
302 pub value: T,
303}
304
305/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait.
306#[derive(Clone, PartialEq, Eq, Debug, Hash)]
307pub struct TraitRef {
308 pub trait_id: ChalkTraitId,
309 pub substitution: Substitution,
310}
311
312/// Like `generics::WherePredicate`, but with resolved types: A condition on the
313/// parameters of a generic item.
314#[derive(Debug, Clone, PartialEq, Eq, Hash)]
315pub enum WhereClause {
316 /// The given trait needs to be implemented for its type parameters.
317 Implemented(TraitRef),
318 /// An associated type bindings like in `Iterator<Item = T>`.
319 AliasEq(AliasEq),
320}
321
322pub type QuantifiedWhereClause = Binders<WhereClause>;
323
324#[derive(Debug, Clone, PartialEq, Eq, Hash)]
325pub struct QuantifiedWhereClauses(Arc<[QuantifiedWhereClause]>);
326
327impl QuantifiedWhereClauses {
328 pub fn from_iter(
329 _interner: &Interner,
330 elements: impl IntoIterator<Item = QuantifiedWhereClause>,
331 ) -> Self {
332 QuantifiedWhereClauses(elements.into_iter().collect())
333 }
334
335 pub fn interned(&self) -> &Arc<[QuantifiedWhereClause]> {
336 &self.0
337 }
338
339 pub fn interned_mut(&mut self) -> &mut Arc<[QuantifiedWhereClause]> {
340 &mut self.0
341 }
342}
343
344/// Basically a claim (currently not validated / checked) that the contained
345/// type / trait ref contains no inference variables; any inference variables it
346/// contained have been replaced by bound variables, and `kinds` tells us how
347/// many there are and whether they were normal or float/int variables. This is
348/// used to erase irrelevant differences between types before using them in
349/// queries.
350#[derive(Debug, Clone, PartialEq, Eq, Hash)]
351pub struct Canonical<T> {
352 pub value: T,
353 pub binders: CanonicalVarKinds,
354}
355
356/// Something (usually a goal), along with an environment.
357#[derive(Clone, Debug, PartialEq, Eq, Hash)]
358pub struct InEnvironment<T> {
359 pub environment: chalk_ir::Environment<Interner>,
360 pub goal: T,
361}
362
363impl<T> InEnvironment<T> {
364 pub fn new(environment: chalk_ir::Environment<Interner>, value: T) -> InEnvironment<T> {
365 InEnvironment { environment, goal: value }
366 }
367}
368
369/// Something that needs to be proven (by Chalk) during type checking, e.g. that
370/// a certain type implements a certain trait. Proving the Obligation might
371/// result in additional information about inference variables.
372#[derive(Clone, Debug, PartialEq, Eq, Hash)]
373pub enum DomainGoal {
374 Holds(WhereClause),
375}
376
377#[derive(Clone, Debug, PartialEq, Eq, Hash)]
378pub struct AliasEq {
379 pub alias: AliasTy,
380 pub ty: Ty,
381}
382
383#[derive(Clone, Debug, PartialEq, Eq)]
384pub struct SolutionVariables(pub Canonical<Substitution>);
385
386#[derive(Clone, Debug, PartialEq, Eq)]
387/// A (possible) solution for a proposed goal.
388pub enum Solution {
389 /// The goal indeed holds, and there is a unique value for all existential
390 /// variables.
391 Unique(SolutionVariables),
392
393 /// The goal may be provable in multiple ways, but regardless we may have some guidance
394 /// for type inference. In this case, we don't return any lifetime
395 /// constraints, since we have not "committed" to any particular solution
396 /// yet.
397 Ambig(Guidance),
398}
399
400#[derive(Clone, Debug, PartialEq, Eq)]
401/// When a goal holds ambiguously (e.g., because there are multiple possible
402/// solutions), we issue a set of *guidance* back to type inference.
403pub enum Guidance {
404 /// The existential variables *must* have the given values if the goal is
405 /// ever to hold, but that alone isn't enough to guarantee the goal will
406 /// actually hold.
407 Definite(SolutionVariables),
408
409 /// There are multiple plausible values for the existentials, but the ones
410 /// here are suggested as the preferred choice heuristically. These should
411 /// be used for inference fallback only.
412 Suggested(SolutionVariables),
413
414 /// There's no useful information to feed back to type inference
415 Unknown,
416}
diff --git a/crates/hir_ty/src/walk.rs b/crates/hir_ty/src/walk.rs
new file mode 100644
index 000000000..bfb3f1041
--- /dev/null
+++ b/crates/hir_ty/src/walk.rs
@@ -0,0 +1,381 @@
1//! The `TypeWalk` trait (probably to be replaced by Chalk's `Fold` and
2//! `Visit`).
3
4use std::mem;
5
6use chalk_ir::DebruijnIndex;
7
8use crate::{
9 utils::make_mut_slice, AliasEq, AliasTy, Binders, CallableSig, GenericArg, GenericArgData,
10 Interner, OpaqueTy, ProjectionTy, Substitution, TraitRef, Ty, TyKind, WhereClause,
11};
12
13/// This allows walking structures that contain types to do something with those
14/// types, similar to Chalk's `Fold` trait.
15pub trait TypeWalk {
16 fn walk(&self, f: &mut impl FnMut(&Ty));
17 fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
18 self.walk_mut_binders(&mut |ty, _binders| f(ty), DebruijnIndex::INNERMOST);
19 }
20 /// Walk the type, counting entered binders.
21 ///
22 /// `TyKind::Bound` variables use DeBruijn indexing, which means that 0 refers
23 /// to the innermost binder, 1 to the next, etc.. So when we want to
24 /// substitute a certain bound variable, we can't just walk the whole type
25 /// and blindly replace each instance of a certain index; when we 'enter'
26 /// things that introduce new bound variables, we have to keep track of
27 /// that. Currently, the only thing that introduces bound variables on our
28 /// side are `TyKind::Dyn` and `TyKind::Opaque`, which each introduce a bound
29 /// variable for the self type.
30 fn walk_mut_binders(
31 &mut self,
32 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
33 binders: DebruijnIndex,
34 );
35
36 fn fold_binders(
37 mut self,
38 f: &mut impl FnMut(Ty, DebruijnIndex) -> Ty,
39 binders: DebruijnIndex,
40 ) -> Self
41 where
42 Self: Sized,
43 {
44 self.walk_mut_binders(
45 &mut |ty_mut, binders| {
46 let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner));
47 *ty_mut = f(ty, binders);
48 },
49 binders,
50 );
51 self
52 }
53
54 fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self
55 where
56 Self: Sized,
57 {
58 self.walk_mut(&mut |ty_mut| {
59 let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner));
60 *ty_mut = f(ty);
61 });
62 self
63 }
64
65 /// Substitutes `TyKind::Bound` vars with the given substitution.
66 fn subst_bound_vars(self, substs: &Substitution) -> Self
67 where
68 Self: Sized,
69 {
70 self.subst_bound_vars_at_depth(substs, DebruijnIndex::INNERMOST)
71 }
72
73 /// Substitutes `TyKind::Bound` vars with the given substitution.
74 fn subst_bound_vars_at_depth(mut self, substs: &Substitution, depth: DebruijnIndex) -> Self
75 where
76 Self: Sized,
77 {
78 self.walk_mut_binders(
79 &mut |ty, binders| {
80 if let &mut TyKind::BoundVar(bound) = ty.interned_mut() {
81 if bound.debruijn >= binders {
82 *ty = substs.interned()[bound.index]
83 .assert_ty_ref(&Interner)
84 .clone()
85 .shift_bound_vars(binders);
86 }
87 }
88 },
89 depth,
90 );
91 self
92 }
93
94 /// Shifts up debruijn indices of `TyKind::Bound` vars by `n`.
95 fn shift_bound_vars(self, n: DebruijnIndex) -> Self
96 where
97 Self: Sized,
98 {
99 self.fold_binders(
100 &mut |ty, binders| match ty.kind(&Interner) {
101 TyKind::BoundVar(bound) if bound.debruijn >= binders => {
102 TyKind::BoundVar(bound.shifted_in_from(n)).intern(&Interner)
103 }
104 _ => ty,
105 },
106 DebruijnIndex::INNERMOST,
107 )
108 }
109
110 /// Shifts debruijn indices of `TyKind::Bound` vars out (down) by `n`.
111 fn shift_bound_vars_out(self, n: DebruijnIndex) -> Self
112 where
113 Self: Sized + std::fmt::Debug,
114 {
115 self.fold_binders(
116 &mut |ty, binders| match ty.kind(&Interner) {
117 TyKind::BoundVar(bound) if bound.debruijn >= binders => {
118 TyKind::BoundVar(bound.shifted_out_to(n).unwrap_or(bound.clone()))
119 .intern(&Interner)
120 }
121 _ => ty,
122 },
123 DebruijnIndex::INNERMOST,
124 )
125 }
126}
127
128impl TypeWalk for Ty {
129 fn walk(&self, f: &mut impl FnMut(&Ty)) {
130 match self.kind(&Interner) {
131 TyKind::Alias(AliasTy::Projection(p_ty)) => {
132 for t in p_ty.substitution.iter(&Interner) {
133 t.walk(f);
134 }
135 }
136 TyKind::Alias(AliasTy::Opaque(o_ty)) => {
137 for t in o_ty.substitution.iter(&Interner) {
138 t.walk(f);
139 }
140 }
141 TyKind::Dyn(dyn_ty) => {
142 for p in dyn_ty.bounds.value.interned().iter() {
143 p.walk(f);
144 }
145 }
146 TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => {
147 ty.walk(f);
148 }
149 _ => {
150 if let Some(substs) = self.substs() {
151 for t in substs.iter(&Interner) {
152 t.walk(f);
153 }
154 }
155 }
156 }
157 f(self);
158 }
159
160 fn walk_mut_binders(
161 &mut self,
162 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
163 binders: DebruijnIndex,
164 ) {
165 match self.interned_mut() {
166 TyKind::Alias(AliasTy::Projection(p_ty)) => {
167 p_ty.substitution.walk_mut_binders(f, binders);
168 }
169 TyKind::Dyn(dyn_ty) => {
170 for p in make_mut_slice(dyn_ty.bounds.value.interned_mut()) {
171 p.walk_mut_binders(f, binders.shifted_in());
172 }
173 }
174 TyKind::Alias(AliasTy::Opaque(o_ty)) => {
175 o_ty.substitution.walk_mut_binders(f, binders);
176 }
177 TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => {
178 ty.walk_mut_binders(f, binders);
179 }
180 _ => {
181 if let Some(substs) = self.substs_mut() {
182 substs.walk_mut_binders(f, binders);
183 }
184 }
185 }
186 f(self, binders);
187 }
188}
189
190impl<T: TypeWalk> TypeWalk for Vec<T> {
191 fn walk(&self, f: &mut impl FnMut(&Ty)) {
192 for t in self {
193 t.walk(f);
194 }
195 }
196 fn walk_mut_binders(
197 &mut self,
198 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
199 binders: DebruijnIndex,
200 ) {
201 for t in self {
202 t.walk_mut_binders(f, binders);
203 }
204 }
205}
206
207impl TypeWalk for OpaqueTy {
208 fn walk(&self, f: &mut impl FnMut(&Ty)) {
209 self.substitution.walk(f);
210 }
211
212 fn walk_mut_binders(
213 &mut self,
214 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
215 binders: DebruijnIndex,
216 ) {
217 self.substitution.walk_mut_binders(f, binders);
218 }
219}
220
221impl TypeWalk for ProjectionTy {
222 fn walk(&self, f: &mut impl FnMut(&Ty)) {
223 self.substitution.walk(f);
224 }
225
226 fn walk_mut_binders(
227 &mut self,
228 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
229 binders: DebruijnIndex,
230 ) {
231 self.substitution.walk_mut_binders(f, binders);
232 }
233}
234
235impl TypeWalk for AliasTy {
236 fn walk(&self, f: &mut impl FnMut(&Ty)) {
237 match self {
238 AliasTy::Projection(it) => it.walk(f),
239 AliasTy::Opaque(it) => it.walk(f),
240 }
241 }
242
243 fn walk_mut_binders(
244 &mut self,
245 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
246 binders: DebruijnIndex,
247 ) {
248 match self {
249 AliasTy::Projection(it) => it.walk_mut_binders(f, binders),
250 AliasTy::Opaque(it) => it.walk_mut_binders(f, binders),
251 }
252 }
253}
254
255impl TypeWalk for GenericArg {
256 fn walk(&self, f: &mut impl FnMut(&Ty)) {
257 match &self.interned() {
258 GenericArgData::Ty(ty) => {
259 ty.walk(f);
260 }
261 }
262 }
263
264 fn walk_mut_binders(
265 &mut self,
266 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
267 binders: DebruijnIndex,
268 ) {
269 match self.interned_mut() {
270 GenericArgData::Ty(ty) => {
271 ty.walk_mut_binders(f, binders);
272 }
273 }
274 }
275}
276
277impl TypeWalk for Substitution {
278 fn walk(&self, f: &mut impl FnMut(&Ty)) {
279 for t in self.iter(&Interner) {
280 t.walk(f);
281 }
282 }
283
284 fn walk_mut_binders(
285 &mut self,
286 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
287 binders: DebruijnIndex,
288 ) {
289 for t in self.interned_mut() {
290 t.walk_mut_binders(f, binders);
291 }
292 }
293}
294
295impl<T: TypeWalk> TypeWalk for Binders<T> {
296 fn walk(&self, f: &mut impl FnMut(&Ty)) {
297 self.value.walk(f);
298 }
299
300 fn walk_mut_binders(
301 &mut self,
302 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
303 binders: DebruijnIndex,
304 ) {
305 self.value.walk_mut_binders(f, binders.shifted_in())
306 }
307}
308
309impl TypeWalk for TraitRef {
310 fn walk(&self, f: &mut impl FnMut(&Ty)) {
311 self.substitution.walk(f);
312 }
313
314 fn walk_mut_binders(
315 &mut self,
316 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
317 binders: DebruijnIndex,
318 ) {
319 self.substitution.walk_mut_binders(f, binders);
320 }
321}
322
323impl TypeWalk for WhereClause {
324 fn walk(&self, f: &mut impl FnMut(&Ty)) {
325 match self {
326 WhereClause::Implemented(trait_ref) => trait_ref.walk(f),
327 WhereClause::AliasEq(alias_eq) => alias_eq.walk(f),
328 }
329 }
330
331 fn walk_mut_binders(
332 &mut self,
333 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
334 binders: DebruijnIndex,
335 ) {
336 match self {
337 WhereClause::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders),
338 WhereClause::AliasEq(alias_eq) => alias_eq.walk_mut_binders(f, binders),
339 }
340 }
341}
342
343impl TypeWalk for CallableSig {
344 fn walk(&self, f: &mut impl FnMut(&Ty)) {
345 for t in self.params_and_return.iter() {
346 t.walk(f);
347 }
348 }
349
350 fn walk_mut_binders(
351 &mut self,
352 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
353 binders: DebruijnIndex,
354 ) {
355 for t in make_mut_slice(&mut self.params_and_return) {
356 t.walk_mut_binders(f, binders);
357 }
358 }
359}
360
361impl TypeWalk for AliasEq {
362 fn walk(&self, f: &mut impl FnMut(&Ty)) {
363 self.ty.walk(f);
364 match &self.alias {
365 AliasTy::Projection(projection_ty) => projection_ty.walk(f),
366 AliasTy::Opaque(opaque) => opaque.walk(f),
367 }
368 }
369
370 fn walk_mut_binders(
371 &mut self,
372 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
373 binders: DebruijnIndex,
374 ) {
375 self.ty.walk_mut_binders(f, binders);
376 match &mut self.alias {
377 AliasTy::Projection(projection_ty) => projection_ty.walk_mut_binders(f, binders),
378 AliasTy::Opaque(opaque) => opaque.walk_mut_binders(f, binders),
379 }
380 }
381}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-25 02:37:06 +0000