//! This module is concerned with finding methods that a given type provides.
//! For details about how this works in rustc, see the method lookup page in the
//! [rustc guide](https://rust-lang.github.io/rustc-guide/method-lookup.html)
//! and the corresponding code mostly in rustc_hir_analysis/check/method/probe.rs.
use std::ops::ControlFlow;

use base_db::CrateId;
use chalk_ir::{cast::Cast, UniverseIndex, WithKind};
use hir_def::{
    data::{adt::StructFlags, ImplData},
    nameres::DefMap,
    AssocItemId, BlockId, ConstId, FunctionId, HasModule, ImplId, ItemContainerId, Lookup,
    ModuleId, TraitId,
};
use hir_expand::name::Name;
use intern::sym;
use rustc_hash::{FxHashMap, FxHashSet};
use smallvec::{smallvec, SmallVec};
use stdx::never;
use triomphe::Arc;

use crate::{
    autoderef::{self, AutoderefKind},
    db::HirDatabase,
    error_lifetime, from_chalk_trait_id, from_foreign_def_id,
    infer::{unify::InferenceTable, Adjust, Adjustment, OverloadedDeref, PointerCast},
    lang_items::is_box,
    primitive::{FloatTy, IntTy, UintTy},
    to_chalk_trait_id,
    utils::all_super_traits,
    AdtId, Canonical, CanonicalVarKinds, DebruijnIndex, DynTyExt, ForeignDefId, GenericArgData,
    Goal, Guidance, InEnvironment, Interner, Mutability, Scalar, Solution, Substitution,
    TraitEnvironment, TraitRef, TraitRefExt, Ty, TyBuilder, TyExt, TyKind, TyVariableKind,
    VariableKind, WhereClause,
};

/// This is used as a key for indexing impls.
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum TyFingerprint {
    // These are lang item impls:
    Str,
    Slice,
    Array,
    Never,
    RawPtr(Mutability),
    Scalar(Scalar),
    // These can have user-defined impls:
    Adt(hir_def::AdtId),
    Dyn(TraitId),
    ForeignType(ForeignDefId),
    // These only exist for trait impls
    Unit,
    Unnameable,
    Function(u32),
}

impl TyFingerprint {
    /// Creates a TyFingerprint for looking up an inherent impl. Only certain
    /// types can have inherent impls: if we have some `struct S`, we can have
    /// an `impl S`, but not `impl &S`. Hence, this will return `None` for
    /// reference types and such.
    pub fn for_inherent_impl(ty: &Ty) -> Option<TyFingerprint> {
        let fp = match ty.kind(Interner) {
            TyKind::Str => TyFingerprint::Str,
            TyKind::Never => TyFingerprint::Never,
            TyKind::Slice(..) => TyFingerprint::Slice,
            TyKind::Array(..) => TyFingerprint::Array,
            TyKind::Scalar(scalar) => TyFingerprint::Scalar(*scalar),
            TyKind::Adt(AdtId(adt), _) => TyFingerprint::Adt(*adt),
            TyKind::Raw(mutability, ..) => TyFingerprint::RawPtr(*mutability),
            TyKind::Foreign(alias_id, ..) => TyFingerprint::ForeignType(*alias_id),
            TyKind::Dyn(_) => ty.dyn_trait().map(TyFingerprint::Dyn)?,
            _ => return None,
        };
        Some(fp)
    }

    /// Creates a TyFingerprint for looking up a trait impl.
    pub fn for_trait_impl(ty: &Ty) -> Option<TyFingerprint> {
        let fp = match ty.kind(Interner) {
            TyKind::Str => TyFingerprint::Str,
            TyKind::Never => TyFingerprint::Never,
            TyKind::Slice(..) => TyFingerprint::Slice,
            TyKind::Array(..) => TyFingerprint::Array,
            TyKind::Scalar(scalar) => TyFingerprint::Scalar(*scalar),
            TyKind::Adt(AdtId(adt), _) => TyFingerprint::Adt(*adt),
            TyKind::Raw(mutability, ..) => TyFingerprint::RawPtr(*mutability),
            TyKind::Foreign(alias_id, ..) => TyFingerprint::ForeignType(*alias_id),
            TyKind::Dyn(_) => ty.dyn_trait().map(TyFingerprint::Dyn)?,
            TyKind::Ref(_, _, ty) => return TyFingerprint::for_trait_impl(ty),
            TyKind::Tuple(_, subst) => {
                let first_ty = subst.interned().first().map(|arg| arg.assert_ty_ref(Interner));
                match first_ty {
                    Some(ty) => return TyFingerprint::for_trait_impl(ty),
                    None => TyFingerprint::Unit,
                }
            }
            TyKind::AssociatedType(_, _)
            | TyKind::OpaqueType(_, _)
            | TyKind::FnDef(_, _)
            | TyKind::Closure(_, _)
            | TyKind::Coroutine(..)
            | TyKind::CoroutineWitness(..) => TyFingerprint::Unnameable,
            TyKind::Function(fn_ptr) => {
                TyFingerprint::Function(fn_ptr.substitution.0.len(Interner) as u32)
            }
            TyKind::Alias(_)
            | TyKind::Placeholder(_)
            | TyKind::BoundVar(_)
            | TyKind::InferenceVar(_, _)
            | TyKind::Error => return None,
        };
        Some(fp)
    }
}

pub(crate) const ALL_INT_FPS: [TyFingerprint; 12] = [
    TyFingerprint::Scalar(Scalar::Int(IntTy::I8)),
    TyFingerprint::Scalar(Scalar::Int(IntTy::I16)),
    TyFingerprint::Scalar(Scalar::Int(IntTy::I32)),
    TyFingerprint::Scalar(Scalar::Int(IntTy::I64)),
    TyFingerprint::Scalar(Scalar::Int(IntTy::I128)),
    TyFingerprint::Scalar(Scalar::Int(IntTy::Isize)),
    TyFingerprint::Scalar(Scalar::Uint(UintTy::U8)),
    TyFingerprint::Scalar(Scalar::Uint(UintTy::U16)),
    TyFingerprint::Scalar(Scalar::Uint(UintTy::U32)),
    TyFingerprint::Scalar(Scalar::Uint(UintTy::U64)),
    TyFingerprint::Scalar(Scalar::Uint(UintTy::U128)),
    TyFingerprint::Scalar(Scalar::Uint(UintTy::Usize)),
];

pub(crate) const ALL_FLOAT_FPS: [TyFingerprint; 4] = [
    TyFingerprint::Scalar(Scalar::Float(FloatTy::F16)),
    TyFingerprint::Scalar(Scalar::Float(FloatTy::F32)),
    TyFingerprint::Scalar(Scalar::Float(FloatTy::F64)),
    TyFingerprint::Scalar(Scalar::Float(FloatTy::F128)),
];

type TraitFpMap = FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Box<[ImplId]>>>;
type TraitFpMapCollector = FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Vec<ImplId>>>;

/// Trait impls defined or available in some crate.
#[derive(Debug, Eq, PartialEq)]
pub struct TraitImpls {
    // If the `Option<TyFingerprint>` is `None`, the impl may apply to any self type.
    map: TraitFpMap,
}

impl TraitImpls {
    pub(crate) fn trait_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
        let _p = tracing::info_span!("trait_impls_in_crate_query", ?krate).entered();
        let mut impls = FxHashMap::default();

        Self::collect_def_map(db, &mut impls, &db.crate_def_map(krate));

