diff options
Diffstat (limited to 'crates/ra_hir_ty/src/infer')
-rw-r--r-- | crates/ra_hir_ty/src/infer/coerce.rs | 205 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/infer/unify.rs | 99 |
2 files changed, 61 insertions, 243 deletions
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 | ||
7 | use hir_def::{lang_item::LangItemTarget, resolver::Resolver, type_ref::Mutability, AdtId}; | 7 | use hir_def::{lang_item::LangItemTarget, type_ref::Mutability}; |
8 | use rustc_hash::FxHashMap; | ||
9 | use test_utils::tested_by; | 8 | use test_utils::tested_by; |
10 | 9 | ||
11 | use crate::{autoderef, db::HirDatabase, Substs, Ty, TypeCtor, TypeWalk}; | 10 | use crate::{ |
11 | autoderef, db::HirDatabase, traits::Solution, Obligation, Substs, TraitRef, Ty, TypeCtor, | ||
12 | }; | ||
12 | 13 | ||
13 | use super::{unify::TypeVarValue, InEnvironment, InferTy, InferenceContext}; | 14 | use 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}; | |||
7 | use test_utils::tested_by; | 7 | use test_utils::tested_by; |
8 | 8 | ||
9 | use super::{InferenceContext, Obligation}; | 9 | use super::{InferenceContext, Obligation}; |
10 | use crate::{ | 10 | use 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 | ||
15 | impl<'a, D: HirDatabase> InferenceContext<'a, D> { | 12 | impl<'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, |