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 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.
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, DebruijnIndex, Mutability, Safety};
22 data::{ConstData, FunctionData, StaticData},
23 expr::{ArithOp, BinaryOp, BindingAnnotation, ExprId, PatId},
24 lang_item::LangItemTarget,
26 resolver::{HasResolver, Resolver, TypeNs},
28 AdtId, AssocItemId, DefWithBodyId, EnumVariantId, FieldId, FunctionId, HasModule, Lookup,
29 TraitId, TypeAliasId, VariantId,
31 use hir_expand::name::name;
32 use la_arena::ArenaMap;
33 use rustc_hash::FxHashMap;
38 db::HirDatabase, fold_tys, lower::ImplTraitLoweringMode, to_assoc_type_id, AliasEq, AliasTy,
39 DomainGoal, Goal, InEnvironment, Interner, ProjectionTy, Substitution, TraitEnvironment,
40 TraitRef, Ty, TyBuilder, TyExt, TyKind,
43 // This lint has a false positive here. See the link below for details.
45 // https://github.com/rust-lang/rust/issues/57411
46 #[allow(unreachable_pub)]
47 pub use unify::could_unify;
48 pub(crate) use unify::unify;
57 /// The entry point of type inference.
58 pub(crate) fn infer_query(db: &dyn HirDatabase, def: DefWithBodyId) -> Arc<InferenceResult> {
59 let _p = profile::span("infer_query");
60 let resolver = def.resolver(db.upcast());
61 let mut ctx = InferenceContext::new(db, def, resolver);
64 DefWithBodyId::ConstId(c) => ctx.collect_const(&db.const_data(c)),
65 DefWithBodyId::FunctionId(f) => ctx.collect_fn(&db.function_data(f)),
66 DefWithBodyId::StaticId(s) => ctx.collect_static(&db.static_data(s)),
71 Arc::new(ctx.resolve_all())
74 #[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
79 impl_from!(ExprId, PatId for ExprOrPatId);
81 /// Binding modes inferred for patterns.
82 /// <https://doc.rust-lang.org/reference/patterns.html#binding-modes>
83 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
90 fn convert(annotation: BindingAnnotation) -> BindingMode {
92 BindingAnnotation::Unannotated | BindingAnnotation::Mutable => BindingMode::Move,
93 BindingAnnotation::Ref => BindingMode::Ref(Mutability::Not),
94 BindingAnnotation::RefMut => BindingMode::Ref(Mutability::Mut),
99 impl Default for BindingMode {
100 fn default() -> Self {
106 pub(crate) struct InferOk<T> {
108 goals: Vec<InEnvironment<Goal>>,
112 fn map<U>(self, f: impl FnOnce(T) -> U) -> InferOk<U> {
113 InferOk { value: f(self.value), goals: self.goals }
118 pub(crate) struct TypeError;
119 pub(crate) type InferResult<T> = Result<InferOk<T>, TypeError>;
121 #[derive(Debug, PartialEq, Eq, Clone)]
122 pub enum InferenceDiagnostic {
123 NoSuchField { expr: ExprId },
124 BreakOutsideOfLoop { expr: ExprId },
127 /// A mismatch between an expected and an inferred type.
128 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
129 pub struct TypeMismatch {
134 #[derive(Clone, PartialEq, Eq, Debug)]
135 struct InternedStandardTypes {
139 impl Default for InternedStandardTypes {
140 fn default() -> Self {
141 InternedStandardTypes { unknown: TyKind::Error.intern(&Interner) }
144 /// Represents coercing a value to a different type of value.
146 /// We transform values by following a number of `Adjust` steps in order.
147 /// See the documentation on variants of `Adjust` for more details.
149 /// Here are some common scenarios:
151 /// 1. The simplest cases are where a pointer is not adjusted fat vs thin.
152 /// Here the pointer will be dereferenced N times (where a dereference can
153 /// happen to raw or borrowed pointers or any smart pointer which implements
154 /// Deref, including Box<_>). The types of dereferences is given by
155 /// `autoderefs`. It can then be auto-referenced zero or one times, indicated
156 /// by `autoref`, to either a raw or borrowed pointer. In these cases unsize is
159 /// 2. A thin-to-fat coercion involves unsizing the underlying data. We start
160 /// with a thin pointer, deref a number of times, unsize the underlying data,
161 /// then autoref. The 'unsize' phase may change a fixed length array to a
162 /// dynamically sized one, a concrete object to a trait object, or statically
163 /// sized struct to a dynamically sized one. E.g., &[i32; 4] -> &[i32] is
167 /// Deref(None) -> [i32; 4],
168 /// Borrow(AutoBorrow::Ref) -> &[i32; 4],
169 /// Unsize -> &[i32],
172 /// Note that for a struct, the 'deep' unsizing of the struct is not recorded.
173 /// E.g., `struct Foo<T> { x: T }` we can coerce &Foo<[i32; 4]> to &Foo<[i32]>
174 /// The autoderef and -ref are the same as in the above example, but the type
175 /// stored in `unsize` is `Foo<[i32]>`, we don't store any further detail about
176 /// the underlying conversions from `[i32; 4]` to `[i32]`.
178 /// 3. Coercing a `Box<T>` to `Box<dyn Trait>` is an interesting special case. In
179 /// that case, we have the pointer we need coming in, so there are no
180 /// autoderefs, and no autoref. Instead we just do the `Unsize` transformation.
181 /// At some point, of course, `Box` should move out of the compiler, in which
182 /// case this is analogous to transforming a struct. E.g., Box<[i32; 4]> ->
183 /// Box<[i32]> is an `Adjust::Unsize` with the target `Box<[i32]>`.
184 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
185 pub struct Adjustment {
190 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
192 /// Go from ! to any type.
194 /// Dereference once, producing a place.
195 Deref(Option<OverloadedDeref>),
196 /// Take the address and produce either a `&` or `*` pointer.
198 Pointer(PointerCast),
201 /// An overloaded autoderef step, representing a `Deref(Mut)::deref(_mut)`
202 /// call, with the signature `&'a T -> &'a U` or `&'a mut T -> &'a mut U`.
203 /// The target type is `U` in both cases, with the region and mutability
204 /// being those shared by both the receiver and the returned reference.
205 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
206 pub struct OverloadedDeref(Mutability);
208 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
209 pub enum AutoBorrow {
210 /// Converts from T to &T.
212 /// Converts from T to *T.
216 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
217 pub enum PointerCast {
218 /// Go from a fn-item type to a fn-pointer type.
221 /// Go from a safe fn pointer to an unsafe fn pointer.
224 /// Go from a non-capturing closure to an fn pointer or an unsafe fn pointer.
225 /// It cannot convert a closure that requires unsafe.
226 ClosureFnPointer(Safety),
228 /// Go from a mut raw pointer to a const raw pointer.
231 /// Go from `*const [T; N]` to `*const T`
234 /// Unsize a pointer/reference value, e.g., `&[T; n]` to
235 /// `&[T]`. Note that the source could be a thin or fat pointer.
236 /// This will do things like convert thin pointers to fat
237 /// pointers, or convert structs containing thin pointers to
238 /// structs containing fat pointers, or convert between fat
239 /// pointers. We don't store the details of how the transform is
240 /// done (in fact, we don't know that, because it might depend on
241 /// the precise type parameters). We just store the target
242 /// type. Codegen backends and miri figure out what has to be done
243 /// based on the precise source/target type at hand.
247 /// The result of type inference: A mapping from expressions and patterns to types.
248 #[derive(Clone, PartialEq, Eq, Debug, Default)]
249 pub struct InferenceResult {
250 /// For each method call expr, records the function it resolves to.
251 method_resolutions: FxHashMap<ExprId, (FunctionId, Substitution)>,
252 /// For each field access expr, records the field it resolves to.
253 field_resolutions: FxHashMap<ExprId, FieldId>,
254 /// For each struct literal or pattern, records the variant it resolves to.
255 variant_resolutions: FxHashMap<ExprOrPatId, VariantId>,
256 /// For each associated item record what it resolves to
257 assoc_resolutions: FxHashMap<ExprOrPatId, AssocItemId>,
258 pub diagnostics: Vec<InferenceDiagnostic>,
259 pub type_of_expr: ArenaMap<ExprId, Ty>,
260 /// For each pattern record the type it resolves to.
262 /// **Note**: When a pattern type is resolved it may still contain
263 /// unresolved or missing subpatterns or subpatterns of mismatched types.
264 pub type_of_pat: ArenaMap<PatId, Ty>,
265 type_mismatches: FxHashMap<ExprOrPatId, TypeMismatch>,
266 /// Interned Unknown to return references to.
267 standard_types: InternedStandardTypes,
268 /// Stores the types which were implicitly dereferenced in pattern binding modes.
269 pub pat_adjustments: FxHashMap<PatId, Vec<Adjustment>>,
270 pub expr_adjustments: FxHashMap<ExprId, Vec<Adjustment>>,
273 impl InferenceResult {
274 pub fn method_resolution(&self, expr: ExprId) -> Option<(FunctionId, Substitution)> {
275 self.method_resolutions.get(&expr).cloned()
277 pub fn field_resolution(&self, expr: ExprId) -> Option<FieldId> {
278 self.field_resolutions.get(&expr).copied()
280 pub fn variant_resolution_for_expr(&self, id: ExprId) -> Option<VariantId> {
281 self.variant_resolutions.get(&id.into()).copied()
283 pub fn variant_resolution_for_pat(&self, id: PatId) -> Option<VariantId> {
284 self.variant_resolutions.get(&id.into()).copied()
286 pub fn assoc_resolutions_for_expr(&self, id: ExprId) -> Option<AssocItemId> {
287 self.assoc_resolutions.get(&id.into()).copied()
289 pub fn assoc_resolutions_for_pat(&self, id: PatId) -> Option<AssocItemId> {
290 self.assoc_resolutions.get(&id.into()).copied()
292 pub fn type_mismatch_for_expr(&self, expr: ExprId) -> Option<&TypeMismatch> {
293 self.type_mismatches.get(&expr.into())
295 pub fn type_mismatch_for_pat(&self, pat: PatId) -> Option<&TypeMismatch> {
296 self.type_mismatches.get(&pat.into())
298 pub fn expr_type_mismatches(&self) -> impl Iterator<Item = (ExprId, &TypeMismatch)> {
299 self.type_mismatches.iter().filter_map(|(expr_or_pat, mismatch)| match *expr_or_pat {
300 ExprOrPatId::ExprId(expr) => Some((expr, mismatch)),
304 pub fn pat_type_mismatches(&self) -> impl Iterator<Item = (PatId, &TypeMismatch)> {
305 self.type_mismatches.iter().filter_map(|(expr_or_pat, mismatch)| match *expr_or_pat {
306 ExprOrPatId::PatId(pat) => Some((pat, mismatch)),
312 impl Index<ExprId> for InferenceResult {
315 fn index(&self, expr: ExprId) -> &Ty {
316 self.type_of_expr.get(expr).unwrap_or(&self.standard_types.unknown)
320 impl Index<PatId> for InferenceResult {
323 fn index(&self, pat: PatId) -> &Ty {
324 self.type_of_pat.get(pat).unwrap_or(&self.standard_types.unknown)
328 /// The inference context contains all information needed during type inference.
329 #[derive(Clone, Debug)]
330 struct InferenceContext<'a> {
331 db: &'a dyn HirDatabase,
332 owner: DefWithBodyId,
335 table: unify::InferenceTable<'a>,
336 trait_env: Arc<TraitEnvironment>,
337 result: InferenceResult,
338 /// The return type of the function being inferred, or the closure if we're
339 /// currently within one.
341 /// We might consider using a nested inference context for checking
342 /// closures, but currently this is the only field that will change there,
343 /// so it doesn't make sense.
346 breakables: Vec<BreakableContext>,
349 #[derive(Clone, Debug)]
350 struct BreakableContext {
353 label: Option<name::Name>,
356 fn find_breakable<'c>(
357 ctxs: &'c mut [BreakableContext],
358 label: Option<&name::Name>,
359 ) -> Option<&'c mut BreakableContext> {
361 Some(_) => ctxs.iter_mut().rev().find(|ctx| ctx.label.as_ref() == label),
362 None => ctxs.last_mut(),
366 impl<'a> InferenceContext<'a> {
367 fn new(db: &'a dyn HirDatabase, owner: DefWithBodyId, resolver: Resolver) -> Self {
368 let krate = owner.module(db.upcast()).krate();
369 let trait_env = owner
371 .map_or_else(|| Arc::new(TraitEnvironment::empty(krate)), |d| db.trait_environment(d));
373 result: InferenceResult::default(),
374 table: unify::InferenceTable::new(db, trait_env.clone()),
376 return_ty: TyKind::Error.intern(&Interner), // set in collect_fn_signature
379 body: db.body(owner),
381 diverges: Diverges::Maybe,
382 breakables: Vec::new(),
386 fn err_ty(&self) -> Ty {
387 self.result.standard_types.unknown.clone()
390 fn resolve_all(mut self) -> InferenceResult {
391 // FIXME resolve obligations as well (use Guidance if necessary)
392 self.table.resolve_obligations_as_possible();
394 // make sure diverging type variables are marked as such
395 self.table.propagate_diverging_flag();
396 let mut result = std::mem::take(&mut self.result);
397 for ty in result.type_of_expr.values_mut() {
398 *ty = self.table.resolve_completely(ty.clone());
400 for ty in result.type_of_pat.values_mut() {
401 *ty = self.table.resolve_completely(ty.clone());
403 for mismatch in result.type_mismatches.values_mut() {
404 mismatch.expected = self.table.resolve_completely(mismatch.expected.clone());
405 mismatch.actual = self.table.resolve_completely(mismatch.actual.clone());
407 for (_, subst) in result.method_resolutions.values_mut() {
408 *subst = self.table.resolve_completely(subst.clone());
413 fn write_expr_ty(&mut self, expr: ExprId, ty: Ty) {
414 self.result.type_of_expr.insert(expr, ty);
417 fn write_expr_adj(&mut self, expr: ExprId, adjustments: Vec<Adjustment>) {
418 self.result.expr_adjustments.insert(expr, adjustments);
421 fn write_method_resolution(&mut self, expr: ExprId, func: FunctionId, subst: Substitution) {
422 self.result.method_resolutions.insert(expr, (func, subst));
425 fn write_field_resolution(&mut self, expr: ExprId, field: FieldId) {
426 self.result.field_resolutions.insert(expr, field);
429 fn write_variant_resolution(&mut self, id: ExprOrPatId, variant: VariantId) {
430 self.result.variant_resolutions.insert(id, variant);
433 fn write_assoc_resolution(&mut self, id: ExprOrPatId, item: AssocItemId) {
434 self.result.assoc_resolutions.insert(id, item);
437 fn write_pat_ty(&mut self, pat: PatId, ty: Ty) {
438 self.result.type_of_pat.insert(pat, ty);
441 fn push_diagnostic(&mut self, diagnostic: InferenceDiagnostic) {
442 self.result.diagnostics.push(diagnostic);
445 fn make_ty_with_mode(
448 impl_trait_mode: ImplTraitLoweringMode,
450 // FIXME use right resolver for block
451 let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver)
452 .with_impl_trait_mode(impl_trait_mode);
453 let ty = ctx.lower_ty(type_ref);
454 let ty = self.insert_type_vars(ty);
455 self.normalize_associated_types_in(ty)
458 fn make_ty(&mut self, type_ref: &TypeRef) -> Ty {
459 self.make_ty_with_mode(type_ref, ImplTraitLoweringMode::Disallowed)
462 /// Replaces Ty::Unknown by a new type var, so we can maybe still infer it.
463 fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty {
464 match ty.kind(&Interner) {
465 TyKind::Error => self.table.new_type_var(),
466 TyKind::InferenceVar(..) => {
467 let ty_resolved = self.resolve_ty_shallow(&ty);
468 if ty_resolved.is_unknown() {
469 self.table.new_type_var()
478 fn insert_type_vars(&mut self, ty: Ty) -> Ty {
479 fold_tys(ty, |ty, _| self.insert_type_vars_shallow(ty), DebruijnIndex::INNERMOST)
482 fn resolve_obligations_as_possible(&mut self) {
483 self.table.resolve_obligations_as_possible();
486 fn push_obligation(&mut self, o: DomainGoal) {
487 self.table.register_obligation(o.cast(&Interner));
490 fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
491 self.table.unify(ty1, ty2)
494 fn resolve_ty_shallow(&mut self, ty: &Ty) -> Ty {
495 self.resolve_obligations_as_possible();
496 self.table.resolve_ty_shallow(ty)
499 fn resolve_associated_type(&mut self, inner_ty: Ty, assoc_ty: Option<TypeAliasId>) -> Ty {
500 self.resolve_associated_type_with_params(inner_ty, assoc_ty, &[])
503 fn resolve_associated_type_with_params(
506 assoc_ty: Option<TypeAliasId>,
510 Some(res_assoc_ty) => {
511 let trait_ = match res_assoc_ty.lookup(self.db.upcast()).container {
512 hir_def::AssocContainerId::TraitId(trait_) => trait_,
513 _ => panic!("resolve_associated_type called with non-associated type"),
515 let ty = self.table.new_type_var();
516 let trait_ref = TyBuilder::trait_ref(self.db, trait_)
518 .fill(params.iter().cloned())
520 let alias_eq = AliasEq {
521 alias: AliasTy::Projection(ProjectionTy {
522 associated_ty_id: to_assoc_type_id(res_assoc_ty),
523 substitution: trait_ref.substitution.clone(),
527 self.push_obligation(trait_ref.cast(&Interner));
528 self.push_obligation(alias_eq.cast(&Interner));
531 None => self.err_ty(),
535 /// Recurses through the given type, normalizing associated types mentioned
536 /// in it by replacing them by type variables and registering obligations to
537 /// resolve later. This should be done once for every type we get from some
538 /// type annotation (e.g. from a let type annotation, field type or function
539 /// call). `make_ty` handles this already, but e.g. for field types we need
540 /// to do it as well.
541 fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty {
542 self.table.normalize_associated_types_in(ty)
545 fn resolve_variant(&mut self, path: Option<&Path>) -> (Ty, Option<VariantId>) {
546 let path = match path {
548 None => return (self.err_ty(), None),
550 let resolver = &self.resolver;
551 let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver);
552 // FIXME: this should resolve assoc items as well, see this example:
553 // https://play.rust-lang.org/?gist=087992e9e22495446c01c0d4e2d69521
554 let (resolution, unresolved) =
555 match resolver.resolve_path_in_type_ns(self.db.upcast(), path.mod_path()) {
557 None => return (self.err_ty(), None),
559 return match resolution {
560 TypeNs::AdtId(AdtId::StructId(strukt)) => {
561 let substs = ctx.substs_from_path(path, strukt.into(), true);
562 let ty = self.db.ty(strukt.into());
563 let ty = self.insert_type_vars(ty.substitute(&Interner, &substs));
564 forbid_unresolved_segments((ty, Some(strukt.into())), unresolved)
566 TypeNs::AdtId(AdtId::UnionId(u)) => {
567 let substs = ctx.substs_from_path(path, u.into(), true);
568 let ty = self.db.ty(u.into());
569 let ty = self.insert_type_vars(ty.substitute(&Interner, &substs));
570 forbid_unresolved_segments((ty, Some(u.into())), unresolved)
572 TypeNs::EnumVariantId(var) => {
573 let substs = ctx.substs_from_path(path, var.into(), true);
574 let ty = self.db.ty(var.parent.into());
575 let ty = self.insert_type_vars(ty.substitute(&Interner, &substs));
576 forbid_unresolved_segments((ty, Some(var.into())), unresolved)
578 TypeNs::SelfType(impl_id) => {
579 let generics = crate::utils::generics(self.db.upcast(), impl_id.into());
580 let substs = generics.type_params_subst(self.db);
581 let ty = self.db.impl_self_ty(impl_id).substitute(&Interner, &substs);
582 self.resolve_variant_on_alias(ty, unresolved, path)
584 TypeNs::TypeAliasId(it) => {
585 let ty = TyBuilder::def_ty(self.db, it.into())
586 .fill(std::iter::repeat_with(|| self.table.new_type_var()))
588 self.resolve_variant_on_alias(ty, unresolved, path)
590 TypeNs::AdtSelfType(_) => {
591 // FIXME this could happen in array size expressions, once we're checking them
592 (self.err_ty(), None)
594 TypeNs::GenericParam(_) => {
595 // FIXME potentially resolve assoc type
596 (self.err_ty(), None)
598 TypeNs::AdtId(AdtId::EnumId(_)) | TypeNs::BuiltinType(_) | TypeNs::TraitId(_) => {
600 (self.err_ty(), None)
604 fn forbid_unresolved_segments(
605 result: (Ty, Option<VariantId>),
606 unresolved: Option<usize>,
607 ) -> (Ty, Option<VariantId>) {
608 if unresolved.is_none() {
612 (TyKind::Error.intern(&Interner), None)
617 fn resolve_variant_on_alias(
620 unresolved: Option<usize>,
622 ) -> (Ty, Option<VariantId>) {
625 let variant = ty.as_adt().and_then(|(adt_id, _)| match adt_id {
626 AdtId::StructId(s) => Some(VariantId::StructId(s)),
627 AdtId::UnionId(u) => Some(VariantId::UnionId(u)),
628 AdtId::EnumId(_) => {
629 // FIXME Error E0071, expected struct, variant or union type, found enum `Foo`
636 let segment = path.mod_path().segments().last().unwrap();
637 // this could be an enum variant or associated type
638 if let Some((AdtId::EnumId(enum_id), _)) = ty.as_adt() {
639 let enum_data = self.db.enum_data(enum_id);
640 if let Some(local_id) = enum_data.variant(segment) {
641 let variant = EnumVariantId { parent: enum_id, local_id };
642 return (ty, Some(variant.into()));
645 // FIXME potentially resolve assoc type
646 (self.err_ty(), None)
650 (self.err_ty(), None)
655 fn collect_const(&mut self, data: &ConstData) {
656 self.return_ty = self.make_ty(&data.type_ref);
659 fn collect_static(&mut self, data: &StaticData) {
660 self.return_ty = self.make_ty(&data.type_ref);
663 fn collect_fn(&mut self, data: &FunctionData) {
664 let body = Arc::clone(&self.body); // avoid borrow checker problem
665 let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver)
666 .with_impl_trait_mode(ImplTraitLoweringMode::Param);
668 data.params.iter().map(|type_ref| ctx.lower_ty(type_ref)).collect::<Vec<_>>();
669 for (ty, pat) in param_tys.into_iter().zip(body.params.iter()) {
670 let ty = self.insert_type_vars(ty);
671 let ty = self.normalize_associated_types_in(ty);
673 self.infer_pat(*pat, &ty, BindingMode::default());
675 let error_ty = &TypeRef::Error;
676 let return_ty = if data.is_async() {
677 data.async_ret_type.as_deref().unwrap_or(error_ty)
681 let return_ty = self.make_ty_with_mode(return_ty, ImplTraitLoweringMode::Disallowed); // FIXME implement RPIT
682 self.return_ty = return_ty;
685 fn infer_body(&mut self) {
686 self.infer_expr_coerce(self.body.body_expr, &Expectation::has_type(self.return_ty.clone()));
689 fn resolve_lang_item(&self, name: &str) -> Option<LangItemTarget> {
690 let krate = self.resolver.krate()?;
691 let name = SmolStr::new_inline(name);
692 self.db.lang_item(krate, name)
695 fn resolve_into_iter_item(&self) -> Option<TypeAliasId> {
696 let path = path![core::iter::IntoIterator];
697 let trait_ = self.resolver.resolve_known_trait(self.db.upcast(), &path)?;
698 self.db.trait_data(trait_).associated_type_by_name(&name![Item])
701 fn resolve_ops_try_ok(&self) -> Option<TypeAliasId> {
702 // FIXME resolve via lang_item once try v2 is stable
703 let path = path![core::ops::Try];
704 let trait_ = self.resolver.resolve_known_trait(self.db.upcast(), &path)?;
705 let trait_data = self.db.trait_data(trait_);
707 // FIXME remove once try v2 is stable
708 .associated_type_by_name(&name![Ok])
709 .or_else(|| trait_data.associated_type_by_name(&name![Output]))
712 fn resolve_ops_neg_output(&self) -> Option<TypeAliasId> {
713 let trait_ = self.resolve_lang_item("neg")?.as_trait()?;
714 self.db.trait_data(trait_).associated_type_by_name(&name![Output])
717 fn resolve_ops_not_output(&self) -> Option<TypeAliasId> {
718 let trait_ = self.resolve_lang_item("not")?.as_trait()?;
719 self.db.trait_data(trait_).associated_type_by_name(&name![Output])
722 fn resolve_future_future_output(&self) -> Option<TypeAliasId> {
723 let trait_ = self.resolve_lang_item("future_trait")?.as_trait()?;
724 self.db.trait_data(trait_).associated_type_by_name(&name![Output])
727 fn resolve_binary_op_output(&self, bop: &BinaryOp) -> Option<TypeAliasId> {
728 let lang_item = match bop {
729 BinaryOp::ArithOp(aop) => match aop {
730 ArithOp::Add => "add",
731 ArithOp::Sub => "sub",
732 ArithOp::Mul => "mul",
733 ArithOp::Div => "div",
734 ArithOp::Shl => "shl",
735 ArithOp::Shr => "shr",
736 ArithOp::Rem => "rem",
737 ArithOp::BitXor => "bitxor",
738 ArithOp::BitOr => "bitor",
739 ArithOp::BitAnd => "bitand",
744 let trait_ = self.resolve_lang_item(lang_item)?.as_trait();
746 self.db.trait_data(trait_?).associated_type_by_name(&name![Output])
749 fn resolve_boxed_box(&self) -> Option<AdtId> {
750 let struct_ = self.resolve_lang_item("owned_box")?.as_struct()?;
754 fn resolve_range_full(&self) -> Option<AdtId> {
755 let path = path![core::ops::RangeFull];
756 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
760 fn resolve_range(&self) -> Option<AdtId> {
761 let path = path![core::ops::Range];
762 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
766 fn resolve_range_inclusive(&self) -> Option<AdtId> {
767 let path = path![core::ops::RangeInclusive];
768 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
772 fn resolve_range_from(&self) -> Option<AdtId> {
773 let path = path![core::ops::RangeFrom];
774 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
778 fn resolve_range_to(&self) -> Option<AdtId> {
779 let path = path![core::ops::RangeTo];
780 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
784 fn resolve_range_to_inclusive(&self) -> Option<AdtId> {
785 let path = path![core::ops::RangeToInclusive];
786 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
790 fn resolve_ops_index(&self) -> Option<TraitId> {
791 self.resolve_lang_item("index")?.as_trait()
794 fn resolve_ops_index_output(&self) -> Option<TypeAliasId> {
795 let trait_ = self.resolve_ops_index()?;
796 self.db.trait_data(trait_).associated_type_by_name(&name![Output])
800 /// When inferring an expression, we propagate downward whatever type hint we
801 /// are able in the form of an `Expectation`.
802 #[derive(Clone, PartialEq, Eq, Debug)]
806 // Castable(Ty), // rustc has this, we currently just don't propagate an expectation for casts
807 RValueLikeUnsized(Ty),
811 /// The expectation that the type of the expression needs to equal the given
813 fn has_type(ty: Ty) -> Self {
815 // FIXME: get rid of this?
818 Expectation::HasType(ty)
822 /// The following explanation is copied straight from rustc:
823 /// Provides an expectation for an rvalue expression given an *optional*
824 /// hint, which is not required for type safety (the resulting type might
825 /// be checked higher up, as is the case with `&expr` and `box expr`), but
826 /// is useful in determining the concrete type.
828 /// The primary use case is where the expected type is a fat pointer,
829 /// like `&[isize]`. For example, consider the following statement:
831 /// let x: &[isize] = &[1, 2, 3];
833 /// In this case, the expected type for the `&[1, 2, 3]` expression is
834 /// `&[isize]`. If however we were to say that `[1, 2, 3]` has the
835 /// expectation `ExpectHasType([isize])`, that would be too strong --
836 /// `[1, 2, 3]` does not have the type `[isize]` but rather `[isize; 3]`.
837 /// It is only the `&[1, 2, 3]` expression as a whole that can be coerced
838 /// to the type `&[isize]`. Therefore, we propagate this more limited hint,
839 /// which still is useful, because it informs integer literals and the like.
840 /// See the test case `test/ui/coerce-expect-unsized.rs` and #20169
841 /// for examples of where this comes up,.
842 fn rvalue_hint(ty: Ty) -> Self {
843 match ty.strip_references().kind(&Interner) {
844 TyKind::Slice(_) | TyKind::Str | TyKind::Dyn(_) => Expectation::RValueLikeUnsized(ty),
845 _ => Expectation::has_type(ty),
849 /// This expresses no expectation on the type.
854 fn resolve(&self, table: &mut unify::InferenceTable) -> Expectation {
856 Expectation::None => Expectation::None,
857 Expectation::HasType(t) => Expectation::HasType(table.resolve_ty_shallow(t)),
858 Expectation::RValueLikeUnsized(t) => {
859 Expectation::RValueLikeUnsized(table.resolve_ty_shallow(t))
864 fn to_option(&self, table: &mut unify::InferenceTable) -> Option<Ty> {
865 match self.resolve(table) {
866 Expectation::None => None,
867 Expectation::HasType(t) |
868 // Expectation::Castable(t) |
869 Expectation::RValueLikeUnsized(t) => Some(t),
873 fn only_has_type(&self, table: &mut unify::InferenceTable) -> Option<Ty> {
875 Expectation::HasType(t) => Some(table.resolve_ty_shallow(t)),
876 // Expectation::Castable(_) |
877 Expectation::RValueLikeUnsized(_) | Expectation::None => None,
881 /// Comment copied from rustc:
882 /// Disregard "castable to" expectations because they
883 /// can lead us astray. Consider for example `if cond
884 /// {22} else {c} as u8` -- if we propagate the
885 /// "castable to u8" constraint to 22, it will pick the
886 /// type 22u8, which is overly constrained (c might not
887 /// be a u8). In effect, the problem is that the
888 /// "castable to" expectation is not the tightest thing
889 /// we can say, so we want to drop it in this case.
890 /// The tightest thing we can say is "must unify with
891 /// else branch". Note that in the case of a "has type"
892 /// constraint, this limitation does not hold.
894 /// If the expected type is just a type variable, then don't use
895 /// an expected type. Otherwise, we might write parts of the type
896 /// when checking the 'then' block which are incompatible with the
898 fn adjust_for_branches(&self, table: &mut unify::InferenceTable) -> Expectation {
900 Expectation::HasType(ety) => {
901 let ety = table.resolve_ty_shallow(ety);
902 if !ety.is_ty_var() {
903 Expectation::HasType(ety)
908 Expectation::RValueLikeUnsized(ety) => Expectation::RValueLikeUnsized(ety.clone()),
909 _ => Expectation::None,
914 #[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
921 fn is_always(self) -> bool {
922 self == Diverges::Always
926 impl std::ops::BitAnd for Diverges {
928 fn bitand(self, other: Self) -> Self {
929 std::cmp::min(self, other)
933 impl std::ops::BitOr for Diverges {
935 fn bitor(self, other: Self) -> Self {
936 std::cmp::max(self, other)
940 impl std::ops::BitAndAssign for Diverges {
941 fn bitand_assign(&mut self, other: Self) {
942 *self = *self & other;
946 impl std::ops::BitOrAssign for Diverges {
947 fn bitor_assign(&mut self, other: Self) {
948 *self = *self | other;