        Arc::new(Self::finish(impls))
    }

    pub(crate) fn trait_impls_in_block_query(
        db: &dyn HirDatabase,
        block: BlockId,
    ) -> Option<Arc<Self>> {
        let _p = tracing::info_span!("trait_impls_in_block_query").entered();
        let mut impls = FxHashMap::default();

        Self::collect_def_map(db, &mut impls, &db.block_def_map(block));

        if impls.is_empty() {
            None
        } else {
            Some(Arc::new(Self::finish(impls)))
        }
    }

    pub(crate) fn trait_impls_in_deps_query(
        db: &dyn HirDatabase,
        krate: CrateId,
    ) -> Arc<[Arc<Self>]> {
        let _p = tracing::info_span!("trait_impls_in_deps_query", ?krate).entered();
        let crate_graph = db.crate_graph();

        Arc::from_iter(
            crate_graph.transitive_deps(krate).map(|krate| db.trait_impls_in_crate(krate)),
        )
    }

    fn finish(map: TraitFpMapCollector) -> TraitImpls {
        TraitImpls {
            map: map
                .into_iter()
                .map(|(k, v)| (k, v.into_iter().map(|(k, v)| (k, v.into_boxed_slice())).collect()))
                .collect(),
        }
    }

    fn collect_def_map(db: &dyn HirDatabase, map: &mut TraitFpMapCollector, def_map: &DefMap) {
        for (_module_id, module_data) in def_map.modules() {
            for impl_id in module_data.scope.impls() {
                // Reservation impls should be ignored during trait resolution, so we never need
                // them during type analysis. See rust-lang/rust#64631 for details.
                //
                // FIXME: Reservation impls should be considered during coherence checks. If we are
                // (ever) to implement coherence checks, this filtering should be done by the trait
                // solver.
                if db.attrs(impl_id.into()).by_key(&sym::rustc_reservation_impl).exists() {
                    continue;
                }
                let target_trait = match db.impl_trait(impl_id) {
                    Some(tr) => tr.skip_binders().hir_trait_id(),
                    None => continue,
                };
                let self_ty = db.impl_self_ty(impl_id);
                let self_ty_fp = TyFingerprint::for_trait_impl(self_ty.skip_binders());
                map.entry(target_trait).or_default().entry(self_ty_fp).or_default().push(impl_id);
            }

            // To better support custom derives, collect impls in all unnamed const items.
            // const _: () = { ... };
            for konst in module_data.scope.unnamed_consts() {
                let body = db.body(konst.into());
                for (_, block_def_map) in body.blocks(db.upcast()) {
                    Self::collect_def_map(db, map, &block_def_map);
                }
            }
        }
    }

    /// Queries all trait impls for the given type.
    pub fn for_self_ty_without_blanket_impls(
        &self,
        fp: TyFingerprint,
    ) -> impl Iterator<Item = ImplId> + '_ {
        self.map
            .values()
            .flat_map(move |impls| impls.get(&Some(fp)).into_iter())
            .flat_map(|it| it.iter().copied())
    }

    /// Queries all impls of the given trait.
    pub fn for_trait(&self, trait_: TraitId) -> impl Iterator<Item = ImplId> + '_ {
        self.map
            .get(&trait_)
            .into_iter()
            .flat_map(|map| map.values().flat_map(|v| v.iter().copied()))
    }

    /// Queries all impls of `trait_` that may apply to `self_ty`.
    pub fn for_trait_and_self_ty(
        &self,
        trait_: TraitId,
        self_ty: TyFingerprint,
    ) -> impl Iterator<Item = ImplId> + '_ {
        self.map
            .get(&trait_)
            .into_iter()
            .flat_map(move |map| map.get(&Some(self_ty)).into_iter().chain(map.get(&None)))
            .flat_map(|v| v.iter().copied())
    }

    /// Queries whether `self_ty` has potentially applicable implementations of `trait_`.
    pub fn has_impls_for_trait_and_self_ty(&self, trait_: TraitId, self_ty: TyFingerprint) -> bool {
        self.for_trait_and_self_ty(trait_, self_ty).next().is_some()
    }

    pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ {
        self.map.values().flat_map(|map| map.values().flat_map(|v| v.iter().copied()))
    }
}

/// Inherent impls defined in some crate.
///
/// Inherent impls can only be defined in the crate that also defines the self type of the impl
/// (note that some primitives are considered to be defined by both libcore and liballoc).
///
/// This makes inherent impl lookup easier than trait impl lookup since we only have to consider a
/// single crate.
#[derive(Debug, Eq, PartialEq)]
pub struct InherentImpls {
    map: FxHashMap<TyFingerprint, Vec<ImplId>>,
    invalid_impls: Vec<ImplId>,
}

impl InherentImpls {
    pub(crate) fn inherent_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
        let _p = tracing::info_span!("inherent_impls_in_crate_query", ?krate).entered();
        let mut impls = Self { map: FxHashMap::default(), invalid_impls: Vec::default() };

        let crate_def_map = db.crate_def_map(krate);
        impls.collect_def_map(db, &crate_def_map);
        impls.shrink_to_fit();

        Arc::new(impls)
    }

    pub(crate) fn inherent_impls_in_block_query(
        db: &dyn HirDatabase,
        block: BlockId,
    ) -> Option<Arc<Self>> {
        let _p = tracing::info_span!("inherent_impls_in_block_query").entered();
        let mut impls = Self { map: FxHashMap::default(), invalid_impls: Vec::default() };

        let block_def_map = db.block_def_map(block);
        impls.collect_def_map(db, &block_def_map);
        impls.shrink_to_fit();

        if impls.map.is_empty() && impls.invalid_impls.is_empty() {
            None
        } else {
            Some(Arc::new(impls))
        }
    }

    fn shrink_to_fit(&mut self) {
        self.map.values_mut().for_each(Vec::shrink_to_fit);
        self.map.shrink_to_fit();
    }

    fn collect_def_map(&mut self, db: &dyn HirDatabase, def_map: &DefMap) {
        for (_module_id, module_data) in def_map.modules() {
            for impl_id in module_data.scope.impls() {
                let data = db.impl_data(impl_id);
                if data.target_trait.is_some() {
                    continue;
                }

                let self_ty = db.impl_self_ty(impl_id);
                let self_ty = self_ty.skip_binders();

                match is_inherent_impl_coherent(db, def_map, &data, self_ty) {
                    true => {
                        // `fp` should only be `None` in error cases (either erroneous code or incomplete name resolution)
                        if let Some(fp) = TyFingerprint::for_inherent_impl(self_ty) {
                            self.map.entry(fp).or_default().push(impl_id);
                        }
                    }
                    false => self.invalid_impls.push(impl_id),
                }
            }

            // To better support custom derives, collect impls in all unnamed const items.
            // const _: () = { ... };
            for konst in module_data.scope.unnamed_consts() {
                let body = db.body(konst.into());
                for (_, block_def_map) in body.blocks(db.upcast()) {
                    self.collect_def_map(db, &block_def_map);
                }
            }
        }
    }

    pub fn for_self_ty(&self, self_ty: &Ty) -> &[ImplId] {
        match TyFingerprint::for_inherent_impl(self_ty) {
            Some(fp) => self.map.get(&fp).map(|vec| vec.as_ref()).unwrap_or(&[]),
            None => &[],
        }
    }

    pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ {
        self.map.values().flat_map(|v| v.iter().copied())
    }

    pub fn invalid_impls(&self) -> &[ImplId] {
        &self.invalid_impls
    }
}

pub(crate) fn incoherent_inherent_impl_crates(
    db: &dyn HirDatabase,
    krate: CrateId,
    fp: TyFingerprint,
) -> SmallVec<[CrateId; 2]> {
    let _p = tracing::info_span!("incoherent_inherent_impl_crates").entered();
    let mut res = SmallVec::new();
    let crate_graph = db.crate_graph();

    // should pass crate for finger print and do reverse deps

    for krate in crate_graph.transitive_deps(krate) {
        let impls = db.inherent_impls_in_crate(krate);
        if impls.map.get(&fp).map_or(false, |v| !v.is_empty()) {
            res.push(krate);
        }
    }

    res
}

