use std::{cell::OnceCell, convert::identity, iter, ops::Index};

use base_db::Crate;

use either::Either;

use hir_def::{

AdtId, AssocItemId, ConstId, DefWithBodyId, FieldId, FunctionId, GenericDefId, GenericParamId,

ImplId, ItemContainerId, LocalFieldId, Lookup, TraitId, TupleFieldId, TupleId, TypeAliasId,

VariantId,

expr_store::{Body, ExpressionStore, HygieneId, path::Path},

hir::{BindingAnnotation, BindingId, ExprId, ExprOrPatId, LabelId, PatId},

lang_item::{LangItem, LangItemTarget, lang_item},

use indexmap::IndexSet;

use intern::sym;

use la_arena::{ArenaMap, Entry};

use rustc_hash::{FxHashMap, FxHashSet};

use triomphe::Arc;

use crate::{

generics::Generics,

infer::{

coerce::{CoerceMany, DynamicCoerceMany},

expr::ExprIsRead,

unify::InferenceTable,

},

mir::MirSpan,

next_solver::{

mapping::{ChalkToNextSolver, NextSolverToChalk},

},

traits::FnTrait,

};

// This lint has a false positive here. See the link below for details.

pub(crate) use closure::analysis::{CaptureKind, CapturedItem, CapturedItemWithoutTy};

/// The entry point of type inference.

let _p = tracing::info_span!("infer_query").entered();

let resolver = def.resolver(db);

let body = db.body(def);

DefWithBodyId::ConstId(c) => ctx.collect_const(c, &db.const_signature(c)),

DefWithBodyId::StaticId(s) => ctx.collect_static(&db.static_signature(s)),

DefWithBodyId::VariantId(v) => {

},

},

},

}

}

Arc::new(ctx.resolve_all())

}

}

/// Fully normalize all the types found within `ty` in context of `owner` body definition.

/// This is appropriate to use only after type-check: it assumes

/// that normalization will succeed, for example.

#[tracing::instrument(level = "debug", skip(db))]

// FIXME: TypeFlags::HAS_CT_PROJECTION is not implemented in chalk, so TypeFlags::HAS_PROJECTION only

// works for the type case, so we check array unconditionally. Remove the array part

// when the bug in chalk becomes fixed.

{

return ty;

}

let mut table = unify::InferenceTable::new(db, trait_env);

table.select_obligations_where_possible();

}

/// Binding modes inferred for patterns.

}

}

#[derive(Debug, PartialEq, Eq, Clone, Copy)]

pub enum InferenceTyDiagnosticSource {

/// Diagnostics that come from types in the body.

Signature,

}

#[derive(Debug, PartialEq, Eq, Clone)]

NoSuchField {

field: ExprOrPatId,

private: Option<LocalFieldId>,

},

UnresolvedField {

expr: ExprId,

name: Name,

method_with_same_name_exists: bool,

},

UnresolvedMethodCall {

expr: ExprId,

name: Name,

/// Contains the type the field resolves to

assoc_func_with_same_name: Option<FunctionId>,

},

UnresolvedAssocItem {

},

ExpectedFunction {

call_expr: ExprId,

},

TypedHole {

expr: ExprId,

},

CastToUnsized {

expr: ExprId,

},

InvalidCast {

expr: ExprId,

error: CastError,

},

TyDiagnostic {

source: InferenceTyDiagnosticSource,

/// A mismatch between an expected and an inferred type.

#[derive(Clone, PartialEq, Eq, Debug, Hash)]

}

/// Represents coercing a value to a different type of value.

///

/// We transform values by following a number of `Adjust` steps in order.

/// case this is analogous to transforming a struct. E.g., Box<[i32; 4]> ->

/// Box<[i32]> is an `Adjust::Unsize` with the target `Box<[i32]>`.

#[derive(Clone, Debug, PartialEq, Eq, Hash)]

}

