src/tools/rust-analyzer/crates/hir-ty/src/method_resolution.rs

   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};
   6
   7 use arrayvec::ArrayVec;
   8 use base_db::{CrateId, Edition};
   9 use chalk_ir::{cast::Cast, Mutability, UniverseIndex};
  10 use hir_def::{
  11     data::ImplData, item_scope::ItemScope, nameres::DefMap, AssocItemId, BlockId, ConstId,
  12     FunctionId, GenericDefId, HasModule, ImplId, ItemContainerId, Lookup, ModuleDefId, ModuleId,
  13     TraitId,
  14 };
  15 use hir_expand::name::Name;
  16 use rustc_hash::{FxHashMap, FxHashSet};
  17 use stdx::never;
  18
  19 use crate::{
  20     autoderef::{self, AutoderefKind},
  21     db::HirDatabase,
  22     from_foreign_def_id,
  23     infer::{unify::InferenceTable, Adjust, Adjustment, AutoBorrow, OverloadedDeref, PointerCast},
  24     primitive::{FloatTy, IntTy, UintTy},
  25     static_lifetime,
  26     utils::all_super_traits,
  27     AdtId, Canonical, CanonicalVarKinds, DebruijnIndex, ForeignDefId, InEnvironment, Interner,
  28     Scalar, TraitEnvironment, TraitRefExt, Ty, TyBuilder, TyExt, TyKind,
  29 };
  30
  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:
  35     Str,
  36     Slice,
  37     Array,
  38     Never,
  39     RawPtr(Mutability),
  40     Scalar(Scalar),
  41     // These can have user-defined impls:
  42     Adt(hir_def::AdtId),
  43     Dyn(TraitId),
  44     ForeignType(ForeignDefId),
  45     // These only exist for trait impls
  46     Unit,
  47     Unnameable,
  48     Function(u32),
  49 }
  50
  51 impl TyFingerprint {
  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)?,
  67             _ => return None,
  68         };
  69         Some(fp)
  70     }
  71
  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));
  87                 match first_ty {
  88                     Some(ty) => return TyFingerprint::for_trait_impl(ty),
  89                     None => TyFingerprint::Unit,
  90                 }
  91             }
  92             TyKind::AssociatedType(_, _)
  93             | TyKind::OpaqueType(_, _)
  94             | TyKind::FnDef(_, _)
  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)
 100             }
 101             TyKind::Alias(_)
 102             | TyKind::Placeholder(_)
 103             | TyKind::BoundVar(_)
 104             | TyKind::InferenceVar(_, _)
 105             | TyKind::Error => return None,
 106         };
 107         Some(fp)
 108     }
 109 }
 110
 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)),
 124 ];
 125
 126 pub(crate) const ALL_FLOAT_FPS: [TyFingerprint; 2] = [
 127     TyFingerprint::Scalar(Scalar::Float(FloatTy::F32)),
 128     TyFingerprint::Scalar(Scalar::Float(FloatTy::F64)),
 129 ];
 130
 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>>>,
 136 }
 137
 138 impl TraitImpls {
 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() };
 142
 143         let crate_def_map = db.crate_def_map(krate);
 144         impls.collect_def_map(db, &crate_def_map);
 145         impls.shrink_to_fit();
 146
 147         Arc::new(impls)
 148     }
 149
 150     pub(crate) fn trait_impls_in_block_query(
 151         db: &dyn HirDatabase,
 152         block: BlockId,
 153     ) -> Option<Arc<Self>> {
 154         let _p = profile::span("trait_impls_in_block_query");
 155         let mut impls = Self { map: FxHashMap::default() };
 156
 157         let block_def_map = db.block_def_map(block)?;
 158         impls.collect_def_map(db, &block_def_map);
 159         impls.shrink_to_fit();
 160
 161         Some(Arc::new(impls))
 162     }
 163
 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() };
 168
 169         for krate in crate_graph.transitive_deps(krate) {
 170             res.merge(&db.trait_impls_in_crate(krate));
 171         }
 172         res.shrink_to_fit();
 173
 174         Arc::new(res)
 175     }
 176
 177     fn shrink_to_fit(&mut self) {
 178         self.map.shrink_to_fit();
 179         self.map.values_mut().for_each(|map| {
 180             map.shrink_to_fit();
 181             map.values_mut().for_each(Vec::shrink_to_fit);
 182         });
 183     }
 184
 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(),
 190                     None => continue,
 191                 };
 192                 let self_ty = db.impl_self_ty(impl_id);
 193                 let self_ty_fp = TyFingerprint::for_trait_impl(self_ty.skip_binders());
 194                 self.map
 195                     .entry(target_trait)
 196                     .or_default()
 197                     .entry(self_ty_fp)
 198                     .or_default()
 199                     .push(impl_id);
 200             }
 201
 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);
 208                 }
 209             }
 210         }
 211     }
 212
 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);
 218             }
 219         }
 220     }
 221
 222     /// Queries all trait impls for the given type.
 223     pub fn for_self_ty_without_blanket_impls(
 224         &self,
 225         fp: TyFingerprint,
 226     ) -> impl Iterator<Item = ImplId> + '_ {
 227         self.map
 228             .values()
 229             .flat_map(move |impls| impls.get(&Some(fp)).into_iter())
 230             .flat_map(|it| it.iter().copied())
 231     }
 232
 233     /// Queries all impls of the given trait.
 234     pub fn for_trait(&self, trait_: TraitId) -> impl Iterator<Item = ImplId> + '_ {
 235         self.map
 236             .get(&trait_)
 237             .into_iter()
 238             .flat_map(|map| map.values().flat_map(|v| v.iter().copied()))
 239     }
 240
 241     /// Queries all impls of `trait_` that may apply to `self_ty`.
 242     pub fn for_trait_and_self_ty(
 243         &self,
 244         trait_: TraitId,
 245         self_ty: TyFingerprint,
 246     ) -> impl Iterator<Item = ImplId> + '_ {
 247         self.map
 248             .get(&trait_)
 249             .into_iter()
 250             .flat_map(move |map| map.get(&Some(self_ty)).into_iter().chain(map.get(&None)))
 251             .flat_map(|v| v.iter().copied())
 252     }
 253
 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()))
 256     }
 257 }
 258
 259 /// Inherent impls defined in some crate.
 260 ///
 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).
 263 ///
 264 /// This makes inherent impl lookup easier than trait impl lookup since we only have to consider a
 265 /// single crate.
 266 #[derive(Debug, Eq, PartialEq)]
 267 pub struct InherentImpls {
 268     map: FxHashMap<TyFingerprint, Vec<ImplId>>,
 269 }
 270
 271 impl InherentImpls {
 272     pub(crate) fn inherent_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
 273         let mut impls = Self { map: FxHashMap::default() };
 274
 275         let crate_def_map = db.crate_def_map(krate);
 276         impls.collect_def_map(db, &crate_def_map);
 277         impls.shrink_to_fit();
 278
 279         Arc::new(impls)
 280     }
 281
 282     pub(crate) fn inherent_impls_in_block_query(
 283         db: &dyn HirDatabase,
 284         block: BlockId,
 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));
 291         }
 292         None
 293     }
 294
 295     fn shrink_to_fit(&mut self) {
 296         self.map.values_mut().for_each(Vec::shrink_to_fit);
 297         self.map.shrink_to_fit();
 298     }
 299
 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() {
 305                     continue;
 306                 }
 307
 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);
 312                 }
 313                 // `fp` should only be `None` in error cases (either erroneous code or incomplete name resolution)
 314             }
 315
 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);
 322                 }
 323             }
 324         }
 325     }
 326
 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(&[]),
 330             None => &[],
 331         }
 332     }
 333
 334     pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ {
 335         self.map.values().flat_map(|v| v.iter().copied())
 336     }
 337 }
 338
 339 pub fn inherent_impl_crates_query(
 340     db: &dyn HirDatabase,
 341     krate: CrateId,
 342     fp: TyFingerprint,
 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();
 347
 348     for krate in crate_graph.transitive_deps(krate) {
 349         if res.is_full() {
 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.
 352             break;
 353         }
 354         let impls = db.inherent_impls_in_crate(krate);
 355         if impls.map.get(&fp).map_or(false, |v| !v.is_empty()) {
 356             res.push(krate);
 357         }
 358     }
 359
 360     res
 361 }
 362
 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();
 368
 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]
 376                 .name
 377                 .as_ref()
 378                 .map_or(false, |n| n.to_smol_str().starts_with("_DERIVE_"))
 379             {
 380                 Some(id)
 381             } else {
 382                 None
 383             }
 384         }
 385         _ => None,
 386     });
 387
 388     unnamed_consts.chain(synstructure_hack_consts)
 389 }
 390
 391 pub fn def_crates(
 392     db: &dyn HirDatabase,
 393     ty: &Ty,
 394     cur_crate: CrateId,
 395 ) -> Option<ArrayVec<CrateId, 2>> {
 396     let mod_to_crate_ids = |module: ModuleId| Some(iter::once(module.krate()).collect());
 397
 398     let fp = TyFingerprint::for_inherent_impl(ty);
 399
 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()))
 404         }
 405         TyKind::Dyn(_) => ty
 406             .dyn_trait()
 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).
 411         TyKind::Scalar(_)
 412         | TyKind::Str
 413         | TyKind::Slice(_)
 414         | TyKind::Array(..)
 415         | TyKind::Raw(..) => {
 416             Some(db.inherent_impl_crates(cur_crate, fp.expect("fingerprint for primitive")))
 417         }
 418         _ => return None,
 419     }
 420 }
 421
 422 /// Look up the method with the given name.
 423 pub(crate) fn lookup_method(
 424     ty: &Canonical<Ty>,
 425     db: &dyn HirDatabase,
 426     env: Arc<TraitEnvironment>,
 427     traits_in_scope: &FxHashSet<TraitId>,
 428     visible_from_module: VisibleFromModule,
 429     name: &Name,
 430 ) -> Option<(ReceiverAdjustments, FunctionId)> {
 431     iterate_method_candidates(
 432         ty,
 433         db,
 434         env,
 435         traits_in_scope,
 436         visible_from_module,
 437         Some(name),
 438         LookupMode::MethodCall,
 439         |adjustments, f| match f {
 440             AssocItemId::FunctionId(f) => Some((adjustments, f)),
 441             _ => None,
 442         },
 443     )
 444 }
 445
 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.
 452     MethodCall,
 453     /// Looking up a path like `Vec::new` or `Vec::default`: We consider all
 454     /// candidates including associated constants, but don't do autoderef.
 455     Path,
 456 }
 457
 458 #[derive(Clone, Copy)]
 459 pub enum VisibleFromModule {
 460     /// Filter for results that are visible from the given module
 461     Filter(ModuleId),
 462     /// Include impls from the given block.
 463     IncludeBlock(BlockId),
 464     /// Do nothing special in regards visibility
 465     None,
 466 }
 467
 468 impl From<Option<ModuleId>> for VisibleFromModule {
 469     fn from(module: Option<ModuleId>) -> Self {
 470         match module {
 471             Some(module) => Self::Filter(module),
 472             None => Self::None,
 473         }
 474     }
 475 }
 476
 477 impl From<Option<BlockId>> for VisibleFromModule {
 478     fn from(block: Option<BlockId>) -> Self {
 479         match block {
 480             Some(block) => Self::IncludeBlock(block),
 481             None => Self::None,
 482         }
 483     }
 484 }
 485
 486 #[derive(Debug, Clone, Default)]
 487 pub struct ReceiverAdjustments {
 488     autoref: Option<Mutability>,
 489     autoderefs: usize,
 490     unsize_array: bool,
 491 }
 492
 493 impl ReceiverAdjustments {
 494     pub(crate) fn apply(&self, table: &mut InferenceTable<'_>, ty: Ty) -> (Ty, Vec<Adjustment>) {
 495         let mut ty = ty;
 496         let mut adjust = Vec::new();
 497         for _ in 0..self.autoderefs {
 498             match autoderef::autoderef_step(table, ty.clone()) {
 499                 None => {
 500                     never!("autoderef not possible for {:?}", ty);
 501                     ty = TyKind::Error.intern(Interner);
 502                     break;
 503                 }
 504                 Some((kind, new_ty)) => {
 505                     ty = new_ty.clone();
 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,
 511                         }),
 512                         target: new_ty,
 513                     });
 514                 }
 515             }
 516         }
 517         if self.unsize_array {
 518             ty = match ty.kind(Interner) {
 519                 TyKind::Array(inner, _) => TyKind::Slice(inner.clone()).intern(Interner),
 520                 _ => {
 521                     never!("unsize_array with non-array {:?}", ty);
 522                     ty
 523                 }
 524             };
 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),
 528                 target: ty.clone(),
 529             });
 530         }
 531         if let Some(m) = self.autoref {
 532             ty = TyKind::Ref(m, static_lifetime(), ty).intern(Interner);
 533             adjust
 534                 .push(Adjustment { kind: Adjust::Borrow(AutoBorrow::Ref(m)), target: ty.clone() });
 535         }
 536         (ty, adjust)
 537     }
 538
 539     fn with_autoref(&self, m: Mutability) -> ReceiverAdjustments {
 540         Self { autoref: Some(m), ..*self }
 541     }
 542 }
 543
 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>(
 548     ty: &Canonical<Ty>,
 549     db: &dyn HirDatabase,
 550     env: Arc<TraitEnvironment>,
 551     traits_in_scope: &FxHashSet<TraitId>,
 552     visible_from_module: VisibleFromModule,
 553     name: Option<&Name>,
 554     mode: LookupMode,
 555     mut callback: impl FnMut(ReceiverAdjustments, AssocItemId) -> Option<T>,
 556 ) -> Option<T> {
 557     let mut slot = None;
 558     iterate_method_candidates_dyn(
 559         ty,
 560         db,
 561         env,
 562         traits_in_scope,
 563         visible_from_module,
 564         name,
 565         mode,
 566         &mut |adj, item| {
 567             assert!(slot.is_none());
 568             if let Some(it) = callback(adj, item) {
 569                 slot = Some(it);
 570                 return ControlFlow::Break(());
 571             }
 572             ControlFlow::Continue(())
 573         },
 574     );
 575     slot
 576 }
 577
 578 pub fn lookup_impl_method(
 579     self_ty: &Ty,
 580     db: &dyn HirDatabase,
 581     env: Arc<TraitEnvironment>,
 582     trait_: TraitId,
 583     name: &Name,
 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),
 592             _ => None,
 593         })
 594     })
 595 }
 596
 597 fn find_matching_impl(
 598     mut impls: impl Iterator<Item = ImplId>,
 599     table: &mut InferenceTable<'_>,
 600     self_ty: &Ty,
 601 ) -> Option<Arc<ImplData>> {
 602     let db = table.db;
 603     loop {
 604         let impl_ = impls.next()?;
 605         let r = table.run_in_snapshot(|table| {
 606             let impl_data = db.impl_data(impl_);
 607             let substs =
 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);
 610
 611             table
 612                 .unify(self_ty, &impl_ty)
 613                 .then(|| {
 614                     let wh_goals =
 615                         crate::chalk_db::convert_where_clauses(db, impl_.into(), &substs)
 616                             .into_iter()
 617                             .map(|b| b.cast(Interner));
 618
 619                     let goal = crate::Goal::all(Interner, wh_goals);
 620
 621                     table.try_obligation(goal).map(|_| impl_data)
 622                 })
 623                 .flatten()
 624         });
 625         if r.is_some() {
 626             break r;
 627         }
 628     }
 629 }
 630
 631 pub fn iterate_path_candidates(
 632     ty: &Canonical<Ty>,
 633     db: &dyn HirDatabase,
 634     env: Arc<TraitEnvironment>,
 635     traits_in_scope: &FxHashSet<TraitId>,
 636     visible_from_module: VisibleFromModule,
 637     name: Option<&Name>,
 638     callback: &mut dyn FnMut(AssocItemId) -> ControlFlow<()>,
 639 ) -> ControlFlow<()> {
 640     iterate_method_candidates_dyn(
 641         ty,
 642         db,
 643         env,
 644         traits_in_scope,
 645         visible_from_module,
 646         name,
 647         LookupMode::Path,
 648         // the adjustments are not relevant for path lookup
 649         &mut |_, id| callback(id),
 650     )
 651 }
 652
 653 pub fn iterate_method_candidates_dyn(
 654     ty: &Canonical<Ty>,
 655     db: &dyn HirDatabase,
 656     env: Arc<TraitEnvironment>,
 657     traits_in_scope: &FxHashSet<TraitId>,
 658     visible_from_module: VisibleFromModule,
 659     name: Option<&Name>,
 660     mode: LookupMode,
 661     callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
 662 ) -> ControlFlow<()> {
 663     match mode {
 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).
 670
 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.
 678             //
 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
 682             // types*.
 683
 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);
 687
 688             let result = deref_chain.into_iter().zip(adj).try_for_each(|(receiver_ty, adj)| {
 689                 iterate_method_candidates_with_autoref(
 690                     &receiver_ty,
 691                     adj,
 692                     db,
 693                     env.clone(),
 694                     traits_in_scope,
 695                     visible_from_module,
 696                     name,
 697                     callback,
 698                 )
 699             });
 700             result
 701         }
 702         LookupMode::Path => {
 703             // No autoderef for path lookups
 704             iterate_method_candidates_for_self_ty(
 705                 ty,
 706                 db,
 707                 env,
 708                 traits_in_scope,
 709                 visible_from_module,
 710                 name,
 711                 callback,
 712             )
 713         }
 714     }
 715 }
 716
 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,
 724     name: Option<&Name>,
 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(());
 730     }
 731
 732     iterate_method_candidates_by_receiver(
 733         receiver_ty,
 734         first_adjustment.clone(),
 735         db,
 736         env.clone(),
 737         traits_in_scope,
 738         visible_from_module,
 739         name,
 740         &mut callback,
 741     )?;
 742
 743     let refed = Canonical {
 744         value: TyKind::Ref(Mutability::Not, static_lifetime(), receiver_ty.value.clone())
 745             .intern(Interner),
 746         binders: receiver_ty.binders.clone(),
 747     };
 748
 749     iterate_method_candidates_by_receiver(
 750         &refed,
 751         first_adjustment.with_autoref(Mutability::Not),
 752         db,
 753         env.clone(),
 754         traits_in_scope,
 755         visible_from_module,
 756         name,
 757         &mut callback,
 758     )?;
 759
 760     let ref_muted = Canonical {
 761         value: TyKind::Ref(Mutability::Mut, static_lifetime(), receiver_ty.value.clone())
 762             .intern(Interner),
 763         binders: receiver_ty.binders.clone(),
 764     };
 765
 766     iterate_method_candidates_by_receiver(
 767         &ref_muted,
 768         first_adjustment.with_autoref(Mutability::Mut),
 769         db,
 770         env,
 771         traits_in_scope,
 772         visible_from_module,
 773         name,
 774         &mut callback,
 775     )
 776 }
 777
 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,
 785     name: Option<&Name>,
 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
 793     // that.
 794     let mut autoderef = autoderef::Autoderef::new(&mut table, receiver_ty.clone());
 795     while let Some((self_ty, _)) = autoderef.next() {
 796         iterate_inherent_methods(
 797             &self_ty,
 798             &mut autoderef.table,
 799             name,
 800             Some(&receiver_ty),
 801             Some(receiver_adjustments.clone()),
 802             visible_from_module,
 803             &mut callback,
 804         )?
 805     }
 806
 807     table.rollback_to(snapshot);
 808
 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(
 812             &self_ty,
 813             &mut autoderef.table,
 814             traits_in_scope,
 815             name,
 816             Some(&receiver_ty),
 817             Some(receiver_adjustments.clone()),
 818             &mut callback,
 819         )?
 820     }
 821
 822     ControlFlow::Continue(())
 823 }
 824
 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,
 831     name: Option<&Name>,
 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(
 837         &self_ty,
 838         &mut table,
 839         name,
 840         None,
 841         None,
 842         visible_from_module,
 843         &mut callback,
 844     )?;
 845     iterate_trait_method_candidates(
 846         &self_ty,
 847         &mut table,
 848         traits_in_scope,
 849         name,
 850         None,
 851         None,
 852         callback,
 853     )
 854 }
 855
 856 fn iterate_trait_method_candidates(
 857     self_ty: &Ty,
 858     table: &mut InferenceTable<'_>,
 859     traits_in_scope: &FxHashSet<TraitId>,
 860     name: Option<&Name>,
 861     receiver_ty: Option<&Ty>,
 862     receiver_adjustments: Option<ReceiverAdjustments>,
 863     callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
 864 ) -> ControlFlow<()> {
 865     let db = table.db;
 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
 869     let inherent_trait =
 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
 873         .then(|| {
 874             env.traits_in_scope_from_clauses(self_ty.clone())
 875                 .flat_map(|t| all_super_traits(db.upcast(), t))
 876         })
 877         .into_iter()
 878         .flatten();
 879     let traits = inherent_trait.chain(env_traits).chain(traits_in_scope.iter().copied());
 880
 881     let canonical_self_ty = table.canonicalize(self_ty.clone()).value;
 882
 883     'traits: for t in traits {
 884         let data = db.trait_data(t);
 885
 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
 888         // 2021.
 889         // This is to make `[a].into_iter()` not break code with the new `IntoIterator` impl for
 890         // arrays.
 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 {
 895                 continue;
 896             }
 897         }
 898
 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
 901         // iteration
 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) {
 907                 continue;
 908             }
 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() {
 912                     continue 'traits;
 913                 }
 914             }
 915             known_implemented = true;
 916             callback(receiver_adjustments.clone().unwrap_or_default(), item)?;
 917         }
 918     }
 919     ControlFlow::Continue(())
 920 }
 921
 922 fn iterate_inherent_methods(
 923     self_ty: &Ty,
 924     table: &mut InferenceTable<'_>,
 925     name: Option<&Name>,
 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<()> {
 931     let db = table.db;
 932     let env = table.trait_env.clone();
 933     let def_crates = match def_crates(db, self_ty, env.krate) {
 934         Some(k) => k,
 935         None => return ControlFlow::Continue(()),
 936     };
 937
 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),
 942     };
 943
 944     if let Some(block_id) = block {
 945         if let Some(impls) = db.inherent_impls_in_block(block_id) {
 946             impls_for_self_ty(
 947                 &impls,
 948                 self_ty,
 949                 table,
 950                 name,
 951                 receiver_ty,
 952                 receiver_adjustments.clone(),
 953                 module,
 954                 callback,
 955             )?;
 956         }
 957     }
 958
 959     for krate in def_crates {
 960         let impls = db.inherent_impls_in_crate(krate);
 961         impls_for_self_ty(
 962             &impls,
 963             self_ty,
 964             table,
 965             name,
 966             receiver_ty,
 967             receiver_adjustments.clone(),
 968             module,
 969             callback,
 970         )?;
 971     }
 972     return ControlFlow::Continue(());
 973
 974     fn impls_for_self_ty(
 975         impls: &InherentImpls,
 976         self_ty: &Ty,
 977         table: &mut InferenceTable<'_>,
 978         name: Option<&Name>,
 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<()> {
 984         let db = table.db;
 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)
 989                 {
 990                     continue;
 991                 }
 992                 callback(receiver_adjustments.clone().unwrap_or_default(), item)?;
 993             }
 994         }
 995         ControlFlow::Continue(())
 996     }
 997 }
 998
 999 /// Returns the receiver type for the index trait call.