pub fn def_crates(
    db: &dyn HirDatabase,
    ty: &Ty,
    cur_crate: CrateId,
) -> Option<SmallVec<[CrateId; 2]>> {
    match ty.kind(Interner) {
        &TyKind::Adt(AdtId(def_id), _) => {
            let rustc_has_incoherent_inherent_impls = match def_id {
                hir_def::AdtId::StructId(id) => db
                    .struct_data(id)
                    .flags
                    .contains(StructFlags::IS_RUSTC_HAS_INCOHERENT_INHERENT_IMPL),
                hir_def::AdtId::UnionId(id) => db
                    .union_data(id)
                    .flags
                    .contains(StructFlags::IS_RUSTC_HAS_INCOHERENT_INHERENT_IMPL),
                hir_def::AdtId::EnumId(id) => db.enum_data(id).rustc_has_incoherent_inherent_impls,
            };
            Some(if rustc_has_incoherent_inherent_impls {
                db.incoherent_inherent_impl_crates(cur_crate, TyFingerprint::Adt(def_id))
            } else {
                smallvec![def_id.module(db.upcast()).krate()]
            })
        }
        &TyKind::Foreign(id) => {
            let alias = from_foreign_def_id(id);
            Some(if db.type_alias_data(alias).rustc_has_incoherent_inherent_impls {
                db.incoherent_inherent_impl_crates(cur_crate, TyFingerprint::ForeignType(id))
            } else {
                smallvec![alias.module(db.upcast()).krate()]
            })
        }
        TyKind::Dyn(_) => {
            let trait_id = ty.dyn_trait()?;
            Some(if db.trait_data(trait_id).rustc_has_incoherent_inherent_impls {
                db.incoherent_inherent_impl_crates(cur_crate, TyFingerprint::Dyn(trait_id))
            } else {
                smallvec![trait_id.module(db.upcast()).krate()]
            })
        }
        // for primitives, there may be impls in various places (core and alloc
        // mostly). We just check the whole crate graph for crates with impls
        // (cached behind a query).
        TyKind::Scalar(_)
        | TyKind::Str
        | TyKind::Slice(_)
        | TyKind::Array(..)
        | TyKind::Raw(..) => Some(db.incoherent_inherent_impl_crates(
            cur_crate,
            TyFingerprint::for_inherent_impl(ty).expect("fingerprint for primitive"),
        )),
        _ => None,
    }
}

/// Look up the method with the given name.
pub(crate) fn lookup_method(
    db: &dyn HirDatabase,
    ty: &Canonical<Ty>,
    env: Arc<TraitEnvironment>,
    traits_in_scope: &FxHashSet<TraitId>,
    visible_from_module: VisibleFromModule,
    name: &Name,
) -> Option<(ReceiverAdjustments, FunctionId, bool)> {
    let mut not_visible = None;
    let res = iterate_method_candidates(
        ty,
        db,
        env,
        traits_in_scope,
        visible_from_module,
        Some(name),
        LookupMode::MethodCall,
        |adjustments, f, visible| match f {
            AssocItemId::FunctionId(f) if visible => Some((adjustments, f, true)),
            AssocItemId::FunctionId(f) if not_visible.is_none() => {
                not_visible = Some((adjustments, f, false));
                None
            }
            _ => None,
        },
    );
    res.or(not_visible)
}

/// Whether we're looking up a dotted method call (like `v.len()`) or a path
/// (like `Vec::new`).
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub enum LookupMode {
    /// Looking up a method call like `v.len()`: We only consider candidates
    /// that have a `self` parameter, and do autoderef.
    MethodCall,
    /// Looking up a path like `Vec::new` or `Vec::default`: We consider all
    /// candidates including associated constants, but don't do autoderef.
    Path,
}

#[derive(Clone, Copy)]
pub enum VisibleFromModule {
    /// Filter for results that are visible from the given module
    Filter(ModuleId),
    /// Include impls from the given block.
    IncludeBlock(BlockId),
    /// Do nothing special in regards visibility
    None,
}

impl From<Option<ModuleId>> for VisibleFromModule {
    fn from(module: Option<ModuleId>) -> Self {
        match module {
            Some(module) => Self::Filter(module),
            None => Self::None,
        }
    }
}

impl From<Option<BlockId>> for VisibleFromModule {
    fn from(block: Option<BlockId>) -> Self {
        match block {
            Some(block) => Self::IncludeBlock(block),
            None => Self::None,
        }
    }
}

#[derive(Debug, Clone, Default)]
pub struct ReceiverAdjustments {
    autoref: Option<Mutability>,
    autoderefs: usize,
    unsize_array: bool,
}

impl ReceiverAdjustments {
    pub(crate) fn apply(&self, table: &mut InferenceTable<'_>, ty: Ty) -> (Ty, Vec<Adjustment>) {
        let mut ty = table.resolve_ty_shallow(&ty);
        let mut adjust = Vec::new();
        for _ in 0..self.autoderefs {
            match autoderef::autoderef_step(table, ty.clone(), true) {
                None => {
                    never!("autoderef not possible for {:?}", ty);
                    ty = TyKind::Error.intern(Interner);
                    break;
                }
                Some((kind, new_ty)) => {
                    ty = new_ty.clone();
                    adjust.push(Adjustment {
                        kind: Adjust::Deref(match kind {
                            // FIXME should we know the mutability here, when autoref is `None`?
                            AutoderefKind::Overloaded => Some(OverloadedDeref(self.autoref)),
                            AutoderefKind::Builtin => None,
                        }),
                        target: new_ty,
                    });
                }
            }
        }
        if let Some(m) = self.autoref {
            let lt = table.new_lifetime_var();
            let a = Adjustment::borrow(m, ty, lt);
            ty = a.target.clone();
            adjust.push(a);
        }
        if self.unsize_array {
            ty = 'it: {
                if let TyKind::Ref(m, l, inner) = ty.kind(Interner) {
                    if let TyKind::Array(inner, _) = inner.kind(Interner) {
                        break 'it TyKind::Ref(
                            *m,
                            l.clone(),
                            TyKind::Slice(inner.clone()).intern(Interner),
                        )
                        .intern(Interner);
                    }
                }
                // FIXME: report diagnostic if array unsizing happens without indirection.
                ty
            };
            adjust.push(Adjustment {
                kind: Adjust::Pointer(PointerCast::Unsize),
                target: ty.clone(),
            });
        }
        (ty, adjust)
    }

    fn with_autoref(&self, m: Mutability) -> ReceiverAdjustments {
        Self { autoref: Some(m), ..*self }
    }
}

// This would be nicer if it just returned an iterator, but that runs into
// lifetime problems, because we need to borrow temp `CrateImplDefs`.
// FIXME add a context type here?
pub(crate) fn iterate_method_candidates<T>(
    ty: &Canonical<Ty>,
    db: &dyn HirDatabase,
    env: Arc<TraitEnvironment>,
    traits_in_scope: &FxHashSet<TraitId>,
    visible_from_module: VisibleFromModule,
    name: Option<&Name>,
    mode: LookupMode,
    mut callback: impl FnMut(ReceiverAdjustments, AssocItemId, bool) -> Option<T>,
) -> Option<T> {
    let mut slot = None;
    iterate_method_candidates_dyn(
        ty,
        db,
        env,
        traits_in_scope,
        visible_from_module,
        name,
        mode,
        &mut |adj, item, visible| {
            assert!(slot.is_none());
            if let Some(it) = callback(adj, item, visible) {
                slot = Some(it);
                return ControlFlow::Break(());
            }
            ControlFlow::Continue(())
        },
    );
    slot
}