Adjustment { kind: Adjust::Borrow(AutoBorrow::Ref(lt, m)), target: ty }

}

}

}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]

/// Go from ! to any type.

NeverToAny,

/// Dereference once, producing a place.

Deref(Option<OverloadedDeref>),

/// Take the address and produce either a `&` or `*` pointer.

Pointer(PointerCast),

}

pub struct OverloadedDeref(pub Option<Mutability>);

#[derive(Clone, Debug, PartialEq, Eq, Hash)]

/// Converts from T to &T.

/// Converts from T to *T.

RawPtr(Mutability),

}

fn mutability(&self) -> Mutability {

let (AutoBorrow::Ref(_, m) | AutoBorrow::RawPtr(m)) = self;

*m

/// When you add a field that stores types (including `Substitution` and the like), don't forget

/// `resolve_completely()`'ing them in `InferenceContext::resolve_all()`. Inference variables must

/// not appear in the final inference result.

/// For each method call expr, records the function it resolves to.

/// For each field access expr, records the field it resolves to.

field_resolutions: FxHashMap<ExprId, Either<FieldId, TupleFieldId>>,

/// For each struct literal or pattern, records the variant it resolves to.

variant_resolutions: FxHashMap<ExprOrPatId, VariantId>,

/// For each associated item record what it resolves to

/// Whenever a tuple field expression access a tuple field, we allocate a tuple id in

/// [`InferenceContext`] and store the tuples substitution there. This map is the reverse of

/// that which allows us to resolve a [`TupleFieldId`]s type.

/// During inference this field is empty and [`InferenceContext::diagnostics`] is filled instead.

/// For each pattern record the type it resolves to.

///

/// **Note**: When a pattern type is resolved it may still contain

/// unresolved or missing subpatterns or subpatterns of mismatched types.

/// Whether there are any type-mismatching errors in the result.

// FIXME: This isn't as useful as initially thought due to us falling back placeholders to

// `TyKind::Error`.

// Which will then mark this field.

pub(crate) has_errors: bool,

/// Stores the types which were implicitly dereferenced in pattern binding modes.

/// Stores the binding mode (`ref` in `let ref x = 2`) of bindings.

///

/// This one is tied to the `PatId` instead of `BindingId`, because in some rare cases, a binding in an

/// ```

/// the first `rest` has implicit `ref` binding mode, but the second `rest` binding mode is `move`.

pub(crate) binding_modes: ArenaMap<PatId, BindingMode>,

// FIXME: remove this field

pub mutated_bindings_in_closure: FxHashSet<BindingId>,

pub(crate) coercion_casts: FxHashSet<ExprId>,

}

}

pub fn field_resolution(&self, expr: ExprId) -> Option<Either<FieldId, TupleFieldId>> {

self.field_resolutions.get(&expr).copied()

ExprOrPatId::PatId(id) => self.variant_resolution_for_pat(id),

}

}

}

}

pub fn assoc_resolutions_for_expr_or_pat(

&self,

id: ExprOrPatId,

match id {

ExprOrPatId::ExprId(id) => self.assoc_resolutions_for_expr(id),

ExprOrPatId::PatId(id) => self.assoc_resolutions_for_pat(id),

}

}

self.type_mismatches.get(&expr.into())

}

self.type_mismatches.get(&pat.into())

}

self.type_mismatches.iter().map(|(expr_or_pat, mismatch)| (*expr_or_pat, mismatch))

}

self.type_mismatches.iter().filter_map(|(expr_or_pat, mismatch)| match *expr_or_pat {

ExprOrPatId::ExprId(expr) => Some((expr, mismatch)),

_ => None,

})

}

}

match id {

}

}

match self.expr_adjustments.get(&id).and_then(|adjustments| {

adjustments

.iter()

})

.next_back()

}) {

}

}

match self.pat_adjustments.get(&id).and_then(|adjustments| adjustments.last()) {

}

}

