From de39d221a15c0a146ed8adbdb1616692180948bb Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Fri, 21 Feb 2020 18:24:18 +0100 Subject: Implement unsize coercion using proper trait solving --- crates/ra_hir_ty/src/traits/builtin.rs | 61 +++++++++++++++++++++++++++++++++- 1 file changed, 60 insertions(+), 1 deletion(-) (limited to 'crates/ra_hir_ty/src/traits') diff --git a/crates/ra_hir_ty/src/traits/builtin.rs b/crates/ra_hir_ty/src/traits/builtin.rs index a537420a5..394232fd9 100644 --- a/crates/ra_hir_ty/src/traits/builtin.rs +++ b/crates/ra_hir_ty/src/traits/builtin.rs @@ -5,7 +5,7 @@ use hir_expand::name::name; use ra_db::CrateId; use super::{AssocTyValue, Impl}; -use crate::{db::HirDatabase, ApplicationTy, Substs, TraitRef, Ty, TypeCtor}; +use crate::{db::HirDatabase, utils::generics, ApplicationTy, Substs, TraitRef, Ty, TypeCtor}; pub(super) struct BuiltinImplData { pub num_vars: usize, @@ -43,12 +43,22 @@ pub(super) fn get_builtin_impls( } } } + if let Ty::Apply(ApplicationTy { ctor: TypeCtor::Array, .. }) = ty { + if let Some(actual_trait) = get_unsize_trait(db, krate) { + if trait_ == actual_trait { + if check_unsize_impl_prerequisites(db, krate) { + callback(Impl::UnsizeArray); + } + } + } + } } pub(super) fn impl_datum(db: &impl HirDatabase, krate: CrateId, impl_: Impl) -> BuiltinImplData { match impl_ { Impl::ImplBlock(_) => unreachable!(), Impl::ClosureFnTraitImpl(data) => closure_fn_trait_impl_datum(db, krate, data), + Impl::UnsizeArray => array_unsize_impl_datum(db, krate), } } @@ -65,6 +75,8 @@ pub(super) fn associated_ty_value( } } +// Closure Fn trait impls + fn check_closure_fn_trait_impl_prerequisites( db: &impl HirDatabase, krate: CrateId, @@ -165,6 +177,45 @@ fn closure_fn_trait_output_assoc_ty_value( } } +// Array unsizing + +fn check_unsize_impl_prerequisites(db: &impl HirDatabase, krate: CrateId) -> bool { + // the Unsize trait needs to exist and have two type parameters (Self and T) + let unsize_trait = match get_unsize_trait(db, krate) { + Some(t) => t, + None => return false, + }; + let generic_params = generics(db, unsize_trait.into()); + if generic_params.len() != 2 { + return false; + } + true +} + +fn array_unsize_impl_datum(db: &impl HirDatabase, krate: CrateId) -> BuiltinImplData { + // impl Unsize<[T]> for [T; _] + // (this can be a single impl because we don't distinguish array sizes currently) + + let trait_ = get_unsize_trait(db, krate) // get unsize trait + // the existence of the Unsize trait has been checked before + .expect("Unsize trait missing"); + + let var = Ty::Bound(0); + let substs = Substs::builder(2) + .push(Ty::apply_one(TypeCtor::Array, var.clone())) + .push(Ty::apply_one(TypeCtor::Slice, var)) + .build(); + + let trait_ref = TraitRef { trait_, substs }; + + BuiltinImplData { + num_vars: 1, + trait_ref, + where_clauses: Vec::new(), + assoc_ty_values: Vec::new(), + } +} + fn get_fn_trait( db: &impl HirDatabase, krate: CrateId, @@ -176,3 +227,11 @@ fn get_fn_trait( _ => None, } } + +fn get_unsize_trait(db: &impl HirDatabase, krate: CrateId) -> Option { + let target = db.lang_item(krate, "unsize".into())?; + match target { + LangItemTarget::TraitId(t) => Some(t), + _ => None, + } +} -- cgit v1.2.3 From 0dfbbaf03b03618dcb7ba203ddc453533bb8d1b4 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Fri, 21 Feb 2020 19:05:27 +0100 Subject: Implement dyn Trait unsizing as well --- crates/ra_hir_ty/src/traits/builtin.rs | 112 ++++++++++++++++++++++++++++++--- crates/ra_hir_ty/src/traits/chalk.rs | 4 +- 2 files changed, 108 insertions(+), 8 deletions(-) (limited to 'crates/ra_hir_ty/src/traits') diff --git a/crates/ra_hir_ty/src/traits/builtin.rs b/crates/ra_hir_ty/src/traits/builtin.rs index 394232fd9..3c8dd4af8 100644 --- a/crates/ra_hir_ty/src/traits/builtin.rs +++ b/crates/ra_hir_ty/src/traits/builtin.rs @@ -4,8 +4,12 @@ use hir_def::{expr::Expr, lang_item::LangItemTarget, TraitId, TypeAliasId}; use hir_expand::name::name; use ra_db::CrateId; -use super::{AssocTyValue, Impl}; -use crate::{db::HirDatabase, utils::generics, ApplicationTy, Substs, TraitRef, Ty, TypeCtor}; +use super::{AssocTyValue, Impl, UnsizeToSuperTraitObjectData}; +use crate::{ + db::HirDatabase, + utils::{all_super_traits, generics}, + ApplicationTy, GenericPredicate, Substs, TraitRef, Ty, TypeCtor, +}; pub(super) struct BuiltinImplData { pub num_vars: usize, @@ -25,6 +29,8 @@ pub(super) fn get_builtin_impls( db: &impl HirDatabase, krate: CrateId, ty: &Ty, + // The first argument for the trait, if present + arg: &Option, trait_: TraitId, mut callback: impl FnMut(Impl), ) { @@ -43,14 +49,43 @@ pub(super) fn get_builtin_impls( } } } + + let unsize_trait = get_unsize_trait(db, krate); + if let Some(actual_trait) = unsize_trait { + if trait_ == actual_trait { + get_builtin_unsize_impls(db, krate, ty, arg, callback); + } + } +} + +fn get_builtin_unsize_impls( + db: &impl HirDatabase, + krate: CrateId, + ty: &Ty, + // The first argument for the trait, if present + arg: &Option, + mut callback: impl FnMut(Impl), +) { + if !check_unsize_impl_prerequisites(db, krate) { + return; + } + if let Ty::Apply(ApplicationTy { ctor: TypeCtor::Array, .. }) = ty { - if let Some(actual_trait) = get_unsize_trait(db, krate) { - if trait_ == actual_trait { - if check_unsize_impl_prerequisites(db, krate) { - callback(Impl::UnsizeArray); - } + callback(Impl::UnsizeArray); + } + + if let Some(target_trait) = arg.as_ref().and_then(|t| t.dyn_trait_ref()) { + if let Some(trait_ref) = ty.dyn_trait_ref() { + let super_traits = all_super_traits(db, trait_ref.trait_); + if super_traits.contains(&target_trait.trait_) { + // callback(Impl::UnsizeToSuperTraitObject(UnsizeToSuperTraitObjectData { + // trait_: trait_ref.trait_, + // super_trait: target_trait.trait_, + // })); } } + + callback(Impl::UnsizeToTraitObject(target_trait.trait_)); } } @@ -59,6 +94,10 @@ pub(super) fn impl_datum(db: &impl HirDatabase, krate: CrateId, impl_: Impl) -> Impl::ImplBlock(_) => unreachable!(), Impl::ClosureFnTraitImpl(data) => closure_fn_trait_impl_datum(db, krate, data), Impl::UnsizeArray => array_unsize_impl_datum(db, krate), + Impl::UnsizeToTraitObject(trait_) => trait_object_unsize_impl_datum(db, krate, trait_), + Impl::UnsizeToSuperTraitObject(data) => { + super_trait_object_unsize_impl_datum(db, krate, data) + } } } @@ -216,6 +255,65 @@ fn array_unsize_impl_datum(db: &impl HirDatabase, krate: CrateId) -> BuiltinImpl } } +// Trait object unsizing + +fn trait_object_unsize_impl_datum( + db: &impl HirDatabase, + krate: CrateId, + trait_: TraitId, +) -> BuiltinImplData { + // impl Unsize> for T where T: Trait + + let unsize_trait = get_unsize_trait(db, krate) // get unsize trait + // the existence of the Unsize trait has been checked before + .expect("Unsize trait missing"); + + let self_ty = Ty::Bound(0); + + let substs = Substs::build_for_def(db, trait_) + // this fits together nicely: $0 is our self type, and the rest are the type + // args for the trait + .fill_with_bound_vars(0) + .build(); + let trait_ref = TraitRef { trait_, substs }; + // This is both the bound for the `dyn` type, *and* the bound for the impl! + // This works because the self type for `dyn` is always Ty::Bound(0), which + // we've also made the parameter for our impl self type. + let bounds = vec![GenericPredicate::Implemented(trait_ref)]; + + let impl_substs = Substs::builder(2).push(self_ty).push(Ty::Dyn(bounds.clone().into())).build(); + + let trait_ref = TraitRef { trait_: unsize_trait, substs: impl_substs }; + + BuiltinImplData { num_vars: 1, trait_ref, where_clauses: bounds, assoc_ty_values: Vec::new() } +} + +fn super_trait_object_unsize_impl_datum( + db: &impl HirDatabase, + krate: CrateId, + _data: UnsizeToSuperTraitObjectData, +) -> BuiltinImplData { + // impl Unsize for dyn Trait + + let unsize_trait = get_unsize_trait(db, krate) // get unsize trait + // the existence of the Unsize trait has been checked before + .expect("Unsize trait missing"); + + let substs = Substs::builder(2) + // .push(Ty::Dyn(todo!())) + // .push(Ty::Dyn(todo!())) + .build(); + + let trait_ref = TraitRef { trait_: unsize_trait, substs }; + + BuiltinImplData { + num_vars: 1, + trait_ref, + where_clauses: Vec::new(), + assoc_ty_values: Vec::new(), + } +} + fn get_fn_trait( db: &impl HirDatabase, krate: CrateId, diff --git a/crates/ra_hir_ty/src/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs index 1bdf13e48..e1e430aeb 100644 --- a/crates/ra_hir_ty/src/traits/chalk.rs +++ b/crates/ra_hir_ty/src/traits/chalk.rs @@ -572,8 +572,10 @@ where .collect(); let ty: Ty = from_chalk(self.db, parameters[0].assert_ty_ref().clone()); + let arg: Option = + parameters.get(1).map(|p| from_chalk(self.db, p.assert_ty_ref().clone())); - builtin::get_builtin_impls(self.db, self.krate, &ty, trait_, |i| { + builtin::get_builtin_impls(self.db, self.krate, &ty, &arg, trait_, |i| { result.push(i.to_chalk(self.db)) }); -- cgit v1.2.3 From 2d5ab6324795e5fc36e4b61cb66737958dc67e7a Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Fri, 21 Feb 2020 21:49:02 +0100 Subject: Add &dyn Trait -> &dyn SuperTrait coercion, and fix &T -> &dyn Trait --- crates/ra_hir_ty/src/traits/builtin.rs | 95 +++++++++++++++++++++++----------- 1 file changed, 65 insertions(+), 30 deletions(-) (limited to 'crates/ra_hir_ty/src/traits') diff --git a/crates/ra_hir_ty/src/traits/builtin.rs b/crates/ra_hir_ty/src/traits/builtin.rs index 3c8dd4af8..19e533cee 100644 --- a/crates/ra_hir_ty/src/traits/builtin.rs +++ b/crates/ra_hir_ty/src/traits/builtin.rs @@ -8,7 +8,7 @@ use super::{AssocTyValue, Impl, UnsizeToSuperTraitObjectData}; use crate::{ db::HirDatabase, utils::{all_super_traits, generics}, - ApplicationTy, GenericPredicate, Substs, TraitRef, Ty, TypeCtor, + ApplicationTy, Binders, GenericPredicate, Substs, TraitRef, Ty, TypeCtor, }; pub(super) struct BuiltinImplData { @@ -72,20 +72,25 @@ fn get_builtin_unsize_impls( if let Ty::Apply(ApplicationTy { ctor: TypeCtor::Array, .. }) = ty { callback(Impl::UnsizeArray); + return; // array is unsized, the rest of the impls shouldn't apply } if let Some(target_trait) = arg.as_ref().and_then(|t| t.dyn_trait_ref()) { + // FIXME what about more complicated dyn tys with marker traits? if let Some(trait_ref) = ty.dyn_trait_ref() { - let super_traits = all_super_traits(db, trait_ref.trait_); - if super_traits.contains(&target_trait.trait_) { - // callback(Impl::UnsizeToSuperTraitObject(UnsizeToSuperTraitObjectData { - // trait_: trait_ref.trait_, - // super_trait: target_trait.trait_, - // })); + if trait_ref.trait_ != target_trait.trait_ { + let super_traits = all_super_traits(db, trait_ref.trait_); + if super_traits.contains(&target_trait.trait_) { + callback(Impl::UnsizeToSuperTraitObject(UnsizeToSuperTraitObjectData { + trait_: trait_ref.trait_, + super_trait: target_trait.trait_, + })); + } } + } else { + // FIXME only for sized types + callback(Impl::UnsizeToTraitObject(target_trait.trait_)); } - - callback(Impl::UnsizeToTraitObject(target_trait.trait_)); } } @@ -270,48 +275,78 @@ fn trait_object_unsize_impl_datum( let self_ty = Ty::Bound(0); - let substs = Substs::build_for_def(db, trait_) - // this fits together nicely: $0 is our self type, and the rest are the type - // args for the trait - .fill_with_bound_vars(0) + let target_substs = Substs::build_for_def(db, trait_) + .push(Ty::Bound(0)) + // starting from ^2 because we want to start with ^1 outside of the + // `dyn`, which is ^2 inside + .fill_with_bound_vars(2) .build(); - let trait_ref = TraitRef { trait_, substs }; - // This is both the bound for the `dyn` type, *and* the bound for the impl! - // This works because the self type for `dyn` is always Ty::Bound(0), which - // we've also made the parameter for our impl self type. - let bounds = vec![GenericPredicate::Implemented(trait_ref)]; + let num_vars = target_substs.len(); + let target_trait_ref = TraitRef { trait_, substs: target_substs }; + let target_bounds = vec![GenericPredicate::Implemented(target_trait_ref)]; - let impl_substs = Substs::builder(2).push(self_ty).push(Ty::Dyn(bounds.clone().into())).build(); + let self_substs = Substs::build_for_def(db, trait_).fill_with_bound_vars(0).build(); + let self_trait_ref = TraitRef { trait_, substs: self_substs }; + let where_clauses = vec![GenericPredicate::Implemented(self_trait_ref)]; + + let impl_substs = + Substs::builder(2).push(self_ty).push(Ty::Dyn(target_bounds.clone().into())).build(); let trait_ref = TraitRef { trait_: unsize_trait, substs: impl_substs }; - BuiltinImplData { num_vars: 1, trait_ref, where_clauses: bounds, assoc_ty_values: Vec::new() } + BuiltinImplData { num_vars, trait_ref, where_clauses, assoc_ty_values: Vec::new() } } fn super_trait_object_unsize_impl_datum( db: &impl HirDatabase, krate: CrateId, - _data: UnsizeToSuperTraitObjectData, + data: UnsizeToSuperTraitObjectData, ) -> BuiltinImplData { - // impl Unsize for dyn Trait + // impl Unsize for dyn Trait let unsize_trait = get_unsize_trait(db, krate) // get unsize trait // the existence of the Unsize trait has been checked before .expect("Unsize trait missing"); + let self_substs = Substs::build_for_def(db, data.trait_).fill_with_bound_vars(0).build(); + + let num_vars = self_substs.len() - 1; + + let self_trait_ref = TraitRef { trait_: data.trait_, substs: self_substs.clone() }; + let self_bounds = vec![GenericPredicate::Implemented(self_trait_ref.clone())]; + + // we need to go from our trait to the super trait, substituting type parameters + let mut path = crate::utils::find_super_trait_path(db, data.super_trait, data.trait_); + path.pop(); // the last one is our current trait, we don't need that + path.reverse(); // we want to go from trait to super trait + + let mut current_trait_ref = self_trait_ref; + for t in path { + let bounds = db.generic_predicates(current_trait_ref.trait_.into()); + let super_trait_ref = bounds + .iter() + .find_map(|b| match &b.value { + GenericPredicate::Implemented(tr) + if tr.trait_ == t && tr.substs[0] == Ty::Bound(0) => + { + Some(Binders { value: tr, num_binders: b.num_binders }) + } + _ => None, + }) + .expect("trait bound for known super trait not found"); + current_trait_ref = super_trait_ref.cloned().subst(¤t_trait_ref.substs); + } + + let super_bounds = vec![GenericPredicate::Implemented(current_trait_ref)]; + let substs = Substs::builder(2) - // .push(Ty::Dyn(todo!())) - // .push(Ty::Dyn(todo!())) + .push(Ty::Dyn(self_bounds.into())) + .push(Ty::Dyn(super_bounds.into())) .build(); let trait_ref = TraitRef { trait_: unsize_trait, substs }; - BuiltinImplData { - num_vars: 1, - trait_ref, - where_clauses: Vec::new(), - assoc_ty_values: Vec::new(), - } + BuiltinImplData { num_vars, trait_ref, where_clauses: Vec::new(), assoc_ty_values: Vec::new() } } fn get_fn_trait( -- cgit v1.2.3 From 3e106c77ff76c39be49444165eac805d32666e41 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sat, 22 Feb 2020 13:14:39 +0100 Subject: Rework find_super_trait_path to protect against cycles --- crates/ra_hir_ty/src/traits/builtin.rs | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) (limited to 'crates/ra_hir_ty/src/traits') diff --git a/crates/ra_hir_ty/src/traits/builtin.rs b/crates/ra_hir_ty/src/traits/builtin.rs index 19e533cee..df0645717 100644 --- a/crates/ra_hir_ty/src/traits/builtin.rs +++ b/crates/ra_hir_ty/src/traits/builtin.rs @@ -316,12 +316,10 @@ fn super_trait_object_unsize_impl_datum( let self_bounds = vec![GenericPredicate::Implemented(self_trait_ref.clone())]; // we need to go from our trait to the super trait, substituting type parameters - let mut path = crate::utils::find_super_trait_path(db, data.super_trait, data.trait_); - path.pop(); // the last one is our current trait, we don't need that - path.reverse(); // we want to go from trait to super trait + let path = crate::utils::find_super_trait_path(db, data.trait_, data.super_trait); let mut current_trait_ref = self_trait_ref; - for t in path { + for t in path.into_iter().skip(1) { let bounds = db.generic_predicates(current_trait_ref.trait_.into()); let super_trait_ref = bounds .iter() -- cgit v1.2.3 From 5a6e770f99d1549432c1e8a1abb1aada09ad2590 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sat, 22 Feb 2020 13:15:54 +0100 Subject: Shorten some code --- crates/ra_hir_ty/src/traits/builtin.rs | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-) (limited to 'crates/ra_hir_ty/src/traits') diff --git a/crates/ra_hir_ty/src/traits/builtin.rs b/crates/ra_hir_ty/src/traits/builtin.rs index df0645717..cc0f3eeb4 100644 --- a/crates/ra_hir_ty/src/traits/builtin.rs +++ b/crates/ra_hir_ty/src/traits/builtin.rs @@ -230,10 +230,7 @@ fn check_unsize_impl_prerequisites(db: &impl HirDatabase, krate: CrateId) -> boo None => return false, }; let generic_params = generics(db, unsize_trait.into()); - if generic_params.len() != 2 { - return false; - } - true + generic_params.len() == 2 } fn array_unsize_impl_datum(db: &impl HirDatabase, krate: CrateId) -> BuiltinImplData { -- cgit v1.2.3