diff options
Diffstat (limited to 'crates/ra_hir')
-rw-r--r-- | crates/ra_hir/Cargo.toml | 9 | ||||
-rw-r--r-- | crates/ra_hir/src/code_model_api.rs | 6 | ||||
-rw-r--r-- | crates/ra_hir/src/db.rs | 26 | ||||
-rw-r--r-- | crates/ra_hir/src/generics.rs | 11 | ||||
-rw-r--r-- | crates/ra_hir/src/ids.rs | 54 | ||||
-rw-r--r-- | crates/ra_hir/src/resolve.rs | 3 | ||||
-rw-r--r-- | crates/ra_hir/src/ty.rs | 49 | ||||
-rw-r--r-- | crates/ra_hir/src/ty/infer.rs | 31 | ||||
-rw-r--r-- | crates/ra_hir/src/ty/infer/unify.rs | 81 | ||||
-rw-r--r-- | crates/ra_hir/src/ty/lower.rs | 30 | ||||
-rw-r--r-- | crates/ra_hir/src/ty/method_resolution.rs | 29 | ||||
-rw-r--r-- | crates/ra_hir/src/ty/tests.rs | 2 | ||||
-rw-r--r-- | crates/ra_hir/src/ty/traits.rs | 493 |
13 files changed, 677 insertions, 147 deletions
diff --git a/crates/ra_hir/Cargo.toml b/crates/ra_hir/Cargo.toml index a2858dad9..ae7e7df62 100644 --- a/crates/ra_hir/Cargo.toml +++ b/crates/ra_hir/Cargo.toml | |||
@@ -19,7 +19,14 @@ ra_db = { path = "../ra_db" } | |||
19 | mbe = { path = "../ra_mbe", package = "ra_mbe" } | 19 | mbe = { path = "../ra_mbe", package = "ra_mbe" } |
20 | tt = { path = "../ra_tt", package = "ra_tt" } | 20 | tt = { path = "../ra_tt", package = "ra_tt" } |
21 | test_utils = { path = "../test_utils" } | 21 | test_utils = { path = "../test_utils" } |
22 | ra_prof = {path = "../ra_prof" } | 22 | ra_prof = { path = "../ra_prof" } |
23 | |||
24 | # chalk-solve = { git = "https://github.com/rust-lang/chalk.git" } | ||
25 | # chalk-rust-ir = { git = "https://github.com/rust-lang/chalk.git" } | ||
26 | # chalk-ir = { git = "https://github.com/rust-lang/chalk.git" } | ||
27 | chalk-solve = { git = "https://github.com/detrumi/chalk.git", branch = "program_clauses_that_could_match" } | ||
28 | chalk-rust-ir = { git = "https://github.com/detrumi/chalk.git", branch = "program_clauses_that_could_match" } | ||
29 | chalk-ir = { git = "https://github.com/detrumi/chalk.git", branch = "program_clauses_that_could_match" } | ||
23 | 30 | ||
24 | [dev-dependencies] | 31 | [dev-dependencies] |
25 | flexi_logger = "0.11.0" | 32 | flexi_logger = "0.11.0" |
diff --git a/crates/ra_hir/src/code_model_api.rs b/crates/ra_hir/src/code_model_api.rs index 8f1ed1086..9dcae50a5 100644 --- a/crates/ra_hir/src/code_model_api.rs +++ b/crates/ra_hir/src/code_model_api.rs | |||
@@ -9,7 +9,7 @@ use crate::{ | |||
9 | type_ref::TypeRef, | 9 | type_ref::TypeRef, |
10 | nameres::{ModuleScope, Namespace, ImportId, CrateModuleId}, | 10 | nameres::{ModuleScope, Namespace, ImportId, CrateModuleId}, |
11 | expr::{Body, BodySourceMap}, | 11 | expr::{Body, BodySourceMap}, |
12 | ty::InferenceResult, | 12 | ty::{ TraitRef, InferenceResult}, |
13 | adt::{EnumVariantId, StructFieldId, VariantDef}, | 13 | adt::{EnumVariantId, StructFieldId, VariantDef}, |
14 | generics::HasGenericParams, | 14 | generics::HasGenericParams, |
15 | docs::{Documentation, Docs, docs_from_ast}, | 15 | docs::{Documentation, Docs, docs_from_ast}, |
@@ -696,6 +696,10 @@ impl Trait { | |||
696 | db.trait_data(self) | 696 | db.trait_data(self) |
697 | } | 697 | } |
698 | 698 | ||
699 | pub fn trait_ref(self, db: &impl HirDatabase) -> TraitRef { | ||
700 | TraitRef::for_trait(db, self) | ||
701 | } | ||
702 | |||
699 | pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver { | 703 | pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver { |
700 | let r = self.module(db).resolver(db); | 704 | let r = self.module(db).resolver(db); |
701 | // add generic params, if present | 705 | // add generic params, if present |
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs index 398e00c42..b2c4fccf2 100644 --- a/crates/ra_hir/src/db.rs +++ b/crates/ra_hir/src/db.rs | |||
@@ -1,4 +1,4 @@ | |||
1 | use std::sync::Arc; | 1 | use std::sync::{Arc, Mutex}; |
2 | 2 | ||
3 | use ra_syntax::{SyntaxNode, TreeArc, SourceFile, SmolStr, ast}; | 3 | use ra_syntax::{SyntaxNode, TreeArc, SourceFile, SmolStr, ast}; |
4 | use ra_db::{SourceDatabase, salsa}; | 4 | use ra_db::{SourceDatabase, salsa}; |
@@ -8,16 +8,16 @@ use crate::{ | |||
8 | Function, FnSignature, ExprScopes, TypeAlias, | 8 | Function, FnSignature, ExprScopes, TypeAlias, |
9 | Struct, Enum, StructField, | 9 | Struct, Enum, StructField, |
10 | Const, ConstSignature, Static, | 10 | Const, ConstSignature, Static, |
11 | DefWithBody, | 11 | DefWithBody, Trait, |
12 | ids, | ||
12 | nameres::{Namespace, ImportSourceMap, RawItems, CrateDefMap}, | 13 | nameres::{Namespace, ImportSourceMap, RawItems, CrateDefMap}, |
13 | ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef, CallableDef, FnSig}, | 14 | ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef, CallableDef, FnSig, TypeCtor}, |
14 | adt::{StructData, EnumData}, | 15 | adt::{StructData, EnumData}, |
15 | impl_block::{ModuleImplBlocks, ImplSourceMap}, | 16 | impl_block::{ModuleImplBlocks, ImplSourceMap, ImplBlock}, |
16 | generics::{GenericParams, GenericDef}, | 17 | generics::{GenericParams, GenericDef}, |
17 | type_ref::TypeRef, | 18 | type_ref::TypeRef, |
18 | traits::TraitData, Trait, ty::TraitRef, | 19 | traits::TraitData, |
19 | lang_item::{LangItems, LangItemTarget}, | 20 | lang_item::{LangItems, LangItemTarget}, |
20 | ids | ||
21 | }; | 21 | }; |
22 | 22 | ||
23 | #[salsa::query_group(DefDatabaseStorage)] | 23 | #[salsa::query_group(DefDatabaseStorage)] |
@@ -39,6 +39,12 @@ pub trait DefDatabase: SourceDatabase { | |||
39 | #[salsa::interned] | 39 | #[salsa::interned] |
40 | fn intern_type_alias(&self, loc: ids::ItemLoc<ast::TypeAliasDef>) -> ids::TypeAliasId; | 40 | fn intern_type_alias(&self, loc: ids::ItemLoc<ast::TypeAliasDef>) -> ids::TypeAliasId; |
41 | 41 | ||
42 | // Interned IDs for Chalk integration | ||
43 | #[salsa::interned] | ||
44 | fn intern_type_ctor(&self, type_ctor: TypeCtor) -> ids::TypeCtorId; | ||
45 | #[salsa::interned] | ||
46 | fn intern_impl_block(&self, impl_block: ImplBlock) -> ids::GlobalImplId; | ||
47 | |||
42 | #[salsa::invoke(crate::ids::macro_def_query)] | 48 | #[salsa::invoke(crate::ids::macro_def_query)] |
43 | fn macro_def(&self, macro_id: MacroDefId) -> Option<Arc<mbe::MacroRules>>; | 49 | fn macro_def(&self, macro_id: MacroDefId) -> Option<Arc<mbe::MacroRules>>; |
44 | 50 | ||
@@ -144,8 +150,12 @@ pub trait HirDatabase: DefDatabase { | |||
144 | #[salsa::invoke(crate::ty::method_resolution::CrateImplBlocks::impls_in_crate_query)] | 150 | #[salsa::invoke(crate::ty::method_resolution::CrateImplBlocks::impls_in_crate_query)] |
145 | fn impls_in_crate(&self, krate: Crate) -> Arc<CrateImplBlocks>; | 151 | fn impls_in_crate(&self, krate: Crate) -> Arc<CrateImplBlocks>; |
146 | 152 | ||
147 | #[salsa::invoke(crate::ty::traits::implements)] | 153 | #[salsa::invoke(crate::ty::traits::impls_for_trait)] |
148 | fn implements(&self, trait_ref: TraitRef) -> Option<crate::ty::traits::Solution>; | 154 | fn impls_for_trait(&self, krate: Crate, trait_: Trait) -> Arc<[ImplBlock]>; |
155 | |||
156 | #[salsa::invoke(crate::ty::traits::solver)] | ||
157 | #[salsa::volatile] | ||
158 | fn chalk_solver(&self, krate: Crate) -> Arc<Mutex<chalk_solve::Solver>>; | ||
149 | } | 159 | } |
150 | 160 | ||
151 | #[test] | 161 | #[test] |
diff --git a/crates/ra_hir/src/generics.rs b/crates/ra_hir/src/generics.rs index 1c71e21ea..2e52c5871 100644 --- a/crates/ra_hir/src/generics.rs +++ b/crates/ra_hir/src/generics.rs | |||
@@ -9,7 +9,7 @@ use ra_syntax::ast::{self, NameOwner, TypeParamsOwner, TypeBoundsOwner}; | |||
9 | 9 | ||
10 | use crate::{ | 10 | use crate::{ |
11 | db::DefDatabase, | 11 | db::DefDatabase, |
12 | Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock, Container, path::Path, type_ref::TypeRef | 12 | Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock, Container, path::Path, type_ref::TypeRef, AdtDef |
13 | }; | 13 | }; |
14 | 14 | ||
15 | /// Data about a generic parameter (to a function, struct, impl, ...). | 15 | /// Data about a generic parameter (to a function, struct, impl, ...). |
@@ -157,6 +157,15 @@ impl From<Container> for GenericDef { | |||
157 | } | 157 | } |
158 | } | 158 | } |
159 | 159 | ||
160 | impl From<crate::adt::AdtDef> for GenericDef { | ||
161 | fn from(adt: crate::adt::AdtDef) -> Self { | ||
162 | match adt { | ||
163 | AdtDef::Struct(s) => s.into(), | ||
164 | AdtDef::Enum(e) => e.into(), | ||
165 | } | ||
166 | } | ||
167 | } | ||
168 | |||
160 | pub trait HasGenericParams { | 169 | pub trait HasGenericParams { |
161 | fn generic_params(self, db: &impl DefDatabase) -> Arc<GenericParams>; | 170 | fn generic_params(self, db: &impl DefDatabase) -> Arc<GenericParams>; |
162 | } | 171 | } |
diff --git a/crates/ra_hir/src/ids.rs b/crates/ra_hir/src/ids.rs index 4102951c9..6875b006d 100644 --- a/crates/ra_hir/src/ids.rs +++ b/crates/ra_hir/src/ids.rs | |||
@@ -323,6 +323,25 @@ impl AstItemDef<ast::TraitDef> for TraitId { | |||
323 | } | 323 | } |
324 | } | 324 | } |
325 | 325 | ||
326 | fn from_chalk<T: salsa::InternKey>(chalk_id: chalk_ir::RawId) -> T { | ||
327 | T::from_intern_id(salsa::InternId::from(chalk_id.index)) | ||
328 | } | ||
329 | fn to_chalk<T: salsa::InternKey>(salsa_id: T) -> chalk_ir::RawId { | ||
330 | chalk_ir::RawId { index: salsa_id.as_intern_id().as_u32() } | ||
331 | } | ||
332 | |||
333 | impl From<chalk_ir::TraitId> for TraitId { | ||
334 | fn from(trait_id: chalk_ir::TraitId) -> Self { | ||
335 | from_chalk(trait_id.0) | ||
336 | } | ||
337 | } | ||
338 | |||
339 | impl From<TraitId> for chalk_ir::TraitId { | ||
340 | fn from(trait_id: TraitId) -> Self { | ||
341 | chalk_ir::TraitId(to_chalk(trait_id)) | ||
342 | } | ||
343 | } | ||
344 | |||
326 | #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] | 345 | #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] |
327 | pub struct TypeAliasId(salsa::InternId); | 346 | pub struct TypeAliasId(salsa::InternId); |
328 | impl_intern_key!(TypeAliasId); | 347 | impl_intern_key!(TypeAliasId); |
@@ -354,3 +373,38 @@ impl MacroCallId { | |||
354 | ) | 373 | ) |
355 | } | 374 | } |
356 | } | 375 | } |
376 | |||
377 | /// This exists just for chalk, because chalk doesn't differentiate between | ||
378 | /// enums and structs. | ||
379 | #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] | ||
380 | pub struct TypeCtorId(salsa::InternId); | ||
381 | impl_intern_key!(TypeCtorId); | ||
382 | |||
383 | impl From<chalk_ir::StructId> for TypeCtorId { | ||
384 | fn from(struct_id: chalk_ir::StructId) -> Self { | ||
385 | from_chalk(struct_id.0) | ||
386 | } | ||
387 | } | ||
388 | |||
389 | impl From<TypeCtorId> for chalk_ir::StructId { | ||
390 | fn from(adt_id: TypeCtorId) -> Self { | ||
391 | chalk_ir::StructId(to_chalk(adt_id)) | ||
392 | } | ||
393 | } | ||
394 | |||
395 | /// This exists just for chalk, because our ImplIds are only unique per module. | ||
396 | #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] | ||
397 | pub struct GlobalImplId(salsa::InternId); | ||
398 | impl_intern_key!(GlobalImplId); | ||
399 | |||
400 | impl From<chalk_ir::ImplId> for GlobalImplId { | ||
401 | fn from(impl_id: chalk_ir::ImplId) -> Self { | ||
402 | from_chalk(impl_id.0) | ||
403 | } | ||
404 | } | ||
405 | |||
406 | impl From<GlobalImplId> for chalk_ir::ImplId { | ||
407 | fn from(impl_id: GlobalImplId) -> Self { | ||
408 | chalk_ir::ImplId(to_chalk(impl_id)) | ||
409 | } | ||
410 | } | ||
diff --git a/crates/ra_hir/src/resolve.rs b/crates/ra_hir/src/resolve.rs index bc9170cdc..707556ef8 100644 --- a/crates/ra_hir/src/resolve.rs +++ b/crates/ra_hir/src/resolve.rs | |||
@@ -6,7 +6,7 @@ use ra_syntax::ast; | |||
6 | use rustc_hash::FxHashMap; | 6 | use rustc_hash::FxHashMap; |
7 | 7 | ||
8 | use crate::{ | 8 | use crate::{ |
9 | ModuleDef, | 9 | ModuleDef, Trait, |
10 | code_model_api::Crate, | 10 | code_model_api::Crate, |
11 | MacroCallId, | 11 | MacroCallId, |
12 | MacroCallLoc, | 12 | MacroCallLoc, |
@@ -18,7 +18,6 @@ use crate::{ | |||
18 | expr::{scope::{ExprScopes, ScopeId}, PatId}, | 18 | expr::{scope::{ExprScopes, ScopeId}, PatId}, |
19 | impl_block::ImplBlock, | 19 | impl_block::ImplBlock, |
20 | path::Path, | 20 | path::Path, |
21 | Trait, | ||
22 | }; | 21 | }; |
23 | 22 | ||
24 | #[derive(Debug, Clone, Default)] | 23 | #[derive(Debug, Clone, Default)] |
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs index 094de62a3..538148956 100644 --- a/crates/ra_hir/src/ty.rs +++ b/crates/ra_hir/src/ty.rs | |||
@@ -15,7 +15,7 @@ pub(crate) mod display; | |||
15 | use std::sync::Arc; | 15 | use std::sync::Arc; |
16 | use std::{fmt, mem}; | 16 | use std::{fmt, mem}; |
17 | 17 | ||
18 | use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait}; | 18 | use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait, GenericParams}; |
19 | use display::{HirDisplay, HirFormatter}; | 19 | use display::{HirDisplay, HirFormatter}; |
20 | 20 | ||
21 | pub(crate) use lower::{TypableDef, type_for_def, type_for_field, callable_item_sig}; | 21 | pub(crate) use lower::{TypableDef, type_for_def, type_for_field, callable_item_sig}; |
@@ -118,6 +118,7 @@ pub enum Ty { | |||
118 | /// surrounding impl, then the current function). | 118 | /// surrounding impl, then the current function). |
119 | idx: u32, | 119 | idx: u32, |
120 | /// The name of the parameter, for displaying. | 120 | /// The name of the parameter, for displaying. |
121 | // FIXME get rid of this | ||
121 | name: Name, | 122 | name: Name, |
122 | }, | 123 | }, |
123 | 124 | ||
@@ -177,6 +178,30 @@ impl Substs { | |||
177 | } | 178 | } |
178 | &self.0[0] | 179 | &self.0[0] |
179 | } | 180 | } |
181 | |||
182 | /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`). | ||
183 | pub fn identity(generic_params: &GenericParams) -> Substs { | ||
184 | Substs( | ||
185 | generic_params | ||
186 | .params_including_parent() | ||
187 | .into_iter() | ||
188 | .map(|p| Ty::Param { idx: p.idx, name: p.name.clone() }) | ||
189 | .collect::<Vec<_>>() | ||
190 | .into(), | ||
191 | ) | ||
192 | } | ||
193 | |||
194 | /// Return Substs that replace each parameter by a bound variable. | ||
195 | pub fn bound_vars(generic_params: &GenericParams) -> Substs { | ||
196 | Substs( | ||
197 | generic_params | ||
198 | .params_including_parent() | ||
199 | .into_iter() | ||
200 | .map(|p| Ty::Bound(p.idx)) | ||
201 | .collect::<Vec<_>>() | ||
202 | .into(), | ||
203 | ) | ||
204 | } | ||
180 | } | 205 | } |
181 | 206 | ||
182 | impl From<Vec<Ty>> for Substs { | 207 | impl From<Vec<Ty>> for Substs { |
@@ -198,6 +223,14 @@ impl TraitRef { | |||
198 | pub fn self_ty(&self) -> &Ty { | 223 | pub fn self_ty(&self) -> &Ty { |
199 | &self.substs.0[0] | 224 | &self.substs.0[0] |
200 | } | 225 | } |
226 | |||
227 | pub fn subst(mut self, substs: &Substs) -> TraitRef { | ||
228 | self.substs.walk_mut(&mut |ty_mut| { | ||
229 | let ty = mem::replace(ty_mut, Ty::Unknown); | ||
230 | *ty_mut = ty.subst(substs); | ||
231 | }); | ||
232 | self | ||
233 | } | ||
201 | } | 234 | } |
202 | 235 | ||
203 | /// A function signature as seen by type inference: Several parameter types and | 236 | /// A function signature as seen by type inference: Several parameter types and |
@@ -376,6 +409,20 @@ impl Ty { | |||
376 | }) | 409 | }) |
377 | } | 410 | } |
378 | 411 | ||
412 | /// Substitutes `Ty::Bound` vars (as opposed to type parameters). | ||
413 | pub fn subst_bound_vars(self, substs: &Substs) -> Ty { | ||
414 | self.fold(&mut |ty| match ty { | ||
415 | Ty::Bound(idx) => { | ||
416 | if (idx as usize) < substs.0.len() { | ||
417 | substs.0[idx as usize].clone() | ||
418 | } else { | ||
419 | Ty::Bound(idx) | ||
420 | } | ||
421 | } | ||
422 | ty => ty, | ||
423 | }) | ||
424 | } | ||
425 | |||
379 | /// Returns the type parameters of this type if it has some (i.e. is an ADT | 426 | /// Returns the type parameters of this type if it has some (i.e. is an ADT |
380 | /// or function); so if `self` is `Option<u32>`, this returns the `u32`. | 427 | /// or function); so if `self` is `Option<u32>`, this returns the `u32`. |
381 | fn substs(&self) -> Option<Substs> { | 428 | fn substs(&self) -> Option<Substs> { |
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs index c7772a7f6..a6d08dbcb 100644 --- a/crates/ra_hir/src/ty/infer.rs +++ b/crates/ra_hir/src/ty/infer.rs | |||
@@ -44,9 +44,13 @@ use crate::{ | |||
44 | }; | 44 | }; |
45 | use super::{ | 45 | use super::{ |
46 | Ty, TypableDef, Substs, primitive, op, ApplicationTy, TypeCtor, CallableDef, TraitRef, | 46 | Ty, TypableDef, Substs, primitive, op, ApplicationTy, TypeCtor, CallableDef, TraitRef, |
47 | traits::{ Solution, Obligation, Guidance}, | 47 | traits::{Solution, Obligation, Guidance}, |
48 | }; | 48 | }; |
49 | 49 | ||
50 | mod unify; | ||
51 | |||
52 | pub(super) use unify::Canonical; | ||
53 | |||
50 | /// The entry point of type inference. | 54 | /// The entry point of type inference. |
51 | pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> { | 55 | pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> { |
52 | db.check_canceled(); | 56 | db.check_canceled(); |
@@ -321,30 +325,27 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
321 | fn resolve_obligations_as_possible(&mut self) { | 325 | fn resolve_obligations_as_possible(&mut self) { |
322 | let obligations = mem::replace(&mut self.obligations, Vec::new()); | 326 | let obligations = mem::replace(&mut self.obligations, Vec::new()); |
323 | for obligation in obligations { | 327 | for obligation in obligations { |
324 | // FIXME resolve types in the obligation first | 328 | let mut canonicalizer = self.canonicalizer(); |
325 | let (solution, var_mapping) = match &obligation { | 329 | let solution = match &obligation { |
326 | Obligation::Trait(tr) => { | 330 | Obligation::Trait(tr) => { |
327 | let (tr, var_mapping) = super::traits::canonicalize(tr.clone()); | 331 | let canonical = canonicalizer.canonicalize_trait_ref(tr.clone()); |
328 | (self.db.implements(tr), var_mapping) | 332 | super::traits::implements( |
333 | canonicalizer.ctx.db, | ||
334 | canonicalizer.ctx.resolver.krate().unwrap(), | ||
335 | canonical, | ||
336 | ) | ||
329 | } | 337 | } |
330 | }; | 338 | }; |
331 | match solution { | 339 | match solution { |
332 | Some(Solution::Unique(substs)) => { | 340 | Some(Solution::Unique(substs)) => { |
333 | for (i, subst) in substs.0.iter().enumerate() { | 341 | canonicalizer.apply_solution(substs.0); |
334 | let uncanonical = var_mapping[i]; | ||
335 | // FIXME the subst may contain type variables, which would need to be mapped back as well | ||
336 | self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst); | ||
337 | } | ||
338 | } | 342 | } |
339 | Some(Solution::Ambig(Guidance::Definite(substs))) => { | 343 | Some(Solution::Ambig(Guidance::Definite(substs))) => { |
340 | for (i, subst) in substs.0.iter().enumerate() { | 344 | canonicalizer.apply_solution(substs.0); |
341 | let uncanonical = var_mapping[i]; | ||
342 | // FIXME the subst may contain type variables, which would need to be mapped back as well | ||
343 | self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst); | ||
344 | } | ||
345 | self.obligations.push(obligation); | 345 | self.obligations.push(obligation); |
346 | } | 346 | } |
347 | Some(_) => { | 347 | Some(_) => { |
348 | // FIXME use this when trying to resolve everything at the end | ||
348 | self.obligations.push(obligation); | 349 | self.obligations.push(obligation); |
349 | } | 350 | } |
350 | None => { | 351 | None => { |
diff --git a/crates/ra_hir/src/ty/infer/unify.rs b/crates/ra_hir/src/ty/infer/unify.rs new file mode 100644 index 000000000..7918b007b --- /dev/null +++ b/crates/ra_hir/src/ty/infer/unify.rs | |||
@@ -0,0 +1,81 @@ | |||
1 | //! Unification and canonicalization logic. | ||
2 | |||
3 | use super::{InferenceContext, Ty, TraitRef, InferTy, HirDatabase}; | ||
4 | |||
5 | impl<'a, D: HirDatabase> InferenceContext<'a, D> { | ||
6 | pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b, D> | ||
7 | where | ||
8 | 'a: 'b, | ||
9 | { | ||
10 | Canonicalizer { ctx: self, free_vars: Vec::new() } | ||
11 | } | ||
12 | } | ||
13 | |||
14 | // TODO improve the interface of this | ||
15 | |||
16 | // TODO move further up? | ||
17 | #[derive(Debug, Clone, PartialEq, Eq, Hash)] | ||
18 | pub(crate) struct Canonical<T> { | ||
19 | pub value: T, | ||
20 | pub num_vars: usize, | ||
21 | } | ||
22 | |||
23 | pub(super) struct Canonicalizer<'a, 'b, D: HirDatabase> | ||
24 | where | ||
25 | 'a: 'b, | ||
26 | { | ||
27 | pub ctx: &'b mut InferenceContext<'a, D>, | ||
28 | pub free_vars: Vec<InferTy>, | ||
29 | } | ||
30 | |||
31 | impl<'a, 'b, D: HirDatabase> Canonicalizer<'a, 'b, D> | ||
32 | where | ||
33 | 'a: 'b, | ||
34 | { | ||
35 | fn add(&mut self, free_var: InferTy) -> usize { | ||
36 | self.free_vars.iter().position(|&v| v == free_var).unwrap_or_else(|| { | ||
37 | let next_index = self.free_vars.len(); | ||
38 | self.free_vars.push(free_var); | ||
39 | next_index | ||
40 | }) | ||
41 | } | ||
42 | |||
43 | pub fn canonicalize_ty(&mut self, ty: Ty) -> Canonical<Ty> { | ||
44 | let value = ty.fold(&mut |ty| match ty { | ||
45 | Ty::Infer(tv) => { | ||
46 | let inner = tv.to_inner(); | ||
47 | // TODO prevent infinite loops? => keep var stack | ||
48 | if let Some(known_ty) = self.ctx.var_unification_table.probe_value(inner).known() { | ||
49 | self.canonicalize_ty(known_ty.clone()).value | ||
50 | } else { | ||
51 | let free_var = InferTy::TypeVar(self.ctx.var_unification_table.find(inner)); | ||
52 | let position = self.add(free_var); | ||
53 | Ty::Bound(position as u32) | ||
54 | } | ||
55 | } | ||
56 | _ => ty, | ||
57 | }); | ||
58 | Canonical { value, num_vars: self.free_vars.len() } | ||
59 | } | ||
60 | |||
61 | pub fn canonicalize_trait_ref(&mut self, trait_ref: TraitRef) -> Canonical<TraitRef> { | ||
62 | let substs = trait_ref | ||
63 | .substs | ||
64 | .0 | ||
65 | .iter() | ||
66 | .map(|ty| self.canonicalize_ty(ty.clone()).value) | ||
67 | .collect::<Vec<_>>(); | ||
68 | let value = TraitRef { trait_: trait_ref.trait_, substs: substs.into() }; | ||
69 | Canonical { value, num_vars: self.free_vars.len() } | ||
70 | } | ||
71 | |||
72 | pub fn apply_solution(&mut self, solution: Canonical<Vec<Ty>>) { | ||
73 | // the solution may contain new variables, which we need to convert to new inference vars | ||
74 | let new_vars = | ||
75 | (0..solution.num_vars).map(|_| self.ctx.new_type_var()).collect::<Vec<_>>().into(); | ||
76 | for (i, ty) in solution.value.into_iter().enumerate() { | ||
77 | let var = self.free_vars[i].clone(); | ||
78 | self.ctx.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars)); | ||
79 | } | ||
80 | } | ||
81 | } | ||
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs index 7fac084ce..2bbd17068 100644 --- a/crates/ra_hir/src/ty/lower.rs +++ b/crates/ra_hir/src/ty/lower.rs | |||
@@ -238,6 +238,11 @@ impl TraitRef { | |||
238 | let segment = path.segments.last().expect("path should have at least one segment"); | 238 | let segment = path.segments.last().expect("path should have at least one segment"); |
239 | substs_from_path_segment(db, resolver, segment, &resolved.generic_params(db), true) | 239 | substs_from_path_segment(db, resolver, segment, &resolved.generic_params(db), true) |
240 | } | 240 | } |
241 | |||
242 | pub(crate) fn for_trait(db: &impl HirDatabase, trait_: Trait) -> TraitRef { | ||
243 | let substs = Substs::identity(&trait_.generic_params(db)); | ||
244 | TraitRef { trait_, substs } | ||
245 | } | ||
241 | } | 246 | } |
242 | 247 | ||
243 | /// Build the declared type of an item. This depends on the namespace; e.g. for | 248 | /// Build the declared type of an item. This depends on the namespace; e.g. for |
@@ -299,7 +304,7 @@ fn fn_sig_for_fn(db: &impl HirDatabase, def: Function) -> FnSig { | |||
299 | /// function body. | 304 | /// function body. |
300 | fn type_for_fn(db: &impl HirDatabase, def: Function) -> Ty { | 305 | fn type_for_fn(db: &impl HirDatabase, def: Function) -> Ty { |
301 | let generics = def.generic_params(db); | 306 | let generics = def.generic_params(db); |
302 | let substs = make_substs(&generics); | 307 | let substs = Substs::identity(&generics); |
303 | Ty::apply(TypeCtor::FnDef(def.into()), substs) | 308 | Ty::apply(TypeCtor::FnDef(def.into()), substs) |
304 | } | 309 | } |
305 | 310 | ||
@@ -341,7 +346,7 @@ fn type_for_struct_constructor(db: &impl HirDatabase, def: Struct) -> Ty { | |||
341 | return type_for_struct(db, def); // Unit struct | 346 | return type_for_struct(db, def); // Unit struct |
342 | } | 347 | } |
343 | let generics = def.generic_params(db); | 348 | let generics = def.generic_params(db); |
344 | let substs = make_substs(&generics); | 349 | let substs = Substs::identity(&generics); |
345 | Ty::apply(TypeCtor::FnDef(def.into()), substs) | 350 | Ty::apply(TypeCtor::FnDef(def.into()), substs) |
346 | } | 351 | } |
347 | 352 | ||
@@ -357,7 +362,7 @@ fn fn_sig_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariant) | |||
357 | .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref)) | 362 | .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref)) |
358 | .collect::<Vec<_>>(); | 363 | .collect::<Vec<_>>(); |
359 | let generics = def.parent_enum(db).generic_params(db); | 364 | let generics = def.parent_enum(db).generic_params(db); |
360 | let substs = make_substs(&generics); | 365 | let substs = Substs::identity(&generics); |
361 | let ret = type_for_enum(db, def.parent_enum(db)).subst(&substs); | 366 | let ret = type_for_enum(db, def.parent_enum(db)).subst(&substs); |
362 | FnSig::from_params_and_return(params, ret) | 367 | FnSig::from_params_and_return(params, ret) |
363 | } | 368 | } |
@@ -369,36 +374,25 @@ fn type_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariant) -> | |||
369 | return type_for_enum(db, def.parent_enum(db)); // Unit variant | 374 | return type_for_enum(db, def.parent_enum(db)); // Unit variant |
370 | } | 375 | } |
371 | let generics = def.parent_enum(db).generic_params(db); | 376 | let generics = def.parent_enum(db).generic_params(db); |
372 | let substs = make_substs(&generics); | 377 | let substs = Substs::identity(&generics); |
373 | Ty::apply(TypeCtor::FnDef(def.into()), substs) | 378 | Ty::apply(TypeCtor::FnDef(def.into()), substs) |
374 | } | 379 | } |
375 | 380 | ||
376 | fn make_substs(generics: &GenericParams) -> Substs { | ||
377 | Substs( | ||
378 | generics | ||
379 | .params_including_parent() | ||
380 | .into_iter() | ||
381 | .map(|p| Ty::Param { idx: p.idx, name: p.name.clone() }) | ||
382 | .collect::<Vec<_>>() | ||
383 | .into(), | ||
384 | ) | ||
385 | } | ||
386 | |||
387 | fn type_for_struct(db: &impl HirDatabase, s: Struct) -> Ty { | 381 | fn type_for_struct(db: &impl HirDatabase, s: Struct) -> Ty { |
388 | let generics = s.generic_params(db); | 382 | let generics = s.generic_params(db); |
389 | Ty::apply(TypeCtor::Adt(s.into()), make_substs(&generics)) | 383 | Ty::apply(TypeCtor::Adt(s.into()), Substs::identity(&generics)) |
390 | } | 384 | } |
391 | 385 | ||
392 | fn type_for_enum(db: &impl HirDatabase, s: Enum) -> Ty { | 386 | fn type_for_enum(db: &impl HirDatabase, s: Enum) -> Ty { |
393 | let generics = s.generic_params(db); | 387 | let generics = s.generic_params(db); |
394 | Ty::apply(TypeCtor::Adt(s.into()), make_substs(&generics)) | 388 | Ty::apply(TypeCtor::Adt(s.into()), Substs::identity(&generics)) |
395 | } | 389 | } |
396 | 390 | ||
397 | fn type_for_type_alias(db: &impl HirDatabase, t: TypeAlias) -> Ty { | 391 | fn type_for_type_alias(db: &impl HirDatabase, t: TypeAlias) -> Ty { |
398 | let generics = t.generic_params(db); | 392 | let generics = t.generic_params(db); |
399 | let resolver = t.resolver(db); | 393 | let resolver = t.resolver(db); |
400 | let type_ref = t.type_ref(db); | 394 | let type_ref = t.type_ref(db); |
401 | let substs = make_substs(&generics); | 395 | let substs = Substs::identity(&generics); |
402 | let inner = Ty::from_hir(db, &resolver, &type_ref); | 396 | let inner = Ty::from_hir(db, &resolver, &type_ref); |
403 | inner.subst(&substs) | 397 | inner.subst(&substs) |
404 | } | 398 | } |
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs index ea6e0dc0f..ea7da0b62 100644 --- a/crates/ra_hir/src/ty/method_resolution.rs +++ b/crates/ra_hir/src/ty/method_resolution.rs | |||
@@ -16,7 +16,7 @@ use crate::{ | |||
16 | generics::HasGenericParams, | 16 | generics::HasGenericParams, |
17 | ty::primitive::{UncertainIntTy, UncertainFloatTy} | 17 | ty::primitive::{UncertainIntTy, UncertainFloatTy} |
18 | }; | 18 | }; |
19 | use super::{TraitRef, Substs}; | 19 | use super::{TraitRef, infer::Canonical, Substs}; |
20 | 20 | ||
21 | /// This is used as a key for indexing impls. | 21 | /// This is used as a key for indexing impls. |
22 | #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] | 22 | #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] |
@@ -183,6 +183,7 @@ impl Ty { | |||
183 | name: Option<&Name>, | 183 | name: Option<&Name>, |
184 | mut callback: impl FnMut(&Ty, Function) -> Option<T>, | 184 | mut callback: impl FnMut(&Ty, Function) -> Option<T>, |
185 | ) -> Option<T> { | 185 | ) -> Option<T> { |
186 | let krate = resolver.krate()?; | ||
186 | 'traits: for t in resolver.traits_in_scope() { | 187 | 'traits: for t in resolver.traits_in_scope() { |
187 | let data = t.trait_data(db); | 188 | let data = t.trait_data(db); |
188 | // we'll be lazy about checking whether the type implements the | 189 | // we'll be lazy about checking whether the type implements the |
@@ -195,12 +196,19 @@ impl Ty { | |||
195 | let sig = m.signature(db); | 196 | let sig = m.signature(db); |
196 | if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() { | 197 | if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() { |
197 | if !known_implemented { | 198 | if !known_implemented { |
199 | // TODO the self type may contain type | ||
200 | // variables, so we need to do proper | ||
201 | // canonicalization here | ||
198 | let trait_ref = TraitRef { | 202 | let trait_ref = TraitRef { |
199 | trait_: t, | 203 | trait_: t, |
200 | substs: fresh_substs_for_trait(db, t, self.clone()), | 204 | substs: fresh_substs_for_trait(db, t, self.clone()), |
201 | }; | 205 | }; |
202 | let (trait_ref, _) = super::traits::canonicalize(trait_ref); | 206 | let canonical = Canonical { |
203 | if db.implements(trait_ref).is_none() { | 207 | num_vars: trait_ref.substs.len(), |
208 | value: trait_ref, | ||
209 | }; | ||
210 | // FIXME cache this implements check (without solution) in a query? | ||
211 | if super::traits::implements(db, krate, canonical).is_none() { | ||
204 | continue 'traits; | 212 | continue 'traits; |
205 | } | 213 | } |
206 | } | 214 | } |
@@ -271,15 +279,18 @@ impl Ty { | |||
271 | } | 279 | } |
272 | 280 | ||
273 | /// This creates Substs for a trait with the given Self type and type variables | 281 | /// This creates Substs for a trait with the given Self type and type variables |
274 | /// for all other parameters. This is kind of a hack since these aren't 'real' | 282 | /// for all other parameters, to query Chalk with it. |
275 | /// type variables; the resulting trait reference is just used for the | ||
276 | /// preliminary method candidate check. | ||
277 | fn fresh_substs_for_trait(db: &impl HirDatabase, tr: Trait, self_ty: Ty) -> Substs { | 283 | fn fresh_substs_for_trait(db: &impl HirDatabase, tr: Trait, self_ty: Ty) -> Substs { |
278 | let mut substs = Vec::new(); | 284 | let mut substs = Vec::new(); |
279 | let generics = tr.generic_params(db); | 285 | let generics = tr.generic_params(db); |
280 | substs.push(self_ty); | 286 | substs.push(self_ty); |
281 | substs.extend(generics.params_including_parent().into_iter().skip(1).enumerate().map( | 287 | substs.extend( |
282 | |(i, _p)| Ty::Infer(super::infer::InferTy::TypeVar(super::infer::TypeVarId(i as u32))), | 288 | generics |
283 | )); | 289 | .params_including_parent() |
290 | .into_iter() | ||
291 | .skip(1) | ||
292 | .enumerate() | ||
293 | .map(|(i, _p)| Ty::Bound(i as u32)), | ||
294 | ); | ||
284 | substs.into() | 295 | substs.into() |
285 | } | 296 | } |
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs index c76a5012f..0aecde37c 100644 --- a/crates/ra_hir/src/ty/tests.rs +++ b/crates/ra_hir/src/ty/tests.rs | |||
@@ -2140,7 +2140,7 @@ fn test() { | |||
2140 | [102; 127) '{ ...d(); }': () | 2140 | [102; 127) '{ ...d(); }': () |
2141 | [108; 109) 'S': S<u32>(T) -> S<T> | 2141 | [108; 109) 'S': S<u32>(T) -> S<T> |
2142 | [108; 115) 'S(1u32)': S<u32> | 2142 | [108; 115) 'S(1u32)': S<u32> |
2143 | [108; 124) 'S(1u32...thod()': {unknown} | 2143 | [108; 124) 'S(1u32...thod()': u32 |
2144 | [110; 114) '1u32': u32"### | 2144 | [110; 114) '1u32': u32"### |
2145 | ); | 2145 | ); |
2146 | } | 2146 | } |
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs index 06f483899..367322ed2 100644 --- a/crates/ra_hir/src/ty/traits.rs +++ b/crates/ra_hir/src/ty/traits.rs | |||
@@ -1,47 +1,329 @@ | |||
1 | //! Stuff that will probably mostly replaced by Chalk. | 1 | //! Chalk integration. |
2 | use std::collections::HashMap; | 2 | use std::sync::{Arc, Mutex}; |
3 | 3 | ||
4 | use crate::{db::HirDatabase, generics::HasGenericParams}; | 4 | use chalk_ir::{TypeId, TraitId, StructId, ImplId, TypeKindId, ProjectionTy, Parameter, Identifier, cast::Cast}; |
5 | use super::{TraitRef, Substs, infer::{TypeVarId, InferTy}, Ty}; | 5 | use chalk_rust_ir::{AssociatedTyDatum, TraitDatum, StructDatum, ImplDatum}; |
6 | 6 | ||
7 | // Copied (and simplified) from Chalk | 7 | use crate::{Crate, Trait, db::HirDatabase, HasGenericParams, ImplBlock}; |
8 | use super::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs, infer::Canonical}; | ||
8 | 9 | ||
9 | #[derive(Clone, Debug, PartialEq, Eq)] | 10 | #[derive(Debug, Copy, Clone)] |
10 | /// A (possible) solution for a proposed goal. Usually packaged in a `Result`, | 11 | struct ChalkContext<'a, DB> { |
11 | /// where `Err` represents definite *failure* to prove a goal. | 12 | db: &'a DB, |
12 | pub enum Solution { | 13 | krate: Crate, |
13 | /// The goal indeed holds, and there is a unique value for all existential | 14 | } |
14 | /// variables. | ||
15 | Unique(Substs), | ||
16 | 15 | ||
17 | /// The goal may be provable in multiple ways, but regardless we may have some guidance | 16 | pub(crate) trait ToChalk { |
18 | /// for type inference. | 17 | type Chalk; |
19 | Ambig(Guidance), | 18 | fn to_chalk(self, db: &impl HirDatabase) -> Self::Chalk; |
19 | fn from_chalk(db: &impl HirDatabase, chalk: Self::Chalk) -> Self; | ||
20 | } | 20 | } |
21 | 21 | ||
22 | #[derive(Clone, Debug, PartialEq, Eq)] | 22 | pub(crate) fn from_chalk<T, ChalkT>(db: &impl HirDatabase, chalk: ChalkT) -> T |
23 | /// When a goal holds ambiguously (e.g., because there are multiple possible | 23 | where |
24 | /// solutions), we issue a set of *guidance* back to type inference. | 24 | T: ToChalk<Chalk = ChalkT>, |
25 | pub enum Guidance { | 25 | { |
26 | /// The existential variables *must* have the given values if the goal is | 26 | T::from_chalk(db, chalk) |
27 | /// ever to hold, but that alone isn't enough to guarantee the goal will | 27 | } |
28 | /// actually hold. | ||
29 | Definite(Substs), | ||
30 | 28 | ||
31 | /// There are multiple plausible values for the existentials, but the ones | 29 | impl ToChalk for Ty { |
32 | /// here are suggested as the preferred choice heuristically. These should | 30 | type Chalk = chalk_ir::Ty; |
33 | /// be used for inference fallback only. | 31 | fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::Ty { |
34 | Suggested(Substs), | 32 | match self { |
33 | Ty::Apply(apply_ty) => chalk_ir::Ty::Apply(apply_ty.to_chalk(db)), | ||
34 | Ty::Param { idx, .. } => { | ||
35 | chalk_ir::PlaceholderIndex { ui: chalk_ir::UniverseIndex::ROOT, idx: idx as usize } | ||
36 | .to_ty() | ||
37 | } | ||
38 | Ty::Bound(idx) => chalk_ir::Ty::BoundVar(idx as usize), | ||
39 | Ty::Infer(_infer_ty) => panic!("uncanonicalized infer ty"), | ||
40 | Ty::Unknown => unimplemented!(), // TODO turn into placeholder? | ||
41 | } | ||
42 | } | ||
43 | fn from_chalk(db: &impl HirDatabase, chalk: chalk_ir::Ty) -> Self { | ||
44 | match chalk { | ||
45 | chalk_ir::Ty::Apply(apply_ty) => { | ||
46 | match apply_ty.name { | ||
47 | // FIXME handle TypeKindId::Trait/Type here | ||
48 | chalk_ir::TypeName::TypeKindId(_) => Ty::Apply(from_chalk(db, apply_ty)), | ||
49 | chalk_ir::TypeName::AssociatedType(_) => unimplemented!(), | ||
50 | chalk_ir::TypeName::Placeholder(idx) => { | ||
51 | assert_eq!(idx.ui, chalk_ir::UniverseIndex::ROOT); | ||
52 | Ty::Param { idx: idx.idx as u32, name: crate::Name::missing() } | ||
53 | } | ||
54 | } | ||
55 | } | ||
56 | chalk_ir::Ty::Projection(_) => unimplemented!(), | ||
57 | chalk_ir::Ty::UnselectedProjection(_) => unimplemented!(), | ||
58 | chalk_ir::Ty::ForAll(_) => unimplemented!(), | ||
59 | chalk_ir::Ty::BoundVar(idx) => Ty::Bound(idx as u32), | ||
60 | chalk_ir::Ty::InferenceVar(_iv) => panic!("unexpected chalk infer ty"), | ||
61 | } | ||
62 | } | ||
63 | } | ||
35 | 64 | ||
36 | /// There's no useful information to feed back to type inference | 65 | impl ToChalk for ApplicationTy { |
37 | Unknown, | 66 | type Chalk = chalk_ir::ApplicationTy; |
67 | |||
68 | fn to_chalk(self: ApplicationTy, db: &impl HirDatabase) -> chalk_ir::ApplicationTy { | ||
69 | let struct_id = self.ctor.to_chalk(db); | ||
70 | let name = chalk_ir::TypeName::TypeKindId(struct_id.into()); | ||
71 | let parameters = self.parameters.to_chalk(db); | ||
72 | chalk_ir::ApplicationTy { name, parameters } | ||
73 | } | ||
74 | |||
75 | fn from_chalk(db: &impl HirDatabase, apply_ty: chalk_ir::ApplicationTy) -> ApplicationTy { | ||
76 | let ctor = match apply_ty.name { | ||
77 | chalk_ir::TypeName::TypeKindId(chalk_ir::TypeKindId::StructId(struct_id)) => { | ||
78 | from_chalk(db, struct_id) | ||
79 | } | ||
80 | chalk_ir::TypeName::TypeKindId(_) => unimplemented!(), | ||
81 | chalk_ir::TypeName::Placeholder(_) => unimplemented!(), | ||
82 | chalk_ir::TypeName::AssociatedType(_) => unimplemented!(), | ||
83 | }; | ||
84 | let parameters = from_chalk(db, apply_ty.parameters); | ||
85 | ApplicationTy { ctor, parameters } | ||
86 | } | ||
87 | } | ||
88 | |||
89 | impl ToChalk for Substs { | ||
90 | type Chalk = Vec<chalk_ir::Parameter>; | ||
91 | |||
92 | fn to_chalk(self, db: &impl HirDatabase) -> Vec<chalk_ir::Parameter> { | ||
93 | self.iter().map(|ty| ty.clone().to_chalk(db).cast()).collect() | ||
94 | } | ||
95 | |||
96 | fn from_chalk(db: &impl HirDatabase, parameters: Vec<chalk_ir::Parameter>) -> Substs { | ||
97 | parameters | ||
98 | .into_iter() | ||
99 | .map(|p| match p { | ||
100 | chalk_ir::Parameter(chalk_ir::ParameterKind::Ty(ty)) => from_chalk(db, ty), | ||
101 | chalk_ir::Parameter(chalk_ir::ParameterKind::Lifetime(_)) => unimplemented!(), | ||
102 | }) | ||
103 | .collect::<Vec<_>>() | ||
104 | .into() | ||
105 | } | ||
106 | } | ||
107 | |||
108 | impl ToChalk for TraitRef { | ||
109 | type Chalk = chalk_ir::TraitRef; | ||
110 | |||
111 | fn to_chalk(self: TraitRef, db: &impl HirDatabase) -> chalk_ir::TraitRef { | ||
112 | let trait_id = self.trait_.to_chalk(db); | ||
113 | let parameters = self.substs.to_chalk(db); | ||
114 | chalk_ir::TraitRef { trait_id, parameters } | ||
115 | } | ||
116 | |||
117 | fn from_chalk(db: &impl HirDatabase, trait_ref: chalk_ir::TraitRef) -> Self { | ||
118 | let trait_ = from_chalk(db, trait_ref.trait_id); | ||
119 | let substs = from_chalk(db, trait_ref.parameters); | ||
120 | TraitRef { trait_, substs } | ||
121 | } | ||
122 | } | ||
123 | |||
124 | impl ToChalk for Trait { | ||
125 | type Chalk = TraitId; | ||
126 | |||
127 | fn to_chalk(self, _db: &impl HirDatabase) -> TraitId { | ||
128 | self.id.into() | ||
129 | } | ||
130 | |||
131 | fn from_chalk(_db: &impl HirDatabase, trait_id: TraitId) -> Trait { | ||
132 | Trait { id: trait_id.into() } | ||
133 | } | ||
134 | } | ||
135 | |||
136 | impl ToChalk for TypeCtor { | ||
137 | type Chalk = chalk_ir::StructId; | ||
138 | |||
139 | fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::StructId { | ||
140 | db.intern_type_ctor(self).into() | ||
141 | } | ||
142 | |||
143 | fn from_chalk(db: &impl HirDatabase, struct_id: chalk_ir::StructId) -> TypeCtor { | ||
144 | db.lookup_intern_type_ctor(struct_id.into()) | ||
145 | } | ||
146 | } | ||
147 | |||
148 | impl ToChalk for ImplBlock { | ||
149 | type Chalk = chalk_ir::ImplId; | ||
150 | |||
151 | fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::ImplId { | ||
152 | db.intern_impl_block(self).into() | ||
153 | } | ||
154 | |||
155 | fn from_chalk(db: &impl HirDatabase, impl_id: chalk_ir::ImplId) -> ImplBlock { | ||
156 | db.lookup_intern_impl_block(impl_id.into()) | ||
157 | } | ||
158 | } | ||
159 | |||
160 | fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T> { | ||
161 | chalk_ir::Binders { | ||
162 | value, | ||
163 | binders: std::iter::repeat(chalk_ir::ParameterKind::Ty(())).take(num_vars).collect(), | ||
164 | } | ||
165 | } | ||
166 | |||
167 | impl<'a, DB> chalk_solve::RustIrDatabase for ChalkContext<'a, DB> | ||
168 | where | ||
169 | DB: HirDatabase, | ||
170 | { | ||
171 | fn associated_ty_data(&self, _ty: TypeId) -> Arc<AssociatedTyDatum> { | ||
172 | unimplemented!() | ||
173 | } | ||
174 | fn trait_datum(&self, trait_id: TraitId) -> Arc<TraitDatum> { | ||
175 | eprintln!("trait_datum {:?}", trait_id); | ||
176 | let trait_: Trait = from_chalk(self.db, trait_id); | ||
177 | let generic_params = trait_.generic_params(self.db); | ||
178 | let bound_vars = Substs::bound_vars(&generic_params); | ||
179 | let trait_ref = trait_.trait_ref(self.db).subst(&bound_vars).to_chalk(self.db); | ||
180 | let flags = chalk_rust_ir::TraitFlags { | ||
181 | // FIXME set these flags correctly | ||
182 | auto: false, | ||
183 | marker: false, | ||
184 | upstream: trait_.module(self.db).krate(self.db) != Some(self.krate), | ||
185 | fundamental: false, | ||
186 | }; | ||
187 | let where_clauses = Vec::new(); // FIXME add where clauses | ||
188 | let trait_datum_bound = chalk_rust_ir::TraitDatumBound { trait_ref, where_clauses, flags }; | ||
189 | let trait_datum = TraitDatum { binders: make_binders(trait_datum_bound, bound_vars.len()) }; | ||
190 | Arc::new(trait_datum) | ||
191 | } | ||
192 | fn struct_datum(&self, struct_id: StructId) -> Arc<StructDatum> { | ||
193 | eprintln!("struct_datum {:?}", struct_id); | ||
194 | let type_ctor = from_chalk(self.db, struct_id); | ||
195 | // TODO might be nicer if we can create a fake GenericParams for the TypeCtor | ||
196 | let (num_params, upstream) = match type_ctor { | ||
197 | TypeCtor::Bool | ||
198 | | TypeCtor::Char | ||
199 | | TypeCtor::Int(_) | ||
200 | | TypeCtor::Float(_) | ||
201 | | TypeCtor::Never | ||
202 | | TypeCtor::Str => (0, true), | ||
203 | TypeCtor::Slice | TypeCtor::Array | TypeCtor::RawPtr(_) | TypeCtor::Ref(_) => (1, true), | ||
204 | TypeCtor::FnPtr | TypeCtor::Tuple => unimplemented!(), // FIXME tuples and FnPtr are currently variadic... we need to make the parameter number explicit | ||
205 | TypeCtor::FnDef(_) => unimplemented!(), | ||
206 | TypeCtor::Adt(adt) => { | ||
207 | let generic_params = adt.generic_params(self.db); | ||
208 | ( | ||
209 | generic_params.count_params_including_parent(), | ||
210 | adt.krate(self.db) != Some(self.krate), | ||
211 | ) | ||
212 | } | ||
213 | }; | ||
214 | let flags = chalk_rust_ir::StructFlags { | ||
215 | upstream, | ||
216 | // FIXME set fundamental flag correctly | ||
217 | fundamental: false, | ||
218 | }; | ||
219 | let where_clauses = Vec::new(); // FIXME add where clauses | ||
220 | let ty = ApplicationTy { | ||
221 | ctor: type_ctor, | ||
222 | parameters: (0..num_params).map(|i| Ty::Bound(i as u32)).collect::<Vec<_>>().into(), | ||
223 | }; | ||
224 | let struct_datum_bound = chalk_rust_ir::StructDatumBound { | ||
225 | self_ty: ty.to_chalk(self.db), | ||
226 | fields: Vec::new(), // FIXME add fields (only relevant for auto traits) | ||
227 | where_clauses, | ||
228 | flags, | ||
229 | }; | ||
230 | let struct_datum = StructDatum { binders: make_binders(struct_datum_bound, num_params) }; | ||
231 | Arc::new(struct_datum) | ||
232 | } | ||
233 | fn impl_datum(&self, impl_id: ImplId) -> Arc<ImplDatum> { | ||
234 | eprintln!("impl_datum {:?}", impl_id); | ||
235 | let impl_block: ImplBlock = from_chalk(self.db, impl_id); | ||
236 | let generic_params = impl_block.generic_params(self.db); | ||
237 | let bound_vars = Substs::bound_vars(&generic_params); | ||
238 | let trait_ref = impl_block | ||
239 | .target_trait_ref(self.db) | ||
240 | .expect("FIXME handle unresolved impl block trait ref") | ||
241 | .subst(&bound_vars); | ||
242 | let impl_type = if impl_block.module().krate(self.db) == Some(self.krate) { | ||
243 | chalk_rust_ir::ImplType::Local | ||
244 | } else { | ||
245 | chalk_rust_ir::ImplType::External | ||
246 | }; | ||
247 | let impl_datum_bound = chalk_rust_ir::ImplDatumBound { | ||
248 | // FIXME handle negative impls (impl !Sync for Foo) | ||
249 | trait_ref: chalk_rust_ir::PolarizedTraitRef::Positive(trait_ref.to_chalk(self.db)), | ||
250 | where_clauses: Vec::new(), // FIXME add where clauses | ||
251 | associated_ty_values: Vec::new(), // FIXME add associated type values | ||
252 | impl_type, | ||
253 | }; | ||
254 | let impl_datum = ImplDatum { binders: make_binders(impl_datum_bound, bound_vars.len()) }; | ||
255 | Arc::new(impl_datum) | ||
256 | } | ||
257 | fn impls_for_trait(&self, trait_id: TraitId) -> Vec<ImplId> { | ||
258 | eprintln!("impls_for_trait {:?}", trait_id); | ||
259 | let trait_ = from_chalk(self.db, trait_id); | ||
260 | self.db | ||
261 | .impls_for_trait(self.krate, trait_) | ||
262 | .iter() | ||
263 | // FIXME temporary hack -- as long as we're not lowering where clauses | ||
264 | // correctly, ignore impls with them completely so as to not treat | ||
265 | // impl<T> Trait for T where T: ... as a blanket impl on all types | ||
266 | .filter(|impl_block| impl_block.generic_params(self.db).where_predicates.is_empty()) | ||
267 | .map(|impl_block| impl_block.to_chalk(self.db)) | ||
268 | .collect() | ||
269 | } | ||
270 | fn impl_provided_for(&self, auto_trait_id: TraitId, struct_id: StructId) -> bool { | ||
271 | eprintln!("impl_provided_for {:?}, {:?}", auto_trait_id, struct_id); | ||
272 | false // FIXME | ||
273 | } | ||
274 | fn type_name(&self, _id: TypeKindId) -> Identifier { | ||
275 | unimplemented!() | ||
276 | } | ||
277 | fn split_projection<'p>( | ||
278 | &self, | ||
279 | projection: &'p ProjectionTy, | ||
280 | ) -> (Arc<AssociatedTyDatum>, &'p [Parameter], &'p [Parameter]) { | ||
281 | eprintln!("split_projection {:?}", projection); | ||
282 | unimplemented!() | ||
283 | } | ||
284 | } | ||
285 | |||
286 | pub(crate) fn solver(_db: &impl HirDatabase, _krate: Crate) -> Arc<Mutex<chalk_solve::Solver>> { | ||
287 | // krate parameter is just so we cache a unique solver per crate | ||
288 | let solver_choice = chalk_solve::SolverChoice::SLG { max_size: 10 }; | ||
289 | Arc::new(Mutex::new(solver_choice.into_solver())) | ||
290 | } | ||
291 | |||
292 | /// Collects impls for the given trait in the whole dependency tree of `krate`. | ||
293 | pub(crate) fn impls_for_trait( | ||
294 | db: &impl HirDatabase, | ||
295 | krate: Crate, | ||
296 | trait_: Trait, | ||
297 | ) -> Arc<[ImplBlock]> { | ||
298 | let mut impls = Vec::new(); | ||
299 | // We call the query recursively here. On the one hand, this means we can | ||
300 | // reuse results from queries for different crates; on the other hand, this | ||
301 | // will only ever get called for a few crates near the root of the tree (the | ||
302 | // ones the user is editing), so this may actually be a waste of memory. I'm | ||
303 | // doing it like this mainly for simplicity for now. | ||
304 | for dep in krate.dependencies(db) { | ||
305 | impls.extend(db.impls_for_trait(dep.krate, trait_).iter()); | ||
306 | } | ||
307 | let crate_impl_blocks = db.impls_in_crate(krate); | ||
308 | impls.extend(crate_impl_blocks.lookup_impl_blocks_for_trait(&trait_)); | ||
309 | impls.into() | ||
310 | } | ||
311 | |||
312 | fn solve( | ||
313 | db: &impl HirDatabase, | ||
314 | krate: Crate, | ||
315 | goal: &chalk_ir::UCanonical<chalk_ir::InEnvironment<chalk_ir::Goal>>, | ||
316 | ) -> Option<chalk_solve::Solution> { | ||
317 | let context = ChalkContext { db, krate }; | ||
318 | let solver = db.chalk_solver(krate); | ||
319 | let solution = solver.lock().unwrap().solve(&context, goal); | ||
320 | eprintln!("solve({:?}) => {:?}", goal, solution); | ||
321 | solution | ||
38 | } | 322 | } |
39 | 323 | ||
40 | /// Something that needs to be proven (by Chalk) during type checking, e.g. that | 324 | /// Something that needs to be proven (by Chalk) during type checking, e.g. that |
41 | /// a certain type implements a certain trait. Proving the Obligation might | 325 | /// a certain type implements a certain trait. Proving the Obligation might |
42 | /// result in additional information about inference variables. | 326 | /// result in additional information about inference variables. |
43 | /// | ||
44 | /// This might be handled by Chalk when we integrate it? | ||
45 | #[derive(Clone, Debug, PartialEq, Eq)] | 327 | #[derive(Clone, Debug, PartialEq, Eq)] |
46 | pub enum Obligation { | 328 | pub enum Obligation { |
47 | /// Prove that a certain type implements a trait (the type is the `Self` type | 329 | /// Prove that a certain type implements a trait (the type is the `Self` type |
@@ -49,67 +331,98 @@ pub enum Obligation { | |||
49 | Trait(TraitRef), | 331 | Trait(TraitRef), |
50 | } | 332 | } |
51 | 333 | ||
52 | /// Rudimentary check whether an impl exists for a given type and trait; this | 334 | /// Check using Chalk whether trait is implemented for given parameters including `Self` type. |
53 | /// will actually be done by chalk. | 335 | pub(crate) fn implements( |
54 | pub(crate) fn implements(db: &impl HirDatabase, trait_ref: TraitRef) -> Option<Solution> { | 336 | db: &impl HirDatabase, |
55 | // FIXME use all trait impls in the whole crate graph | 337 | krate: Crate, |
56 | let krate = trait_ref.trait_.module(db).krate(db); | 338 | trait_ref: Canonical<TraitRef>, |
57 | let krate = match krate { | 339 | ) -> Option<Solution> { |
58 | Some(krate) => krate, | 340 | let goal: chalk_ir::Goal = trait_ref.value.to_chalk(db).cast(); |
59 | None => return None, | 341 | eprintln!("goal: {:?}", goal); |
60 | }; | 342 | let env = chalk_ir::Environment::new(); |
61 | let crate_impl_blocks = db.impls_in_crate(krate); | 343 | let in_env = chalk_ir::InEnvironment::new(&env, goal); |
62 | let mut impl_blocks = crate_impl_blocks | 344 | let parameter = chalk_ir::ParameterKind::Ty(chalk_ir::UniverseIndex::ROOT); |
63 | .lookup_impl_blocks_for_trait(&trait_ref.trait_) | 345 | let canonical = |
64 | // we don't handle where clauses at all, waiting for Chalk for that | 346 | chalk_ir::Canonical { value: in_env, binders: vec![parameter; trait_ref.num_vars] }; |
65 | .filter(|impl_block| impl_block.generic_params(db).where_predicates.is_empty()); | 347 | // We currently don't deal with universes (I think / hope they're not yet |
66 | impl_blocks | 348 | // relevant for our use cases?) |
67 | .find_map(|impl_block| unify_trait_refs(&trait_ref, &impl_block.target_trait_ref(db)?)) | 349 | let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 }; |
68 | } | 350 | let solution = solve(db, krate, &u_canonical); |
69 | 351 | solution_from_chalk(db, solution) | |
70 | pub(super) fn canonicalize(trait_ref: TraitRef) -> (TraitRef, Vec<TypeVarId>) { | ||
71 | let mut canonical = HashMap::new(); // mapping uncanonical -> canonical | ||
72 | let mut uncanonical = Vec::new(); // mapping canonical -> uncanonical (which is dense) | ||
73 | let mut substs = trait_ref.substs.0.to_vec(); | ||
74 | for ty in &mut substs { | ||
75 | ty.walk_mut(&mut |ty| match ty { | ||
76 | Ty::Infer(InferTy::TypeVar(tv)) => { | ||
77 | let tv: &mut TypeVarId = tv; | ||
78 | *tv = *canonical.entry(*tv).or_insert_with(|| { | ||
79 | let i = uncanonical.len(); | ||
80 | uncanonical.push(*tv); | ||
81 | TypeVarId(i as u32) | ||
82 | }); | ||
83 | } | ||
84 | _ => {} | ||
85 | }); | ||
86 | } | ||
87 | (TraitRef { substs: substs.into(), ..trait_ref }, uncanonical) | ||
88 | } | 352 | } |
89 | 353 | ||
90 | fn unify_trait_refs(tr1: &TraitRef, tr2: &TraitRef) -> Option<Solution> { | 354 | fn solution_from_chalk( |
91 | if tr1.trait_ != tr2.trait_ { | 355 | db: &impl HirDatabase, |
92 | return None; | 356 | solution: Option<chalk_solve::Solution>, |
93 | } | 357 | ) -> Option<Solution> { |
94 | let mut solution_substs = Vec::new(); | 358 | let convert_subst = |subst: chalk_ir::Canonical<chalk_ir::Substitution>| { |
95 | for (t1, t2) in tr1.substs.0.iter().zip(tr2.substs.0.iter()) { | 359 | let value = subst |
96 | // this is very bad / hacky 'unification' logic, just enough to make the simple tests pass | 360 | .value |
97 | match (t1, t2) { | 361 | .parameters |
98 | (_, Ty::Infer(InferTy::TypeVar(_))) | (_, Ty::Unknown) | (_, Ty::Param { .. }) => { | 362 | .into_iter() |
99 | // type variable (or similar) in the impl, we just assume it works | 363 | .map(|p| { |
100 | } | 364 | let ty = match p { |
101 | (Ty::Infer(InferTy::TypeVar(v1)), _) => { | 365 | chalk_ir::Parameter(chalk_ir::ParameterKind::Ty(ty)) => from_chalk(db, ty), |
102 | // type variable in the query and fixed type in the impl, record its value | 366 | chalk_ir::Parameter(chalk_ir::ParameterKind::Lifetime(_)) => unimplemented!(), |
103 | solution_substs.resize_with(v1.0 as usize + 1, || Ty::Unknown); | 367 | }; |
104 | solution_substs[v1.0 as usize] = t2.clone(); | 368 | ty |
105 | } | 369 | }) |
106 | _ => { | 370 | .collect(); |
107 | // check that they're equal (actually we'd have to recurse etc.) | 371 | let result = Canonical { value, num_vars: subst.binders.len() }; |
108 | if t1 != t2 { | 372 | SolutionVariables(result) |
109 | return None; | 373 | }; |
110 | } | 374 | match solution { |
111 | } | 375 | Some(chalk_solve::Solution::Unique(constr_subst)) => { |
376 | let subst = chalk_ir::Canonical { | ||
377 | value: constr_subst.value.subst, | ||
378 | binders: constr_subst.binders, | ||
379 | }; | ||
380 | Some(Solution::Unique(convert_subst(subst))) | ||
381 | } | ||
382 | Some(chalk_solve::Solution::Ambig(chalk_solve::Guidance::Definite(subst))) => { | ||
383 | Some(Solution::Ambig(Guidance::Definite(convert_subst(subst)))) | ||
384 | } | ||
385 | Some(chalk_solve::Solution::Ambig(chalk_solve::Guidance::Suggested(subst))) => { | ||
386 | Some(Solution::Ambig(Guidance::Suggested(convert_subst(subst)))) | ||
112 | } | 387 | } |
388 | Some(chalk_solve::Solution::Ambig(chalk_solve::Guidance::Unknown)) => { | ||
389 | Some(Solution::Ambig(Guidance::Unknown)) | ||
390 | } | ||
391 | None => None, | ||
113 | } | 392 | } |
114 | Some(Solution::Unique(solution_substs.into())) | 393 | } |
394 | |||
395 | #[derive(Clone, Debug, PartialEq, Eq)] | ||
396 | pub(crate) struct SolutionVariables(pub Canonical<Vec<Ty>>); | ||
397 | |||
398 | #[derive(Clone, Debug, PartialEq, Eq)] | ||
399 | /// A (possible) solution for a proposed goal. | ||
400 | pub(crate) enum Solution { | ||
401 | /// The goal indeed holds, and there is a unique value for all existential | ||
402 | /// variables. | ||
403 | Unique(SolutionVariables), | ||
404 | |||
405 | /// The goal may be provable in multiple ways, but regardless we may have some guidance | ||
406 | /// for type inference. In this case, we don't return any lifetime | ||
407 | /// constraints, since we have not "committed" to any particular solution | ||
408 | /// yet. | ||
409 | Ambig(Guidance), | ||
410 | } | ||
411 | |||
412 | #[derive(Clone, Debug, PartialEq, Eq)] | ||
413 | /// When a goal holds ambiguously (e.g., because there are multiple possible | ||
414 | /// solutions), we issue a set of *guidance* back to type inference. | ||
415 | pub(crate) enum Guidance { | ||
416 | /// The existential variables *must* have the given values if the goal is | ||
417 | /// ever to hold, but that alone isn't enough to guarantee the goal will | ||
418 | /// actually hold. | ||
419 | Definite(SolutionVariables), | ||
420 | |||
421 | /// There are multiple plausible values for the existentials, but the ones | ||
422 | /// here are suggested as the preferred choice heuristically. These should | ||
423 | /// be used for inference fallback only. | ||
424 | Suggested(SolutionVariables), | ||
425 | |||
426 | /// There's no useful information to feed back to type inference | ||
427 | Unknown, | ||
115 | } | 428 | } |