pub fn is_erroneous(&self) -> bool {

self.has_errors && self.type_of_expr.iter().count() == 0

}

&self.diagnostics

}

}

self.pat_adjustments.get(&id).map(|it| &**it)

}

self.expr_adjustments.get(&id).map(|it| &**it)

}

}

// This method is consumed by external tools to run rust-analyzer as a library. Don't remove, please.

}

// This method is consumed by external tools to run rust-analyzer as a library. Don't remove, please.

}

// This method is consumed by external tools to run rust-analyzer as a library. Don't remove, please.

}

// This method is consumed by external tools to run rust-analyzer as a library. Don't remove, please.

}

}

}

}

}

}

}

}

}

}

#[derive(Debug, Clone)]

}

fn new(interner: DbInterner<'db>) -> Self {

Self {

}

}

}

/// The inference context contains all information needed during type inference.

#[derive(Clone, Debug)]

pub(crate) db: &'db dyn HirDatabase,

pub(crate) owner: DefWithBodyId,

/// Generally you should not resolve things via this resolver. Instead create a TyLoweringContext

/// and resolve the path via its methods. This will ensure proper error reporting.

pub(crate) resolver: Resolver<'db>,

table: unify::InferenceTable<'db>,

/// The traits in scope, disregarding block modules. This is used for caching purposes.

traits_in_scope: FxHashSet<TraitId>,

tuple_field_accesses_rev:

/// The return type of the function being inferred, the closure or async block if we're

/// currently within one.

///

/// We might consider using a nested inference context for checking

/// closures so we can swap all shared things out at once.

/// If `Some`, this stores coercion information for returned

/// expressions. If `None`, this is in a context where return is

/// inappropriate, such as a const expression.

return_coercion: Option<DynamicCoerceMany<'db>>,

/// The resume type and the yield type, respectively, of the coroutine being inferred.

diverges: Diverges,

breakables: Vec<BreakableContext<'db>>,

/// Whether we are inside the pattern of a destructuring assignment.

inside_assignment: bool,

// fields related to closure capture

/// A stack that has an entry for each projection in the current capture.

///

/// For example, in `a.b.c`, we capture the spans of `a`, `a.b`, and `a.b.c`.

/// Stores the list of closure ids that need to be analyzed before this closure. See the

/// comment on `InferenceContext::sort_closures`

closure_dependencies: FxHashMap<InternedClosureId, Vec<InternedClosureId>>,

}

#[derive(Clone, Debug)]

}

}

TypeAlias,

}

fn new(

db: &'db dyn HirDatabase,

owner: DefWithBodyId,

resolver: Resolver<'db>,

) -> Self {

let trait_env = db.trait_environment_for_body(owner);

let table = unify::InferenceTable::new(db, trait_env);

InferenceContext {

target_features: OnceCell::new(),

generics: OnceCell::new(),

table,

tuple_field_accesses_rev: Default::default(),

resume_yield_tys: None,

return_coercion: None,

db,

/// Clones `self` and calls `resolve_all()` on it.

// FIXME: Remove this.

let mut ctx = self.clone();

ctx.type_inference_fallback();

// `InferenceResult` in the middle of inference. See the fixme comment in `consteval::eval_to_const`. If you

// used this function for another workaround, mention it here. If you really need this function and believe that

// there is no problem in it being `pub(crate)`, remove this comment.

let InferenceContext {

mut table, mut result, tuple_field_accesses_rev, diagnostics, ..

} = self;

type_of_rpit,

type_mismatches,

has_errors,

pat_adjustments,

binding_modes: _,

expr_adjustments,

} = &mut result;

for ty in type_of_expr.values_mut() {

}

type_of_expr.shrink_to_fit();

for ty in type_of_pat.values_mut() {

}

type_of_pat.shrink_to_fit();

for ty in type_of_binding.values_mut() {

}

type_of_binding.shrink_to_fit();

for ty in type_of_rpit.values_mut() {

}

type_of_rpit.shrink_to_fit();

*has_errors |= !type_mismatches.is_empty();

type_mismatches.shrink_to_fit();

diagnostics.retain_mut(|diagnostic| {

use InferenceDiagnostic::*;

ExpectedFunction { found: ty, .. }

| UnresolvedField { receiver: ty, .. }

| UnresolvedMethodCall { receiver: ty, .. } => {

// FIXME: Remove this when we are on par with rustc in terms of inference

return false;

}

if let UnresolvedMethodCall { field_with_same_name, .. } = diagnostic

&& let Some(ty) = field_with_same_name

{

*field_with_same_name = None;

}

}

}

TypedHole { expected: ty, .. } => {

}

_ => (),

}

});

