From b9c0c2abb79769852119dc9a595e63ee74eeba03 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sat, 20 Apr 2019 12:34:36 +0200 Subject: Chalk integration - add proper canonicalization logic - add conversions from/to Chalk IR --- crates/ra_hir/Cargo.toml | 9 +- crates/ra_hir/src/code_model_api.rs | 6 +- crates/ra_hir/src/db.rs | 26 +- crates/ra_hir/src/generics.rs | 11 +- crates/ra_hir/src/ids.rs | 54 ++++ crates/ra_hir/src/resolve.rs | 3 +- crates/ra_hir/src/ty.rs | 49 ++- crates/ra_hir/src/ty/infer.rs | 31 +- crates/ra_hir/src/ty/infer/unify.rs | 81 +++++ crates/ra_hir/src/ty/lower.rs | 30 +- crates/ra_hir/src/ty/method_resolution.rs | 29 +- crates/ra_hir/src/ty/tests.rs | 2 +- crates/ra_hir/src/ty/traits.rs | 493 ++++++++++++++++++++++++------ 13 files changed, 677 insertions(+), 147 deletions(-) create mode 100644 crates/ra_hir/src/ty/infer/unify.rs (limited to 'crates/ra_hir') 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" } mbe = { path = "../ra_mbe", package = "ra_mbe" } tt = { path = "../ra_tt", package = "ra_tt" } test_utils = { path = "../test_utils" } -ra_prof = {path = "../ra_prof" } +ra_prof = { path = "../ra_prof" } + +# chalk-solve = { git = "https://github.com/rust-lang/chalk.git" } +# chalk-rust-ir = { git = "https://github.com/rust-lang/chalk.git" } +# chalk-ir = { git = "https://github.com/rust-lang/chalk.git" } +chalk-solve = { git = "https://github.com/detrumi/chalk.git", branch = "program_clauses_that_could_match" } +chalk-rust-ir = { git = "https://github.com/detrumi/chalk.git", branch = "program_clauses_that_could_match" } +chalk-ir = { git = "https://github.com/detrumi/chalk.git", branch = "program_clauses_that_could_match" } [dev-dependencies] 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::{ type_ref::TypeRef, nameres::{ModuleScope, Namespace, ImportId, CrateModuleId}, expr::{Body, BodySourceMap}, - ty::InferenceResult, + ty::{ TraitRef, InferenceResult}, adt::{EnumVariantId, StructFieldId, VariantDef}, generics::HasGenericParams, docs::{Documentation, Docs, docs_from_ast}, @@ -696,6 +696,10 @@ impl Trait { db.trait_data(self) } + pub fn trait_ref(self, db: &impl HirDatabase) -> TraitRef { + TraitRef::for_trait(db, self) + } + pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver { let r = self.module(db).resolver(db); // 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 @@ -use std::sync::Arc; +use std::sync::{Arc, Mutex}; use ra_syntax::{SyntaxNode, TreeArc, SourceFile, SmolStr, ast}; use ra_db::{SourceDatabase, salsa}; @@ -8,16 +8,16 @@ use crate::{ Function, FnSignature, ExprScopes, TypeAlias, Struct, Enum, StructField, Const, ConstSignature, Static, - DefWithBody, + DefWithBody, Trait, + ids, nameres::{Namespace, ImportSourceMap, RawItems, CrateDefMap}, - ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef, CallableDef, FnSig}, + ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef, CallableDef, FnSig, TypeCtor}, adt::{StructData, EnumData}, - impl_block::{ModuleImplBlocks, ImplSourceMap}, + impl_block::{ModuleImplBlocks, ImplSourceMap, ImplBlock}, generics::{GenericParams, GenericDef}, type_ref::TypeRef, - traits::TraitData, Trait, ty::TraitRef, + traits::TraitData, lang_item::{LangItems, LangItemTarget}, - ids }; #[salsa::query_group(DefDatabaseStorage)] @@ -39,6 +39,12 @@ pub trait DefDatabase: SourceDatabase { #[salsa::interned] fn intern_type_alias(&self, loc: ids::ItemLoc) -> ids::TypeAliasId; + // Interned IDs for Chalk integration + #[salsa::interned] + fn intern_type_ctor(&self, type_ctor: TypeCtor) -> ids::TypeCtorId; + #[salsa::interned] + fn intern_impl_block(&self, impl_block: ImplBlock) -> ids::GlobalImplId; + #[salsa::invoke(crate::ids::macro_def_query)] fn macro_def(&self, macro_id: MacroDefId) -> Option>; @@ -144,8 +150,12 @@ pub trait HirDatabase: DefDatabase { #[salsa::invoke(crate::ty::method_resolution::CrateImplBlocks::impls_in_crate_query)] fn impls_in_crate(&self, krate: Crate) -> Arc; - #[salsa::invoke(crate::ty::traits::implements)] - fn implements(&self, trait_ref: TraitRef) -> Option; + #[salsa::invoke(crate::ty::traits::impls_for_trait)] + fn impls_for_trait(&self, krate: Crate, trait_: Trait) -> Arc<[ImplBlock]>; + + #[salsa::invoke(crate::ty::traits::solver)] + #[salsa::volatile] + fn chalk_solver(&self, krate: Crate) -> Arc>; } #[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}; use crate::{ db::DefDatabase, - Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock, Container, path::Path, type_ref::TypeRef + Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock, Container, path::Path, type_ref::TypeRef, AdtDef }; /// Data about a generic parameter (to a function, struct, impl, ...). @@ -157,6 +157,15 @@ impl From for GenericDef { } } +impl From for GenericDef { + fn from(adt: crate::adt::AdtDef) -> Self { + match adt { + AdtDef::Struct(s) => s.into(), + AdtDef::Enum(e) => e.into(), + } + } +} + pub trait HasGenericParams { fn generic_params(self, db: &impl DefDatabase) -> Arc; } 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 for TraitId { } } +fn from_chalk(chalk_id: chalk_ir::RawId) -> T { + T::from_intern_id(salsa::InternId::from(chalk_id.index)) +} +fn to_chalk(salsa_id: T) -> chalk_ir::RawId { + chalk_ir::RawId { index: salsa_id.as_intern_id().as_u32() } +} + +impl From for TraitId { + fn from(trait_id: chalk_ir::TraitId) -> Self { + from_chalk(trait_id.0) + } +} + +impl From for chalk_ir::TraitId { + fn from(trait_id: TraitId) -> Self { + chalk_ir::TraitId(to_chalk(trait_id)) + } +} + #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] pub struct TypeAliasId(salsa::InternId); impl_intern_key!(TypeAliasId); @@ -354,3 +373,38 @@ impl MacroCallId { ) } } + +/// This exists just for chalk, because chalk doesn't differentiate between +/// enums and structs. +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +pub struct TypeCtorId(salsa::InternId); +impl_intern_key!(TypeCtorId); + +impl From for TypeCtorId { + fn from(struct_id: chalk_ir::StructId) -> Self { + from_chalk(struct_id.0) + } +} + +impl From for chalk_ir::StructId { + fn from(adt_id: TypeCtorId) -> Self { + chalk_ir::StructId(to_chalk(adt_id)) + } +} + +/// This exists just for chalk, because our ImplIds are only unique per module. +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +pub struct GlobalImplId(salsa::InternId); +impl_intern_key!(GlobalImplId); + +impl From for GlobalImplId { + fn from(impl_id: chalk_ir::ImplId) -> Self { + from_chalk(impl_id.0) + } +} + +impl From for chalk_ir::ImplId { + fn from(impl_id: GlobalImplId) -> Self { + chalk_ir::ImplId(to_chalk(impl_id)) + } +} 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; use rustc_hash::FxHashMap; use crate::{ - ModuleDef, + ModuleDef, Trait, code_model_api::Crate, MacroCallId, MacroCallLoc, @@ -18,7 +18,6 @@ use crate::{ expr::{scope::{ExprScopes, ScopeId}, PatId}, impl_block::ImplBlock, path::Path, - Trait, }; #[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; use std::sync::Arc; use std::{fmt, mem}; -use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait}; +use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait, GenericParams}; use display::{HirDisplay, HirFormatter}; pub(crate) use lower::{TypableDef, type_for_def, type_for_field, callable_item_sig}; @@ -118,6 +118,7 @@ pub enum Ty { /// surrounding impl, then the current function). idx: u32, /// The name of the parameter, for displaying. + // FIXME get rid of this name: Name, }, @@ -177,6 +178,30 @@ impl Substs { } &self.0[0] } + + /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`). + pub fn identity(generic_params: &GenericParams) -> Substs { + Substs( + generic_params + .params_including_parent() + .into_iter() + .map(|p| Ty::Param { idx: p.idx, name: p.name.clone() }) + .collect::>() + .into(), + ) + } + + /// Return Substs that replace each parameter by a bound variable. + pub fn bound_vars(generic_params: &GenericParams) -> Substs { + Substs( + generic_params + .params_including_parent() + .into_iter() + .map(|p| Ty::Bound(p.idx)) + .collect::>() + .into(), + ) + } } impl From> for Substs { @@ -198,6 +223,14 @@ impl TraitRef { pub fn self_ty(&self) -> &Ty { &self.substs.0[0] } + + pub fn subst(mut self, substs: &Substs) -> TraitRef { + self.substs.walk_mut(&mut |ty_mut| { + let ty = mem::replace(ty_mut, Ty::Unknown); + *ty_mut = ty.subst(substs); + }); + self + } } /// A function signature as seen by type inference: Several parameter types and @@ -376,6 +409,20 @@ impl Ty { }) } + /// Substitutes `Ty::Bound` vars (as opposed to type parameters). + pub fn subst_bound_vars(self, substs: &Substs) -> Ty { + self.fold(&mut |ty| match ty { + Ty::Bound(idx) => { + if (idx as usize) < substs.0.len() { + substs.0[idx as usize].clone() + } else { + Ty::Bound(idx) + } + } + ty => ty, + }) + } + /// Returns the type parameters of this type if it has some (i.e. is an ADT /// or function); so if `self` is `Option`, this returns the `u32`. fn substs(&self) -> Option { 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::{ }; use super::{ Ty, TypableDef, Substs, primitive, op, ApplicationTy, TypeCtor, CallableDef, TraitRef, - traits::{ Solution, Obligation, Guidance}, + traits::{Solution, Obligation, Guidance}, }; +mod unify; + +pub(super) use unify::Canonical; + /// The entry point of type inference. pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc { db.check_canceled(); @@ -321,30 +325,27 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { fn resolve_obligations_as_possible(&mut self) { let obligations = mem::replace(&mut self.obligations, Vec::new()); for obligation in obligations { - // FIXME resolve types in the obligation first - let (solution, var_mapping) = match &obligation { + let mut canonicalizer = self.canonicalizer(); + let solution = match &obligation { Obligation::Trait(tr) => { - let (tr, var_mapping) = super::traits::canonicalize(tr.clone()); - (self.db.implements(tr), var_mapping) + let canonical = canonicalizer.canonicalize_trait_ref(tr.clone()); + super::traits::implements( + canonicalizer.ctx.db, + canonicalizer.ctx.resolver.krate().unwrap(), + canonical, + ) } }; match solution { Some(Solution::Unique(substs)) => { - for (i, subst) in substs.0.iter().enumerate() { - let uncanonical = var_mapping[i]; - // FIXME the subst may contain type variables, which would need to be mapped back as well - self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst); - } + canonicalizer.apply_solution(substs.0); } Some(Solution::Ambig(Guidance::Definite(substs))) => { - for (i, subst) in substs.0.iter().enumerate() { - let uncanonical = var_mapping[i]; - // FIXME the subst may contain type variables, which would need to be mapped back as well - self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst); - } + canonicalizer.apply_solution(substs.0); self.obligations.push(obligation); } Some(_) => { + // FIXME use this when trying to resolve everything at the end self.obligations.push(obligation); } 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 @@ +//! Unification and canonicalization logic. + +use super::{InferenceContext, Ty, TraitRef, InferTy, HirDatabase}; + +impl<'a, D: HirDatabase> InferenceContext<'a, D> { + pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b, D> + where + 'a: 'b, + { + Canonicalizer { ctx: self, free_vars: Vec::new() } + } +} + +// TODO improve the interface of this + +// TODO move further up? +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub(crate) struct Canonical { + pub value: T, + pub num_vars: usize, +} + +pub(super) struct Canonicalizer<'a, 'b, D: HirDatabase> +where + 'a: 'b, +{ + pub ctx: &'b mut InferenceContext<'a, D>, + pub free_vars: Vec, +} + +impl<'a, 'b, D: HirDatabase> Canonicalizer<'a, 'b, D> +where + 'a: 'b, +{ + fn add(&mut self, free_var: InferTy) -> usize { + self.free_vars.iter().position(|&v| v == free_var).unwrap_or_else(|| { + let next_index = self.free_vars.len(); + self.free_vars.push(free_var); + next_index + }) + } + + pub fn canonicalize_ty(&mut self, ty: Ty) -> Canonical { + let value = ty.fold(&mut |ty| match ty { + Ty::Infer(tv) => { + let inner = tv.to_inner(); + // TODO prevent infinite loops? => keep var stack + if let Some(known_ty) = self.ctx.var_unification_table.probe_value(inner).known() { + self.canonicalize_ty(known_ty.clone()).value + } else { + let free_var = InferTy::TypeVar(self.ctx.var_unification_table.find(inner)); + let position = self.add(free_var); + Ty::Bound(position as u32) + } + } + _ => ty, + }); + Canonical { value, num_vars: self.free_vars.len() } + } + + pub fn canonicalize_trait_ref(&mut self, trait_ref: TraitRef) -> Canonical { + let substs = trait_ref + .substs + .0 + .iter() + .map(|ty| self.canonicalize_ty(ty.clone()).value) + .collect::>(); + let value = TraitRef { trait_: trait_ref.trait_, substs: substs.into() }; + Canonical { value, num_vars: self.free_vars.len() } + } + + pub fn apply_solution(&mut self, solution: Canonical>) { + // the solution may contain new variables, which we need to convert to new inference vars + let new_vars = + (0..solution.num_vars).map(|_| self.ctx.new_type_var()).collect::>().into(); + for (i, ty) in solution.value.into_iter().enumerate() { + let var = self.free_vars[i].clone(); + self.ctx.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars)); + } + } +} 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 { let segment = path.segments.last().expect("path should have at least one segment"); substs_from_path_segment(db, resolver, segment, &resolved.generic_params(db), true) } + + pub(crate) fn for_trait(db: &impl HirDatabase, trait_: Trait) -> TraitRef { + let substs = Substs::identity(&trait_.generic_params(db)); + TraitRef { trait_, substs } + } } /// 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 { /// function body. fn type_for_fn(db: &impl HirDatabase, def: Function) -> Ty { let generics = def.generic_params(db); - let substs = make_substs(&generics); + let substs = Substs::identity(&generics); Ty::apply(TypeCtor::FnDef(def.into()), substs) } @@ -341,7 +346,7 @@ fn type_for_struct_constructor(db: &impl HirDatabase, def: Struct) -> Ty { return type_for_struct(db, def); // Unit struct } let generics = def.generic_params(db); - let substs = make_substs(&generics); + let substs = Substs::identity(&generics); Ty::apply(TypeCtor::FnDef(def.into()), substs) } @@ -357,7 +362,7 @@ fn fn_sig_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariant) .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref)) .collect::>(); let generics = def.parent_enum(db).generic_params(db); - let substs = make_substs(&generics); + let substs = Substs::identity(&generics); let ret = type_for_enum(db, def.parent_enum(db)).subst(&substs); FnSig::from_params_and_return(params, ret) } @@ -369,36 +374,25 @@ fn type_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariant) -> return type_for_enum(db, def.parent_enum(db)); // Unit variant } let generics = def.parent_enum(db).generic_params(db); - let substs = make_substs(&generics); + let substs = Substs::identity(&generics); Ty::apply(TypeCtor::FnDef(def.into()), substs) } -fn make_substs(generics: &GenericParams) -> Substs { - Substs( - generics - .params_including_parent() - .into_iter() - .map(|p| Ty::Param { idx: p.idx, name: p.name.clone() }) - .collect::>() - .into(), - ) -} - fn type_for_struct(db: &impl HirDatabase, s: Struct) -> Ty { let generics = s.generic_params(db); - Ty::apply(TypeCtor::Adt(s.into()), make_substs(&generics)) + Ty::apply(TypeCtor::Adt(s.into()), Substs::identity(&generics)) } fn type_for_enum(db: &impl HirDatabase, s: Enum) -> Ty { let generics = s.generic_params(db); - Ty::apply(TypeCtor::Adt(s.into()), make_substs(&generics)) + Ty::apply(TypeCtor::Adt(s.into()), Substs::identity(&generics)) } fn type_for_type_alias(db: &impl HirDatabase, t: TypeAlias) -> Ty { let generics = t.generic_params(db); let resolver = t.resolver(db); let type_ref = t.type_ref(db); - let substs = make_substs(&generics); + let substs = Substs::identity(&generics); let inner = Ty::from_hir(db, &resolver, &type_ref); inner.subst(&substs) } 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::{ generics::HasGenericParams, ty::primitive::{UncertainIntTy, UncertainFloatTy} }; -use super::{TraitRef, Substs}; +use super::{TraitRef, infer::Canonical, Substs}; /// This is used as a key for indexing impls. #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] @@ -183,6 +183,7 @@ impl Ty { name: Option<&Name>, mut callback: impl FnMut(&Ty, Function) -> Option, ) -> Option { + let krate = resolver.krate()?; 'traits: for t in resolver.traits_in_scope() { let data = t.trait_data(db); // we'll be lazy about checking whether the type implements the @@ -195,12 +196,19 @@ impl Ty { let sig = m.signature(db); if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() { if !known_implemented { + // TODO the self type may contain type + // variables, so we need to do proper + // canonicalization here let trait_ref = TraitRef { trait_: t, substs: fresh_substs_for_trait(db, t, self.clone()), }; - let (trait_ref, _) = super::traits::canonicalize(trait_ref); - if db.implements(trait_ref).is_none() { + let canonical = Canonical { + num_vars: trait_ref.substs.len(), + value: trait_ref, + }; + // FIXME cache this implements check (without solution) in a query? + if super::traits::implements(db, krate, canonical).is_none() { continue 'traits; } } @@ -271,15 +279,18 @@ impl Ty { } /// This creates Substs for a trait with the given Self type and type variables -/// for all other parameters. This is kind of a hack since these aren't 'real' -/// type variables; the resulting trait reference is just used for the -/// preliminary method candidate check. +/// for all other parameters, to query Chalk with it. fn fresh_substs_for_trait(db: &impl HirDatabase, tr: Trait, self_ty: Ty) -> Substs { let mut substs = Vec::new(); let generics = tr.generic_params(db); substs.push(self_ty); - substs.extend(generics.params_including_parent().into_iter().skip(1).enumerate().map( - |(i, _p)| Ty::Infer(super::infer::InferTy::TypeVar(super::infer::TypeVarId(i as u32))), - )); + substs.extend( + generics + .params_including_parent() + .into_iter() + .skip(1) + .enumerate() + .map(|(i, _p)| Ty::Bound(i as u32)), + ); substs.into() } 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() { [102; 127) '{ ...d(); }': () [108; 109) 'S': S(T) -> S [108; 115) 'S(1u32)': S -[108; 124) 'S(1u32...thod()': {unknown} +[108; 124) 'S(1u32...thod()': u32 [110; 114) '1u32': u32"### ); } 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 @@ -//! Stuff that will probably mostly replaced by Chalk. -use std::collections::HashMap; +//! Chalk integration. +use std::sync::{Arc, Mutex}; -use crate::{db::HirDatabase, generics::HasGenericParams}; -use super::{TraitRef, Substs, infer::{TypeVarId, InferTy}, Ty}; +use chalk_ir::{TypeId, TraitId, StructId, ImplId, TypeKindId, ProjectionTy, Parameter, Identifier, cast::Cast}; +use chalk_rust_ir::{AssociatedTyDatum, TraitDatum, StructDatum, ImplDatum}; -// Copied (and simplified) from Chalk +use crate::{Crate, Trait, db::HirDatabase, HasGenericParams, ImplBlock}; +use super::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs, infer::Canonical}; -#[derive(Clone, Debug, PartialEq, Eq)] -/// A (possible) solution for a proposed goal. Usually packaged in a `Result`, -/// where `Err` represents definite *failure* to prove a goal. -pub enum Solution { - /// The goal indeed holds, and there is a unique value for all existential - /// variables. - Unique(Substs), +#[derive(Debug, Copy, Clone)] +struct ChalkContext<'a, DB> { + db: &'a DB, + krate: Crate, +} - /// The goal may be provable in multiple ways, but regardless we may have some guidance - /// for type inference. - Ambig(Guidance), +pub(crate) trait ToChalk { + type Chalk; + fn to_chalk(self, db: &impl HirDatabase) -> Self::Chalk; + fn from_chalk(db: &impl HirDatabase, chalk: Self::Chalk) -> Self; } -#[derive(Clone, Debug, PartialEq, Eq)] -/// When a goal holds ambiguously (e.g., because there are multiple possible -/// solutions), we issue a set of *guidance* back to type inference. -pub enum Guidance { - /// The existential variables *must* have the given values if the goal is - /// ever to hold, but that alone isn't enough to guarantee the goal will - /// actually hold. - Definite(Substs), +pub(crate) fn from_chalk(db: &impl HirDatabase, chalk: ChalkT) -> T +where + T: ToChalk, +{ + T::from_chalk(db, chalk) +} - /// There are multiple plausible values for the existentials, but the ones - /// here are suggested as the preferred choice heuristically. These should - /// be used for inference fallback only. - Suggested(Substs), +impl ToChalk for Ty { + type Chalk = chalk_ir::Ty; + fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::Ty { + match self { + Ty::Apply(apply_ty) => chalk_ir::Ty::Apply(apply_ty.to_chalk(db)), + Ty::Param { idx, .. } => { + chalk_ir::PlaceholderIndex { ui: chalk_ir::UniverseIndex::ROOT, idx: idx as usize } + .to_ty() + } + Ty::Bound(idx) => chalk_ir::Ty::BoundVar(idx as usize), + Ty::Infer(_infer_ty) => panic!("uncanonicalized infer ty"), + Ty::Unknown => unimplemented!(), // TODO turn into placeholder? + } + } + fn from_chalk(db: &impl HirDatabase, chalk: chalk_ir::Ty) -> Self { + match chalk { + chalk_ir::Ty::Apply(apply_ty) => { + match apply_ty.name { + // FIXME handle TypeKindId::Trait/Type here + chalk_ir::TypeName::TypeKindId(_) => Ty::Apply(from_chalk(db, apply_ty)), + chalk_ir::TypeName::AssociatedType(_) => unimplemented!(), + chalk_ir::TypeName::Placeholder(idx) => { + assert_eq!(idx.ui, chalk_ir::UniverseIndex::ROOT); + Ty::Param { idx: idx.idx as u32, name: crate::Name::missing() } + } + } + } + chalk_ir::Ty::Projection(_) => unimplemented!(), + chalk_ir::Ty::UnselectedProjection(_) => unimplemented!(), + chalk_ir::Ty::ForAll(_) => unimplemented!(), + chalk_ir::Ty::BoundVar(idx) => Ty::Bound(idx as u32), + chalk_ir::Ty::InferenceVar(_iv) => panic!("unexpected chalk infer ty"), + } + } +} - /// There's no useful information to feed back to type inference - Unknown, +impl ToChalk for ApplicationTy { + type Chalk = chalk_ir::ApplicationTy; + + fn to_chalk(self: ApplicationTy, db: &impl HirDatabase) -> chalk_ir::ApplicationTy { + let struct_id = self.ctor.to_chalk(db); + let name = chalk_ir::TypeName::TypeKindId(struct_id.into()); + let parameters = self.parameters.to_chalk(db); + chalk_ir::ApplicationTy { name, parameters } + } + + fn from_chalk(db: &impl HirDatabase, apply_ty: chalk_ir::ApplicationTy) -> ApplicationTy { + let ctor = match apply_ty.name { + chalk_ir::TypeName::TypeKindId(chalk_ir::TypeKindId::StructId(struct_id)) => { + from_chalk(db, struct_id) + } + chalk_ir::TypeName::TypeKindId(_) => unimplemented!(), + chalk_ir::TypeName::Placeholder(_) => unimplemented!(), + chalk_ir::TypeName::AssociatedType(_) => unimplemented!(), + }; + let parameters = from_chalk(db, apply_ty.parameters); + ApplicationTy { ctor, parameters } + } +} + +impl ToChalk for Substs { + type Chalk = Vec; + + fn to_chalk(self, db: &impl HirDatabase) -> Vec { + self.iter().map(|ty| ty.clone().to_chalk(db).cast()).collect() + } + + fn from_chalk(db: &impl HirDatabase, parameters: Vec) -> Substs { + parameters + .into_iter() + .map(|p| match p { + chalk_ir::Parameter(chalk_ir::ParameterKind::Ty(ty)) => from_chalk(db, ty), + chalk_ir::Parameter(chalk_ir::ParameterKind::Lifetime(_)) => unimplemented!(), + }) + .collect::>() + .into() + } +} + +impl ToChalk for TraitRef { + type Chalk = chalk_ir::TraitRef; + + fn to_chalk(self: TraitRef, db: &impl HirDatabase) -> chalk_ir::TraitRef { + let trait_id = self.trait_.to_chalk(db); + let parameters = self.substs.to_chalk(db); + chalk_ir::TraitRef { trait_id, parameters } + } + + fn from_chalk(db: &impl HirDatabase, trait_ref: chalk_ir::TraitRef) -> Self { + let trait_ = from_chalk(db, trait_ref.trait_id); + let substs = from_chalk(db, trait_ref.parameters); + TraitRef { trait_, substs } + } +} + +impl ToChalk for Trait { + type Chalk = TraitId; + + fn to_chalk(self, _db: &impl HirDatabase) -> TraitId { + self.id.into() + } + + fn from_chalk(_db: &impl HirDatabase, trait_id: TraitId) -> Trait { + Trait { id: trait_id.into() } + } +} + +impl ToChalk for TypeCtor { + type Chalk = chalk_ir::StructId; + + fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::StructId { + db.intern_type_ctor(self).into() + } + + fn from_chalk(db: &impl HirDatabase, struct_id: chalk_ir::StructId) -> TypeCtor { + db.lookup_intern_type_ctor(struct_id.into()) + } +} + +impl ToChalk for ImplBlock { + type Chalk = chalk_ir::ImplId; + + fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::ImplId { + db.intern_impl_block(self).into() + } + + fn from_chalk(db: &impl HirDatabase, impl_id: chalk_ir::ImplId) -> ImplBlock { + db.lookup_intern_impl_block(impl_id.into()) + } +} + +fn make_binders(value: T, num_vars: usize) -> chalk_ir::Binders { + chalk_ir::Binders { + value, + binders: std::iter::repeat(chalk_ir::ParameterKind::Ty(())).take(num_vars).collect(), + } +} + +impl<'a, DB> chalk_solve::RustIrDatabase for ChalkContext<'a, DB> +where + DB: HirDatabase, +{ + fn associated_ty_data(&self, _ty: TypeId) -> Arc { + unimplemented!() + } + fn trait_datum(&self, trait_id: TraitId) -> Arc { + eprintln!("trait_datum {:?}", trait_id); + let trait_: Trait = from_chalk(self.db, trait_id); + let generic_params = trait_.generic_params(self.db); + let bound_vars = Substs::bound_vars(&generic_params); + let trait_ref = trait_.trait_ref(self.db).subst(&bound_vars).to_chalk(self.db); + let flags = chalk_rust_ir::TraitFlags { + // FIXME set these flags correctly + auto: false, + marker: false, + upstream: trait_.module(self.db).krate(self.db) != Some(self.krate), + fundamental: false, + }; + let where_clauses = Vec::new(); // FIXME add where clauses + let trait_datum_bound = chalk_rust_ir::TraitDatumBound { trait_ref, where_clauses, flags }; + let trait_datum = TraitDatum { binders: make_binders(trait_datum_bound, bound_vars.len()) }; + Arc::new(trait_datum) + } + fn struct_datum(&self, struct_id: StructId) -> Arc { + eprintln!("struct_datum {:?}", struct_id); + let type_ctor = from_chalk(self.db, struct_id); + // TODO might be nicer if we can create a fake GenericParams for the TypeCtor + let (num_params, upstream) = match type_ctor { + TypeCtor::Bool + | TypeCtor::Char + | TypeCtor::Int(_) + | TypeCtor::Float(_) + | TypeCtor::Never + | TypeCtor::Str => (0, true), + TypeCtor::Slice | TypeCtor::Array | TypeCtor::RawPtr(_) | TypeCtor::Ref(_) => (1, true), + TypeCtor::FnPtr | TypeCtor::Tuple => unimplemented!(), // FIXME tuples and FnPtr are currently variadic... we need to make the parameter number explicit + TypeCtor::FnDef(_) => unimplemented!(), + TypeCtor::Adt(adt) => { + let generic_params = adt.generic_params(self.db); + ( + generic_params.count_params_including_parent(), + adt.krate(self.db) != Some(self.krate), + ) + } + }; + let flags = chalk_rust_ir::StructFlags { + upstream, + // FIXME set fundamental flag correctly + fundamental: false, + }; + let where_clauses = Vec::new(); // FIXME add where clauses + let ty = ApplicationTy { + ctor: type_ctor, + parameters: (0..num_params).map(|i| Ty::Bound(i as u32)).collect::>().into(), + }; + let struct_datum_bound = chalk_rust_ir::StructDatumBound { + self_ty: ty.to_chalk(self.db), + fields: Vec::new(), // FIXME add fields (only relevant for auto traits) + where_clauses, + flags, + }; + let struct_datum = StructDatum { binders: make_binders(struct_datum_bound, num_params) }; + Arc::new(struct_datum) + } + fn impl_datum(&self, impl_id: ImplId) -> Arc { + eprintln!("impl_datum {:?}", impl_id); + let impl_block: ImplBlock = from_chalk(self.db, impl_id); + let generic_params = impl_block.generic_params(self.db); + let bound_vars = Substs::bound_vars(&generic_params); + let trait_ref = impl_block + .target_trait_ref(self.db) + .expect("FIXME handle unresolved impl block trait ref") + .subst(&bound_vars); + let impl_type = if impl_block.module().krate(self.db) == Some(self.krate) { + chalk_rust_ir::ImplType::Local + } else { + chalk_rust_ir::ImplType::External + }; + let impl_datum_bound = chalk_rust_ir::ImplDatumBound { + // FIXME handle negative impls (impl !Sync for Foo) + trait_ref: chalk_rust_ir::PolarizedTraitRef::Positive(trait_ref.to_chalk(self.db)), + where_clauses: Vec::new(), // FIXME add where clauses + associated_ty_values: Vec::new(), // FIXME add associated type values + impl_type, + }; + let impl_datum = ImplDatum { binders: make_binders(impl_datum_bound, bound_vars.len()) }; + Arc::new(impl_datum) + } + fn impls_for_trait(&self, trait_id: TraitId) -> Vec { + eprintln!("impls_for_trait {:?}", trait_id); + let trait_ = from_chalk(self.db, trait_id); + self.db + .impls_for_trait(self.krate, trait_) + .iter() + // FIXME temporary hack -- as long as we're not lowering where clauses + // correctly, ignore impls with them completely so as to not treat + // impl Trait for T where T: ... as a blanket impl on all types + .filter(|impl_block| impl_block.generic_params(self.db).where_predicates.is_empty()) + .map(|impl_block| impl_block.to_chalk(self.db)) + .collect() + } + fn impl_provided_for(&self, auto_trait_id: TraitId, struct_id: StructId) -> bool { + eprintln!("impl_provided_for {:?}, {:?}", auto_trait_id, struct_id); + false // FIXME + } + fn type_name(&self, _id: TypeKindId) -> Identifier { + unimplemented!() + } + fn split_projection<'p>( + &self, + projection: &'p ProjectionTy, + ) -> (Arc, &'p [Parameter], &'p [Parameter]) { + eprintln!("split_projection {:?}", projection); + unimplemented!() + } +} + +pub(crate) fn solver(_db: &impl HirDatabase, _krate: Crate) -> Arc> { + // krate parameter is just so we cache a unique solver per crate + let solver_choice = chalk_solve::SolverChoice::SLG { max_size: 10 }; + Arc::new(Mutex::new(solver_choice.into_solver())) +} + +/// Collects impls for the given trait in the whole dependency tree of `krate`. +pub(crate) fn impls_for_trait( + db: &impl HirDatabase, + krate: Crate, + trait_: Trait, +) -> Arc<[ImplBlock]> { + let mut impls = Vec::new(); + // We call the query recursively here. On the one hand, this means we can + // reuse results from queries for different crates; on the other hand, this + // will only ever get called for a few crates near the root of the tree (the + // ones the user is editing), so this may actually be a waste of memory. I'm + // doing it like this mainly for simplicity for now. + for dep in krate.dependencies(db) { + impls.extend(db.impls_for_trait(dep.krate, trait_).iter()); + } + let crate_impl_blocks = db.impls_in_crate(krate); + impls.extend(crate_impl_blocks.lookup_impl_blocks_for_trait(&trait_)); + impls.into() +} + +fn solve( + db: &impl HirDatabase, + krate: Crate, + goal: &chalk_ir::UCanonical>, +) -> Option { + let context = ChalkContext { db, krate }; + let solver = db.chalk_solver(krate); + let solution = solver.lock().unwrap().solve(&context, goal); + eprintln!("solve({:?}) => {:?}", goal, solution); + solution } /// Something that needs to be proven (by Chalk) during type checking, e.g. that /// a certain type implements a certain trait. Proving the Obligation might /// result in additional information about inference variables. -/// -/// This might be handled by Chalk when we integrate it? #[derive(Clone, Debug, PartialEq, Eq)] pub enum Obligation { /// Prove that a certain type implements a trait (the type is the `Self` type @@ -49,67 +331,98 @@ pub enum Obligation { Trait(TraitRef), } -/// Rudimentary check whether an impl exists for a given type and trait; this -/// will actually be done by chalk. -pub(crate) fn implements(db: &impl HirDatabase, trait_ref: TraitRef) -> Option { - // FIXME use all trait impls in the whole crate graph - let krate = trait_ref.trait_.module(db).krate(db); - let krate = match krate { - Some(krate) => krate, - None => return None, - }; - let crate_impl_blocks = db.impls_in_crate(krate); - let mut impl_blocks = crate_impl_blocks - .lookup_impl_blocks_for_trait(&trait_ref.trait_) - // we don't handle where clauses at all, waiting for Chalk for that - .filter(|impl_block| impl_block.generic_params(db).where_predicates.is_empty()); - impl_blocks - .find_map(|impl_block| unify_trait_refs(&trait_ref, &impl_block.target_trait_ref(db)?)) -} - -pub(super) fn canonicalize(trait_ref: TraitRef) -> (TraitRef, Vec) { - let mut canonical = HashMap::new(); // mapping uncanonical -> canonical - let mut uncanonical = Vec::new(); // mapping canonical -> uncanonical (which is dense) - let mut substs = trait_ref.substs.0.to_vec(); - for ty in &mut substs { - ty.walk_mut(&mut |ty| match ty { - Ty::Infer(InferTy::TypeVar(tv)) => { - let tv: &mut TypeVarId = tv; - *tv = *canonical.entry(*tv).or_insert_with(|| { - let i = uncanonical.len(); - uncanonical.push(*tv); - TypeVarId(i as u32) - }); - } - _ => {} - }); - } - (TraitRef { substs: substs.into(), ..trait_ref }, uncanonical) +/// Check using Chalk whether trait is implemented for given parameters including `Self` type. +pub(crate) fn implements( + db: &impl HirDatabase, + krate: Crate, + trait_ref: Canonical, +) -> Option { + let goal: chalk_ir::Goal = trait_ref.value.to_chalk(db).cast(); + eprintln!("goal: {:?}", goal); + let env = chalk_ir::Environment::new(); + let in_env = chalk_ir::InEnvironment::new(&env, goal); + let parameter = chalk_ir::ParameterKind::Ty(chalk_ir::UniverseIndex::ROOT); + let canonical = + chalk_ir::Canonical { value: in_env, binders: vec![parameter; trait_ref.num_vars] }; + // We currently don't deal with universes (I think / hope they're not yet + // relevant for our use cases?) + let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 }; + let solution = solve(db, krate, &u_canonical); + solution_from_chalk(db, solution) } -fn unify_trait_refs(tr1: &TraitRef, tr2: &TraitRef) -> Option { - if tr1.trait_ != tr2.trait_ { - return None; - } - let mut solution_substs = Vec::new(); - for (t1, t2) in tr1.substs.0.iter().zip(tr2.substs.0.iter()) { - // this is very bad / hacky 'unification' logic, just enough to make the simple tests pass - match (t1, t2) { - (_, Ty::Infer(InferTy::TypeVar(_))) | (_, Ty::Unknown) | (_, Ty::Param { .. }) => { - // type variable (or similar) in the impl, we just assume it works - } - (Ty::Infer(InferTy::TypeVar(v1)), _) => { - // type variable in the query and fixed type in the impl, record its value - solution_substs.resize_with(v1.0 as usize + 1, || Ty::Unknown); - solution_substs[v1.0 as usize] = t2.clone(); - } - _ => { - // check that they're equal (actually we'd have to recurse etc.) - if t1 != t2 { - return None; - } - } +fn solution_from_chalk( + db: &impl HirDatabase, + solution: Option, +) -> Option { + let convert_subst = |subst: chalk_ir::Canonical| { + let value = subst + .value + .parameters + .into_iter() + .map(|p| { + let ty = match p { + chalk_ir::Parameter(chalk_ir::ParameterKind::Ty(ty)) => from_chalk(db, ty), + chalk_ir::Parameter(chalk_ir::ParameterKind::Lifetime(_)) => unimplemented!(), + }; + ty + }) + .collect(); + let result = Canonical { value, num_vars: subst.binders.len() }; + SolutionVariables(result) + }; + match solution { + Some(chalk_solve::Solution::Unique(constr_subst)) => { + let subst = chalk_ir::Canonical { + value: constr_subst.value.subst, + binders: constr_subst.binders, + }; + Some(Solution::Unique(convert_subst(subst))) + } + Some(chalk_solve::Solution::Ambig(chalk_solve::Guidance::Definite(subst))) => { + Some(Solution::Ambig(Guidance::Definite(convert_subst(subst)))) + } + Some(chalk_solve::Solution::Ambig(chalk_solve::Guidance::Suggested(subst))) => { + Some(Solution::Ambig(Guidance::Suggested(convert_subst(subst)))) } + Some(chalk_solve::Solution::Ambig(chalk_solve::Guidance::Unknown)) => { + Some(Solution::Ambig(Guidance::Unknown)) + } + None => None, } - Some(Solution::Unique(solution_substs.into())) +} + +#[derive(Clone, Debug, PartialEq, Eq)] +pub(crate) struct SolutionVariables(pub Canonical>); + +#[derive(Clone, Debug, PartialEq, Eq)] +/// A (possible) solution for a proposed goal. +pub(crate) enum Solution { + /// The goal indeed holds, and there is a unique value for all existential + /// variables. + Unique(SolutionVariables), + + /// The goal may be provable in multiple ways, but regardless we may have some guidance + /// for type inference. In this case, we don't return any lifetime + /// constraints, since we have not "committed" to any particular solution + /// yet. + Ambig(Guidance), +} + +#[derive(Clone, Debug, PartialEq, Eq)] +/// When a goal holds ambiguously (e.g., because there are multiple possible +/// solutions), we issue a set of *guidance* back to type inference. +pub(crate) enum Guidance { + /// The existential variables *must* have the given values if the goal is + /// ever to hold, but that alone isn't enough to guarantee the goal will + /// actually hold. + Definite(SolutionVariables), + + /// There are multiple plausible values for the existentials, but the ones + /// here are suggested as the preferred choice heuristically. These should + /// be used for inference fallback only. + Suggested(SolutionVariables), + + /// There's no useful information to feed back to type inference + Unknown, } -- cgit v1.2.3