pub fn lookup_impl_const(
    db: &dyn HirDatabase,
    env: Arc<TraitEnvironment>,
    const_id: ConstId,
    subs: Substitution,
) -> (ConstId, Substitution) {
    let trait_id = match const_id.lookup(db.upcast()).container {
        ItemContainerId::TraitId(id) => id,
        _ => return (const_id, subs),
    };
    let substitution = Substitution::from_iter(Interner, subs.iter(Interner));
    let trait_ref = TraitRef { trait_id: to_chalk_trait_id(trait_id), substitution };

    let const_data = db.const_data(const_id);
    let name = match const_data.name.as_ref() {
        Some(name) => name,
        None => return (const_id, subs),
    };

    lookup_impl_assoc_item_for_trait_ref(trait_ref, db, env, name)
        .and_then(
            |assoc| if let (AssocItemId::ConstId(id), s) = assoc { Some((id, s)) } else { None },
        )
        .unwrap_or((const_id, subs))
}

/// Checks if the self parameter of `Trait` method is the `dyn Trait` and we should
/// call the method using the vtable.
pub fn is_dyn_method(
    db: &dyn HirDatabase,
    _env: Arc<TraitEnvironment>,
    func: FunctionId,
    fn_subst: Substitution,
) -> Option<usize> {
    let ItemContainerId::TraitId(trait_id) = func.lookup(db.upcast()).container else {
        return None;
    };
    let trait_params = db.generic_params(trait_id.into()).len();
    let fn_params = fn_subst.len(Interner) - trait_params;
    let trait_ref = TraitRef {
        trait_id: to_chalk_trait_id(trait_id),
        substitution: Substitution::from_iter(Interner, fn_subst.iter(Interner).skip(fn_params)),
    };
    let self_ty = trait_ref.self_type_parameter(Interner);
    if let TyKind::Dyn(d) = self_ty.kind(Interner) {
        let is_my_trait_in_bounds = d
            .bounds
            .skip_binders()
            .as_slice(Interner)
            .iter()
            .map(|it| it.skip_binders())
            .flat_map(|it| match it {
                WhereClause::Implemented(tr) => {
                    all_super_traits(db.upcast(), from_chalk_trait_id(tr.trait_id))
                }
                _ => smallvec![],
            })
            // rustc doesn't accept `impl Foo<2> for dyn Foo<5>`, so if the trait id is equal, no matter
            // what the generics are, we are sure that the method is come from the vtable.
            .any(|x| x == trait_id);
        if is_my_trait_in_bounds {
            return Some(fn_params);
        }
    }
    None
}

/// Looks up the impl method that actually runs for the trait method `func`.
///
/// Returns `func` if it's not a method defined in a trait or the lookup failed.
pub(crate) fn lookup_impl_method_query(
    db: &dyn HirDatabase,
    env: Arc<TraitEnvironment>,
    func: FunctionId,
    fn_subst: Substitution,
) -> (FunctionId, Substitution) {
    let ItemContainerId::TraitId(trait_id) = func.lookup(db.upcast()).container else {
        return (func, fn_subst);
    };
    let trait_params = db.generic_params(trait_id.into()).len();
    let fn_params = fn_subst.len(Interner) - trait_params;
    let trait_ref = TraitRef {
        trait_id: to_chalk_trait_id(trait_id),
        substitution: Substitution::from_iter(Interner, fn_subst.iter(Interner).skip(fn_params)),
    };

    let name = &db.function_data(func).name;
    let Some((impl_fn, impl_subst)) =
        lookup_impl_assoc_item_for_trait_ref(trait_ref, db, env, name).and_then(|assoc| {
            if let (AssocItemId::FunctionId(id), subst) = assoc {
                Some((id, subst))
            } else {
                None
            }
        })
    else {
        return (func, fn_subst);
    };
    (
        impl_fn,
        Substitution::from_iter(
            Interner,
            fn_subst.iter(Interner).take(fn_params).chain(impl_subst.iter(Interner)),
        ),
    )
}

fn lookup_impl_assoc_item_for_trait_ref(
    trait_ref: TraitRef,
    db: &dyn HirDatabase,
    env: Arc<TraitEnvironment>,
    name: &Name,
) -> Option<(AssocItemId, Substitution)> {
    let hir_trait_id = trait_ref.hir_trait_id();
    let self_ty = trait_ref.self_type_parameter(Interner);
    let self_ty_fp = TyFingerprint::for_trait_impl(&self_ty)?;
    let impls = db.trait_impls_in_deps(env.krate);
    let self_impls = match self_ty.kind(Interner) {
        TyKind::Adt(id, _) => {
            id.0.module(db.upcast()).containing_block().and_then(|it| db.trait_impls_in_block(it))
        }
        _ => None,
    };
    let impls = impls
        .iter()
        .chain(self_impls.as_ref())
        .flat_map(|impls| impls.for_trait_and_self_ty(hir_trait_id, self_ty_fp));

    let table = InferenceTable::new(db, env);

    let (impl_data, impl_subst) = find_matching_impl(impls, table, trait_ref)?;
    let item = impl_data.items.iter().find_map(|&it| match it {
        AssocItemId::FunctionId(f) => {
            (db.function_data(f).name == *name).then_some(AssocItemId::FunctionId(f))
        }
        AssocItemId::ConstId(c) => db
            .const_data(c)
            .name
            .as_ref()
            .map(|n| n == name)
            .and_then(|result| if result { Some(AssocItemId::ConstId(c)) } else { None }),
        AssocItemId::TypeAliasId(_) => None,
    })?;
    Some((item, impl_subst))
}

fn find_matching_impl(
    mut impls: impl Iterator<Item = ImplId>,
    mut table: InferenceTable<'_>,
    actual_trait_ref: TraitRef,
) -> Option<(Arc<ImplData>, Substitution)> {
    let db = table.db;
    impls.find_map(|impl_| {
        table.run_in_snapshot(|table| {
            let impl_data = db.impl_data(impl_);
            let impl_substs =
                TyBuilder::subst_for_def(db, impl_, None).fill_with_inference_vars(table).build();
            let trait_ref = db
                .impl_trait(impl_)
                .expect("non-trait method in find_matching_impl")
                .substitute(Interner, &impl_substs);

            if !table.unify(&trait_ref, &actual_trait_ref) {
                return None;
            }

            let wcs = crate::chalk_db::convert_where_clauses(db, impl_.into(), &impl_substs)
                .into_iter()
                .map(|b| b.cast(Interner));
            let goal = crate::Goal::all(Interner, wcs);
            table.try_obligation(goal.clone())?;
            table.register_obligation(goal);
            Some((impl_data, table.resolve_completely(impl_substs)))
        })
    })
}