diagnostics.shrink_to_fit();

for (_, subst) in method_resolutions.values_mut() {

}

method_resolutions.shrink_to_fit();

for (_, subst) in assoc_resolutions.values_mut() {

}

assoc_resolutions.shrink_to_fit();

for adjustment in expr_adjustments.values_mut().flatten() {

}

expr_adjustments.shrink_to_fit();

for adjustment in pat_adjustments.values_mut().flatten() {

}

pat_adjustments.shrink_to_fit();

result.tuple_field_access_types = tuple_field_accesses_rev

.into_iter()

.enumerate()

.inspect(|(_, subst)| {

})

.collect();

result.tuple_field_access_types.shrink_to_fit();

data.type_ref,

&data.store,

InferenceTyDiagnosticSource::Signature,

);

// Constants might be defining usage sites of TAITs.

self.return_ty = return_ty;

}

data.type_ref,

&data.store,

InferenceTyDiagnosticSource::Signature,

);

// Statics might be defining usage sites of TAITs.

self.return_ty = return_ty;

}

&data.store,

InferenceTyDiagnosticSource::Signature,

LifetimeElisionKind::for_fn_params(&data),

);

// Check if function contains a va_list, if it does then we append it to the parameter types

// that are collected from the function data

if data.is_varargs() {

let va_list_ty = match self.resolve_va_list() {

None => self.err_ty(),

};

param_tys.push(va_list_ty);

}

if let Some(self_param) = self.body.self_param

&& let Some(ty) = param_tys.next()

{

for (ty, pat) in param_tys.zip(&*self.body.params) {

let ty = self.process_user_written_ty(ty);

tait_candidates.insert(ty);

}

}

let return_ty = self.with_ty_lowering(

&data.store,

InferenceTyDiagnosticSource::Signature,

|ctx| {

ctx.lower_ty(return_ty)

},

);

let return_ty = self.insert_type_vars(return_ty);

let mut mode = ImplTraitReplacingMode::ReturnPosition(FxHashSet::default());

if let ImplTraitReplacingMode::ReturnPosition(taits) = mode {

tait_candidates.extend(taits);

}

for (id, _) in rpits.impl_traits.iter() {

if let Entry::Vacant(e) = self.result.type_of_rpit.entry(id) {

never!("Missed RPIT in `insert_inference_vars_for_rpit`");

}

}

result

return_ty

}

}

};

self.return_ty = self.process_user_written_ty(return_ty);

// Functions might be defining usage sites of TAITs.

// To define an TAITs, that TAIT must appear in the function's signatures.

// So, it suffices to check for params and return types.

}

}

fn insert_inference_vars_for_impl_trait<T>(

&mut self,

t: T,

) -> T

where

{

}

}

}

/// The coercion of a non-inference var into an opaque type should fail,

/// - We are pushing `impl Trait` bounds into it

///

/// This function inserts a map that maps the opaque type to that proxy inference var.

}

&& let ImplTraitId::TypeAliasImplTrait(alias_id, _) =

{

let loc = self.db.lookup_intern_type_alias(alias_id);

match loc.container {

ItemContainerId::ImplId(impl_id) => {

}

ItemContainerId::ModuleId(..) | ItemContainerId::ExternBlockId(..) => {

}

_ => {}

}

}

}

}

