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(crate) 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 pub fn lang_names_for_bin_op(op: syntax::ast::BinaryOp) -> Option<(Name, Name)> {
423 use hir_expand::name;
424 use syntax::ast::{ArithOp, BinaryOp, CmpOp, Ordering};
426 BinaryOp::LogicOp(_) => return None,
427 BinaryOp::ArithOp(aop) => match aop {
428 ArithOp::Add => (name!(add), name!(add)),
429 ArithOp::Mul => (name!(mul), name!(mul)),
430 ArithOp::Sub => (name!(sub), name!(sub)),
431 ArithOp::Div => (name!(div), name!(div)),
432 ArithOp::Rem => (name!(rem), name!(rem)),
433 ArithOp::Shl => (name!(shl), name!(shl)),
434 ArithOp::Shr => (name!(shr), name!(shr)),
435 ArithOp::BitXor => (name!(bitxor), name!(bitxor)),
436 ArithOp::BitOr => (name!(bitor), name!(bitor)),
437 ArithOp::BitAnd => (name!(bitand), name!(bitand)),
439 BinaryOp::Assignment { op: Some(aop) } => match aop {
440 ArithOp::Add => (name!(add_assign), name!(add_assign)),
441 ArithOp::Mul => (name!(mul_assign), name!(mul_assign)),
442 ArithOp::Sub => (name!(sub_assign), name!(sub_assign)),
443 ArithOp::Div => (name!(div_assign), name!(div_assign)),
444 ArithOp::Rem => (name!(rem_assign), name!(rem_assign)),
445 ArithOp::Shl => (name!(shl_assign), name!(shl_assign)),
446 ArithOp::Shr => (name!(shr_assign), name!(shr_assign)),
447 ArithOp::BitXor => (name!(bitxor_assign), name!(bitxor_assign)),
448 ArithOp::BitOr => (name!(bitor_assign), name!(bitor_assign)),
449 ArithOp::BitAnd => (name!(bitand_assign), name!(bitand_assign)),
451 BinaryOp::CmpOp(cop) => match cop {
452 CmpOp::Eq { negated: false } => (name!(eq), name!(eq)),
453 CmpOp::Eq { negated: true } => (name!(ne), name!(eq)),
454 CmpOp::Ord { ordering: Ordering::Less, strict: false } => {
455 (name!(le), name!(partial_ord))
457 CmpOp::Ord { ordering: Ordering::Less, strict: true } => {
458 (name!(lt), name!(partial_ord))
460 CmpOp::Ord { ordering: Ordering::Greater, strict: false } => {
461 (name!(ge), name!(partial_ord))
463 CmpOp::Ord { ordering: Ordering::Greater, strict: true } => {
464 (name!(gt), name!(partial_ord))
467 BinaryOp::Assignment { op: None } => return None,
471 /// Look up the method with the given name.
472 pub(crate) fn lookup_method(
474 db: &dyn HirDatabase,
475 env: Arc<TraitEnvironment>,
476 traits_in_scope: &FxHashSet<TraitId>,
477 visible_from_module: VisibleFromModule,
479 ) -> Option<(ReceiverAdjustments, FunctionId)> {
480 iterate_method_candidates(
487 LookupMode::MethodCall,
488 |adjustments, f| match f {
489 AssocItemId::FunctionId(f) => Some((adjustments, f)),
495 /// Whether we're looking up a dotted method call (like `v.len()`) or a path
496 /// (like `Vec::new`).
497 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
498 pub enum LookupMode {
499 /// Looking up a method call like `v.len()`: We only consider candidates
500 /// that have a `self` parameter, and do autoderef.
502 /// Looking up a path like `Vec::new` or `Vec::default`: We consider all
503 /// candidates including associated constants, but don't do autoderef.
507 #[derive(Clone, Copy)]
508 pub enum VisibleFromModule {
509 /// Filter for results that are visible from the given module
511 /// Include impls from the given block.
512 IncludeBlock(BlockId),
513 /// Do nothing special in regards visibility
517 impl From<Option<ModuleId>> for VisibleFromModule {
518 fn from(module: Option<ModuleId>) -> Self {
520 Some(module) => Self::Filter(module),
526 impl From<Option<BlockId>> for VisibleFromModule {
527 fn from(block: Option<BlockId>) -> Self {
529 Some(block) => Self::IncludeBlock(block),
535 #[derive(Debug, Clone, Default)]
536 pub struct ReceiverAdjustments {
537 autoref: Option<Mutability>,
542 impl ReceiverAdjustments {
543 pub(crate) fn apply(&self, table: &mut InferenceTable<'_>, ty: Ty) -> (Ty, Vec<Adjustment>) {
545 let mut adjust = Vec::new();
546 for _ in 0..self.autoderefs {
547 match autoderef::autoderef_step(table, ty.clone()) {
549 never!("autoderef not possible for {:?}", ty);
550 ty = TyKind::Error.intern(Interner);
553 Some((kind, new_ty)) => {
555 adjust.push(Adjustment {
556 kind: Adjust::Deref(match kind {
557 // FIXME should we know the mutability here?
558 AutoderefKind::Overloaded => Some(OverloadedDeref(Mutability::Not)),
559 AutoderefKind::Builtin => None,
566 if self.unsize_array {
567 ty = match ty.kind(Interner) {
568 TyKind::Array(inner, _) => TyKind::Slice(inner.clone()).intern(Interner),
570 never!("unsize_array with non-array {:?}", ty);
574 // FIXME this is kind of wrong since the unsize needs to happen to a pointer/reference
575 adjust.push(Adjustment {
576 kind: Adjust::Pointer(PointerCast::Unsize),
580 if let Some(m) = self.autoref {
581 ty = TyKind::Ref(m, static_lifetime(), ty).intern(Interner);
583 .push(Adjustment { kind: Adjust::Borrow(AutoBorrow::Ref(m)), target: ty.clone() });
588 fn with_autoref(&self, m: Mutability) -> ReceiverAdjustments {
589 Self { autoref: Some(m), ..*self }
593 // This would be nicer if it just returned an iterator, but that runs into
594 // lifetime problems, because we need to borrow temp `CrateImplDefs`.
595 // FIXME add a context type here?
596 pub(crate) fn iterate_method_candidates<T>(
598 db: &dyn HirDatabase,
599 env: Arc<TraitEnvironment>,
600 traits_in_scope: &FxHashSet<TraitId>,
601 visible_from_module: VisibleFromModule,
604 mut callback: impl FnMut(ReceiverAdjustments, AssocItemId) -> Option<T>,
607 iterate_method_candidates_dyn(
616 assert!(slot.is_none());
617 if let Some(it) = callback(adj, item) {
619 return ControlFlow::Break(());
621 ControlFlow::Continue(())
627 pub fn lookup_impl_method(
629 db: &dyn HirDatabase,
630 env: Arc<TraitEnvironment>,
633 ) -> Option<FunctionId> {
634 let self_ty_fp = TyFingerprint::for_trait_impl(self_ty)?;
635 let trait_impls = db.trait_impls_in_deps(env.krate);
636 let impls = trait_impls.for_trait_and_self_ty(trait_, self_ty_fp);
637 let mut table = InferenceTable::new(db, env.clone());
638 find_matching_impl(impls, &mut table, &self_ty).and_then(|data| {
639 data.items.iter().find_map(|it| match it {
640 AssocItemId::FunctionId(f) => (db.function_data(*f).name == *name).then(|| *f),
646 fn find_matching_impl(
647 mut impls: impl Iterator<Item = ImplId>,
648 table: &mut InferenceTable<'_>,
650 ) -> Option<Arc<ImplData>> {
653 let impl_ = impls.next()?;
654 let r = table.run_in_snapshot(|table| {
655 let impl_data = db.impl_data(impl_);
657 TyBuilder::subst_for_def(db, impl_).fill_with_inference_vars(table).build();
658 let impl_ty = db.impl_self_ty(impl_).substitute(Interner, &substs);
661 .unify(self_ty, &impl_ty)
664 crate::chalk_db::convert_where_clauses(db, impl_.into(), &substs)
666 .map(|b| b.cast(Interner));
668 let goal = crate::Goal::all(Interner, wh_goals);
670 table.try_obligation(goal).map(|_| impl_data)
680 pub fn iterate_path_candidates(
682 db: &dyn HirDatabase,
683 env: Arc<TraitEnvironment>,
684 traits_in_scope: &FxHashSet<TraitId>,
685 visible_from_module: VisibleFromModule,
687 callback: &mut dyn FnMut(AssocItemId) -> ControlFlow<()>,
688 ) -> ControlFlow<()> {
689 iterate_method_candidates_dyn(
697 // the adjustments are not relevant for path lookup
698 &mut |_, id| callback(id),
702 pub fn iterate_method_candidates_dyn(
704 db: &dyn HirDatabase,
705 env: Arc<TraitEnvironment>,
706 traits_in_scope: &FxHashSet<TraitId>,
707 visible_from_module: VisibleFromModule,
710 callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
711 ) -> ControlFlow<()> {
713 LookupMode::MethodCall => {
714 // For method calls, rust first does any number of autoderef, and
715 // then one autoref (i.e. when the method takes &self or &mut self).
716 // Note that when we've got a receiver like &S, even if the method
717 // we find in the end takes &self, we still do the autoderef step
718 // (just as rustc does an autoderef and then autoref again).
720 // We have to be careful about the order we're looking at candidates
721 // in here. Consider the case where we're resolving `x.clone()`
722 // where `x: &Vec<_>`. This resolves to the clone method with self
723 // type `Vec<_>`, *not* `&_`. I.e. we need to consider methods where
724 // the receiver type exactly matches before cases where we have to
725 // do autoref. But in the autoderef steps, the `&_` self type comes
726 // up *before* the `Vec<_>` self type.
728 // On the other hand, we don't want to just pick any by-value method
729 // before any by-autoref method; it's just that we need to consider
730 // the methods by autoderef order of *receiver types*, not *self
733 let mut table = InferenceTable::new(db, env.clone());
734 let ty = table.instantiate_canonical(ty.clone());
735 let (deref_chain, adj) = autoderef_method_receiver(&mut table, ty);
737 let result = deref_chain.into_iter().zip(adj).try_for_each(|(receiver_ty, adj)| {
738 iterate_method_candidates_with_autoref(
751 LookupMode::Path => {
752 // No autoderef for path lookups
753 iterate_method_candidates_for_self_ty(
766 fn iterate_method_candidates_with_autoref(
767 receiver_ty: &Canonical<Ty>,
768 first_adjustment: ReceiverAdjustments,
769 db: &dyn HirDatabase,
770 env: Arc<TraitEnvironment>,
771 traits_in_scope: &FxHashSet<TraitId>,
772 visible_from_module: VisibleFromModule,
774 mut callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
775 ) -> ControlFlow<()> {
776 if receiver_ty.value.is_general_var(Interner, &receiver_ty.binders) {
777 // don't try to resolve methods on unknown types
778 return ControlFlow::Continue(());
781 iterate_method_candidates_by_receiver(
783 first_adjustment.clone(),
792 let refed = Canonical {
793 value: TyKind::Ref(Mutability::Not, static_lifetime(), receiver_ty.value.clone())
795 binders: receiver_ty.binders.clone(),
798 iterate_method_candidates_by_receiver(
800 first_adjustment.with_autoref(Mutability::Not),
809 let ref_muted = Canonical {
810 value: TyKind::Ref(Mutability::Mut, static_lifetime(), receiver_ty.value.clone())
812 binders: receiver_ty.binders.clone(),
815 iterate_method_candidates_by_receiver(
817 first_adjustment.with_autoref(Mutability::Mut),
827 fn iterate_method_candidates_by_receiver(
828 receiver_ty: &Canonical<Ty>,
829 receiver_adjustments: ReceiverAdjustments,
830 db: &dyn HirDatabase,
831 env: Arc<TraitEnvironment>,
832 traits_in_scope: &FxHashSet<TraitId>,
833 visible_from_module: VisibleFromModule,
835 mut callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
836 ) -> ControlFlow<()> {
837 let mut table = InferenceTable::new(db, env);
838 let receiver_ty = table.instantiate_canonical(receiver_ty.clone());
839 let snapshot = table.snapshot();
840 // We're looking for methods with *receiver* type receiver_ty. These could
841 // be found in any of the derefs of receiver_ty, so we have to go through
843 let mut autoderef = autoderef::Autoderef::new(&mut table, receiver_ty.clone());
844 while let Some((self_ty, _)) = autoderef.next() {
845 iterate_inherent_methods(
847 &mut autoderef.table,
850 Some(receiver_adjustments.clone()),
856 table.rollback_to(snapshot);
858 let mut autoderef = autoderef::Autoderef::new(&mut table, receiver_ty.clone());
859 while let Some((self_ty, _)) = autoderef.next() {
860 iterate_trait_method_candidates(
862 &mut autoderef.table,
866 Some(receiver_adjustments.clone()),
871 ControlFlow::Continue(())
874 fn iterate_method_candidates_for_self_ty(
875 self_ty: &Canonical<Ty>,
876 db: &dyn HirDatabase,
877 env: Arc<TraitEnvironment>,
878 traits_in_scope: &FxHashSet<TraitId>,
879 visible_from_module: VisibleFromModule,
881 mut callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
882 ) -> ControlFlow<()> {
883 let mut table = InferenceTable::new(db, env);
884 let self_ty = table.instantiate_canonical(self_ty.clone());
885 iterate_inherent_methods(
894 iterate_trait_method_candidates(
905 fn iterate_trait_method_candidates(
907 table: &mut InferenceTable<'_>,
908 traits_in_scope: &FxHashSet<TraitId>,
910 receiver_ty: Option<&Ty>,
911 receiver_adjustments: Option<ReceiverAdjustments>,
912 callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
913 ) -> ControlFlow<()> {
915 let env = table.trait_env.clone();
916 let self_is_array = matches!(self_ty.kind(Interner), chalk_ir::TyKind::Array(..));
917 // if ty is `dyn Trait`, the trait doesn't need to be in scope
919 self_ty.dyn_trait().into_iter().flat_map(|t| all_super_traits(db.upcast(), t));
920 let env_traits = matches!(self_ty.kind(Interner), TyKind::Placeholder(_))
921 // if we have `T: Trait` in the param env, the trait doesn't need to be in scope
923 env.traits_in_scope_from_clauses(self_ty.clone())
924 .flat_map(|t| all_super_traits(db.upcast(), t))
928 let traits = inherent_trait.chain(env_traits).chain(traits_in_scope.iter().copied());
930 let canonical_self_ty = table.canonicalize(self_ty.clone()).value;
932 'traits: for t in traits {
933 let data = db.trait_data(t);
935 // Traits annotated with `#[rustc_skip_array_during_method_dispatch]` are skipped during
936 // method resolution, if the receiver is an array, and we're compiling for editions before
938 // This is to make `[a].into_iter()` not break code with the new `IntoIterator` impl for
940 if data.skip_array_during_method_dispatch && self_is_array {
941 // FIXME: this should really be using the edition of the method name's span, in case it
942 // comes from a macro
943 if db.crate_graph()[env.krate].edition < Edition::Edition2021 {
948 // we'll be lazy about checking whether the type implements the
949 // trait, but if we find out it doesn't, we'll skip the rest of the
951 let mut known_implemented = false;
952 for &(_, item) in data.items.iter() {
953 // Don't pass a `visible_from_module` down to `is_valid_candidate`,
954 // since only inherent methods should be included into visibility checking.
955 if !is_valid_candidate(table, name, receiver_ty, item, self_ty, None) {
958 if !known_implemented {
959 let goal = generic_implements_goal(db, env.clone(), t, &canonical_self_ty);
960 if db.trait_solve(env.krate, goal.cast(Interner)).is_none() {
964 known_implemented = true;
965 callback(receiver_adjustments.clone().unwrap_or_default(), item)?;
968 ControlFlow::Continue(())
971 fn iterate_inherent_methods(
973 table: &mut InferenceTable<'_>,
975 receiver_ty: Option<&Ty>,
976 receiver_adjustments: Option<ReceiverAdjustments>,
977 visible_from_module: VisibleFromModule,
978 callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
979 ) -> ControlFlow<()> {
981 let env = table.trait_env.clone();
982 let def_crates = match def_crates(db, self_ty, env.krate) {
984 None => return ControlFlow::Continue(()),
987 let (module, block) = match visible_from_module {
988 VisibleFromModule::Filter(module) => (Some(module), module.containing_block()),
989 VisibleFromModule::IncludeBlock(block) => (None, Some(block)),
990 VisibleFromModule::None => (None, None),
993 if let Some(block_id) = block {
994 if let Some(impls) = db.inherent_impls_in_block(block_id) {
1001 receiver_adjustments.clone(),
1008 for krate in def_crates {
1009 let impls = db.inherent_impls_in_crate(krate);
1016 receiver_adjustments.clone(),
1021 return ControlFlow::Continue(());
1023 fn impls_for_self_ty(
1024 impls: &InherentImpls,
1026 table: &mut InferenceTable<'_>,
1027 name: Option<&Name>,
1028 receiver_ty: Option<&Ty>,
1029 receiver_adjustments: Option<ReceiverAdjustments>,
1030 visible_from_module: Option<ModuleId>,
1031 callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
1032 ) -> ControlFlow<()> {
1034 let impls_for_self_ty = impls.for_self_ty(self_ty);
1035 for &impl_def in impls_for_self_ty {
1036 for &item in &db.impl_data(impl_def).items {
1037 if !is_valid_candidate(table, name, receiver_ty, item, self_ty, visible_from_module)
1041 callback(receiver_adjustments.clone().unwrap_or_default(), item)?;
1044 ControlFlow::Continue(())
1048 /// Returns the receiver type for the index trait call.
1049 pub fn resolve_indexing_op(
1050 db: &dyn HirDatabase,
1051 env: Arc<TraitEnvironment>,
1053 index_trait: TraitId,
1054 ) -> Option<ReceiverAdjustments> {
1055 let mut table = InferenceTable::new(db, env.clone());
1056 let ty = table.instantiate_canonical(ty);
1057 let (deref_chain, adj) = autoderef_method_receiver(&mut table, ty);
1058 for (ty, adj) in deref_chain.into_iter().zip(adj) {
1059 let goal = generic_implements_goal(db, env.clone(), index_trait, &ty);
1060 if db.trait_solve(env.krate, goal.cast(Interner)).is_some() {
1067 fn is_valid_candidate(
1068 table: &mut InferenceTable<'_>,
1069 name: Option<&Name>,
1070 receiver_ty: Option<&Ty>,
1073 visible_from_module: Option<ModuleId>,
1075 macro_rules! check_that {
1085 AssocItemId::FunctionId(m) => {
1086 let data = db.function_data(m);
1088 check_that!(name.map_or(true, |n| n == &data.name));
1089 check_that!(visible_from_module.map_or(true, |from_module| {
1090 let v = db.function_visibility(m).is_visible_from(db.upcast(), from_module);
1092 cov_mark::hit!(autoderef_candidate_not_visible);
1097 table.run_in_snapshot(|table| {
1098 let subst = TyBuilder::subst_for_def(db, m).fill_with_inference_vars(table).build();
1099 let expect_self_ty = match m.lookup(db.upcast()).container {
1100 ItemContainerId::TraitId(_) => {
1101 subst.at(Interner, 0).assert_ty_ref(Interner).clone()
1103 ItemContainerId::ImplId(impl_id) => {
1104 subst.apply(db.impl_self_ty(impl_id).skip_binders().clone(), Interner)
1106 // We should only get called for associated items (impl/trait)
1107 ItemContainerId::ModuleId(_) | ItemContainerId::ExternBlockId(_) => {
1111 check_that!(table.unify(&expect_self_ty, self_ty));
1112 if let Some(receiver_ty) = receiver_ty {
1113 check_that!(data.has_self_param());
1115 let sig = db.callable_item_signature(m.into());
1116 let expected_receiver =
1117 sig.map(|s| s.params()[0].clone()).substitute(Interner, &subst);
1119 check_that!(table.unify(&receiver_ty, &expected_receiver));
1124 AssocItemId::ConstId(c) => {
1125 let data = db.const_data(c);
1126 check_that!(receiver_ty.is_none());
1128 check_that!(name.map_or(true, |n| data.name.as_ref() == Some(n)));
1129 check_that!(visible_from_module.map_or(true, |from_module| {
1130 let v = db.const_visibility(c).is_visible_from(db.upcast(), from_module);
1132 cov_mark::hit!(const_candidate_not_visible);
1136 if let ItemContainerId::ImplId(impl_id) = c.lookup(db.upcast()).container {
1137 let self_ty_matches = table.run_in_snapshot(|table| {
1139 TyBuilder::subst_for_def(db, c).fill_with_inference_vars(table).build();
1140 let expected_self_ty =
1141 subst.apply(db.impl_self_ty(impl_id).skip_binders().clone(), Interner);
1142 table.unify(&expected_self_ty, &self_ty)
1144 if !self_ty_matches {
1145 cov_mark::hit!(const_candidate_self_type_mismatch);
1155 pub fn implements_trait(
1157 db: &dyn HirDatabase,
1158 env: Arc<TraitEnvironment>,
1161 let goal = generic_implements_goal(db, env.clone(), trait_, ty);
1162 let solution = db.trait_solve(env.krate, goal.cast(Interner));
1167 pub fn implements_trait_unique(
1169 db: &dyn HirDatabase,
1170 env: Arc<TraitEnvironment>,
1173 let goal = generic_implements_goal(db, env.clone(), trait_, ty);
1174 let solution = db.trait_solve(env.krate, goal.cast(Interner));
1176 matches!(solution, Some(crate::Solution::Unique(_)))
1179 /// This creates Substs for a trait with the given Self type and type variables
1180 /// for all other parameters, to query Chalk with it.
1181 fn generic_implements_goal(
1182 db: &dyn HirDatabase,
1183 env: Arc<TraitEnvironment>,
1185 self_ty: &Canonical<Ty>,
1186 ) -> Canonical<InEnvironment<super::DomainGoal>> {
1187 let mut kinds = self_ty.binders.interned().to_vec();
1188 let trait_ref = TyBuilder::trait_ref(db, trait_)
1189 .push(self_ty.value.clone())
1190 .fill_with_bound_vars(DebruijnIndex::INNERMOST, kinds.len())
1192 kinds.extend(trait_ref.substitution.iter(Interner).skip(1).map(|x| {
1193 let vk = match x.data(Interner) {
1194 chalk_ir::GenericArgData::Ty(_) => {
1195 chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General)
1197 chalk_ir::GenericArgData::Lifetime(_) => chalk_ir::VariableKind::Lifetime,
1198 chalk_ir::GenericArgData::Const(c) => {
1199 chalk_ir::VariableKind::Const(c.data(Interner).ty.clone())
1202 chalk_ir::WithKind::new(vk, UniverseIndex::ROOT)
1204 let obligation = trait_ref.cast(Interner);
1206 binders: CanonicalVarKinds::from_iter(Interner, kinds),
1207 value: InEnvironment::new(&env.env, obligation),
1211 fn autoderef_method_receiver(
1212 table: &mut InferenceTable<'_>,
1214 ) -> (Vec<Canonical<Ty>>, Vec<ReceiverAdjustments>) {
1215 let (mut deref_chain, mut adjustments): (Vec<_>, Vec<_>) = (Vec::new(), Vec::new());
1216 let mut autoderef = autoderef::Autoderef::new(table, ty);
1217 while let Some((ty, derefs)) = autoderef.next() {
1218 deref_chain.push(autoderef.table.canonicalize(ty).value);
1219 adjustments.push(ReceiverAdjustments {
1222 unsize_array: false,
1225 // As a last step, we can do array unsizing (that's the only unsizing that rustc does for method receivers!)
1226 if let (Some((TyKind::Array(parameters, _), binders)), Some(adj)) = (
1227 deref_chain.last().map(|ty| (ty.value.kind(Interner), ty.binders.clone())),
1228 adjustments.last().cloned(),
1230 let unsized_ty = TyKind::Slice(parameters.clone()).intern(Interner);
1231 deref_chain.push(Canonical { value: unsized_ty, binders });
1232 adjustments.push(ReceiverAdjustments { unsize_array: true, ..adj });
1234 (deref_chain, adjustments)