bendns' repos / rust-analyzer
Unnamed repository; edit this file 'description' to name the repository.
Diffstat (limited to 'crates/hir-ty/src/method_resolution.rs')
-rw-r--r--crates/hir-ty/src/method_resolution.rs2429
1 files changed, 648 insertions, 1781 deletions
diff --git a/crates/hir-ty/src/method_resolution.rs b/crates/hir-ty/src/method_resolution.rs
index 7fa3d31fe5..9a6adedb99 100644
--- a/crates/hir-ty/src/method_resolution.rs
+++ b/crates/hir-ty/src/method_resolution.rs
@@ -2,755 +2,366 @@
//! 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 arrayvec::ArrayVec;
+mod confirm;
+mod probe;
+
+use either::Either;
+use hir_expand::name::Name;
+use span::Edition;
+use tracing::{debug, instrument};
+
use base_db::Crate;
-use chalk_ir::{UniverseIndex, WithKind, cast::Cast};
use hir_def::{
- AssocItemId, BlockId, ConstId, FunctionId, HasModule, ImplId, ItemContainerId, Lookup,
+ AssocItemId, BlockId, ConstId, FunctionId, GenericParamId, HasModule, ImplId, ItemContainerId,
ModuleId, TraitId,
- nameres::{DefMap, assoc::ImplItems, block_def_map, crate_def_map},
- signatures::{ConstFlags, EnumFlags, FnFlags, StructFlags, TraitFlags, TypeAliasFlags},
+ attrs::AttrFlags,
+ expr_store::path::GenericArgs as HirGenericArgs,
+ hir::ExprId,
+ nameres::{DefMap, block_def_map, crate_def_map},
+ resolver::Resolver,
};
-use hir_expand::name::Name;
-use intern::sym;
+use intern::{Symbol, sym};
use rustc_hash::{FxHashMap, FxHashSet};
-use rustc_type_ir::inherent::{IntoKind, SliceLike, Ty as _};
-use smallvec::{SmallVec, smallvec};
-use stdx::never;
+use rustc_type_ir::{
+ TypeVisitableExt,
+ fast_reject::{TreatParams, simplify_type},
+ inherent::{BoundExistentialPredicates, IntoKind, SliceLike},
+};
+use stdx::impl_from;
use triomphe::Arc;
use crate::{
- AdtId, Canonical, CanonicalVarKinds, DebruijnIndex, DynTyExt, ForeignDefId, GenericArgData,
- Goal, InEnvironment, Interner, Mutability, Scalar, Substitution, TraitEnvironment, TraitRef,
- TraitRefExt, Ty, TyBuilder, TyExt, TyKind, VariableKind, WhereClause,
- autoderef::{self, AutoderefKind},
+ TraitEnvironment, all_super_traits,
db::HirDatabase,
- from_chalk_trait_id, from_foreign_def_id,
- infer::{Adjust, Adjustment, OverloadedDeref, PointerCast, unify::InferenceTable},
- lang_items::is_box,
+ infer::{InferenceContext, unify::InferenceTable},
+ lower::GenericPredicates,
next_solver::{
- self, SolverDefId,
- fulfill::FulfillmentCtxt,
- infer::DefineOpaqueTypes,
- mapping::{ChalkToNextSolver, NextSolverToChalk},
+ Binder, ClauseKind, DbInterner, FnSig, GenericArgs, PredicateKind, SimplifiedType,
+ SolverDefId, TraitRef, Ty, TyKind, TypingMode,
+ infer::{
+ BoundRegionConversionTime, DbInternerInferExt, InferCtxt, InferOk,
+ select::ImplSource,
+ traits::{Obligation, ObligationCause, PredicateObligations},
+ },
+ obligation_ctxt::ObligationCtxt,
+ util::clauses_as_obligations,
},
- primitive::{FloatTy, IntTy, UintTy},
- to_chalk_trait_id,
- traits::next_trait_solve_canonical_in_ctxt,
- utils::all_super_traits,
};
-/// 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,
- Ref(Mutability),
- 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(mutability, _, _) => TyFingerprint::Ref(*mutability),
- 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(_, _)
- // FIXME(next-solver): Putting `Alias` here is *probably* incorrect, AFAIK it should return `None`. But this breaks
- // flyimport, which uses an incorrect but fast method resolution algorithm. Therefore we put it here,
- // because this function is only called by flyimport, and anyway we should get rid of `TyFingerprint`
- // and switch to `rustc_type_ir`'s `SimplifiedType`.
- | TyKind::Alias(_)
- | 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::Placeholder(_)
- | TyKind::BoundVar(_)
- | TyKind::InferenceVar(_, _)
- | TyKind::Error => return None,
- };
- Some(fp)
- }
-
- /// Creates a TyFingerprint for looking up a trait impl.
- pub fn for_trait_impl_ns<'db>(ty: &next_solver::Ty<'db>) -> Option<TyFingerprint> {
- use rustc_type_ir::TyKind;
- let fp = match (*ty).kind() {
- TyKind::Str => TyFingerprint::Str,
- TyKind::Never => TyFingerprint::Never,
- TyKind::Slice(..) => TyFingerprint::Slice,
- TyKind::Array(..) => TyFingerprint::Array,
- TyKind::Int(int) => TyFingerprint::Scalar(Scalar::Int(match int {
- rustc_type_ir::IntTy::Isize => IntTy::Isize,
- rustc_type_ir::IntTy::I8 => IntTy::I8,
- rustc_type_ir::IntTy::I16 => IntTy::I16,
- rustc_type_ir::IntTy::I32 => IntTy::I32,
- rustc_type_ir::IntTy::I64 => IntTy::I64,
- rustc_type_ir::IntTy::I128 => IntTy::I128,
- })),
- TyKind::Uint(uint) => TyFingerprint::Scalar(Scalar::Uint(match uint {
- rustc_type_ir::UintTy::Usize => UintTy::Usize,
- rustc_type_ir::UintTy::U8 => UintTy::U8,
- rustc_type_ir::UintTy::U16 => UintTy::U16,
- rustc_type_ir::UintTy::U32 => UintTy::U32,
- rustc_type_ir::UintTy::U64 => UintTy::U64,
- rustc_type_ir::UintTy::U128 => UintTy::U128,
- })),
- TyKind::Float(float) => TyFingerprint::Scalar(Scalar::Float(match float {
- rustc_type_ir::FloatTy::F16 => FloatTy::F16,
- rustc_type_ir::FloatTy::F32 => FloatTy::F32,
- rustc_type_ir::FloatTy::F64 => FloatTy::F64,
- rustc_type_ir::FloatTy::F128 => FloatTy::F128,
- })),
- TyKind::Bool => TyFingerprint::Scalar(Scalar::Bool),
- TyKind::Char => TyFingerprint::Scalar(Scalar::Char),
- TyKind::Adt(def, _) => TyFingerprint::Adt(def.inner().id),
- TyKind::RawPtr(.., mutability) => match mutability {
- rustc_ast_ir::Mutability::Mut => TyFingerprint::RawPtr(Mutability::Mut),
- rustc_ast_ir::Mutability::Not => TyFingerprint::RawPtr(Mutability::Not),
- },
- TyKind::Foreign(def) => TyFingerprint::ForeignType(crate::to_foreign_def_id(def.0)),
- TyKind::Dynamic(bounds, _) => {
- let trait_ref = bounds
- .as_slice()
- .iter()
- .map(|b| (*b).skip_binder())
- .filter_map(|b| match b {
- rustc_type_ir::ExistentialPredicate::Trait(t) => Some(t.def_id),
- _ => None,
- })
- .next()?;
- TyFingerprint::Dyn(trait_ref.0)
- }
- TyKind::Ref(_, _, mutability) => match mutability {
- rustc_ast_ir::Mutability::Mut => TyFingerprint::Ref(Mutability::Mut),
- rustc_ast_ir::Mutability::Not => TyFingerprint::Ref(Mutability::Not),
- },
- TyKind::Tuple(tys) => {
- let first_ty = tys.as_slice().iter().next();
- match first_ty {
- Some(ty) => return TyFingerprint::for_trait_impl_ns(ty),
- None => TyFingerprint::Unit,
- }
- }
- TyKind::FnDef(_, _)
- | TyKind::Closure(_, _)
- | TyKind::Coroutine(..)
- | TyKind::CoroutineWitness(..)
- | TyKind::Pat(..)
- | TyKind::CoroutineClosure(..) => TyFingerprint::Unnameable,
- TyKind::FnPtr(sig, _) => {
- TyFingerprint::Function(sig.inputs().skip_binder().len() as u32)
- }
- TyKind::Alias(..)
- | TyKind::Placeholder(_)
- | TyKind::Bound(..)
- | TyKind::Infer(_)
- | TyKind::Error(_)
- | TyKind::Param(..)
- | TyKind::UnsafeBinder(..) => return None,
- };
- Some(fp)
- }
-}
+pub use self::probe::{
+ Candidate, CandidateKind, CandidateStep, CandidateWithPrivate, Mode, Pick, PickKind,
+};
-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,
+#[derive(Debug, Clone)]
+pub struct MethodResolutionUnstableFeatures {
+ arbitrary_self_types: bool,
+ arbitrary_self_types_pointers: bool,
+ supertrait_item_shadowing: bool,
}
-impl TraitImpls {
- pub(crate) fn trait_impls_in_crate_query(db: &dyn HirDatabase, krate: Crate) -> 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, crate_def_map(db, 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, block_def_map(db, 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: Crate,
- ) -> Arc<[Arc<Self>]> {
- let _p = tracing::info_span!("trait_impls_in_deps_query", ?krate).entered();
- Arc::from_iter(
- db.transitive_deps(krate).into_iter().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(),
+impl MethodResolutionUnstableFeatures {
+ pub fn from_def_map(def_map: &DefMap) -> Self {
+ Self {
+ arbitrary_self_types: def_map.is_unstable_feature_enabled(&sym::arbitrary_self_types),
+ arbitrary_self_types_pointers: def_map
+ .is_unstable_feature_enabled(&sym::arbitrary_self_types_pointers),
+ supertrait_item_shadowing: def_map
+ .is_unstable_feature_enabled(&sym::supertrait_item_shadowing),
}
}
-
- 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) {
- 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>,
+pub struct MethodResolutionContext<'a, 'db> {
+ pub infcx: &'a InferCtxt<'db>,
+ pub resolver: &'a Resolver<'db>,
+ pub env: &'a TraitEnvironment<'db>,
+ pub traits_in_scope: &'a FxHashSet<TraitId>,
+ pub edition: Edition,
+ pub unstable_features: &'a MethodResolutionUnstableFeatures,
}
-impl InherentImpls {
- pub(crate) fn inherent_impls_in_crate_query(db: &dyn HirDatabase, krate: Crate) -> 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 = crate_def_map(db, 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 = block_def_map(db, block);
- impls.collect_def_map(db, block_def_map);
- impls.shrink_to_fit();
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, salsa::Update)]
+pub enum CandidateId {
+ FunctionId(FunctionId),
+ ConstId(ConstId),
+}
+impl_from!(FunctionId, ConstId for CandidateId);
- if impls.map.is_empty() && impls.invalid_impls.is_empty() {
- None
- } else {
- Some(Arc::new(impls))
+impl CandidateId {
+ fn container(self, db: &dyn HirDatabase) -> ItemContainerId {
+ match self {
+ CandidateId::FunctionId(id) => id.loc(db).container,
+ CandidateId::ConstId(id) => id.loc(db).container,
}
}
+}
- fn shrink_to_fit(&mut self) {
- self.map.values_mut().for_each(Vec::shrink_to_fit);
- self.map.shrink_to_fit();
- }
+#[derive(Clone, Copy, Debug)]
+pub(crate) struct MethodCallee<'db> {
+ /// Impl method ID, for inherent methods, or trait method ID, otherwise.
+ pub def_id: FunctionId,
+ pub args: GenericArgs<'db>,
- 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_signature(impl_id);
- if data.target_trait.is_some() {
- continue;
- }
+ /// Instantiated method signature, i.e., it has been
+ /// instantiated, normalized, and has had late-bound
+ /// lifetimes replaced with inference variables.
+ pub sig: FnSig<'db>,
+}
- let self_ty = db.impl_self_ty(impl_id);
- let self_ty = self_ty.skip_binders();
+#[derive(Debug)]
+pub enum MethodError<'db> {
+ /// Did not find an applicable method.
+ NoMatch,
- match is_inherent_impl_coherent(db, def_map, impl_id, 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),
- }
- }
+ /// Multiple methods might apply.
+ Ambiguity(Vec<CandidateSource>),
- // 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) {
- self.collect_def_map(db, block_def_map);
- }
- }
- }
- }
+ /// Found an applicable method, but it is not visible.
+ PrivateMatch(Pick<'db>),
- 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 => &[],
- }
- }
+ /// Found a `Self: Sized` bound where `Self` is a trait object.
+ IllegalSizedBound { candidates: Vec<FunctionId>, needs_mut: bool },
- pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ {
- self.map.values().flat_map(|v| v.iter().copied())
- }
+ /// Error has already been emitted, no need to emit another one.
+ ErrorReported,
+}
- pub fn invalid_impls(&self) -> &[ImplId] {
- &self.invalid_impls
- }
+// A pared down enum describing just the places from which a method
+// candidate can arise. Used for error reporting only.
+#[derive(Copy, Clone, Debug, Eq, PartialEq)]
+pub enum CandidateSource {
+ Impl(ImplId),
+ Trait(TraitId),
}
-pub(crate) fn incoherent_inherent_impl_crates(
- db: &dyn HirDatabase,
- krate: Crate,
- fp: TyFingerprint,
-) -> SmallVec<[Crate; 2]> {
- let _p = tracing::info_span!("incoherent_inherent_impl_crates").entered();
- let mut res = SmallVec::new();
+impl<'a, 'db> InferenceContext<'a, 'db> {
+ /// Performs method lookup. If lookup is successful, it will return the callee
+ /// and store an appropriate adjustment for the self-expr. In some cases it may
+ /// report an error (e.g., invoking the `drop` method).
+ #[instrument(level = "debug", skip(self))]
+ pub(crate) fn lookup_method_including_private(
+ &mut self,
+ self_ty: Ty<'db>,
+ name: Name,
+ generic_args: Option<&HirGenericArgs>,
+ receiver: ExprId,
+ call_expr: ExprId,
+ ) -> Result<(MethodCallee<'db>, bool), MethodError<'db>> {
+ let (pick, is_visible) = match self.lookup_probe(name, self_ty) {
+ Ok(it) => (it, true),
+ Err(MethodError::PrivateMatch(it)) => {
+ // FIXME: Report error.
+ (it, false)
+ }
+ Err(err) => return Err(err),
+ };
- // should pass crate for finger print and do reverse deps
+ let result = self.confirm_method(&pick, self_ty, call_expr, generic_args);
+ debug!("result = {:?}", result);
- for krate in db.transitive_deps(krate) {
- let impls = db.inherent_impls_in_crate(krate);
- if impls.map.get(&fp).is_some_and(|v| !v.is_empty()) {
- res.push(krate);
+ if result.illegal_sized_bound {
+ // FIXME: Report an error.
}
- }
- res
-}
+ self.write_expr_adj(receiver, result.adjustments);
+ self.write_method_resolution(call_expr, result.callee.def_id, result.callee.args);
-pub fn def_crates(db: &dyn HirDatabase, ty: &Ty, cur_crate: Crate) -> Option<SmallVec<[Crate; 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_signature(id)
- .flags
- .contains(StructFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS),
- hir_def::AdtId::UnionId(id) => db
- .union_signature(id)
- .flags
- .contains(StructFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS),
- hir_def::AdtId::EnumId(id) => db
- .enum_signature(id)
- .flags
- .contains(EnumFlags::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).krate()]
- })
- }
- &TyKind::Foreign(id) => {
- let alias = from_foreign_def_id(id);
- Some(
- if db
- .type_alias_signature(alias)
- .flags
- .contains(TypeAliasFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPL)
- {
- db.incoherent_inherent_impl_crates(cur_crate, TyFingerprint::ForeignType(id))
- } else {
- smallvec![alias.module(db).krate()]
- },
- )
- }
- TyKind::Dyn(_) => {
- let trait_id = ty.dyn_trait()?;
- Some(
- if db
- .trait_signature(trait_id)
- .flags
- .contains(TraitFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS)
- {
- db.incoherent_inherent_impl_crates(cur_crate, TyFingerprint::Dyn(trait_id))
- } else {
- smallvec![trait_id.module(db).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,
+ Ok((result.callee, is_visible))
}
-}
-
-/// Look up the method with the given name.
-pub(crate) fn lookup_method<'db>(
- db: &'db dyn HirDatabase,
- ty: &next_solver::Canonical<'db, crate::next_solver::Ty<'db>>,
- 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,
- }
+ #[instrument(level = "debug", skip(self))]
+ pub(crate) fn lookup_probe(
+ &self,
+ method_name: Name,
+ self_ty: Ty<'db>,
+ ) -> probe::PickResult<'db> {
+ self.with_method_resolution(|ctx| {
+ let pick = ctx.probe_for_name(probe::Mode::MethodCall, method_name, self_ty)?;
+ Ok(pick)
+ })
}
-}
-impl From<Option<BlockId>> for VisibleFromModule {
- fn from(block: Option<BlockId>) -> Self {
- match block {
- Some(block) => Self::IncludeBlock(block),
- None => Self::None,
- }
+ pub(crate) fn with_method_resolution<R>(
+ &self,
+ f: impl FnOnce(&MethodResolutionContext<'_, 'db>) -> R,
+ ) -> R {
+ let traits_in_scope = self.get_traits_in_scope();
+ let traits_in_scope = match &traits_in_scope {
+ Either::Left(it) => it,
+ Either::Right(it) => *it,
+ };
+ let ctx = MethodResolutionContext {
+ infcx: &self.table.infer_ctxt,
+ resolver: &self.resolver,
+ env: &self.table.trait_env,
+ traits_in_scope,
+ edition: self.edition,
+ unstable_features: &self.unstable_features,
+ };
+ f(&ctx)
}
}
-#[derive(Debug, Clone)]
-pub enum AutorefOrPtrAdjustment {
- Autoref(Mutability),
- ToConstPtr,
-}
-
-#[derive(Debug, Clone, Default)]
-pub struct ReceiverAdjustments {
- autoref: Option<AutorefOrPtrAdjustment>,
- autoderefs: usize,
- unsize_array: bool,
-}
-
-impl ReceiverAdjustments {
- pub(crate) fn apply(
+/// Used by [FnCtxt::lookup_method_for_operator] with `-Znext-solver`.
+///
+/// With `AsRigid` we error on `impl Opaque: NotInItemBounds` while
+/// `AsInfer` just treats it as ambiguous and succeeds. This is necessary
+/// as we want [FnCtxt::check_expr_call] to treat not-yet-defined opaque
+/// types as rigid to support `impl Deref<Target = impl FnOnce()>` and
+/// `Box<impl FnOnce()>`.
+///
+/// We only want to treat opaque types as rigid if we need to eagerly choose
+/// between multiple candidates. We otherwise treat them as ordinary inference
+/// variable to avoid rejecting otherwise correct code.
+#[derive(Debug)]
+#[expect(dead_code)]
+pub(super) enum TreatNotYetDefinedOpaques {
+ AsInfer,
+ AsRigid,
+}
+
+impl<'db> InferenceTable<'db> {
+ /// `lookup_method_in_trait` is used for overloaded operators.
+ /// It does a very narrow slice of what the normal probe/confirm path does.
+ /// In particular, it doesn't really do any probing: it simply constructs
+ /// an obligation for a particular trait with the given self type and checks
+ /// whether that trait is implemented.
+ #[instrument(level = "debug", skip(self))]
+ pub(super) fn lookup_method_for_operator(
&self,
- table: &mut InferenceTable<'_>,
- mut ty: Ty,
- ) -> (Ty, Vec<Adjustment>) {
- let mut adjust = Vec::new();
- let mut autoderef = table.autoderef(ty.to_nextsolver(table.interner));
- autoderef.next();
- for _ in 0..self.autoderefs {
- match autoderef.next() {
- None => {
- never!("autoderef not possible for {:?}", ty);
- ty = TyKind::Error.intern(Interner);
- break;
- }
- Some((new_ty, _)) => {
- ty = new_ty.to_chalk(autoderef.table.interner);
- let mutbl = match self.autoref {
- Some(AutorefOrPtrAdjustment::Autoref(m)) => Some(m),
- Some(AutorefOrPtrAdjustment::ToConstPtr) => Some(Mutability::Not),
- // FIXME should we know the mutability here, when autoref is `None`?
- None => None,
- };
- adjust.push(Adjustment {
- kind: Adjust::Deref(match autoderef.steps().last().unwrap().1 {
- AutoderefKind::Overloaded => Some(OverloadedDeref(mutbl)),
- AutoderefKind::Builtin => None,
- }),
- target: ty.clone(),
- });
+ cause: ObligationCause,
+ method_name: Symbol,
+ trait_def_id: TraitId,
+ self_ty: Ty<'db>,
+ opt_rhs_ty: Option<Ty<'db>>,
+ treat_opaques: TreatNotYetDefinedOpaques,
+ ) -> Option<InferOk<'db, MethodCallee<'db>>> {
+ // Construct a trait-reference `self_ty : Trait<input_tys>`
+ let args = GenericArgs::for_item(
+ self.interner(),
+ trait_def_id.into(),
+ |param_idx, param_id, _| match param_id {
+ GenericParamId::LifetimeParamId(_) | GenericParamId::ConstParamId(_) => {
+ unreachable!("did not expect operator trait to have lifetime/const")
}
- }
- }
- if let Some(autoref) = &self.autoref {
- let lt = table.new_lifetime_var();
- match autoref {
- AutorefOrPtrAdjustment::Autoref(m) => {
- let a = Adjustment::borrow(*m, ty, lt);
- ty = a.target.clone();
- adjust.push(a);
- }
- AutorefOrPtrAdjustment::ToConstPtr => {
- if let TyKind::Raw(Mutability::Mut, pointee) = ty.kind(Interner) {
- let a = Adjustment {
- kind: Adjust::Pointer(PointerCast::MutToConstPointer),
- target: TyKind::Raw(Mutability::Not, pointee.clone()).intern(Interner),
- };
- ty = a.target.clone();
- adjust.push(a);
+ GenericParamId::TypeParamId(_) => {
+ if param_idx == 0 {
+ self_ty.into()
+ } else if let Some(rhs_ty) = opt_rhs_ty {
+ assert_eq!(param_idx, 1, "did not expect >1 param on operator trait");
+ rhs_ty.into()
} else {
- never!("`ToConstPtr` target is not a raw mutable pointer");
+ // FIXME: We should stop passing `None` for the failure case
+ // when probing for call exprs. I.e. `opt_rhs_ty` should always
+ // be set when it needs to be.
+ self.next_var_for_param(param_id)
}
}
- };
- }
- if self.unsize_array {
- ty = 'it: {
- if let TyKind::Ref(m, l, inner) = ty.kind(Interner)
- && 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, a: AutorefOrPtrAdjustment) -> ReceiverAdjustments {
- Self { autoref: Some(a), ..*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<'db, T>(
- ty: &next_solver::Canonical<'db, crate::next_solver::Ty<'db>>,
- db: &'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(());
+ },
+ );
+
+ let obligation = Obligation::new(
+ self.interner(),
+ cause,
+ self.trait_env.env,
+ TraitRef::new_from_args(self.interner(), trait_def_id.into(), args),
+ );
+
+ // Now we want to know if this can be matched
+ let matches_trait = match treat_opaques {
+ TreatNotYetDefinedOpaques::AsInfer => self.infer_ctxt.predicate_may_hold(&obligation),
+ TreatNotYetDefinedOpaques::AsRigid => {
+ self.infer_ctxt.predicate_may_hold_opaque_types_jank(&obligation)
}
- ControlFlow::Continue(())
- },
- );
- slot
-}
+ };
+
+ if !matches_trait {
+ debug!("--> Cannot match obligation");
+ // Cannot be matched, no such method resolution is possible.
+ return None;
+ }
+
+ // Trait must have a method named `m_name` and it should not have
+ // type parameters or early-bound regions.
+ let interner = self.interner();
+ // We use `Ident::with_dummy_span` since no built-in operator methods have
+ // any macro-specific hygiene, so the span's context doesn't really matter.
+ let Some(method_item) =
+ trait_def_id.trait_items(self.db).method_by_name(&Name::new_symbol_root(method_name))
+ else {
+ panic!("expected associated item for operator trait")
+ };
-pub fn lookup_impl_const(
- db: &dyn HirDatabase,
- env: Arc<TraitEnvironment>,
+ let def_id = method_item;
+
+ debug!("lookup_in_trait_adjusted: method_item={:?}", method_item);
+ let mut obligations = PredicateObligations::new();
+
+ // Instantiate late-bound regions and instantiate the trait
+ // parameters into the method type to get the actual method type.
+ //
+ // N.B., instantiate late-bound regions before normalizing the
+ // function signature so that normalization does not need to deal
+ // with bound regions.
+ let fn_sig =
+ self.db.callable_item_signature(method_item.into()).instantiate(interner, args);
+ let fn_sig = self
+ .infer_ctxt
+ .instantiate_binder_with_fresh_vars(BoundRegionConversionTime::FnCall, fn_sig);
+
+ // Register obligations for the parameters. This will include the
+ // `Self` parameter, which in turn has a bound of the main trait,
+ // so this also effectively registers `obligation` as well. (We
+ // used to register `obligation` explicitly, but that resulted in
+ // double error messages being reported.)
+ //
+ // Note that as the method comes from a trait, it should not have
+ // any late-bound regions appearing in its bounds.
+ let bounds = GenericPredicates::query_all(self.db, method_item.into());
+ let bounds = clauses_as_obligations(
+ bounds.iter_instantiated_copied(interner, args.as_slice()),
+ ObligationCause::new(),
+ self.trait_env.env,
+ );
+
+ obligations.extend(bounds);
+
+ // Also add an obligation for the method type being well-formed.
+ debug!(
+ "lookup_method_in_trait: matched method fn_sig={:?} obligation={:?}",
+ fn_sig, obligation
+ );
+ for ty in fn_sig.inputs_and_output {
+ obligations.push(Obligation::new(
+ interner,
+ obligation.cause.clone(),
+ self.trait_env.env,
+ Binder::dummy(PredicateKind::Clause(ClauseKind::WellFormed(ty.into()))),
+ ));
+ }
+
+ let callee = MethodCallee { def_id, args, sig: fn_sig };
+ debug!("callee = {:?}", callee);
+
+ Some(InferOk { obligations, value: callee })
+ }
+}
+
+pub fn lookup_impl_const<'db>(
+ infcx: &InferCtxt<'db>,
+ env: Arc<TraitEnvironment<'db>>,
const_id: ConstId,
- subs: Substitution,
-) -> (ConstId, Substitution) {
- let trait_id = match const_id.lookup(db).container {
+ subs: GenericArgs<'db>,
+) -> (ConstId, GenericArgs<'db>) {
+ let interner = infcx.interner;
+ let db = interner.db;
+
+ let trait_id = match const_id.loc(db).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 trait_ref = TraitRef::new(interner, trait_id.into(), subs);
let const_signature = db.const_signature(const_id);
let name = match const_signature.name.as_ref() {
@@ -758,7 +369,7 @@ pub fn lookup_impl_const(
None => return (const_id, subs),
};
- lookup_impl_assoc_item_for_trait_ref(trait_ref, db, env, name)
+ lookup_impl_assoc_item_for_trait_ref(infcx, trait_ref, env, name)
.and_then(
|assoc| if let (AssocItemId::ConstId(id), s) = assoc { Some((id, s)) } else { None },
)
@@ -767,38 +378,31 @@ pub fn lookup_impl_const(
/// 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>,
+pub fn is_dyn_method<'db>(
+ interner: DbInterner<'db>,
+ _env: Arc<TraitEnvironment<'db>>,
func: FunctionId,
- fn_subst: Substitution,
+ fn_subst: GenericArgs<'db>,
) -> Option<usize> {
- let ItemContainerId::TraitId(trait_id) = func.lookup(db).container else {
+ let db = interner.db;
+
+ let ItemContainerId::TraitId(trait_id) = func.loc(db).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).take(trait_params)),
- };
- let self_ty = trait_ref.self_type_parameter(Interner);
- if let TyKind::Dyn(d) = self_ty.kind(Interner) {
+ let fn_params = fn_subst.len() - trait_params;
+ let trait_ref = TraitRef::new(
+ interner,
+ trait_id.into(),
+ GenericArgs::new_from_iter(interner, fn_subst.iter().take(trait_params)),
+ );
+ let self_ty = trait_ref.self_ty();
+ if let TyKind::Dynamic(d, _) = self_ty.kind() {
+ // 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.
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, 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);
+ .principal_def_id()
+ .is_some_and(|trait_| all_super_traits(db, trait_.0).contains(&trait_id));
if is_my_trait_in_bounds {
return Some(fn_params);
}
@@ -809,24 +413,28 @@ pub fn is_dyn_method(
/// 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>,
+pub(crate) fn lookup_impl_method_query<'db>(
+ db: &'db dyn HirDatabase,
+ env: Arc<TraitEnvironment<'db>>,
func: FunctionId,
- fn_subst: Substitution,
-) -> (FunctionId, Substitution) {
- let ItemContainerId::TraitId(trait_id) = func.lookup(db).container else {
+ fn_subst: GenericArgs<'db>,
+) -> (FunctionId, GenericArgs<'db>) {
+ let interner = DbInterner::new_with(db, env.krate);
+ let infcx = interner.infer_ctxt().build(TypingMode::PostAnalysis);
+
+ let ItemContainerId::TraitId(trait_id) = func.loc(db).container else {
return (func, fn_subst);
};
let trait_params = db.generic_params(trait_id.into()).len();
- let trait_ref = TraitRef {
- trait_id: to_chalk_trait_id(trait_id),
- substitution: Substitution::from_iter(Interner, fn_subst.iter(Interner).take(trait_params)),
- };
+ let trait_ref = TraitRef::new(
+ interner,
+ trait_id.into(),
+ GenericArgs::new_from_iter(interner, fn_subst.iter().take(trait_params)),
+ );
let name = &db.function_signature(func).name;
let Some((impl_fn, impl_subst)) =
- lookup_impl_assoc_item_for_trait_ref(trait_ref, db, env, name).and_then(|assoc| {
+ lookup_impl_assoc_item_for_trait_ref(&infcx, trait_ref, env, name).and_then(|assoc| {
if let (AssocItemId::FunctionId(id), subst) = assoc { Some((id, subst)) } else { None }
})
else {
@@ -835,1136 +443,395 @@ pub(crate) fn lookup_impl_method_query(
(
impl_fn,
- Substitution::from_iter(
- Interner,
- impl_subst.iter(Interner).chain(fn_subst.iter(Interner).skip(trait_params)),
+ GenericArgs::new_from_iter(
+ interner,
+ impl_subst.iter().chain(fn_subst.iter().skip(trait_params)),
),
)
}
-fn lookup_impl_assoc_item_for_trait_ref(
- trait_ref: TraitRef,
- db: &dyn HirDatabase,
- env: Arc<TraitEnvironment>,
+fn lookup_impl_assoc_item_for_trait_ref<'db>(
+ infcx: &InferCtxt<'db>,
+ trait_ref: TraitRef<'db>,
+ env: Arc<TraitEnvironment<'db>>,
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 trait_module = hir_trait_id.module(db);
- let type_module = match self_ty_fp {
- TyFingerprint::Adt(adt_id) => Some(adt_id.module(db)),
- TyFingerprint::ForeignType(type_id) => Some(from_foreign_def_id(type_id).module(db)),
- TyFingerprint::Dyn(trait_id) => Some(trait_id.module(db)),
- _ => None,
- };
-
- let def_blocks: ArrayVec<_, 2> =
- [trait_module.containing_block(), type_module.and_then(|it| it.containing_block())]
- .into_iter()
- .flatten()
- .filter_map(|block_id| db.trait_impls_in_block(block_id))
- .collect();
-
- let impls = impls
- .iter()
- .chain(&def_blocks)
- .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(|(n, it)| match *it {
- AssocItemId::FunctionId(f) => (n == name).then_some(AssocItemId::FunctionId(f)),
- AssocItemId::ConstId(c) => (n == name).then_some(AssocItemId::ConstId(c)),
- AssocItemId::TypeAliasId(_) => None,
- })?;
+) -> Option<(AssocItemId, GenericArgs<'db>)> {
+ let (impl_id, impl_subst) = find_matching_impl(infcx, &env, trait_ref)?;
+ let item =
+ impl_id.impl_items(infcx.interner.db).items.iter().find_map(|(n, it)| match *it {
+ AssocItemId::FunctionId(f) => (n == name).then_some(AssocItemId::FunctionId(f)),
+ AssocItemId::ConstId(c) => (n == name).then_some(AssocItemId::ConstId(c)),
+ 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<(&ImplItems, Substitution)> {
- let db = table.db;
- impls.find_map(|impl_| {
- table.run_in_snapshot(|table| {
- 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;
- }
+pub(crate) fn find_matching_impl<'db>(
+ infcx: &InferCtxt<'db>,
+ env: &TraitEnvironment<'db>,
+ trait_ref: TraitRef<'db>,
+) -> Option<(ImplId, GenericArgs<'db>)> {
+ let trait_ref =
+ infcx.at(&ObligationCause::dummy(), env.env).deeply_normalize(trait_ref).ok()?;
- let wcs = crate::chalk_db::convert_where_clauses(db, impl_.into(), &impl_substs)
- .into_iter()
- .map(|b| -> Goal { b.cast(Interner) });
- for goal in wcs {
- if table.try_obligation(goal.clone()).no_solution() {
- return None;
- }
- table.register_obligation(goal.to_nextsolver(table.interner));
- }
- Some((
- impl_.impl_items(db),
- table.resolve_completely::<_, crate::next_solver::GenericArgs<'_>>(impl_substs),
- ))
- })
- })
-}
+ let obligation = Obligation::new(infcx.interner, ObligationCause::dummy(), env.env, trait_ref);
-fn is_inherent_impl_coherent(
- db: &dyn HirDatabase,
- def_map: &DefMap,
- impl_id: ImplId,
- 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).krate() == def_map.krate(),
- TyKind::Dyn(it) => it.principal_id().is_some_and(|trait_id| {
- from_chalk_trait_id(trait_id).module(db).krate() == def_map.krate()
- }),
+ let selection = infcx.select(&obligation).ok()??;
- _ => 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_signature(id)
- .flags
- .contains(StructFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS),
- hir_def::AdtId::UnionId(id) => db
- .union_signature(id)
- .flags
- .contains(StructFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS),
- hir_def::AdtId::EnumId(it) => db
- .enum_signature(it)
- .flags
- .contains(EnumFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS),
- },
- TyKind::Dyn(it) => it.principal_id().is_some_and(|trait_id| {
- db.trait_signature(from_chalk_trait_id(trait_id))
- .flags
- .contains(TraitFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS)
- }),
+ // Currently, we use a fulfillment context to completely resolve
+ // all nested obligations. This is because they can inform the
+ // inference of the impl's type parameters.
+ let mut ocx = ObligationCtxt::new(infcx);
+ let impl_source = selection.map(|obligation| ocx.register_obligation(obligation));
- _ => false,
- };
- let items = impl_id.impl_items(db);
- rustc_has_incoherent_inherent_impls
- && !items.items.is_empty()
- && items.items.iter().all(|&(_, assoc)| match assoc {
- AssocItemId::FunctionId(it) => {
- db.function_signature(it).flags.contains(FnFlags::RUSTC_ALLOW_INCOHERENT_IMPL)
- }
- AssocItemId::ConstId(it) => {
- db.const_signature(it).flags.contains(ConstFlags::RUSTC_ALLOW_INCOHERENT_IMPL)
- }
- AssocItemId::TypeAliasId(it) => db
- .type_alias_signature(it)
- .flags
- .contains(TypeAliasFlags::RUSTC_ALLOW_INCOHERENT_IMPL),
- })
+ let errors = ocx.evaluate_obligations_error_on_ambiguity();
+ if !errors.is_empty() {
+ return None;
}
-}
-/// 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).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).krate()) {
- // trait to be implemented is local
- return true;
+ let impl_source = infcx.resolve_vars_if_possible(impl_source);
+ if impl_source.has_non_region_infer() {
+ return None;
}
- let unwrap_fundamental = |mut ty: Ty| {
- // Unwrap all layers of fundamental types with a loop.
- loop {
- match ty.kind(Interner) {
- TyKind::Ref(_, _, referenced) => ty = referenced.clone(),
- &TyKind::Adt(AdtId(hir_def::AdtId::StructId(s)), ref subs) => {
- let struct_signature = db.struct_signature(s);
- if struct_signature.flags.contains(StructFlags::FUNDAMENTAL) {
- let next = subs.type_parameters(Interner).next();
- match next {
- Some(it) => ty = it,
- None => break ty,
- }
- } else {
- break ty;
- }
- }
- _ => break ty,
- }
- }
- };
- // - At least one of the types `T0..=Tn`` must be a local type. Let `Ti`` be the first such type.
-
- // FIXME: param coverage
- // - No uncovered type parameters `P1..=Pn` may appear in `T0..Ti`` (excluding `Ti`)
- 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).krate()),
- TyKind::Error => true,
- TyKind::Dyn(it) => it
- .principal_id()
- .is_some_and(|trait_id| is_local(from_chalk_trait_id(trait_id).module(db).krate())),
- _ => false,
- }
- });
- #[allow(clippy::let_and_return)]
- is_not_orphan
-}
-
-pub fn iterate_path_candidates<'db>(
- ty: &next_solver::Canonical<'db, crate::next_solver::Ty<'db>>,
- db: &'db dyn HirDatabase,
- env: Arc<TraitEnvironment>,
- traits_in_scope: &FxHashSet<TraitId>,
- visible_from_module: VisibleFromModule,
- name: Option<&Name>,
- callback: &mut dyn MethodCandidateCallback,
-) -> 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
- callback,
- )
+ match impl_source {
+ ImplSource::UserDefined(impl_source) => Some((impl_source.impl_def_id, impl_source.args)),
+ ImplSource::Param(_) | ImplSource::Builtin(..) => None,
+ }
}
-pub fn iterate_method_candidates_dyn<'db>(
- ty: &next_solver::Canonical<'db, crate::next_solver::Ty<'db>>,
- db: &'db dyn HirDatabase,
- env: Arc<TraitEnvironment>,
- traits_in_scope: &FxHashSet<TraitId>,
- visible_from_module: VisibleFromModule,
- name: Option<&Name>,
- mode: LookupMode,
- callback: &mut dyn MethodCandidateCallback,
-) -> 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_ns(*ty);
- 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,
- )
- }
- }
+#[salsa::tracked(returns(ref))]
+fn crates_containing_incoherent_inherent_impls(db: &dyn HirDatabase) -> Box<[Crate]> {
+ // We assume that only sysroot crates contain `#[rustc_has_incoherent_inherent_impls]`
+ // impls, since this is an internal feature and only std uses it.
+ db.all_crates().iter().copied().filter(|krate| krate.data(db).origin.is_lang()).collect()
}
-#[tracing::instrument(skip_all, fields(name = ?name))]
-fn iterate_method_candidates_with_autoref<'db>(
- table: &mut InferenceTable<'db>,
- receiver_ty: next_solver::Canonical<'db, crate::next_solver::Ty<'db>>,
- first_adjustment: ReceiverAdjustments,
- traits_in_scope: &FxHashSet<TraitId>,
- visible_from_module: VisibleFromModule,
- name: Option<&Name>,
- callback: &mut dyn MethodCandidateCallback,
-) -> ControlFlow<()> {
- let interner = table.interner;
-
- 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,
- callback,
- )
+pub fn incoherent_inherent_impls(db: &dyn HirDatabase, self_ty: SimplifiedType) -> &[ImplId] {
+ let has_incoherent_impls = match self_ty.def() {
+ Some(def_id) => match def_id.try_into() {
+ Ok(def_id) => AttrFlags::query(db, def_id)
+ .contains(AttrFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS),
+ Err(()) => true,
+ },
+ _ => true,
};
-
- let mut maybe_reborrowed = first_adjustment.clone();
- if let rustc_type_ir::TyKind::Ref(_, _, m) = receiver_ty.value.kind() {
- let m = match m {
- rustc_ast_ir::Mutability::Mut => chalk_ir::Mutability::Mut,
- rustc_ast_ir::Mutability::Not => chalk_ir::Mutability::Not,
- };
- // Prefer reborrow of references to move
- maybe_reborrowed.autoref = Some(AutorefOrPtrAdjustment::Autoref(m));
- maybe_reborrowed.autoderefs += 1;
- }
-
- iterate_method_candidates_by_receiver(receiver_ty, maybe_reborrowed)?;
-
- let refed = next_solver::Canonical {
- max_universe: receiver_ty.max_universe,
- variables: receiver_ty.variables,
- value: next_solver::Ty::new_ref(
- interner,
- next_solver::Region::error(interner),
- receiver_ty.value,
- rustc_ast_ir::Mutability::Not,
- ),
+ return if !has_incoherent_impls {
+ &[]
+ } else {
+ incoherent_inherent_impls_query(db, (), self_ty)
};
- iterate_method_candidates_by_receiver(
- refed,
- first_adjustment.with_autoref(AutorefOrPtrAdjustment::Autoref(Mutability::Not)),
- )?;
-
- let ref_muted = next_solver::Canonical {
- max_universe: receiver_ty.max_universe,
- variables: receiver_ty.variables,
- value: next_solver::Ty::new_ref(
- interner,
- next_solver::Region::error(interner),
- receiver_ty.value,
- rustc_ast_ir::Mutability::Mut,
- ),
- };
+ #[salsa::tracked(returns(ref))]
+ fn incoherent_inherent_impls_query(
+ db: &dyn HirDatabase,
+ _force_query_input_to_be_interned: (),
+ self_ty: SimplifiedType,
+ ) -> Box<[ImplId]> {
+ let _p = tracing::info_span!("incoherent_inherent_impl_crates").entered();
- iterate_method_candidates_by_receiver(
- ref_muted,
- first_adjustment.with_autoref(AutorefOrPtrAdjustment::Autoref(Mutability::Mut)),
- )?;
-
- if let rustc_type_ir::TyKind::RawPtr(ty, rustc_ast_ir::Mutability::Mut) =
- receiver_ty.value.kind()
- {
- let const_ptr_ty = rustc_type_ir::Canonical {
- max_universe: rustc_type_ir::UniverseIndex::ZERO,
- value: next_solver::Ty::new_ptr(interner, ty, rustc_ast_ir::Mutability::Not),
- variables: receiver_ty.variables,
- };
- iterate_method_candidates_by_receiver(
- const_ptr_ty,
- first_adjustment.with_autoref(AutorefOrPtrAdjustment::ToConstPtr),
- )?;
+ let mut result = Vec::new();
+ for &krate in crates_containing_incoherent_inherent_impls(db) {
+ let impls = InherentImpls::for_crate(db, krate);
+ result.extend_from_slice(impls.for_self_ty(&self_ty));
+ }
+ result.into_boxed_slice()
}
-
- ControlFlow::Continue(())
}
-pub trait MethodCandidateCallback {
- fn on_inherent_method(
- &mut self,
- adjustments: ReceiverAdjustments,
- item: AssocItemId,
- is_visible: bool,
- ) -> ControlFlow<()>;
+pub fn simplified_type_module(db: &dyn HirDatabase, ty: &SimplifiedType) -> Option<ModuleId> {
+ match ty.def()? {
+ SolverDefId::AdtId(id) => Some(id.module(db)),
+ SolverDefId::TypeAliasId(id) => Some(id.module(db)),
+ SolverDefId::TraitId(id) => Some(id.module(db)),
+ _ => None,
+ }
+}
- fn on_trait_method(
- &mut self,
- adjustments: ReceiverAdjustments,
- item: AssocItemId,
- is_visible: bool,
- ) -> ControlFlow<()>;
+#[derive(Debug, PartialEq, Eq)]
+pub struct InherentImpls {
+ map: FxHashMap<SimplifiedType, Box<[ImplId]>>,
}
-impl<F> MethodCandidateCallback for F
-where
- F: FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
-{
- fn on_inherent_method(
- &mut self,
- adjustments: ReceiverAdjustments,
- item: AssocItemId,
- is_visible: bool,
- ) -> ControlFlow<()> {
- self(adjustments, item, is_visible)
- }
+#[salsa::tracked]
+impl InherentImpls {
+ #[salsa::tracked(returns(ref))]
+ pub fn for_crate(db: &dyn HirDatabase, krate: Crate) -> Self {
+ let _p = tracing::info_span!("inherent_impls_in_crate_query", ?krate).entered();
- fn on_trait_method(
- &mut self,
- adjustments: ReceiverAdjustments,
- item: AssocItemId,
- is_visible: bool,
- ) -> ControlFlow<()> {
- self(adjustments, item, is_visible)
+ let crate_def_map = crate_def_map(db, krate);
+
+ Self::collect_def_map(db, crate_def_map)
}
-}
-#[tracing::instrument(skip_all, fields(name = ?name))]
-fn iterate_method_candidates_by_receiver<'db>(
- table: &mut InferenceTable<'db>,
- receiver_ty: next_solver::Canonical<'db, crate::next_solver::Ty<'db>>,
- receiver_adjustments: ReceiverAdjustments,
- traits_in_scope: &FxHashSet<TraitId>,
- visible_from_module: VisibleFromModule,
- name: Option<&Name>,
- callback: &mut dyn MethodCandidateCallback,
-) -> ControlFlow<()> {
- let interner = table.interner;
- let receiver_ty = table.instantiate_canonical_ns(receiver_ty);
- let receiver_ty: crate::Ty = receiver_ty.to_chalk(interner);
- // 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.to_nextsolver(interner))
- .include_raw_pointers()
- .use_receiver_trait();
- while let Some((self_ty, _)) = autoderef.next() {
- iterate_inherent_methods(
- &self_ty.to_chalk(interner),
- autoderef.table,
- name,
- Some(&receiver_ty),
- Some(receiver_adjustments.clone()),
- visible_from_module,
- LookupMode::MethodCall,
- &mut |adjustments, item, is_visible| {
- callback.on_inherent_method(adjustments, item, is_visible)
- },
- )?
- }
- ControlFlow::Continue(())
- })?;
- table.run_in_snapshot(|table| {
- let mut autoderef =
- autoderef::Autoderef::new_no_tracking(table, receiver_ty.to_nextsolver(interner))
- .include_raw_pointers()
- .use_receiver_trait();
- while let Some((self_ty, _)) = autoderef.next() {
- if matches!(self_ty.kind(), crate::next_solver::TyKind::Infer(rustc_type_ir::TyVar(_)))
- {
- // don't try to resolve methods on unknown types
- return ControlFlow::Continue(());
- }
+ #[salsa::tracked(returns(ref))]
+ pub fn for_block(db: &dyn HirDatabase, block: BlockId) -> Option<Box<Self>> {
+ let _p = tracing::info_span!("inherent_impls_in_block_query").entered();
- iterate_trait_method_candidates(
- &self_ty.to_chalk(interner),
- autoderef.table,
- traits_in_scope,
- name,
- Some(&receiver_ty),
- Some(receiver_adjustments.clone()),
- LookupMode::MethodCall,
- &mut |adjustments, item, is_visible| {
- callback.on_trait_method(adjustments, item, is_visible)
- },
- )?
- }
- ControlFlow::Continue(())
- })
+ let block_def_map = block_def_map(db, block);
+ let result = Self::collect_def_map(db, block_def_map);
+ if result.map.is_empty() { None } else { Some(Box::new(result)) }
+ }
}
-#[tracing::instrument(skip_all, fields(name = ?name))]
-fn iterate_method_candidates_for_self_ty<'db>(
- self_ty: &next_solver::Canonical<'db, crate::next_solver::Ty<'db>>,
- db: &'db dyn HirDatabase,
- env: Arc<TraitEnvironment>,
- traits_in_scope: &FxHashSet<TraitId>,
- visible_from_module: VisibleFromModule,
- name: Option<&Name>,
- callback: &mut dyn MethodCandidateCallback,
-) -> ControlFlow<()> {
- let mut table = InferenceTable::new(db, env);
- let self_ty = table.instantiate_canonical_ns(*self_ty).to_chalk(table.interner);
- iterate_inherent_methods(
- &self_ty,
- &mut table,
- name,
- None,
- None,
- visible_from_module,
- LookupMode::Path,
- &mut |adjustments, item, is_visible| {
- callback.on_inherent_method(adjustments, item, is_visible)
- },
- )?;
- iterate_trait_method_candidates(
- &self_ty,
- &mut table,
- traits_in_scope,
- name,
- None,
- None,
- LookupMode::Path,
- &mut |adjustments, item, is_visible| {
- callback.on_trait_method(adjustments, item, is_visible)
- },
- )
-}
+impl InherentImpls {
+ fn collect_def_map(db: &dyn HirDatabase, def_map: &DefMap) -> Self {
+ let mut map = FxHashMap::default();
+ collect(db, def_map, &mut map);
+ let mut map = map
+ .into_iter()
+ .map(|(self_ty, impls)| (self_ty, impls.into_boxed_slice()))
+ .collect::<FxHashMap<_, _>>();
+ map.shrink_to_fit();
+ return Self { map };
+
+ fn collect(
+ db: &dyn HirDatabase,
+ def_map: &DefMap,
+ map: &mut FxHashMap<SimplifiedType, Vec<ImplId>>,
+ ) {
+ for (_module_id, module_data) in def_map.modules() {
+ for impl_id in module_data.scope.impls() {
+ let data = db.impl_signature(impl_id);
+ if data.target_trait.is_some() {
+ continue;
+ }
-#[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>,
- mode: LookupMode,
- callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
-) -> ControlFlow<()> {
- let db = table.db;
-
- let canonical_self_ty = table.canonicalize(self_ty.clone().to_nextsolver(table.interner));
- let TraitEnvironment { krate, .. } = *table.trait_env;
-
- 'traits: for &t in traits_in_scope {
- let data = db.trait_signature(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.flags.contains(TraitFlags::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 !krate.data(db).edition.at_least_2021() {
- continue;
- }
- }
- if data.flags.contains(TraitFlags::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 !krate.data(db).edition.at_least_2024() {
- continue;
- }
- }
+ let interner = DbInterner::new_no_crate(db);
+ let self_ty = db.impl_self_ty(impl_id);
+ let self_ty = self_ty.instantiate_identity();
+ if let Some(self_ty) =
+ simplify_type(interner, self_ty, TreatParams::InstantiateWithInfer)
+ {
+ map.entry(self_ty).or_default().push(impl_id);
+ }
+ }
- // 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 t.trait_items(db).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,
- mode,
- ) {
- IsValidCandidate::Yes => true,
- IsValidCandidate::NotVisible => false,
- IsValidCandidate::No => continue,
- };
- if !known_implemented {
- let goal = generic_implements_goal_ns(table, t, canonical_self_ty);
- if next_trait_solve_canonical_in_ctxt(&table.infer_ctxt, goal).no_solution() {
- continue 'traits;
+ // 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) {
+ collect(db, block_def_map, map);
+ }
}
}
- 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,
- mode: LookupMode,
- 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, t));
- iterate_inherent_trait_methods(
- self_ty,
- table,
- name,
- receiver_ty,
- receiver_adjustments.clone(),
- callback,
- traits,
- mode,
- )?;
- }
- TyKind::Dyn(_) => {
- if let Some(principal_trait) = self_ty.dyn_trait() {
- let traits = all_super_traits(db, principal_trait);
- iterate_inherent_trait_methods(
- self_ty,
- table,
- name,
- receiver_ty,
- receiver_adjustments.clone(),
- callback,
- traits.into_iter(),
- mode,
- )?;
- }
- }
- _ => {}
+ pub fn for_self_ty(&self, self_ty: &SimplifiedType) -> &[ImplId] {
+ self.map.get(self_ty).map(|it| &**it).unwrap_or_default()
}
- 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 = block_def_map(db, block_id).parent().and_then(|module| module.containing_block());
+ pub fn for_each_crate_and_block(
+ db: &dyn HirDatabase,
+ krate: Crate,
+ block: Option<BlockId>,
+ for_each: &mut dyn FnMut(&InherentImpls),
+ ) {
+ let blocks = std::iter::successors(block, |block| block.loc(db).module.containing_block());
+ blocks.filter_map(|block| Self::for_block(db, block).as_deref()).for_each(&mut *for_each);
+ for_each(Self::for_crate(db, krate));
}
+}
- 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>,
- mode: LookupMode,
- ) -> ControlFlow<()> {
- let db = table.db;
- for t in traits {
- let data = t.trait_items(db);
- 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,
- mode,
- ) {
- IsValidCandidate::Yes => true,
- IsValidCandidate::NotVisible => false,
- IsValidCandidate::No => continue,
- };
- callback(receiver_adjustments.clone().unwrap_or_default(), item, visible)?;
- }
- }
- ControlFlow::Continue(())
- }
+#[derive(Debug, PartialEq)]
+struct OneTraitImpls {
+ non_blanket_impls: FxHashMap<SimplifiedType, Box<[ImplId]>>,
+ blanket_impls: Box<[ImplId]>,
+}
- #[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 &(ref item_name, item) in impl_id.impl_items(table.db).items.iter() {
- let visible = match is_valid_impl_method_candidate(
- table,
- self_ty,
- receiver_ty,
- visible_from_module,
- name,
- impl_id,
- item,
- item_name,
- ) {
- IsValidCandidate::Yes => true,
- IsValidCandidate::NotVisible => false,
- IsValidCandidate::No => continue,
- };
- callback(receiver_adjustments.clone().unwrap_or_default(), item, visible)?;
- }
- }
- ControlFlow::Continue(())
- }
+#[derive(Default)]
+struct OneTraitImplsBuilder {
+ non_blanket_impls: FxHashMap<SimplifiedType, Vec<ImplId>>,
+ blanket_impls: Vec<ImplId>,
}
-/// Returns the receiver type for the index trait call.
-pub(crate) fn resolve_indexing_op<'db>(
- table: &mut InferenceTable<'db>,
- ty: next_solver::Canonical<'db, next_solver::Ty<'db>>,
- index_trait: TraitId,
-) -> Option<ReceiverAdjustments> {
- let ty = table.instantiate_canonical_ns(ty);
- let deref_chain = autoderef_method_receiver(table, ty);
- for (ty, adj) in deref_chain {
- //let goal = generic_implements_goal_ns(db, &table.trait_env, index_trait, &ty);
- let goal = generic_implements_goal_ns(table, index_trait, ty);
- if !next_trait_solve_canonical_in_ctxt(&table.infer_ctxt, goal).no_solution() {
- return Some(adj);
- }
+impl OneTraitImplsBuilder {
+ fn finish(self) -> OneTraitImpls {
+ let mut non_blanket_impls = self
+ .non_blanket_impls
+ .into_iter()
+ .map(|(self_ty, impls)| (self_ty, impls.into_boxed_slice()))
+ .collect::<FxHashMap<_, _>>();
+ non_blanket_impls.shrink_to_fit();
+ let blanket_impls = self.blanket_impls.into_boxed_slice();
+ OneTraitImpls { non_blanket_impls, blanket_impls }
}
- None
}
-// FIXME: Replace this with a `Try` impl once stable
-macro_rules! check_that {
- ($cond:expr) => {
- if !$cond {
- return IsValidCandidate::No;
- }
- };
+#[derive(Debug, PartialEq)]
+pub struct TraitImpls {
+ map: FxHashMap<TraitId, OneTraitImpls>,
}
-#[derive(Debug)]
-enum IsValidCandidate {
- Yes,
- No,
- NotVisible,
-}
+#[salsa::tracked]
+impl TraitImpls {
+ #[salsa::tracked(returns(ref))]
+ pub fn for_crate(db: &dyn HirDatabase, krate: Crate) -> Arc<Self> {
+ let _p = tracing::info_span!("inherent_impls_in_crate_query", ?krate).entered();
-#[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,
- item_name: &Name,
-) -> IsValidCandidate {
- match item {
- AssocItemId::FunctionId(f) => is_valid_impl_fn_candidate(
- table,
- impl_id,
- f,
- name,
- receiver_ty,
- self_ty,
- visible_from_module,
- item_name,
- ),
- AssocItemId::ConstId(c) => {
- let db = table.db;
- check_that!(receiver_ty.is_none());
- check_that!(name.is_none_or(|n| n == item_name));
-
- if let Some(from_module) = visible_from_module
- && !db.assoc_visibility(c.into()).is_visible_from(db, 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,
+ let crate_def_map = crate_def_map(db, krate);
+ let result = Self::collect_def_map(db, crate_def_map);
+ Arc::new(result)
+ }
+
+ #[salsa::tracked(returns(ref))]
+ pub fn for_block(db: &dyn HirDatabase, block: BlockId) -> Option<Box<Self>> {
+ let _p = tracing::info_span!("inherent_impls_in_block_query").entered();
+
+ let block_def_map = block_def_map(db, block);
+ let result = Self::collect_def_map(db, block_def_map);
+ if result.map.is_empty() { None } else { Some(Box::new(result)) }
+ }
+
+ #[salsa::tracked(returns(ref))]
+ pub fn for_crate_and_deps(db: &dyn HirDatabase, krate: Crate) -> Box<[Arc<Self>]> {
+ krate.transitive_deps(db).iter().map(|&dep| Self::for_crate(db, dep).clone()).collect()
}
}
-/// 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,
- mode: LookupMode,
-) -> IsValidCandidate {
- let db = table.db;
- match item {
- AssocItemId::FunctionId(fn_id) => {
- let data = db.function_signature(fn_id);
-
- check_that!(name.is_none_or(|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);
-
- // FIXME: Clean up this mess with some context struct like rustc's `ProbeContext`
- let variance = match mode {
- LookupMode::MethodCall => rustc_type_ir::Variance::Covariant,
- LookupMode::Path => rustc_type_ir::Variance::Invariant,
- };
- let res = table
- .infer_ctxt
- .at(
- &next_solver::infer::traits::ObligationCause::dummy(),
- table.trait_env.env.to_nextsolver(table.interner),
- )
- .relate(
- DefineOpaqueTypes::No,
- expected_receiver.to_nextsolver(table.interner),
- variance,
- receiver_ty.to_nextsolver(table.interner),
- );
- let Ok(infer_ok) = res else {
- return IsValidCandidate::No;
+impl TraitImpls {
+ fn collect_def_map(db: &dyn HirDatabase, def_map: &DefMap) -> Self {
+ let mut map = FxHashMap::default();
+ collect(db, def_map, &mut map);
+ let mut map = map
+ .into_iter()
+ .map(|(trait_id, trait_map)| (trait_id, trait_map.finish()))
+ .collect::<FxHashMap<_, _>>();
+ map.shrink_to_fit();
+ return Self { map };
+
+ fn collect(
+ db: &dyn HirDatabase,
+ def_map: &DefMap,
+ map: &mut FxHashMap<TraitId, OneTraitImplsBuilder>,
+ ) {
+ 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 AttrFlags::query(db, impl_id.into())
+ .contains(AttrFlags::RUSTC_RESERVATION_IMPL)
+ {
+ continue;
+ }
+ let trait_ref = match db.impl_trait(impl_id) {
+ Some(tr) => tr.instantiate_identity(),
+ None => continue,
};
-
- if !infer_ok.obligations.is_empty() {
- let mut ctxt = FulfillmentCtxt::new(&table.infer_ctxt);
- for pred in infer_ok.into_obligations() {
- ctxt.register_predicate_obligation(&table.infer_ctxt, pred);
+ let self_ty = trait_ref.self_ty();
+ let interner = DbInterner::new_no_crate(db);
+ let entry = map.entry(trait_ref.def_id.0).or_default();
+ match simplify_type(interner, self_ty, TreatParams::InstantiateWithInfer) {
+ Some(self_ty) => {
+ entry.non_blanket_impls.entry(self_ty).or_default().push(impl_id)
}
- // FIXME: Are we doing this correctly? Probably better to follow rustc more closely.
- check_that!(ctxt.select_where_possible(&table.infer_ctxt).is_empty());
+ None => entry.blanket_impls.push(impl_id),
}
-
- check_that!(table.unify(receiver_ty, &expected_receiver));
}
- IsValidCandidate::Yes
- })
- }
- AssocItemId::ConstId(c) => {
- check_that!(receiver_ty.is_none());
- check_that!(name.is_none_or(|n| db.const_signature(c).name.as_ref() == Some(n)));
-
- IsValidCandidate::Yes
+ // 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) {
+ collect(db, block_def_map, map);
+ }
+ }
+ }
}
- _ => 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>,
- item_name: &Name,
-) -> IsValidCandidate {
- check_that!(name.is_none_or(|n| n == item_name));
-
- let db = table.db;
- let data = db.function_signature(fn_id);
-
- if let Some(from_module) = visible_from_module
- && !db.assoc_visibility(fn_id.into()).is_visible_from(db, from_module)
- {
- cov_mark::hit!(autoderef_candidate_not_visible);
- return IsValidCandidate::NotVisible;
+ pub fn blanket_impls(&self, for_trait: TraitId) -> &[ImplId] {
+ self.map.get(&for_trait).map(|it| &*it.blanket_impls).unwrap_or_default()
}
- 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);
+ /// Queries whether `self_ty` has potentially applicable implementations of `trait_`.
+ pub fn has_impls_for_trait_and_self_ty(
+ &self,
+ trait_: TraitId,
+ self_ty: &SimplifiedType,
+ ) -> bool {
+ self.map.get(&trait_).is_some_and(|trait_impls| {
+ trait_impls.non_blanket_impls.contains_key(self_ty)
+ || !trait_impls.blanket_impls.is_empty()
+ })
+ }
- check_that!(table.unify(receiver_ty, &expected_receiver));
- }
+ pub fn for_trait_and_self_ty(&self, trait_: TraitId, self_ty: &SimplifiedType) -> &[ImplId] {
+ self.map
+ .get(&trait_)
+ .and_then(|map| map.non_blanket_impls.get(self_ty))
+ .map(|it| &**it)
+ .unwrap_or_default()
+ }
- // 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() {
- match table.solve_obligation(goal) {
- Ok(_) => {}
- Err(_) => {
- return IsValidCandidate::No;
- }
+ pub fn for_trait(&self, trait_: TraitId, mut callback: impl FnMut(&[ImplId])) {
+ if let Some(impls) = self.map.get(&trait_) {
+ callback(&impls.blanket_impls);
+ for impls in impls.non_blanket_impls.values() {
+ callback(impls);
}
}
+ }
- for goal in goals {
- if table.try_obligation(goal).no_solution() {
- return IsValidCandidate::No;
+ pub fn for_self_ty(&self, self_ty: &SimplifiedType, mut callback: impl FnMut(&[ImplId])) {
+ for for_trait in self.map.values() {
+ if let Some(for_ty) = for_trait.non_blanket_impls.get(self_ty) {
+ callback(for_ty);
}
}
+ }
- 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);
- !db.trait_solve(env.krate, env.block, goal.cast(Interner)).no_solution()
-}
-
-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);
- db.trait_solve(env.krate, env.block, goal.cast(Interner)).certain()
-}
-
-/// 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 }
-}
-
-/// This creates Substs for a trait with the given Self type and type variables
-/// for all other parameters, to query the trait solver with it.
-#[tracing::instrument(skip_all)]
-fn generic_implements_goal_ns<'db>(
- table: &mut InferenceTable<'db>,
- trait_: TraitId,
- self_ty: next_solver::Canonical<'db, crate::next_solver::Ty<'db>>,
-) -> next_solver::Canonical<'db, next_solver::Goal<'db, crate::next_solver::Predicate<'db>>> {
- let args = table.infer_ctxt.fresh_args_for_item(SolverDefId::TraitId(trait_));
- let self_ty = table.instantiate_canonical_ns(self_ty);
- let trait_ref =
- rustc_type_ir::TraitRef::new_from_args(table.infer_ctxt.interner, trait_.into(), args)
- .with_replaced_self_ty(table.infer_ctxt.interner, self_ty);
- let goal = next_solver::Goal::new(
- table.infer_ctxt.interner,
- table.trait_env.env.to_nextsolver(table.infer_ctxt.interner),
- trait_ref,
- );
-
- table.canonicalize(goal)
-}
-
-fn autoderef_method_receiver<'db>(
- table: &mut InferenceTable<'db>,
- ty: next_solver::Ty<'db>,
-) -> Vec<(next_solver::Canonical<'db, crate::next_solver::Ty<'db>>, ReceiverAdjustments)> {
- let interner = table.interner;
- let mut deref_chain = Vec::new();
- let mut autoderef = autoderef::Autoderef::new_no_tracking(table, ty).use_receiver_trait();
- while let Some((ty, derefs)) = autoderef.next() {
- deref_chain.push((
- autoderef.table.canonicalize(ty),
- ReceiverAdjustments { autoref: None, autoderefs: derefs, unsize_array: false },
- ));
+ pub fn for_each_crate_and_block(
+ db: &dyn HirDatabase,
+ krate: Crate,
+ block: Option<BlockId>,
+ for_each: &mut dyn FnMut(&TraitImpls),
+ ) {
+ let blocks = std::iter::successors(block, |block| block.loc(db).module.containing_block());
+ blocks.filter_map(|block| Self::for_block(db, block).as_deref()).for_each(&mut *for_each);
+ Self::for_crate_and_deps(db, krate).iter().map(|it| &**it).for_each(for_each);
}
- // As a last step, we can do array unsizing (that's the only unsizing that rustc does for method receivers!)
- if let Some((rustc_type_ir::Array(parameters, _), variables, max_universe, adj)) =
- deref_chain.last().map(|d| (d.0.value.kind(), d.0.variables, d.0.max_universe, d.1.clone()))
- {
- let unsized_ty = next_solver::Ty::new_slice(interner, parameters);
- deref_chain.push((
- next_solver::Canonical { max_universe, value: unsized_ty, variables },
- ReceiverAdjustments { unsize_array: true, ..adj.clone() },
- ));
+
+ /// Like [`Self::for_each_crate_and_block()`], but takes in account two blocks, one for a trait and one for a self type.
+ pub fn for_each_crate_and_block_trait_and_type(
+ db: &dyn HirDatabase,
+ krate: Crate,
+ type_block: Option<BlockId>,
+ trait_block: Option<BlockId>,
+ for_each: &mut dyn FnMut(&TraitImpls),
+ ) {
+ let in_self_and_deps = TraitImpls::for_crate_and_deps(db, krate);
+ in_self_and_deps.iter().for_each(|impls| for_each(impls));
+
+ // We must not provide duplicate impls to the solver. Therefore we work with the following strategy:
+ // start from each block, and walk ancestors until you meet the other block. If they never meet,
+ // that means there can't be duplicate impls; if they meet, we stop the search of the deeper block.
+ // This breaks when they are equal (both will stop immediately), therefore we handle this case
+ // specifically.
+ let blocks_iter = |block: Option<BlockId>| {
+ std::iter::successors(block, |block| block.loc(db).module.containing_block())
+ };
+ let for_each_block = |current_block: Option<BlockId>, other_block: Option<BlockId>| {
+ blocks_iter(current_block)
+ .take_while(move |&block| {
+ other_block.is_none_or(|other_block| other_block != block)
+ })
+ .filter_map(move |block| TraitImpls::for_block(db, block).as_deref())
+ };
+ if trait_block == type_block {
+ blocks_iter(trait_block)
+ .filter_map(|block| TraitImpls::for_block(db, block).as_deref())
+ .for_each(for_each);
+ } else {
+ for_each_block(trait_block, type_block).for_each(&mut *for_each);
+ for_each_block(type_block, trait_block).for_each(for_each);
+ }
}
- deref_chain
}