fn is_inherent_impl_coherent(
    db: &dyn HirDatabase,
    def_map: &DefMap,
    impl_data: &ImplData,
    self_ty: &Ty,
) -> bool {
    let self_ty = self_ty.kind(Interner);
    let impl_allowed = match self_ty {
        TyKind::Tuple(_, _)
        | TyKind::FnDef(_, _)
        | TyKind::Array(_, _)
        | TyKind::Never
        | TyKind::Raw(_, _)
        | TyKind::Ref(_, _, _)
        | TyKind::Slice(_)
        | TyKind::Str
        | TyKind::Scalar(_) => def_map.is_rustc_coherence_is_core(),

        &TyKind::Adt(AdtId(adt), _) => adt.module(db.upcast()).krate() == def_map.krate(),
        TyKind::Dyn(it) => it.principal().map_or(false, |trait_ref| {
            from_chalk_trait_id(trait_ref.trait_id).module(db.upcast()).krate() == def_map.krate()
        }),

        _ => true,
    };
    impl_allowed || {
        let rustc_has_incoherent_inherent_impls = match self_ty {
            TyKind::Tuple(_, _)
            | TyKind::FnDef(_, _)
            | TyKind::Array(_, _)
            | TyKind::Never
            | TyKind::Raw(_, _)
            | TyKind::Ref(_, _, _)
            | TyKind::Slice(_)
            | TyKind::Str
            | TyKind::Scalar(_) => true,

            &TyKind::Adt(AdtId(adt), _) => match adt {
                hir_def::AdtId::StructId(id) => db
                    .struct_data(id)
                    .flags
                    .contains(StructFlags::IS_RUSTC_HAS_INCOHERENT_INHERENT_IMPL),
                hir_def::AdtId::UnionId(id) => db
                    .union_data(id)
                    .flags
                    .contains(StructFlags::IS_RUSTC_HAS_INCOHERENT_INHERENT_IMPL),
                hir_def::AdtId::EnumId(it) => db.enum_data(it).rustc_has_incoherent_inherent_impls,
            },
            TyKind::Dyn(it) => it.principal().map_or(false, |trait_ref| {
                db.trait_data(from_chalk_trait_id(trait_ref.trait_id))
                    .rustc_has_incoherent_inherent_impls
            }),

            _ => false,
        };
        rustc_has_incoherent_inherent_impls
            && !impl_data.items.is_empty()
            && impl_data.items.iter().copied().all(|assoc| match assoc {
                AssocItemId::FunctionId(it) => db.function_data(it).rustc_allow_incoherent_impl,
                AssocItemId::ConstId(it) => db.const_data(it).rustc_allow_incoherent_impl,
                AssocItemId::TypeAliasId(it) => db.type_alias_data(it).rustc_allow_incoherent_impl,
            })
    }
}

/// Checks whether the impl satisfies the orphan rules.
///
/// Given `impl<P1..=Pn> Trait<T1..=Tn> for T0`, an `impl`` is valid only if at least one of the following is true:
/// - Trait is a local trait
/// - All of
///   - At least one of the types `T0..=Tn`` must be a local type. Let `Ti`` be the first such type.
///   - No uncovered type parameters `P1..=Pn` may appear in `T0..Ti`` (excluding `Ti`)
pub fn check_orphan_rules(db: &dyn HirDatabase, impl_: ImplId) -> bool {
    let substs = TyBuilder::placeholder_subst(db, impl_);
    let Some(impl_trait) = db.impl_trait(impl_) else {
        // not a trait impl
        return true;
    };

    let local_crate = impl_.lookup(db.upcast()).container.krate();
    let is_local = |tgt_crate| tgt_crate == local_crate;

    let trait_ref = impl_trait.substitute(Interner, &substs);
    let trait_id = from_chalk_trait_id(trait_ref.trait_id);
    if is_local(trait_id.module(db.upcast()).krate()) {
        // trait to be implemented is local
        return true;
    }

    let unwrap_fundamental = |ty: Ty| match ty.kind(Interner) {
        TyKind::Ref(_, _, referenced) => referenced.clone(),
        &TyKind::Adt(AdtId(hir_def::AdtId::StructId(s)), ref subs) => {
            let struct_data = db.struct_data(s);
            if struct_data.flags.contains(StructFlags::IS_FUNDAMENTAL) {
                let next = subs.type_parameters(Interner).next();
                match next {
                    Some(ty) => ty,
                    None => ty,
                }
            } else {
                ty
            }
        }
        _ => ty,
    };
    //   - At least one of the types `T0..=Tn`` must be a local type. Let `Ti`` be the first such type.
    let is_not_orphan = trait_ref.substitution.type_parameters(Interner).any(|ty| {
        match unwrap_fundamental(ty).kind(Interner) {
            &TyKind::Adt(AdtId(id), _) => is_local(id.module(db.upcast()).krate()),
            TyKind::Error => true,
            TyKind::Dyn(it) => it.principal().map_or(false, |trait_ref| {
                is_local(from_chalk_trait_id(trait_ref.trait_id).module(db.upcast()).krate())
            }),
            _ => false,
        }
    });
    // FIXME: param coverage
    //   - No uncovered type parameters `P1..=Pn` may appear in `T0..Ti`` (excluding `Ti`)
    is_not_orphan
}

pub fn iterate_path_candidates(
    ty: &Canonical<Ty>,
    db: &dyn HirDatabase,
    env: Arc<TraitEnvironment>,
    traits_in_scope: &FxHashSet<TraitId>,
    visible_from_module: VisibleFromModule,
    name: Option<&Name>,
    callback: &mut dyn FnMut(AssocItemId) -> ControlFlow<()>,
) -> ControlFlow<()> {
    iterate_method_candidates_dyn(
        ty,
        db,
        env,
        traits_in_scope,
        visible_from_module,
        name,
        LookupMode::Path,
        // the adjustments are not relevant for path lookup
        &mut |_, id, _| callback(id),
    )
}

pub fn iterate_method_candidates_dyn(
    ty: &Canonical<Ty>,
    db: &dyn HirDatabase,
    env: Arc<TraitEnvironment>,
    traits_in_scope: &FxHashSet<TraitId>,
    visible_from_module: VisibleFromModule,
    name: Option<&Name>,
    mode: LookupMode,
    callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
) -> ControlFlow<()> {
    let _p = tracing::info_span!(
        "iterate_method_candidates_dyn",
        ?mode,
        ?name,
        traits_in_scope_len = traits_in_scope.len()
    )
    .entered();

    match mode {
        LookupMode::MethodCall => {
            // For method calls, rust first does any number of autoderef, and
            // then one autoref (i.e. when the method takes &self or &mut self).
            // Note that when we've got a receiver like &S, even if the method
            // we find in the end takes &self, we still do the autoderef step
            // (just as rustc does an autoderef and then autoref again).

            // We have to be careful about the order we're looking at candidates
            // in here. Consider the case where we're resolving `it.clone()`
            // where `it: &Vec<_>`. This resolves to the clone method with self
            // type `Vec<_>`, *not* `&_`. I.e. we need to consider methods where
            // the receiver type exactly matches before cases where we have to
            // do autoref. But in the autoderef steps, the `&_` self type comes
            // up *before* the `Vec<_>` self type.
            //
            // On the other hand, we don't want to just pick any by-value method
            // before any by-autoref method; it's just that we need to consider
            // the methods by autoderef order of *receiver types*, not *self
            // types*.

            let mut table = InferenceTable::new(db, env);
            let ty = table.instantiate_canonical(ty.clone());
            let deref_chain = autoderef_method_receiver(&mut table, ty);

            deref_chain.into_iter().try_for_each(|(receiver_ty, adj)| {
                iterate_method_candidates_with_autoref(
                    &mut table,
                    receiver_ty,
                    adj,
                    traits_in_scope,
                    visible_from_module,
                    name,
                    callback,
                )
            })
        }
        LookupMode::Path => {
            // No autoderef for path lookups
            iterate_method_candidates_for_self_ty(
                ty,
                db,
                env,
                traits_in_scope,
                visible_from_module,
                name,
                callback,
            )
        }
    }
}

