diff options
author | Aleksey Kladov <[email protected]> | 2020-08-13 15:35:29 +0100 |
---|---|---|
committer | Aleksey Kladov <[email protected]> | 2020-08-13 15:35:29 +0100 |
commit | 6a77ec7bbe6ddbf663dce9529d11d1bb56c5489a (patch) | |
tree | b6e3d7e0109eb82bca75b5ebc35a7d723542b8dd /crates/ra_hir_ty/src/infer.rs | |
parent | 50f8c1ebf23f634b68529603a917e3feeda457fa (diff) |
Rename ra_hir_ty -> hir_ty
Diffstat (limited to 'crates/ra_hir_ty/src/infer.rs')
-rw-r--r-- | crates/ra_hir_ty/src/infer.rs | 802 |
1 files changed, 0 insertions, 802 deletions
diff --git a/crates/ra_hir_ty/src/infer.rs b/crates/ra_hir_ty/src/infer.rs deleted file mode 100644 index 03b00b101..000000000 --- a/crates/ra_hir_ty/src/infer.rs +++ /dev/null | |||
@@ -1,802 +0,0 @@ | |||
1 | //! Type inference, i.e. the process of walking through the code and determining | ||
2 | //! the type of each expression and pattern. | ||
3 | //! | ||
4 | //! For type inference, compare the implementations in rustc (the various | ||
5 | //! check_* methods in librustc_typeck/check/mod.rs are a good entry point) and | ||
6 | //! IntelliJ-Rust (org.rust.lang.core.types.infer). Our entry point for | ||
7 | //! inference here is the `infer` function, which infers the types of all | ||
8 | //! expressions in a given function. | ||
9 | //! | ||
10 | //! During inference, types (i.e. the `Ty` struct) can contain type 'variables' | ||
11 | //! which represent currently unknown types; as we walk through the expressions, | ||
12 | //! we might determine that certain variables need to be equal to each other, or | ||
13 | //! to certain types. To record this, we use the union-find implementation from | ||
14 | //! the `ena` crate, which is extracted from rustc. | ||
15 | |||
16 | use std::borrow::Cow; | ||
17 | use std::mem; | ||
18 | use std::ops::Index; | ||
19 | use std::sync::Arc; | ||
20 | |||
21 | use arena::map::ArenaMap; | ||
22 | use hir_def::{ | ||
23 | body::Body, | ||
24 | data::{ConstData, FunctionData, StaticData}, | ||
25 | expr::{BindingAnnotation, ExprId, PatId}, | ||
26 | lang_item::LangItemTarget, | ||
27 | path::{path, Path}, | ||
28 | resolver::{HasResolver, Resolver, TypeNs}, | ||
29 | type_ref::{Mutability, TypeRef}, | ||
30 | AdtId, AssocItemId, DefWithBodyId, EnumVariantId, FieldId, FunctionId, Lookup, TraitId, | ||
31 | TypeAliasId, VariantId, | ||
32 | }; | ||
33 | use hir_expand::{diagnostics::DiagnosticSink, name::name}; | ||
34 | use rustc_hash::FxHashMap; | ||
35 | use stdx::impl_from; | ||
36 | use syntax::SmolStr; | ||
37 | |||
38 | use super::{ | ||
39 | primitive::{FloatTy, IntTy}, | ||
40 | traits::{Guidance, Obligation, ProjectionPredicate, Solution}, | ||
41 | InEnvironment, ProjectionTy, Substs, TraitEnvironment, TraitRef, Ty, TypeCtor, TypeWalk, | ||
42 | }; | ||
43 | use crate::{ | ||
44 | db::HirDatabase, infer::diagnostics::InferenceDiagnostic, lower::ImplTraitLoweringMode, | ||
45 | }; | ||
46 | |||
47 | pub(crate) use unify::unify; | ||
48 | |||
49 | macro_rules! ty_app { | ||
50 | ($ctor:pat, $param:pat) => { | ||
51 | crate::Ty::Apply(crate::ApplicationTy { ctor: $ctor, parameters: $param }) | ||
52 | }; | ||
53 | ($ctor:pat) => { | ||
54 | ty_app!($ctor, _) | ||
55 | }; | ||
56 | } | ||
57 | |||
58 | mod unify; | ||
59 | mod path; | ||
60 | mod expr; | ||
61 | mod pat; | ||
62 | mod coerce; | ||
63 | |||
64 | /// The entry point of type inference. | ||
65 | pub(crate) fn infer_query(db: &dyn HirDatabase, def: DefWithBodyId) -> Arc<InferenceResult> { | ||
66 | let _p = profile::span("infer_query"); | ||
67 | let resolver = def.resolver(db.upcast()); | ||
68 | let mut ctx = InferenceContext::new(db, def, resolver); | ||
69 | |||
70 | match def { | ||
71 | DefWithBodyId::ConstId(c) => ctx.collect_const(&db.const_data(c)), | ||
72 | DefWithBodyId::FunctionId(f) => ctx.collect_fn(&db.function_data(f)), | ||
73 | DefWithBodyId::StaticId(s) => ctx.collect_static(&db.static_data(s)), | ||
74 | } | ||
75 | |||
76 | ctx.infer_body(); | ||
77 | |||
78 | Arc::new(ctx.resolve_all()) | ||
79 | } | ||
80 | |||
81 | #[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)] | ||
82 | enum ExprOrPatId { | ||
83 | ExprId(ExprId), | ||
84 | PatId(PatId), | ||
85 | } | ||
86 | impl_from!(ExprId, PatId for ExprOrPatId); | ||
87 | |||
88 | /// Binding modes inferred for patterns. | ||
89 | /// https://doc.rust-lang.org/reference/patterns.html#binding-modes | ||
90 | #[derive(Copy, Clone, Debug, Eq, PartialEq)] | ||
91 | enum BindingMode { | ||
92 | Move, | ||
93 | Ref(Mutability), | ||
94 | } | ||
95 | |||
96 | impl BindingMode { | ||
97 | pub fn convert(annotation: BindingAnnotation) -> BindingMode { | ||
98 | match annotation { | ||
99 | BindingAnnotation::Unannotated | BindingAnnotation::Mutable => BindingMode::Move, | ||
100 | BindingAnnotation::Ref => BindingMode::Ref(Mutability::Shared), | ||
101 | BindingAnnotation::RefMut => BindingMode::Ref(Mutability::Mut), | ||
102 | } | ||
103 | } | ||
104 | } | ||
105 | |||
106 | impl Default for BindingMode { | ||
107 | fn default() -> Self { | ||
108 | BindingMode::Move | ||
109 | } | ||
110 | } | ||
111 | |||
112 | /// A mismatch between an expected and an inferred type. | ||
113 | #[derive(Clone, PartialEq, Eq, Debug, Hash)] | ||
114 | pub struct TypeMismatch { | ||
115 | pub expected: Ty, | ||
116 | pub actual: Ty, | ||
117 | } | ||
118 | |||
119 | /// The result of type inference: A mapping from expressions and patterns to types. | ||
120 | #[derive(Clone, PartialEq, Eq, Debug, Default)] | ||
121 | pub struct InferenceResult { | ||
122 | /// For each method call expr, records the function it resolves to. | ||
123 | method_resolutions: FxHashMap<ExprId, FunctionId>, | ||
124 | /// For each field access expr, records the field it resolves to. | ||
125 | field_resolutions: FxHashMap<ExprId, FieldId>, | ||
126 | /// For each field in record literal, records the field it resolves to. | ||
127 | record_field_resolutions: FxHashMap<ExprId, FieldId>, | ||
128 | record_field_pat_resolutions: FxHashMap<PatId, FieldId>, | ||
129 | /// For each struct literal, records the variant it resolves to. | ||
130 | variant_resolutions: FxHashMap<ExprOrPatId, VariantId>, | ||
131 | /// For each associated item record what it resolves to | ||
132 | assoc_resolutions: FxHashMap<ExprOrPatId, AssocItemId>, | ||
133 | diagnostics: Vec<InferenceDiagnostic>, | ||
134 | pub type_of_expr: ArenaMap<ExprId, Ty>, | ||
135 | pub type_of_pat: ArenaMap<PatId, Ty>, | ||
136 | pub(super) type_mismatches: ArenaMap<ExprId, TypeMismatch>, | ||
137 | } | ||
138 | |||
139 | impl InferenceResult { | ||
140 | pub fn method_resolution(&self, expr: ExprId) -> Option<FunctionId> { | ||
141 | self.method_resolutions.get(&expr).copied() | ||
142 | } | ||
143 | pub fn field_resolution(&self, expr: ExprId) -> Option<FieldId> { | ||
144 | self.field_resolutions.get(&expr).copied() | ||
145 | } | ||
146 | pub fn record_field_resolution(&self, expr: ExprId) -> Option<FieldId> { | ||
147 | self.record_field_resolutions.get(&expr).copied() | ||
148 | } | ||
149 | pub fn record_field_pat_resolution(&self, pat: PatId) -> Option<FieldId> { | ||
150 | self.record_field_pat_resolutions.get(&pat).copied() | ||
151 | } | ||
152 | pub fn variant_resolution_for_expr(&self, id: ExprId) -> Option<VariantId> { | ||
153 | self.variant_resolutions.get(&id.into()).copied() | ||
154 | } | ||
155 | pub fn variant_resolution_for_pat(&self, id: PatId) -> Option<VariantId> { | ||
156 | self.variant_resolutions.get(&id.into()).copied() | ||
157 | } | ||
158 | pub fn assoc_resolutions_for_expr(&self, id: ExprId) -> Option<AssocItemId> { | ||
159 | self.assoc_resolutions.get(&id.into()).copied() | ||
160 | } | ||
161 | pub fn assoc_resolutions_for_pat(&self, id: PatId) -> Option<AssocItemId> { | ||
162 | self.assoc_resolutions.get(&id.into()).copied() | ||
163 | } | ||
164 | pub fn type_mismatch_for_expr(&self, expr: ExprId) -> Option<&TypeMismatch> { | ||
165 | self.type_mismatches.get(expr) | ||
166 | } | ||
167 | pub fn add_diagnostics( | ||
168 | &self, | ||
169 | db: &dyn HirDatabase, | ||
170 | owner: DefWithBodyId, | ||
171 | sink: &mut DiagnosticSink, | ||
172 | ) { | ||
173 | self.diagnostics.iter().for_each(|it| it.add_to(db, owner, sink)) | ||
174 | } | ||
175 | } | ||
176 | |||
177 | impl Index<ExprId> for InferenceResult { | ||
178 | type Output = Ty; | ||
179 | |||
180 | fn index(&self, expr: ExprId) -> &Ty { | ||
181 | self.type_of_expr.get(expr).unwrap_or(&Ty::Unknown) | ||
182 | } | ||
183 | } | ||
184 | |||
185 | impl Index<PatId> for InferenceResult { | ||
186 | type Output = Ty; | ||
187 | |||
188 | fn index(&self, pat: PatId) -> &Ty { | ||
189 | self.type_of_pat.get(pat).unwrap_or(&Ty::Unknown) | ||
190 | } | ||
191 | } | ||
192 | |||
193 | /// The inference context contains all information needed during type inference. | ||
194 | #[derive(Clone, Debug)] | ||
195 | struct InferenceContext<'a> { | ||
196 | db: &'a dyn HirDatabase, | ||
197 | owner: DefWithBodyId, | ||
198 | body: Arc<Body>, | ||
199 | resolver: Resolver, | ||
200 | table: unify::InferenceTable, | ||
201 | trait_env: Arc<TraitEnvironment>, | ||
202 | obligations: Vec<Obligation>, | ||
203 | result: InferenceResult, | ||
204 | /// The return type of the function being inferred, or the closure if we're | ||
205 | /// currently within one. | ||
206 | /// | ||
207 | /// We might consider using a nested inference context for checking | ||
208 | /// closures, but currently this is the only field that will change there, | ||
209 | /// so it doesn't make sense. | ||
210 | return_ty: Ty, | ||
211 | diverges: Diverges, | ||
212 | breakables: Vec<BreakableContext>, | ||
213 | } | ||
214 | |||
215 | #[derive(Clone, Debug)] | ||
216 | struct BreakableContext { | ||
217 | pub may_break: bool, | ||
218 | pub break_ty: Ty, | ||
219 | pub label: Option<name::Name>, | ||
220 | } | ||
221 | |||
222 | fn find_breakable<'c>( | ||
223 | ctxs: &'c mut [BreakableContext], | ||
224 | label: Option<&name::Name>, | ||
225 | ) -> Option<&'c mut BreakableContext> { | ||
226 | match label { | ||
227 | Some(_) => ctxs.iter_mut().rev().find(|ctx| ctx.label.as_ref() == label), | ||
228 | None => ctxs.last_mut(), | ||
229 | } | ||
230 | } | ||
231 | |||
232 | impl<'a> InferenceContext<'a> { | ||
233 | fn new(db: &'a dyn HirDatabase, owner: DefWithBodyId, resolver: Resolver) -> Self { | ||
234 | InferenceContext { | ||
235 | result: InferenceResult::default(), | ||
236 | table: unify::InferenceTable::new(), | ||
237 | obligations: Vec::default(), | ||
238 | return_ty: Ty::Unknown, // set in collect_fn_signature | ||
239 | trait_env: TraitEnvironment::lower(db, &resolver), | ||
240 | db, | ||
241 | owner, | ||
242 | body: db.body(owner), | ||
243 | resolver, | ||
244 | diverges: Diverges::Maybe, | ||
245 | breakables: Vec::new(), | ||
246 | } | ||
247 | } | ||
248 | |||
249 | fn resolve_all(mut self) -> InferenceResult { | ||
250 | // FIXME resolve obligations as well (use Guidance if necessary) | ||
251 | let mut result = std::mem::take(&mut self.result); | ||
252 | for ty in result.type_of_expr.values_mut() { | ||
253 | let resolved = self.table.resolve_ty_completely(mem::replace(ty, Ty::Unknown)); | ||
254 | *ty = resolved; | ||
255 | } | ||
256 | for ty in result.type_of_pat.values_mut() { | ||
257 | let resolved = self.table.resolve_ty_completely(mem::replace(ty, Ty::Unknown)); | ||
258 | *ty = resolved; | ||
259 | } | ||
260 | result | ||
261 | } | ||
262 | |||
263 | fn write_expr_ty(&mut self, expr: ExprId, ty: Ty) { | ||
264 | self.result.type_of_expr.insert(expr, ty); | ||
265 | } | ||
266 | |||
267 | fn write_method_resolution(&mut self, expr: ExprId, func: FunctionId) { | ||
268 | self.result.method_resolutions.insert(expr, func); | ||
269 | } | ||
270 | |||
271 | fn write_field_resolution(&mut self, expr: ExprId, field: FieldId) { | ||
272 | self.result.field_resolutions.insert(expr, field); | ||
273 | } | ||
274 | |||
275 | fn write_variant_resolution(&mut self, id: ExprOrPatId, variant: VariantId) { | ||
276 | self.result.variant_resolutions.insert(id, variant); | ||
277 | } | ||
278 | |||
279 | fn write_assoc_resolution(&mut self, id: ExprOrPatId, item: AssocItemId) { | ||
280 | self.result.assoc_resolutions.insert(id, item); | ||
281 | } | ||
282 | |||
283 | fn write_pat_ty(&mut self, pat: PatId, ty: Ty) { | ||
284 | self.result.type_of_pat.insert(pat, ty); | ||
285 | } | ||
286 | |||
287 | fn push_diagnostic(&mut self, diagnostic: InferenceDiagnostic) { | ||
288 | self.result.diagnostics.push(diagnostic); | ||
289 | } | ||
290 | |||
291 | fn make_ty_with_mode( | ||
292 | &mut self, | ||
293 | type_ref: &TypeRef, | ||
294 | impl_trait_mode: ImplTraitLoweringMode, | ||
295 | ) -> Ty { | ||
296 | // FIXME use right resolver for block | ||
297 | let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver) | ||
298 | .with_impl_trait_mode(impl_trait_mode); | ||
299 | let ty = Ty::from_hir(&ctx, type_ref); | ||
300 | let ty = self.insert_type_vars(ty); | ||
301 | self.normalize_associated_types_in(ty) | ||
302 | } | ||
303 | |||
304 | fn make_ty(&mut self, type_ref: &TypeRef) -> Ty { | ||
305 | self.make_ty_with_mode(type_ref, ImplTraitLoweringMode::Disallowed) | ||
306 | } | ||
307 | |||
308 | /// Replaces Ty::Unknown by a new type var, so we can maybe still infer it. | ||
309 | fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty { | ||
310 | match ty { | ||
311 | Ty::Unknown => self.table.new_type_var(), | ||
312 | _ => ty, | ||
313 | } | ||
314 | } | ||
315 | |||
316 | fn insert_type_vars(&mut self, ty: Ty) -> Ty { | ||
317 | ty.fold(&mut |ty| self.insert_type_vars_shallow(ty)) | ||
318 | } | ||
319 | |||
320 | fn resolve_obligations_as_possible(&mut self) { | ||
321 | let obligations = mem::replace(&mut self.obligations, Vec::new()); | ||
322 | for obligation in obligations { | ||
323 | let in_env = InEnvironment::new(self.trait_env.clone(), obligation.clone()); | ||
324 | let canonicalized = self.canonicalizer().canonicalize_obligation(in_env); | ||
325 | let solution = | ||
326 | self.db.trait_solve(self.resolver.krate().unwrap(), canonicalized.value.clone()); | ||
327 | |||
328 | match solution { | ||
329 | Some(Solution::Unique(substs)) => { | ||
330 | canonicalized.apply_solution(self, substs.0); | ||
331 | } | ||
332 | Some(Solution::Ambig(Guidance::Definite(substs))) => { | ||
333 | canonicalized.apply_solution(self, substs.0); | ||
334 | self.obligations.push(obligation); | ||
335 | } | ||
336 | Some(_) => { | ||
337 | // FIXME use this when trying to resolve everything at the end | ||
338 | self.obligations.push(obligation); | ||
339 | } | ||
340 | None => { | ||
341 | // FIXME obligation cannot be fulfilled => diagnostic | ||
342 | } | ||
343 | }; | ||
344 | } | ||
345 | } | ||
346 | |||
347 | fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool { | ||
348 | self.table.unify(ty1, ty2) | ||
349 | } | ||
350 | |||
351 | /// Resolves the type as far as currently possible, replacing type variables | ||
352 | /// by their known types. All types returned by the infer_* functions should | ||
353 | /// be resolved as far as possible, i.e. contain no type variables with | ||
354 | /// known type. | ||
355 | fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty { | ||
356 | self.resolve_obligations_as_possible(); | ||
357 | |||
358 | self.table.resolve_ty_as_possible(ty) | ||
359 | } | ||
360 | |||
361 | fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> { | ||
362 | self.table.resolve_ty_shallow(ty) | ||
363 | } | ||
364 | |||
365 | fn resolve_associated_type(&mut self, inner_ty: Ty, assoc_ty: Option<TypeAliasId>) -> Ty { | ||
366 | self.resolve_associated_type_with_params(inner_ty, assoc_ty, &[]) | ||
367 | } | ||
368 | |||
369 | fn resolve_associated_type_with_params( | ||
370 | &mut self, | ||
371 | inner_ty: Ty, | ||
372 | assoc_ty: Option<TypeAliasId>, | ||
373 | params: &[Ty], | ||
374 | ) -> Ty { | ||
375 | match assoc_ty { | ||
376 | Some(res_assoc_ty) => { | ||
377 | let trait_ = match res_assoc_ty.lookup(self.db.upcast()).container { | ||
378 | hir_def::AssocContainerId::TraitId(trait_) => trait_, | ||
379 | _ => panic!("resolve_associated_type called with non-associated type"), | ||
380 | }; | ||
381 | let ty = self.table.new_type_var(); | ||
382 | let substs = Substs::build_for_def(self.db, res_assoc_ty) | ||
383 | .push(inner_ty) | ||
384 | .fill(params.iter().cloned()) | ||
385 | .build(); | ||
386 | let trait_ref = TraitRef { trait_, substs: substs.clone() }; | ||
387 | let projection = ProjectionPredicate { | ||
388 | ty: ty.clone(), | ||
389 | projection_ty: ProjectionTy { associated_ty: res_assoc_ty, parameters: substs }, | ||
390 | }; | ||
391 | self.obligations.push(Obligation::Trait(trait_ref)); | ||
392 | self.obligations.push(Obligation::Projection(projection)); | ||
393 | self.resolve_ty_as_possible(ty) | ||
394 | } | ||
395 | None => Ty::Unknown, | ||
396 | } | ||
397 | } | ||
398 | |||
399 | /// Recurses through the given type, normalizing associated types mentioned | ||
400 | /// in it by replacing them by type variables and registering obligations to | ||
401 | /// resolve later. This should be done once for every type we get from some | ||
402 | /// type annotation (e.g. from a let type annotation, field type or function | ||
403 | /// call). `make_ty` handles this already, but e.g. for field types we need | ||
404 | /// to do it as well. | ||
405 | fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty { | ||
406 | let ty = self.resolve_ty_as_possible(ty); | ||
407 | ty.fold(&mut |ty| match ty { | ||
408 | Ty::Projection(proj_ty) => self.normalize_projection_ty(proj_ty), | ||
409 | _ => ty, | ||
410 | }) | ||
411 | } | ||
412 | |||
413 | fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty { | ||
414 | let var = self.table.new_type_var(); | ||
415 | let predicate = ProjectionPredicate { projection_ty: proj_ty, ty: var.clone() }; | ||
416 | let obligation = Obligation::Projection(predicate); | ||
417 | self.obligations.push(obligation); | ||
418 | var | ||
419 | } | ||
420 | |||
421 | fn resolve_variant(&mut self, path: Option<&Path>) -> (Ty, Option<VariantId>) { | ||
422 | let path = match path { | ||
423 | Some(path) => path, | ||
424 | None => return (Ty::Unknown, None), | ||
425 | }; | ||
426 | let resolver = &self.resolver; | ||
427 | let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver); | ||
428 | // FIXME: this should resolve assoc items as well, see this example: | ||
429 | // https://play.rust-lang.org/?gist=087992e9e22495446c01c0d4e2d69521 | ||
430 | let (resolution, unresolved) = | ||
431 | match resolver.resolve_path_in_type_ns(self.db.upcast(), path.mod_path()) { | ||
432 | Some(it) => it, | ||
433 | None => return (Ty::Unknown, None), | ||
434 | }; | ||
435 | return match resolution { | ||
436 | TypeNs::AdtId(AdtId::StructId(strukt)) => { | ||
437 | let substs = Ty::substs_from_path(&ctx, path, strukt.into(), true); | ||
438 | let ty = self.db.ty(strukt.into()); | ||
439 | let ty = self.insert_type_vars(ty.subst(&substs)); | ||
440 | forbid_unresolved_segments((ty, Some(strukt.into())), unresolved) | ||
441 | } | ||
442 | TypeNs::AdtId(AdtId::UnionId(u)) => { | ||
443 | let substs = Ty::substs_from_path(&ctx, path, u.into(), true); | ||
444 | let ty = self.db.ty(u.into()); | ||
445 | let ty = self.insert_type_vars(ty.subst(&substs)); | ||
446 | forbid_unresolved_segments((ty, Some(u.into())), unresolved) | ||
447 | } | ||
448 | TypeNs::EnumVariantId(var) => { | ||
449 | let substs = Ty::substs_from_path(&ctx, path, var.into(), true); | ||
450 | let ty = self.db.ty(var.parent.into()); | ||
451 | let ty = self.insert_type_vars(ty.subst(&substs)); | ||
452 | forbid_unresolved_segments((ty, Some(var.into())), unresolved) | ||
453 | } | ||
454 | TypeNs::SelfType(impl_id) => { | ||
455 | let generics = crate::utils::generics(self.db.upcast(), impl_id.into()); | ||
456 | let substs = Substs::type_params_for_generics(&generics); | ||
457 | let ty = self.db.impl_self_ty(impl_id).subst(&substs); | ||
458 | match unresolved { | ||
459 | None => { | ||
460 | let variant = ty_variant(&ty); | ||
461 | (ty, variant) | ||
462 | } | ||
463 | Some(1) => { | ||
464 | let segment = path.mod_path().segments.last().unwrap(); | ||
465 | // this could be an enum variant or associated type | ||
466 | if let Some((AdtId::EnumId(enum_id), _)) = ty.as_adt() { | ||
467 | let enum_data = self.db.enum_data(enum_id); | ||
468 | if let Some(local_id) = enum_data.variant(segment) { | ||
469 | let variant = EnumVariantId { parent: enum_id, local_id }; | ||
470 | return (ty, Some(variant.into())); | ||
471 | } | ||
472 | } | ||
473 | // FIXME potentially resolve assoc type | ||
474 | (Ty::Unknown, None) | ||
475 | } | ||
476 | Some(_) => { | ||
477 | // FIXME diagnostic | ||
478 | (Ty::Unknown, None) | ||
479 | } | ||
480 | } | ||
481 | } | ||
482 | TypeNs::TypeAliasId(it) => { | ||
483 | let substs = Substs::build_for_def(self.db, it) | ||
484 | .fill(std::iter::repeat_with(|| self.table.new_type_var())) | ||
485 | .build(); | ||
486 | let ty = self.db.ty(it.into()).subst(&substs); | ||
487 | let variant = ty_variant(&ty); | ||
488 | forbid_unresolved_segments((ty, variant), unresolved) | ||
489 | } | ||
490 | TypeNs::AdtSelfType(_) => { | ||
491 | // FIXME this could happen in array size expressions, once we're checking them | ||
492 | (Ty::Unknown, None) | ||
493 | } | ||
494 | TypeNs::GenericParam(_) => { | ||
495 | // FIXME potentially resolve assoc type | ||
496 | (Ty::Unknown, None) | ||
497 | } | ||
498 | TypeNs::AdtId(AdtId::EnumId(_)) | TypeNs::BuiltinType(_) | TypeNs::TraitId(_) => { | ||
499 | // FIXME diagnostic | ||
500 | (Ty::Unknown, None) | ||
501 | } | ||
502 | }; | ||
503 | |||
504 | fn forbid_unresolved_segments( | ||
505 | result: (Ty, Option<VariantId>), | ||
506 | unresolved: Option<usize>, | ||
507 | ) -> (Ty, Option<VariantId>) { | ||
508 | if unresolved.is_none() { | ||
509 | result | ||
510 | } else { | ||
511 | // FIXME diagnostic | ||
512 | (Ty::Unknown, None) | ||
513 | } | ||
514 | } | ||
515 | |||
516 | fn ty_variant(ty: &Ty) -> Option<VariantId> { | ||
517 | ty.as_adt().and_then(|(adt_id, _)| match adt_id { | ||
518 | AdtId::StructId(s) => Some(VariantId::StructId(s)), | ||
519 | AdtId::UnionId(u) => Some(VariantId::UnionId(u)), | ||
520 | AdtId::EnumId(_) => { | ||
521 | // FIXME Error E0071, expected struct, variant or union type, found enum `Foo` | ||
522 | None | ||
523 | } | ||
524 | }) | ||
525 | } | ||
526 | } | ||
527 | |||
528 | fn collect_const(&mut self, data: &ConstData) { | ||
529 | self.return_ty = self.make_ty(&data.type_ref); | ||
530 | } | ||
531 | |||
532 | fn collect_static(&mut self, data: &StaticData) { | ||
533 | self.return_ty = self.make_ty(&data.type_ref); | ||
534 | } | ||
535 | |||
536 | fn collect_fn(&mut self, data: &FunctionData) { | ||
537 | let body = Arc::clone(&self.body); // avoid borrow checker problem | ||
538 | let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver) | ||
539 | .with_impl_trait_mode(ImplTraitLoweringMode::Param); | ||
540 | let param_tys = | ||
541 | data.params.iter().map(|type_ref| Ty::from_hir(&ctx, type_ref)).collect::<Vec<_>>(); | ||
542 | for (ty, pat) in param_tys.into_iter().zip(body.params.iter()) { | ||
543 | let ty = self.insert_type_vars(ty); | ||
544 | let ty = self.normalize_associated_types_in(ty); | ||
545 | |||
546 | self.infer_pat(*pat, &ty, BindingMode::default()); | ||
547 | } | ||
548 | let return_ty = self.make_ty_with_mode(&data.ret_type, ImplTraitLoweringMode::Disallowed); // FIXME implement RPIT | ||
549 | self.return_ty = return_ty; | ||
550 | } | ||
551 | |||
552 | fn infer_body(&mut self) { | ||
553 | self.infer_expr_coerce(self.body.body_expr, &Expectation::has_type(self.return_ty.clone())); | ||
554 | } | ||
555 | |||
556 | fn resolve_lang_item(&self, name: &str) -> Option<LangItemTarget> { | ||
557 | let krate = self.resolver.krate()?; | ||
558 | let name = SmolStr::new_inline_from_ascii(name.len(), name.as_bytes()); | ||
559 | self.db.lang_item(krate, name) | ||
560 | } | ||
561 | |||
562 | fn resolve_into_iter_item(&self) -> Option<TypeAliasId> { | ||
563 | let path = path![core::iter::IntoIterator]; | ||
564 | let trait_ = self.resolver.resolve_known_trait(self.db.upcast(), &path)?; | ||
565 | self.db.trait_data(trait_).associated_type_by_name(&name![Item]) | ||
566 | } | ||
567 | |||
568 | fn resolve_ops_try_ok(&self) -> Option<TypeAliasId> { | ||
569 | let path = path![core::ops::Try]; | ||
570 | let trait_ = self.resolver.resolve_known_trait(self.db.upcast(), &path)?; | ||
571 | self.db.trait_data(trait_).associated_type_by_name(&name![Ok]) | ||
572 | } | ||
573 | |||
574 | fn resolve_ops_neg_output(&self) -> Option<TypeAliasId> { | ||
575 | let trait_ = self.resolve_lang_item("neg")?.as_trait()?; | ||
576 | self.db.trait_data(trait_).associated_type_by_name(&name![Output]) | ||
577 | } | ||
578 | |||
579 | fn resolve_ops_not_output(&self) -> Option<TypeAliasId> { | ||
580 | let trait_ = self.resolve_lang_item("not")?.as_trait()?; | ||
581 | self.db.trait_data(trait_).associated_type_by_name(&name![Output]) | ||
582 | } | ||
583 | |||
584 | fn resolve_future_future_output(&self) -> Option<TypeAliasId> { | ||
585 | let trait_ = self.resolve_lang_item("future_trait")?.as_trait()?; | ||
586 | self.db.trait_data(trait_).associated_type_by_name(&name![Output]) | ||
587 | } | ||
588 | |||
589 | fn resolve_boxed_box(&self) -> Option<AdtId> { | ||
590 | let struct_ = self.resolve_lang_item("owned_box")?.as_struct()?; | ||
591 | Some(struct_.into()) | ||
592 | } | ||
593 | |||
594 | fn resolve_range_full(&self) -> Option<AdtId> { | ||
595 | let path = path![core::ops::RangeFull]; | ||
596 | let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?; | ||
597 | Some(struct_.into()) | ||
598 | } | ||
599 | |||
600 | fn resolve_range(&self) -> Option<AdtId> { | ||
601 | let path = path![core::ops::Range]; | ||
602 | let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?; | ||
603 | Some(struct_.into()) | ||
604 | } | ||
605 | |||
606 | fn resolve_range_inclusive(&self) -> Option<AdtId> { | ||
607 | let path = path![core::ops::RangeInclusive]; | ||
608 | let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?; | ||
609 | Some(struct_.into()) | ||
610 | } | ||
611 | |||
612 | fn resolve_range_from(&self) -> Option<AdtId> { | ||
613 | let path = path![core::ops::RangeFrom]; | ||
614 | let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?; | ||
615 | Some(struct_.into()) | ||
616 | } | ||
617 | |||
618 | fn resolve_range_to(&self) -> Option<AdtId> { | ||
619 | let path = path![core::ops::RangeTo]; | ||
620 | let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?; | ||
621 | Some(struct_.into()) | ||
622 | } | ||
623 | |||
624 | fn resolve_range_to_inclusive(&self) -> Option<AdtId> { | ||
625 | let path = path![core::ops::RangeToInclusive]; | ||
626 | let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?; | ||
627 | Some(struct_.into()) | ||
628 | } | ||
629 | |||
630 | fn resolve_ops_index(&self) -> Option<TraitId> { | ||
631 | self.resolve_lang_item("index")?.as_trait() | ||
632 | } | ||
633 | |||
634 | fn resolve_ops_index_output(&self) -> Option<TypeAliasId> { | ||
635 | let trait_ = self.resolve_ops_index()?; | ||
636 | self.db.trait_data(trait_).associated_type_by_name(&name![Output]) | ||
637 | } | ||
638 | } | ||
639 | |||
640 | /// The kinds of placeholders we need during type inference. There's separate | ||
641 | /// values for general types, and for integer and float variables. The latter | ||
642 | /// two are used for inference of literal values (e.g. `100` could be one of | ||
643 | /// several integer types). | ||
644 | #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)] | ||
645 | pub enum InferTy { | ||
646 | TypeVar(unify::TypeVarId), | ||
647 | IntVar(unify::TypeVarId), | ||
648 | FloatVar(unify::TypeVarId), | ||
649 | MaybeNeverTypeVar(unify::TypeVarId), | ||
650 | } | ||
651 | |||
652 | impl InferTy { | ||
653 | fn to_inner(self) -> unify::TypeVarId { | ||
654 | match self { | ||
655 | InferTy::TypeVar(ty) | ||
656 | | InferTy::IntVar(ty) | ||
657 | | InferTy::FloatVar(ty) | ||
658 | | InferTy::MaybeNeverTypeVar(ty) => ty, | ||
659 | } | ||
660 | } | ||
661 | |||
662 | fn fallback_value(self) -> Ty { | ||
663 | match self { | ||
664 | InferTy::TypeVar(..) => Ty::Unknown, | ||
665 | InferTy::IntVar(..) => Ty::simple(TypeCtor::Int(IntTy::i32())), | ||
666 | InferTy::FloatVar(..) => Ty::simple(TypeCtor::Float(FloatTy::f64())), | ||
667 | InferTy::MaybeNeverTypeVar(..) => Ty::simple(TypeCtor::Never), | ||
668 | } | ||
669 | } | ||
670 | } | ||
671 | |||
672 | /// When inferring an expression, we propagate downward whatever type hint we | ||
673 | /// are able in the form of an `Expectation`. | ||
674 | #[derive(Clone, PartialEq, Eq, Debug)] | ||
675 | struct Expectation { | ||
676 | ty: Ty, | ||
677 | /// See the `rvalue_hint` method. | ||
678 | rvalue_hint: bool, | ||
679 | } | ||
680 | |||
681 | impl Expectation { | ||
682 | /// The expectation that the type of the expression needs to equal the given | ||
683 | /// type. | ||
684 | fn has_type(ty: Ty) -> Self { | ||
685 | Expectation { ty, rvalue_hint: false } | ||
686 | } | ||
687 | |||
688 | /// The following explanation is copied straight from rustc: | ||
689 | /// Provides an expectation for an rvalue expression given an *optional* | ||
690 | /// hint, which is not required for type safety (the resulting type might | ||
691 | /// be checked higher up, as is the case with `&expr` and `box expr`), but | ||
692 | /// is useful in determining the concrete type. | ||
693 | /// | ||
694 | /// The primary use case is where the expected type is a fat pointer, | ||
695 | /// like `&[isize]`. For example, consider the following statement: | ||
696 | /// | ||
697 | /// let x: &[isize] = &[1, 2, 3]; | ||
698 | /// | ||
699 | /// In this case, the expected type for the `&[1, 2, 3]` expression is | ||
700 | /// `&[isize]`. If however we were to say that `[1, 2, 3]` has the | ||
701 | /// expectation `ExpectHasType([isize])`, that would be too strong -- | ||
702 | /// `[1, 2, 3]` does not have the type `[isize]` but rather `[isize; 3]`. | ||
703 | /// It is only the `&[1, 2, 3]` expression as a whole that can be coerced | ||
704 | /// to the type `&[isize]`. Therefore, we propagate this more limited hint, | ||
705 | /// which still is useful, because it informs integer literals and the like. | ||
706 | /// See the test case `test/ui/coerce-expect-unsized.rs` and #20169 | ||
707 | /// for examples of where this comes up,. | ||
708 | fn rvalue_hint(ty: Ty) -> Self { | ||
709 | Expectation { ty, rvalue_hint: true } | ||
710 | } | ||
711 | |||
712 | /// This expresses no expectation on the type. | ||
713 | fn none() -> Self { | ||
714 | Expectation { ty: Ty::Unknown, rvalue_hint: false } | ||
715 | } | ||
716 | |||
717 | fn coercion_target(&self) -> &Ty { | ||
718 | if self.rvalue_hint { | ||
719 | &Ty::Unknown | ||
720 | } else { | ||
721 | &self.ty | ||
722 | } | ||
723 | } | ||
724 | } | ||
725 | |||
726 | #[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)] | ||
727 | enum Diverges { | ||
728 | Maybe, | ||
729 | Always, | ||
730 | } | ||
731 | |||
732 | impl Diverges { | ||
733 | fn is_always(self) -> bool { | ||
734 | self == Diverges::Always | ||
735 | } | ||
736 | } | ||
737 | |||
738 | impl std::ops::BitAnd for Diverges { | ||
739 | type Output = Self; | ||
740 | fn bitand(self, other: Self) -> Self { | ||
741 | std::cmp::min(self, other) | ||
742 | } | ||
743 | } | ||
744 | |||
745 | impl std::ops::BitOr for Diverges { | ||
746 | type Output = Self; | ||
747 | fn bitor(self, other: Self) -> Self { | ||
748 | std::cmp::max(self, other) | ||
749 | } | ||
750 | } | ||
751 | |||
752 | impl std::ops::BitAndAssign for Diverges { | ||
753 | fn bitand_assign(&mut self, other: Self) { | ||
754 | *self = *self & other; | ||
755 | } | ||
756 | } | ||
757 | |||
758 | impl std::ops::BitOrAssign for Diverges { | ||
759 | fn bitor_assign(&mut self, other: Self) { | ||
760 | *self = *self | other; | ||
761 | } | ||
762 | } | ||
763 | |||
764 | mod diagnostics { | ||
765 | use hir_def::{expr::ExprId, DefWithBodyId}; | ||
766 | use hir_expand::diagnostics::DiagnosticSink; | ||
767 | |||
768 | use crate::{ | ||
769 | db::HirDatabase, | ||
770 | diagnostics::{BreakOutsideOfLoop, NoSuchField}, | ||
771 | }; | ||
772 | |||
773 | #[derive(Debug, PartialEq, Eq, Clone)] | ||
774 | pub(super) enum InferenceDiagnostic { | ||
775 | NoSuchField { expr: ExprId, field: usize }, | ||
776 | BreakOutsideOfLoop { expr: ExprId }, | ||
777 | } | ||
778 | |||
779 | impl InferenceDiagnostic { | ||
780 | pub(super) fn add_to( | ||
781 | &self, | ||
782 | db: &dyn HirDatabase, | ||
783 | owner: DefWithBodyId, | ||
784 | sink: &mut DiagnosticSink, | ||
785 | ) { | ||
786 | match self { | ||
787 | InferenceDiagnostic::NoSuchField { expr, field } => { | ||
788 | let (_, source_map) = db.body_with_source_map(owner); | ||
789 | let field = source_map.field_syntax(*expr, *field); | ||
790 | sink.push(NoSuchField { file: field.file_id, field: field.value }) | ||
791 | } | ||
792 | InferenceDiagnostic::BreakOutsideOfLoop { expr } => { | ||
793 | let (_, source_map) = db.body_with_source_map(owner); | ||
794 | let ptr = source_map | ||
795 | .expr_syntax(*expr) | ||
796 | .expect("break outside of loop in synthetic syntax"); | ||
797 | sink.push(BreakOutsideOfLoop { file: ptr.file_id, expr: ptr.value }) | ||
798 | } | ||
799 | } | ||
800 | } | ||
801 | } | ||
802 | } | ||