From 50bbf9eb09dc34781cc34e10bfba5f154e833123 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sun, 5 May 2019 14:21:00 +0200 Subject: Handle where clauses in trait solving --- crates/ra_hir/src/db.rs | 5 ++- crates/ra_hir/src/generics.rs | 19 ++++++++-- crates/ra_hir/src/ty.rs | 31 +++++++++++++++- crates/ra_hir/src/ty/lower.rs | 53 +++++++++++++++++++++++----- crates/ra_hir/src/ty/tests.rs | 41 ++++++++++++++++++++-- crates/ra_hir/src/ty/traits/chalk.rs | 68 +++++++++++++++++++++++++++++------- 6 files changed, 188 insertions(+), 29 deletions(-) diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs index 689dd6225..8f98ca3a5 100644 --- a/crates/ra_hir/src/db.rs +++ b/crates/ra_hir/src/db.rs @@ -11,7 +11,7 @@ use crate::{ DefWithBody, Trait, ids, nameres::{Namespace, ImportSourceMap, RawItems, CrateDefMap}, - ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef, CallableDef, FnSig, TypeCtor}, + ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef, CallableDef, FnSig, TypeCtor, GenericPredicate}, adt::{StructData, EnumData}, impl_block::{ModuleImplBlocks, ImplSourceMap, ImplBlock}, generics::{GenericParams, GenericDef}, @@ -138,6 +138,9 @@ pub trait HirDatabase: DefDatabase { #[salsa::invoke(crate::ty::callable_item_sig)] fn callable_item_signature(&self, def: CallableDef) -> FnSig; + #[salsa::invoke(crate::ty::generic_predicates)] + fn generic_predicates(&self, def: GenericDef) -> Arc<[GenericPredicate]>; + #[salsa::invoke(crate::expr::body_with_source_map_query)] fn body_with_source_map( &self, diff --git a/crates/ra_hir/src/generics.rs b/crates/ra_hir/src/generics.rs index 2e52c5871..826117ba5 100644 --- a/crates/ra_hir/src/generics.rs +++ b/crates/ra_hir/src/generics.rs @@ -8,7 +8,7 @@ use std::sync::Arc; use ra_syntax::ast::{self, NameOwner, TypeParamsOwner, TypeBoundsOwner}; use crate::{ - db::DefDatabase, + db::{ HirDatabase, DefDatabase}, Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock, Container, path::Path, type_ref::TypeRef, AdtDef }; @@ -32,8 +32,8 @@ pub struct GenericParams { /// where clauses like `where T: Foo + Bar` are turned into multiple of these. #[derive(Clone, PartialEq, Eq, Debug)] pub struct WherePredicate { - type_ref: TypeRef, - trait_ref: Path, + pub(crate) type_ref: TypeRef, + pub(crate) trait_ref: Path, } // FIXME: consts can have type parameters from their parents (i.e. associated consts of traits) @@ -148,6 +148,19 @@ impl GenericParams { } } +impl GenericDef { + pub(crate) fn resolver(&self, db: &impl HirDatabase) -> crate::Resolver { + match self { + GenericDef::Function(inner) => inner.resolver(db), + GenericDef::Struct(inner) => inner.resolver(db), + GenericDef::Enum(inner) => inner.resolver(db), + GenericDef::Trait(inner) => inner.resolver(db), + GenericDef::TypeAlias(inner) => inner.resolver(db), + GenericDef::ImplBlock(inner) => inner.resolver(db), + } + } +} + impl From for GenericDef { fn from(c: Container) -> Self { match c { diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs index 12429a668..cfe07156b 100644 --- a/crates/ra_hir/src/ty.rs +++ b/crates/ra_hir/src/ty.rs @@ -19,7 +19,7 @@ use std::{fmt, mem}; 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}; +pub(crate) use lower::{TypableDef, type_for_def, type_for_field, callable_item_sig, generic_predicates}; pub(crate) use infer::{infer, InferenceResult, InferTy}; pub use lower::CallableDef; @@ -234,6 +234,35 @@ impl TraitRef { } } +/// Like `generics::WherePredicate`, but with resolved types: A condition on the +/// parameters of a generic item. +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub enum GenericPredicate { + /// The given trait needs to be implemented for its type parameters. + Implemented(TraitRef), + /// We couldn't resolve the trait reference. (If some type parameters can't + /// be resolved, they will just be Unknown). + Error, +} + +impl GenericPredicate { + pub fn is_error(&self) -> bool { + match self { + GenericPredicate::Error => true, + _ => false, + } + } + + pub fn subst(self, substs: &Substs) -> GenericPredicate { + match self { + GenericPredicate::Implemented(trait_ref) => { + GenericPredicate::Implemented(trait_ref.subst(substs)) + } + GenericPredicate::Error => self, + } + } +} + /// Basically a claim (currently not validated / checked) that the contained /// type / trait ref contains no inference variables; any inference variables it /// contained have been replaced by bound variables, and `num_vars` tells us how diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs index 8bab7e54b..09d26ce5a 100644 --- a/crates/ra_hir/src/ty/lower.rs +++ b/crates/ra_hir/src/ty/lower.rs @@ -5,6 +5,7 @@ //! - Building the type for an item: This happens through the `type_for_def` query. //! //! This usually involves resolving names, collecting generic arguments etc. +use std::sync::Arc; use std::iter; use crate::{ @@ -18,9 +19,9 @@ use crate::{ resolve::{Resolver, Resolution}, path::{PathSegment, GenericArg}, generics::{GenericParams, HasGenericParams}, - adt::VariantDef, Trait + adt::VariantDef, Trait, generics::{ WherePredicate, GenericDef} }; -use super::{Ty, primitive, FnSig, Substs, TypeCtor, TraitRef}; +use super::{Ty, primitive, FnSig, Substs, TypeCtor, TraitRef, GenericPredicate}; impl Ty { pub(crate) fn from_hir(db: &impl HirDatabase, resolver: &Resolver, type_ref: &TypeRef) -> Self { @@ -208,16 +209,12 @@ pub(super) fn substs_from_path_segment( } impl TraitRef { - pub(crate) fn from_hir( + pub(crate) fn from_path( db: &impl HirDatabase, resolver: &Resolver, - type_ref: &TypeRef, + path: &Path, explicit_self_ty: Option, ) -> Option { - let path = match type_ref { - TypeRef::Path(path) => path, - _ => return None, - }; let resolved = match resolver.resolve_path(db, &path).take_types()? { Resolution::Def(ModuleDef::Trait(tr)) => tr, _ => return None, @@ -232,6 +229,19 @@ impl TraitRef { Some(TraitRef { trait_: resolved, substs }) } + pub(crate) fn from_hir( + db: &impl HirDatabase, + resolver: &Resolver, + type_ref: &TypeRef, + explicit_self_ty: Option, + ) -> Option { + let path = match type_ref { + TypeRef::Path(path) => path, + _ => return None, + }; + TraitRef::from_path(db, resolver, path, explicit_self_ty) + } + fn substs_from_path( db: &impl HirDatabase, resolver: &Resolver, @@ -246,6 +256,15 @@ impl TraitRef { let substs = Substs::identity(&trait_.generic_params(db)); TraitRef { trait_, substs } } + + pub(crate) fn for_where_predicate( + db: &impl HirDatabase, + resolver: &Resolver, + pred: &WherePredicate, + ) -> Option { + let self_ty = Ty::from_hir(db, resolver, &pred.type_ref); + TraitRef::from_path(db, resolver, &pred.trait_ref, Some(self_ty)) + } } /// Build the declared type of an item. This depends on the namespace; e.g. for @@ -294,6 +313,24 @@ pub(crate) fn type_for_field(db: &impl HirDatabase, field: StructField) -> Ty { Ty::from_hir(db, &resolver, type_ref) } +/// Resolve the where clause(s) of an item with generics. +pub(crate) fn generic_predicates( + db: &impl HirDatabase, + def: GenericDef, +) -> Arc<[GenericPredicate]> { + let resolver = def.resolver(db); + let generic_params = def.generic_params(db); + let predicates = generic_params + .where_predicates + .iter() + .map(|pred| { + TraitRef::for_where_predicate(db, &resolver, pred) + .map_or(GenericPredicate::Error, GenericPredicate::Implemented) + }) + .collect::>(); + predicates.into() +} + fn fn_sig_for_fn(db: &impl HirDatabase, def: Function) -> FnSig { let signature = def.signature(db); let resolver = def.resolver(db); diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs index a38fe35c7..c3edf42b1 100644 --- a/crates/ra_hir/src/ty/tests.rs +++ b/crates/ra_hir/src/ty/tests.rs @@ -2510,12 +2510,47 @@ fn method_resolution_where_clause_not_met() { trait Clone {} trait Trait { fn foo(self) -> u128; } struct S; -impl S { fn foo(self) -> i8 { 0 } } -impl Trait for T where T: Clone { fn foo(self) -> u128 { 0 } } +impl Trait for T where T: Clone {} fn test() { (&S).foo()<|>; } "#, ); - assert_eq!(t, "i8"); + // This is also to make sure that we don't resolve to the foo method just + // because that's the only method named foo we can find, which would make + // the below tests not work + assert_eq!(t, "{unknown}"); +} + +#[test] +fn method_resolution_where_clause_1() { + let t = type_at( + r#" +//- /main.rs +trait Clone {} +trait Trait { fn foo(self) -> u128; } +struct S; +impl Clone for S {}; +impl Trait for T where T: Clone {} +fn test() { S.foo()<|>; } +"#, + ); + assert_eq!(t, "u128"); +} + +#[test] +fn method_resolution_where_clause_2() { + let t = type_at( + r#" +//- /main.rs +trait Into { fn into(self) -> T; } +trait From { fn from(other: T) -> Self; } +struct S1; +struct S2; +impl From for S1 {}; +impl Into for T where U: From {} +fn test() { S2.into()<|>; } +"#, + ); + assert_eq!(t, "S1"); } fn type_at_pos(db: &MockDatabase, pos: FilePosition) -> String { diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs index 8b77d21b4..2772a0432 100644 --- a/crates/ra_hir/src/ty/traits/chalk.rs +++ b/crates/ra_hir/src/ty/traits/chalk.rs @@ -11,7 +11,7 @@ use ra_db::salsa::{InternId, InternKey}; use crate::{ Trait, HasGenericParams, ImplBlock, db::HirDatabase, - ty::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs}, + ty::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs, GenericPredicate}, generics::GenericDef, }; use super::ChalkContext; @@ -146,6 +146,27 @@ impl ToChalk for ImplBlock { } } +impl ToChalk for GenericPredicate { + type Chalk = chalk_ir::QuantifiedWhereClause; + + fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::QuantifiedWhereClause { + match self { + GenericPredicate::Implemented(trait_ref) => { + make_binders(chalk_ir::WhereClause::Implemented(trait_ref.to_chalk(db)), 0) + } + GenericPredicate::Error => panic!("Trying to pass errored where clause to Chalk"), + } + } + + fn from_chalk( + _db: &impl HirDatabase, + _where_clause: chalk_ir::QuantifiedWhereClause, + ) -> GenericPredicate { + // This should never need to be called + unimplemented!() + } +} + fn make_binders(value: T, num_vars: usize) -> chalk_ir::Binders { chalk_ir::Binders { value, @@ -153,6 +174,25 @@ fn make_binders(value: T, num_vars: usize) -> chalk_ir::Binders { } } +fn convert_where_clauses( + db: &impl HirDatabase, + def: GenericDef, + substs: &Substs, +) -> (Vec, bool) { + let generic_predicates = db.generic_predicates(def); + let mut result = Vec::with_capacity(generic_predicates.len()); + let mut has_error = false; + for pred in generic_predicates.iter() { + // FIXME: it would probably be nicer if we could just convert errored predicates to a where clause that is never true... + if pred.is_error() { + has_error = true; + } else { + result.push(pred.clone().subst(substs).to_chalk(db)); + } + } + (result, has_error) +} + impl<'a, DB> chalk_solve::RustIrDatabase for ChalkContext<'a, DB> where DB: HirDatabase, @@ -173,7 +213,7 @@ where upstream: trait_.module(self.db).krate(self.db) != Some(self.krate), fundamental: false, }; - let where_clauses = Vec::new(); // FIXME add where clauses + let (where_clauses, _) = convert_where_clauses(self.db, trait_.into(), &bound_vars); let associated_ty_ids = Vec::new(); // FIXME add associated tys let trait_datum_bound = chalk_rust_ir::TraitDatumBound { trait_ref, where_clauses, flags, associated_ty_ids }; @@ -185,21 +225,26 @@ where let type_ctor = from_chalk(self.db, struct_id); // FIXME might be nicer if we can create a fake GenericParams for the TypeCtor // FIXME extract this to a method on Ty - let (num_params, upstream) = match type_ctor { + let (num_params, where_clauses, 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 { num_args } => (num_args as usize + 1, true), - TypeCtor::Tuple { cardinality } => (cardinality as usize, true), + | TypeCtor::Str => (0, vec![], true), + TypeCtor::Slice | TypeCtor::Array | TypeCtor::RawPtr(_) | TypeCtor::Ref(_) => { + (1, vec![], true) + } + TypeCtor::FnPtr { num_args } => (num_args as usize + 1, vec![], true), + TypeCtor::Tuple { cardinality } => (cardinality as usize, vec![], true), TypeCtor::FnDef(_) => unimplemented!(), TypeCtor::Adt(adt) => { let generic_params = adt.generic_params(self.db); + let bound_vars = Substs::bound_vars(&generic_params); + let (where_clauses, _) = convert_where_clauses(self.db, adt.into(), &bound_vars); ( generic_params.count_params_including_parent(), + where_clauses, adt.krate(self.db) != Some(self.krate), ) } @@ -209,7 +254,6 @@ where // FIXME set fundamental flag correctly fundamental: false, }; - let where_clauses = Vec::new(); // FIXME add where clauses let self_ty = chalk_ir::ApplicationTy { name: TypeName::TypeKindId(type_ctor.to_chalk(self.db).into()), parameters: (0..num_params).map(|i| chalk_ir::Ty::BoundVar(i).cast()).collect(), @@ -237,10 +281,12 @@ where } else { chalk_rust_ir::ImplType::External }; + let (where_clauses, where_clause_error) = + convert_where_clauses(self.db, impl_block.into(), &bound_vars); 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 + where_clauses, associated_ty_values: Vec::new(), // FIXME add associated type values impl_type, }; @@ -253,10 +299,6 @@ where 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() } -- cgit v1.2.3 From 58b68966bf0e0d5ae5c56e2da1d6def5e0ec0925 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sun, 5 May 2019 14:42:12 +0200 Subject: Handle resolution errors in where clauses This is slightly hacky, but maybe more elegant than alternative solutions: We just use a hardcoded Chalk trait ID which we special-case to have no impls. --- crates/ra_hir/src/ty/tests.rs | 15 ++++++++++ crates/ra_hir/src/ty/traits/chalk.rs | 56 ++++++++++++++++++++++++++---------- 2 files changed, 56 insertions(+), 15 deletions(-) diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs index c3edf42b1..3c55a093f 100644 --- a/crates/ra_hir/src/ty/tests.rs +++ b/crates/ra_hir/src/ty/tests.rs @@ -2501,6 +2501,21 @@ fn test() { (&S).foo()<|>; } assert_eq!(t, "u128"); } +#[test] +fn method_resolution_where_clause_for_unknown_trait() { + // The blanket impl shouldn't apply because we can't even resolve UnknownTrait + let t = type_at( + r#" +//- /main.rs +trait Trait { fn foo(self) -> u128; } +struct S; +impl Trait for T where T: UnknownTrait {} +fn test() { (&S).foo()<|>; } +"#, + ); + assert_eq!(t, "{unknown}"); +} + #[test] fn method_resolution_where_clause_not_met() { // The blanket impl shouldn't apply because we can't prove S: Clone diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs index 2772a0432..787970186 100644 --- a/crates/ra_hir/src/ty/traits/chalk.rs +++ b/crates/ra_hir/src/ty/traits/chalk.rs @@ -15,6 +15,10 @@ use crate::{ }; use super::ChalkContext; +/// This represents a trait whose name we could not resolve. +const UNKNOWN_TRAIT: chalk_ir::TraitId = + chalk_ir::TraitId(chalk_ir::RawId { index: u32::max_value() }); + pub(super) trait ToChalk { type Chalk; fn to_chalk(self, db: &impl HirDatabase) -> Self::Chalk; @@ -45,7 +49,10 @@ impl ToChalk for Ty { Ty::Infer(_infer_ty) => panic!("uncanonicalized infer ty"), // FIXME this is clearly incorrect, but probably not too incorrect // and I'm not sure what to actually do with Ty::Unknown - Ty::Unknown => PlaceholderIndex { ui: UniverseIndex::ROOT, idx: 0 }.to_ty(), + // maybe an alternative would be `for T`? (meaningless in rust, but expressible in chalk's Ty) + Ty::Unknown => { + PlaceholderIndex { ui: UniverseIndex::ROOT, idx: usize::max_value() }.to_ty() + } } } fn from_chalk(db: &impl HirDatabase, chalk: chalk_ir::Ty) -> Self { @@ -154,7 +161,13 @@ impl ToChalk for GenericPredicate { GenericPredicate::Implemented(trait_ref) => { make_binders(chalk_ir::WhereClause::Implemented(trait_ref.to_chalk(db)), 0) } - GenericPredicate::Error => panic!("Trying to pass errored where clause to Chalk"), + GenericPredicate::Error => { + let impossible_trait_ref = chalk_ir::TraitRef { + trait_id: UNKNOWN_TRAIT, + parameters: vec![Ty::Unknown.to_chalk(db).cast()], + }; + make_binders(chalk_ir::WhereClause::Implemented(impossible_trait_ref), 0) + } } } @@ -178,19 +191,13 @@ fn convert_where_clauses( db: &impl HirDatabase, def: GenericDef, substs: &Substs, -) -> (Vec, bool) { +) -> Vec { let generic_predicates = db.generic_predicates(def); let mut result = Vec::with_capacity(generic_predicates.len()); - let mut has_error = false; for pred in generic_predicates.iter() { - // FIXME: it would probably be nicer if we could just convert errored predicates to a where clause that is never true... - if pred.is_error() { - has_error = true; - } else { - result.push(pred.clone().subst(substs).to_chalk(db)); - } + result.push(pred.clone().subst(substs).to_chalk(db)); } - (result, has_error) + result } impl<'a, DB> chalk_solve::RustIrDatabase for ChalkContext<'a, DB> @@ -202,6 +209,23 @@ where } fn trait_datum(&self, trait_id: chalk_ir::TraitId) -> Arc { debug!("trait_datum {:?}", trait_id); + if trait_id == UNKNOWN_TRAIT { + let trait_datum_bound = chalk_rust_ir::TraitDatumBound { + trait_ref: chalk_ir::TraitRef { + trait_id: UNKNOWN_TRAIT, + parameters: vec![chalk_ir::Ty::BoundVar(0).cast()], + }, + associated_ty_ids: Vec::new(), + where_clauses: Vec::new(), + flags: chalk_rust_ir::TraitFlags { + auto: false, + marker: false, + upstream: true, + fundamental: false, + }, + }; + return Arc::new(TraitDatum { binders: make_binders(trait_datum_bound, 1) }); + } 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); @@ -213,7 +237,7 @@ where upstream: trait_.module(self.db).krate(self.db) != Some(self.krate), fundamental: false, }; - let (where_clauses, _) = convert_where_clauses(self.db, trait_.into(), &bound_vars); + let where_clauses = convert_where_clauses(self.db, trait_.into(), &bound_vars); let associated_ty_ids = Vec::new(); // FIXME add associated tys let trait_datum_bound = chalk_rust_ir::TraitDatumBound { trait_ref, where_clauses, flags, associated_ty_ids }; @@ -241,7 +265,7 @@ where TypeCtor::Adt(adt) => { let generic_params = adt.generic_params(self.db); let bound_vars = Substs::bound_vars(&generic_params); - let (where_clauses, _) = convert_where_clauses(self.db, adt.into(), &bound_vars); + let where_clauses = convert_where_clauses(self.db, adt.into(), &bound_vars); ( generic_params.count_params_including_parent(), where_clauses, @@ -281,8 +305,7 @@ where } else { chalk_rust_ir::ImplType::External }; - let (where_clauses, where_clause_error) = - convert_where_clauses(self.db, impl_block.into(), &bound_vars); + let where_clauses = convert_where_clauses(self.db, impl_block.into(), &bound_vars); 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)), @@ -295,6 +318,9 @@ where } fn impls_for_trait(&self, trait_id: chalk_ir::TraitId) -> Vec { debug!("impls_for_trait {:?}", trait_id); + if trait_id == UNKNOWN_TRAIT { + return Vec::new(); + } let trait_ = from_chalk(self.db, trait_id); self.db .impls_for_trait(self.krate, trait_) -- cgit v1.2.3 From d8cd0e36f5288dd4c14fb5a07b73533d88f29788 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sun, 5 May 2019 15:01:07 +0200 Subject: Handle Chalk conversion for FnDef --- crates/ra_hir/src/marks.rs | 1 + crates/ra_hir/src/ty/tests.rs | 13 +++++++++++++ crates/ra_hir/src/ty/traits/chalk.rs | 27 +++++++++++++++++++++++++-- 3 files changed, 39 insertions(+), 2 deletions(-) diff --git a/crates/ra_hir/src/marks.rs b/crates/ra_hir/src/marks.rs index 5b6400042..2d831f0d8 100644 --- a/crates/ra_hir/src/marks.rs +++ b/crates/ra_hir/src/marks.rs @@ -9,4 +9,5 @@ test_utils::marks!( glob_across_crates std_prelude match_ergonomics_ref + trait_resolution_on_fn_type ); diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs index 3c55a093f..f0793bfb4 100644 --- a/crates/ra_hir/src/ty/tests.rs +++ b/crates/ra_hir/src/ty/tests.rs @@ -2568,6 +2568,19 @@ fn test() { S2.into()<|>; } assert_eq!(t, "S1"); } +#[test] +fn method_resolution_encountering_fn_type() { + covers!(trait_resolution_on_fn_type); + type_at( + r#" +//- /main.rs +fn foo() {} +trait FnOnce { fn call(self); } +fn test() { foo.call()<|>; } +"#, + ); +} + fn type_at_pos(db: &MockDatabase, pos: FilePosition) -> String { let file = db.parse(pos.file_id); let expr = algo::find_node_at_offset::(file.syntax(), pos.offset).unwrap(); diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs index 787970186..7bb6a4f4a 100644 --- a/crates/ra_hir/src/ty/traits/chalk.rs +++ b/crates/ra_hir/src/ty/traits/chalk.rs @@ -6,12 +6,13 @@ use log::debug; use chalk_ir::{TypeId, ImplId, TypeKindId, ProjectionTy, Parameter, Identifier, cast::Cast, PlaceholderIndex, UniverseIndex, TypeName}; use chalk_rust_ir::{AssociatedTyDatum, TraitDatum, StructDatum, ImplDatum}; +use test_utils::tested_by; use ra_db::salsa::{InternId, InternKey}; use crate::{ Trait, HasGenericParams, ImplBlock, db::HirDatabase, - ty::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs, GenericPredicate}, generics::GenericDef, + ty::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs, GenericPredicate}, generics::GenericDef, ty::CallableDef, }; use super::ChalkContext; @@ -261,7 +262,29 @@ where } TypeCtor::FnPtr { num_args } => (num_args as usize + 1, vec![], true), TypeCtor::Tuple { cardinality } => (cardinality as usize, vec![], true), - TypeCtor::FnDef(_) => unimplemented!(), + TypeCtor::FnDef(callable) => { + tested_by!(trait_resolution_on_fn_type); + let krate = match callable { + CallableDef::Function(f) => f.module(self.db).krate(self.db), + CallableDef::Struct(s) => s.module(self.db).krate(self.db), + CallableDef::EnumVariant(v) => { + v.parent_enum(self.db).module(self.db).krate(self.db) + } + }; + let generic_def: GenericDef = match callable { + CallableDef::Function(f) => f.into(), + CallableDef::Struct(s) => s.into(), + CallableDef::EnumVariant(v) => v.parent_enum(self.db).into(), + }; + let generic_params = generic_def.generic_params(self.db); + let bound_vars = Substs::bound_vars(&generic_params); + let where_clauses = convert_where_clauses(self.db, generic_def, &bound_vars); + ( + generic_params.count_params_including_parent(), + where_clauses, + krate != Some(self.krate), + ) + } TypeCtor::Adt(adt) => { let generic_params = adt.generic_params(self.db); let bound_vars = Substs::bound_vars(&generic_params); -- cgit v1.2.3 From 7744cd41e2ad79c1b36d3d9fccd3bc0dbfd9e2d9 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Tue, 7 May 2019 17:35:45 +0200 Subject: Reduce Chalk max_size parameter, add test for slow case --- crates/ra_hir/src/ty/tests.rs | 29 +++++++++++++++++++++++++++++ crates/ra_hir/src/ty/traits.rs | 9 ++++++++- crates/ra_hir/src/ty/traits/chalk.rs | 7 +++++-- 3 files changed, 42 insertions(+), 3 deletions(-) diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs index f0793bfb4..6f8d8fa49 100644 --- a/crates/ra_hir/src/ty/tests.rs +++ b/crates/ra_hir/src/ty/tests.rs @@ -2581,6 +2581,35 @@ fn test() { foo.call()<|>; } ); } +#[test] +fn method_resolution_slow() { + // this can get quite slow if we set the solver size limit too high + let t = type_at( + r#" +//- /main.rs +trait Send {} + +struct S1; impl Send for S1; +struct S2; impl Send for S2; +struct U1; + +trait Trait { fn method(self); } + +struct X1 {} +impl Send for X1 where A: Send, B: Send {} + +struct S {} + +trait Fn {} + +impl Trait for S where C: Fn, B: Send {} + +fn test() { (S {}).method()<|>; } +"#, + ); + assert_eq!(t, "{unknown}"); +} + fn type_at_pos(db: &MockDatabase, pos: FilePosition) -> String { let file = db.parse(pos.file_id); let expr = algo::find_node_at_offset::(file.syntax(), pos.offset).unwrap(); diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs index 4bbc99f0e..4260f7ef7 100644 --- a/crates/ra_hir/src/ty/traits.rs +++ b/crates/ra_hir/src/ty/traits.rs @@ -14,6 +14,11 @@ mod chalk; pub(crate) type Solver = chalk_solve::Solver; +/// This controls the maximum size of types Chalk considers. If we set this too +/// high, we can run into slow edge cases; if we set it too low, Chalk won't +/// find some solutions. +const CHALK_SOLVER_MAX_SIZE: usize = 2; + #[derive(Debug, Copy, Clone)] struct ChalkContext<'a, DB> { db: &'a DB, @@ -22,7 +27,8 @@ struct ChalkContext<'a, DB> { 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 }; + let solver_choice = chalk_solve::SolverChoice::SLG { max_size: CHALK_SOLVER_MAX_SIZE }; + debug!("Creating new solver for crate {:?}", _krate); Arc::new(Mutex::new(solver_choice.into_solver())) } @@ -53,6 +59,7 @@ fn solve( ) -> Option { let context = ChalkContext { db, krate }; let solver = db.solver(krate); + debug!("solve goal: {:?}", goal); let solution = solver.lock().unwrap().solve(&context, goal); debug!("solve({:?}) => {:?}", goal, solution); solution diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs index 7bb6a4f4a..8fa0ba7a5 100644 --- a/crates/ra_hir/src/ty/traits/chalk.rs +++ b/crates/ra_hir/src/ty/traits/chalk.rs @@ -345,11 +345,14 @@ where return Vec::new(); } let trait_ = from_chalk(self.db, trait_id); - self.db + let result: Vec<_> = self + .db .impls_for_trait(self.krate, trait_) .iter() .map(|impl_block| impl_block.to_chalk(self.db)) - .collect() + .collect(); + debug!("impls_for_trait returned {} impls", result.len()); + result } fn impl_provided_for( &self, -- cgit v1.2.3 From d6dc75f9f22b73faf8c526be69ca43e52d6db1bf Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Tue, 7 May 2019 18:53:16 +0200 Subject: Handle auto traits & negative impls We don't pass field types to Chalk yet though, so the auto trait inference won't be correct. --- crates/ra_hir/src/code_model_api.rs | 4 ++++ crates/ra_hir/src/impl_block.rs | 8 +++++++- crates/ra_hir/src/traits.rs | 8 +++++++- crates/ra_hir/src/ty/traits/chalk.rs | 24 +++++++++++++++++++----- crates/ra_syntax/src/ast/extensions.rs | 10 ++++++++++ 5 files changed, 47 insertions(+), 7 deletions(-) diff --git a/crates/ra_hir/src/code_model_api.rs b/crates/ra_hir/src/code_model_api.rs index 55e1793c5..0c4a80bfa 100644 --- a/crates/ra_hir/src/code_model_api.rs +++ b/crates/ra_hir/src/code_model_api.rs @@ -703,6 +703,10 @@ impl Trait { TraitRef::for_trait(db, self) } + pub fn is_auto(self, db: &impl DefDatabase) -> bool { + self.trait_data(db).is_auto() + } + 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/impl_block.rs b/crates/ra_hir/src/impl_block.rs index a8a466e43..b7dd775f1 100644 --- a/crates/ra_hir/src/impl_block.rs +++ b/crates/ra_hir/src/impl_block.rs @@ -93,6 +93,10 @@ impl ImplBlock { db.impls_in_module(self.module).impls[self.impl_id].items().to_vec() } + pub fn is_negative(&self, db: &impl DefDatabase) -> bool { + db.impls_in_module(self.module).impls[self.impl_id].negative + } + pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver { let r = self.module().resolver(db); // add generic params, if present @@ -108,6 +112,7 @@ pub struct ImplData { target_trait: Option, target_type: TypeRef, items: Vec, + negative: bool, } impl ImplData { @@ -120,6 +125,7 @@ impl ImplData { let target_trait = node.target_trait().map(TypeRef::from_ast); let target_type = TypeRef::from_ast_opt(node.target_type()); let ctx = LocationCtx::new(db, module, file_id); + let negative = node.is_negative(); let items = if let Some(item_list) = node.item_list() { item_list .impl_items() @@ -132,7 +138,7 @@ impl ImplData { } else { Vec::new() }; - ImplData { target_trait, target_type, items } + ImplData { target_trait, target_type, items, negative } } pub fn target_trait(&self) -> Option<&TypeRef> { diff --git a/crates/ra_hir/src/traits.rs b/crates/ra_hir/src/traits.rs index 15f0977b7..dfe883fa4 100644 --- a/crates/ra_hir/src/traits.rs +++ b/crates/ra_hir/src/traits.rs @@ -11,6 +11,7 @@ use crate::{Function, Const, TypeAlias, Name, DefDatabase, Trait, ids::LocationC pub struct TraitData { name: Option, items: Vec, + auto: bool, } impl TraitData { @@ -19,6 +20,7 @@ impl TraitData { let name = node.name().map(|n| n.as_name()); let module = tr.module(db); let ctx = LocationCtx::new(db, module, file_id); + let auto = node.is_auto(); let items = if let Some(item_list) = node.item_list() { item_list .impl_items() @@ -31,7 +33,7 @@ impl TraitData { } else { Vec::new() }; - Arc::new(TraitData { name, items }) + Arc::new(TraitData { name, items, auto }) } pub(crate) fn name(&self) -> &Option { @@ -41,6 +43,10 @@ impl TraitData { pub(crate) fn items(&self) -> &[TraitItem] { &self.items } + + pub(crate) fn is_auto(&self) -> bool { + self.auto + } } #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs index 8fa0ba7a5..027c5ec4c 100644 --- a/crates/ra_hir/src/ty/traits/chalk.rs +++ b/crates/ra_hir/src/ty/traits/chalk.rs @@ -12,7 +12,9 @@ use ra_db::salsa::{InternId, InternKey}; use crate::{ Trait, HasGenericParams, ImplBlock, db::HirDatabase, - ty::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs, GenericPredicate}, generics::GenericDef, ty::CallableDef, + ty::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs, GenericPredicate, CallableDef}, + ty::display::HirDisplay, + generics::GenericDef, }; use super::ChalkContext; @@ -232,10 +234,10 @@ where 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 { + auto: trait_.is_auto(self.db), + upstream: trait_.module(self.db).krate(self.db) != Some(self.krate), // 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 = convert_where_clauses(self.db, trait_.into(), &bound_vars); @@ -329,9 +331,21 @@ where chalk_rust_ir::ImplType::External }; let where_clauses = convert_where_clauses(self.db, impl_block.into(), &bound_vars); + let negative = impl_block.is_negative(self.db); + debug!( + "impl {:?}: {}{} where {:?}", + impl_id, + if negative { "!" } else { "" }, + trait_ref.display(self.db), + where_clauses + ); + let trait_ref = trait_ref.to_chalk(self.db); 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)), + trait_ref: if negative { + chalk_rust_ir::PolarizedTraitRef::Negative(trait_ref) + } else { + chalk_rust_ir::PolarizedTraitRef::Positive(trait_ref) + }, where_clauses, associated_ty_values: Vec::new(), // FIXME add associated type values impl_type, diff --git a/crates/ra_syntax/src/ast/extensions.rs b/crates/ra_syntax/src/ast/extensions.rs index 9cbd2c6b8..f3466c585 100644 --- a/crates/ra_syntax/src/ast/extensions.rs +++ b/crates/ra_syntax/src/ast/extensions.rs @@ -170,6 +170,10 @@ impl ast::ImplBlock { let second = types.next(); (first, second) } + + pub fn is_negative(&self) -> bool { + self.syntax().children_with_tokens().any(|t| t.kind() == EXCL) + } } #[derive(Debug, Clone, PartialEq, Eq)] @@ -348,3 +352,9 @@ impl ast::WherePred { .find(|it| it.kind() == LIFETIME) } } + +impl ast::TraitDef { + pub fn is_auto(&self) -> bool { + self.syntax().children_with_tokens().any(|t| t.kind() == AUTO_KW) + } +} -- cgit v1.2.3 From cbe75676b90d93e5b0ac461dce2d916cef4c0476 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sat, 11 May 2019 16:49:55 +0200 Subject: Add support for inline bounds E.g. impl Foo for T. --- crates/ra_hir/src/generics.rs | 43 +++++++++++++++++++++++++++---------------- crates/ra_hir/src/ty/tests.rs | 33 +++++++++++++++++++++++++++++++++ 2 files changed, 60 insertions(+), 16 deletions(-) diff --git a/crates/ra_hir/src/generics.rs b/crates/ra_hir/src/generics.rs index 826117ba5..c29b96f50 100644 --- a/crates/ra_hir/src/generics.rs +++ b/crates/ra_hir/src/generics.rs @@ -90,8 +90,17 @@ impl GenericParams { fn fill_params(&mut self, params: &ast::TypeParamList, start: u32) { for (idx, type_param) in params.type_params().enumerate() { let name = type_param.name().map(AsName::as_name).unwrap_or_else(Name::missing); - let param = GenericParam { idx: idx as u32 + start, name }; + let param = GenericParam { idx: idx as u32 + start, name: name.clone() }; self.params.push(param); + + let type_ref = TypeRef::Path(name.into()); + for bound in type_param + .type_bound_list() + .iter() + .flat_map(|type_bound_list| type_bound_list.bounds()) + { + self.add_where_predicate_from_bound(bound, type_ref.clone()); + } } } @@ -101,26 +110,28 @@ impl GenericParams { Some(type_ref) => type_ref, None => continue, }; + let type_ref = TypeRef::from_ast(type_ref); for bound in pred.type_bound_list().iter().flat_map(|l| l.bounds()) { - let path = bound - .type_ref() - .and_then(|tr| match tr.kind() { - ast::TypeRefKind::PathType(path) => path.path(), - _ => None, - }) - .and_then(Path::from_ast); - let path = match path { - Some(p) => p, - None => continue, - }; - self.where_predicates.push(WherePredicate { - type_ref: TypeRef::from_ast(type_ref), - trait_ref: path, - }); + self.add_where_predicate_from_bound(bound, type_ref.clone()); } } } + fn add_where_predicate_from_bound(&mut self, bound: &ast::TypeBound, type_ref: TypeRef) { + let path = bound + .type_ref() + .and_then(|tr| match tr.kind() { + ast::TypeRefKind::PathType(path) => path.path(), + _ => None, + }) + .and_then(Path::from_ast); + let path = match path { + Some(p) => p, + None => return, + }; + self.where_predicates.push(WherePredicate { type_ref, trait_ref: path }); + } + pub(crate) fn find_by_name(&self, name: &Name) -> Option<&GenericParam> { self.params.iter().find(|p| &p.name == name) } diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs index 6f8d8fa49..59c85daed 100644 --- a/crates/ra_hir/src/ty/tests.rs +++ b/crates/ra_hir/src/ty/tests.rs @@ -2535,6 +2535,22 @@ fn test() { (&S).foo()<|>; } assert_eq!(t, "{unknown}"); } +#[test] +fn method_resolution_where_clause_inline_not_met() { + // The blanket impl shouldn't apply because we can't prove S: Clone + let t = type_at( + r#" +//- /main.rs +trait Clone {} +trait Trait { fn foo(self) -> u128; } +struct S; +impl Trait for T {} +fn test() { (&S).foo()<|>; } +"#, + ); + assert_eq!(t, "{unknown}"); +} + #[test] fn method_resolution_where_clause_1() { let t = type_at( @@ -2568,6 +2584,23 @@ fn test() { S2.into()<|>; } assert_eq!(t, "S1"); } +#[test] +fn method_resolution_where_clause_inline() { + let t = type_at( + r#" +//- /main.rs +trait Into { fn into(self) -> T; } +trait From { fn from(other: T) -> Self; } +struct S1; +struct S2; +impl From for S1 {}; +impl> Into for T {} +fn test() { S2.into()<|>; } +"#, + ); + assert_eq!(t, "S1"); +} + #[test] fn method_resolution_encountering_fn_type() { covers!(trait_resolution_on_fn_type); -- cgit v1.2.3