1 //! Type inference, i.e. the process of walking through the code and determining
2 //! the type of each expression and pattern.
4 //! For type inference, compare the implementations in rustc (the various
5 //! check_* methods in rustc_hir_analysis/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.
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.
19 use chalk_ir::{cast::Cast, ConstValue, DebruijnIndex, Mutability, Safety, Scalar, TypeFlags};
22 builtin_type::{BuiltinInt, BuiltinType, BuiltinUint},
23 data::{ConstData, StaticData},
24 expr::{BindingAnnotation, ExprId, ExprOrPatId, PatId},
25 lang_item::LangItemTarget,
28 resolver::{HasResolver, ResolveValueResult, Resolver, TypeNs, ValueNs},
30 AdtId, AssocItemId, DefWithBodyId, EnumVariantId, FieldId, FunctionId, HasModule,
31 ItemContainerId, Lookup, TraitId, TypeAliasId, VariantId,
33 use hir_expand::name::{name, Name};
34 use itertools::Either;
35 use la_arena::ArenaMap;
36 use rustc_hash::FxHashMap;
40 db::HirDatabase, fold_tys, fold_tys_and_consts, infer::coerce::CoerceMany,
41 lower::ImplTraitLoweringMode, to_assoc_type_id, AliasEq, AliasTy, Const, DomainGoal,
42 GenericArg, Goal, ImplTraitId, InEnvironment, Interner, ProjectionTy, Substitution,
43 TraitEnvironment, TraitRef, Ty, TyBuilder, TyExt, TyKind,
46 // This lint has a false positive here. See the link below for details.
48 // https://github.com/rust-lang/rust/issues/57411
49 #[allow(unreachable_pub)]
50 pub use coerce::could_coerce;
51 #[allow(unreachable_pub)]
52 pub use unify::could_unify;
61 /// The entry point of type inference.
62 pub(crate) fn infer_query(db: &dyn HirDatabase, def: DefWithBodyId) -> Arc<InferenceResult> {
63 let _p = profile::span("infer_query");
64 let resolver = def.resolver(db.upcast());
65 let body = db.body(def);
66 let mut ctx = InferenceContext::new(db, def, &body, resolver);
69 DefWithBodyId::ConstId(c) => ctx.collect_const(&db.const_data(c)),
70 DefWithBodyId::FunctionId(f) => ctx.collect_fn(f),
71 DefWithBodyId::StaticId(s) => ctx.collect_static(&db.static_data(s)),
72 DefWithBodyId::VariantId(v) => {
73 ctx.return_ty = TyBuilder::builtin(match db.enum_data(v.parent).variant_body_type() {
74 hir_def::layout::IntegerType::Pointer(signed) => match signed {
75 true => BuiltinType::Int(BuiltinInt::Isize),
76 false => BuiltinType::Uint(BuiltinUint::Usize),
78 hir_def::layout::IntegerType::Fixed(size, signed) => match signed {
79 true => BuiltinType::Int(match size {
80 Integer::I8 => BuiltinInt::I8,
81 Integer::I16 => BuiltinInt::I16,
82 Integer::I32 => BuiltinInt::I32,
83 Integer::I64 => BuiltinInt::I64,
84 Integer::I128 => BuiltinInt::I128,
86 false => BuiltinType::Uint(match size {
87 Integer::I8 => BuiltinUint::U8,
88 Integer::I16 => BuiltinUint::U16,
89 Integer::I32 => BuiltinUint::U32,
90 Integer::I64 => BuiltinUint::U64,
91 Integer::I128 => BuiltinUint::U128,
100 Arc::new(ctx.resolve_all())
103 /// Fully normalize all the types found within `ty` in context of `owner` body definition.
105 /// This is appropriate to use only after type-check: it assumes
106 /// that normalization will succeed, for example.
107 pub(crate) fn normalize(db: &dyn HirDatabase, owner: DefWithBodyId, ty: Ty) -> Ty {
108 if !ty.data(Interner).flags.intersects(TypeFlags::HAS_PROJECTION) {
111 let krate = owner.module(db.upcast()).krate();
112 let trait_env = owner
114 .map_or_else(|| Arc::new(TraitEnvironment::empty(krate)), |d| db.trait_environment(d));
115 let mut table = unify::InferenceTable::new(db, trait_env);
117 let ty_with_vars = table.normalize_associated_types_in(ty);
118 table.resolve_obligations_as_possible();
119 table.propagate_diverging_flag();
120 table.resolve_completely(ty_with_vars)
123 /// Binding modes inferred for patterns.
124 /// <https://doc.rust-lang.org/reference/patterns.html#binding-modes>
125 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
126 pub enum BindingMode {
132 fn convert(annotation: BindingAnnotation) -> BindingMode {
134 BindingAnnotation::Unannotated | BindingAnnotation::Mutable => BindingMode::Move,
135 BindingAnnotation::Ref => BindingMode::Ref(Mutability::Not),
136 BindingAnnotation::RefMut => BindingMode::Ref(Mutability::Mut),
141 impl Default for BindingMode {
142 fn default() -> Self {
147 /// Used to generalize patterns and assignee expressions.
148 trait PatLike: Into<ExprOrPatId> + Copy {
149 type BindingMode: Copy;
152 this: &mut InferenceContext<'_>,
155 default_bm: Self::BindingMode,
159 impl PatLike for ExprId {
160 type BindingMode = ();
163 this: &mut InferenceContext<'_>,
166 _: Self::BindingMode,
168 this.infer_assignee_expr(id, expected_ty)
172 impl PatLike for PatId {
173 type BindingMode = BindingMode;
176 this: &mut InferenceContext<'_>,
179 default_bm: Self::BindingMode,
181 this.infer_pat(id, expected_ty, default_bm)
186 pub(crate) struct InferOk<T> {
188 goals: Vec<InEnvironment<Goal>>,
192 fn map<U>(self, f: impl FnOnce(T) -> U) -> InferOk<U> {
193 InferOk { value: f(self.value), goals: self.goals }
198 pub(crate) struct TypeError;
199 pub(crate) type InferResult<T> = Result<InferOk<T>, TypeError>;
201 #[derive(Debug, PartialEq, Eq, Clone)]
202 pub enum InferenceDiagnostic {
203 NoSuchField { expr: ExprId },
204 PrivateField { expr: ExprId, field: FieldId },
205 PrivateAssocItem { id: ExprOrPatId, item: AssocItemId },
206 BreakOutsideOfLoop { expr: ExprId, is_break: bool },
207 MismatchedArgCount { call_expr: ExprId, expected: usize, found: usize },
210 /// A mismatch between an expected and an inferred type.
211 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
212 pub struct TypeMismatch {
217 #[derive(Clone, PartialEq, Eq, Debug)]
218 struct InternedStandardTypes {
224 impl Default for InternedStandardTypes {
225 fn default() -> Self {
226 InternedStandardTypes {
227 unknown: TyKind::Error.intern(Interner),
228 bool_: TyKind::Scalar(Scalar::Bool).intern(Interner),
229 unit: TyKind::Tuple(0, Substitution::empty(Interner)).intern(Interner),
233 /// Represents coercing a value to a different type of value.
235 /// We transform values by following a number of `Adjust` steps in order.
236 /// See the documentation on variants of `Adjust` for more details.
238 /// Here are some common scenarios:
240 /// 1. The simplest cases are where a pointer is not adjusted fat vs thin.
241 /// Here the pointer will be dereferenced N times (where a dereference can
242 /// happen to raw or borrowed pointers or any smart pointer which implements
243 /// Deref, including Box<_>). The types of dereferences is given by
244 /// `autoderefs`. It can then be auto-referenced zero or one times, indicated
245 /// by `autoref`, to either a raw or borrowed pointer. In these cases unsize is
248 /// 2. A thin-to-fat coercion involves unsizing the underlying data. We start
249 /// with a thin pointer, deref a number of times, unsize the underlying data,
250 /// then autoref. The 'unsize' phase may change a fixed length array to a
251 /// dynamically sized one, a concrete object to a trait object, or statically
252 /// sized struct to a dynamically sized one. E.g., &[i32; 4] -> &[i32] is
256 /// Deref(None) -> [i32; 4],
257 /// Borrow(AutoBorrow::Ref) -> &[i32; 4],
258 /// Unsize -> &[i32],
261 /// Note that for a struct, the 'deep' unsizing of the struct is not recorded.
262 /// E.g., `struct Foo<T> { x: T }` we can coerce &Foo<[i32; 4]> to &Foo<[i32]>
263 /// The autoderef and -ref are the same as in the above example, but the type
264 /// stored in `unsize` is `Foo<[i32]>`, we don't store any further detail about
265 /// the underlying conversions from `[i32; 4]` to `[i32]`.
267 /// 3. Coercing a `Box<T>` to `Box<dyn Trait>` is an interesting special case. In
268 /// that case, we have the pointer we need coming in, so there are no
269 /// autoderefs, and no autoref. Instead we just do the `Unsize` transformation.
270 /// At some point, of course, `Box` should move out of the compiler, in which
271 /// case this is analogous to transforming a struct. E.g., Box<[i32; 4]> ->
272 /// Box<[i32]> is an `Adjust::Unsize` with the target `Box<[i32]>`.
273 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
274 pub struct Adjustment {
279 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
281 /// Go from ! to any type.
283 /// Dereference once, producing a place.
284 Deref(Option<OverloadedDeref>),
285 /// Take the address and produce either a `&` or `*` pointer.
287 Pointer(PointerCast),
290 /// An overloaded autoderef step, representing a `Deref(Mut)::deref(_mut)`
291 /// call, with the signature `&'a T -> &'a U` or `&'a mut T -> &'a mut U`.
292 /// The target type is `U` in both cases, with the region and mutability
293 /// being those shared by both the receiver and the returned reference.
294 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
295 pub struct OverloadedDeref(pub Mutability);
297 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
298 pub enum AutoBorrow {
299 /// Converts from T to &T.
301 /// Converts from T to *T.
305 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
306 pub enum PointerCast {
307 /// Go from a fn-item type to a fn-pointer type.
310 /// Go from a safe fn pointer to an unsafe fn pointer.
313 /// Go from a non-capturing closure to an fn pointer or an unsafe fn pointer.
314 /// It cannot convert a closure that requires unsafe.
315 ClosureFnPointer(Safety),
317 /// Go from a mut raw pointer to a const raw pointer.
321 /// Go from `*const [T; N]` to `*const T`
324 /// Unsize a pointer/reference value, e.g., `&[T; n]` to
325 /// `&[T]`. Note that the source could be a thin or fat pointer.
326 /// This will do things like convert thin pointers to fat
327 /// pointers, or convert structs containing thin pointers to
328 /// structs containing fat pointers, or convert between fat
329 /// pointers. We don't store the details of how the transform is
330 /// done (in fact, we don't know that, because it might depend on
331 /// the precise type parameters). We just store the target
332 /// type. Codegen backends and miri figure out what has to be done
333 /// based on the precise source/target type at hand.
337 /// The result of type inference: A mapping from expressions and patterns to types.
338 #[derive(Clone, PartialEq, Eq, Debug, Default)]
339 pub struct InferenceResult {
340 /// For each method call expr, records the function it resolves to.
341 method_resolutions: FxHashMap<ExprId, (FunctionId, Substitution)>,
342 /// For each field access expr, records the field it resolves to.
343 field_resolutions: FxHashMap<ExprId, FieldId>,
344 /// For each struct literal or pattern, records the variant it resolves to.
345 variant_resolutions: FxHashMap<ExprOrPatId, VariantId>,
346 /// For each associated item record what it resolves to
347 assoc_resolutions: FxHashMap<ExprOrPatId, (AssocItemId, Substitution)>,
348 pub diagnostics: Vec<InferenceDiagnostic>,
349 pub type_of_expr: ArenaMap<ExprId, Ty>,
350 /// For each pattern record the type it resolves to.
352 /// **Note**: When a pattern type is resolved it may still contain
353 /// unresolved or missing subpatterns or subpatterns of mismatched types.
354 pub type_of_pat: ArenaMap<PatId, Ty>,
355 type_mismatches: FxHashMap<ExprOrPatId, TypeMismatch>,
356 /// Interned common types to return references to.
357 standard_types: InternedStandardTypes,
358 /// Stores the types which were implicitly dereferenced in pattern binding modes.
359 pub pat_adjustments: FxHashMap<PatId, Vec<Ty>>,
360 pub pat_binding_modes: FxHashMap<PatId, BindingMode>,
361 pub expr_adjustments: FxHashMap<ExprId, Vec<Adjustment>>,
364 impl InferenceResult {
365 pub fn method_resolution(&self, expr: ExprId) -> Option<(FunctionId, Substitution)> {
366 self.method_resolutions.get(&expr).cloned()
368 pub fn field_resolution(&self, expr: ExprId) -> Option<FieldId> {
369 self.field_resolutions.get(&expr).copied()
371 pub fn variant_resolution_for_expr(&self, id: ExprId) -> Option<VariantId> {
372 self.variant_resolutions.get(&id.into()).copied()
374 pub fn variant_resolution_for_pat(&self, id: PatId) -> Option<VariantId> {
375 self.variant_resolutions.get(&id.into()).copied()
377 pub fn assoc_resolutions_for_expr(&self, id: ExprId) -> Option<(AssocItemId, Substitution)> {
378 self.assoc_resolutions.get(&id.into()).cloned()
380 pub fn assoc_resolutions_for_pat(&self, id: PatId) -> Option<(AssocItemId, Substitution)> {
381 self.assoc_resolutions.get(&id.into()).cloned()
383 pub fn type_mismatch_for_expr(&self, expr: ExprId) -> Option<&TypeMismatch> {
384 self.type_mismatches.get(&expr.into())
386 pub fn type_mismatch_for_pat(&self, pat: PatId) -> Option<&TypeMismatch> {
387 self.type_mismatches.get(&pat.into())
389 pub fn expr_type_mismatches(&self) -> impl Iterator<Item = (ExprId, &TypeMismatch)> {
390 self.type_mismatches.iter().filter_map(|(expr_or_pat, mismatch)| match *expr_or_pat {
391 ExprOrPatId::ExprId(expr) => Some((expr, mismatch)),
395 pub fn pat_type_mismatches(&self) -> impl Iterator<Item = (PatId, &TypeMismatch)> {
396 self.type_mismatches.iter().filter_map(|(expr_or_pat, mismatch)| match *expr_or_pat {
397 ExprOrPatId::PatId(pat) => Some((pat, mismatch)),
403 impl Index<ExprId> for InferenceResult {
406 fn index(&self, expr: ExprId) -> &Ty {
407 self.type_of_expr.get(expr).unwrap_or(&self.standard_types.unknown)
411 impl Index<PatId> for InferenceResult {
414 fn index(&self, pat: PatId) -> &Ty {
415 self.type_of_pat.get(pat).unwrap_or(&self.standard_types.unknown)
419 /// The inference context contains all information needed during type inference.
420 #[derive(Clone, Debug)]
421 pub(crate) struct InferenceContext<'a> {
422 pub(crate) db: &'a dyn HirDatabase,
423 pub(crate) owner: DefWithBodyId,
424 pub(crate) body: &'a Body,
425 pub(crate) resolver: Resolver,
426 table: unify::InferenceTable<'a>,
427 trait_env: Arc<TraitEnvironment>,
428 pub(crate) result: InferenceResult,
429 /// The return type of the function being inferred, the closure or async block if we're
430 /// currently within one.
432 /// We might consider using a nested inference context for checking
433 /// closures, but currently this is the only field that will change there,
434 /// so it doesn't make sense.
436 /// The resume type and the yield type, respectively, of the generator being inferred.
437 resume_yield_tys: Option<(Ty, Ty)>,
439 breakables: Vec<BreakableContext>,
442 #[derive(Clone, Debug)]
443 struct BreakableContext {
444 /// Whether this context contains at least one break expression.
446 /// The coercion target of the context.
448 /// The optional label of the context.
449 label: Option<name::Name>,
453 #[derive(Clone, Debug)]
457 /// A border is something like an async block, closure etc. Anything that prevents
458 /// breaking/continuing through
462 fn find_breakable<'c>(
463 ctxs: &'c mut [BreakableContext],
464 label: Option<&name::Name>,
465 ) -> Option<&'c mut BreakableContext> {
469 .take_while(|it| matches!(it.kind, BreakableKind::Block | BreakableKind::Loop));
471 Some(_) => ctxs.find(|ctx| ctx.label.as_ref() == label),
472 None => ctxs.find(|ctx| matches!(ctx.kind, BreakableKind::Loop)),
476 fn find_continuable<'c>(
477 ctxs: &'c mut [BreakableContext],
478 label: Option<&name::Name>,
479 ) -> Option<&'c mut BreakableContext> {
481 Some(_) => find_breakable(ctxs, label).filter(|it| matches!(it.kind, BreakableKind::Loop)),
482 None => find_breakable(ctxs, label),
486 impl<'a> InferenceContext<'a> {
488 db: &'a dyn HirDatabase,
489 owner: DefWithBodyId,
493 let krate = owner.module(db.upcast()).krate();
494 let trait_env = owner
496 .map_or_else(|| Arc::new(TraitEnvironment::empty(krate)), |d| db.trait_environment(d));
498 result: InferenceResult::default(),
499 table: unify::InferenceTable::new(db, trait_env.clone()),
501 return_ty: TyKind::Error.intern(Interner), // set in collect_* calls
502 resume_yield_tys: None,
507 diverges: Diverges::Maybe,
508 breakables: Vec::new(),
512 fn resolve_all(self) -> InferenceResult {
513 let InferenceContext { mut table, mut result, .. } = self;
515 table.fallback_if_possible();
517 // FIXME resolve obligations as well (use Guidance if necessary)
518 table.resolve_obligations_as_possible();
520 // make sure diverging type variables are marked as such
521 table.propagate_diverging_flag();
522 for ty in result.type_of_expr.values_mut() {
523 *ty = table.resolve_completely(ty.clone());
525 for ty in result.type_of_pat.values_mut() {
526 *ty = table.resolve_completely(ty.clone());
528 for mismatch in result.type_mismatches.values_mut() {
529 mismatch.expected = table.resolve_completely(mismatch.expected.clone());
530 mismatch.actual = table.resolve_completely(mismatch.actual.clone());
532 for (_, subst) in result.method_resolutions.values_mut() {
533 *subst = table.resolve_completely(subst.clone());
535 for (_, subst) in result.assoc_resolutions.values_mut() {
536 *subst = table.resolve_completely(subst.clone());
538 for adjustment in result.expr_adjustments.values_mut().flatten() {
539 adjustment.target = table.resolve_completely(adjustment.target.clone());
541 for adjustment in result.pat_adjustments.values_mut().flatten() {
542 *adjustment = table.resolve_completely(adjustment.clone());
547 fn collect_const(&mut self, data: &ConstData) {
548 self.return_ty = self.make_ty(&data.type_ref);
551 fn collect_static(&mut self, data: &StaticData) {
552 self.return_ty = self.make_ty(&data.type_ref);
555 fn collect_fn(&mut self, func: FunctionId) {
556 let data = self.db.function_data(func);
557 let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver)
558 .with_impl_trait_mode(ImplTraitLoweringMode::Param);
560 data.params.iter().map(|(_, type_ref)| ctx.lower_ty(type_ref)).collect::<Vec<_>>();
561 // Check if function contains a va_list, if it does then we append it to the parameter types
562 // that are collected from the function data
563 if data.is_varargs() {
564 let va_list_ty = match self.resolve_va_list() {
565 Some(va_list) => TyBuilder::adt(self.db, va_list)
566 .fill_with_defaults(self.db, || self.table.new_type_var())
568 None => self.err_ty(),
571 param_tys.push(va_list_ty)
573 for (ty, pat) in param_tys.into_iter().zip(self.body.params.iter()) {
574 let ty = self.insert_type_vars(ty);
575 let ty = self.normalize_associated_types_in(ty);
577 self.infer_pat(*pat, &ty, BindingMode::default());
579 let error_ty = &TypeRef::Error;
580 let return_ty = if data.has_async_kw() {
581 data.async_ret_type.as_deref().unwrap_or(error_ty)
586 let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver)
587 .with_impl_trait_mode(ImplTraitLoweringMode::Opaque);
588 let return_ty = ctx.lower_ty(return_ty);
589 let return_ty = self.insert_type_vars(return_ty);
591 let return_ty = if let Some(rpits) = self.db.return_type_impl_traits(func) {
592 // RPIT opaque types use substitution of their parent function.
593 let fn_placeholders = TyBuilder::placeholder_subst(self.db, func);
597 let opaque_ty_id = match ty.kind(Interner) {
598 TyKind::OpaqueType(opaque_ty_id, _) => *opaque_ty_id,
601 let idx = match self.db.lookup_intern_impl_trait_id(opaque_ty_id.into()) {
602 ImplTraitId::ReturnTypeImplTrait(_, idx) => idx,
605 let bounds = (*rpits).map_ref(|rpits| {
606 rpits.impl_traits[idx as usize].bounds.map_ref(|it| it.into_iter())
608 let var = self.table.new_type_var();
609 let var_subst = Substitution::from1(Interner, var.clone());
610 for bound in bounds {
612 bound.map(|it| it.cloned()).substitute(Interner, &fn_placeholders);
613 let (var_predicate, binders) = predicate
614 .substitute(Interner, &var_subst)
615 .into_value_and_skipped_binders();
616 always!(binders.is_empty(Interner)); // quantified where clauses not yet handled
617 self.push_obligation(var_predicate.cast(Interner));
621 DebruijnIndex::INNERMOST,
627 self.return_ty = self.normalize_associated_types_in(return_ty);
630 fn infer_body(&mut self) {
631 self.infer_expr_coerce(self.body.body_expr, &Expectation::has_type(self.return_ty.clone()));
634 fn write_expr_ty(&mut self, expr: ExprId, ty: Ty) {
635 self.result.type_of_expr.insert(expr, ty);
638 fn write_expr_adj(&mut self, expr: ExprId, adjustments: Vec<Adjustment>) {
639 self.result.expr_adjustments.insert(expr, adjustments);
642 fn write_method_resolution(&mut self, expr: ExprId, func: FunctionId, subst: Substitution) {
643 self.result.method_resolutions.insert(expr, (func, subst));
646 fn write_variant_resolution(&mut self, id: ExprOrPatId, variant: VariantId) {
647 self.result.variant_resolutions.insert(id, variant);
650 fn write_assoc_resolution(&mut self, id: ExprOrPatId, item: AssocItemId, subs: Substitution) {
651 self.result.assoc_resolutions.insert(id, (item, subs));
654 fn write_pat_ty(&mut self, pat: PatId, ty: Ty) {
655 self.result.type_of_pat.insert(pat, ty);
658 fn push_diagnostic(&mut self, diagnostic: InferenceDiagnostic) {
659 self.result.diagnostics.push(diagnostic);
662 fn make_ty(&mut self, type_ref: &TypeRef) -> Ty {
663 // FIXME use right resolver for block
664 let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver);
665 let ty = ctx.lower_ty(type_ref);
666 let ty = self.insert_type_vars(ty);
667 self.normalize_associated_types_in(ty)
670 fn err_ty(&self) -> Ty {
671 self.result.standard_types.unknown.clone()
674 /// Replaces ConstScalar::Unknown by a new type var, so we can maybe still infer it.
675 fn insert_const_vars_shallow(&mut self, c: Const) -> Const {
676 let data = c.data(Interner);
678 ConstValue::Concrete(cc) => match cc.interned {
679 hir_def::type_ref::ConstScalar::Unknown => {
680 self.table.new_const_var(data.ty.clone())
688 /// Replaces `Ty::Error` by a new type var, so we can maybe still infer it.
689 fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty {
690 match ty.kind(Interner) {
691 TyKind::Error => self.table.new_type_var(),
692 TyKind::InferenceVar(..) => {
693 let ty_resolved = self.resolve_ty_shallow(&ty);
694 if ty_resolved.is_unknown() {
695 self.table.new_type_var()
704 fn insert_type_vars(&mut self, ty: Ty) -> Ty {
708 Either::Left(ty) => Either::Left(self.insert_type_vars_shallow(ty)),
709 Either::Right(c) => Either::Right(self.insert_const_vars_shallow(c)),
711 DebruijnIndex::INNERMOST,
715 fn push_obligation(&mut self, o: DomainGoal) {
716 self.table.register_obligation(o.cast(Interner));
719 fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
720 self.table.unify(ty1, ty2)
723 /// Recurses through the given type, normalizing associated types mentioned
724 /// in it by replacing them by type variables and registering obligations to
725 /// resolve later. This should be done once for every type we get from some
726 /// type annotation (e.g. from a let type annotation, field type or function
727 /// call). `make_ty` handles this already, but e.g. for field types we need
728 /// to do it as well.
729 fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty {
730 self.table.normalize_associated_types_in(ty)
733 fn resolve_ty_shallow(&mut self, ty: &Ty) -> Ty {
734 self.table.resolve_ty_shallow(ty)
737 fn resolve_associated_type(&mut self, inner_ty: Ty, assoc_ty: Option<TypeAliasId>) -> Ty {
738 self.resolve_associated_type_with_params(inner_ty, assoc_ty, &[])
741 fn resolve_associated_type_with_params(
744 assoc_ty: Option<TypeAliasId>,
745 // FIXME(GATs): these are args for the trait ref, args for assoc type itself should be
746 // handled when we support them.
747 params: &[GenericArg],
750 Some(res_assoc_ty) => {
751 let trait_ = match res_assoc_ty.lookup(self.db.upcast()).container {
752 hir_def::ItemContainerId::TraitId(trait_) => trait_,
753 _ => panic!("resolve_associated_type called with non-associated type"),
755 let ty = self.table.new_type_var();
756 let mut param_iter = params.iter().cloned();
757 let trait_ref = TyBuilder::trait_ref(self.db, trait_)
759 .fill(|_| param_iter.next().unwrap())
761 let alias_eq = AliasEq {
762 alias: AliasTy::Projection(ProjectionTy {
763 associated_ty_id: to_assoc_type_id(res_assoc_ty),
764 substitution: trait_ref.substitution.clone(),
768 self.push_obligation(trait_ref.cast(Interner));
769 self.push_obligation(alias_eq.cast(Interner));
772 None => self.err_ty(),
776 fn resolve_variant(&mut self, path: Option<&Path>, value_ns: bool) -> (Ty, Option<VariantId>) {
777 let path = match path {
779 None => return (self.err_ty(), None),
781 let resolver = &self.resolver;
782 let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver);
783 // FIXME: this should resolve assoc items as well, see this example:
784 // https://play.rust-lang.org/?gist=087992e9e22495446c01c0d4e2d69521
785 let (resolution, unresolved) = if value_ns {
786 match resolver.resolve_path_in_value_ns(self.db.upcast(), path.mod_path()) {
787 Some(ResolveValueResult::ValueNs(value)) => match value {
788 ValueNs::EnumVariantId(var) => {
789 let substs = ctx.substs_from_path(path, var.into(), true);
790 let ty = self.db.ty(var.parent.into());
791 let ty = self.insert_type_vars(ty.substitute(Interner, &substs));
792 return (ty, Some(var.into()));
794 ValueNs::StructId(strukt) => {
795 let substs = ctx.substs_from_path(path, strukt.into(), true);
796 let ty = self.db.ty(strukt.into());
797 let ty = self.insert_type_vars(ty.substitute(Interner, &substs));
798 return (ty, Some(strukt.into()));
800 ValueNs::ImplSelf(impl_id) => (TypeNs::SelfType(impl_id), None),
801 _ => return (self.err_ty(), None),
803 Some(ResolveValueResult::Partial(typens, unresolved)) => (typens, Some(unresolved)),
804 None => return (self.err_ty(), None),
807 match resolver.resolve_path_in_type_ns(self.db.upcast(), path.mod_path()) {
809 None => return (self.err_ty(), None),
812 return match resolution {
813 TypeNs::AdtId(AdtId::StructId(strukt)) => {
814 let substs = ctx.substs_from_path(path, strukt.into(), true);
815 let ty = self.db.ty(strukt.into());
816 let ty = self.insert_type_vars(ty.substitute(Interner, &substs));
817 forbid_unresolved_segments((ty, Some(strukt.into())), unresolved)
819 TypeNs::AdtId(AdtId::UnionId(u)) => {
820 let substs = ctx.substs_from_path(path, u.into(), true);
821 let ty = self.db.ty(u.into());
822 let ty = self.insert_type_vars(ty.substitute(Interner, &substs));
823 forbid_unresolved_segments((ty, Some(u.into())), unresolved)
825 TypeNs::EnumVariantId(var) => {
826 let substs = ctx.substs_from_path(path, var.into(), true);
827 let ty = self.db.ty(var.parent.into());
828 let ty = self.insert_type_vars(ty.substitute(Interner, &substs));
829 forbid_unresolved_segments((ty, Some(var.into())), unresolved)
831 TypeNs::SelfType(impl_id) => {
832 let generics = crate::utils::generics(self.db.upcast(), impl_id.into());
833 let substs = generics.placeholder_subst(self.db);
834 let ty = self.db.impl_self_ty(impl_id).substitute(Interner, &substs);
835 self.resolve_variant_on_alias(ty, unresolved, path)
837 TypeNs::TypeAliasId(it) => {
838 let container = it.lookup(self.db.upcast()).container;
839 let parent_subst = match container {
840 ItemContainerId::TraitId(id) => {
841 let subst = TyBuilder::subst_for_def(self.db, id, None)
842 .fill_with_inference_vars(&mut self.table)
846 // Type aliases do not exist in impls.
849 let ty = TyBuilder::def_ty(self.db, it.into(), parent_subst)
850 .fill_with_inference_vars(&mut self.table)
852 self.resolve_variant_on_alias(ty, unresolved, path)
854 TypeNs::AdtSelfType(_) => {
855 // FIXME this could happen in array size expressions, once we're checking them
856 (self.err_ty(), None)
858 TypeNs::GenericParam(_) => {
859 // FIXME potentially resolve assoc type
860 (self.err_ty(), None)
862 TypeNs::AdtId(AdtId::EnumId(_)) | TypeNs::BuiltinType(_) | TypeNs::TraitId(_) => {
864 (self.err_ty(), None)
868 fn forbid_unresolved_segments(
869 result: (Ty, Option<VariantId>),
870 unresolved: Option<usize>,
871 ) -> (Ty, Option<VariantId>) {
872 if unresolved.is_none() {
876 (TyKind::Error.intern(Interner), None)
881 fn resolve_variant_on_alias(
884 unresolved: Option<usize>,
886 ) -> (Ty, Option<VariantId>) {
887 let remaining = unresolved.map(|x| path.segments().skip(x).len()).filter(|x| x > &0);
890 let variant = ty.as_adt().and_then(|(adt_id, _)| match adt_id {
891 AdtId::StructId(s) => Some(VariantId::StructId(s)),
892 AdtId::UnionId(u) => Some(VariantId::UnionId(u)),
893 AdtId::EnumId(_) => {
894 // FIXME Error E0071, expected struct, variant or union type, found enum `Foo`
901 let segment = path.mod_path().segments().last().unwrap();
902 // this could be an enum variant or associated type
903 if let Some((AdtId::EnumId(enum_id), _)) = ty.as_adt() {
904 let enum_data = self.db.enum_data(enum_id);
905 if let Some(local_id) = enum_data.variant(segment) {
906 let variant = EnumVariantId { parent: enum_id, local_id };
907 return (ty, Some(variant.into()));
910 // FIXME potentially resolve assoc type
911 (self.err_ty(), None)
915 (self.err_ty(), None)
920 fn resolve_lang_item(&self, name: Name) -> Option<LangItemTarget> {
921 let krate = self.resolver.krate();
922 self.db.lang_item(krate, name.to_smol_str())
925 fn resolve_into_iter_item(&self) -> Option<TypeAliasId> {
926 let path = path![core::iter::IntoIterator];
927 let trait_ = self.resolver.resolve_known_trait(self.db.upcast(), &path)?;
928 self.db.trait_data(trait_).associated_type_by_name(&name![IntoIter])
931 fn resolve_iterator_item(&self) -> Option<TypeAliasId> {
932 let path = path![core::iter::Iterator];
933 let trait_ = self.resolver.resolve_known_trait(self.db.upcast(), &path)?;
934 self.db.trait_data(trait_).associated_type_by_name(&name![Item])
937 fn resolve_ops_try_ok(&self) -> Option<TypeAliasId> {
938 // FIXME resolve via lang_item once try v2 is stable
939 let path = path![core::ops::Try];
940 let trait_ = self.resolver.resolve_known_trait(self.db.upcast(), &path)?;
941 let trait_data = self.db.trait_data(trait_);
943 // FIXME remove once try v2 is stable
944 .associated_type_by_name(&name![Ok])
945 .or_else(|| trait_data.associated_type_by_name(&name![Output]))
948 fn resolve_ops_neg_output(&self) -> Option<TypeAliasId> {
949 let trait_ = self.resolve_lang_item(name![neg])?.as_trait()?;
950 self.db.trait_data(trait_).associated_type_by_name(&name![Output])
953 fn resolve_ops_not_output(&self) -> Option<TypeAliasId> {
954 let trait_ = self.resolve_lang_item(name![not])?.as_trait()?;
955 self.db.trait_data(trait_).associated_type_by_name(&name![Output])
958 fn resolve_future_future_output(&self) -> Option<TypeAliasId> {
961 .resolve_known_trait(self.db.upcast(), &path![core::future::IntoFuture])
962 .or_else(|| self.resolve_lang_item(name![future_trait])?.as_trait())?;
963 self.db.trait_data(trait_).associated_type_by_name(&name![Output])
966 fn resolve_boxed_box(&self) -> Option<AdtId> {
967 let struct_ = self.resolve_lang_item(name![owned_box])?.as_struct()?;
971 fn resolve_range_full(&self) -> Option<AdtId> {
972 let path = path![core::ops::RangeFull];
973 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
977 fn resolve_range(&self) -> Option<AdtId> {
978 let path = path![core::ops::Range];
979 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
983 fn resolve_range_inclusive(&self) -> Option<AdtId> {
984 let path = path![core::ops::RangeInclusive];
985 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
989 fn resolve_range_from(&self) -> Option<AdtId> {
990 let path = path![core::ops::RangeFrom];
991 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
995 fn resolve_range_to(&self) -> Option<AdtId> {
996 let path = path![core::ops::RangeTo];
997 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
1001 fn resolve_range_to_inclusive(&self) -> Option<AdtId> {
1002 let path = path![core::ops::RangeToInclusive];
1003 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
1004 Some(struct_.into())
1007 fn resolve_ops_index(&self) -> Option<TraitId> {
1008 self.resolve_lang_item(name![index])?.as_trait()
1011 fn resolve_ops_index_output(&self) -> Option<TypeAliasId> {
1012 let trait_ = self.resolve_ops_index()?;
1013 self.db.trait_data(trait_).associated_type_by_name(&name![Output])
1016 fn resolve_va_list(&self) -> Option<AdtId> {
1017 let struct_ = self.resolve_lang_item(name![va_list])?.as_struct()?;
1018 Some(struct_.into())
1022 /// When inferring an expression, we propagate downward whatever type hint we
1023 /// are able in the form of an `Expectation`.
1024 #[derive(Clone, PartialEq, Eq, Debug)]
1025 pub(crate) enum Expectation {
1028 // Castable(Ty), // rustc has this, we currently just don't propagate an expectation for casts
1029 RValueLikeUnsized(Ty),
1033 /// The expectation that the type of the expression needs to equal the given
1035 fn has_type(ty: Ty) -> Self {
1036 if ty.is_unknown() {
1037 // FIXME: get rid of this?
1040 Expectation::HasType(ty)
1044 fn from_option(ty: Option<Ty>) -> Self {
1045 ty.map_or(Expectation::None, Expectation::HasType)
1048 /// The following explanation is copied straight from rustc:
1049 /// Provides an expectation for an rvalue expression given an *optional*
1050 /// hint, which is not required for type safety (the resulting type might
1051 /// be checked higher up, as is the case with `&expr` and `box expr`), but
1052 /// is useful in determining the concrete type.
1054 /// The primary use case is where the expected type is a fat pointer,
1055 /// like `&[isize]`. For example, consider the following statement:
1057 /// let x: &[isize] = &[1, 2, 3];
1059 /// In this case, the expected type for the `&[1, 2, 3]` expression is
1060 /// `&[isize]`. If however we were to say that `[1, 2, 3]` has the
1061 /// expectation `ExpectHasType([isize])`, that would be too strong --
1062 /// `[1, 2, 3]` does not have the type `[isize]` but rather `[isize; 3]`.
1063 /// It is only the `&[1, 2, 3]` expression as a whole that can be coerced
1064 /// to the type `&[isize]`. Therefore, we propagate this more limited hint,
1065 /// which still is useful, because it informs integer literals and the like.
1066 /// See the test case `test/ui/coerce-expect-unsized.rs` and #20169
1067 /// for examples of where this comes up,.
1068 fn rvalue_hint(table: &mut unify::InferenceTable<'_>, ty: Ty) -> Self {
1069 // FIXME: do struct_tail_without_normalization
1070 match table.resolve_ty_shallow(&ty).kind(Interner) {
1071 TyKind::Slice(_) | TyKind::Str | TyKind::Dyn(_) => Expectation::RValueLikeUnsized(ty),
1072 _ => Expectation::has_type(ty),
1076 /// This expresses no expectation on the type.
1081 fn resolve(&self, table: &mut unify::InferenceTable<'_>) -> Expectation {
1083 Expectation::None => Expectation::None,
1084 Expectation::HasType(t) => Expectation::HasType(table.resolve_ty_shallow(t)),
1085 Expectation::RValueLikeUnsized(t) => {
1086 Expectation::RValueLikeUnsized(table.resolve_ty_shallow(t))
1091 fn to_option(&self, table: &mut unify::InferenceTable<'_>) -> Option<Ty> {
1092 match self.resolve(table) {
1093 Expectation::None => None,
1094 Expectation::HasType(t) |
1095 // Expectation::Castable(t) |
1096 Expectation::RValueLikeUnsized(t) => Some(t),
1100 fn only_has_type(&self, table: &mut unify::InferenceTable<'_>) -> Option<Ty> {
1102 Expectation::HasType(t) => Some(table.resolve_ty_shallow(t)),
1103 // Expectation::Castable(_) |
1104 Expectation::RValueLikeUnsized(_) | Expectation::None => None,
1108 /// Comment copied from rustc:
1109 /// Disregard "castable to" expectations because they
1110 /// can lead us astray. Consider for example `if cond
1111 /// {22} else {c} as u8` -- if we propagate the
1112 /// "castable to u8" constraint to 22, it will pick the
1113 /// type 22u8, which is overly constrained (c might not
1114 /// be a u8). In effect, the problem is that the
1115 /// "castable to" expectation is not the tightest thing
1116 /// we can say, so we want to drop it in this case.
1117 /// The tightest thing we can say is "must unify with
1118 /// else branch". Note that in the case of a "has type"
1119 /// constraint, this limitation does not hold.
1121 /// If the expected type is just a type variable, then don't use
1122 /// an expected type. Otherwise, we might write parts of the type
1123 /// when checking the 'then' block which are incompatible with the
1125 fn adjust_for_branches(&self, table: &mut unify::InferenceTable<'_>) -> Expectation {
1127 Expectation::HasType(ety) => {
1128 let ety = table.resolve_ty_shallow(ety);
1129 if !ety.is_ty_var() {
1130 Expectation::HasType(ety)
1135 Expectation::RValueLikeUnsized(ety) => Expectation::RValueLikeUnsized(ety.clone()),
1136 _ => Expectation::None,
1141 #[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
1148 fn is_always(self) -> bool {
1149 self == Diverges::Always
1153 impl std::ops::BitAnd for Diverges {
1155 fn bitand(self, other: Self) -> Self {
1156 std::cmp::min(self, other)
1160 impl std::ops::BitOr for Diverges {
1162 fn bitor(self, other: Self) -> Self {
1163 std::cmp::max(self, other)
1167 impl std::ops::BitAndAssign for Diverges {
1168 fn bitand_assign(&mut self, other: Self) {
1169 *self = *self & other;
1173 impl std::ops::BitOrAssign for Diverges {
1174 fn bitor_assign(&mut self, other: Self) {
1175 *self = *self | other;