#[tracing::instrument(skip_all, fields(name = ?name))]
fn iterate_method_candidates_with_autoref(
    table: &mut InferenceTable<'_>,
    receiver_ty: Canonical<Ty>,
    first_adjustment: ReceiverAdjustments,
    traits_in_scope: &FxHashSet<TraitId>,
    visible_from_module: VisibleFromModule,
    name: Option<&Name>,
    mut callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
) -> ControlFlow<()> {
    if receiver_ty.value.is_general_var(Interner, &receiver_ty.binders) {
        // don't try to resolve methods on unknown types
        return ControlFlow::Continue(());
    }

    let mut iterate_method_candidates_by_receiver = move |receiver_ty, first_adjustment| {
        iterate_method_candidates_by_receiver(
            table,
            receiver_ty,
            first_adjustment,
            traits_in_scope,
            visible_from_module,
            name,
            &mut callback,
        )
    };

    let mut maybe_reborrowed = first_adjustment.clone();
    if let Some((_, _, m)) = receiver_ty.value.as_reference() {
        // Prefer reborrow of references to move
        maybe_reborrowed.autoref = Some(m);
        maybe_reborrowed.autoderefs += 1;
    }

    iterate_method_candidates_by_receiver(receiver_ty.clone(), maybe_reborrowed)?;

    let refed = Canonical {
        value: TyKind::Ref(Mutability::Not, error_lifetime(), receiver_ty.value.clone())
            .intern(Interner),
        binders: receiver_ty.binders.clone(),
    };

    iterate_method_candidates_by_receiver(refed, first_adjustment.with_autoref(Mutability::Not))?;

    let ref_muted = Canonical {
        value: TyKind::Ref(Mutability::Mut, error_lifetime(), receiver_ty.value.clone())
            .intern(Interner),
        binders: receiver_ty.binders,
    };

    iterate_method_candidates_by_receiver(ref_muted, first_adjustment.with_autoref(Mutability::Mut))
}

#[tracing::instrument(skip_all, fields(name = ?name))]
fn iterate_method_candidates_by_receiver(
    table: &mut InferenceTable<'_>,
    receiver_ty: Canonical<Ty>,
    receiver_adjustments: ReceiverAdjustments,
    traits_in_scope: &FxHashSet<TraitId>,
    visible_from_module: VisibleFromModule,
    name: Option<&Name>,
    mut callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
) -> ControlFlow<()> {
    let receiver_ty = table.instantiate_canonical(receiver_ty);
    // We're looking for methods with *receiver* type receiver_ty. These could
    // be found in any of the derefs of receiver_ty, so we have to go through
    // that, including raw derefs.
    table.run_in_snapshot(|table| {
        let mut autoderef = autoderef::Autoderef::new_no_tracking(table, receiver_ty.clone(), true);
        while let Some((self_ty, _)) = autoderef.next() {
            iterate_inherent_methods(
                &self_ty,
                autoderef.table,
                name,
                Some(&receiver_ty),
                Some(receiver_adjustments.clone()),
                visible_from_module,
                &mut callback,
            )?
        }
        ControlFlow::Continue(())
    })?;
    table.run_in_snapshot(|table| {
        let mut autoderef = autoderef::Autoderef::new_no_tracking(table, receiver_ty.clone(), true);
        while let Some((self_ty, _)) = autoderef.next() {
            if matches!(self_ty.kind(Interner), TyKind::InferenceVar(_, TyVariableKind::General)) {
                // don't try to resolve methods on unknown types
                return ControlFlow::Continue(());
            }

            iterate_trait_method_candidates(
                &self_ty,
                autoderef.table,
                traits_in_scope,
                name,
                Some(&receiver_ty),
                Some(receiver_adjustments.clone()),
                &mut callback,
            )?
        }
        ControlFlow::Continue(())
    })
}

#[tracing::instrument(skip_all, fields(name = ?name))]
fn iterate_method_candidates_for_self_ty(
    self_ty: &Canonical<Ty>,
    db: &dyn HirDatabase,
    env: Arc<TraitEnvironment>,
    traits_in_scope: &FxHashSet<TraitId>,
    visible_from_module: VisibleFromModule,
    name: Option<&Name>,
    mut callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
) -> ControlFlow<()> {
    let mut table = InferenceTable::new(db, env);
    let self_ty = table.instantiate_canonical(self_ty.clone());
    iterate_inherent_methods(
        &self_ty,
        &mut table,
        name,
        None,
        None,
        visible_from_module,
        &mut callback,
    )?;
    iterate_trait_method_candidates(
        &self_ty,
        &mut table,
        traits_in_scope,
        name,
        None,
        None,
        callback,
    )
}

#[tracing::instrument(skip_all, fields(name = ?name, visible_from_module, receiver_ty))]
fn iterate_trait_method_candidates(
    self_ty: &Ty,
    table: &mut InferenceTable<'_>,
    traits_in_scope: &FxHashSet<TraitId>,
    name: Option<&Name>,
    receiver_ty: Option<&Ty>,
    receiver_adjustments: Option<ReceiverAdjustments>,
    callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
) -> ControlFlow<()> {
    let db = table.db;

    let canonical_self_ty = table.canonicalize(self_ty.clone());
    let TraitEnvironment { krate, block, .. } = *table.trait_env;

    'traits: for &t in traits_in_scope {
        let data = db.trait_data(t);

        // Traits annotated with `#[rustc_skip_during_method_dispatch]` are skipped during
        // method resolution, if the receiver is an array, and we're compiling for editions before
        // 2021.
        // This is to make `[a].into_iter()` not break code with the new `IntoIterator` impl for
        // arrays.
        if data.skip_array_during_method_dispatch
            && matches!(self_ty.kind(Interner), TyKind::Array(..))
        {
            // FIXME: this should really be using the edition of the method name's span, in case it
            // comes from a macro
            if !db.crate_graph()[krate].edition.at_least_2021() {
                continue;
            }
        }
        if data.skip_boxed_slice_during_method_dispatch
            && matches!(
                self_ty.kind(Interner), TyKind::Adt(AdtId(def), subst)
                if is_box(table.db, *def)
                    && matches!(subst.at(Interner, 0).assert_ty_ref(Interner).kind(Interner), TyKind::Slice(..))
            )
        {
            // FIXME: this should really be using the edition of the method name's span, in case it
            // comes from a macro
            if !db.crate_graph()[krate].edition.at_least_2024() {
                continue;
            }
        }

        // we'll be lazy about checking whether the type implements the
        // trait, but if we find out it doesn't, we'll skip the rest of the
        // iteration
        let mut known_implemented = false;
        for &(_, item) in data.items.iter() {
            // Don't pass a `visible_from_module` down to `is_valid_candidate`,
            // since only inherent methods should be included into visibility checking.
            let visible =
                match is_valid_trait_method_candidate(table, t, name, receiver_ty, item, self_ty) {
                    IsValidCandidate::Yes => true,
                    IsValidCandidate::NotVisible => false,
                    IsValidCandidate::No => continue,
                };
            if !known_implemented {
                let goal = generic_implements_goal(db, &table.trait_env, t, &canonical_self_ty);
                if db.trait_solve(krate, block, goal.cast(Interner)).is_none() {
                    continue 'traits;
                }
            }
            known_implemented = true;
            callback(receiver_adjustments.clone().unwrap_or_default(), item, visible)?;
        }
    }
    ControlFlow::Continue(())
}