non_assocs: FxHashMap::default(),

};

for ty in tait_candidates {

}

// Non-assoc TAITs can be define-used everywhere as long as they are

let tait_coercion_table: FxHashMap<_, _> = taits

.into_iter()

.filter_map(|(id, ty)| {

{

let ty = self.insert_inference_vars_for_impl_trait(

ty,

&mut ImplTraitReplacingMode::TypeAlias,

);

Some((id, ty))

None => {

_ = self.infer_expr_coerce(

self.body.body_expr,

ExprIsRead::Yes,

)

}

}

}

self.result.type_of_expr.insert(expr, ty);

}

if adjustments.is_empty() {

return;

}

) => {

// NeverToAny coercion can target any type, so instead of adding a new

// adjustment on top we can change the target.

}

_ => {

*entry.get_mut() = adjustments;

}

}

if adjustments.is_empty() {

return;

}

self.result.pat_adjustments.entry(pat).or_default().extend(adjustments);

}

self.result.method_resolutions.insert(expr, (func, subst));

}

self.result.variant_resolutions.insert(id, variant);

}

self.result.assoc_resolutions.insert(id, (item, subs));

}

self.result.type_of_pat.insert(pat, ty);

}

self.result.type_of_binding.insert(id, ty);

}

self.diagnostics.push(diagnostic);

}

&mut self,

store: &ExpressionStore,

types_source: InferenceTyDiagnosticSource,

) -> R {

let mut ctx = TyLoweringContext::new(

self.db,

f(&mut ctx)

}

self.with_ty_lowering(

self.body,

InferenceTyDiagnosticSource::Body,

type_ref: TypeRefId,

store: &ExpressionStore,

type_source: InferenceTyDiagnosticSource,

let ty = self

.with_ty_lowering(store, type_source, lifetime_elision, |ctx| ctx.lower_ty(type_ref));

self.process_user_written_ty(ty)

}

self.make_ty(

type_ref,

self.body,

)

}

let const_ = self.with_ty_lowering(

self.body,

InferenceTyDiagnosticSource::Body,

LifetimeElisionKind::Infer,

);

self.insert_type_vars(const_)

}

let const_ = self.with_ty_lowering(

self.body,

InferenceTyDiagnosticSource::Body,

LifetimeElisionKind::Infer,

);

self.insert_type_vars(const_)

}

}

let lt = self.with_ty_lowering(

self.body,

InferenceTyDiagnosticSource::Body,

}

/// Replaces `Ty::Error` by a new type var, so we can maybe still infer it.

self.table.insert_type_vars_shallow(ty)

}

fn insert_type_vars<T>(&mut self, ty: T) -> T

where

{

self.table.insert_type_vars(ty)

}

}

/// Attempts to returns the deeply last field of nested structures, but

/// does not apply any normalization in its search. Returns the same type

/// if input `ty` is not a structure at all.

self.struct_tail_with_normalize(ty, identity)

}

/// function to indicate no normalization should take place.

fn struct_tail_with_normalize(

&mut self,

// FIXME: fetch the limit properly

let recursion_limit = 10;

for iteration in 0.. {

if iteration > recursion_limit {

return self.err_ty();

}

}

}

TyKind::Alias(..) => {

if ty == normalized {

return ty;

} else {

}

/// Whenever you lower a user-written type, you should call this.

where

{

self.table.process_user_written_ty(ty)

}

/// The difference of this method from `process_user_written_ty()` is that this method doesn't register a well-formed obligation,

/// while `process_user_written_ty()` should (but doesn't currently).

where

{

self.table.process_remote_user_written_ty(ty)

}

self.table.shallow_resolve(ty)

}

self.resolve_associated_type_with_params(inner_ty, assoc_ty, &[])

}

let result = self

.table

.infer_ctxt

