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
;