aboutsummaryrefslogtreecommitdiff
path: root/crates/hir_ty/src/infer.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/hir_ty/src/infer.rs')
-rw-r--r--crates/hir_ty/src/infer.rs802
1 files changed, 802 insertions, 0 deletions
diff --git a/crates/hir_ty/src/infer.rs b/crates/hir_ty/src/infer.rs
new file mode 100644
index 000000000..03b00b101
--- /dev/null
+++ b/crates/hir_ty/src/infer.rs
@@ -0,0 +1,802 @@
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
16use std::borrow::Cow;
17use std::mem;
18use std::ops::Index;
19use std::sync::Arc;
20
21use arena::map::ArenaMap;
22use 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};
33use hir_expand::{diagnostics::DiagnosticSink, name::name};
34use rustc_hash::FxHashMap;
35use stdx::impl_from;
36use syntax::SmolStr;
37
38use super::{
39 primitive::{FloatTy, IntTy},
40 traits::{Guidance, Obligation, ProjectionPredicate, Solution},
41 InEnvironment, ProjectionTy, Substs, TraitEnvironment, TraitRef, Ty, TypeCtor, TypeWalk,
42};
43use crate::{
44 db::HirDatabase, infer::diagnostics::InferenceDiagnostic, lower::ImplTraitLoweringMode,
45};
46
47pub(crate) use unify::unify;
48
49macro_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
58mod unify;
59mod path;
60mod expr;
61mod pat;
62mod coerce;
63
64/// The entry point of type inference.
65pub(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)]
82enum ExprOrPatId {
83 ExprId(ExprId),
84 PatId(PatId),
85}
86impl_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)]
91enum BindingMode {
92 Move,
93 Ref(Mutability),
94}
95
96impl 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
106impl 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)]
114pub 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)]
121pub 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
139impl 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
177impl 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
185impl 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)]
195struct 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)]
216struct BreakableContext {
217 pub may_break: bool,
218 pub break_ty: Ty,
219 pub label: Option<name::Name>,
220}
221
222fn 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
232impl<'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)]
645pub enum InferTy {
646 TypeVar(unify::TypeVarId),
647 IntVar(unify::TypeVarId),
648 FloatVar(unify::TypeVarId),
649 MaybeNeverTypeVar(unify::TypeVarId),
650}
651
652impl 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)]
675struct Expectation {
676 ty: Ty,
677 /// See the `rvalue_hint` method.
678 rvalue_hint: bool,
679}
680
681impl 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)]
727enum Diverges {
728 Maybe,
729 Always,
730}
731
732impl Diverges {
733 fn is_always(self) -> bool {
734 self == Diverges::Always
735 }
736}
737
738impl 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
745impl 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
752impl std::ops::BitAndAssign for Diverges {
753 fn bitand_assign(&mut self, other: Self) {
754 *self = *self & other;
755 }
756}
757
758impl std::ops::BitOrAssign for Diverges {
759 fn bitor_assign(&mut self, other: Self) {
760 *self = *self | other;
761 }
762}
763
764mod 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}