1000 pub fn resolve_indexing_op(
1001     db: &dyn HirDatabase,
1002     env: Arc<TraitEnvironment>,
1003     ty: Canonical<Ty>,
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() {
1012             return Some(adj);
1013         }
1014     }
1015     None
1016 }
1017
1018 fn is_valid_candidate(
1019     table: &mut InferenceTable<'_>,
1020     name: Option<&Name>,
1021     receiver_ty: Option<&Ty>,
1022     item: AssocItemId,
1023     self_ty: &Ty,
1024     visible_from_module: Option<ModuleId>,
1025 ) -> bool {
1026     macro_rules! check_that {
1027         ($cond:expr) => {
1028             if !$cond {
1029                 return false;
1030             }
1031         };
1032     }
1033
1034     let db = table.db;
1035     match item {
1036         AssocItemId::FunctionId(m) => {
1037             let data = db.function_data(m);
1038
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);
1042                 if !v {
1043                     cov_mark::hit!(autoderef_candidate_not_visible);
1044                 }
1045                 v
1046             }));
1047
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()
1053                     }
1054                     ItemContainerId::ImplId(impl_id) => {
1055                         subst.apply(db.impl_self_ty(impl_id).skip_binders().clone(), Interner)
1056                     }
1057                     // We should only get called for associated items (impl/trait)
1058                     ItemContainerId::ModuleId(_) | ItemContainerId::ExternBlockId(_) => {
1059                         unreachable!()
1060                     }
1061                 };
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());
1065
1066                     let sig = db.callable_item_signature(m.into());
1067                     let expected_receiver =
1068                         sig.map(|s| s.params()[0].clone()).substitute(Interner, &subst);
1069
1070                     check_that!(table.unify(&receiver_ty, &expected_receiver));
1071                 }
1072                 true
1073             })
1074         }
1075         AssocItemId::ConstId(c) => {
1076             let data = db.const_data(c);
1077             check_that!(receiver_ty.is_none());
1078
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);
1082                 if !v {
1083                     cov_mark::hit!(const_candidate_not_visible);
1084                 }
1085                 v
1086             }));
1087             if let ItemContainerId::ImplId(impl_id) = c.lookup(db.upcast()).container {
1088                 let self_ty_matches = table.run_in_snapshot(|table| {
1089                     let subst =
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)
1094                 });
1095                 if !self_ty_matches {
1096                     cov_mark::hit!(const_candidate_self_type_mismatch);
1097                     return false;
1098                 }
1099             }
1100             true
1101         }
1102         _ => false,
1103     }
1104 }
1105
1106 pub fn implements_trait(
1107     ty: &Canonical<Ty>,
1108     db: &dyn HirDatabase,
1109     env: Arc<TraitEnvironment>,
1110     trait_: TraitId,
1111 ) -> bool {
1112     let goal = generic_implements_goal(db, env.clone(), trait_, ty);
1113     let solution = db.trait_solve(env.krate, goal.cast(Interner));
1114
1115     solution.is_some()
1116 }
1117
1118 pub fn implements_trait_unique(
1119     ty: &Canonical<Ty>,
1120     db: &dyn HirDatabase,
1121     env: Arc<TraitEnvironment>,
1122     trait_: TraitId,
1123 ) -> bool {
1124     let goal = generic_implements_goal(db, env.clone(), trait_, ty);
1125     let solution = db.trait_solve(env.krate, goal.cast(Interner));
1126
1127     matches!(solution, Some(crate::Solution::Unique(_)))
1128 }
1129
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>,
1135     trait_: TraitId,
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())
1142         .build();
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)
1147             }
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())
1151             }
1152         };
1153         chalk_ir::WithKind::new(vk, UniverseIndex::ROOT)
1154     }));
1155     let obligation = trait_ref.cast(Interner);
1156     Canonical {
1157         binders: CanonicalVarKinds::from_iter(Interner, kinds),
1158         value: InEnvironment::new(&env.env, obligation),
1159     }
1160 }
1161
1162 fn autoderef_method_receiver(
1163     table: &mut InferenceTable<'_>,
1164     ty: Ty,
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 {
1171             autoref: None,
1172             autoderefs: derefs,
1173             unsize_array: false,
1174         });
1175     }
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(),
1180     ) {
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 });
1184     }
1185     (deref_chain, adjustments)
1186 }