1 //! This module is concerned with finding methods that a given type provides.
2 //! For details about how this works in rustc, see the method lookup page in the
3 //! [rustc guide](https://rust-lang.github.io/rustc-guide/method-lookup.html)
4 //! and the corresponding code mostly in librustc_typeck/check/method/probe.rs.
5 use std::{iter, ops::ControlFlow, sync::Arc};
7 use arrayvec::ArrayVec;
8 use base_db::{CrateId, Edition};
9 use chalk_ir::{cast::Cast, Mutability, UniverseIndex};
11 data::ImplData, item_scope::ItemScope, nameres::DefMap, AssocItemId, BlockId, ConstId,
12 FunctionId, GenericDefId, HasModule, ImplId, ItemContainerId, Lookup, ModuleDefId, ModuleId,
15 use hir_expand::name::Name;
16 use rustc_hash::{FxHashMap, FxHashSet};
20 autoderef::{self, AutoderefKind},
23 infer::{unify::InferenceTable, Adjust, Adjustment, AutoBorrow, OverloadedDeref, PointerCast},
24 primitive::{FloatTy, IntTy, UintTy},
26 utils::all_super_traits,
27 AdtId, Canonical, CanonicalVarKinds, DebruijnIndex, ForeignDefId, InEnvironment, Interner,
28 Scalar, TraitEnvironment, TraitRefExt, Ty, TyBuilder, TyExt, TyKind,
31 /// This is used as a key for indexing impls.
32 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
33 pub enum TyFingerprint {
34 // These are lang item impls:
41 // These can have user-defined impls:
44 ForeignType(ForeignDefId),
45 // These only exist for trait impls
52 /// Creates a TyFingerprint for looking up an inherent impl. Only certain
53 /// types can have inherent impls: if we have some `struct S`, we can have
54 /// an `impl S`, but not `impl &S`. Hence, this will return `None` for
55 /// reference types and such.
56 pub fn for_inherent_impl(ty: &Ty) -> Option<TyFingerprint> {
57 let fp = match ty.kind(Interner) {
58 TyKind::Str => TyFingerprint::Str,
59 TyKind::Never => TyFingerprint::Never,
60 TyKind::Slice(..) => TyFingerprint::Slice,
61 TyKind::Array(..) => TyFingerprint::Array,
62 TyKind::Scalar(scalar) => TyFingerprint::Scalar(*scalar),
63 TyKind::Adt(AdtId(adt), _) => TyFingerprint::Adt(*adt),
64 TyKind::Raw(mutability, ..) => TyFingerprint::RawPtr(*mutability),
65 TyKind::Foreign(alias_id, ..) => TyFingerprint::ForeignType(*alias_id),
66 TyKind::Dyn(_) => ty.dyn_trait().map(TyFingerprint::Dyn)?,
72 /// Creates a TyFingerprint for looking up a trait impl.
73 pub fn for_trait_impl(ty: &Ty) -> Option<TyFingerprint> {
74 let fp = match ty.kind(Interner) {
75 TyKind::Str => TyFingerprint::Str,
76 TyKind::Never => TyFingerprint::Never,
77 TyKind::Slice(..) => TyFingerprint::Slice,
78 TyKind::Array(..) => TyFingerprint::Array,
79 TyKind::Scalar(scalar) => TyFingerprint::Scalar(*scalar),
80 TyKind::Adt(AdtId(adt), _) => TyFingerprint::Adt(*adt),
81 TyKind::Raw(mutability, ..) => TyFingerprint::RawPtr(*mutability),
82 TyKind::Foreign(alias_id, ..) => TyFingerprint::ForeignType(*alias_id),
83 TyKind::Dyn(_) => ty.dyn_trait().map(TyFingerprint::Dyn)?,
84 TyKind::Ref(_, _, ty) => return TyFingerprint::for_trait_impl(ty),
85 TyKind::Tuple(_, subst) => {
86 let first_ty = subst.interned().get(0).map(|arg| arg.assert_ty_ref(Interner));
88 Some(ty) => return TyFingerprint::for_trait_impl(ty),
89 None => TyFingerprint::Unit,
92 TyKind::AssociatedType(_, _)
93 | TyKind::OpaqueType(_, _)
95 | TyKind::Closure(_, _)
96 | TyKind::Generator(..)
97 | TyKind::GeneratorWitness(..) => TyFingerprint::Unnameable,
98 TyKind::Function(fn_ptr) => {
99 TyFingerprint::Function(fn_ptr.substitution.0.len(Interner) as u32)
102 | TyKind::Placeholder(_)
103 | TyKind::BoundVar(_)
104 | TyKind::InferenceVar(_, _)
105 | TyKind::Error => return None,
111 pub(crate) const ALL_INT_FPS: [TyFingerprint; 12] = [
112 TyFingerprint::Scalar(Scalar::Int(IntTy::I8)),
113 TyFingerprint::Scalar(Scalar::Int(IntTy::I16)),
114 TyFingerprint::Scalar(Scalar::Int(IntTy::I32)),
115 TyFingerprint::Scalar(Scalar::Int(IntTy::I64)),
116 TyFingerprint::Scalar(Scalar::Int(IntTy::I128)),
117 TyFingerprint::Scalar(Scalar::Int(IntTy::Isize)),
118 TyFingerprint::Scalar(Scalar::Uint(UintTy::U8)),
119 TyFingerprint::Scalar(Scalar::Uint(UintTy::U16)),
120 TyFingerprint::Scalar(Scalar::Uint(UintTy::U32)),
121 TyFingerprint::Scalar(Scalar::Uint(UintTy::U64)),
122 TyFingerprint::Scalar(Scalar::Uint(UintTy::U128)),
123 TyFingerprint::Scalar(Scalar::Uint(UintTy::Usize)),
126 pub(crate) const ALL_FLOAT_FPS: [TyFingerprint; 2] = [
127 TyFingerprint::Scalar(Scalar::Float(FloatTy::F32)),
128 TyFingerprint::Scalar(Scalar::Float(FloatTy::F64)),
131 /// Trait impls defined or available in some crate.
132 #[derive(Debug, Eq, PartialEq)]
133 pub struct TraitImpls {
134 // If the `Option<TyFingerprint>` is `None`, the impl may apply to any self type.
135 map: FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Vec<ImplId>>>,
139 pub(crate) fn trait_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
140 let _p = profile::span("trait_impls_in_crate_query").detail(|| format!("{krate:?}"));
141 let mut impls = Self { map: FxHashMap::default() };
143 let crate_def_map = db.crate_def_map(krate);
144 impls.collect_def_map(db, &crate_def_map);
145 impls.shrink_to_fit();
150 pub(crate) fn trait_impls_in_block_query(
151 db: &dyn HirDatabase,
153 ) -> Option<Arc<Self>> {
154 let _p = profile::span("trait_impls_in_block_query");
155 let mut impls = Self { map: FxHashMap::default() };
157 let block_def_map = db.block_def_map(block)?;
158 impls.collect_def_map(db, &block_def_map);
159 impls.shrink_to_fit();
161 Some(Arc::new(impls))
164 pub(crate) fn trait_impls_in_deps_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
165 let _p = profile::span("trait_impls_in_deps_query").detail(|| format!("{krate:?}"));
166 let crate_graph = db.crate_graph();
167 let mut res = Self { map: FxHashMap::default() };
169 for krate in crate_graph.transitive_deps(krate) {
170 res.merge(&db.trait_impls_in_crate(krate));
177 fn shrink_to_fit(&mut self) {
178 self.map.shrink_to_fit();
179 self.map.values_mut().for_each(|map| {
181 map.values_mut().for_each(Vec::shrink_to_fit);
185 fn collect_def_map(&mut self, db: &dyn HirDatabase, def_map: &DefMap) {
186 for (_module_id, module_data) in def_map.modules() {
187 for impl_id in module_data.scope.impls() {
188 let target_trait = match db.impl_trait(impl_id) {
189 Some(tr) => tr.skip_binders().hir_trait_id(),
192 let self_ty = db.impl_self_ty(impl_id);
193 let self_ty_fp = TyFingerprint::for_trait_impl(self_ty.skip_binders());
202 // To better support custom derives, collect impls in all unnamed const items.
203 // const _: () = { ... };
204 for konst in collect_unnamed_consts(db, &module_data.scope) {
205 let body = db.body(konst.into());
206 for (_, block_def_map) in body.blocks(db.upcast()) {
207 self.collect_def_map(db, &block_def_map);
213 fn merge(&mut self, other: &Self) {
214 for (trait_, other_map) in &other.map {
215 let map = self.map.entry(*trait_).or_default();
216 for (fp, impls) in other_map {
217 map.entry(*fp).or_default().extend(impls);
222 /// Queries all trait impls for the given type.
223 pub fn for_self_ty_without_blanket_impls(
226 ) -> impl Iterator<Item = ImplId> + '_ {
229 .flat_map(move |impls| impls.get(&Some(fp)).into_iter())
230 .flat_map(|it| it.iter().copied())
233 /// Queries all impls of the given trait.
234 pub fn for_trait(&self, trait_: TraitId) -> impl Iterator<Item = ImplId> + '_ {
238 .flat_map(|map| map.values().flat_map(|v| v.iter().copied()))
241 /// Queries all impls of `trait_` that may apply to `self_ty`.
242 pub fn for_trait_and_self_ty(
245 self_ty: TyFingerprint,
246 ) -> impl Iterator<Item = ImplId> + '_ {
250 .flat_map(move |map| map.get(&Some(self_ty)).into_iter().chain(map.get(&None)))
251 .flat_map(|v| v.iter().copied())
254 pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ {
255 self.map.values().flat_map(|map| map.values().flat_map(|v| v.iter().copied()))
259 /// Inherent impls defined in some crate.
261 /// Inherent impls can only be defined in the crate that also defines the self type of the impl
262 /// (note that some primitives are considered to be defined by both libcore and liballoc).
264 /// This makes inherent impl lookup easier than trait impl lookup since we only have to consider a
266 #[derive(Debug, Eq, PartialEq)]
267 pub struct InherentImpls {
268 map: FxHashMap<TyFingerprint, Vec<ImplId>>,
272 pub(crate) fn inherent_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
273 let mut impls = Self { map: FxHashMap::default() };
275 let crate_def_map = db.crate_def_map(krate);
276 impls.collect_def_map(db, &crate_def_map);
277 impls.shrink_to_fit();
282 pub(crate) fn inherent_impls_in_block_query(
283 db: &dyn HirDatabase,
285 ) -> Option<Arc<Self>> {
286 let mut impls = Self { map: FxHashMap::default() };
287 if let Some(block_def_map) = db.block_def_map(block) {
288 impls.collect_def_map(db, &block_def_map);
289 impls.shrink_to_fit();
290 return Some(Arc::new(impls));
295 fn shrink_to_fit(&mut self) {
296 self.map.values_mut().for_each(Vec::shrink_to_fit);
297 self.map.shrink_to_fit();
300 fn collect_def_map(&mut self, db: &dyn HirDatabase, def_map: &DefMap) {
301 for (_module_id, module_data) in def_map.modules() {
302 for impl_id in module_data.scope.impls() {
303 let data = db.impl_data(impl_id);
304 if data.target_trait.is_some() {
308 let self_ty = db.impl_self_ty(impl_id);
309 let fp = TyFingerprint::for_inherent_impl(self_ty.skip_binders());
310 if let Some(fp) = fp {
311 self.map.entry(fp).or_default().push(impl_id);
313 // `fp` should only be `None` in error cases (either erroneous code or incomplete name resolution)
316 // To better support custom derives, collect impls in all unnamed const items.
317 // const _: () = { ... };
318 for konst in collect_unnamed_consts(db, &module_data.scope) {
319 let body = db.body(konst.into());
320 for (_, block_def_map) in body.blocks(db.upcast()) {
321 self.collect_def_map(db, &block_def_map);
327 pub fn for_self_ty(&self, self_ty: &Ty) -> &[ImplId] {
328 match TyFingerprint::for_inherent_impl(self_ty) {
329 Some(fp) => self.map.get(&fp).map(|vec| vec.as_ref()).unwrap_or(&[]),
334 pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ {
335 self.map.values().flat_map(|v| v.iter().copied())
339 pub fn inherent_impl_crates_query(
340 db: &dyn HirDatabase,
343 ) -> ArrayVec<CrateId, 2> {
344 let _p = profile::span("inherent_impl_crates_query");
345 let mut res = ArrayVec::new();
346 let crate_graph = db.crate_graph();
348 for krate in crate_graph.transitive_deps(krate) {
350 // we don't currently look for or store more than two crates here,
351 // so don't needlessly look at more crates than necessary.
354 let impls = db.inherent_impls_in_crate(krate);
355 if impls.map.get(&fp).map_or(false, |v| !v.is_empty()) {
363 fn collect_unnamed_consts<'a>(
364 db: &'a dyn HirDatabase,
365 scope: &'a ItemScope,
366 ) -> impl Iterator<Item = ConstId> + 'a {
367 let unnamed_consts = scope.unnamed_consts();
369 // FIXME: Also treat consts named `_DERIVE_*` as unnamed, since synstructure generates those.
370 // Should be removed once synstructure stops doing that.
371 let synstructure_hack_consts = scope.values().filter_map(|(item, _)| match item {
372 ModuleDefId::ConstId(id) => {
373 let loc = id.lookup(db.upcast());
374 let item_tree = loc.id.item_tree(db.upcast());
375 if item_tree[loc.id.value]
378 .map_or(false, |n| n.to_smol_str().starts_with("_DERIVE_"))
388 unnamed_consts.chain(synstructure_hack_consts)
392 db: &dyn HirDatabase,
395 ) -> Option<ArrayVec<CrateId, 2>> {
396 let mod_to_crate_ids = |module: ModuleId| Some(iter::once(module.krate()).collect());
398 let fp = TyFingerprint::for_inherent_impl(ty);
400 match ty.kind(Interner) {
401 TyKind::Adt(AdtId(def_id), _) => mod_to_crate_ids(def_id.module(db.upcast())),
402 TyKind::Foreign(id) => {
403 mod_to_crate_ids(from_foreign_def_id(*id).lookup(db.upcast()).module(db.upcast()))
407 .and_then(|trait_| mod_to_crate_ids(GenericDefId::TraitId(trait_).module(db.upcast()))),
408 // for primitives, there may be impls in various places (core and alloc
409 // mostly). We just check the whole crate graph for crates with impls
410 // (cached behind a query).
415 | TyKind::Raw(..) => {
416 Some(db.inherent_impl_crates(cur_crate, fp.expect("fingerprint for primitive")))
422 /// Look up the method with the given name.
423 pub(crate) fn lookup_method(
425 db: &dyn HirDatabase,
426 env: Arc<TraitEnvironment>,
427 traits_in_scope: &FxHashSet<TraitId>,
428 visible_from_module: VisibleFromModule,
430 ) -> Option<(ReceiverAdjustments, FunctionId)> {
431 iterate_method_candidates(
438 LookupMode::MethodCall,
439 |adjustments, f| match f {
440 AssocItemId::FunctionId(f) => Some((adjustments, f)),
446 /// Whether we're looking up a dotted method call (like `v.len()`) or a path
447 /// (like `Vec::new`).
448 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
449 pub enum LookupMode {
450 /// Looking up a method call like `v.len()`: We only consider candidates
451 /// that have a `self` parameter, and do autoderef.
453 /// Looking up a path like `Vec::new` or `Vec::default`: We consider all
454 /// candidates including associated constants, but don't do autoderef.
458 #[derive(Clone, Copy)]
459 pub enum VisibleFromModule {
460 /// Filter for results that are visible from the given module
462 /// Include impls from the given block.
463 IncludeBlock(BlockId),
464 /// Do nothing special in regards visibility
468 impl From<Option<ModuleId>> for VisibleFromModule {
469 fn from(module: Option<ModuleId>) -> Self {
471 Some(module) => Self::Filter(module),
477 impl From<Option<BlockId>> for VisibleFromModule {
478 fn from(block: Option<BlockId>) -> Self {
480 Some(block) => Self::IncludeBlock(block),
486 #[derive(Debug, Clone, Default)]
487 pub struct ReceiverAdjustments {
488 autoref: Option<Mutability>,
493 impl ReceiverAdjustments {
494 pub(crate) fn apply(&self, table: &mut InferenceTable<'_>, ty: Ty) -> (Ty, Vec<Adjustment>) {
496 let mut adjust = Vec::new();
497 for _ in 0..self.autoderefs {
498 match autoderef::autoderef_step(table, ty.clone()) {
500 never!("autoderef not possible for {:?}", ty);
501 ty = TyKind::Error.intern(Interner);
504 Some((kind, new_ty)) => {
506 adjust.push(Adjustment {
507 kind: Adjust::Deref(match kind {
508 // FIXME should we know the mutability here?
509 AutoderefKind::Overloaded => Some(OverloadedDeref(Mutability::Not)),
510 AutoderefKind::Builtin => None,
517 if self.unsize_array {
518 ty = match ty.kind(Interner) {
519 TyKind::Array(inner, _) => TyKind::Slice(inner.clone()).intern(Interner),
521 never!("unsize_array with non-array {:?}", ty);
525 // FIXME this is kind of wrong since the unsize needs to happen to a pointer/reference
526 adjust.push(Adjustment {
527 kind: Adjust::Pointer(PointerCast::Unsize),
531 if let Some(m) = self.autoref {
532 ty = TyKind::Ref(m, static_lifetime(), ty).intern(Interner);
534 .push(Adjustment { kind: Adjust::Borrow(AutoBorrow::Ref(m)), target: ty.clone() });
539 fn with_autoref(&self, m: Mutability) -> ReceiverAdjustments {
540 Self { autoref: Some(m), ..*self }
544 // This would be nicer if it just returned an iterator, but that runs into
545 // lifetime problems, because we need to borrow temp `CrateImplDefs`.
546 // FIXME add a context type here?
547 pub(crate) fn iterate_method_candidates<T>(
549 db: &dyn HirDatabase,
550 env: Arc<TraitEnvironment>,
551 traits_in_scope: &FxHashSet<TraitId>,
552 visible_from_module: VisibleFromModule,
555 mut callback: impl FnMut(ReceiverAdjustments, AssocItemId) -> Option<T>,
558 iterate_method_candidates_dyn(
567 assert!(slot.is_none());
568 if let Some(it) = callback(adj, item) {
570 return ControlFlow::Break(());
572 ControlFlow::Continue(())
578 pub fn lookup_impl_method(
580 db: &dyn HirDatabase,
581 env: Arc<TraitEnvironment>,
584 ) -> Option<FunctionId> {
585 let self_ty_fp = TyFingerprint::for_trait_impl(self_ty)?;
586 let trait_impls = db.trait_impls_in_deps(env.krate);
587 let impls = trait_impls.for_trait_and_self_ty(trait_, self_ty_fp);
588 let mut table = InferenceTable::new(db, env.clone());
589 find_matching_impl(impls, &mut table, &self_ty).and_then(|data| {
590 data.items.iter().find_map(|it| match it {
591 AssocItemId::FunctionId(f) => (db.function_data(*f).name == *name).then(|| *f),
597 fn find_matching_impl(
598 mut impls: impl Iterator<Item = ImplId>,
599 table: &mut InferenceTable<'_>,
601 ) -> Option<Arc<ImplData>> {
604 let impl_ = impls.next()?;
605 let r = table.run_in_snapshot(|table| {
606 let impl_data = db.impl_data(impl_);
608 TyBuilder::subst_for_def(db, impl_).fill_with_inference_vars(table).build();
609 let impl_ty = db.impl_self_ty(impl_).substitute(Interner, &substs);
612 .unify(self_ty, &impl_ty)
615 crate::chalk_db::convert_where_clauses(db, impl_.into(), &substs)
617 .map(|b| b.cast(Interner));
619 let goal = crate::Goal::all(Interner, wh_goals);
621 table.try_obligation(goal).map(|_| impl_data)
631 pub fn iterate_path_candidates(
633 db: &dyn HirDatabase,
634 env: Arc<TraitEnvironment>,
635 traits_in_scope: &FxHashSet<TraitId>,
636 visible_from_module: VisibleFromModule,
638 callback: &mut dyn FnMut(AssocItemId) -> ControlFlow<()>,
639 ) -> ControlFlow<()> {
640 iterate_method_candidates_dyn(
648 // the adjustments are not relevant for path lookup
649 &mut |_, id| callback(id),
653 pub fn iterate_method_candidates_dyn(
655 db: &dyn HirDatabase,
656 env: Arc<TraitEnvironment>,
657 traits_in_scope: &FxHashSet<TraitId>,
658 visible_from_module: VisibleFromModule,
661 callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
662 ) -> ControlFlow<()> {
664 LookupMode::MethodCall => {
665 // For method calls, rust first does any number of autoderef, and
666 // then one autoref (i.e. when the method takes &self or &mut self).
667 // Note that when we've got a receiver like &S, even if the method
668 // we find in the end takes &self, we still do the autoderef step
669 // (just as rustc does an autoderef and then autoref again).
671 // We have to be careful about the order we're looking at candidates
672 // in here. Consider the case where we're resolving `x.clone()`
673 // where `x: &Vec<_>`. This resolves to the clone method with self
674 // type `Vec<_>`, *not* `&_`. I.e. we need to consider methods where
675 // the receiver type exactly matches before cases where we have to
676 // do autoref. But in the autoderef steps, the `&_` self type comes
677 // up *before* the `Vec<_>` self type.
679 // On the other hand, we don't want to just pick any by-value method
680 // before any by-autoref method; it's just that we need to consider
681 // the methods by autoderef order of *receiver types*, not *self
684 let mut table = InferenceTable::new(db, env.clone());
685 let ty = table.instantiate_canonical(ty.clone());
686 let (deref_chain, adj) = autoderef_method_receiver(&mut table, ty);
688 let result = deref_chain.into_iter().zip(adj).try_for_each(|(receiver_ty, adj)| {
689 iterate_method_candidates_with_autoref(
702 LookupMode::Path => {
703 // No autoderef for path lookups
704 iterate_method_candidates_for_self_ty(
717 fn iterate_method_candidates_with_autoref(
718 receiver_ty: &Canonical<Ty>,
719 first_adjustment: ReceiverAdjustments,
720 db: &dyn HirDatabase,
721 env: Arc<TraitEnvironment>,
722 traits_in_scope: &FxHashSet<TraitId>,
723 visible_from_module: VisibleFromModule,
725 mut callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
726 ) -> ControlFlow<()> {
727 if receiver_ty.value.is_general_var(Interner, &receiver_ty.binders) {
728 // don't try to resolve methods on unknown types
729 return ControlFlow::Continue(());
732 iterate_method_candidates_by_receiver(
734 first_adjustment.clone(),
743 let refed = Canonical {
744 value: TyKind::Ref(Mutability::Not, static_lifetime(), receiver_ty.value.clone())
746 binders: receiver_ty.binders.clone(),
749 iterate_method_candidates_by_receiver(
751 first_adjustment.with_autoref(Mutability::Not),
760 let ref_muted = Canonical {
761 value: TyKind::Ref(Mutability::Mut, static_lifetime(), receiver_ty.value.clone())
763 binders: receiver_ty.binders.clone(),
766 iterate_method_candidates_by_receiver(
768 first_adjustment.with_autoref(Mutability::Mut),
778 fn iterate_method_candidates_by_receiver(
779 receiver_ty: &Canonical<Ty>,
780 receiver_adjustments: ReceiverAdjustments,
781 db: &dyn HirDatabase,
782 env: Arc<TraitEnvironment>,
783 traits_in_scope: &FxHashSet<TraitId>,
784 visible_from_module: VisibleFromModule,
786 mut callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
787 ) -> ControlFlow<()> {
788 let mut table = InferenceTable::new(db, env);
789 let receiver_ty = table.instantiate_canonical(receiver_ty.clone());
790 let snapshot = table.snapshot();
791 // We're looking for methods with *receiver* type receiver_ty. These could
792 // be found in any of the derefs of receiver_ty, so we have to go through
794 let mut autoderef = autoderef::Autoderef::new(&mut table, receiver_ty.clone());
795 while let Some((self_ty, _)) = autoderef.next() {
796 iterate_inherent_methods(
798 &mut autoderef.table,
801 Some(receiver_adjustments.clone()),
807 table.rollback_to(snapshot);
809 let mut autoderef = autoderef::Autoderef::new(&mut table, receiver_ty.clone());
810 while let Some((self_ty, _)) = autoderef.next() {
811 iterate_trait_method_candidates(
813 &mut autoderef.table,
817 Some(receiver_adjustments.clone()),
822 ControlFlow::Continue(())
825 fn iterate_method_candidates_for_self_ty(
826 self_ty: &Canonical<Ty>,
827 db: &dyn HirDatabase,
828 env: Arc<TraitEnvironment>,
829 traits_in_scope: &FxHashSet<TraitId>,
830 visible_from_module: VisibleFromModule,
832 mut callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
833 ) -> ControlFlow<()> {
834 let mut table = InferenceTable::new(db, env);
835 let self_ty = table.instantiate_canonical(self_ty.clone());
836 iterate_inherent_methods(
845 iterate_trait_method_candidates(
856 fn iterate_trait_method_candidates(
858 table: &mut InferenceTable<'_>,
859 traits_in_scope: &FxHashSet<TraitId>,
861 receiver_ty: Option<&Ty>,
862 receiver_adjustments: Option<ReceiverAdjustments>,
863 callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
864 ) -> ControlFlow<()> {
866 let env = table.trait_env.clone();
867 let self_is_array = matches!(self_ty.kind(Interner), chalk_ir::TyKind::Array(..));
868 // if ty is `dyn Trait`, the trait doesn't need to be in scope
870 self_ty.dyn_trait().into_iter().flat_map(|t| all_super_traits(db.upcast(), t));
871 let env_traits = matches!(self_ty.kind(Interner), TyKind::Placeholder(_))
872 // if we have `T: Trait` in the param env, the trait doesn't need to be in scope
874 env.traits_in_scope_from_clauses(self_ty.clone())
875 .flat_map(|t| all_super_traits(db.upcast(), t))
879 let traits = inherent_trait.chain(env_traits).chain(traits_in_scope.iter().copied());
881 let canonical_self_ty = table.canonicalize(self_ty.clone()).value;
883 'traits: for t in traits {
884 let data = db.trait_data(t);
886 // Traits annotated with `#[rustc_skip_array_during_method_dispatch]` are skipped during
887 // method resolution, if the receiver is an array, and we're compiling for editions before
889 // This is to make `[a].into_iter()` not break code with the new `IntoIterator` impl for
891 if data.skip_array_during_method_dispatch && self_is_array {
892 // FIXME: this should really be using the edition of the method name's span, in case it
893 // comes from a macro
894 if db.crate_graph()[env.krate].edition < Edition::Edition2021 {
899 // we'll be lazy about checking whether the type implements the
900 // trait, but if we find out it doesn't, we'll skip the rest of the
902 let mut known_implemented = false;
903 for &(_, item) in data.items.iter() {
904 // Don't pass a `visible_from_module` down to `is_valid_candidate`,
905 // since only inherent methods should be included into visibility checking.
906 if !is_valid_candidate(table, name, receiver_ty, item, self_ty, None) {
909 if !known_implemented {
910 let goal = generic_implements_goal(db, env.clone(), t, &canonical_self_ty);
911 if db.trait_solve(env.krate, goal.cast(Interner)).is_none() {
915 known_implemented = true;
916 callback(receiver_adjustments.clone().unwrap_or_default(), item)?;
919 ControlFlow::Continue(())
922 fn iterate_inherent_methods(
924 table: &mut InferenceTable<'_>,
926 receiver_ty: Option<&Ty>,
927 receiver_adjustments: Option<ReceiverAdjustments>,
928 visible_from_module: VisibleFromModule,
929 callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
930 ) -> ControlFlow<()> {
932 let env = table.trait_env.clone();
933 let def_crates = match def_crates(db, self_ty, env.krate) {
935 None => return ControlFlow::Continue(()),
938 let (module, block) = match visible_from_module {
939 VisibleFromModule::Filter(module) => (Some(module), module.containing_block()),
940 VisibleFromModule::IncludeBlock(block) => (None, Some(block)),
941 VisibleFromModule::None => (None, None),
944 if let Some(block_id) = block {
945 if let Some(impls) = db.inherent_impls_in_block(block_id) {
952 receiver_adjustments.clone(),
959 for krate in def_crates {
960 let impls = db.inherent_impls_in_crate(krate);
967 receiver_adjustments.clone(),
972 return ControlFlow::Continue(());
974 fn impls_for_self_ty(
975 impls: &InherentImpls,
977 table: &mut InferenceTable<'_>,
979 receiver_ty: Option<&Ty>,
980 receiver_adjustments: Option<ReceiverAdjustments>,
981 visible_from_module: Option<ModuleId>,
982 callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
983 ) -> ControlFlow<()> {
985 let impls_for_self_ty = impls.for_self_ty(self_ty);
986 for &impl_def in impls_for_self_ty {
987 for &item in &db.impl_data(impl_def).items {
988 if !is_valid_candidate(table, name, receiver_ty, item, self_ty, visible_from_module)
992 callback(receiver_adjustments.clone().unwrap_or_default(), item)?;
995 ControlFlow::Continue(())
999 /// Returns the receiver type for the index trait call.
1000 pub fn resolve_indexing_op(
1001 db: &dyn HirDatabase,
1002 env: Arc<TraitEnvironment>,
1004 index_trait: TraitId,
1005 ) -> Option<ReceiverAdjustments> {
1006 let mut table = InferenceTable::new(db, env.clone());
1007 let ty = table.instantiate_canonical(ty);
1008 let (deref_chain, adj) = autoderef_method_receiver(&mut table, ty);
1009 for (ty, adj) in deref_chain.into_iter().zip(adj) {
1010 let goal = generic_implements_goal(db, env.clone(), index_trait, &ty);
1011 if db.trait_solve(env.krate, goal.cast(Interner)).is_some() {
1018 fn is_valid_candidate(
1019 table: &mut InferenceTable<'_>,
1020 name: Option<&Name>,
1021 receiver_ty: Option<&Ty>,
1024 visible_from_module: Option<ModuleId>,
1026 macro_rules! check_that {
1036 AssocItemId::FunctionId(m) => {
1037 let data = db.function_data(m);
1039 check_that!(name.map_or(true, |n| n == &data.name));
1040 check_that!(visible_from_module.map_or(true, |from_module| {
1041 let v = db.function_visibility(m).is_visible_from(db.upcast(), from_module);
1043 cov_mark::hit!(autoderef_candidate_not_visible);
1048 table.run_in_snapshot(|table| {
1049 let subst = TyBuilder::subst_for_def(db, m).fill_with_inference_vars(table).build();
1050 let expect_self_ty = match m.lookup(db.upcast()).container {
1051 ItemContainerId::TraitId(_) => {
1052 subst.at(Interner, 0).assert_ty_ref(Interner).clone()
1054 ItemContainerId::ImplId(impl_id) => {
1055 subst.apply(db.impl_self_ty(impl_id).skip_binders().clone(), Interner)
1057 // We should only get called for associated items (impl/trait)
1058 ItemContainerId::ModuleId(_) | ItemContainerId::ExternBlockId(_) => {
1062 check_that!(table.unify(&expect_self_ty, self_ty));
1063 if let Some(receiver_ty) = receiver_ty {
1064 check_that!(data.has_self_param());
1066 let sig = db.callable_item_signature(m.into());
1067 let expected_receiver =
1068 sig.map(|s| s.params()[0].clone()).substitute(Interner, &subst);
1070 check_that!(table.unify(&receiver_ty, &expected_receiver));
1075 AssocItemId::ConstId(c) => {
1076 let data = db.const_data(c);
1077 check_that!(receiver_ty.is_none());
1079 check_that!(name.map_or(true, |n| data.name.as_ref() == Some(n)));
1080 check_that!(visible_from_module.map_or(true, |from_module| {
1081 let v = db.const_visibility(c).is_visible_from(db.upcast(), from_module);
1083 cov_mark::hit!(const_candidate_not_visible);
1087 if let ItemContainerId::ImplId(impl_id) = c.lookup(db.upcast()).container {
1088 let self_ty_matches = table.run_in_snapshot(|table| {
1090 TyBuilder::subst_for_def(db, c).fill_with_inference_vars(table).build();
1091 let expected_self_ty =
1092 subst.apply(db.impl_self_ty(impl_id).skip_binders().clone(), Interner);
1093 table.unify(&expected_self_ty, &self_ty)
1095 if !self_ty_matches {
1096 cov_mark::hit!(const_candidate_self_type_mismatch);
1106 pub fn implements_trait(
1108 db: &dyn HirDatabase,
1109 env: Arc<TraitEnvironment>,
1112 let goal = generic_implements_goal(db, env.clone(), trait_, ty);
1113 let solution = db.trait_solve(env.krate, goal.cast(Interner));
1118 pub fn implements_trait_unique(
1120 db: &dyn HirDatabase,
1121 env: Arc<TraitEnvironment>,
1124 let goal = generic_implements_goal(db, env.clone(), trait_, ty);
1125 let solution = db.trait_solve(env.krate, goal.cast(Interner));
1127 matches!(solution, Some(crate::Solution::Unique(_)))
1130 /// This creates Substs for a trait with the given Self type and type variables
1131 /// for all other parameters, to query Chalk with it.
1132 fn generic_implements_goal(
1133 db: &dyn HirDatabase,
1134 env: Arc<TraitEnvironment>,
1136 self_ty: &Canonical<Ty>,
1137 ) -> Canonical<InEnvironment<super::DomainGoal>> {
1138 let mut kinds = self_ty.binders.interned().to_vec();
1139 let trait_ref = TyBuilder::trait_ref(db, trait_)
1140 .push(self_ty.value.clone())
1141 .fill_with_bound_vars(DebruijnIndex::INNERMOST, kinds.len())
1143 kinds.extend(trait_ref.substitution.iter(Interner).skip(1).map(|x| {
1144 let vk = match x.data(Interner) {
1145 chalk_ir::GenericArgData::Ty(_) => {
1146 chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General)
1148 chalk_ir::GenericArgData::Lifetime(_) => chalk_ir::VariableKind::Lifetime,
1149 chalk_ir::GenericArgData::Const(c) => {
1150 chalk_ir::VariableKind::Const(c.data(Interner).ty.clone())
1153 chalk_ir::WithKind::new(vk, UniverseIndex::ROOT)
1155 let obligation = trait_ref.cast(Interner);
1157 binders: CanonicalVarKinds::from_iter(Interner, kinds),
1158 value: InEnvironment::new(&env.env, obligation),
1162 fn autoderef_method_receiver(
1163 table: &mut InferenceTable<'_>,
1165 ) -> (Vec<Canonical<Ty>>, Vec<ReceiverAdjustments>) {
1166 let (mut deref_chain, mut adjustments): (Vec<_>, Vec<_>) = (Vec::new(), Vec::new());
1167 let mut autoderef = autoderef::Autoderef::new(table, ty);
1168 while let Some((ty, derefs)) = autoderef.next() {
1169 deref_chain.push(autoderef.table.canonicalize(ty).value);
1170 adjustments.push(ReceiverAdjustments {
1173 unsize_array: false,
1176 // As a last step, we can do array unsizing (that's the only unsizing that rustc does for method receivers!)
1177 if let (Some((TyKind::Array(parameters, _), binders)), Some(adj)) = (
1178 deref_chain.last().map(|ty| (ty.value.kind(Interner), ty.binders.clone())),
1179 adjustments.last().cloned(),
1181 let unsized_ty = TyKind::Slice(parameters.clone()).intern(Interner);
1182 deref_chain.push(Canonical { value: unsized_ty, binders });
1183 adjustments.push(ReceiverAdjustments { unsize_array: true, ..adj });
1185 (deref_chain, adjustments)