fn resolve_associated_type_with_params(

&mut self,

assoc_ty: Option<TypeAliasId>,

// FIXME(GATs): these are args for the trait ref, args for assoc type itself should be

// handled when we support them.

match assoc_ty {

Some(res_assoc_ty) => {

}

None => self.err_ty(),

}

node: ExprOrPatId,

path: Option<&Path>,

value_ns: bool,

let path = match path {

Some(path) => path,

None => return (self.err_ty(), None),

match res {

ResolveValueResult::ValueNs(value, _) => match value {

ValueNs::EnumVariantId(var) => {

drop(ctx);

let ty = self

.db

.ty(var.lookup(self.db).parent.into())

let ty = self.insert_type_vars(ty);

return (ty, Some(var.into()));

}

ValueNs::StructId(strukt) => {

drop(ctx);

let ty = self.insert_type_vars(ty);

return (ty, Some(strukt.into()));

}

};

return match resolution {

TypeNs::AdtId(AdtId::StructId(strukt)) => {

drop(ctx);

let ty = self.insert_type_vars(ty);

}

TypeNs::AdtId(AdtId::UnionId(u)) => {

drop(ctx);

let ty = self.insert_type_vars(ty);

}

TypeNs::EnumVariantId(var) => {

drop(ctx);

let ty = self.insert_type_vars(ty);

}

TypeNs::SelfType(impl_id) => {

let Some(remaining_idx) = unresolved else {

drop(ctx);

while let Some(current_segment) = remaining_segments.first() {

// If we can resolve to an enum variant, it takes priority over associated type

// of the same name.

let enum_data = id.enum_variants(self.db);

if let Some(variant) = enum_data.variant(current_segment.name) {

return if remaining_segments.len() == 1 {

ty = self.table.insert_type_vars(ty);

ty = self.table.normalize_associated_types_in(ty);

return (self.err_ty(), None);

}

never!("resolver should always resolve lang item paths");

return (self.err_ty(), None);

};

drop(ctx);

let interner = DbInterner::conjure();

let ty = self.insert_type_vars(ty);

self.resolve_variant_on_alias(ty, unresolved, mod_path)

}

};

unresolved: Option<usize>,

if unresolved.is_none() {

result

} else {

// FIXME diagnostic

}

}

}

fn resolve_variant_on_alias(

&mut self,

unresolved: Option<usize>,

path: &ModPath,

let remaining = unresolved.map(|it| path.segments()[it..].len()).filter(|it| it > &0);

match remaining {

None => {

let variant = ty.as_adt().and_then(|(adt_id, _)| match adt_id {

/// When inferring an expression, we propagate downward whatever type hint we

/// are able in the form of an `Expectation`.

#[derive(Clone, PartialEq, Eq, Debug)]

None,

}

/// The expectation that the type of the expression needs to equal the given

/// type.

// FIXME: get rid of this?

Expectation::None

} else {

/// which still is useful, because it informs integer literals and the like.

/// See the test case `test/ui/coerce-expect-unsized.rs` and #20169

/// for examples of where this comes up,.

_ => Expectation::has_type(ty),

}

}

Expectation::None

}

match self {

Expectation::None => Expectation::None,

Expectation::RValueLikeUnsized(t) => {

}

}

}

match self.resolve(table) {

Expectation::None => None,

Expectation::HasType(t)

}

}

match self {

Expectation::Castable(_) | Expectation::RValueLikeUnsized(_) | Expectation::None => {

None

}

}

}

}

/// Comment copied from rustc:

/// an expected type. Otherwise, we might write parts of the type

/// when checking the 'then' block which are incompatible with the

/// 'else' branch.

Expectation::HasType(ety) => {

let ety = table.structurally_resolve_type(ety);

if ety.is_ty_var() { Expectation::None } else { Expectation::HasType(ety) }

}

_ => Expectation::None,

}

}

*self = *self | other;

}

}