aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--crates/ra_hir_ty/src/infer.rs7
-rw-r--r--crates/ra_hir_ty/src/infer/coerce.rs205
-rw-r--r--crates/ra_hir_ty/src/infer/unify.rs99
-rw-r--r--crates/ra_hir_ty/src/lib.rs48
-rw-r--r--crates/ra_hir_ty/src/lower.rs5
-rw-r--r--crates/ra_hir_ty/src/tests/coercion.rs138
-rw-r--r--crates/ra_hir_ty/src/traits.rs12
-rw-r--r--crates/ra_hir_ty/src/traits/builtin.rs191
-rw-r--r--crates/ra_hir_ty/src/traits/chalk.rs4
-rw-r--r--crates/ra_hir_ty/src/utils.rs32
10 files changed, 480 insertions, 261 deletions
diff --git a/crates/ra_hir_ty/src/infer.rs b/crates/ra_hir_ty/src/infer.rs
index 76069eb9c..6e1d268de 100644
--- a/crates/ra_hir_ty/src/infer.rs
+++ b/crates/ra_hir_ty/src/infer.rs
@@ -206,12 +206,6 @@ struct InferenceContext<'a, D: HirDatabase> {
206 /// closures, but currently this is the only field that will change there, 206 /// closures, but currently this is the only field that will change there,
207 /// so it doesn't make sense. 207 /// so it doesn't make sense.
208 return_ty: Ty, 208 return_ty: Ty,
209
210 /// Impls of `CoerceUnsized` used in coercion.
211 /// (from_ty_ctor, to_ty_ctor) => coerce_generic_index
212 // FIXME: Use trait solver for this.
213 // Chalk seems unable to work well with builtin impl of `Unsize` now.
214 coerce_unsized_map: FxHashMap<(TypeCtor, TypeCtor), usize>,
215} 209}
216 210
217impl<'a, D: HirDatabase> InferenceContext<'a, D> { 211impl<'a, D: HirDatabase> InferenceContext<'a, D> {
@@ -222,7 +216,6 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
222 obligations: Vec::default(), 216 obligations: Vec::default(),
223 return_ty: Ty::Unknown, // set in collect_fn_signature 217 return_ty: Ty::Unknown, // set in collect_fn_signature
224 trait_env: TraitEnvironment::lower(db, &resolver), 218 trait_env: TraitEnvironment::lower(db, &resolver),
225 coerce_unsized_map: Self::init_coerce_unsized_map(db, &resolver),
226 db, 219 db,
227 owner, 220 owner,
228 body: db.body(owner), 221 body: db.body(owner),
diff --git a/crates/ra_hir_ty/src/infer/coerce.rs b/crates/ra_hir_ty/src/infer/coerce.rs
index fb6a51b12..95ac3c713 100644
--- a/crates/ra_hir_ty/src/infer/coerce.rs
+++ b/crates/ra_hir_ty/src/infer/coerce.rs
@@ -4,11 +4,12 @@
4//! 4//!
5//! See: https://doc.rust-lang.org/nomicon/coercions.html 5//! See: https://doc.rust-lang.org/nomicon/coercions.html
6 6
7use hir_def::{lang_item::LangItemTarget, resolver::Resolver, type_ref::Mutability, AdtId}; 7use hir_def::{lang_item::LangItemTarget, type_ref::Mutability};
8use rustc_hash::FxHashMap;
9use test_utils::tested_by; 8use test_utils::tested_by;
10 9
11use crate::{autoderef, db::HirDatabase, Substs, Ty, TypeCtor, TypeWalk}; 10use crate::{
11 autoderef, db::HirDatabase, traits::Solution, Obligation, Substs, TraitRef, Ty, TypeCtor,
12};
12 13
13use super::{unify::TypeVarValue, InEnvironment, InferTy, InferenceContext}; 14use super::{unify::TypeVarValue, InEnvironment, InferTy, InferenceContext};
14 15
@@ -39,44 +40,6 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
39 } 40 }
40 } 41 }
41 42
42 pub(super) fn init_coerce_unsized_map(
43 db: &'a D,
44 resolver: &Resolver,
45 ) -> FxHashMap<(TypeCtor, TypeCtor), usize> {
46 let krate = resolver.krate().unwrap();
47 let impls = match db.lang_item(krate, "coerce_unsized".into()) {
48 Some(LangItemTarget::TraitId(trait_)) => db.impls_for_trait(krate, trait_),
49 _ => return FxHashMap::default(),
50 };
51
52 impls
53 .iter()
54 .filter_map(|&impl_id| {
55 let trait_ref = db.impl_trait(impl_id)?;
56
57 // `CoerseUnsized` has one generic parameter for the target type.
58 let cur_from_ty = trait_ref.value.substs.0.get(0)?;
59 let cur_to_ty = trait_ref.value.substs.0.get(1)?;
60
61 match (&cur_from_ty, cur_to_ty) {
62 (ty_app!(ctor1, st1), ty_app!(ctor2, st2)) => {
63 // FIXME: We return the first non-equal bound as the type parameter to coerce to unsized type.
64 // This works for smart-pointer-like coercion, which covers all impls from std.
65 st1.iter().zip(st2.iter()).enumerate().find_map(|(i, (ty1, ty2))| {
66 match (ty1, ty2) {
67 (Ty::Bound(idx1), Ty::Bound(idx2)) if idx1 != idx2 => {
68 Some(((*ctor1, *ctor2), i))
69 }
70 _ => None,
71 }
72 })
73 }
74 _ => None,
75 }
76 })
77 .collect()
78 }
79
80 fn coerce_inner(&mut self, mut from_ty: Ty, to_ty: &Ty) -> bool { 43 fn coerce_inner(&mut self, mut from_ty: Ty, to_ty: &Ty) -> bool {
81 match (&from_ty, to_ty) { 44 match (&from_ty, to_ty) {
82 // Never type will make type variable to fallback to Never Type instead of Unknown. 45 // Never type will make type variable to fallback to Never Type instead of Unknown.
@@ -157,154 +120,38 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
157 /// 120 ///
158 /// See: https://doc.rust-lang.org/nightly/std/marker/trait.CoerceUnsized.html 121 /// See: https://doc.rust-lang.org/nightly/std/marker/trait.CoerceUnsized.html
159 fn try_coerce_unsized(&mut self, from_ty: &Ty, to_ty: &Ty) -> Option<bool> { 122 fn try_coerce_unsized(&mut self, from_ty: &Ty, to_ty: &Ty) -> Option<bool> {
160 let (ctor1, st1, ctor2, st2) = match (from_ty, to_ty) { 123 let krate = self.resolver.krate().unwrap();
161 (ty_app!(ctor1, st1), ty_app!(ctor2, st2)) => (ctor1, st1, ctor2, st2), 124 let coerce_unsized_trait = match self.db.lang_item(krate, "coerce_unsized".into()) {
125 Some(LangItemTarget::TraitId(trait_)) => trait_,
162 _ => return None, 126 _ => return None,
163 }; 127 };
164 128
165 let coerce_generic_index = *self.coerce_unsized_map.get(&(*ctor1, *ctor2))?; 129 let generic_params = crate::utils::generics(self.db, coerce_unsized_trait.into());
166 130 if generic_params.len() != 2 {
167 // Check `Unsize` first 131 // The CoerceUnsized trait should have two generic params: Self and T.
168 match self.check_unsize_and_coerce( 132 return None;
169 st1.0.get(coerce_generic_index)?,
170 st2.0.get(coerce_generic_index)?,
171 0,
172 ) {
173 Some(true) => {}
174 ret => return ret,
175 } 133 }
176 134
177 let ret = st1 135 let substs = Substs::build_for_generics(&generic_params)
178 .iter() 136 .push(from_ty.clone())
179 .zip(st2.iter()) 137 .push(to_ty.clone())
180 .enumerate() 138 .build();
181 .filter(|&(idx, _)| idx != coerce_generic_index) 139 let trait_ref = TraitRef { trait_: coerce_unsized_trait, substs };
182 .all(|(_, (ty1, ty2))| self.unify(ty1, ty2)); 140 let goal = InEnvironment::new(self.trait_env.clone(), Obligation::Trait(trait_ref));
183 141
184 Some(ret) 142 let canonicalizer = self.canonicalizer();
185 } 143 let canonicalized = canonicalizer.canonicalize_obligation(goal);
186 144
187 /// Check if `from_ty: Unsize<to_ty>`, and coerce to `to_ty` if it holds. 145 let solution = self.db.trait_solve(krate, canonicalized.value.clone())?;
188 ///
189 /// It should not be directly called. It is only used by `try_coerce_unsized`.
190 ///
191 /// See: https://doc.rust-lang.org/nightly/std/marker/trait.Unsize.html
192 fn check_unsize_and_coerce(&mut self, from_ty: &Ty, to_ty: &Ty, depth: usize) -> Option<bool> {
193 if depth > 1000 {
194 panic!("Infinite recursion in coercion");
195 }
196
197 match (&from_ty, &to_ty) {
198 // `[T; N]` -> `[T]`
199 (ty_app!(TypeCtor::Array, st1), ty_app!(TypeCtor::Slice, st2)) => {
200 Some(self.unify(&st1[0], &st2[0]))
201 }
202 146
203 // `T` -> `dyn Trait` when `T: Trait` 147 match solution {
204 (_, Ty::Dyn(_)) => { 148 Solution::Unique(v) => {
205 // FIXME: Check predicates 149 canonicalized.apply_solution(self, v.0);
206 Some(true)
207 }
208
209 // `(..., T)` -> `(..., U)` when `T: Unsize<U>`
210 (
211 ty_app!(TypeCtor::Tuple { cardinality: len1 }, st1),
212 ty_app!(TypeCtor::Tuple { cardinality: len2 }, st2),
213 ) => {
214 if len1 != len2 || *len1 == 0 {
215 return None;
216 }
217
218 match self.check_unsize_and_coerce(
219 st1.last().unwrap(),
220 st2.last().unwrap(),
221 depth + 1,
222 ) {
223 Some(true) => {}
224 ret => return ret,
225 }
226
227 let ret = st1[..st1.len() - 1]
228 .iter()
229 .zip(&st2[..st2.len() - 1])
230 .all(|(ty1, ty2)| self.unify(ty1, ty2));
231
232 Some(ret)
233 }
234
235 // Foo<..., T, ...> is Unsize<Foo<..., U, ...>> if:
236 // - T: Unsize<U>
237 // - Foo is a struct
238 // - Only the last field of Foo has a type involving T
239 // - T is not part of the type of any other fields
240 // - Bar<T>: Unsize<Bar<U>>, if the last field of Foo has type Bar<T>
241 (
242 ty_app!(TypeCtor::Adt(AdtId::StructId(struct1)), st1),
243 ty_app!(TypeCtor::Adt(AdtId::StructId(struct2)), st2),
244 ) if struct1 == struct2 => {
245 let field_tys = self.db.field_types((*struct1).into());
246 let struct_data = self.db.struct_data(*struct1);
247
248 let mut fields = struct_data.variant_data.fields().iter();
249 let (last_field_id, _data) = fields.next_back()?;
250
251 // Get the generic parameter involved in the last field.
252 let unsize_generic_index = {
253 let mut index = None;
254 let mut multiple_param = false;
255 field_tys[last_field_id].value.walk(&mut |ty| {
256 if let &Ty::Bound(idx) = ty {
257 if index.is_none() {
258 index = Some(idx);
259 } else if Some(idx) != index {
260 multiple_param = true;
261 }
262 }
263 });
264
265 if multiple_param {
266 return None;
267 }
268 index?
269 };
270
271 // Check other fields do not involve it.
272 let mut multiple_used = false;
273 fields.for_each(|(field_id, _data)| {
274 field_tys[field_id].value.walk(&mut |ty| match ty {
275 &Ty::Bound(idx) if idx == unsize_generic_index => multiple_used = true,
276 _ => {}
277 })
278 });
279 if multiple_used {
280 return None;
281 }
282
283 let unsize_generic_index = unsize_generic_index as usize;
284
285 // Check `Unsize` first
286 match self.check_unsize_and_coerce(
287 st1.get(unsize_generic_index)?,
288 st2.get(unsize_generic_index)?,
289 depth + 1,
290 ) {
291 Some(true) => {}
292 ret => return ret,
293 }
294
295 // Then unify other parameters
296 let ret = st1
297 .iter()
298 .zip(st2.iter())
299 .enumerate()
300 .filter(|&(idx, _)| idx != unsize_generic_index)
301 .all(|(_, (ty1, ty2))| self.unify(ty1, ty2));
302
303 Some(ret)
304 } 150 }
151 _ => return None,
152 };
305 153
306 _ => None, 154 Some(true)
307 }
308 } 155 }
309 156
310 /// Unify `from_ty` to `to_ty` with optional auto Deref 157 /// Unify `from_ty` to `to_ty` with optional auto Deref
diff --git a/crates/ra_hir_ty/src/infer/unify.rs b/crates/ra_hir_ty/src/infer/unify.rs
index 2d03c5c33..aed527fe5 100644
--- a/crates/ra_hir_ty/src/infer/unify.rs
+++ b/crates/ra_hir_ty/src/infer/unify.rs
@@ -7,10 +7,7 @@ use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue};
7use test_utils::tested_by; 7use test_utils::tested_by;
8 8
9use super::{InferenceContext, Obligation}; 9use super::{InferenceContext, Obligation};
10use crate::{ 10use crate::{db::HirDatabase, Canonical, InEnvironment, InferTy, Substs, Ty, TypeCtor, TypeWalk};
11 db::HirDatabase, utils::make_mut_slice, Canonical, InEnvironment, InferTy, ProjectionPredicate,
12 ProjectionTy, Substs, TraitRef, Ty, TypeCtor, TypeWalk,
13};
14 11
15impl<'a, D: HirDatabase> InferenceContext<'a, D> { 12impl<'a, D: HirDatabase> InferenceContext<'a, D> {
16 pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b, D> 13 pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b, D>
@@ -50,42 +47,38 @@ where
50 }) 47 })
51 } 48 }
52 49
53 fn do_canonicalize_ty(&mut self, ty: Ty) -> Ty { 50 fn do_canonicalize<T: TypeWalk>(&mut self, t: T, binders: usize) -> T {
54 ty.fold(&mut |ty| match ty { 51 t.fold_binders(
55 Ty::Infer(tv) => { 52 &mut |ty, binders| match ty {
56 let inner = tv.to_inner(); 53 Ty::Infer(tv) => {
57 if self.var_stack.contains(&inner) { 54 let inner = tv.to_inner();
58 // recursive type 55 if self.var_stack.contains(&inner) {
59 return tv.fallback_value(); 56 // recursive type
60 } 57 return tv.fallback_value();
61 if let Some(known_ty) = 58 }
62 self.ctx.table.var_unification_table.inlined_probe_value(inner).known() 59 if let Some(known_ty) =
63 { 60 self.ctx.table.var_unification_table.inlined_probe_value(inner).known()
64 self.var_stack.push(inner); 61 {
65 let result = self.do_canonicalize_ty(known_ty.clone()); 62 self.var_stack.push(inner);
66 self.var_stack.pop(); 63 let result = self.do_canonicalize(known_ty.clone(), binders);
67 result 64 self.var_stack.pop();
68 } else { 65 result
69 let root = self.ctx.table.var_unification_table.find(inner); 66 } else {
70 let free_var = match tv { 67 let root = self.ctx.table.var_unification_table.find(inner);
71 InferTy::TypeVar(_) => InferTy::TypeVar(root), 68 let free_var = match tv {
72 InferTy::IntVar(_) => InferTy::IntVar(root), 69 InferTy::TypeVar(_) => InferTy::TypeVar(root),
73 InferTy::FloatVar(_) => InferTy::FloatVar(root), 70 InferTy::IntVar(_) => InferTy::IntVar(root),
74 InferTy::MaybeNeverTypeVar(_) => InferTy::MaybeNeverTypeVar(root), 71 InferTy::FloatVar(_) => InferTy::FloatVar(root),
75 }; 72 InferTy::MaybeNeverTypeVar(_) => InferTy::MaybeNeverTypeVar(root),
76 let position = self.add(free_var); 73 };
77 Ty::Bound(position as u32) 74 let position = self.add(free_var);
75 Ty::Bound((position + binders) as u32)
76 }
78 } 77 }
79 } 78 _ => ty,
80 _ => ty, 79 },
81 }) 80 binders,
82 } 81 )
83
84 fn do_canonicalize_trait_ref(&mut self, mut trait_ref: TraitRef) -> TraitRef {
85 for ty in make_mut_slice(&mut trait_ref.substs.0) {
86 *ty = self.do_canonicalize_ty(ty.clone());
87 }
88 trait_ref
89 } 82 }
90 83
91 fn into_canonicalized<T>(self, result: T) -> Canonicalized<T> { 84 fn into_canonicalized<T>(self, result: T) -> Canonicalized<T> {
@@ -95,28 +88,8 @@ where
95 } 88 }
96 } 89 }
97 90
98 fn do_canonicalize_projection_ty(&mut self, mut projection_ty: ProjectionTy) -> ProjectionTy {
99 for ty in make_mut_slice(&mut projection_ty.parameters.0) {
100 *ty = self.do_canonicalize_ty(ty.clone());
101 }
102 projection_ty
103 }
104
105 fn do_canonicalize_projection_predicate(
106 &mut self,
107 projection: ProjectionPredicate,
108 ) -> ProjectionPredicate {
109 let ty = self.do_canonicalize_ty(projection.ty);
110 let projection_ty = self.do_canonicalize_projection_ty(projection.projection_ty);
111
112 ProjectionPredicate { ty, projection_ty }
113 }
114
115 // FIXME: add some point, we need to introduce a `Fold` trait that abstracts
116 // over all the things that can be canonicalized (like Chalk and rustc have)
117
118 pub(crate) fn canonicalize_ty(mut self, ty: Ty) -> Canonicalized<Ty> { 91 pub(crate) fn canonicalize_ty(mut self, ty: Ty) -> Canonicalized<Ty> {
119 let result = self.do_canonicalize_ty(ty); 92 let result = self.do_canonicalize(ty, 0);
120 self.into_canonicalized(result) 93 self.into_canonicalized(result)
121 } 94 }
122 95
@@ -125,10 +98,8 @@ where
125 obligation: InEnvironment<Obligation>, 98 obligation: InEnvironment<Obligation>,
126 ) -> Canonicalized<InEnvironment<Obligation>> { 99 ) -> Canonicalized<InEnvironment<Obligation>> {
127 let result = match obligation.value { 100 let result = match obligation.value {
128 Obligation::Trait(tr) => Obligation::Trait(self.do_canonicalize_trait_ref(tr)), 101 Obligation::Trait(tr) => Obligation::Trait(self.do_canonicalize(tr, 0)),
129 Obligation::Projection(pr) => { 102 Obligation::Projection(pr) => Obligation::Projection(self.do_canonicalize(pr, 0)),
130 Obligation::Projection(self.do_canonicalize_projection_predicate(pr))
131 }
132 }; 103 };
133 self.into_canonicalized(InEnvironment { 104 self.into_canonicalized(InEnvironment {
134 value: result, 105 value: result,
diff --git a/crates/ra_hir_ty/src/lib.rs b/crates/ra_hir_ty/src/lib.rs
index 13c5e6c6b..0009c426c 100644
--- a/crates/ra_hir_ty/src/lib.rs
+++ b/crates/ra_hir_ty/src/lib.rs
@@ -461,6 +461,12 @@ impl<T> Binders<T> {
461 } 461 }
462} 462}
463 463
464impl<T: Clone> Binders<&T> {
465 pub fn cloned(&self) -> Binders<T> {
466 Binders { num_binders: self.num_binders, value: self.value.clone() }
467 }
468}
469
464impl<T: TypeWalk> Binders<T> { 470impl<T: TypeWalk> Binders<T> {
465 /// Substitutes all variables. 471 /// Substitutes all variables.
466 pub fn subst(self, subst: &Substs) -> T { 472 pub fn subst(self, subst: &Substs) -> T {
@@ -661,6 +667,17 @@ impl Ty {
661 } 667 }
662 } 668 }
663 669
670 /// If this is a `dyn Trait` type, this returns the `Trait` part.
671 pub fn dyn_trait_ref(&self) -> Option<&TraitRef> {
672 match self {
673 Ty::Dyn(bounds) => bounds.get(0).and_then(|b| match b {
674 GenericPredicate::Implemented(trait_ref) => Some(trait_ref),
675 _ => None,
676 }),
677 _ => None,
678 }
679 }
680
664 fn builtin_deref(&self) -> Option<Ty> { 681 fn builtin_deref(&self) -> Option<Ty> {
665 match self { 682 match self {
666 Ty::Apply(a_ty) => match a_ty.ctor { 683 Ty::Apply(a_ty) => match a_ty.ctor {
@@ -746,6 +763,20 @@ pub trait TypeWalk {
746 /// variable for the self type. 763 /// variable for the self type.
747 fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize); 764 fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize);
748 765
766 fn fold_binders(mut self, f: &mut impl FnMut(Ty, usize) -> Ty, binders: usize) -> Self
767 where
768 Self: Sized,
769 {
770 self.walk_mut_binders(
771 &mut |ty_mut, binders| {
772 let ty = mem::replace(ty_mut, Ty::Unknown);
773 *ty_mut = f(ty, binders);
774 },
775 binders,
776 );
777 self
778 }
779
749 fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self 780 fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self
750 where 781 where
751 Self: Sized, 782 Self: Sized,
@@ -783,13 +814,16 @@ pub trait TypeWalk {
783 where 814 where
784 Self: Sized, 815 Self: Sized,
785 { 816 {
786 self.fold(&mut |ty| match ty { 817 self.fold_binders(
787 Ty::Bound(idx) => { 818 &mut |ty, binders| match ty {
788 assert!(idx as i32 >= -n); 819 Ty::Bound(idx) if idx as usize >= binders => {
789 Ty::Bound((idx as i32 + n) as u32) 820 assert!(idx as i32 >= -n);
790 } 821 Ty::Bound((idx as i32 + n) as u32)
791 ty => ty, 822 }
792 }) 823 ty => ty,
824 },
825 0,
826 )
793 } 827 }
794} 828}
795 829
diff --git a/crates/ra_hir_ty/src/lower.rs b/crates/ra_hir_ty/src/lower.rs
index 52da34574..092977e93 100644
--- a/crates/ra_hir_ty/src/lower.rs
+++ b/crates/ra_hir_ty/src/lower.rs
@@ -239,7 +239,10 @@ impl Ty {
239 ) -> Ty { 239 ) -> Ty {
240 let ty = match resolution { 240 let ty = match resolution {
241 TypeNs::TraitId(trait_) => { 241 TypeNs::TraitId(trait_) => {
242 let trait_ref = TraitRef::from_resolved_path(ctx, trait_, resolved_segment, None); 242 // if this is a bare dyn Trait, we'll directly put the required ^0 for the self type in there
243 let self_ty = if remaining_segments.len() == 0 { Some(Ty::Bound(0)) } else { None };
244 let trait_ref =
245 TraitRef::from_resolved_path(ctx, trait_, resolved_segment, self_ty);
243 return if remaining_segments.len() == 1 { 246 return if remaining_segments.len() == 1 {
244 let segment = remaining_segments.first().unwrap(); 247 let segment = remaining_segments.first().unwrap();
245 let associated_ty = associated_type_by_name_including_super_traits( 248 let associated_ty = associated_type_by_name_including_super_traits(
diff --git a/crates/ra_hir_ty/src/tests/coercion.rs b/crates/ra_hir_ty/src/tests/coercion.rs
index 42330b269..60ad6e9be 100644
--- a/crates/ra_hir_ty/src/tests/coercion.rs
+++ b/crates/ra_hir_ty/src/tests/coercion.rs
@@ -548,3 +548,141 @@ impl<TT> S<TT> {
548 "### 548 "###
549 ); 549 );
550} 550}
551
552#[test]
553fn coerce_unsize_array() {
554 assert_snapshot!(
555 infer_with_mismatches(r#"
556#[lang = "unsize"]
557pub trait Unsize<T> {}
558#[lang = "coerce_unsized"]
559pub trait CoerceUnsized<T> {}
560
561impl<T: Unsize<U>, U> CoerceUnsized<&U> for &T {}
562
563fn test() {
564 let f: &[usize] = &[1, 2, 3];
565}
566"#, true),
567 @r###"
568 [162; 199) '{ ... 3]; }': ()
569 [172; 173) 'f': &[usize]
570 [186; 196) '&[1, 2, 3]': &[usize; _]
571 [187; 196) '[1, 2, 3]': [usize; _]
572 [188; 189) '1': usize
573 [191; 192) '2': usize
574 [194; 195) '3': usize
575 "###
576 );
577}
578
579#[test]
580fn coerce_unsize_trait_object() {
581 assert_snapshot!(
582 infer_with_mismatches(r#"
583#[lang = "unsize"]
584pub trait Unsize<T> {}
585#[lang = "coerce_unsized"]
586pub trait CoerceUnsized<T> {}
587
588impl<T: Unsize<U>, U> CoerceUnsized<&U> for &T {}
589
590trait Foo<T, U> {}
591trait Bar<U, T, X>: Foo<T, U> {}
592trait Baz<T, X>: Bar<usize, T, X> {}
593
594struct S<T, X>;
595impl<T, X> Foo<T, usize> for S<T, X> {}
596impl<T, X> Bar<usize, T, X> for S<T, X> {}
597impl<T, X> Baz<T, X> for S<T, X> {}
598
599fn test() {
600 let obj: &dyn Baz<i8, i16> = &S;
601 let obj: &dyn Bar<_, _, _> = obj;
602 let obj: &dyn Foo<_, _> = obj;
603 let obj2: &dyn Baz<i8, i16> = &S;
604 let _: &dyn Foo<_, _> = obj2;
605}
606"#, true),
607 @r###"
608 [388; 573) '{ ...bj2; }': ()
609 [398; 401) 'obj': &dyn Baz<i8, i16>
610 [423; 425) '&S': &S<i8, i16>
611 [424; 425) 'S': S<i8, i16>
612 [435; 438) 'obj': &dyn Bar<usize, i8, i16>
613 [460; 463) 'obj': &dyn Baz<i8, i16>
614 [473; 476) 'obj': &dyn Foo<i8, usize>
615 [495; 498) 'obj': &dyn Bar<usize, i8, i16>
616 [508; 512) 'obj2': &dyn Baz<i8, i16>
617 [534; 536) '&S': &S<i8, i16>
618 [535; 536) 'S': S<i8, i16>
619 [546; 547) '_': &dyn Foo<i8, usize>
620 [566; 570) 'obj2': &dyn Baz<i8, i16>
621 "###
622 );
623}
624
625#[test]
626fn coerce_unsize_super_trait_cycle() {
627 assert_snapshot!(
628 infer_with_mismatches(r#"
629#[lang = "unsize"]
630pub trait Unsize<T> {}
631#[lang = "coerce_unsized"]
632pub trait CoerceUnsized<T> {}
633
634impl<T: Unsize<U>, U> CoerceUnsized<&U> for &T {}
635
636trait A {}
637trait B: C + A {}
638trait C: B {}
639trait D: C
640
641struct S;
642impl A for S {}
643impl B for S {}
644impl C for S {}
645impl D for S {}
646
647fn test() {
648 let obj: &dyn D = &S;
649 let obj: &dyn A = obj;
650}
651"#, true),
652 @r###"
653 [292; 348) '{ ...obj; }': ()
654 [302; 305) 'obj': &dyn D
655 [316; 318) '&S': &S
656 [317; 318) 'S': S
657 [328; 331) 'obj': &dyn A
658 [342; 345) 'obj': &dyn D
659 "###
660 );
661}
662
663#[ignore]
664#[test]
665fn coerce_unsize_generic() {
666 // FIXME: Implement this
667 // https://doc.rust-lang.org/reference/type-coercions.html#unsized-coercions
668 assert_snapshot!(
669 infer_with_mismatches(r#"
670#[lang = "unsize"]
671pub trait Unsize<T> {}
672#[lang = "coerce_unsized"]
673pub trait CoerceUnsized<T> {}
674
675impl<T: Unsize<U>, U> CoerceUnsized<&U> for &T {}
676
677struct Foo<T> { t: T };
678struct Bar<T>(Foo<T>);
679
680fn test() {
681 let _: &Foo<[usize]> = &Foo { t: [1, 2, 3] };
682 let _: &Bar<[usize]> = &Bar(Foo { t: [1, 2, 3] });
683}
684"#, true),
685 @r###"
686 "###
687 );
688}
diff --git a/crates/ra_hir_ty/src/traits.rs b/crates/ra_hir_ty/src/traits.rs
index e83449957..2317fcac3 100644
--- a/crates/ra_hir_ty/src/traits.rs
+++ b/crates/ra_hir_ty/src/traits.rs
@@ -335,6 +335,12 @@ pub struct ClosureFnTraitImplData {
335 fn_trait: FnTrait, 335 fn_trait: FnTrait,
336} 336}
337 337
338#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
339pub struct UnsizeToSuperTraitObjectData {
340 trait_: TraitId,
341 super_trait: TraitId,
342}
343
338/// An impl. Usually this comes from an impl block, but some built-in types get 344/// An impl. Usually this comes from an impl block, but some built-in types get
339/// synthetic impls. 345/// synthetic impls.
340#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] 346#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
@@ -343,6 +349,12 @@ pub enum Impl {
343 ImplBlock(ImplId), 349 ImplBlock(ImplId),
344 /// Closure types implement the Fn traits synthetically. 350 /// Closure types implement the Fn traits synthetically.
345 ClosureFnTraitImpl(ClosureFnTraitImplData), 351 ClosureFnTraitImpl(ClosureFnTraitImplData),
352 /// [T; n]: Unsize<[T]>
353 UnsizeArray,
354 /// T: Unsize<dyn Trait> where T: Trait
355 UnsizeToTraitObject(TraitId),
356 /// dyn Trait: Unsize<dyn SuperTrait> if Trait: SuperTrait
357 UnsizeToSuperTraitObject(UnsizeToSuperTraitObjectData),
346} 358}
347/// This exists just for Chalk, because our ImplIds are only unique per module. 359/// This exists just for Chalk, because our ImplIds are only unique per module.
348#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] 360#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
diff --git a/crates/ra_hir_ty/src/traits/builtin.rs b/crates/ra_hir_ty/src/traits/builtin.rs
index a537420a5..cc0f3eeb4 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};
4use hir_expand::name::name; 4use hir_expand::name::name;
5use ra_db::CrateId; 5use ra_db::CrateId;
6 6
7use super::{AssocTyValue, Impl}; 7use super::{AssocTyValue, Impl, UnsizeToSuperTraitObjectData};
8use crate::{db::HirDatabase, ApplicationTy, Substs, TraitRef, Ty, TypeCtor}; 8use crate::{
9 db::HirDatabase,
10 utils::{all_super_traits, generics},
11 ApplicationTy, Binders, GenericPredicate, Substs, TraitRef, Ty, TypeCtor,
12};
9 13
10pub(super) struct BuiltinImplData { 14pub(super) struct BuiltinImplData {
11 pub num_vars: usize, 15 pub num_vars: usize,
@@ -25,6 +29,8 @@ pub(super) fn get_builtin_impls(
25 db: &impl HirDatabase, 29 db: &impl HirDatabase,
26 krate: CrateId, 30 krate: CrateId,
27 ty: &Ty, 31 ty: &Ty,
32 // The first argument for the trait, if present
33 arg: &Option<Ty>,
28 trait_: TraitId, 34 trait_: TraitId,
29 mut callback: impl FnMut(Impl), 35 mut callback: impl FnMut(Impl),
30) { 36) {
@@ -43,12 +49,60 @@ pub(super) fn get_builtin_impls(
43 } 49 }
44 } 50 }
45 } 51 }
52
53 let unsize_trait = get_unsize_trait(db, krate);
54 if let Some(actual_trait) = unsize_trait {
55 if trait_ == actual_trait {
56 get_builtin_unsize_impls(db, krate, ty, arg, callback);
57 }
58 }
59}
60
61fn get_builtin_unsize_impls(
62 db: &impl HirDatabase,
63 krate: CrateId,
64 ty: &Ty,
65 // The first argument for the trait, if present
66 arg: &Option<Ty>,
67 mut callback: impl FnMut(Impl),
68) {
69 if !check_unsize_impl_prerequisites(db, krate) {
70 return;
71 }
72
73 if let Ty::Apply(ApplicationTy { ctor: TypeCtor::Array, .. }) = ty {
74 callback(Impl::UnsizeArray);
75 return; // array is unsized, the rest of the impls shouldn't apply
76 }
77
78 if let Some(target_trait) = arg.as_ref().and_then(|t| t.dyn_trait_ref()) {
79 // FIXME what about more complicated dyn tys with marker traits?
80 if let Some(trait_ref) = ty.dyn_trait_ref() {
81 if trait_ref.trait_ != target_trait.trait_ {
82 let super_traits = all_super_traits(db, trait_ref.trait_);
83 if super_traits.contains(&target_trait.trait_) {
84 callback(Impl::UnsizeToSuperTraitObject(UnsizeToSuperTraitObjectData {
85 trait_: trait_ref.trait_,
86 super_trait: target_trait.trait_,
87 }));
88 }
89 }
90 } else {
91 // FIXME only for sized types
92 callback(Impl::UnsizeToTraitObject(target_trait.trait_));
93 }
94 }
46} 95}
47 96
48pub(super) fn impl_datum(db: &impl HirDatabase, krate: CrateId, impl_: Impl) -> BuiltinImplData { 97pub(super) fn impl_datum(db: &impl HirDatabase, krate: CrateId, impl_: Impl) -> BuiltinImplData {
49 match impl_ { 98 match impl_ {
50 Impl::ImplBlock(_) => unreachable!(), 99 Impl::ImplBlock(_) => unreachable!(),
51 Impl::ClosureFnTraitImpl(data) => closure_fn_trait_impl_datum(db, krate, data), 100 Impl::ClosureFnTraitImpl(data) => closure_fn_trait_impl_datum(db, krate, data),
101 Impl::UnsizeArray => array_unsize_impl_datum(db, krate),
102 Impl::UnsizeToTraitObject(trait_) => trait_object_unsize_impl_datum(db, krate, trait_),
103 Impl::UnsizeToSuperTraitObject(data) => {
104 super_trait_object_unsize_impl_datum(db, krate, data)
105 }
52 } 106 }
53} 107}
54 108
@@ -65,6 +119,8 @@ pub(super) fn associated_ty_value(
65 } 119 }
66} 120}
67 121
122// Closure Fn trait impls
123
68fn check_closure_fn_trait_impl_prerequisites( 124fn check_closure_fn_trait_impl_prerequisites(
69 db: &impl HirDatabase, 125 db: &impl HirDatabase,
70 krate: CrateId, 126 krate: CrateId,
@@ -165,6 +221,129 @@ fn closure_fn_trait_output_assoc_ty_value(
165 } 221 }
166} 222}
167 223
224// Array unsizing
225
226fn check_unsize_impl_prerequisites(db: &impl HirDatabase, krate: CrateId) -> bool {
227 // the Unsize trait needs to exist and have two type parameters (Self and T)
228 let unsize_trait = match get_unsize_trait(db, krate) {
229 Some(t) => t,
230 None => return false,
231 };
232 let generic_params = generics(db, unsize_trait.into());
233 generic_params.len() == 2
234}
235
236fn array_unsize_impl_datum(db: &impl HirDatabase, krate: CrateId) -> BuiltinImplData {
237 // impl<T> Unsize<[T]> for [T; _]
238 // (this can be a single impl because we don't distinguish array sizes currently)
239
240 let trait_ = get_unsize_trait(db, krate) // get unsize trait
241 // the existence of the Unsize trait has been checked before
242 .expect("Unsize trait missing");
243
244 let var = Ty::Bound(0);
245 let substs = Substs::builder(2)
246 .push(Ty::apply_one(TypeCtor::Array, var.clone()))
247 .push(Ty::apply_one(TypeCtor::Slice, var))
248 .build();
249
250 let trait_ref = TraitRef { trait_, substs };
251
252 BuiltinImplData {
253 num_vars: 1,
254 trait_ref,
255 where_clauses: Vec::new(),
256 assoc_ty_values: Vec::new(),
257 }
258}
259
260// Trait object unsizing
261
262fn trait_object_unsize_impl_datum(
263 db: &impl HirDatabase,
264 krate: CrateId,
265 trait_: TraitId,
266) -> BuiltinImplData {
267 // impl<T, T1, ...> Unsize<dyn Trait<T1, ...>> for T where T: Trait<T1, ...>
268
269 let unsize_trait = get_unsize_trait(db, krate) // get unsize trait
270 // the existence of the Unsize trait has been checked before
271 .expect("Unsize trait missing");
272
273 let self_ty = Ty::Bound(0);
274
275 let target_substs = Substs::build_for_def(db, trait_)
276 .push(Ty::Bound(0))
277 // starting from ^2 because we want to start with ^1 outside of the
278 // `dyn`, which is ^2 inside
279 .fill_with_bound_vars(2)
280 .build();
281 let num_vars = target_substs.len();
282 let target_trait_ref = TraitRef { trait_, substs: target_substs };
283 let target_bounds = vec![GenericPredicate::Implemented(target_trait_ref)];
284
285 let self_substs = Substs::build_for_def(db, trait_).fill_with_bound_vars(0).build();
286 let self_trait_ref = TraitRef { trait_, substs: self_substs };
287 let where_clauses = vec![GenericPredicate::Implemented(self_trait_ref)];
288
289 let impl_substs =
290 Substs::builder(2).push(self_ty).push(Ty::Dyn(target_bounds.clone().into())).build();
291
292 let trait_ref = TraitRef { trait_: unsize_trait, substs: impl_substs };
293
294 BuiltinImplData { num_vars, trait_ref, where_clauses, assoc_ty_values: Vec::new() }
295}
296
297fn super_trait_object_unsize_impl_datum(
298 db: &impl HirDatabase,
299 krate: CrateId,
300 data: UnsizeToSuperTraitObjectData,
301) -> BuiltinImplData {
302 // impl<T1, ...> Unsize<dyn SuperTrait> for dyn Trait<T1, ...>
303
304 let unsize_trait = get_unsize_trait(db, krate) // get unsize trait
305 // the existence of the Unsize trait has been checked before
306 .expect("Unsize trait missing");
307
308 let self_substs = Substs::build_for_def(db, data.trait_).fill_with_bound_vars(0).build();
309
310 let num_vars = self_substs.len() - 1;
311
312 let self_trait_ref = TraitRef { trait_: data.trait_, substs: self_substs.clone() };
313 let self_bounds = vec![GenericPredicate::Implemented(self_trait_ref.clone())];
314
315 // we need to go from our trait to the super trait, substituting type parameters
316 let path = crate::utils::find_super_trait_path(db, data.trait_, data.super_trait);
317
318 let mut current_trait_ref = self_trait_ref;
319 for t in path.into_iter().skip(1) {
320 let bounds = db.generic_predicates(current_trait_ref.trait_.into());
321 let super_trait_ref = bounds
322 .iter()
323 .find_map(|b| match &b.value {
324 GenericPredicate::Implemented(tr)
325 if tr.trait_ == t && tr.substs[0] == Ty::Bound(0) =>
326 {
327 Some(Binders { value: tr, num_binders: b.num_binders })
328 }
329 _ => None,
330 })
331 .expect("trait bound for known super trait not found");
332 current_trait_ref = super_trait_ref.cloned().subst(&current_trait_ref.substs);
333 }
334
335 let super_bounds = vec![GenericPredicate::Implemented(current_trait_ref)];
336
337 let substs = Substs::builder(2)
338 .push(Ty::Dyn(self_bounds.into()))
339 .push(Ty::Dyn(super_bounds.into()))
340 .build();
341
342 let trait_ref = TraitRef { trait_: unsize_trait, substs };
343
344 BuiltinImplData { num_vars, trait_ref, where_clauses: Vec::new(), assoc_ty_values: Vec::new() }
345}
346
168fn get_fn_trait( 347fn get_fn_trait(
169 db: &impl HirDatabase, 348 db: &impl HirDatabase,
170 krate: CrateId, 349 krate: CrateId,
@@ -176,3 +355,11 @@ fn get_fn_trait(
176 _ => None, 355 _ => None,
177 } 356 }
178} 357}
358
359fn get_unsize_trait(db: &impl HirDatabase, krate: CrateId) -> Option<TraitId> {
360 let target = db.lang_item(krate, "unsize".into())?;
361 match target {
362 LangItemTarget::TraitId(t) => Some(t),
363 _ => None,
364 }
365}
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
572 .collect(); 572 .collect();
573 573
574 let ty: Ty = from_chalk(self.db, parameters[0].assert_ty_ref().clone()); 574 let ty: Ty = from_chalk(self.db, parameters[0].assert_ty_ref().clone());
575 let arg: Option<Ty> =
576 parameters.get(1).map(|p| from_chalk(self.db, p.assert_ty_ref().clone()));
575 577
576 builtin::get_builtin_impls(self.db, self.krate, &ty, trait_, |i| { 578 builtin::get_builtin_impls(self.db, self.krate, &ty, &arg, trait_, |i| {
577 result.push(i.to_chalk(self.db)) 579 result.push(i.to_chalk(self.db))
578 }); 580 });
579 581
diff --git a/crates/ra_hir_ty/src/utils.rs b/crates/ra_hir_ty/src/utils.rs
index 508ae9046..463fd65b4 100644
--- a/crates/ra_hir_ty/src/utils.rs
+++ b/crates/ra_hir_ty/src/utils.rs
@@ -62,6 +62,38 @@ pub(super) fn all_super_traits(db: &impl DefDatabase, trait_: TraitId) -> Vec<Tr
62 result 62 result
63} 63}
64 64
65/// Finds a path from a trait to one of its super traits. Returns an empty
66/// vector if there is no path.
67pub(super) fn find_super_trait_path(
68 db: &impl DefDatabase,
69 trait_: TraitId,
70 super_trait: TraitId,
71) -> Vec<TraitId> {
72 let mut result = Vec::with_capacity(2);
73 result.push(trait_);
74 return if go(db, super_trait, &mut result) { result } else { Vec::new() };
75
76 fn go(db: &impl DefDatabase, super_trait: TraitId, path: &mut Vec<TraitId>) -> bool {
77 let trait_ = *path.last().unwrap();
78 if trait_ == super_trait {
79 return true;
80 }
81
82 for tt in direct_super_traits(db, trait_) {
83 if path.contains(&tt) {
84 continue;
85 }
86 path.push(tt);
87 if go(db, super_trait, path) {
88 return true;
89 } else {
90 path.pop();
91 }
92 }
93 false
94 }
95}
96
65pub(super) fn associated_type_by_name_including_super_traits( 97pub(super) fn associated_type_by_name_including_super_traits(
66 db: &impl DefDatabase, 98 db: &impl DefDatabase,
67 trait_: TraitId, 99 trait_: TraitId,