#[tracing::instrument(skip_all, fields(name = ?name, visible_from_module, receiver_ty))]
fn iterate_inherent_methods(
    self_ty: &Ty,
    table: &mut InferenceTable<'_>,
    name: Option<&Name>,
    receiver_ty: Option<&Ty>,
    receiver_adjustments: Option<ReceiverAdjustments>,
    visible_from_module: VisibleFromModule,
    callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
) -> ControlFlow<()> {
    let db = table.db;
    let env = table.trait_env.clone();

    // For trait object types and placeholder types with trait bounds, the methods of the trait and
    // its super traits are considered inherent methods. This matters because these methods have
    // higher priority than the other traits' methods, which would be considered in
    // `iterate_trait_method_candidates()` only after this function.
    match self_ty.kind(Interner) {
        TyKind::Placeholder(_) => {
            let env = table.trait_env.clone();
            let traits = env
                .traits_in_scope_from_clauses(self_ty.clone())
                .flat_map(|t| all_super_traits(db.upcast(), t));
            iterate_inherent_trait_methods(
                self_ty,
                table,
                name,
                receiver_ty,
                receiver_adjustments.clone(),
                callback,
                traits,
            )?;
        }
        TyKind::Dyn(_) => {
            if let Some(principal_trait) = self_ty.dyn_trait() {
                let traits = all_super_traits(db.upcast(), principal_trait);
                iterate_inherent_trait_methods(
                    self_ty,
                    table,
                    name,
                    receiver_ty,
                    receiver_adjustments.clone(),
                    callback,
                    traits.into_iter(),
                )?;
            }
        }
        _ => {}
    }

    let def_crates = match def_crates(db, self_ty, env.krate) {
        Some(k) => k,
        None => return ControlFlow::Continue(()),
    };

    let (module, mut block) = match visible_from_module {
        VisibleFromModule::Filter(module) => (Some(module), module.containing_block()),
        VisibleFromModule::IncludeBlock(block) => (None, Some(block)),
        VisibleFromModule::None => (None, None),
    };

    while let Some(block_id) = block {
        if let Some(impls) = db.inherent_impls_in_block(block_id) {
            impls_for_self_ty(
                &impls,
                self_ty,
                table,
                name,
                receiver_ty,
                receiver_adjustments.clone(),
                module,
                callback,
            )?;
        }

        block = db.block_def_map(block_id).parent().and_then(|module| module.containing_block());
    }

    for krate in def_crates {
        let impls = db.inherent_impls_in_crate(krate);
        impls_for_self_ty(
            &impls,
            self_ty,
            table,
            name,
            receiver_ty,
            receiver_adjustments.clone(),
            module,
            callback,
        )?;
    }
    return ControlFlow::Continue(());

    #[tracing::instrument(skip_all, fields(name = ?name, visible_from_module, receiver_ty))]
    fn iterate_inherent_trait_methods(
        self_ty: &Ty,
        table: &mut InferenceTable<'_>,
        name: Option<&Name>,
        receiver_ty: Option<&Ty>,
        receiver_adjustments: Option<ReceiverAdjustments>,
        callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
        traits: impl Iterator<Item = TraitId>,
    ) -> ControlFlow<()> {
        let db = table.db;
        for t in traits {
            let data = db.trait_data(t);
            for &(_, item) in data.items.iter() {
                // We don't pass `visible_from_module` as all trait items should be visible.
                let visible = match is_valid_trait_method_candidate(
                    table,
                    t,
                    name,
                    receiver_ty,
                    item,
                    self_ty,
                ) {
                    IsValidCandidate::Yes => true,
                    IsValidCandidate::NotVisible => false,
                    IsValidCandidate::No => continue,
                };
                callback(receiver_adjustments.clone().unwrap_or_default(), item, visible)?;
            }
        }
        ControlFlow::Continue(())
    }

    #[tracing::instrument(skip_all, fields(name = ?name, visible_from_module, receiver_ty))]
    fn impls_for_self_ty(
        impls: &InherentImpls,
        self_ty: &Ty,
        table: &mut InferenceTable<'_>,
        name: Option<&Name>,
        receiver_ty: Option<&Ty>,
        receiver_adjustments: Option<ReceiverAdjustments>,
        visible_from_module: Option<ModuleId>,
        callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
    ) -> ControlFlow<()> {
        for &impl_id in impls.for_self_ty(self_ty) {
            for &item in table.db.impl_data(impl_id).items.iter() {
                let visible = match is_valid_impl_method_candidate(
                    table,
                    self_ty,
                    receiver_ty,
                    visible_from_module,
                    name,
                    impl_id,
                    item,
                ) {
                    IsValidCandidate::Yes => true,
                    IsValidCandidate::NotVisible => false,
                    IsValidCandidate::No => continue,
                };
                callback(receiver_adjustments.clone().unwrap_or_default(), item, visible)?;
            }
        }
        ControlFlow::Continue(())
    }
}

/// Returns the receiver type for the index trait call.
pub(crate) fn resolve_indexing_op(
    db: &dyn HirDatabase,
    env: Arc<TraitEnvironment>,
    ty: Canonical<Ty>,
    index_trait: TraitId,
) -> Option<ReceiverAdjustments> {
    let mut table = InferenceTable::new(db, env);
    let ty = table.instantiate_canonical(ty);
    let deref_chain = autoderef_method_receiver(&mut table, ty);
    for (ty, adj) in deref_chain {
        let goal = generic_implements_goal(db, &table.trait_env, index_trait, &ty);
        if db
            .trait_solve(table.trait_env.krate, table.trait_env.block, goal.cast(Interner))
            .is_some()
        {
            return Some(adj);
        }
    }
    None
}

// FIXME: Replace this with a `Try` impl once stable
macro_rules! check_that {
    ($cond:expr) => {
        if !$cond {
            return IsValidCandidate::No;
        }
    };
}

#[derive(Debug)]
enum IsValidCandidate {
    Yes,
    No,
    NotVisible,
}

#[tracing::instrument(skip_all, fields(name))]
fn is_valid_impl_method_candidate(
    table: &mut InferenceTable<'_>,
    self_ty: &Ty,
    receiver_ty: Option<&Ty>,
    visible_from_module: Option<ModuleId>,
    name: Option<&Name>,
    impl_id: ImplId,
    item: AssocItemId,
) -> IsValidCandidate {
    match item {
        AssocItemId::FunctionId(f) => is_valid_impl_fn_candidate(
            table,
            impl_id,
            f,
            name,
            receiver_ty,
            self_ty,
            visible_from_module,
        ),
        AssocItemId::ConstId(c) => {
            let db = table.db;
            check_that!(receiver_ty.is_none());
            check_that!(name.map_or(true, |n| db.const_data(c).name.as_ref() == Some(n)));

            if let Some(from_module) = visible_from_module {
                if !db.const_visibility(c).is_visible_from(db.upcast(), from_module) {
                    cov_mark::hit!(const_candidate_not_visible);
                    return IsValidCandidate::NotVisible;
                }
            }
            let self_ty_matches = table.run_in_snapshot(|table| {
                let expected_self_ty =
                    TyBuilder::impl_self_ty(db, impl_id).fill_with_inference_vars(table).build();
                table.unify(&expected_self_ty, self_ty)
            });
            if !self_ty_matches {
                cov_mark::hit!(const_candidate_self_type_mismatch);
                return IsValidCandidate::No;
            }
            IsValidCandidate::Yes
        }
        _ => IsValidCandidate::No,
    }
}

