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, ConstValue, DebruijnIndex, Mutability, Safety, Scalar, TypeFlags};
22 data::{ConstData, StaticData},
23 expr::{BindingAnnotation, ExprId, PatId},
24 lang_item::LangItemTarget,
26 resolver::{HasResolver, ResolveValueResult, Resolver, TypeNs, ValueNs},
28 AdtId, AssocItemId, DefWithBodyId, EnumVariantId, FieldId, FunctionId, HasModule, Lookup,
29 TraitId, TypeAliasId, VariantId,
31 use hir_expand::name::{name, Name};
32 use itertools::Either;
33 use la_arena::ArenaMap;
34 use rustc_hash::FxHashMap;
35 use stdx::{always, impl_from};
38 db::HirDatabase, fold_tys, fold_tys_and_consts, infer::coerce::CoerceMany,
39 lower::ImplTraitLoweringMode, to_assoc_type_id, AliasEq, AliasTy, Const, DomainGoal,
40 GenericArg, Goal, ImplTraitId, InEnvironment, Interner, ProjectionTy, Substitution,
41 TraitEnvironment, TraitRef, Ty, TyBuilder, TyExt, TyKind,
44 // This lint has a false positive here. See the link below for details.
46 // https://github.com/rust-lang/rust/issues/57411
47 #[allow(unreachable_pub)]
48 pub use coerce::could_coerce;
49 #[allow(unreachable_pub)]
50 pub use unify::could_unify;
59 /// The entry point of type inference.
60 pub(crate) fn infer_query(db: &dyn HirDatabase, def: DefWithBodyId) -> Arc<InferenceResult> {
61 let _p = profile::span("infer_query");
62 let resolver = def.resolver(db.upcast());
63 let body = db.body(def);
64 let mut ctx = InferenceContext::new(db, def, &body, resolver);
67 DefWithBodyId::ConstId(c) => ctx.collect_const(&db.const_data(c)),
68 DefWithBodyId::FunctionId(f) => ctx.collect_fn(f),
69 DefWithBodyId::StaticId(s) => ctx.collect_static(&db.static_data(s)),
74 Arc::new(ctx.resolve_all())
77 /// Fully normalize all the types found within `ty` in context of `owner` body definition.
79 /// This is appropriate to use only after type-check: it assumes
80 /// that normalization will succeed, for example.
81 pub(crate) fn normalize(db: &dyn HirDatabase, owner: DefWithBodyId, ty: Ty) -> Ty {
82 if !ty.data(Interner).flags.intersects(TypeFlags::HAS_PROJECTION) {
85 let krate = owner.module(db.upcast()).krate();
88 .map_or_else(|| Arc::new(TraitEnvironment::empty(krate)), |d| db.trait_environment(d));
89 let mut table = unify::InferenceTable::new(db, trait_env);
91 let ty_with_vars = table.normalize_associated_types_in(ty);
92 table.resolve_obligations_as_possible();
93 table.propagate_diverging_flag();
94 table.resolve_completely(ty_with_vars)
97 #[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
102 impl_from!(ExprId, PatId for ExprOrPatId);
104 /// Binding modes inferred for patterns.
105 /// <https://doc.rust-lang.org/reference/patterns.html#binding-modes>
106 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
107 pub enum BindingMode {
113 fn convert(annotation: BindingAnnotation) -> BindingMode {
115 BindingAnnotation::Unannotated | BindingAnnotation::Mutable => BindingMode::Move,
116 BindingAnnotation::Ref => BindingMode::Ref(Mutability::Not),
117 BindingAnnotation::RefMut => BindingMode::Ref(Mutability::Mut),
122 impl Default for BindingMode {
123 fn default() -> Self {
128 /// Used to generalize patterns and assignee expressions.
129 trait PatLike: Into<ExprOrPatId> + Copy {
130 type BindingMode: Copy;
133 this: &mut InferenceContext<'_>,
136 default_bm: Self::BindingMode,
140 impl PatLike for ExprId {
141 type BindingMode = ();
144 this: &mut InferenceContext<'_>,
147 _: Self::BindingMode,
149 this.infer_assignee_expr(id, expected_ty)
153 impl PatLike for PatId {
154 type BindingMode = BindingMode;
157 this: &mut InferenceContext<'_>,
160 default_bm: Self::BindingMode,
162 this.infer_pat(id, expected_ty, default_bm)
167 pub(crate) struct InferOk<T> {
169 goals: Vec<InEnvironment<Goal>>,
173 fn map<U>(self, f: impl FnOnce(T) -> U) -> InferOk<U> {
174 InferOk { value: f(self.value), goals: self.goals }
179 pub(crate) struct TypeError;
180 pub(crate) type InferResult<T> = Result<InferOk<T>, TypeError>;
182 #[derive(Debug, PartialEq, Eq, Clone)]
183 pub enum InferenceDiagnostic {
184 NoSuchField { expr: ExprId },
185 BreakOutsideOfLoop { expr: ExprId },
186 MismatchedArgCount { call_expr: ExprId, expected: usize, found: usize },
189 /// A mismatch between an expected and an inferred type.
190 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
191 pub struct TypeMismatch {
196 #[derive(Clone, PartialEq, Eq, Debug)]
197 struct InternedStandardTypes {
203 impl Default for InternedStandardTypes {
204 fn default() -> Self {
205 InternedStandardTypes {
206 unknown: TyKind::Error.intern(Interner),
207 bool_: TyKind::Scalar(Scalar::Bool).intern(Interner),
208 unit: TyKind::Tuple(0, Substitution::empty(Interner)).intern(Interner),
212 /// Represents coercing a value to a different type of value.
214 /// We transform values by following a number of `Adjust` steps in order.
215 /// See the documentation on variants of `Adjust` for more details.
217 /// Here are some common scenarios:
219 /// 1. The simplest cases are where a pointer is not adjusted fat vs thin.
220 /// Here the pointer will be dereferenced N times (where a dereference can
221 /// happen to raw or borrowed pointers or any smart pointer which implements
222 /// Deref, including Box<_>). The types of dereferences is given by
223 /// `autoderefs`. It can then be auto-referenced zero or one times, indicated
224 /// by `autoref`, to either a raw or borrowed pointer. In these cases unsize is
227 /// 2. A thin-to-fat coercion involves unsizing the underlying data. We start
228 /// with a thin pointer, deref a number of times, unsize the underlying data,
229 /// then autoref. The 'unsize' phase may change a fixed length array to a
230 /// dynamically sized one, a concrete object to a trait object, or statically
231 /// sized struct to a dynamically sized one. E.g., &[i32; 4] -> &[i32] is
235 /// Deref(None) -> [i32; 4],
236 /// Borrow(AutoBorrow::Ref) -> &[i32; 4],
237 /// Unsize -> &[i32],
240 /// Note that for a struct, the 'deep' unsizing of the struct is not recorded.
241 /// E.g., `struct Foo<T> { x: T }` we can coerce &Foo<[i32; 4]> to &Foo<[i32]>
242 /// The autoderef and -ref are the same as in the above example, but the type
243 /// stored in `unsize` is `Foo<[i32]>`, we don't store any further detail about
244 /// the underlying conversions from `[i32; 4]` to `[i32]`.
246 /// 3. Coercing a `Box<T>` to `Box<dyn Trait>` is an interesting special case. In
247 /// that case, we have the pointer we need coming in, so there are no
248 /// autoderefs, and no autoref. Instead we just do the `Unsize` transformation.
249 /// At some point, of course, `Box` should move out of the compiler, in which
250 /// case this is analogous to transforming a struct. E.g., Box<[i32; 4]> ->
251 /// Box<[i32]> is an `Adjust::Unsize` with the target `Box<[i32]>`.
252 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
253 pub struct Adjustment {
258 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
260 /// Go from ! to any type.
262 /// Dereference once, producing a place.
263 Deref(Option<OverloadedDeref>),
264 /// Take the address and produce either a `&` or `*` pointer.
266 Pointer(PointerCast),
269 /// An overloaded autoderef step, representing a `Deref(Mut)::deref(_mut)`
270 /// call, with the signature `&'a T -> &'a U` or `&'a mut T -> &'a mut U`.
271 /// The target type is `U` in both cases, with the region and mutability
272 /// being those shared by both the receiver and the returned reference.
273 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
274 pub struct OverloadedDeref(pub Mutability);
276 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
277 pub enum AutoBorrow {
278 /// Converts from T to &T.
280 /// Converts from T to *T.
284 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
285 pub enum PointerCast {
286 /// Go from a fn-item type to a fn-pointer type.
289 /// Go from a safe fn pointer to an unsafe fn pointer.
292 /// Go from a non-capturing closure to an fn pointer or an unsafe fn pointer.
293 /// It cannot convert a closure that requires unsafe.
294 ClosureFnPointer(Safety),
296 /// Go from a mut raw pointer to a const raw pointer.
300 /// Go from `*const [T; N]` to `*const T`
303 /// Unsize a pointer/reference value, e.g., `&[T; n]` to
304 /// `&[T]`. Note that the source could be a thin or fat pointer.
305 /// This will do things like convert thin pointers to fat
306 /// pointers, or convert structs containing thin pointers to
307 /// structs containing fat pointers, or convert between fat
308 /// pointers. We don't store the details of how the transform is
309 /// done (in fact, we don't know that, because it might depend on
310 /// the precise type parameters). We just store the target
311 /// type. Codegen backends and miri figure out what has to be done
312 /// based on the precise source/target type at hand.
316 /// The result of type inference: A mapping from expressions and patterns to types.
317 #[derive(Clone, PartialEq, Eq, Debug, Default)]
318 pub struct InferenceResult {
319 /// For each method call expr, records the function it resolves to.
320 method_resolutions: FxHashMap<ExprId, (FunctionId, Substitution)>,
321 /// For each field access expr, records the field it resolves to.
322 field_resolutions: FxHashMap<ExprId, FieldId>,
323 /// For each struct literal or pattern, records the variant it resolves to.
324 variant_resolutions: FxHashMap<ExprOrPatId, VariantId>,
325 /// For each associated item record what it resolves to
326 assoc_resolutions: FxHashMap<ExprOrPatId, AssocItemId>,
327 pub diagnostics: Vec<InferenceDiagnostic>,
328 pub type_of_expr: ArenaMap<ExprId, Ty>,
329 /// For each pattern record the type it resolves to.
331 /// **Note**: When a pattern type is resolved it may still contain
332 /// unresolved or missing subpatterns or subpatterns of mismatched types.
333 pub type_of_pat: ArenaMap<PatId, Ty>,
334 type_mismatches: FxHashMap<ExprOrPatId, TypeMismatch>,
335 /// Interned Unknown to return references to.
336 standard_types: InternedStandardTypes,
337 /// Stores the types which were implicitly dereferenced in pattern binding modes.
338 pub pat_adjustments: FxHashMap<PatId, Vec<Ty>>,
339 pub pat_binding_modes: FxHashMap<PatId, BindingMode>,
340 pub expr_adjustments: FxHashMap<ExprId, Vec<Adjustment>>,
343 impl InferenceResult {
344 pub fn method_resolution(&self, expr: ExprId) -> Option<(FunctionId, Substitution)> {
345 self.method_resolutions.get(&expr).cloned()
347 pub fn field_resolution(&self, expr: ExprId) -> Option<FieldId> {
348 self.field_resolutions.get(&expr).copied()
350 pub fn variant_resolution_for_expr(&self, id: ExprId) -> Option<VariantId> {
351 self.variant_resolutions.get(&id.into()).copied()
353 pub fn variant_resolution_for_pat(&self, id: PatId) -> Option<VariantId> {
354 self.variant_resolutions.get(&id.into()).copied()
356 pub fn assoc_resolutions_for_expr(&self, id: ExprId) -> Option<AssocItemId> {
357 self.assoc_resolutions.get(&id.into()).copied()
359 pub fn assoc_resolutions_for_pat(&self, id: PatId) -> Option<AssocItemId> {
360 self.assoc_resolutions.get(&id.into()).copied()
362 pub fn type_mismatch_for_expr(&self, expr: ExprId) -> Option<&TypeMismatch> {
363 self.type_mismatches.get(&expr.into())
365 pub fn type_mismatch_for_pat(&self, pat: PatId) -> Option<&TypeMismatch> {
366 self.type_mismatches.get(&pat.into())
368 pub fn expr_type_mismatches(&self) -> impl Iterator<Item = (ExprId, &TypeMismatch)> {
369 self.type_mismatches.iter().filter_map(|(expr_or_pat, mismatch)| match *expr_or_pat {
370 ExprOrPatId::ExprId(expr) => Some((expr, mismatch)),
374 pub fn pat_type_mismatches(&self) -> impl Iterator<Item = (PatId, &TypeMismatch)> {
375 self.type_mismatches.iter().filter_map(|(expr_or_pat, mismatch)| match *expr_or_pat {
376 ExprOrPatId::PatId(pat) => Some((pat, mismatch)),
382 impl Index<ExprId> for InferenceResult {
385 fn index(&self, expr: ExprId) -> &Ty {
386 self.type_of_expr.get(expr).unwrap_or(&self.standard_types.unknown)
390 impl Index<PatId> for InferenceResult {
393 fn index(&self, pat: PatId) -> &Ty {
394 self.type_of_pat.get(pat).unwrap_or(&self.standard_types.unknown)
398 /// The inference context contains all information needed during type inference.
399 #[derive(Clone, Debug)]
400 pub(crate) struct InferenceContext<'a> {
401 pub(crate) db: &'a dyn HirDatabase,
402 pub(crate) owner: DefWithBodyId,
403 pub(crate) body: &'a Body,
404 pub(crate) resolver: Resolver,
405 table: unify::InferenceTable<'a>,
406 trait_env: Arc<TraitEnvironment>,
407 pub(crate) result: InferenceResult,
408 /// The return type of the function being inferred, the closure or async block if we're
409 /// currently within one.
411 /// We might consider using a nested inference context for checking
412 /// closures, but currently this is the only field that will change there,
413 /// so it doesn't make sense.
416 breakables: Vec<BreakableContext>,
419 #[derive(Clone, Debug)]
420 struct BreakableContext {
423 label: Option<name::Name>,
426 fn find_breakable<'c>(
427 ctxs: &'c mut [BreakableContext],
428 label: Option<&name::Name>,
429 ) -> Option<&'c mut BreakableContext> {
431 Some(_) => ctxs.iter_mut().rev().find(|ctx| ctx.label.as_ref() == label),
432 None => ctxs.last_mut(),
436 impl<'a> InferenceContext<'a> {
438 db: &'a dyn HirDatabase,
439 owner: DefWithBodyId,
443 let krate = owner.module(db.upcast()).krate();
444 let trait_env = owner
446 .map_or_else(|| Arc::new(TraitEnvironment::empty(krate)), |d| db.trait_environment(d));
448 result: InferenceResult::default(),
449 table: unify::InferenceTable::new(db, trait_env.clone()),
451 return_ty: TyKind::Error.intern(Interner), // set in collect_fn_signature
456 diverges: Diverges::Maybe,
457 breakables: Vec::new(),
461 fn resolve_all(self) -> InferenceResult {
462 let InferenceContext { mut table, mut result, .. } = self;
464 // FIXME resolve obligations as well (use Guidance if necessary)
465 table.resolve_obligations_as_possible();
467 // make sure diverging type variables are marked as such
468 table.propagate_diverging_flag();
469 for ty in result.type_of_expr.values_mut() {
470 *ty = table.resolve_completely(ty.clone());
472 for ty in result.type_of_pat.values_mut() {
473 *ty = table.resolve_completely(ty.clone());
475 for mismatch in result.type_mismatches.values_mut() {
476 mismatch.expected = table.resolve_completely(mismatch.expected.clone());
477 mismatch.actual = table.resolve_completely(mismatch.actual.clone());
479 for (_, subst) in result.method_resolutions.values_mut() {
480 *subst = table.resolve_completely(subst.clone());
482 for adjustment in result.expr_adjustments.values_mut().flatten() {
483 adjustment.target = table.resolve_completely(adjustment.target.clone());
485 for adjustment in result.pat_adjustments.values_mut().flatten() {
486 *adjustment = table.resolve_completely(adjustment.clone());
491 fn collect_const(&mut self, data: &ConstData) {
492 self.return_ty = self.make_ty(&data.type_ref);
495 fn collect_static(&mut self, data: &StaticData) {
496 self.return_ty = self.make_ty(&data.type_ref);
499 fn collect_fn(&mut self, func: FunctionId) {
500 let data = self.db.function_data(func);
501 let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver)
502 .with_impl_trait_mode(ImplTraitLoweringMode::Param);
504 data.params.iter().map(|(_, type_ref)| ctx.lower_ty(type_ref)).collect::<Vec<_>>();
505 for (ty, pat) in param_tys.into_iter().zip(self.body.params.iter()) {
506 let ty = self.insert_type_vars(ty);
507 let ty = self.normalize_associated_types_in(ty);
509 self.infer_pat(*pat, &ty, BindingMode::default());
511 let error_ty = &TypeRef::Error;
512 let return_ty = if data.has_async_kw() {
513 data.async_ret_type.as_deref().unwrap_or(error_ty)
517 let return_ty = self.make_ty_with_mode(return_ty, ImplTraitLoweringMode::Opaque);
518 self.return_ty = return_ty;
520 if let Some(rpits) = self.db.return_type_impl_traits(func) {
521 // RPIT opaque types use substitution of their parent function.
522 let fn_placeholders = TyBuilder::placeholder_subst(self.db, func);
523 self.return_ty = fold_tys(
524 self.return_ty.clone(),
526 let opaque_ty_id = match ty.kind(Interner) {
527 TyKind::OpaqueType(opaque_ty_id, _) => *opaque_ty_id,
530 let idx = match self.db.lookup_intern_impl_trait_id(opaque_ty_id.into()) {
531 ImplTraitId::ReturnTypeImplTrait(_, idx) => idx,
534 let bounds = (*rpits).map_ref(|rpits| {
535 rpits.impl_traits[idx as usize].bounds.map_ref(|it| it.into_iter())
537 let var = self.table.new_type_var();
538 let var_subst = Substitution::from1(Interner, var.clone());
539 for bound in bounds {
541 bound.map(|it| it.cloned()).substitute(Interner, &fn_placeholders);
542 let (var_predicate, binders) = predicate
543 .substitute(Interner, &var_subst)
544 .into_value_and_skipped_binders();
545 always!(binders.len(Interner) == 0); // quantified where clauses not yet handled
546 self.push_obligation(var_predicate.cast(Interner));
550 DebruijnIndex::INNERMOST,
555 fn infer_body(&mut self) {
556 self.infer_expr_coerce(self.body.body_expr, &Expectation::has_type(self.return_ty.clone()));
559 fn write_expr_ty(&mut self, expr: ExprId, ty: Ty) {
560 self.result.type_of_expr.insert(expr, ty);
563 fn write_expr_adj(&mut self, expr: ExprId, adjustments: Vec<Adjustment>) {
564 self.result.expr_adjustments.insert(expr, adjustments);
567 fn write_method_resolution(&mut self, expr: ExprId, func: FunctionId, subst: Substitution) {
568 self.result.method_resolutions.insert(expr, (func, subst));
571 fn write_variant_resolution(&mut self, id: ExprOrPatId, variant: VariantId) {
572 self.result.variant_resolutions.insert(id, variant);
575 fn write_assoc_resolution(&mut self, id: ExprOrPatId, item: AssocItemId) {
576 self.result.assoc_resolutions.insert(id, item);
579 fn write_pat_ty(&mut self, pat: PatId, ty: Ty) {
580 self.result.type_of_pat.insert(pat, ty);
583 fn push_diagnostic(&mut self, diagnostic: InferenceDiagnostic) {
584 self.result.diagnostics.push(diagnostic);
587 fn make_ty_with_mode(
590 impl_trait_mode: ImplTraitLoweringMode,
592 // FIXME use right resolver for block
593 let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver)
594 .with_impl_trait_mode(impl_trait_mode);
595 let ty = ctx.lower_ty(type_ref);
596 let ty = self.insert_type_vars(ty);
597 self.normalize_associated_types_in(ty)
600 fn make_ty(&mut self, type_ref: &TypeRef) -> Ty {
601 self.make_ty_with_mode(type_ref, ImplTraitLoweringMode::Disallowed)
604 fn err_ty(&self) -> Ty {
605 self.result.standard_types.unknown.clone()
608 /// Replaces ConstScalar::Unknown by a new type var, so we can maybe still infer it.
609 fn insert_const_vars_shallow(&mut self, c: Const) -> Const {
610 let data = c.data(Interner);
612 ConstValue::Concrete(cc) => match cc.interned {
613 hir_def::type_ref::ConstScalar::Unknown => {
614 self.table.new_const_var(data.ty.clone())
622 /// Replaces Ty::Unknown by a new type var, so we can maybe still infer it.
623 fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty {
624 match ty.kind(Interner) {
625 TyKind::Error => self.table.new_type_var(),
626 TyKind::InferenceVar(..) => {
627 let ty_resolved = self.resolve_ty_shallow(&ty);
628 if ty_resolved.is_unknown() {
629 self.table.new_type_var()
638 fn insert_type_vars(&mut self, ty: Ty) -> Ty {
642 Either::Left(ty) => Either::Left(self.insert_type_vars_shallow(ty)),
643 Either::Right(c) => Either::Right(self.insert_const_vars_shallow(c)),
645 DebruijnIndex::INNERMOST,
649 fn resolve_obligations_as_possible(&mut self) {
650 self.table.resolve_obligations_as_possible();
653 fn push_obligation(&mut self, o: DomainGoal) {
654 self.table.register_obligation(o.cast(Interner));
657 fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
658 self.table.unify(ty1, ty2)
661 /// Recurses through the given type, normalizing associated types mentioned
662 /// in it by replacing them by type variables and registering obligations to
663 /// resolve later. This should be done once for every type we get from some
664 /// type annotation (e.g. from a let type annotation, field type or function
665 /// call). `make_ty` handles this already, but e.g. for field types we need
666 /// to do it as well.
667 fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty {
668 self.table.normalize_associated_types_in(ty)
671 fn resolve_ty_shallow(&mut self, ty: &Ty) -> Ty {
672 self.resolve_obligations_as_possible();
673 self.table.resolve_ty_shallow(ty)
676 fn resolve_associated_type(&mut self, inner_ty: Ty, assoc_ty: Option<TypeAliasId>) -> Ty {
677 self.resolve_associated_type_with_params(inner_ty, assoc_ty, &[])
680 fn resolve_associated_type_with_params(
683 assoc_ty: Option<TypeAliasId>,
684 params: &[GenericArg],
687 Some(res_assoc_ty) => {
688 let trait_ = match res_assoc_ty.lookup(self.db.upcast()).container {
689 hir_def::ItemContainerId::TraitId(trait_) => trait_,
690 _ => panic!("resolve_associated_type called with non-associated type"),
692 let ty = self.table.new_type_var();
693 let mut param_iter = params.iter().cloned();
694 let trait_ref = TyBuilder::trait_ref(self.db, trait_)
696 .fill(|_| param_iter.next().unwrap())
698 let alias_eq = AliasEq {
699 alias: AliasTy::Projection(ProjectionTy {
700 associated_ty_id: to_assoc_type_id(res_assoc_ty),
701 substitution: trait_ref.substitution.clone(),
705 self.push_obligation(trait_ref.cast(Interner));
706 self.push_obligation(alias_eq.cast(Interner));
709 None => self.err_ty(),
713 fn resolve_variant(&mut self, path: Option<&Path>, value_ns: bool) -> (Ty, Option<VariantId>) {
714 let path = match path {
716 None => return (self.err_ty(), None),
718 let resolver = &self.resolver;
719 let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver);
720 // FIXME: this should resolve assoc items as well, see this example:
721 // https://play.rust-lang.org/?gist=087992e9e22495446c01c0d4e2d69521
722 let (resolution, unresolved) = if value_ns {
723 match resolver.resolve_path_in_value_ns(self.db.upcast(), path.mod_path()) {
724 Some(ResolveValueResult::ValueNs(value)) => match value {
725 ValueNs::EnumVariantId(var) => {
726 let substs = ctx.substs_from_path(path, var.into(), true);
727 let ty = self.db.ty(var.parent.into());
728 let ty = self.insert_type_vars(ty.substitute(Interner, &substs));
729 return (ty, Some(var.into()));
731 ValueNs::StructId(strukt) => {
732 let substs = ctx.substs_from_path(path, strukt.into(), true);
733 let ty = self.db.ty(strukt.into());
734 let ty = self.insert_type_vars(ty.substitute(Interner, &substs));
735 return (ty, Some(strukt.into()));
737 _ => return (self.err_ty(), None),
739 Some(ResolveValueResult::Partial(typens, unresolved)) => (typens, Some(unresolved)),
740 None => return (self.err_ty(), None),
743 match resolver.resolve_path_in_type_ns(self.db.upcast(), path.mod_path()) {
745 None => return (self.err_ty(), None),
748 return match resolution {
749 TypeNs::AdtId(AdtId::StructId(strukt)) => {
750 let substs = ctx.substs_from_path(path, strukt.into(), true);
751 let ty = self.db.ty(strukt.into());
752 let ty = self.insert_type_vars(ty.substitute(Interner, &substs));
753 forbid_unresolved_segments((ty, Some(strukt.into())), unresolved)
755 TypeNs::AdtId(AdtId::UnionId(u)) => {
756 let substs = ctx.substs_from_path(path, u.into(), true);
757 let ty = self.db.ty(u.into());
758 let ty = self.insert_type_vars(ty.substitute(Interner, &substs));
759 forbid_unresolved_segments((ty, Some(u.into())), unresolved)
761 TypeNs::EnumVariantId(var) => {
762 let substs = ctx.substs_from_path(path, var.into(), true);
763 let ty = self.db.ty(var.parent.into());
764 let ty = self.insert_type_vars(ty.substitute(Interner, &substs));
765 forbid_unresolved_segments((ty, Some(var.into())), unresolved)
767 TypeNs::SelfType(impl_id) => {
768 let generics = crate::utils::generics(self.db.upcast(), impl_id.into());
769 let substs = generics.placeholder_subst(self.db);
770 let ty = self.db.impl_self_ty(impl_id).substitute(Interner, &substs);
771 self.resolve_variant_on_alias(ty, unresolved, path)
773 TypeNs::TypeAliasId(it) => {
774 let ty = TyBuilder::def_ty(self.db, it.into())
775 .fill_with_inference_vars(&mut self.table)
777 self.resolve_variant_on_alias(ty, unresolved, path)
779 TypeNs::AdtSelfType(_) => {
780 // FIXME this could happen in array size expressions, once we're checking them
781 (self.err_ty(), None)
783 TypeNs::GenericParam(_) => {
784 // FIXME potentially resolve assoc type
785 (self.err_ty(), None)
787 TypeNs::AdtId(AdtId::EnumId(_)) | TypeNs::BuiltinType(_) | TypeNs::TraitId(_) => {
789 (self.err_ty(), None)
793 fn forbid_unresolved_segments(
794 result: (Ty, Option<VariantId>),
795 unresolved: Option<usize>,
796 ) -> (Ty, Option<VariantId>) {
797 if unresolved.is_none() {
801 (TyKind::Error.intern(Interner), None)
806 fn resolve_variant_on_alias(
809 unresolved: Option<usize>,
811 ) -> (Ty, Option<VariantId>) {
812 let remaining = unresolved.map(|x| path.segments().skip(x).len()).filter(|x| x > &0);
815 let variant = ty.as_adt().and_then(|(adt_id, _)| match adt_id {
816 AdtId::StructId(s) => Some(VariantId::StructId(s)),
817 AdtId::UnionId(u) => Some(VariantId::UnionId(u)),
818 AdtId::EnumId(_) => {
819 // FIXME Error E0071, expected struct, variant or union type, found enum `Foo`
826 let segment = path.mod_path().segments().last().unwrap();
827 // this could be an enum variant or associated type
828 if let Some((AdtId::EnumId(enum_id), _)) = ty.as_adt() {
829 let enum_data = self.db.enum_data(enum_id);
830 if let Some(local_id) = enum_data.variant(segment) {
831 let variant = EnumVariantId { parent: enum_id, local_id };
832 return (ty, Some(variant.into()));
835 // FIXME potentially resolve assoc type
836 (self.err_ty(), None)
840 (self.err_ty(), None)
845 fn resolve_lang_item(&self, name: Name) -> Option<LangItemTarget> {
846 let krate = self.resolver.krate();
847 self.db.lang_item(krate, name.to_smol_str())
850 fn resolve_into_iter_item(&self) -> Option<TypeAliasId> {
851 let path = path![core::iter::IntoIterator];
852 let trait_ = self.resolver.resolve_known_trait(self.db.upcast(), &path)?;
853 self.db.trait_data(trait_).associated_type_by_name(&name![Item])
856 fn resolve_ops_try_ok(&self) -> Option<TypeAliasId> {
857 // FIXME resolve via lang_item once try v2 is stable
858 let path = path![core::ops::Try];
859 let trait_ = self.resolver.resolve_known_trait(self.db.upcast(), &path)?;
860 let trait_data = self.db.trait_data(trait_);
862 // FIXME remove once try v2 is stable
863 .associated_type_by_name(&name![Ok])
864 .or_else(|| trait_data.associated_type_by_name(&name![Output]))
867 fn resolve_ops_neg_output(&self) -> Option<TypeAliasId> {
868 let trait_ = self.resolve_lang_item(name![neg])?.as_trait()?;
869 self.db.trait_data(trait_).associated_type_by_name(&name![Output])
872 fn resolve_ops_not_output(&self) -> Option<TypeAliasId> {
873 let trait_ = self.resolve_lang_item(name![not])?.as_trait()?;
874 self.db.trait_data(trait_).associated_type_by_name(&name![Output])
877 fn resolve_future_future_output(&self) -> Option<TypeAliasId> {
878 let trait_ = self.resolve_lang_item(name![future_trait])?.as_trait()?;
879 self.db.trait_data(trait_).associated_type_by_name(&name![Output])
882 fn resolve_boxed_box(&self) -> Option<AdtId> {
883 let struct_ = self.resolve_lang_item(name![owned_box])?.as_struct()?;
887 fn resolve_range_full(&self) -> Option<AdtId> {
888 let path = path![core::ops::RangeFull];
889 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
893 fn resolve_range(&self) -> Option<AdtId> {
894 let path = path![core::ops::Range];
895 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
899 fn resolve_range_inclusive(&self) -> Option<AdtId> {
900 let path = path![core::ops::RangeInclusive];
901 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
905 fn resolve_range_from(&self) -> Option<AdtId> {
906 let path = path![core::ops::RangeFrom];
907 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
911 fn resolve_range_to(&self) -> Option<AdtId> {
912 let path = path![core::ops::RangeTo];
913 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
917 fn resolve_range_to_inclusive(&self) -> Option<AdtId> {
918 let path = path![core::ops::RangeToInclusive];
919 let struct_ = self.resolver.resolve_known_struct(self.db.upcast(), &path)?;
923 fn resolve_ops_index(&self) -> Option<TraitId> {
924 self.resolve_lang_item(name![index])?.as_trait()
927 fn resolve_ops_index_output(&self) -> Option<TypeAliasId> {
928 let trait_ = self.resolve_ops_index()?;
929 self.db.trait_data(trait_).associated_type_by_name(&name![Output])
933 /// When inferring an expression, we propagate downward whatever type hint we
934 /// are able in the form of an `Expectation`.
935 #[derive(Clone, PartialEq, Eq, Debug)]
936 pub(crate) enum Expectation {
939 // Castable(Ty), // rustc has this, we currently just don't propagate an expectation for casts
940 RValueLikeUnsized(Ty),
944 /// The expectation that the type of the expression needs to equal the given
946 fn has_type(ty: Ty) -> Self {
948 // FIXME: get rid of this?
951 Expectation::HasType(ty)
955 fn from_option(ty: Option<Ty>) -> Self {
956 ty.map_or(Expectation::None, Expectation::HasType)
959 /// The following explanation is copied straight from rustc:
960 /// Provides an expectation for an rvalue expression given an *optional*
961 /// hint, which is not required for type safety (the resulting type might
962 /// be checked higher up, as is the case with `&expr` and `box expr`), but
963 /// is useful in determining the concrete type.
965 /// The primary use case is where the expected type is a fat pointer,
966 /// like `&[isize]`. For example, consider the following statement:
968 /// let x: &[isize] = &[1, 2, 3];
970 /// In this case, the expected type for the `&[1, 2, 3]` expression is
971 /// `&[isize]`. If however we were to say that `[1, 2, 3]` has the
972 /// expectation `ExpectHasType([isize])`, that would be too strong --
973 /// `[1, 2, 3]` does not have the type `[isize]` but rather `[isize; 3]`.
974 /// It is only the `&[1, 2, 3]` expression as a whole that can be coerced
975 /// to the type `&[isize]`. Therefore, we propagate this more limited hint,
976 /// which still is useful, because it informs integer literals and the like.
977 /// See the test case `test/ui/coerce-expect-unsized.rs` and #20169
978 /// for examples of where this comes up,.
979 fn rvalue_hint(table: &mut unify::InferenceTable<'_>, ty: Ty) -> Self {
980 // FIXME: do struct_tail_without_normalization
981 match table.resolve_ty_shallow(&ty).kind(Interner) {
982 TyKind::Slice(_) | TyKind::Str | TyKind::Dyn(_) => Expectation::RValueLikeUnsized(ty),
983 _ => Expectation::has_type(ty),
987 /// This expresses no expectation on the type.
992 fn resolve(&self, table: &mut unify::InferenceTable<'_>) -> Expectation {
994 Expectation::None => Expectation::None,
995 Expectation::HasType(t) => Expectation::HasType(table.resolve_ty_shallow(t)),
996 Expectation::RValueLikeUnsized(t) => {
997 Expectation::RValueLikeUnsized(table.resolve_ty_shallow(t))
1002 fn to_option(&self, table: &mut unify::InferenceTable<'_>) -> Option<Ty> {
1003 match self.resolve(table) {
1004 Expectation::None => None,
1005 Expectation::HasType(t) |
1006 // Expectation::Castable(t) |
1007 Expectation::RValueLikeUnsized(t) => Some(t),
1011 fn only_has_type(&self, table: &mut unify::InferenceTable<'_>) -> Option<Ty> {
1013 Expectation::HasType(t) => Some(table.resolve_ty_shallow(t)),
1014 // Expectation::Castable(_) |
1015 Expectation::RValueLikeUnsized(_) | Expectation::None => None,
1019 /// Comment copied from rustc:
1020 /// Disregard "castable to" expectations because they
1021 /// can lead us astray. Consider for example `if cond
1022 /// {22} else {c} as u8` -- if we propagate the
1023 /// "castable to u8" constraint to 22, it will pick the
1024 /// type 22u8, which is overly constrained (c might not
1025 /// be a u8). In effect, the problem is that the
1026 /// "castable to" expectation is not the tightest thing
1027 /// we can say, so we want to drop it in this case.
1028 /// The tightest thing we can say is "must unify with
1029 /// else branch". Note that in the case of a "has type"
1030 /// constraint, this limitation does not hold.
1032 /// If the expected type is just a type variable, then don't use
1033 /// an expected type. Otherwise, we might write parts of the type
1034 /// when checking the 'then' block which are incompatible with the
1036 fn adjust_for_branches(&self, table: &mut unify::InferenceTable<'_>) -> Expectation {
1038 Expectation::HasType(ety) => {
1039 let ety = table.resolve_ty_shallow(ety);
1040 if !ety.is_ty_var() {
1041 Expectation::HasType(ety)
1046 Expectation::RValueLikeUnsized(ety) => Expectation::RValueLikeUnsized(ety.clone()),
1047 _ => Expectation::None,
1052 #[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
1059 fn is_always(self) -> bool {
1060 self == Diverges::Always
1064 impl std::ops::BitAnd for Diverges {
1066 fn bitand(self, other: Self) -> Self {
1067 std::cmp::min(self, other)
1071 impl std::ops::BitOr for Diverges {
1073 fn bitor(self, other: Self) -> Self {
1074 std::cmp::max(self, other)
1078 impl std::ops::BitAndAssign for Diverges {
1079 fn bitand_assign(&mut self, other: Self) {
1080 *self = *self & other;
1084 impl std::ops::BitOrAssign for Diverges {
1085 fn bitor_assign(&mut self, other: Self) {
1086 *self = *self | other;