aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Cargo.lock8
-rw-r--r--crates/hir/src/lib.rs4
-rw-r--r--crates/hir_ty/src/builder.rs12
-rw-r--r--crates/hir_ty/src/chalk_cast.rs65
-rw-r--r--crates/hir_ty/src/display.rs18
-rw-r--r--crates/hir_ty/src/infer.rs26
-rw-r--r--crates/hir_ty/src/infer/coerce.rs10
-rw-r--r--crates/hir_ty/src/infer/expr.rs3
-rw-r--r--crates/hir_ty/src/infer/unify.rs166
-rw-r--r--crates/hir_ty/src/lib.rs128
-rw-r--r--crates/hir_ty/src/lower.rs41
-rw-r--r--crates/hir_ty/src/method_resolution.rs23
-rw-r--r--crates/hir_ty/src/traits.rs28
-rw-r--r--crates/hir_ty/src/traits/chalk.rs75
-rw-r--r--crates/hir_ty/src/traits/chalk/mapping.rs431
-rw-r--r--crates/hir_ty/src/types.rs549
-rw-r--r--crates/hir_ty/src/utils.rs18
-rw-r--r--crates/hir_ty/src/walk.rs287
-rw-r--r--crates/rust-analyzer/Cargo.toml2
19 files changed, 344 insertions, 1550 deletions
diff --git a/Cargo.lock b/Cargo.lock
index bcb1cbd9f..d7e6d3ac8 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -852,9 +852,9 @@ dependencies = [
852 852
853[[package]] 853[[package]]
854name = "lsp-types" 854name = "lsp-types"
855version = "0.88.0" 855version = "0.89.0"
856source = "registry+https://github.com/rust-lang/crates.io-index" 856source = "registry+https://github.com/rust-lang/crates.io-index"
857checksum = "d8e8e042772e4e10b3785822f63c82399d0dd233825de44d2596f7fa86e023e0" 857checksum = "07731ecd4ee0654728359a5b95e2a254c857876c04b85225496a35d60345daa7"
858dependencies = [ 858dependencies = [
859 "bitflags", 859 "bitflags",
860 "serde", 860 "serde",
@@ -1577,9 +1577,9 @@ dependencies = [
1577 1577
1578[[package]] 1578[[package]]
1579name = "syn" 1579name = "syn"
1580version = "1.0.68" 1580version = "1.0.69"
1581source = "registry+https://github.com/rust-lang/crates.io-index" 1581source = "registry+https://github.com/rust-lang/crates.io-index"
1582checksum = "3ce15dd3ed8aa2f8eeac4716d6ef5ab58b6b9256db41d7e1a0224c2788e8fd87" 1582checksum = "48fe99c6bd8b1cc636890bcc071842de909d902c81ac7dab53ba33c421ab8ffb"
1583dependencies = [ 1583dependencies = [
1584 "proc-macro2", 1584 "proc-macro2",
1585 "quote", 1585 "quote",
diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index 0afc06906..817a01db1 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -1903,7 +1903,9 @@ impl Type {
1903 | TyKind::Dyn(_) 1903 | TyKind::Dyn(_)
1904 | TyKind::Function(_) 1904 | TyKind::Function(_)
1905 | TyKind::Alias(_) 1905 | TyKind::Alias(_)
1906 | TyKind::Foreign(_) => false, 1906 | TyKind::Foreign(_)
1907 | TyKind::Generator(..)
1908 | TyKind::GeneratorWitness(..) => false,
1907 } 1909 }
1908 } 1910 }
1909 } 1911 }
diff --git a/crates/hir_ty/src/builder.rs b/crates/hir_ty/src/builder.rs
index 09512d1ce..e25ef866d 100644
--- a/crates/hir_ty/src/builder.rs
+++ b/crates/hir_ty/src/builder.rs
@@ -4,6 +4,7 @@ use std::iter;
4 4
5use chalk_ir::{ 5use chalk_ir::{
6 cast::{Cast, CastTo, Caster}, 6 cast::{Cast, CastTo, Caster},
7 fold::Fold,
7 interner::HasInterner, 8 interner::HasInterner,
8 AdtId, BoundVar, DebruijnIndex, Safety, Scalar, 9 AdtId, BoundVar, DebruijnIndex, Safety, Scalar,
9}; 10};
@@ -13,7 +14,7 @@ use smallvec::SmallVec;
13use crate::{ 14use crate::{
14 db::HirDatabase, primitive, to_assoc_type_id, to_chalk_trait_id, utils::generics, Binders, 15 db::HirDatabase, primitive, to_assoc_type_id, to_chalk_trait_id, utils::generics, Binders,
15 CallableSig, FnPointer, FnSig, FnSubst, GenericArg, Interner, ProjectionTy, Substitution, 16 CallableSig, FnPointer, FnSig, FnSubst, GenericArg, Interner, ProjectionTy, Substitution,
16 TraitRef, Ty, TyDefId, TyExt, TyKind, TypeWalk, ValueTyDefId, 17 TraitRef, Ty, TyDefId, TyExt, TyKind, ValueTyDefId,
17}; 18};
18 19
19/// This is a builder for `Ty` or anything that needs a `Substitution`. 20/// This is a builder for `Ty` or anything that needs a `Substitution`.
@@ -32,8 +33,7 @@ impl<D> TyBuilder<D> {
32 33
33 fn build_internal(self) -> (D, Substitution) { 34 fn build_internal(self) -> (D, Substitution) {
34 assert_eq!(self.vec.len(), self.param_count); 35 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 36 let subst = Substitution::from_iter(&Interner, self.vec);
36 let subst = Substitution::intern(self.vec);
37 (self.data, subst) 37 (self.data, subst)
38 } 38 }
39 39
@@ -141,7 +141,7 @@ impl TyBuilder<hir_def::AdtId> {
141 self.vec.push(fallback().cast(&Interner)); 141 self.vec.push(fallback().cast(&Interner));
142 } else { 142 } else {
143 // each default can depend on the previous parameters 143 // each default can depend on the previous parameters
144 let subst_so_far = Substitution::intern(self.vec.clone()); 144 let subst_so_far = Substitution::from_iter(&Interner, self.vec.clone());
145 self.vec 145 self.vec
146 .push(default_ty.clone().substitute(&Interner, &subst_so_far).cast(&Interner)); 146 .push(default_ty.clone().substitute(&Interner, &subst_so_far).cast(&Interner));
147 } 147 }
@@ -196,13 +196,13 @@ impl TyBuilder<TypeAliasId> {
196 } 196 }
197} 197}
198 198
199impl<T: TypeWalk + HasInterner<Interner = Interner>> TyBuilder<Binders<T>> { 199impl<T: HasInterner<Interner = Interner> + Fold<Interner>> TyBuilder<Binders<T>> {
200 fn subst_binders(b: Binders<T>) -> Self { 200 fn subst_binders(b: Binders<T>) -> Self {
201 let param_count = b.binders.len(&Interner); 201 let param_count = b.binders.len(&Interner);
202 TyBuilder::new(b, param_count) 202 TyBuilder::new(b, param_count)
203 } 203 }
204 204
205 pub fn build(self) -> T { 205 pub fn build(self) -> <T as Fold<Interner>>::Result {
206 let (b, subst) = self.build_internal(); 206 let (b, subst) = self.build_internal();
207 b.substitute(&Interner, &subst) 207 b.substitute(&Interner, &subst)
208 } 208 }
diff --git a/crates/hir_ty/src/chalk_cast.rs b/crates/hir_ty/src/chalk_cast.rs
index df6492113..f27dee3fd 100644
--- a/crates/hir_ty/src/chalk_cast.rs
+++ b/crates/hir_ty/src/chalk_cast.rs
@@ -1,11 +1,8 @@
1//! Implementations of the Chalk `Cast` trait for our types. 1//! Implementations of the Chalk `Cast` trait for our types.
2 2
3use chalk_ir::{ 3use chalk_ir::interner::HasInterner;
4 cast::{Cast, CastTo},
5 interner::HasInterner,
6};
7 4
8use crate::{AliasEq, DomainGoal, GenericArg, GenericArgData, Interner, TraitRef, Ty, WhereClause}; 5use crate::{CallableSig, ReturnTypeImplTraits};
9 6
10macro_rules! has_interner { 7macro_rules! has_interner {
11 ($t:ty) => { 8 ($t:ty) => {
@@ -15,59 +12,5 @@ macro_rules! has_interner {
15 }; 12 };
16} 13}
17 14
18has_interner!(WhereClause); 15has_interner!(CallableSig);
19has_interner!(DomainGoal); 16has_interner!(ReturnTypeImplTraits);
20has_interner!(GenericArg);
21has_interner!(Ty);
22
23impl CastTo<WhereClause> for TraitRef {
24 fn cast_to(self, _interner: &Interner) -> WhereClause {
25 WhereClause::Implemented(self)
26 }
27}
28
29impl CastTo<WhereClause> for AliasEq {
30 fn cast_to(self, _interner: &Interner) -> WhereClause {
31 WhereClause::AliasEq(self)
32 }
33}
34
35impl CastTo<DomainGoal> for WhereClause {
36 fn cast_to(self, _interner: &Interner) -> DomainGoal {
37 DomainGoal::Holds(self)
38 }
39}
40
41impl CastTo<GenericArg> for Ty {
42 fn cast_to(self, interner: &Interner) -> GenericArg {
43 GenericArg::new(interner, GenericArgData::Ty(self))
44 }
45}
46
47macro_rules! transitive_impl {
48 ($a:ty, $b:ty, $c:ty) => {
49 impl CastTo<$c> for $a {
50 fn cast_to(self, interner: &Interner) -> $c {
51 self.cast::<$b>(interner).cast(interner)
52 }
53 }
54 };
55}
56
57// In Chalk, these can be done as blanket impls, but that doesn't work here
58// because of coherence
59
60transitive_impl!(TraitRef, WhereClause, DomainGoal);
61transitive_impl!(AliasEq, WhereClause, DomainGoal);
62
63macro_rules! reflexive_impl {
64 ($a:ty) => {
65 impl CastTo<$a> for $a {
66 fn cast_to(self, _interner: &Interner) -> $a {
67 self
68 }
69 }
70 };
71}
72
73reflexive_impl!(GenericArg);
diff --git a/crates/hir_ty/src/display.rs b/crates/hir_ty/src/display.rs
index e0ca96c6d..d7a3977e5 100644
--- a/crates/hir_ty/src/display.rs
+++ b/crates/hir_ty/src/display.rs
@@ -287,6 +287,8 @@ impl HirDisplay for GenericArg {
287 fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> { 287 fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
288 match self.interned() { 288 match self.interned() {
289 crate::GenericArgData::Ty(ty) => ty.hir_fmt(f), 289 crate::GenericArgData::Ty(ty) => ty.hir_fmt(f),
290 crate::GenericArgData::Lifetime(lt) => lt.hir_fmt(f),
291 crate::GenericArgData::Const(c) => c.hir_fmt(f),
290 } 292 }
291 } 293 }
292} 294}
@@ -664,6 +666,8 @@ impl HirDisplay for Ty {
664 write!(f, "{{unknown}}")?; 666 write!(f, "{{unknown}}")?;
665 } 667 }
666 TyKind::InferenceVar(..) => write!(f, "_")?, 668 TyKind::InferenceVar(..) => write!(f, "_")?,
669 TyKind::Generator(..) => write!(f, "{{generator}}")?,
670 TyKind::GeneratorWitness(..) => write!(f, "{{generator witness}}")?,
667 } 671 }
668 Ok(()) 672 Ok(())
669 } 673 }
@@ -741,7 +745,7 @@ fn write_bounds_like_dyn_trait(
741 if !first { 745 if !first {
742 write!(f, " + ")?; 746 write!(f, " + ")?;
743 } 747 }
744 // We assume that the self type is $0 (i.e. the 748 // We assume that the self type is ^0.0 (i.e. the
745 // existential) here, which is the only thing that's 749 // existential) here, which is the only thing that's
746 // possible in actual Rust, and hence don't print it 750 // possible in actual Rust, and hence don't print it
747 write!(f, "{}", f.db.trait_data(trait_).name)?; 751 write!(f, "{}", f.db.trait_data(trait_).name)?;
@@ -783,6 +787,10 @@ fn write_bounds_like_dyn_trait(
783 } 787 }
784 ty.hir_fmt(f)?; 788 ty.hir_fmt(f)?;
785 } 789 }
790
791 // FIXME implement these
792 WhereClause::LifetimeOutlives(_) => {}
793 WhereClause::TypeOutlives(_) => {}
786 } 794 }
787 first = false; 795 first = false;
788 } 796 }
@@ -837,6 +845,10 @@ impl HirDisplay for WhereClause {
837 ty.hir_fmt(f)?; 845 ty.hir_fmt(f)?;
838 } 846 }
839 WhereClause::AliasEq(_) => write!(f, "{{error}}")?, 847 WhereClause::AliasEq(_) => write!(f, "{{error}}")?,
848
849 // FIXME implement these
850 WhereClause::TypeOutlives(..) => {}
851 WhereClause::LifetimeOutlives(..) => {}
840 } 852 }
841 Ok(()) 853 Ok(())
842 } 854 }
@@ -881,9 +893,11 @@ impl HirDisplay for DomainGoal {
881 DomainGoal::Holds(wc) => { 893 DomainGoal::Holds(wc) => {
882 write!(f, "Holds(")?; 894 write!(f, "Holds(")?;
883 wc.hir_fmt(f)?; 895 wc.hir_fmt(f)?;
884 write!(f, ")") 896 write!(f, ")")?;
885 } 897 }
898 _ => write!(f, "?")?,
886 } 899 }
900 Ok(())
887 } 901 }
888} 902}
889 903
diff --git a/crates/hir_ty/src/infer.rs b/crates/hir_ty/src/infer.rs
index 531159e54..bf2da2d4a 100644
--- a/crates/hir_ty/src/infer.rs
+++ b/crates/hir_ty/src/infer.rs
@@ -18,7 +18,7 @@ use std::mem;
18use std::ops::Index; 18use std::ops::Index;
19use std::sync::Arc; 19use std::sync::Arc;
20 20
21use chalk_ir::{cast::Cast, Mutability}; 21use chalk_ir::{cast::Cast, DebruijnIndex, Mutability};
22use hir_def::{ 22use hir_def::{
23 body::Body, 23 body::Body,
24 data::{ConstData, FunctionData, StaticData}, 24 data::{ConstData, FunctionData, StaticData},
@@ -38,11 +38,11 @@ use syntax::SmolStr;
38 38
39use super::{ 39use super::{
40 DomainGoal, Guidance, InEnvironment, ProjectionTy, Solution, TraitEnvironment, TraitRef, Ty, 40 DomainGoal, Guidance, InEnvironment, ProjectionTy, Solution, TraitEnvironment, TraitRef, Ty,
41 TypeWalk,
42}; 41};
43use crate::{ 42use crate::{
44 db::HirDatabase, infer::diagnostics::InferenceDiagnostic, lower::ImplTraitLoweringMode, 43 db::HirDatabase, fold_tys, infer::diagnostics::InferenceDiagnostic,
45 to_assoc_type_id, AliasEq, AliasTy, Canonical, Interner, TyBuilder, TyExt, TyKind, 44 lower::ImplTraitLoweringMode, to_assoc_type_id, AliasEq, AliasTy, Canonical, Interner,
45 TyBuilder, TyExt, TyKind,
46}; 46};
47 47
48// This lint has a false positive here. See the link below for details. 48// This lint has a false positive here. See the link below for details.
@@ -323,7 +323,7 @@ impl<'a> InferenceContext<'a> {
323 } 323 }
324 324
325 fn insert_type_vars(&mut self, ty: Ty) -> Ty { 325 fn insert_type_vars(&mut self, ty: Ty) -> Ty {
326 ty.fold(&mut |ty| self.insert_type_vars_shallow(ty)) 326 fold_tys(ty, |ty, _| self.insert_type_vars_shallow(ty), DebruijnIndex::INNERMOST)
327 } 327 }
328 328
329 fn resolve_obligations_as_possible(&mut self) { 329 fn resolve_obligations_as_possible(&mut self) {
@@ -434,12 +434,16 @@ impl<'a> InferenceContext<'a> {
434 /// to do it as well. 434 /// to do it as well.
435 fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty { 435 fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty {
436 let ty = self.resolve_ty_as_possible(ty); 436 let ty = self.resolve_ty_as_possible(ty);
437 ty.fold(&mut |ty| match ty.kind(&Interner) { 437 fold_tys(
438 TyKind::Alias(AliasTy::Projection(proj_ty)) => { 438 ty,
439 self.normalize_projection_ty(proj_ty.clone()) 439 |ty, _| match ty.kind(&Interner) {
440 } 440 TyKind::Alias(AliasTy::Projection(proj_ty)) => {
441 _ => ty, 441 self.normalize_projection_ty(proj_ty.clone())
442 }) 442 }
443 _ => ty,
444 },
445 DebruijnIndex::INNERMOST,
446 )
443 } 447 }
444 448
445 fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty { 449 fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty {
diff --git a/crates/hir_ty/src/infer/coerce.rs b/crates/hir_ty/src/infer/coerce.rs
index fd679f444..1f463a425 100644
--- a/crates/hir_ty/src/infer/coerce.rs
+++ b/crates/hir_ty/src/infer/coerce.rs
@@ -71,12 +71,14 @@ impl<'a> InferenceContext<'a> {
71 } 71 }
72 72
73 // Pointer weakening and function to pointer 73 // Pointer weakening and function to pointer
74 match (from_ty.interned_mut(), to_ty.kind(&Interner)) { 74 match (from_ty.kind(&Interner), to_ty.kind(&Interner)) {
75 // `*mut T` -> `*const T` 75 // `*mut T` -> `*const T`
76 (TyKind::Raw(_, inner), TyKind::Raw(m2 @ Mutability::Not, ..)) => {
77 from_ty = TyKind::Raw(*m2, inner.clone()).intern(&Interner);
78 }
76 // `&mut T` -> `&T` 79 // `&mut T` -> `&T`
77 (TyKind::Raw(m1, ..), TyKind::Raw(m2 @ Mutability::Not, ..)) 80 (TyKind::Ref(_, lt, inner), TyKind::Ref(m2 @ Mutability::Not, ..)) => {
78 | (TyKind::Ref(m1, ..), TyKind::Ref(m2 @ Mutability::Not, ..)) => { 81 from_ty = TyKind::Ref(*m2, lt.clone(), inner.clone()).intern(&Interner);
79 *m1 = *m2;
80 } 82 }
81 // `&T` -> `*const T` 83 // `&T` -> `*const T`
82 // `&mut T` -> `*mut T`/`*const T` 84 // `&mut T` -> `*mut T`/`*const T`
diff --git a/crates/hir_ty/src/infer/expr.rs b/crates/hir_ty/src/infer/expr.rs
index 9841988c5..cbbfa8b5c 100644
--- a/crates/hir_ty/src/infer/expr.rs
+++ b/crates/hir_ty/src/infer/expr.rs
@@ -3,7 +3,7 @@
3use std::iter::{repeat, repeat_with}; 3use std::iter::{repeat, repeat_with};
4use std::{mem, sync::Arc}; 4use std::{mem, sync::Arc};
5 5
6use chalk_ir::{cast::Cast, Mutability, TyVariableKind}; 6use chalk_ir::{cast::Cast, fold::Shift, Mutability, TyVariableKind};
7use hir_def::{ 7use hir_def::{
8 expr::{Array, BinaryOp, Expr, ExprId, Literal, Statement, UnaryOp}, 8 expr::{Array, BinaryOp, Expr, ExprId, Literal, Statement, UnaryOp},
9 path::{GenericArg, GenericArgs}, 9 path::{GenericArg, GenericArgs},
@@ -24,7 +24,6 @@ use crate::{
24 utils::{generics, Generics}, 24 utils::{generics, Generics},
25 AdtId, Binders, CallableDefId, FnPointer, FnSig, FnSubst, InEnvironment, Interner, 25 AdtId, Binders, CallableDefId, FnPointer, FnSig, FnSubst, InEnvironment, Interner,
26 ProjectionTyExt, Rawness, Scalar, Substitution, TraitRef, Ty, TyBuilder, TyExt, TyKind, 26 ProjectionTyExt, Rawness, Scalar, Substitution, TraitRef, Ty, TyBuilder, TyExt, TyKind,
27 TypeWalk,
28}; 27};
29 28
30use super::{ 29use super::{
diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs
index 2ea9dd920..a887e20b0 100644
--- a/crates/hir_ty/src/infer/unify.rs
+++ b/crates/hir_ty/src/infer/unify.rs
@@ -2,14 +2,17 @@
2 2
3use std::borrow::Cow; 3use std::borrow::Cow;
4 4
5use chalk_ir::{FloatTy, IntTy, TyVariableKind, UniverseIndex, VariableKind}; 5use chalk_ir::{
6 cast::Cast, fold::Fold, interner::HasInterner, FloatTy, IntTy, TyVariableKind, UniverseIndex,
7 VariableKind,
8};
6use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue}; 9use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue};
7 10
8use super::{DomainGoal, InferenceContext}; 11use super::{DomainGoal, InferenceContext};
9use crate::{ 12use crate::{
10 AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, DebruijnIndex, FnPointer, FnSubst, 13 fold_tys, static_lifetime, AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds,
11 InEnvironment, InferenceVar, Interner, Scalar, Substitution, Ty, TyExt, TyKind, TypeWalk, 14 DebruijnIndex, FnPointer, FnSubst, InEnvironment, InferenceVar, Interner, Scalar, Substitution,
12 WhereClause, 15 Ty, TyExt, TyKind, WhereClause,
13}; 16};
14 17
15impl<'a> InferenceContext<'a> { 18impl<'a> InferenceContext<'a> {
@@ -34,7 +37,10 @@ where
34} 37}
35 38
36#[derive(Debug)] 39#[derive(Debug)]
37pub(super) struct Canonicalized<T> { 40pub(super) struct Canonicalized<T>
41where
42 T: HasInterner<Interner = Interner>,
43{
38 pub(super) value: Canonical<T>, 44 pub(super) value: Canonical<T>,
39 free_vars: Vec<(InferenceVar, TyVariableKind)>, 45 free_vars: Vec<(InferenceVar, TyVariableKind)>,
40} 46}
@@ -48,9 +54,14 @@ impl<'a, 'b> Canonicalizer<'a, 'b> {
48 }) 54 })
49 } 55 }
50 56
51 fn do_canonicalize<T: TypeWalk>(&mut self, t: T, binders: DebruijnIndex) -> T { 57 fn do_canonicalize<T: Fold<Interner, Result = T> + HasInterner<Interner = Interner>>(
52 t.fold_binders( 58 &mut self,
53 &mut |ty, binders| match ty.kind(&Interner) { 59 t: T,
60 binders: DebruijnIndex,
61 ) -> T {
62 fold_tys(
63 t,
64 |ty, binders| match ty.kind(&Interner) {
54 &TyKind::InferenceVar(var, kind) => { 65 &TyKind::InferenceVar(var, kind) => {
55 let inner = from_inference_var(var); 66 let inner = from_inference_var(var);
56 if self.var_stack.contains(&inner) { 67 if self.var_stack.contains(&inner) {
@@ -76,7 +87,10 @@ impl<'a, 'b> Canonicalizer<'a, 'b> {
76 ) 87 )
77 } 88 }
78 89
79 fn into_canonicalized<T>(self, result: T) -> Canonicalized<T> { 90 fn into_canonicalized<T: HasInterner<Interner = Interner>>(
91 self,
92 result: T,
93 ) -> Canonicalized<T> {
80 let kinds = self 94 let kinds = self
81 .free_vars 95 .free_vars
82 .iter() 96 .iter()
@@ -103,28 +117,18 @@ impl<'a, 'b> Canonicalizer<'a, 'b> {
103 DomainGoal::Holds(wc) => { 117 DomainGoal::Holds(wc) => {
104 DomainGoal::Holds(self.do_canonicalize(wc, DebruijnIndex::INNERMOST)) 118 DomainGoal::Holds(self.do_canonicalize(wc, DebruijnIndex::INNERMOST))
105 } 119 }
120 _ => unimplemented!(),
106 }; 121 };
107 self.into_canonicalized(InEnvironment { goal: result, environment: obligation.environment }) 122 self.into_canonicalized(InEnvironment { goal: result, environment: obligation.environment })
108 } 123 }
109} 124}
110 125
111impl<T> Canonicalized<T> { 126impl<T: HasInterner<Interner = Interner>> Canonicalized<T> {
112 pub(super) fn decanonicalize_ty(&self, ty: Ty) -> Ty { 127 pub(super) fn decanonicalize_ty(&self, ty: Ty) -> Ty {
113 ty.fold_binders( 128 crate::fold_free_vars(ty, |bound, _binders| {
114 &mut |ty, binders| { 129 let (v, k) = self.free_vars[bound.index];
115 if let TyKind::BoundVar(bound) = ty.kind(&Interner) { 130 TyKind::InferenceVar(v, k).intern(&Interner)
116 if bound.debruijn >= binders { 131 })
117 let (v, k) = self.free_vars[bound.index];
118 TyKind::InferenceVar(v, k).intern(&Interner)
119 } else {
120 ty
121 }
122 } else {
123 ty
124 }
125 },
126 DebruijnIndex::INNERMOST,
127 )
128 } 132 }
129 133
130 pub(super) fn apply_solution( 134 pub(super) fn apply_solution(
@@ -136,15 +140,17 @@ impl<T> Canonicalized<T> {
136 let new_vars = Substitution::from_iter( 140 let new_vars = Substitution::from_iter(
137 &Interner, 141 &Interner,
138 solution.binders.iter(&Interner).map(|k| match k.kind { 142 solution.binders.iter(&Interner).map(|k| match k.kind {
139 VariableKind::Ty(TyVariableKind::General) => ctx.table.new_type_var(), 143 VariableKind::Ty(TyVariableKind::General) => {
140 VariableKind::Ty(TyVariableKind::Integer) => ctx.table.new_integer_var(), 144 ctx.table.new_type_var().cast(&Interner)
141 VariableKind::Ty(TyVariableKind::Float) => ctx.table.new_float_var(), 145 }
142 // HACK: Chalk can sometimes return new lifetime variables. We 146 VariableKind::Ty(TyVariableKind::Integer) => {
143 // want to just skip them, but to not mess up the indices of 147 ctx.table.new_integer_var().cast(&Interner)
144 // other variables, we'll just create a new type variable in 148 }
145 // their place instead. This should not matter (we never see the 149 VariableKind::Ty(TyVariableKind::Float) => {
146 // actual *uses* of the lifetime variable). 150 ctx.table.new_float_var().cast(&Interner)
147 VariableKind::Lifetime => ctx.table.new_type_var(), 151 }
152 // Chalk can sometimes return new lifetime variables. We just use the static lifetime everywhere
153 VariableKind::Lifetime => static_lifetime().cast(&Interner),
148 _ => panic!("const variable in solution"), 154 _ => panic!("const variable in solution"),
149 }), 155 }),
150 ); 156 );
@@ -488,55 +494,63 @@ impl InferenceTable {
488 /// be resolved as far as possible, i.e. contain no type variables with 494 /// be resolved as far as possible, i.e. contain no type variables with
489 /// known type. 495 /// known type.
490 fn resolve_ty_as_possible_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { 496 fn resolve_ty_as_possible_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
491 ty.fold(&mut |ty| match ty.kind(&Interner) { 497 fold_tys(
492 &TyKind::InferenceVar(tv, kind) => { 498 ty,
493 let inner = from_inference_var(tv); 499 |ty, _| match ty.kind(&Interner) {
494 if tv_stack.contains(&inner) { 500 &TyKind::InferenceVar(tv, kind) => {
495 cov_mark::hit!(type_var_cycles_resolve_as_possible); 501 let inner = from_inference_var(tv);
496 // recursive type 502 if tv_stack.contains(&inner) {
497 return self.type_variable_table.fallback_value(tv, kind); 503 cov_mark::hit!(type_var_cycles_resolve_as_possible);
498 } 504 // recursive type
499 if let Some(known_ty) = 505 return self.type_variable_table.fallback_value(tv, kind);
500 self.var_unification_table.inlined_probe_value(inner).known() 506 }
501 { 507 if let Some(known_ty) =
502 // known_ty may contain other variables that are known by now 508 self.var_unification_table.inlined_probe_value(inner).known()
503 tv_stack.push(inner); 509 {
504 let result = self.resolve_ty_as_possible_inner(tv_stack, known_ty.clone()); 510 // known_ty may contain other variables that are known by now
505 tv_stack.pop(); 511 tv_stack.push(inner);
506 result 512 let result = self.resolve_ty_as_possible_inner(tv_stack, known_ty.clone());
507 } else { 513 tv_stack.pop();
508 ty 514 result
515 } else {
516 ty
517 }
509 } 518 }
510 } 519 _ => ty,
511 _ => ty, 520 },
512 }) 521 DebruijnIndex::INNERMOST,
522 )
513 } 523 }
514 524
515 /// Resolves the type completely; type variables without known type are 525 /// Resolves the type completely; type variables without known type are
516 /// replaced by TyKind::Unknown. 526 /// replaced by TyKind::Unknown.
517 fn resolve_ty_completely_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { 527 fn resolve_ty_completely_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
518 ty.fold(&mut |ty| match ty.kind(&Interner) { 528 fold_tys(
519 &TyKind::InferenceVar(tv, kind) => { 529 ty,
520 let inner = from_inference_var(tv); 530 |ty, _| match ty.kind(&Interner) {
521 if tv_stack.contains(&inner) { 531 &TyKind::InferenceVar(tv, kind) => {
522 cov_mark::hit!(type_var_cycles_resolve_completely); 532 let inner = from_inference_var(tv);
523 // recursive type 533 if tv_stack.contains(&inner) {
524 return self.type_variable_table.fallback_value(tv, kind); 534 cov_mark::hit!(type_var_cycles_resolve_completely);
525 } 535 // recursive type
526 if let Some(known_ty) = 536 return self.type_variable_table.fallback_value(tv, kind);
527 self.var_unification_table.inlined_probe_value(inner).known() 537 }
528 { 538 if let Some(known_ty) =
529 // known_ty may contain other variables that are known by now 539 self.var_unification_table.inlined_probe_value(inner).known()
530 tv_stack.push(inner); 540 {
531 let result = self.resolve_ty_completely_inner(tv_stack, known_ty.clone()); 541 // known_ty may contain other variables that are known by now
532 tv_stack.pop(); 542 tv_stack.push(inner);
533 result 543 let result = self.resolve_ty_completely_inner(tv_stack, known_ty.clone());
534 } else { 544 tv_stack.pop();
535 self.type_variable_table.fallback_value(tv, kind) 545 result
546 } else {
547 self.type_variable_table.fallback_value(tv, kind)
548 }
536 } 549 }
537 } 550 _ => ty,
538 _ => ty, 551 },
539 }) 552 DebruijnIndex::INNERMOST,
553 )
540 } 554 }
541} 555}
542 556
diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs
index 87f10e9d5..874c95411 100644
--- a/crates/hir_ty/src/lib.rs
+++ b/crates/hir_ty/src/lib.rs
@@ -1,5 +1,6 @@
1//! The type system. We currently use this to infer types for completion, hover 1//! The type system. We currently use this to infer types for completion, hover
2//! information and various assists. 2//! information and various assists.
3
3#[allow(unused)] 4#[allow(unused)]
4macro_rules! eprintln { 5macro_rules! eprintln {
5 ($($tt:tt)*) => { stdx::eprintln!($($tt)*) }; 6 ($($tt:tt)*) => { stdx::eprintln!($($tt)*) };
@@ -17,7 +18,6 @@ mod chalk_cast;
17mod chalk_ext; 18mod chalk_ext;
18mod builder; 19mod builder;
19mod walk; 20mod walk;
20mod types;
21 21
22pub mod display; 22pub mod display;
23pub mod db; 23pub mod db;
@@ -31,7 +31,11 @@ mod test_db;
31use std::sync::Arc; 31use std::sync::Arc;
32 32
33use base_db::salsa; 33use base_db::salsa;
34use chalk_ir::UintTy; 34use chalk_ir::{
35 fold::{Fold, Shift},
36 interner::HasInterner,
37 UintTy,
38};
35use hir_def::{ 39use hir_def::{
36 expr::ExprId, type_ref::Rawness, ConstParamId, LifetimeParamId, TraitId, TypeAliasId, 40 expr::ExprId, type_ref::Rawness, ConstParamId, LifetimeParamId, TraitId, TypeAliasId,
37 TypeParamId, 41 TypeParamId,
@@ -48,7 +52,6 @@ pub use lower::{
48 TyDefId, TyLoweringContext, ValueTyDefId, 52 TyDefId, TyLoweringContext, ValueTyDefId,
49}; 53};
50pub use traits::{chalk::Interner, TraitEnvironment}; 54pub use traits::{chalk::Interner, TraitEnvironment};
51pub use types::*;
52pub use walk::TypeWalk; 55pub use walk::TypeWalk;
53 56
54pub use chalk_ir::{ 57pub use chalk_ir::{
@@ -65,6 +68,21 @@ pub type PlaceholderIndex = chalk_ir::PlaceholderIndex;
65pub type VariableKind = chalk_ir::VariableKind<Interner>; 68pub type VariableKind = chalk_ir::VariableKind<Interner>;
66pub type VariableKinds = chalk_ir::VariableKinds<Interner>; 69pub type VariableKinds = chalk_ir::VariableKinds<Interner>;
67pub type CanonicalVarKinds = chalk_ir::CanonicalVarKinds<Interner>; 70pub type CanonicalVarKinds = chalk_ir::CanonicalVarKinds<Interner>;
71pub type Binders<T> = chalk_ir::Binders<T>;
72pub type Substitution = chalk_ir::Substitution<Interner>;
73pub type GenericArg = chalk_ir::GenericArg<Interner>;
74pub type GenericArgData = chalk_ir::GenericArgData<Interner>;
75
76pub type Ty = chalk_ir::Ty<Interner>;
77pub type TyKind = chalk_ir::TyKind<Interner>;
78pub type DynTy = chalk_ir::DynTy<Interner>;
79pub type FnPointer = chalk_ir::FnPointer<Interner>;
80// pub type FnSubst = chalk_ir::FnSubst<Interner>;
81pub use chalk_ir::FnSubst;
82pub type ProjectionTy = chalk_ir::ProjectionTy<Interner>;
83pub type AliasTy = chalk_ir::AliasTy<Interner>;
84pub type OpaqueTy = chalk_ir::OpaqueTy<Interner>;
85pub type InferenceVar = chalk_ir::InferenceVar;
68 86
69pub type Lifetime = chalk_ir::Lifetime<Interner>; 87pub type Lifetime = chalk_ir::Lifetime<Interner>;
70pub type LifetimeData = chalk_ir::LifetimeData<Interner>; 88pub type LifetimeData = chalk_ir::LifetimeData<Interner>;
@@ -79,9 +97,20 @@ pub type ChalkTraitId = chalk_ir::TraitId<Interner>;
79 97
80pub type FnSig = chalk_ir::FnSig<Interner>; 98pub type FnSig = chalk_ir::FnSig<Interner>;
81 99
100pub type InEnvironment<T> = chalk_ir::InEnvironment<T>;
101pub type DomainGoal = chalk_ir::DomainGoal<Interner>;
102pub type AliasEq = chalk_ir::AliasEq<Interner>;
103pub type Solution = chalk_solve::Solution<Interner>;
104pub type ConstrainedSubst = chalk_ir::ConstrainedSubst<Interner>;
105pub type Guidance = chalk_solve::Guidance<Interner>;
106pub type WhereClause = chalk_ir::WhereClause<Interner>;
107
82// FIXME: get rid of this 108// FIXME: get rid of this
83pub fn subst_prefix(s: &Substitution, n: usize) -> Substitution { 109pub fn subst_prefix(s: &Substitution, n: usize) -> Substitution {
84 Substitution::intern(s.interned()[..std::cmp::min(s.len(&Interner), n)].into()) 110 Substitution::from_iter(
111 &Interner,
112 s.interned()[..std::cmp::min(s.len(&Interner), n)].iter().cloned(),
113 )
85} 114}
86 115
87/// Return an index of a parameter in the generic type parameter list by it's id. 116/// Return an index of a parameter in the generic type parameter list by it's id.
@@ -91,12 +120,15 @@ pub fn param_idx(db: &dyn HirDatabase, id: TypeParamId) -> Option<usize> {
91 120
92pub fn wrap_empty_binders<T>(value: T) -> Binders<T> 121pub fn wrap_empty_binders<T>(value: T) -> Binders<T>
93where 122where
94 T: TypeWalk, 123 T: Fold<Interner, Result = T> + HasInterner<Interner = Interner>,
95{ 124{
96 Binders::empty(&Interner, value.shifted_in_from(DebruijnIndex::ONE)) 125 Binders::empty(&Interner, value.shifted_in_from(&Interner, DebruijnIndex::ONE))
97} 126}
98 127
99pub fn make_only_type_binders<T>(num_vars: usize, value: T) -> Binders<T> { 128pub fn make_only_type_binders<T: HasInterner<Interner = Interner>>(
129 num_vars: usize,
130 value: T,
131) -> Binders<T> {
100 Binders::new( 132 Binders::new(
101 VariableKinds::from_iter( 133 VariableKinds::from_iter(
102 &Interner, 134 &Interner,
@@ -108,7 +140,7 @@ pub fn make_only_type_binders<T>(num_vars: usize, value: T) -> Binders<T> {
108} 140}
109 141
110// FIXME: get rid of this 142// FIXME: get rid of this
111pub fn make_canonical<T>( 143pub fn make_canonical<T: HasInterner<Interner = Interner>>(
112 value: T, 144 value: T,
113 kinds: impl IntoIterator<Item = TyVariableKind>, 145 kinds: impl IntoIterator<Item = TyVariableKind>,
114) -> Canonical<T> { 146) -> Canonical<T> {
@@ -121,6 +153,14 @@ pub fn make_canonical<T>(
121 Canonical { value, binders: chalk_ir::CanonicalVarKinds::from_iter(&Interner, kinds) } 153 Canonical { value, binders: chalk_ir::CanonicalVarKinds::from_iter(&Interner, kinds) }
122} 154}
123 155
156pub type TraitRef = chalk_ir::TraitRef<Interner>;
157
158pub type QuantifiedWhereClause = Binders<WhereClause>;
159
160pub type QuantifiedWhereClauses = chalk_ir::QuantifiedWhereClauses<Interner>;
161
162pub type Canonical<T> = chalk_ir::Canonical<T>;
163
124/// A function signature as seen by type inference: Several parameter types and 164/// A function signature as seen by type inference: Several parameter types and
125/// one return type. 165/// one return type.
126#[derive(Clone, PartialEq, Eq, Debug)] 166#[derive(Clone, PartialEq, Eq, Debug)]
@@ -144,7 +184,7 @@ impl CallableSig {
144 params_and_return: fn_ptr 184 params_and_return: fn_ptr
145 .substitution 185 .substitution
146 .clone() 186 .clone()
147 .shifted_out_to(DebruijnIndex::ONE) 187 .shifted_out_to(&Interner, DebruijnIndex::ONE)
148 .expect("unexpected lifetime vars in fn ptr") 188 .expect("unexpected lifetime vars in fn ptr")
149 .0 189 .0
150 .interned() 190 .interned()
@@ -164,7 +204,22 @@ impl CallableSig {
164 } 204 }
165} 205}
166 206
167impl Ty {} 207impl Fold<Interner> for CallableSig {
208 type Result = CallableSig;
209
210 fn fold_with<'i>(
211 self,
212 folder: &mut dyn chalk_ir::fold::Folder<'i, Interner>,
213 outer_binder: DebruijnIndex,
214 ) -> chalk_ir::Fallible<Self::Result>
215 where
216 Interner: 'i,
217 {
218 let vec = self.params_and_return.to_vec();
219 let folded = vec.fold_with(folder, outer_binder)?;
220 Ok(CallableSig { params_and_return: folded.into(), is_varargs: self.is_varargs })
221 }
222}
168 223
169#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)] 224#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
170pub enum ImplTraitId { 225pub enum ImplTraitId {
@@ -244,3 +299,56 @@ pub fn dummy_usize_const() -> Const {
244 } 299 }
245 .intern(&Interner) 300 .intern(&Interner)
246} 301}
302
303pub(crate) fn fold_free_vars<T: HasInterner<Interner = Interner> + Fold<Interner>>(
304 t: T,
305 f: impl FnMut(BoundVar, DebruijnIndex) -> Ty,
306) -> T::Result {
307 use chalk_ir::{fold::Folder, Fallible};
308 struct FreeVarFolder<F>(F);
309 impl<'i, F: FnMut(BoundVar, DebruijnIndex) -> Ty + 'i> Folder<'i, Interner> for FreeVarFolder<F> {
310 fn as_dyn(&mut self) -> &mut dyn Folder<'i, Interner> {
311 self
312 }
313
314 fn interner(&self) -> &'i Interner {
315 &Interner
316 }
317
318 fn fold_free_var_ty(
319 &mut self,
320 bound_var: BoundVar,
321 outer_binder: DebruijnIndex,
322 ) -> Fallible<Ty> {
323 Ok(self.0(bound_var, outer_binder))
324 }
325 }
326 t.fold_with(&mut FreeVarFolder(f), DebruijnIndex::INNERMOST).expect("fold failed unexpectedly")
327}
328
329pub(crate) fn fold_tys<T: HasInterner<Interner = Interner> + Fold<Interner>>(
330 t: T,
331 f: impl FnMut(Ty, DebruijnIndex) -> Ty,
332 binders: DebruijnIndex,
333) -> T::Result {
334 use chalk_ir::{
335 fold::{Folder, SuperFold},
336 Fallible,
337 };
338 struct TyFolder<F>(F);
339 impl<'i, F: FnMut(Ty, DebruijnIndex) -> Ty + 'i> Folder<'i, Interner> for TyFolder<F> {
340 fn as_dyn(&mut self) -> &mut dyn Folder<'i, Interner> {
341 self
342 }
343
344 fn interner(&self) -> &'i Interner {
345 &Interner
346 }
347
348 fn fold_ty(&mut self, ty: Ty, outer_binder: DebruijnIndex) -> Fallible<Ty> {
349 let ty = ty.super_fold_with(self.as_dyn(), outer_binder)?;
350 Ok(self.0(ty, outer_binder))
351 }
352 }
353 t.fold_with(&mut TyFolder(f), binders).expect("fold failed unexpectedly")
354}
diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs
index e6903e189..8a22d9ea3 100644
--- a/crates/hir_ty/src/lower.rs
+++ b/crates/hir_ty/src/lower.rs
@@ -8,7 +8,7 @@
8use std::{iter, sync::Arc}; 8use std::{iter, sync::Arc};
9 9
10use base_db::CrateId; 10use base_db::CrateId;
11use chalk_ir::{cast::Cast, Mutability, Safety}; 11use chalk_ir::{cast::Cast, fold::Shift, interner::HasInterner, Mutability, Safety};
12use hir_def::{ 12use hir_def::{
13 adt::StructKind, 13 adt::StructKind,
14 builtin_type::BuiltinType, 14 builtin_type::BuiltinType,
@@ -35,7 +35,7 @@ use crate::{
35 AliasEq, AliasTy, Binders, BoundVar, CallableSig, DebruijnIndex, DynTy, FnPointer, FnSig, 35 AliasEq, AliasTy, Binders, BoundVar, CallableSig, DebruijnIndex, DynTy, FnPointer, FnSig,
36 FnSubst, ImplTraitId, OpaqueTy, PolyFnSig, ProjectionTy, QuantifiedWhereClause, 36 FnSubst, ImplTraitId, OpaqueTy, PolyFnSig, ProjectionTy, QuantifiedWhereClause,
37 QuantifiedWhereClauses, ReturnTypeImplTrait, ReturnTypeImplTraits, Substitution, 37 QuantifiedWhereClauses, ReturnTypeImplTrait, ReturnTypeImplTraits, Substitution,
38 TraitEnvironment, TraitRef, TraitRefExt, Ty, TyBuilder, TyKind, TypeWalk, WhereClause, 38 TraitEnvironment, TraitRef, TraitRefExt, Ty, TyBuilder, TyKind, WhereClause,
39}; 39};
40 40
41#[derive(Debug)] 41#[derive(Debug)]
@@ -488,7 +488,7 @@ impl<'a> TyLoweringContext<'a> {
488 }; 488 };
489 // We need to shift in the bound vars, since 489 // We need to shift in the bound vars, since
490 // associated_type_shorthand_candidates does not do that 490 // associated_type_shorthand_candidates does not do that
491 let substs = substs.shifted_in_from(self.in_binders); 491 let substs = substs.shifted_in_from(&Interner, self.in_binders);
492 // FIXME handle type parameters on the segment 492 // FIXME handle type parameters on the segment
493 return Some( 493 return Some(
494 TyKind::Alias(AliasTy::Projection(ProjectionTy { 494 TyKind::Alias(AliasTy::Projection(ProjectionTy {
@@ -847,7 +847,7 @@ pub fn associated_type_shorthand_candidates<R>(
847 // FIXME: how to correctly handle higher-ranked bounds here? 847 // FIXME: how to correctly handle higher-ranked bounds here?
848 WhereClause::Implemented(tr) => search( 848 WhereClause::Implemented(tr) => search(
849 tr.clone() 849 tr.clone()
850 .shifted_out_to(DebruijnIndex::ONE) 850 .shifted_out_to(&Interner, DebruijnIndex::ONE)
851 .expect("FIXME unexpected higher-ranked trait bound"), 851 .expect("FIXME unexpected higher-ranked trait bound"),
852 ), 852 ),
853 _ => None, 853 _ => None,
@@ -950,8 +950,7 @@ pub(crate) fn trait_environment_query(
950 traits_in_scope 950 traits_in_scope
951 .push((tr.self_type_parameter(&Interner).clone(), tr.hir_trait_id())); 951 .push((tr.self_type_parameter(&Interner).clone(), tr.hir_trait_id()));
952 } 952 }
953 let program_clause: chalk_ir::ProgramClause<Interner> = 953 let program_clause: chalk_ir::ProgramClause<Interner> = pred.clone().cast(&Interner);
954 pred.clone().to_chalk(db).cast(&Interner);
955 clauses.push(program_clause.into_from_env_clause(&Interner)); 954 clauses.push(program_clause.into_from_env_clause(&Interner));
956 } 955 }
957 } 956 }
@@ -974,7 +973,7 @@ pub(crate) fn trait_environment_query(
974 let substs = TyBuilder::type_params_subst(db, trait_id); 973 let substs = TyBuilder::type_params_subst(db, trait_id);
975 let trait_ref = TraitRef { trait_id: to_chalk_trait_id(trait_id), substitution: substs }; 974 let trait_ref = TraitRef { trait_id: to_chalk_trait_id(trait_id), substitution: substs };
976 let pred = WhereClause::Implemented(trait_ref); 975 let pred = WhereClause::Implemented(trait_ref);
977 let program_clause: chalk_ir::ProgramClause<Interner> = pred.to_chalk(db).cast(&Interner); 976 let program_clause: chalk_ir::ProgramClause<Interner> = pred.cast(&Interner);
978 clauses.push(program_clause.into_from_env_clause(&Interner)); 977 clauses.push(program_clause.into_from_env_clause(&Interner));
979 } 978 }
980 979
@@ -1016,22 +1015,16 @@ pub(crate) fn generic_defaults_query(
1016 p.default.as_ref().map_or(TyKind::Error.intern(&Interner), |t| ctx.lower_ty(t)); 1015 p.default.as_ref().map_or(TyKind::Error.intern(&Interner), |t| ctx.lower_ty(t));
1017 1016
1018 // Each default can only refer to previous parameters. 1017 // Each default can only refer to previous parameters.
1019 ty = ty.fold_binders( 1018 ty = crate::fold_free_vars(ty, |bound, binders| {
1020 &mut |ty, binders| match ty.kind(&Interner) { 1019 if bound.index >= idx && bound.debruijn == DebruijnIndex::INNERMOST {
1021 TyKind::BoundVar(BoundVar { debruijn, index }) if *debruijn == binders => { 1020 // type variable default referring to parameter coming
1022 if *index >= idx { 1021 // after it. This is forbidden (FIXME: report
1023 // type variable default referring to parameter coming 1022 // diagnostic)
1024 // after it. This is forbidden (FIXME: report 1023 TyKind::Error.intern(&Interner)
1025 // diagnostic) 1024 } else {
1026 TyKind::Error.intern(&Interner) 1025 bound.shifted_in_from(binders).to_ty(&Interner)
1027 } else { 1026 }
1028 ty 1027 });
1029 }
1030 }
1031 _ => ty,
1032 },
1033 DebruijnIndex::INNERMOST,
1034 );
1035 1028
1036 crate::make_only_type_binders(idx, ty) 1029 crate::make_only_type_binders(idx, ty)
1037 }) 1030 })
@@ -1307,6 +1300,6 @@ pub(crate) fn lower_to_chalk_mutability(m: hir_def::type_ref::Mutability) -> Mut
1307 } 1300 }
1308} 1301}
1309 1302
1310fn make_binders<T>(generics: &Generics, value: T) -> Binders<T> { 1303fn make_binders<T: HasInterner<Interner = Interner>>(generics: &Generics, value: T) -> Binders<T> {
1311 crate::make_only_type_binders(generics.len(), value) 1304 crate::make_only_type_binders(generics.len(), value)
1312} 1305}
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs
index 7e09a1539..be3e4f09a 100644
--- a/crates/hir_ty/src/method_resolution.rs
+++ b/crates/hir_ty/src/method_resolution.rs
@@ -23,7 +23,7 @@ use crate::{
23 utils::all_super_traits, 23 utils::all_super_traits,
24 AdtId, Canonical, CanonicalVarKinds, DebruijnIndex, FnPointer, FnSig, ForeignDefId, 24 AdtId, Canonical, CanonicalVarKinds, DebruijnIndex, FnPointer, FnSig, ForeignDefId,
25 InEnvironment, Interner, Scalar, Substitution, TraitEnvironment, TraitRefExt, Ty, TyBuilder, 25 InEnvironment, Interner, Scalar, Substitution, TraitEnvironment, TraitRefExt, Ty, TyBuilder,
26 TyExt, TyKind, TypeWalk, 26 TyExt, TyKind,
27}; 27};
28 28
29/// This is used as a key for indexing impls. 29/// This is used as a key for indexing impls.
@@ -757,20 +757,13 @@ pub(crate) fn inherent_impl_substs(
757/// This replaces any 'free' Bound vars in `s` (i.e. those with indices past 757/// This replaces any 'free' Bound vars in `s` (i.e. those with indices past
758/// num_vars_to_keep) by `TyKind::Unknown`. 758/// num_vars_to_keep) by `TyKind::Unknown`.
759fn fallback_bound_vars(s: Substitution, num_vars_to_keep: usize) -> Substitution { 759fn fallback_bound_vars(s: Substitution, num_vars_to_keep: usize) -> Substitution {
760 s.fold_binders( 760 crate::fold_free_vars(s, |bound, binders| {
761 &mut |ty, binders| { 761 if bound.index >= num_vars_to_keep && bound.debruijn == DebruijnIndex::INNERMOST {
762 if let TyKind::BoundVar(bound) = ty.kind(&Interner) { 762 TyKind::Error.intern(&Interner)
763 if bound.index >= num_vars_to_keep && bound.debruijn >= binders { 763 } else {
764 TyKind::Error.intern(&Interner) 764 bound.shifted_in_from(binders).to_ty(&Interner)
765 } else { 765 }
766 ty 766 })
767 }
768 } else {
769 ty
770 }
771 },
772 DebruijnIndex::INNERMOST,
773 )
774} 767}
775 768
776fn transform_receiver_ty( 769fn transform_receiver_ty(
diff --git a/crates/hir_ty/src/traits.rs b/crates/hir_ty/src/traits.rs
index 7d87741b8..1cda72d22 100644
--- a/crates/hir_ty/src/traits.rs
+++ b/crates/hir_ty/src/traits.rs
@@ -12,7 +12,7 @@ use crate::{
12 Solution, TraitRefExt, Ty, TyKind, WhereClause, 12 Solution, TraitRefExt, Ty, TyKind, WhereClause,
13}; 13};
14 14
15use self::chalk::{from_chalk, Interner, ToChalk}; 15use self::chalk::Interner;
16 16
17pub(crate) mod chalk; 17pub(crate) mod chalk;
18 18
@@ -81,6 +81,7 @@ pub(crate) fn trait_solve_query(
81 db.trait_data(it.hir_trait_id()).name.to_string() 81 db.trait_data(it.hir_trait_id()).name.to_string()
82 } 82 }
83 DomainGoal::Holds(WhereClause::AliasEq(_)) => "alias_eq".to_string(), 83 DomainGoal::Holds(WhereClause::AliasEq(_)) => "alias_eq".to_string(),
84 _ => "??".to_string(),
84 }); 85 });
85 log::info!("trait_solve_query({})", goal.value.goal.display(db)); 86 log::info!("trait_solve_query({})", goal.value.goal.display(db));
86 87
@@ -95,13 +96,12 @@ pub(crate) fn trait_solve_query(
95 } 96 }
96 } 97 }
97 98
98 let canonical = goal.to_chalk(db).cast(&Interner); 99 let canonical = goal.cast(&Interner);
99 100
100 // We currently don't deal with universes (I think / hope they're not yet 101 // We currently don't deal with universes (I think / hope they're not yet
101 // relevant for our use cases?) 102 // relevant for our use cases?)
102 let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 }; 103 let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 };
103 let solution = solve(db, krate, &u_canonical); 104 solve(db, krate, &u_canonical)
104 solution.map(|solution| solution_from_chalk(db, solution))
105} 105}
106 106
107fn solve( 107fn solve(
@@ -169,26 +169,6 @@ fn is_chalk_print() -> bool {
169 std::env::var("CHALK_PRINT").is_ok() 169 std::env::var("CHALK_PRINT").is_ok()
170} 170}
171 171
172fn solution_from_chalk(
173 db: &dyn HirDatabase,
174 solution: chalk_solve::Solution<Interner>,
175) -> Solution {
176 match solution {
177 chalk_solve::Solution::Unique(constr_subst) => {
178 Solution::Unique(from_chalk(db, constr_subst))
179 }
180 chalk_solve::Solution::Ambig(chalk_solve::Guidance::Definite(subst)) => {
181 Solution::Ambig(Guidance::Definite(from_chalk(db, subst)))
182 }
183 chalk_solve::Solution::Ambig(chalk_solve::Guidance::Suggested(subst)) => {
184 Solution::Ambig(Guidance::Suggested(from_chalk(db, subst)))
185 }
186 chalk_solve::Solution::Ambig(chalk_solve::Guidance::Unknown) => {
187 Solution::Ambig(Guidance::Unknown)
188 }
189 }
190}
191
192#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] 172#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
193pub enum FnTrait { 173pub enum FnTrait {
194 FnOnce, 174 FnOnce,
diff --git a/crates/hir_ty/src/traits/chalk.rs b/crates/hir_ty/src/traits/chalk.rs
index 090f6492b..b8c390b2e 100644
--- a/crates/hir_ty/src/traits/chalk.rs
+++ b/crates/hir_ty/src/traits/chalk.rs
@@ -17,16 +17,14 @@ use super::ChalkContext;
17use crate::{ 17use crate::{
18 db::HirDatabase, 18 db::HirDatabase,
19 display::HirDisplay, 19 display::HirDisplay,
20 from_assoc_type_id, 20 from_assoc_type_id, make_only_type_binders,
21 method_resolution::{TyFingerprint, ALL_FLOAT_FPS, ALL_INT_FPS}, 21 method_resolution::{TyFingerprint, ALL_FLOAT_FPS, ALL_INT_FPS},
22 to_assoc_type_id, to_chalk_trait_id, 22 to_assoc_type_id, to_chalk_trait_id,
23 utils::generics, 23 utils::generics,
24 AliasEq, AliasTy, BoundVar, CallableDefId, DebruijnIndex, FnDefId, ProjectionTy, Substitution, 24 AliasEq, AliasTy, BoundVar, CallableDefId, DebruijnIndex, FnDefId, ProjectionTy, Substitution,
25 TraitRef, TraitRefExt, Ty, TyBuilder, TyExt, TyKind, WhereClause, 25 TraitRef, TraitRefExt, Ty, TyBuilder, TyExt, TyKind, WhereClause,
26}; 26};
27use mapping::{ 27use mapping::{convert_where_clauses, generic_predicate_to_inline_bound, TypeAliasAsValue};
28 convert_where_clauses, generic_predicate_to_inline_bound, make_binders, TypeAliasAsValue,
29};
30 28
31pub use self::interner::Interner; 29pub use self::interner::Interner;
32pub(crate) use self::interner::*; 30pub(crate) use self::interner::*;
@@ -86,7 +84,7 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
86 debug!("impls_for_trait {:?}", trait_id); 84 debug!("impls_for_trait {:?}", trait_id);
87 let trait_: hir_def::TraitId = from_chalk(self.db, trait_id); 85 let trait_: hir_def::TraitId = from_chalk(self.db, trait_id);
88 86
89 let ty: Ty = from_chalk(self.db, parameters[0].assert_ty_ref(&Interner).clone()); 87 let ty: Ty = parameters[0].assert_ty_ref(&Interner).clone();
90 88
91 fn binder_kind( 89 fn binder_kind(
92 ty: &Ty, 90 ty: &Ty,
@@ -187,16 +185,11 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
187 let (datas, binders) = (*datas).as_ref().into_value_and_skipped_binders(); 185 let (datas, binders) = (*datas).as_ref().into_value_and_skipped_binders();
188 let data = &datas.impl_traits[idx as usize]; 186 let data = &datas.impl_traits[idx as usize];
189 let bound = OpaqueTyDatumBound { 187 let bound = OpaqueTyDatumBound {
190 bounds: make_binders( 188 bounds: make_only_type_binders(
191 data.bounds
192 .skip_binders()
193 .iter()
194 .cloned()
195 .map(|b| b.to_chalk(self.db))
196 .collect(),
197 1, 189 1,
190 data.bounds.skip_binders().iter().cloned().collect(),
198 ), 191 ),
199 where_clauses: make_binders(vec![], 0), 192 where_clauses: make_only_type_binders(0, vec![]),
200 }; 193 };
201 chalk_ir::Binders::new(binders, bound) 194 chalk_ir::Binders::new(binders, bound)
202 } 195 }
@@ -244,25 +237,25 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
244 .intern(&Interner), 237 .intern(&Interner),
245 }); 238 });
246 let bound = OpaqueTyDatumBound { 239 let bound = OpaqueTyDatumBound {
247 bounds: make_binders( 240 bounds: make_only_type_binders(
241 1,
248 vec![ 242 vec![
249 crate::wrap_empty_binders(impl_bound).to_chalk(self.db), 243 crate::wrap_empty_binders(impl_bound),
250 crate::wrap_empty_binders(proj_bound).to_chalk(self.db), 244 crate::wrap_empty_binders(proj_bound),
251 ], 245 ],
252 1,
253 ), 246 ),
254 where_clauses: make_binders(vec![], 0), 247 where_clauses: make_only_type_binders(0, vec![]),
255 }; 248 };
256 // The opaque type has 1 parameter. 249 // The opaque type has 1 parameter.
257 make_binders(bound, 1) 250 make_only_type_binders(1, bound)
258 } else { 251 } else {
259 // If failed to find Symbol’s value as variable is void: Future::Output, return empty bounds as fallback. 252 // If failed to find Symbol’s value as variable is void: Future::Output, return empty bounds as fallback.
260 let bound = OpaqueTyDatumBound { 253 let bound = OpaqueTyDatumBound {
261 bounds: make_binders(vec![], 0), 254 bounds: make_only_type_binders(0, vec![]),
262 where_clauses: make_binders(vec![], 0), 255 where_clauses: make_only_type_binders(0, vec![]),
263 }; 256 };
264 // The opaque type has 1 parameter. 257 // The opaque type has 1 parameter.
265 make_binders(bound, 1) 258 make_only_type_binders(1, bound)
266 } 259 }
267 } 260 }
268 }; 261 };
@@ -272,7 +265,7 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
272 265
273 fn hidden_opaque_type(&self, _id: chalk_ir::OpaqueTyId<Interner>) -> chalk_ir::Ty<Interner> { 266 fn hidden_opaque_type(&self, _id: chalk_ir::OpaqueTyId<Interner>) -> chalk_ir::Ty<Interner> {
274 // FIXME: actually provide the hidden type; it is relevant for auto traits 267 // FIXME: actually provide the hidden type; it is relevant for auto traits
275 TyKind::Error.intern(&Interner).to_chalk(self.db) 268 TyKind::Error.intern(&Interner)
276 } 269 }
277 270
278 fn is_object_safe(&self, _trait_id: chalk_ir::TraitId<Interner>) -> bool { 271 fn is_object_safe(&self, _trait_id: chalk_ir::TraitId<Interner>) -> bool {
@@ -293,29 +286,28 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
293 _closure_id: chalk_ir::ClosureId<Interner>, 286 _closure_id: chalk_ir::ClosureId<Interner>,
294 substs: &chalk_ir::Substitution<Interner>, 287 substs: &chalk_ir::Substitution<Interner>,
295 ) -> chalk_ir::Binders<rust_ir::FnDefInputsAndOutputDatum<Interner>> { 288 ) -> chalk_ir::Binders<rust_ir::FnDefInputsAndOutputDatum<Interner>> {
296 let sig_ty: Ty = 289 let sig_ty = substs.at(&Interner, 0).assert_ty_ref(&Interner).clone();
297 from_chalk(self.db, substs.at(&Interner, 0).assert_ty_ref(&Interner).clone());
298 let sig = &sig_ty.callable_sig(self.db).expect("first closure param should be fn ptr"); 290 let sig = &sig_ty.callable_sig(self.db).expect("first closure param should be fn ptr");
299 let io = rust_ir::FnDefInputsAndOutputDatum { 291 let io = rust_ir::FnDefInputsAndOutputDatum {
300 argument_types: sig.params().iter().map(|ty| ty.clone().to_chalk(self.db)).collect(), 292 argument_types: sig.params().iter().cloned().collect(),
301 return_type: sig.ret().clone().to_chalk(self.db), 293 return_type: sig.ret().clone(),
302 }; 294 };
303 make_binders(io.shifted_in(&Interner), 0) 295 make_only_type_binders(0, io.shifted_in(&Interner))
304 } 296 }
305 fn closure_upvars( 297 fn closure_upvars(
306 &self, 298 &self,
307 _closure_id: chalk_ir::ClosureId<Interner>, 299 _closure_id: chalk_ir::ClosureId<Interner>,
308 _substs: &chalk_ir::Substitution<Interner>, 300 _substs: &chalk_ir::Substitution<Interner>,
309 ) -> chalk_ir::Binders<chalk_ir::Ty<Interner>> { 301 ) -> chalk_ir::Binders<chalk_ir::Ty<Interner>> {
310 let ty = TyBuilder::unit().to_chalk(self.db); 302 let ty = TyBuilder::unit();
311 make_binders(ty, 0) 303 make_only_type_binders(0, ty)
312 } 304 }
313 fn closure_fn_substitution( 305 fn closure_fn_substitution(
314 &self, 306 &self,
315 _closure_id: chalk_ir::ClosureId<Interner>, 307 _closure_id: chalk_ir::ClosureId<Interner>,
316 _substs: &chalk_ir::Substitution<Interner>, 308 _substs: &chalk_ir::Substitution<Interner>,
317 ) -> chalk_ir::Substitution<Interner> { 309 ) -> chalk_ir::Substitution<Interner> {
318 Substitution::empty(&Interner).to_chalk(self.db) 310 Substitution::empty(&Interner)
319 } 311 }
320 312
321 fn trait_name(&self, trait_id: chalk_ir::TraitId<Interner>) -> String { 313 fn trait_name(&self, trait_id: chalk_ir::TraitId<Interner>) -> String {
@@ -410,10 +402,10 @@ pub(crate) fn associated_ty_data_query(
410 let where_clauses = convert_where_clauses(db, type_alias.into(), &bound_vars); 402 let where_clauses = convert_where_clauses(db, type_alias.into(), &bound_vars);
411 let bound_data = rust_ir::AssociatedTyDatumBound { bounds, where_clauses }; 403 let bound_data = rust_ir::AssociatedTyDatumBound { bounds, where_clauses };
412 let datum = AssociatedTyDatum { 404 let datum = AssociatedTyDatum {
413 trait_id: trait_.to_chalk(db), 405 trait_id: to_chalk_trait_id(trait_),
414 id, 406 id,
415 name: type_alias, 407 name: type_alias,
416 binders: make_binders(bound_data, generic_params.len()), 408 binders: make_only_type_binders(generic_params.len(), bound_data),
417 }; 409 };
418 Arc::new(datum) 410 Arc::new(datum)
419} 411}
@@ -446,7 +438,7 @@ pub(crate) fn trait_datum_query(
446 lang_attr(db.upcast(), trait_).and_then(|name| well_known_trait_from_lang_attr(&name)); 438 lang_attr(db.upcast(), trait_).and_then(|name| well_known_trait_from_lang_attr(&name));
447 let trait_datum = TraitDatum { 439 let trait_datum = TraitDatum {
448 id: trait_id, 440 id: trait_id,
449 binders: make_binders(trait_datum_bound, bound_vars.len(&Interner)), 441 binders: make_only_type_binders(bound_vars.len(&Interner), trait_datum_bound),
450 flags, 442 flags,
451 associated_ty_ids, 443 associated_ty_ids,
452 well_known, 444 well_known,
@@ -515,7 +507,7 @@ pub(crate) fn struct_datum_query(
515 // FIXME set ADT kind 507 // FIXME set ADT kind
516 kind: rust_ir::AdtKind::Struct, 508 kind: rust_ir::AdtKind::Struct,
517 id: struct_id, 509 id: struct_id,
518 binders: make_binders(struct_datum_bound, num_params), 510 binders: make_only_type_binders(num_params, struct_datum_bound),
519 flags, 511 flags,
520 }; 512 };
521 Arc::new(struct_datum) 513 Arc::new(struct_datum)
@@ -563,7 +555,6 @@ fn impl_def_datum(
563 trait_ref.display(db), 555 trait_ref.display(db),
564 where_clauses 556 where_clauses
565 ); 557 );
566 let trait_ref = trait_ref.to_chalk(db);
567 558
568 let polarity = if negative { rust_ir::Polarity::Negative } else { rust_ir::Polarity::Positive }; 559 let polarity = if negative { rust_ir::Polarity::Negative } else { rust_ir::Polarity::Positive };
569 560
@@ -585,7 +576,7 @@ fn impl_def_datum(
585 .collect(); 576 .collect();
586 debug!("impl_datum: {:?}", impl_datum_bound); 577 debug!("impl_datum: {:?}", impl_datum_bound);
587 let impl_datum = ImplDatum { 578 let impl_datum = ImplDatum {
588 binders: make_binders(impl_datum_bound, bound_vars.len(&Interner)), 579 binders: make_only_type_binders(bound_vars.len(&Interner), impl_datum_bound),
589 impl_type, 580 impl_type,
590 polarity, 581 polarity,
591 associated_ty_value_ids, 582 associated_ty_value_ids,
@@ -624,7 +615,7 @@ fn type_alias_associated_ty_value(
624 .associated_type_by_name(&type_alias_data.name) 615 .associated_type_by_name(&type_alias_data.name)
625 .expect("assoc ty value should not exist"); // validated when building the impl data as well 616 .expect("assoc ty value should not exist"); // validated when building the impl data as well
626 let (ty, binders) = db.ty(type_alias.into()).into_value_and_skipped_binders(); 617 let (ty, binders) = db.ty(type_alias.into()).into_value_and_skipped_binders();
627 let value_bound = rust_ir::AssociatedTyValueBound { ty: ty.to_chalk(db) }; 618 let value_bound = rust_ir::AssociatedTyValueBound { ty };
628 let value = rust_ir::AssociatedTyValue { 619 let value = rust_ir::AssociatedTyValue {
629 impl_id: impl_id.to_chalk(db), 620 impl_id: impl_id.to_chalk(db),
630 associated_ty_id: to_assoc_type_id(assoc_ty), 621 associated_ty_id: to_assoc_type_id(assoc_ty),
@@ -645,13 +636,13 @@ pub(crate) fn fn_def_datum_query(
645 let where_clauses = convert_where_clauses(db, callable_def.into(), &bound_vars); 636 let where_clauses = convert_where_clauses(db, callable_def.into(), &bound_vars);
646 let bound = rust_ir::FnDefDatumBound { 637 let bound = rust_ir::FnDefDatumBound {
647 // Note: Chalk doesn't actually use this information yet as far as I am aware, but we provide it anyway 638 // Note: Chalk doesn't actually use this information yet as far as I am aware, but we provide it anyway
648 inputs_and_output: make_binders( 639 inputs_and_output: make_only_type_binders(
640 0,
649 rust_ir::FnDefInputsAndOutputDatum { 641 rust_ir::FnDefInputsAndOutputDatum {
650 argument_types: sig.params().iter().map(|ty| ty.clone().to_chalk(db)).collect(), 642 argument_types: sig.params().iter().cloned().collect(),
651 return_type: sig.ret().clone().to_chalk(db), 643 return_type: sig.ret().clone(),
652 } 644 }
653 .shifted_in(&Interner), 645 .shifted_in(&Interner),
654 0,
655 ), 646 ),
656 where_clauses, 647 where_clauses,
657 }; 648 };
diff --git a/crates/hir_ty/src/traits/chalk/mapping.rs b/crates/hir_ty/src/traits/chalk/mapping.rs
index 701359e6f..7818f6387 100644
--- a/crates/hir_ty/src/traits/chalk/mapping.rs
+++ b/crates/hir_ty/src/traits/chalk/mapping.rs
@@ -3,233 +3,20 @@
3//! Chalk (in both directions); plus some helper functions for more specialized 3//! Chalk (in both directions); plus some helper functions for more specialized
4//! conversions. 4//! conversions.
5 5
6use chalk_ir::{cast::Cast, interner::HasInterner}; 6use chalk_ir::cast::Cast;
7use chalk_solve::rust_ir; 7use chalk_solve::rust_ir;
8 8
9use base_db::salsa::InternKey; 9use base_db::salsa::InternKey;
10use hir_def::{GenericDefId, TypeAliasId}; 10use hir_def::{GenericDefId, TypeAliasId};
11 11
12use crate::{ 12use crate::{
13 db::HirDatabase, static_lifetime, AliasTy, CallableDefId, Canonical, ConstrainedSubst, 13 db::HirDatabase, AliasTy, CallableDefId, ProjectionTyExt, QuantifiedWhereClause, Substitution,
14 DomainGoal, FnPointer, GenericArg, InEnvironment, OpaqueTy, ProjectionTy, ProjectionTyExt, 14 Ty, WhereClause,
15 QuantifiedWhereClause, Substitution, TraitRef, Ty, TypeWalk, WhereClause,
16}; 15};
17 16
18use super::interner::*; 17use super::interner::*;
19use super::*; 18use super::*;
20 19
21impl ToChalk for Ty {
22 type Chalk = chalk_ir::Ty<Interner>;
23 fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Ty<Interner> {
24 match self.into_inner() {
25 TyKind::Ref(m, lt, ty) => {
26 chalk_ir::TyKind::Ref(m, lt, ty.to_chalk(db)).intern(&Interner)
27 }
28 TyKind::Array(ty, size) => {
29 chalk_ir::TyKind::Array(ty.to_chalk(db), size).intern(&Interner)
30 }
31 TyKind::Function(FnPointer { sig, substitution: substs, num_binders }) => {
32 let substitution = chalk_ir::FnSubst(substs.0.to_chalk(db));
33 chalk_ir::TyKind::Function(chalk_ir::FnPointer { num_binders, sig, substitution })
34 .intern(&Interner)
35 }
36 TyKind::AssociatedType(assoc_type_id, substs) => {
37 let substitution = substs.to_chalk(db);
38 chalk_ir::TyKind::AssociatedType(assoc_type_id, substitution).intern(&Interner)
39 }
40
41 TyKind::OpaqueType(id, substs) => {
42 let substitution = substs.to_chalk(db);
43 chalk_ir::TyKind::OpaqueType(id, substitution).intern(&Interner)
44 }
45
46 TyKind::Foreign(id) => chalk_ir::TyKind::Foreign(id).intern(&Interner),
47
48 TyKind::Scalar(scalar) => chalk_ir::TyKind::Scalar(scalar).intern(&Interner),
49
50 TyKind::Tuple(cardinality, substs) => {
51 let substitution = substs.to_chalk(db);
52 chalk_ir::TyKind::Tuple(cardinality, substitution).intern(&Interner)
53 }
54 TyKind::Raw(mutability, ty) => {
55 let ty = ty.to_chalk(db);
56 chalk_ir::TyKind::Raw(mutability, ty).intern(&Interner)
57 }
58 TyKind::Slice(ty) => chalk_ir::TyKind::Slice(ty.to_chalk(db)).intern(&Interner),
59 TyKind::Str => chalk_ir::TyKind::Str.intern(&Interner),
60 TyKind::FnDef(id, substs) => {
61 let substitution = substs.to_chalk(db);
62 chalk_ir::TyKind::FnDef(id, substitution).intern(&Interner)
63 }
64 TyKind::Never => chalk_ir::TyKind::Never.intern(&Interner),
65
66 TyKind::Closure(closure_id, substs) => {
67 let substitution = substs.to_chalk(db);
68 chalk_ir::TyKind::Closure(closure_id, substitution).intern(&Interner)
69 }
70
71 TyKind::Adt(adt_id, substs) => {
72 let substitution = substs.to_chalk(db);
73 chalk_ir::TyKind::Adt(adt_id, substitution).intern(&Interner)
74 }
75 TyKind::Alias(AliasTy::Projection(proj_ty)) => {
76 chalk_ir::AliasTy::Projection(proj_ty.to_chalk(db))
77 .cast(&Interner)
78 .intern(&Interner)
79 }
80 TyKind::Alias(AliasTy::Opaque(opaque_ty)) => {
81 chalk_ir::AliasTy::Opaque(opaque_ty.to_chalk(db)).cast(&Interner).intern(&Interner)
82 }
83 TyKind::Placeholder(idx) => idx.to_ty::<Interner>(&Interner),
84 TyKind::BoundVar(idx) => chalk_ir::TyKind::BoundVar(idx).intern(&Interner),
85 TyKind::InferenceVar(..) => panic!("uncanonicalized infer ty"),
86 TyKind::Dyn(dyn_ty) => {
87 let (bounds, binders) = dyn_ty.bounds.into_value_and_skipped_binders();
88 let where_clauses = chalk_ir::QuantifiedWhereClauses::from_iter(
89 &Interner,
90 bounds.interned().iter().cloned().map(|p| p.to_chalk(db)),
91 );
92 let bounded_ty = chalk_ir::DynTy {
93 bounds: chalk_ir::Binders::new(binders, where_clauses),
94 lifetime: dyn_ty.lifetime,
95 };
96 chalk_ir::TyKind::Dyn(bounded_ty).intern(&Interner)
97 }
98 TyKind::Error => chalk_ir::TyKind::Error.intern(&Interner),
99 }
100 }
101 fn from_chalk(db: &dyn HirDatabase, chalk: chalk_ir::Ty<Interner>) -> Self {
102 match chalk.data(&Interner).kind.clone() {
103 chalk_ir::TyKind::Error => TyKind::Error,
104 chalk_ir::TyKind::Array(ty, size) => TyKind::Array(from_chalk(db, ty), size),
105 chalk_ir::TyKind::Placeholder(idx) => TyKind::Placeholder(idx),
106 chalk_ir::TyKind::Alias(chalk_ir::AliasTy::Projection(proj)) => {
107 TyKind::Alias(AliasTy::Projection(from_chalk(db, proj)))
108 }
109 chalk_ir::TyKind::Alias(chalk_ir::AliasTy::Opaque(opaque_ty)) => {
110 TyKind::Alias(AliasTy::Opaque(from_chalk(db, opaque_ty)))
111 }
112 chalk_ir::TyKind::Function(chalk_ir::FnPointer {
113 num_binders,
114 sig,
115 substitution,
116 ..
117 }) => {
118 assert_eq!(num_binders, 0);
119 let substs = crate::FnSubst(from_chalk(db, substitution.0));
120 TyKind::Function(FnPointer { num_binders, sig, substitution: substs })
121 }
122 chalk_ir::TyKind::BoundVar(idx) => TyKind::BoundVar(idx),
123 chalk_ir::TyKind::InferenceVar(_iv, _kind) => TyKind::Error,
124 chalk_ir::TyKind::Dyn(dyn_ty) => {
125 assert_eq!(dyn_ty.bounds.binders.len(&Interner), 1);
126 let (bounds, binders) = dyn_ty.bounds.into_value_and_skipped_binders();
127 let where_clauses = crate::QuantifiedWhereClauses::from_iter(
128 &Interner,
129 bounds.interned().iter().cloned().map(|p| from_chalk(db, p)),
130 );
131 TyKind::Dyn(crate::DynTy {
132 bounds: crate::Binders::new(binders, where_clauses),
133 // HACK: we sometimes get lifetime variables back in solutions
134 // from Chalk, and don't have the infrastructure to substitute
135 // them yet. So for now we just turn them into 'static right
136 // when we get them
137 lifetime: static_lifetime(),
138 })
139 }
140
141 chalk_ir::TyKind::Adt(adt_id, subst) => TyKind::Adt(adt_id, from_chalk(db, subst)),
142 chalk_ir::TyKind::AssociatedType(type_id, subst) => {
143 TyKind::AssociatedType(type_id, from_chalk(db, subst))
144 }
145
146 chalk_ir::TyKind::OpaqueType(opaque_type_id, subst) => {
147 TyKind::OpaqueType(opaque_type_id, from_chalk(db, subst))
148 }
149
150 chalk_ir::TyKind::Scalar(scalar) => TyKind::Scalar(scalar),
151 chalk_ir::TyKind::Tuple(cardinality, subst) => {
152 TyKind::Tuple(cardinality, from_chalk(db, subst))
153 }
154 chalk_ir::TyKind::Raw(mutability, ty) => TyKind::Raw(mutability, from_chalk(db, ty)),
155 chalk_ir::TyKind::Slice(ty) => TyKind::Slice(from_chalk(db, ty)),
156 chalk_ir::TyKind::Ref(mutability, _lifetime, ty) => {
157 // HACK: we sometimes get lifetime variables back in solutions
158 // from Chalk, and don't have the infrastructure to substitute
159 // them yet. So for now we just turn them into 'static right
160 // when we get them
161 TyKind::Ref(mutability, static_lifetime(), from_chalk(db, ty))
162 }
163 chalk_ir::TyKind::Str => TyKind::Str,
164 chalk_ir::TyKind::Never => TyKind::Never,
165
166 chalk_ir::TyKind::FnDef(fn_def_id, subst) => {
167 TyKind::FnDef(fn_def_id, from_chalk(db, subst))
168 }
169
170 chalk_ir::TyKind::Closure(id, subst) => TyKind::Closure(id, from_chalk(db, subst)),
171
172 chalk_ir::TyKind::Foreign(foreign_def_id) => TyKind::Foreign(foreign_def_id),
173 chalk_ir::TyKind::Generator(_, _) => unimplemented!(), // FIXME
174 chalk_ir::TyKind::GeneratorWitness(_, _) => unimplemented!(), // FIXME
175 }
176 .intern(&Interner)
177 }
178}
179
180impl ToChalk for GenericArg {
181 type Chalk = chalk_ir::GenericArg<Interner>;
182
183 fn to_chalk(self, db: &dyn HirDatabase) -> Self::Chalk {
184 match self.interned() {
185 crate::GenericArgData::Ty(ty) => ty.clone().to_chalk(db).cast(&Interner),
186 }
187 }
188
189 fn from_chalk(db: &dyn HirDatabase, chalk: Self::Chalk) -> Self {
190 match chalk.interned() {
191 chalk_ir::GenericArgData::Ty(ty) => Ty::from_chalk(db, ty.clone()).cast(&Interner),
192 chalk_ir::GenericArgData::Lifetime(_) => unimplemented!(),
193 chalk_ir::GenericArgData::Const(_) => unimplemented!(),
194 }
195 }
196}
197
198impl ToChalk for Substitution {
199 type Chalk = chalk_ir::Substitution<Interner>;
200
201 fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Substitution<Interner> {
202 chalk_ir::Substitution::from_iter(
203 &Interner,
204 self.iter(&Interner).map(|ty| ty.clone().to_chalk(db)),
205 )
206 }
207
208 fn from_chalk(
209 db: &dyn HirDatabase,
210 parameters: chalk_ir::Substitution<Interner>,
211 ) -> Substitution {
212 let tys = parameters.iter(&Interner).map(|p| from_chalk(db, p.clone())).collect();
213 Substitution::intern(tys)
214 }
215}
216
217impl ToChalk for TraitRef {
218 type Chalk = chalk_ir::TraitRef<Interner>;
219
220 fn to_chalk(self: TraitRef, db: &dyn HirDatabase) -> chalk_ir::TraitRef<Interner> {
221 let trait_id = self.trait_id;
222 let substitution = self.substitution.to_chalk(db);
223 chalk_ir::TraitRef { trait_id, substitution }
224 }
225
226 fn from_chalk(db: &dyn HirDatabase, trait_ref: chalk_ir::TraitRef<Interner>) -> Self {
227 let trait_id = trait_ref.trait_id;
228 let substs = from_chalk(db, trait_ref.substitution);
229 TraitRef { trait_id, substitution: substs }
230 }
231}
232
233impl ToChalk for hir_def::TraitId { 20impl ToChalk for hir_def::TraitId {
234 type Chalk = TraitId; 21 type Chalk = TraitId;
235 22
@@ -283,208 +70,6 @@ impl ToChalk for TypeAliasAsValue {
283 } 70 }
284} 71}
285 72
286impl ToChalk for WhereClause {
287 type Chalk = chalk_ir::WhereClause<Interner>;
288
289 fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::WhereClause<Interner> {
290 match self {
291 WhereClause::Implemented(trait_ref) => {
292 chalk_ir::WhereClause::Implemented(trait_ref.to_chalk(db))
293 }
294 WhereClause::AliasEq(alias_eq) => chalk_ir::WhereClause::AliasEq(alias_eq.to_chalk(db)),
295 }
296 }
297
298 fn from_chalk(
299 db: &dyn HirDatabase,
300 where_clause: chalk_ir::WhereClause<Interner>,
301 ) -> WhereClause {
302 match where_clause {
303 chalk_ir::WhereClause::Implemented(tr) => WhereClause::Implemented(from_chalk(db, tr)),
304 chalk_ir::WhereClause::AliasEq(alias_eq) => {
305 WhereClause::AliasEq(from_chalk(db, alias_eq))
306 }
307
308 chalk_ir::WhereClause::LifetimeOutlives(_) => {
309 // we shouldn't get these from Chalk
310 panic!("encountered LifetimeOutlives from Chalk")
311 }
312
313 chalk_ir::WhereClause::TypeOutlives(_) => {
314 // we shouldn't get these from Chalk
315 panic!("encountered TypeOutlives from Chalk")
316 }
317 }
318 }
319}
320
321impl ToChalk for ProjectionTy {
322 type Chalk = chalk_ir::ProjectionTy<Interner>;
323
324 fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::ProjectionTy<Interner> {
325 chalk_ir::ProjectionTy {
326 associated_ty_id: self.associated_ty_id,
327 substitution: self.substitution.to_chalk(db),
328 }
329 }
330
331 fn from_chalk(
332 db: &dyn HirDatabase,
333 projection_ty: chalk_ir::ProjectionTy<Interner>,
334 ) -> ProjectionTy {
335 ProjectionTy {
336 associated_ty_id: projection_ty.associated_ty_id,
337 substitution: from_chalk(db, projection_ty.substitution),
338 }
339 }
340}
341impl ToChalk for OpaqueTy {
342 type Chalk = chalk_ir::OpaqueTy<Interner>;
343
344 fn to_chalk(self, db: &dyn HirDatabase) -> Self::Chalk {
345 chalk_ir::OpaqueTy {
346 opaque_ty_id: self.opaque_ty_id,
347 substitution: self.substitution.to_chalk(db),
348 }
349 }
350
351 fn from_chalk(db: &dyn HirDatabase, chalk: Self::Chalk) -> Self {
352 OpaqueTy {
353 opaque_ty_id: chalk.opaque_ty_id,
354 substitution: from_chalk(db, chalk.substitution),
355 }
356 }
357}
358
359impl ToChalk for AliasTy {
360 type Chalk = chalk_ir::AliasTy<Interner>;
361
362 fn to_chalk(self, db: &dyn HirDatabase) -> Self::Chalk {
363 match self {
364 AliasTy::Projection(projection_ty) => {
365 chalk_ir::AliasTy::Projection(projection_ty.to_chalk(db))
366 }
367 AliasTy::Opaque(opaque_ty) => chalk_ir::AliasTy::Opaque(opaque_ty.to_chalk(db)),
368 }
369 }
370
371 fn from_chalk(db: &dyn HirDatabase, chalk: Self::Chalk) -> Self {
372 match chalk {
373 chalk_ir::AliasTy::Projection(projection_ty) => {
374 AliasTy::Projection(from_chalk(db, projection_ty))
375 }
376 chalk_ir::AliasTy::Opaque(opaque_ty) => AliasTy::Opaque(from_chalk(db, opaque_ty)),
377 }
378 }
379}
380
381impl ToChalk for AliasEq {
382 type Chalk = chalk_ir::AliasEq<Interner>;
383
384 fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::AliasEq<Interner> {
385 chalk_ir::AliasEq { alias: self.alias.to_chalk(db), ty: self.ty.to_chalk(db) }
386 }
387
388 fn from_chalk(db: &dyn HirDatabase, alias_eq: chalk_ir::AliasEq<Interner>) -> Self {
389 AliasEq { alias: from_chalk(db, alias_eq.alias), ty: from_chalk(db, alias_eq.ty) }
390 }
391}
392
393impl ToChalk for DomainGoal {
394 type Chalk = chalk_ir::DomainGoal<Interner>;
395
396 fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::DomainGoal<Interner> {
397 match self {
398 DomainGoal::Holds(WhereClause::Implemented(tr)) => tr.to_chalk(db).cast(&Interner),
399 DomainGoal::Holds(WhereClause::AliasEq(alias_eq)) => {
400 alias_eq.to_chalk(db).cast(&Interner)
401 }
402 }
403 }
404
405 fn from_chalk(_db: &dyn HirDatabase, _goal: chalk_ir::DomainGoal<Interner>) -> Self {
406 unimplemented!()
407 }
408}
409
410impl<T> ToChalk for Canonical<T>
411where
412 T: ToChalk,
413 T::Chalk: HasInterner<Interner = Interner>,
414{
415 type Chalk = chalk_ir::Canonical<T::Chalk>;
416
417 fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Canonical<T::Chalk> {
418 let value = self.value.to_chalk(db);
419 chalk_ir::Canonical { value, binders: self.binders }
420 }
421
422 fn from_chalk(db: &dyn HirDatabase, canonical: chalk_ir::Canonical<T::Chalk>) -> Canonical<T> {
423 Canonical { binders: canonical.binders, value: from_chalk(db, canonical.value) }
424 }
425}
426
427impl<T: ToChalk> ToChalk for InEnvironment<T>
428where
429 T::Chalk: chalk_ir::interner::HasInterner<Interner = Interner>,
430{
431 type Chalk = chalk_ir::InEnvironment<T::Chalk>;
432
433 fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::InEnvironment<T::Chalk> {
434 chalk_ir::InEnvironment { environment: self.environment, goal: self.goal.to_chalk(db) }
435 }
436
437 fn from_chalk(
438 _db: &dyn HirDatabase,
439 _in_env: chalk_ir::InEnvironment<T::Chalk>,
440 ) -> InEnvironment<T> {
441 unimplemented!()
442 }
443}
444
445impl<T: ToChalk> ToChalk for crate::Binders<T>
446where
447 T::Chalk: chalk_ir::interner::HasInterner<Interner = Interner>,
448{
449 type Chalk = chalk_ir::Binders<T::Chalk>;
450
451 fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Binders<T::Chalk> {
452 let (value, binders) = self.into_value_and_skipped_binders();
453 chalk_ir::Binders::new(binders, value.to_chalk(db))
454 }
455
456 fn from_chalk(db: &dyn HirDatabase, binders: chalk_ir::Binders<T::Chalk>) -> crate::Binders<T> {
457 let (v, b) = binders.into_value_and_skipped_binders();
458 crate::Binders::new(b, from_chalk(db, v))
459 }
460}
461
462impl ToChalk for crate::ConstrainedSubst {
463 type Chalk = chalk_ir::ConstrainedSubst<Interner>;
464
465 fn to_chalk(self, _db: &dyn HirDatabase) -> Self::Chalk {
466 unimplemented!()
467 }
468
469 fn from_chalk(db: &dyn HirDatabase, chalk: Self::Chalk) -> Self {
470 ConstrainedSubst { subst: from_chalk(db, chalk.subst) }
471 }
472}
473
474pub(super) fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T>
475where
476 T: HasInterner<Interner = Interner>,
477{
478 chalk_ir::Binders::new(
479 chalk_ir::VariableKinds::from_iter(
480 &Interner,
481 std::iter::repeat(chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General))
482 .take(num_vars),
483 ),
484 value,
485 )
486}
487
488pub(super) fn convert_where_clauses( 73pub(super) fn convert_where_clauses(
489 db: &dyn HirDatabase, 74 db: &dyn HirDatabase,
490 def: GenericDefId, 75 def: GenericDefId,
@@ -493,7 +78,7 @@ pub(super) fn convert_where_clauses(
493 let generic_predicates = db.generic_predicates(def); 78 let generic_predicates = db.generic_predicates(def);
494 let mut result = Vec::with_capacity(generic_predicates.len()); 79 let mut result = Vec::with_capacity(generic_predicates.len());
495 for pred in generic_predicates.iter() { 80 for pred in generic_predicates.iter() {
496 result.push(pred.clone().substitute(&Interner, substs).to_chalk(db)); 81 result.push(pred.clone().substitute(&Interner, substs));
497 } 82 }
498 result 83 result
499} 84}
@@ -505,7 +90,7 @@ pub(super) fn generic_predicate_to_inline_bound(
505) -> Option<chalk_ir::Binders<rust_ir::InlineBound<Interner>>> { 90) -> Option<chalk_ir::Binders<rust_ir::InlineBound<Interner>>> {
506 // An InlineBound is like a GenericPredicate, except the self type is left out. 91 // An InlineBound is like a GenericPredicate, except the self type is left out.
507 // We don't have a special type for this, but Chalk does. 92 // We don't have a special type for this, but Chalk does.
508 let self_ty_shifted_in = self_ty.clone().shifted_in_from(DebruijnIndex::ONE); 93 let self_ty_shifted_in = self_ty.clone().shifted_in_from(&Interner, DebruijnIndex::ONE);
509 let (pred, binders) = pred.as_ref().into_value_and_skipped_binders(); 94 let (pred, binders) = pred.as_ref().into_value_and_skipped_binders();
510 match pred { 95 match pred {
511 WhereClause::Implemented(trait_ref) => { 96 WhereClause::Implemented(trait_ref) => {
@@ -516,7 +101,7 @@ pub(super) fn generic_predicate_to_inline_bound(
516 } 101 }
517 let args_no_self = trait_ref.substitution.interned()[1..] 102 let args_no_self = trait_ref.substitution.interned()[1..]
518 .iter() 103 .iter()
519 .map(|ty| ty.clone().to_chalk(db).cast(&Interner)) 104 .map(|ty| ty.clone().cast(&Interner))
520 .collect(); 105 .collect();
521 let trait_bound = rust_ir::TraitBound { trait_id: trait_ref.trait_id, args_no_self }; 106 let trait_bound = rust_ir::TraitBound { trait_id: trait_ref.trait_id, args_no_self };
522 Some(chalk_ir::Binders::new(binders, rust_ir::InlineBound::TraitBound(trait_bound))) 107 Some(chalk_ir::Binders::new(binders, rust_ir::InlineBound::TraitBound(trait_bound)))
@@ -528,10 +113,10 @@ pub(super) fn generic_predicate_to_inline_bound(
528 let trait_ = projection_ty.trait_(db); 113 let trait_ = projection_ty.trait_(db);
529 let args_no_self = projection_ty.substitution.interned()[1..] 114 let args_no_self = projection_ty.substitution.interned()[1..]
530 .iter() 115 .iter()
531 .map(|ty| ty.clone().to_chalk(db).cast(&Interner)) 116 .map(|ty| ty.clone().cast(&Interner))
532 .collect(); 117 .collect();
533 let alias_eq_bound = rust_ir::AliasEqBound { 118 let alias_eq_bound = rust_ir::AliasEqBound {
534 value: ty.clone().to_chalk(db), 119 value: ty.clone(),
535 trait_bound: rust_ir::TraitBound { trait_id: trait_.to_chalk(db), args_no_self }, 120 trait_bound: rust_ir::TraitBound { trait_id: trait_.to_chalk(db), args_no_self },
536 associated_ty_id: projection_ty.associated_ty_id, 121 associated_ty_id: projection_ty.associated_ty_id,
537 parameters: Vec::new(), // FIXME we don't support generic associated types yet 122 parameters: Vec::new(), // FIXME we don't support generic associated types yet
diff --git a/crates/hir_ty/src/types.rs b/crates/hir_ty/src/types.rs
deleted file mode 100644
index 89adad108..000000000
--- a/crates/hir_ty/src/types.rs
+++ /dev/null
@@ -1,549 +0,0 @@
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::{Cast, CastTo, Caster},
8 BoundVar, Mutability, Scalar, TyVariableKind,
9};
10use smallvec::SmallVec;
11
12use crate::{
13 AssocTypeId, CanonicalVarKinds, ChalkTraitId, ClosureId, Const, FnDefId, FnSig, ForeignDefId,
14 Interner, Lifetime, OpaqueTyId, PlaceholderIndex, TypeWalk, VariableKind, VariableKinds,
15};
16
17#[derive(Clone, PartialEq, Eq, Debug, Hash)]
18pub struct OpaqueTy {
19 pub opaque_ty_id: OpaqueTyId,
20 pub substitution: Substitution,
21}
22
23/// A "projection" type corresponds to an (unnormalized)
24/// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
25/// trait and all its parameters are fully known.
26#[derive(Clone, PartialEq, Eq, Debug, Hash)]
27pub struct ProjectionTy {
28 pub associated_ty_id: AssocTypeId,
29 pub substitution: Substitution,
30}
31
32impl ProjectionTy {
33 pub fn self_type_parameter(&self, interner: &Interner) -> Ty {
34 self.substitution.interned()[0].assert_ty_ref(interner).clone()
35 }
36}
37
38#[derive(Clone, PartialEq, Eq, Debug, Hash)]
39pub struct DynTy {
40 /// The unknown self type.
41 pub bounds: Binders<QuantifiedWhereClauses>,
42 pub lifetime: Lifetime,
43}
44
45#[derive(Clone, PartialEq, Eq, Debug, Hash)]
46pub struct FnPointer {
47 pub num_binders: usize,
48 pub sig: FnSig,
49 pub substitution: FnSubst,
50}
51/// A wrapper for the substs on a Fn.
52#[derive(Clone, PartialEq, Eq, Debug, Hash)]
53pub struct FnSubst(pub Substitution);
54
55impl FnPointer {
56 /// Represent the current `Fn` as if it was wrapped in `Binders`
57 pub fn into_binders(self, interner: &Interner) -> Binders<FnSubst> {
58 Binders::new(
59 VariableKinds::from_iter(
60 interner,
61 (0..self.num_binders).map(|_| VariableKind::Lifetime),
62 ),
63 self.substitution,
64 )
65 }
66
67 /// Represent the current `Fn` as if it was wrapped in `Binders`
68 pub fn as_binders(&self, interner: &Interner) -> Binders<&FnSubst> {
69 Binders::new(
70 VariableKinds::from_iter(
71 interner,
72 (0..self.num_binders).map(|_| VariableKind::Lifetime),
73 ),
74 &self.substitution,
75 )
76 }
77}
78
79#[derive(Clone, PartialEq, Eq, Debug, Hash)]
80pub enum AliasTy {
81 /// A "projection" type corresponds to an (unnormalized)
82 /// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
83 /// trait and all its parameters are fully known.
84 Projection(ProjectionTy),
85 /// An opaque type (`impl Trait`).
86 ///
87 /// This is currently only used for return type impl trait; each instance of
88 /// `impl Trait` in a return type gets its own ID.
89 Opaque(OpaqueTy),
90}
91
92/// A type.
93///
94/// See also the `TyKind` enum in rustc (librustc/ty/sty.rs), which represents
95/// the same thing (but in a different way).
96///
97/// This should be cheap to clone.
98#[derive(Clone, PartialEq, Eq, Debug, Hash)]
99pub enum TyKind {
100 /// Structures, enumerations and unions.
101 Adt(chalk_ir::AdtId<Interner>, Substitution),
102
103 /// Represents an associated item like `Iterator::Item`. This is used
104 /// when we have tried to normalize a projection like `T::Item` but
105 /// couldn't find a better representation. In that case, we generate
106 /// an **application type** like `(Iterator::Item)<T>`.
107 AssociatedType(AssocTypeId, Substitution),
108
109 /// a scalar type like `bool` or `u32`
110 Scalar(Scalar),
111
112 /// A tuple type. For example, `(i32, bool)`.
113 Tuple(usize, Substitution),
114
115 /// An array with the given length. Written as `[T; n]`.
116 Array(Ty, Const),
117
118 /// The pointee of an array slice. Written as `[T]`.
119 Slice(Ty),
120
121 /// A raw pointer. Written as `*mut T` or `*const T`
122 Raw(Mutability, Ty),
123
124 /// A reference; a pointer with an associated lifetime. Written as
125 /// `&'a mut T` or `&'a T`.
126 Ref(Mutability, Lifetime, Ty),
127
128 /// This represents a placeholder for an opaque type in situations where we
129 /// don't know the hidden type (i.e. currently almost always). This is
130 /// analogous to the `AssociatedType` type constructor.
131 /// It is also used as the type of async block, with one type parameter
132 /// representing the Future::Output type.
133 OpaqueType(OpaqueTyId, Substitution),
134
135 /// The anonymous type of a function declaration/definition. Each
136 /// function has a unique type, which is output (for a function
137 /// named `foo` returning an `i32`) as `fn() -> i32 {foo}`.
138 ///
139 /// This includes tuple struct / enum variant constructors as well.
140 ///
141 /// For example the type of `bar` here:
142 ///
143 /// ```
144 /// fn foo() -> i32 { 1 }
145 /// let bar = foo; // bar: fn() -> i32 {foo}
146 /// ```
147 FnDef(FnDefId, Substitution),
148
149 /// The pointee of a string slice. Written as `str`.
150 Str,
151
152 /// The never type `!`.
153 Never,
154
155 /// The type of a specific closure.
156 ///
157 /// The closure signature is stored in a `FnPtr` type in the first type
158 /// parameter.
159 Closure(ClosureId, Substitution),
160
161 /// Represents a foreign type declared in external blocks.
162 Foreign(ForeignDefId),
163
164 /// A pointer to a function. Written as `fn() -> i32`.
165 ///
166 /// For example the type of `bar` here:
167 ///
168 /// ```
169 /// fn foo() -> i32 { 1 }
170 /// let bar: fn() -> i32 = foo;
171 /// ```
172 Function(FnPointer),
173
174 /// An "alias" type represents some form of type alias, such as:
175 /// - An associated type projection like `<T as Iterator>::Item`
176 /// - `impl Trait` types
177 /// - Named type aliases like `type Foo<X> = Vec<X>`
178 Alias(AliasTy),
179
180 /// A placeholder for a type parameter; for example, `T` in `fn f<T>(x: T)
181 /// {}` when we're type-checking the body of that function. In this
182 /// situation, we know this stands for *some* type, but don't know the exact
183 /// type.
184 Placeholder(PlaceholderIndex),
185
186 /// A bound type variable. This is used in various places: when representing
187 /// some polymorphic type like the type of function `fn f<T>`, the type
188 /// parameters get turned into variables; during trait resolution, inference
189 /// variables get turned into bound variables and back; and in `Dyn` the
190 /// `Self` type is represented with a bound variable as well.
191 BoundVar(BoundVar),
192
193 /// A type variable used during type checking.
194 InferenceVar(InferenceVar, TyVariableKind),
195
196 /// A trait object (`dyn Trait` or bare `Trait` in pre-2018 Rust).
197 ///
198 /// The predicates are quantified over the `Self` type, i.e. `Ty::Bound(0)`
199 /// represents the `Self` type inside the bounds. This is currently
200 /// implicit; Chalk has the `Binders` struct to make it explicit, but it
201 /// didn't seem worth the overhead yet.
202 Dyn(DynTy),
203
204 /// A placeholder for a type which could not be computed; this is propagated
205 /// to avoid useless error messages. Doubles as a placeholder where type
206 /// variables are inserted before type checking, since we want to try to
207 /// infer a better type here anyway -- for the IDE use case, we want to try
208 /// to infer as much as possible even in the presence of type errors.
209 Error,
210}
211
212#[derive(Clone, PartialEq, Eq, Debug, Hash)]
213pub struct Ty(Arc<TyKind>);
214
215impl TyKind {
216 pub fn intern(self, _interner: &Interner) -> Ty {
217 Ty(Arc::new(self))
218 }
219}
220
221impl Ty {
222 pub fn kind(&self, _interner: &Interner) -> &TyKind {
223 &self.0
224 }
225
226 pub fn interned_mut(&mut self) -> &mut TyKind {
227 Arc::make_mut(&mut self.0)
228 }
229
230 pub fn into_inner(self) -> TyKind {
231 Arc::try_unwrap(self.0).unwrap_or_else(|a| (*a).clone())
232 }
233}
234
235#[derive(Clone, PartialEq, Eq, Debug, Hash)]
236pub struct GenericArg {
237 interned: GenericArgData,
238}
239
240#[derive(Clone, PartialEq, Eq, Debug, Hash)]
241pub enum GenericArgData {
242 Ty(Ty),
243}
244
245impl GenericArg {
246 /// Constructs a generic argument using `GenericArgData`.
247 pub fn new(_interner: &Interner, data: GenericArgData) -> Self {
248 GenericArg { interned: data }
249 }
250
251 /// Gets the interned value.
252 pub fn interned(&self) -> &GenericArgData {
253 &self.interned
254 }
255
256 /// Asserts that this is a type argument.
257 pub fn assert_ty_ref(&self, interner: &Interner) -> &Ty {
258 self.ty(interner).unwrap()
259 }
260
261 /// Checks whether the generic argument is a type.
262 pub fn is_ty(&self, _interner: &Interner) -> bool {
263 match self.interned() {
264 GenericArgData::Ty(_) => true,
265 }
266 }
267
268 /// Returns the type if it is one, `None` otherwise.
269 pub fn ty(&self, _interner: &Interner) -> Option<&Ty> {
270 match self.interned() {
271 GenericArgData::Ty(t) => Some(t),
272 }
273 }
274
275 pub fn interned_mut(&mut self) -> &mut GenericArgData {
276 &mut self.interned
277 }
278}
279
280/// A list of substitutions for generic parameters.
281#[derive(Clone, PartialEq, Eq, Debug, Hash)]
282pub struct Substitution(SmallVec<[GenericArg; 2]>);
283
284impl Substitution {
285 pub fn interned(&self) -> &SmallVec<[GenericArg; 2]> {
286 &self.0
287 }
288
289 pub fn len(&self, _: &Interner) -> usize {
290 self.0.len()
291 }
292
293 pub fn is_empty(&self, _: &Interner) -> bool {
294 self.0.is_empty()
295 }
296
297 pub fn at(&self, _: &Interner, i: usize) -> &GenericArg {
298 &self.0[i]
299 }
300
301 pub fn empty(_: &Interner) -> Substitution {
302 Substitution(SmallVec::new())
303 }
304
305 pub fn iter(&self, _: &Interner) -> std::slice::Iter<'_, GenericArg> {
306 self.0.iter()
307 }
308
309 pub fn from1(_interner: &Interner, ty: Ty) -> Substitution {
310 Substitution::intern({
311 let mut v = SmallVec::new();
312 v.push(ty.cast(&Interner));
313 v
314 })
315 }
316
317 pub fn from_iter(
318 interner: &Interner,
319 elements: impl IntoIterator<Item = impl CastTo<GenericArg>>,
320 ) -> Self {
321 Substitution(elements.into_iter().casted(interner).collect())
322 }
323
324 pub fn apply<T: TypeWalk>(&self, value: T, _interner: &Interner) -> T {
325 value.subst_bound_vars(self)
326 }
327
328 // Temporary helper functions, to be removed
329 pub fn intern(interned: SmallVec<[GenericArg; 2]>) -> Substitution {
330 Substitution(interned)
331 }
332
333 pub fn interned_mut(&mut self) -> &mut SmallVec<[GenericArg; 2]> {
334 &mut self.0
335 }
336}
337
338#[derive(Clone, PartialEq, Eq, Hash)]
339pub struct Binders<T> {
340 /// The binders that quantify over the value.
341 pub binders: VariableKinds,
342 value: T,
343}
344
345impl<T> Binders<T> {
346 pub fn new(binders: VariableKinds, value: T) -> Self {
347 Self { binders, value }
348 }
349
350 pub fn empty(_interner: &Interner, value: T) -> Self {
351 crate::make_only_type_binders(0, value)
352 }
353
354 pub fn as_ref(&self) -> Binders<&T> {
355 Binders { binders: self.binders.clone(), value: &self.value }
356 }
357
358 pub fn map<U>(self, f: impl FnOnce(T) -> U) -> Binders<U> {
359 Binders { binders: self.binders, value: f(self.value) }
360 }
361
362 pub fn filter_map<U>(self, f: impl FnOnce(T) -> Option<U>) -> Option<Binders<U>> {
363 Some(Binders { binders: self.binders, value: f(self.value)? })
364 }
365
366 pub fn skip_binders(&self) -> &T {
367 &self.value
368 }
369
370 pub fn into_value_and_skipped_binders(self) -> (T, VariableKinds) {
371 (self.value, self.binders)
372 }
373
374 /// Returns the number of binders.
375 pub fn len(&self, interner: &Interner) -> usize {
376 self.binders.len(interner)
377 }
378
379 // Temporary helper function, to be removed
380 pub fn skip_binders_mut(&mut self) -> &mut T {
381 &mut self.value
382 }
383}
384
385impl<T: Clone> Binders<&T> {
386 pub fn cloned(&self) -> Binders<T> {
387 Binders::new(self.binders.clone(), self.value.clone())
388 }
389}
390
391impl<T: TypeWalk> Binders<T> {
392 /// Substitutes all variables.
393 pub fn substitute(self, interner: &Interner, subst: &Substitution) -> T {
394 let (value, binders) = self.into_value_and_skipped_binders();
395 assert_eq!(subst.len(interner), binders.len(interner));
396 value.subst_bound_vars(subst)
397 }
398}
399
400impl<T: std::fmt::Debug> std::fmt::Debug for Binders<T> {
401 fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
402 let Binders { ref binders, ref value } = *self;
403 write!(fmt, "for{:?} ", binders.inner_debug(&Interner))?;
404 std::fmt::Debug::fmt(value, fmt)
405 }
406}
407
408/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait.
409#[derive(Clone, PartialEq, Eq, Debug, Hash)]
410pub struct TraitRef {
411 pub trait_id: ChalkTraitId,
412 pub substitution: Substitution,
413}
414
415impl TraitRef {
416 pub fn self_type_parameter(&self, interner: &Interner) -> Ty {
417 self.substitution.at(interner, 0).assert_ty_ref(interner).clone()
418 }
419}
420
421/// Like `generics::WherePredicate`, but with resolved types: A condition on the
422/// parameters of a generic item.
423#[derive(Debug, Clone, PartialEq, Eq, Hash)]
424pub enum WhereClause {
425 /// The given trait needs to be implemented for its type parameters.
426 Implemented(TraitRef),
427 /// An associated type bindings like in `Iterator<Item = T>`.
428 AliasEq(AliasEq),
429}
430
431pub type QuantifiedWhereClause = Binders<WhereClause>;
432
433#[derive(Debug, Clone, PartialEq, Eq, Hash)]
434pub struct QuantifiedWhereClauses(Arc<[QuantifiedWhereClause]>);
435
436impl QuantifiedWhereClauses {
437 pub fn from_iter(
438 _interner: &Interner,
439 elements: impl IntoIterator<Item = QuantifiedWhereClause>,
440 ) -> Self {
441 QuantifiedWhereClauses(elements.into_iter().collect())
442 }
443
444 pub fn interned(&self) -> &Arc<[QuantifiedWhereClause]> {
445 &self.0
446 }
447
448 pub fn interned_mut(&mut self) -> &mut Arc<[QuantifiedWhereClause]> {
449 &mut self.0
450 }
451}
452
453/// Basically a claim (currently not validated / checked) that the contained
454/// type / trait ref contains no inference variables; any inference variables it
455/// contained have been replaced by bound variables, and `kinds` tells us how
456/// many there are and whether they were normal or float/int variables. This is
457/// used to erase irrelevant differences between types before using them in
458/// queries.
459#[derive(Debug, Clone, PartialEq, Eq, Hash)]
460pub struct Canonical<T> {
461 pub value: T,
462 pub binders: CanonicalVarKinds,
463}
464
465/// Something (usually a goal), along with an environment.
466#[derive(Clone, Debug, PartialEq, Eq, Hash)]
467pub struct InEnvironment<T> {
468 pub environment: chalk_ir::Environment<Interner>,
469 pub goal: T,
470}
471
472impl<T> InEnvironment<T> {
473 pub fn new(environment: &chalk_ir::Environment<Interner>, value: T) -> InEnvironment<T> {
474 InEnvironment { environment: environment.clone(), goal: value }
475 }
476}
477
478/// Something that needs to be proven (by Chalk) during type checking, e.g. that
479/// a certain type implements a certain trait. Proving the Obligation might
480/// result in additional information about inference variables.
481#[derive(Clone, Debug, PartialEq, Eq, Hash)]
482pub enum DomainGoal {
483 Holds(WhereClause),
484}
485
486#[derive(Clone, Debug, PartialEq, Eq, Hash)]
487pub struct AliasEq {
488 pub alias: AliasTy,
489 pub ty: Ty,
490}
491
492#[derive(Clone, Debug, PartialEq, Eq)]
493pub struct ConstrainedSubst {
494 pub subst: Substitution,
495}
496
497#[derive(Clone, Debug, PartialEq, Eq)]
498/// A (possible) solution for a proposed goal.
499pub enum Solution {
500 /// The goal indeed holds, and there is a unique value for all existential
501 /// variables.
502 Unique(Canonical<ConstrainedSubst>),
503
504 /// The goal may be provable in multiple ways, but regardless we may have some guidance
505 /// for type inference. In this case, we don't return any lifetime
506 /// constraints, since we have not "committed" to any particular solution
507 /// yet.
508 Ambig(Guidance),
509}
510
511#[derive(Clone, Debug, PartialEq, Eq)]
512/// When a goal holds ambiguously (e.g., because there are multiple possible
513/// solutions), we issue a set of *guidance* back to type inference.
514pub enum Guidance {
515 /// The existential variables *must* have the given values if the goal is
516 /// ever to hold, but that alone isn't enough to guarantee the goal will
517 /// actually hold.
518 Definite(Canonical<Substitution>),
519
520 /// There are multiple plausible values for the existentials, but the ones
521 /// here are suggested as the preferred choice heuristically. These should
522 /// be used for inference fallback only.
523 Suggested(Canonical<Substitution>),
524
525 /// There's no useful information to feed back to type inference
526 Unknown,
527}
528
529/// The kinds of placeholders we need during type inference. There's separate
530/// values for general types, and for integer and float variables. The latter
531/// two are used for inference of literal values (e.g. `100` could be one of
532/// several integer types).
533#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
534pub struct InferenceVar {
535 index: u32,
536}
537
538impl From<u32> for InferenceVar {
539 fn from(index: u32) -> InferenceVar {
540 InferenceVar { index }
541 }
542}
543
544impl InferenceVar {
545 /// Gets the underlying index value.
546 pub fn index(self) -> u32 {
547 self.index
548 }
549}
diff --git a/crates/hir_ty/src/utils.rs b/crates/hir_ty/src/utils.rs
index 8d5d5cd73..5f6cb052a 100644
--- a/crates/hir_ty/src/utils.rs
+++ b/crates/hir_ty/src/utils.rs
@@ -1,8 +1,7 @@
1//! Helper functions for working with def, which don't need to be a separate 1//! Helper functions for working with def, which don't need to be a separate
2//! query, but can't be computed directly from `*Data` (ie, which need a `db`). 2//! query, but can't be computed directly from `*Data` (ie, which need a `db`).
3use std::sync::Arc;
4 3
5use chalk_ir::{BoundVar, DebruijnIndex}; 4use chalk_ir::{fold::Shift, BoundVar, DebruijnIndex};
6use hir_def::{ 5use hir_def::{
7 db::DefDatabase, 6 db::DefDatabase,
8 generics::{ 7 generics::{
@@ -16,9 +15,7 @@ use hir_def::{
16}; 15};
17use hir_expand::name::{name, Name}; 16use hir_expand::name::{name, Name};
18 17
19use crate::{ 18use crate::{db::HirDatabase, Interner, Substitution, TraitRef, TraitRefExt, TyKind, WhereClause};
20 db::HirDatabase, Interner, Substitution, TraitRef, TraitRefExt, TyKind, TypeWalk, WhereClause,
21};
22 19
23fn direct_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> Vec<TraitId> { 20fn direct_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> Vec<TraitId> {
24 let resolver = trait_.resolver(db); 21 let resolver = trait_.resolver(db);
@@ -69,7 +66,7 @@ fn direct_super_trait_refs(db: &dyn HirDatabase, trait_ref: &TraitRef) -> Vec<Tr
69 // FIXME: how to correctly handle higher-ranked bounds here? 66 // FIXME: how to correctly handle higher-ranked bounds here?
70 WhereClause::Implemented(tr) => Some( 67 WhereClause::Implemented(tr) => Some(
71 tr.clone() 68 tr.clone()
72 .shifted_out_to(DebruijnIndex::ONE) 69 .shifted_out_to(&Interner, DebruijnIndex::ONE)
73 .expect("FIXME unexpected higher-ranked trait bound"), 70 .expect("FIXME unexpected higher-ranked trait bound"),
74 ), 71 ),
75 _ => None, 72 _ => None,
@@ -137,15 +134,6 @@ pub(super) fn associated_type_by_name_including_super_traits(
137 }) 134 })
138} 135}
139 136
140/// Helper for mutating `Arc<[T]>` (i.e. `Arc::make_mut` for Arc slices).
141/// The underlying values are cloned if there are other strong references.
142pub(crate) fn make_mut_slice<T: Clone>(a: &mut Arc<[T]>) -> &mut [T] {
143 if Arc::get_mut(a).is_none() {
144 *a = a.iter().cloned().collect();
145 }
146 Arc::get_mut(a).unwrap()
147}
148
149pub(crate) fn generics(db: &dyn DefDatabase, def: GenericDefId) -> Generics { 137pub(crate) fn generics(db: &dyn DefDatabase, def: GenericDefId) -> Generics {
150 let parent_generics = parent_generic_def(db, def).map(|def| Box::new(generics(db, def))); 138 let parent_generics = parent_generic_def(db, def).map(|def| Box::new(generics(db, def)));
151 Generics { def, params: db.generic_params(def), parent_generics } 139 Generics { def, params: db.generic_params(def), parent_generics }
diff --git a/crates/hir_ty/src/walk.rs b/crates/hir_ty/src/walk.rs
index 91116dcda..6ef1d5336 100644
--- a/crates/hir_ty/src/walk.rs
+++ b/crates/hir_ty/src/walk.rs
@@ -1,138 +1,17 @@
1//! The `TypeWalk` trait (probably to be replaced by Chalk's `Fold` and 1//! The `TypeWalk` trait (probably to be replaced by Chalk's `Fold` and
2//! `Visit`). 2//! `Visit`).
3 3
4use std::mem; 4use chalk_ir::interner::HasInterner;
5
6use chalk_ir::DebruijnIndex;
7 5
8use crate::{ 6use crate::{
9 utils::make_mut_slice, AliasEq, AliasTy, Binders, CallableSig, FnSubst, GenericArg, 7 AliasEq, AliasTy, Binders, CallableSig, FnSubst, GenericArg, GenericArgData, Interner,
10 GenericArgData, Interner, OpaqueTy, ProjectionTy, Substitution, TraitRef, Ty, TyKind, 8 OpaqueTy, ProjectionTy, Substitution, TraitRef, Ty, TyKind, WhereClause,
11 WhereClause,
12}; 9};
13 10
14/// This allows walking structures that contain types to do something with those 11/// This allows walking structures that contain types to do something with those
15/// types, similar to Chalk's `Fold` trait. 12/// types, similar to Chalk's `Fold` trait.
16pub trait TypeWalk { 13pub trait TypeWalk {
17 fn walk(&self, f: &mut impl FnMut(&Ty)); 14 fn walk(&self, f: &mut impl FnMut(&Ty));
18 fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
19 self.walk_mut_binders(&mut |ty, _binders| f(ty), DebruijnIndex::INNERMOST);
20 }
21 /// Walk the type, counting entered binders.
22 ///
23 /// `TyKind::Bound` variables use DeBruijn indexing, which means that 0 refers
24 /// to the innermost binder, 1 to the next, etc.. So when we want to
25 /// substitute a certain bound variable, we can't just walk the whole type
26 /// and blindly replace each instance of a certain index; when we 'enter'
27 /// things that introduce new bound variables, we have to keep track of
28 /// that. Currently, the only thing that introduces bound variables on our
29 /// side are `TyKind::Dyn` and `TyKind::Opaque`, which each introduce a bound
30 /// variable for the self type.
31 fn walk_mut_binders(
32 &mut self,
33 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
34 binders: DebruijnIndex,
35 );
36
37 fn fold_binders(
38 mut self,
39 f: &mut impl FnMut(Ty, DebruijnIndex) -> Ty,
40 binders: DebruijnIndex,
41 ) -> Self
42 where
43 Self: Sized,
44 {
45 self.walk_mut_binders(
46 &mut |ty_mut, binders| {
47 let ty = mem::replace(ty_mut, TyKind::Error.intern(&Interner));
48 *ty_mut = f(ty, binders);
49 },
50 binders,
51 );
52 self
53 }
54
55 fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self
56 where
57 Self: Sized,
58 {
59 self.walk_mut(&mut |ty_mut| {
60 let ty = mem::replace(ty_mut, TyKind::Error.intern(&Interner));
61 *ty_mut = f(ty);
62 });
63 self
64 }
65
66 /// Substitutes `TyKind::Bound` vars with the given substitution.
67 fn subst_bound_vars(self, substs: &Substitution) -> Self
68 where
69 Self: Sized,
70 {
71 self.subst_bound_vars_at_depth(substs, DebruijnIndex::INNERMOST)
72 }
73
74 /// Substitutes `TyKind::Bound` vars with the given substitution.
75 fn subst_bound_vars_at_depth(mut self, substs: &Substitution, depth: DebruijnIndex) -> Self
76 where
77 Self: Sized,
78 {
79 self.walk_mut_binders(
80 &mut |ty, binders| {
81 if let &mut TyKind::BoundVar(bound) = ty.interned_mut() {
82 if bound.debruijn >= binders {
83 *ty = substs.interned()[bound.index]
84 .assert_ty_ref(&Interner)
85 .clone()
86 .shifted_in_from(binders);
87 }
88 }
89 },
90 depth,
91 );
92 self
93 }
94
95 fn shifted_in(self, _interner: &Interner) -> Self
96 where
97 Self: Sized,
98 {
99 self.shifted_in_from(DebruijnIndex::ONE)
100 }
101
102 /// Shifts up debruijn indices of `TyKind::Bound` vars by `n`.
103 fn shifted_in_from(self, n: DebruijnIndex) -> Self
104 where
105 Self: Sized,
106 {
107 self.fold_binders(
108 &mut |ty, binders| match ty.kind(&Interner) {
109 TyKind::BoundVar(bound) if bound.debruijn >= binders => {
110 TyKind::BoundVar(bound.shifted_in_from(n)).intern(&Interner)
111 }
112 _ => ty,
113 },
114 DebruijnIndex::INNERMOST,
115 )
116 }
117
118 /// Shifts debruijn indices of `TyKind::Bound` vars out (down) by `n`.
119 fn shifted_out_to(self, n: DebruijnIndex) -> Option<Self>
120 where
121 Self: Sized + std::fmt::Debug,
122 {
123 Some(self.fold_binders(
124 &mut |ty, binders| {
125 match ty.kind(&Interner) {
126 TyKind::BoundVar(bound) if bound.debruijn >= binders => {
127 TyKind::BoundVar(bound.shifted_out_to(n).unwrap_or(bound.clone()))
128 .intern(&Interner)
129 }
130 _ => ty,
131 }
132 },
133 DebruijnIndex::INNERMOST,
134 ))
135 }
136} 15}
137 16
138impl TypeWalk for Ty { 17impl TypeWalk for Ty {
@@ -174,45 +53,6 @@ impl TypeWalk for Ty {
174 } 53 }
175 f(self); 54 f(self);
176 } 55 }
177
178 fn walk_mut_binders(
179 &mut self,
180 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
181 binders: DebruijnIndex,
182 ) {
183 match self.interned_mut() {
184 TyKind::Alias(AliasTy::Projection(p_ty)) => {
185 p_ty.substitution.walk_mut_binders(f, binders);
186 }
187 TyKind::Dyn(dyn_ty) => {
188 for p in make_mut_slice(dyn_ty.bounds.skip_binders_mut().interned_mut()) {
189 p.walk_mut_binders(f, binders.shifted_in());
190 }
191 }
192 TyKind::Alias(AliasTy::Opaque(o_ty)) => {
193 o_ty.substitution.walk_mut_binders(f, binders);
194 }
195 TyKind::Slice(ty)
196 | TyKind::Array(ty, _)
197 | TyKind::Ref(_, _, ty)
198 | TyKind::Raw(_, ty) => {
199 ty.walk_mut_binders(f, binders);
200 }
201 TyKind::Function(fn_pointer) => {
202 fn_pointer.substitution.0.walk_mut_binders(f, binders.shifted_in());
203 }
204 TyKind::Adt(_, substs)
205 | TyKind::FnDef(_, substs)
206 | TyKind::Tuple(_, substs)
207 | TyKind::OpaqueType(_, substs)
208 | TyKind::AssociatedType(_, substs)
209 | TyKind::Closure(.., substs) => {
210 substs.walk_mut_binders(f, binders);
211 }
212 _ => {}
213 }
214 f(self, binders);
215 }
216} 56}
217 57
218impl<T: TypeWalk> TypeWalk for Vec<T> { 58impl<T: TypeWalk> TypeWalk for Vec<T> {
@@ -221,43 +61,18 @@ impl<T: TypeWalk> TypeWalk for Vec<T> {
221 t.walk(f); 61 t.walk(f);
222 } 62 }
223 } 63 }
224 fn walk_mut_binders(
225 &mut self,
226 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
227 binders: DebruijnIndex,
228 ) {
229 for t in self {
230 t.walk_mut_binders(f, binders);
231 }
232 }
233} 64}
234 65
235impl TypeWalk for OpaqueTy { 66impl TypeWalk for OpaqueTy {
236 fn walk(&self, f: &mut impl FnMut(&Ty)) { 67 fn walk(&self, f: &mut impl FnMut(&Ty)) {
237 self.substitution.walk(f); 68 self.substitution.walk(f);
238 } 69 }
239
240 fn walk_mut_binders(
241 &mut self,
242 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
243 binders: DebruijnIndex,
244 ) {
245 self.substitution.walk_mut_binders(f, binders);
246 }
247} 70}
248 71
249impl TypeWalk for ProjectionTy { 72impl TypeWalk for ProjectionTy {
250 fn walk(&self, f: &mut impl FnMut(&Ty)) { 73 fn walk(&self, f: &mut impl FnMut(&Ty)) {
251 self.substitution.walk(f); 74 self.substitution.walk(f);
252 } 75 }
253
254 fn walk_mut_binders(
255 &mut self,
256 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
257 binders: DebruijnIndex,
258 ) {
259 self.substitution.walk_mut_binders(f, binders);
260 }
261} 76}
262 77
263impl TypeWalk for AliasTy { 78impl TypeWalk for AliasTy {
@@ -267,17 +82,6 @@ impl TypeWalk for AliasTy {
267 AliasTy::Opaque(it) => it.walk(f), 82 AliasTy::Opaque(it) => it.walk(f),
268 } 83 }
269 } 84 }
270
271 fn walk_mut_binders(
272 &mut self,
273 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
274 binders: DebruijnIndex,
275 ) {
276 match self {
277 AliasTy::Projection(it) => it.walk_mut_binders(f, binders),
278 AliasTy::Opaque(it) => it.walk_mut_binders(f, binders),
279 }
280 }
281} 85}
282 86
283impl TypeWalk for GenericArg { 87impl TypeWalk for GenericArg {
@@ -286,18 +90,7 @@ impl TypeWalk for GenericArg {
286 GenericArgData::Ty(ty) => { 90 GenericArgData::Ty(ty) => {
287 ty.walk(f); 91 ty.walk(f);
288 } 92 }
289 } 93 _ => {}
290 }
291
292 fn walk_mut_binders(
293 &mut self,
294 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
295 binders: DebruijnIndex,
296 ) {
297 match self.interned_mut() {
298 GenericArgData::Ty(ty) => {
299 ty.walk_mut_binders(f, binders);
300 }
301 } 94 }
302 } 95 }
303} 96}
@@ -308,44 +101,18 @@ impl TypeWalk for Substitution {
308 t.walk(f); 101 t.walk(f);
309 } 102 }
310 } 103 }
311
312 fn walk_mut_binders(
313 &mut self,
314 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
315 binders: DebruijnIndex,
316 ) {
317 for t in self.interned_mut() {
318 t.walk_mut_binders(f, binders);
319 }
320 }
321} 104}
322 105
323impl<T: TypeWalk> TypeWalk for Binders<T> { 106impl<T: TypeWalk + HasInterner<Interner = Interner>> TypeWalk for Binders<T> {
324 fn walk(&self, f: &mut impl FnMut(&Ty)) { 107 fn walk(&self, f: &mut impl FnMut(&Ty)) {
325 self.skip_binders().walk(f); 108 self.skip_binders().walk(f);
326 } 109 }
327
328 fn walk_mut_binders(
329 &mut self,
330 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
331 binders: DebruijnIndex,
332 ) {
333 self.skip_binders_mut().walk_mut_binders(f, binders.shifted_in())
334 }
335} 110}
336 111
337impl TypeWalk for TraitRef { 112impl TypeWalk for TraitRef {
338 fn walk(&self, f: &mut impl FnMut(&Ty)) { 113 fn walk(&self, f: &mut impl FnMut(&Ty)) {
339 self.substitution.walk(f); 114 self.substitution.walk(f);
340 } 115 }
341
342 fn walk_mut_binders(
343 &mut self,
344 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
345 binders: DebruijnIndex,
346 ) {
347 self.substitution.walk_mut_binders(f, binders);
348 }
349} 116}
350 117
351impl TypeWalk for WhereClause { 118impl TypeWalk for WhereClause {
@@ -353,17 +120,7 @@ impl TypeWalk for WhereClause {
353 match self { 120 match self {
354 WhereClause::Implemented(trait_ref) => trait_ref.walk(f), 121 WhereClause::Implemented(trait_ref) => trait_ref.walk(f),
355 WhereClause::AliasEq(alias_eq) => alias_eq.walk(f), 122 WhereClause::AliasEq(alias_eq) => alias_eq.walk(f),
356 } 123 _ => {}
357 }
358
359 fn walk_mut_binders(
360 &mut self,
361 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
362 binders: DebruijnIndex,
363 ) {
364 match self {
365 WhereClause::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders),
366 WhereClause::AliasEq(alias_eq) => alias_eq.walk_mut_binders(f, binders),
367 } 124 }
368 } 125 }
369} 126}
@@ -374,16 +131,6 @@ impl TypeWalk for CallableSig {
374 t.walk(f); 131 t.walk(f);
375 } 132 }
376 } 133 }
377
378 fn walk_mut_binders(
379 &mut self,
380 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
381 binders: DebruijnIndex,
382 ) {
383 for t in make_mut_slice(&mut self.params_and_return) {
384 t.walk_mut_binders(f, binders);
385 }
386 }
387} 134}
388 135
389impl TypeWalk for AliasEq { 136impl TypeWalk for AliasEq {
@@ -394,30 +141,10 @@ impl TypeWalk for AliasEq {
394 AliasTy::Opaque(opaque) => opaque.walk(f), 141 AliasTy::Opaque(opaque) => opaque.walk(f),
395 } 142 }
396 } 143 }
397
398 fn walk_mut_binders(
399 &mut self,
400 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
401 binders: DebruijnIndex,
402 ) {
403 self.ty.walk_mut_binders(f, binders);
404 match &mut self.alias {
405 AliasTy::Projection(projection_ty) => projection_ty.walk_mut_binders(f, binders),
406 AliasTy::Opaque(opaque) => opaque.walk_mut_binders(f, binders),
407 }
408 }
409} 144}
410 145
411impl TypeWalk for FnSubst { 146impl TypeWalk for FnSubst<Interner> {
412 fn walk(&self, f: &mut impl FnMut(&Ty)) { 147 fn walk(&self, f: &mut impl FnMut(&Ty)) {
413 self.0.walk(f) 148 self.0.walk(f)
414 } 149 }
415
416 fn walk_mut_binders(
417 &mut self,
418 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
419 binders: DebruijnIndex,
420 ) {
421 self.0.walk_mut_binders(f, binders)
422 }
423} 150}
diff --git a/crates/rust-analyzer/Cargo.toml b/crates/rust-analyzer/Cargo.toml
index 3130785cc..0571a912c 100644
--- a/crates/rust-analyzer/Cargo.toml
+++ b/crates/rust-analyzer/Cargo.toml
@@ -22,7 +22,7 @@ env_logger = { version = "0.8.1", default-features = false }
22itertools = "0.10.0" 22itertools = "0.10.0"
23jod-thread = "0.1.0" 23jod-thread = "0.1.0"
24log = "0.4.8" 24log = "0.4.8"
25lsp-types = { version = "0.88.0", features = ["proposed"] } 25lsp-types = { version = "0.89.0", features = ["proposed"] }
26parking_lot = "0.11.0" 26parking_lot = "0.11.0"
27xflags = "0.2.1" 27xflags = "0.2.1"
28oorandom = "11.1.2" 28oorandom = "11.1.2"