/// Checks whether a given `AssocItemId` is applicable for `receiver_ty`.
#[tracing::instrument(skip_all, fields(name))]
fn is_valid_trait_method_candidate(
    table: &mut InferenceTable<'_>,
    trait_id: TraitId,
    name: Option<&Name>,
    receiver_ty: Option<&Ty>,
    item: AssocItemId,
    self_ty: &Ty,
) -> IsValidCandidate {
    let db = table.db;
    match item {
        AssocItemId::FunctionId(fn_id) => {
            let data = db.function_data(fn_id);

            check_that!(name.map_or(true, |n| n == &data.name));

            table.run_in_snapshot(|table| {
                let impl_subst = TyBuilder::subst_for_def(db, trait_id, None)
                    .fill_with_inference_vars(table)
                    .build();
                let expect_self_ty = impl_subst.at(Interner, 0).assert_ty_ref(Interner).clone();

                check_that!(table.unify(&expect_self_ty, self_ty));

                if let Some(receiver_ty) = receiver_ty {
                    check_that!(data.has_self_param());

                    let fn_subst = TyBuilder::subst_for_def(db, fn_id, Some(impl_subst))
                        .fill_with_inference_vars(table)
                        .build();

                    let sig = db.callable_item_signature(fn_id.into());
                    let expected_receiver =
                        sig.map(|s| s.params()[0].clone()).substitute(Interner, &fn_subst);

                    check_that!(table.unify(receiver_ty, &expected_receiver));
                }

                IsValidCandidate::Yes
            })
        }
        AssocItemId::ConstId(c) => {
            check_that!(receiver_ty.is_none());
            check_that!(name.map_or(true, |n| db.const_data(c).name.as_ref() == Some(n)));

            IsValidCandidate::Yes
        }
        _ => IsValidCandidate::No,
    }
}

#[tracing::instrument(skip_all, fields(name))]
fn is_valid_impl_fn_candidate(
    table: &mut InferenceTable<'_>,
    impl_id: ImplId,
    fn_id: FunctionId,
    name: Option<&Name>,
    receiver_ty: Option<&Ty>,
    self_ty: &Ty,
    visible_from_module: Option<ModuleId>,
) -> IsValidCandidate {
    let db = table.db;
    let data = db.function_data(fn_id);

    check_that!(name.map_or(true, |n| n == &data.name));
    if let Some(from_module) = visible_from_module {
        if !db.function_visibility(fn_id).is_visible_from(db.upcast(), from_module) {
            cov_mark::hit!(autoderef_candidate_not_visible);
            return IsValidCandidate::NotVisible;
        }
    }
    table.run_in_snapshot(|table| {
        let _p = tracing::info_span!("subst_for_def").entered();
        let impl_subst =
            TyBuilder::subst_for_def(db, impl_id, None).fill_with_inference_vars(table).build();
        let expect_self_ty = db.impl_self_ty(impl_id).substitute(Interner, &impl_subst);

        check_that!(table.unify(&expect_self_ty, self_ty));

        if let Some(receiver_ty) = receiver_ty {
            let _p = tracing::info_span!("check_receiver_ty").entered();
            check_that!(data.has_self_param());

            let fn_subst = TyBuilder::subst_for_def(db, fn_id, Some(impl_subst.clone()))
                .fill_with_inference_vars(table)
                .build();

            let sig = db.callable_item_signature(fn_id.into());
            let expected_receiver =
                sig.map(|s| s.params()[0].clone()).substitute(Interner, &fn_subst);

            check_that!(table.unify(receiver_ty, &expected_receiver));
        }

        // We need to consider the bounds on the impl to distinguish functions of the same name
        // for a type.
        let predicates = db.generic_predicates(impl_id.into());
        let goals = predicates.iter().map(|p| {
            let (p, b) = p
                .clone()
                .substitute(Interner, &impl_subst)
                // Skipping the inner binders is ok, as we don't handle quantified where
                // clauses yet.
                .into_value_and_skipped_binders();
            stdx::always!(b.len(Interner) == 0);

            p.cast::<Goal>(Interner)
        });

        for goal in goals.clone() {
            let in_env = InEnvironment::new(&table.trait_env.env, goal);
            let canonicalized = table.canonicalize_with_free_vars(in_env);
            let solution = table.db.trait_solve(
                table.trait_env.krate,
                table.trait_env.block,
                canonicalized.value.clone(),
            );

            match solution {
                Some(Solution::Unique(canonical_subst)) => {
                    canonicalized.apply_solution(
                        table,
                        Canonical {
                            binders: canonical_subst.binders,
                            value: canonical_subst.value.subst,
                        },
                    );
                }
                Some(Solution::Ambig(Guidance::Definite(substs))) => {
                    canonicalized.apply_solution(table, substs);
                }
                Some(_) => (),
                None => return IsValidCandidate::No,
            }
        }

        for goal in goals {
            if table.try_obligation(goal).is_none() {
                return IsValidCandidate::No;
            }
        }

        IsValidCandidate::Yes
    })
}

pub fn implements_trait(
    ty: &Canonical<Ty>,
    db: &dyn HirDatabase,
    env: &TraitEnvironment,
    trait_: TraitId,
) -> bool {
    let goal = generic_implements_goal(db, env, trait_, ty);
    let solution = db.trait_solve(env.krate, env.block, goal.cast(Interner));

    solution.is_some()
}

pub fn implements_trait_unique(
    ty: &Canonical<Ty>,
    db: &dyn HirDatabase,
    env: &TraitEnvironment,
    trait_: TraitId,
) -> bool {
    let goal = generic_implements_goal(db, env, trait_, ty);
    let solution = db.trait_solve(env.krate, env.block, goal.cast(Interner));

    matches!(solution, Some(crate::Solution::Unique(_)))
}

/// This creates Substs for a trait with the given Self type and type variables
/// for all other parameters, to query Chalk with it.
#[tracing::instrument(skip_all)]
fn generic_implements_goal(
    db: &dyn HirDatabase,
    env: &TraitEnvironment,
    trait_: TraitId,
    self_ty: &Canonical<Ty>,
) -> Canonical<InEnvironment<super::DomainGoal>> {
    let binders = self_ty.binders.interned();
    let trait_ref = TyBuilder::trait_ref(db, trait_)
        .push(self_ty.value.clone())
        .fill_with_bound_vars(DebruijnIndex::INNERMOST, binders.len())
        .build();

    let kinds =
        binders.iter().cloned().chain(trait_ref.substitution.iter(Interner).skip(1).map(|it| {
            let vk = match it.data(Interner) {
                GenericArgData::Ty(_) => VariableKind::Ty(chalk_ir::TyVariableKind::General),
                GenericArgData::Lifetime(_) => VariableKind::Lifetime,
                GenericArgData::Const(c) => VariableKind::Const(c.data(Interner).ty.clone()),
            };
            WithKind::new(vk, UniverseIndex::ROOT)
        }));
    let binders = CanonicalVarKinds::from_iter(Interner, kinds);

    let obligation = trait_ref.cast(Interner);
    let value = InEnvironment::new(&env.env, obligation);
    Canonical { binders, value }
}

fn autoderef_method_receiver(
    table: &mut InferenceTable<'_>,
    ty: Ty,
) -> Vec<(Canonical<Ty>, ReceiverAdjustments)> {
    let mut deref_chain: Vec<_> = Vec::new();
    let mut autoderef = autoderef::Autoderef::new_no_tracking(table, ty, false);
    while let Some((ty, derefs)) = autoderef.next() {
        deref_chain.push((
            autoderef.table.canonicalize(ty),
            ReceiverAdjustments { autoref: None, autoderefs: derefs, unsize_array: false },
        ));
    }
    // As a last step, we can do array unsizing (that's the only unsizing that rustc does for method receivers!)
    if let Some((TyKind::Array(parameters, _), binders, adj)) =
        deref_chain.last().map(|(ty, adj)| (ty.value.kind(Interner), ty.binders.clone(), adj))
    {
        let unsized_ty = TyKind::Slice(parameters.clone()).intern(Interner);
        deref_chain.push((
            Canonical { value: unsized_ty, binders },
            ReceiverAdjustments { unsize_array: true, ..adj.clone() },
        ));
    }
    deref_chain
}