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 rustc_hir_analysis/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(crate) 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 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};
 425     Some(match op {
 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)),
 438         },
 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)),
 450         },
 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))
 456             }
 457             CmpOp::Ord { ordering: Ordering::Less, strict: true } => {
 458                 (name!(lt), name!(partial_ord))
 459             }
 460             CmpOp::Ord { ordering: Ordering::Greater, strict: false } => {
 461                 (name!(ge), name!(partial_ord))
 462             }
 463             CmpOp::Ord { ordering: Ordering::Greater, strict: true } => {
 464                 (name!(gt), name!(partial_ord))
 465             }
 466         },
 467         BinaryOp::Assignment { op: None } => return None,
 468     })
 469 }
 470
 471 /// Look up the method with the given name.
 472 pub(crate) fn lookup_method(
 473     ty: &Canonical<Ty>,
 474     db: &dyn HirDatabase,
 475     env: Arc<TraitEnvironment>,
 476     traits_in_scope: &FxHashSet<TraitId>,
 477     visible_from_module: VisibleFromModule,
 478     name: &Name,
 479 ) -> Option<(ReceiverAdjustments, FunctionId)> {
 480     iterate_method_candidates(
 481         ty,
 482         db,
 483         env,
 484         traits_in_scope,
 485         visible_from_module,
 486         Some(name),
 487         LookupMode::MethodCall,
 488         |adjustments, f| match f {
 489             AssocItemId::FunctionId(f) => Some((adjustments, f)),
 490             _ => None,
 491         },
 492     )
 493 }
 494
 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.
 501     MethodCall,
 502     /// Looking up a path like `Vec::new` or `Vec::default`: We consider all
 503     /// candidates including associated constants, but don't do autoderef.
 504     Path,
 505 }
 506
 507 #[derive(Clone, Copy)]
 508 pub enum VisibleFromModule {
 509     /// Filter for results that are visible from the given module
 510     Filter(ModuleId),
 511     /// Include impls from the given block.
 512     IncludeBlock(BlockId),
 513     /// Do nothing special in regards visibility
 514     None,
 515 }
 516
 517 impl From<Option<ModuleId>> for VisibleFromModule {
 518     fn from(module: Option<ModuleId>) -> Self {
 519         match module {
 520             Some(module) => Self::Filter(module),
 521             None => Self::None,
 522         }
 523     }
 524 }
 525
 526 impl From<Option<BlockId>> for VisibleFromModule {
 527     fn from(block: Option<BlockId>) -> Self {
 528         match block {
 529             Some(block) => Self::IncludeBlock(block),
 530             None => Self::None,
 531         }
 532     }
 533 }
 534
 535 #[derive(Debug, Clone, Default)]
 536 pub struct ReceiverAdjustments {
 537     autoref: Option<Mutability>,
 538     autoderefs: usize,
 539     unsize_array: bool,
 540 }
 541
 542 impl ReceiverAdjustments {
 543     pub(crate) fn apply(&self, table: &mut InferenceTable<'_>, ty: Ty) -> (Ty, Vec<Adjustment>) {
 544         let mut ty = ty;
 545         let mut adjust = Vec::new();
 546         for _ in 0..self.autoderefs {
 547             match autoderef::autoderef_step(table, ty.clone()) {
 548                 None => {
 549                     never!("autoderef not possible for {:?}", ty);
 550                     ty = TyKind::Error.intern(Interner);
 551                     break;
 552                 }
 553                 Some((kind, new_ty)) => {
 554                     ty = new_ty.clone();
 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,
 560                         }),
 561                         target: new_ty,
 562                     });
 563                 }
 564             }
 565         }
 566         if self.unsize_array {
 567             ty = match ty.kind(Interner) {
 568                 TyKind::Array(inner, _) => TyKind::Slice(inner.clone()).intern(Interner),
 569                 _ => {
 570                     never!("unsize_array with non-array {:?}", ty);
 571                     ty
 572                 }
 573             };
 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),
 577                 target: ty.clone(),
 578             });
 579         }
 580         if let Some(m) = self.autoref {
 581             ty = TyKind::Ref(m, static_lifetime(), ty).intern(Interner);
 582             adjust
 583                 .push(Adjustment { kind: Adjust::Borrow(AutoBorrow::Ref(m)), target: ty.clone() });
 584         }
 585         (ty, adjust)
 586     }
 587
 588     fn with_autoref(&self, m: Mutability) -> ReceiverAdjustments {
 589         Self { autoref: Some(m), ..*self }
 590     }
 591 }
 592
 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>(
 597     ty: &Canonical<Ty>,
 598     db: &dyn HirDatabase,
 599     env: Arc<TraitEnvironment>,
 600     traits_in_scope: &FxHashSet<TraitId>,
 601     visible_from_module: VisibleFromModule,
 602     name: Option<&Name>,
 603     mode: LookupMode,
 604     mut callback: impl FnMut(ReceiverAdjustments, AssocItemId) -> Option<T>,
 605 ) -> Option<T> {
 606     let mut slot = None;
 607     iterate_method_candidates_dyn(
 608         ty,
 609         db,
 610         env,
 611         traits_in_scope,
 612         visible_from_module,
 613         name,
 614         mode,
 615         &mut |adj, item| {
 616             assert!(slot.is_none());
 617             if let Some(it) = callback(adj, item) {
 618                 slot = Some(it);
 619                 return ControlFlow::Break(());
 620             }
 621             ControlFlow::Continue(())
 622         },
 623     );
 624     slot
 625 }
 626
 627 pub fn lookup_impl_method(
 628     self_ty: &Ty,
 629     db: &dyn HirDatabase,
 630     env: Arc<TraitEnvironment>,
 631     trait_: TraitId,
 632     name: &Name,
 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),
 641             _ => None,
 642         })
 643     })
 644 }
 645
 646 fn find_matching_impl(
 647     mut impls: impl Iterator<Item = ImplId>,
 648     table: &mut InferenceTable<'_>,
 649     self_ty: &Ty,
 650 ) -> Option<Arc<ImplData>> {
 651     let db = table.db;
 652     loop {
 653         let impl_ = impls.next()?;
 654         let r = table.run_in_snapshot(|table| {
 655             let impl_data = db.impl_data(impl_);
 656             let substs =
 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);
 659
 660             table
 661                 .unify(self_ty, &impl_ty)
 662                 .then(|| {
 663                     let wh_goals =
 664                         crate::chalk_db::convert_where_clauses(db, impl_.into(), &substs)
 665                             .into_iter()
 666                             .map(|b| b.cast(Interner));
 667
 668                     let goal = crate::Goal::all(Interner, wh_goals);
 669
 670                     table.try_obligation(goal).map(|_| impl_data)
 671                 })
 672                 .flatten()
 673         });
 674         if r.is_some() {
 675             break r;
 676         }
 677     }
 678 }
 679
 680 pub fn iterate_path_candidates(
 681     ty: &Canonical<Ty>,
 682     db: &dyn HirDatabase,
 683     env: Arc<TraitEnvironment>,
 684     traits_in_scope: &FxHashSet<TraitId>,
 685     visible_from_module: VisibleFromModule,
 686     name: Option<&Name>,
 687     callback: &mut dyn FnMut(AssocItemId) -> ControlFlow<()>,
 688 ) -> ControlFlow<()> {
 689     iterate_method_candidates_dyn(
 690         ty,
 691         db,
 692         env,
 693         traits_in_scope,
 694         visible_from_module,
 695         name,
 696         LookupMode::Path,
 697         // the adjustments are not relevant for path lookup
 698         &mut |_, id| callback(id),
 699     )
 700 }
 701
 702 pub fn iterate_method_candidates_dyn(
 703     ty: &Canonical<Ty>,
 704     db: &dyn HirDatabase,
 705     env: Arc<TraitEnvironment>,
 706     traits_in_scope: &FxHashSet<TraitId>,
 707     visible_from_module: VisibleFromModule,
 708     name: Option<&Name>,
 709     mode: LookupMode,
 710     callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
 711 ) -> ControlFlow<()> {
 712     match mode {
 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).
 719
 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.
 727             //
 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
 731             // types*.
 732
 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);
 736
 737             let result = deref_chain.into_iter().zip(adj).try_for_each(|(receiver_ty, adj)| {
 738                 iterate_method_candidates_with_autoref(
 739                     &receiver_ty,
 740                     adj,
 741                     db,
 742                     env.clone(),
 743                     traits_in_scope,
 744                     visible_from_module,
 745                     name,
 746                     callback,
 747                 )
 748             });
 749             result
 750         }
 751         LookupMode::Path => {
 752             // No autoderef for path lookups
 753             iterate_method_candidates_for_self_ty(
 754                 ty,
 755                 db,
 756                 env,
 757                 traits_in_scope,
 758                 visible_from_module,
 759                 name,
 760                 callback,
 761             )
 762         }
 763     }
 764 }
 765
 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,
 773     name: Option<&Name>,
 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(());
 779     }
 780
 781     iterate_method_candidates_by_receiver(
 782         receiver_ty,
 783         first_adjustment.clone(),
 784         db,
 785         env.clone(),
 786         traits_in_scope,
 787         visible_from_module,
 788         name,
 789         &mut callback,
 790     )?;
 791
 792     let refed = Canonical {
 793         value: TyKind::Ref(Mutability::Not, static_lifetime(), receiver_ty.value.clone())
 794             .intern(Interner),
 795         binders: receiver_ty.binders.clone(),
 796     };
 797
 798     iterate_method_candidates_by_receiver(
 799         &refed,
 800         first_adjustment.with_autoref(Mutability::Not),
 801         db,
 802         env.clone(),
 803         traits_in_scope,
 804         visible_from_module,
 805         name,
 806         &mut callback,
 807     )?;
 808
 809     let ref_muted = Canonical {
 810         value: TyKind::Ref(Mutability::Mut, static_lifetime(), receiver_ty.value.clone())
 811             .intern(Interner),
 812         binders: receiver_ty.binders.clone(),
 813     };
 814
 815     iterate_method_candidates_by_receiver(
 816         &ref_muted,
 817         first_adjustment.with_autoref(Mutability::Mut),
 818         db,
 819         env,
 820         traits_in_scope,
 821         visible_from_module,
 822         name,
 823         &mut callback,
 824     )
 825 }
 826
 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,
 834     name: Option<&Name>,
 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
 842     // that.
 843     let mut autoderef = autoderef::Autoderef::new(&mut table, receiver_ty.clone());
 844     while let Some((self_ty, _)) = autoderef.next() {
 845         iterate_inherent_methods(
 846             &self_ty,
 847             &mut autoderef.table,
 848             name,
 849             Some(&receiver_ty),
 850             Some(receiver_adjustments.clone()),
 851             visible_from_module,
 852             &mut callback,
 853         )?
 854     }
 855
 856     table.rollback_to(snapshot);
 857
 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(
 861             &self_ty,
 862             &mut autoderef.table,
 863             traits_in_scope,
 864             name,
 865             Some(&receiver_ty),
 866             Some(receiver_adjustments.clone()),
 867             &mut callback,
 868         )?
 869     }
 870
 871     ControlFlow::Continue(())
 872 }
 873
 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,
 880     name: Option<&Name>,
 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(
 886         &self_ty,
 887         &mut table,
 888         name,
 889         None,
 890         None,
 891         visible_from_module,
 892         &mut callback,
 893     )?;
 894     iterate_trait_method_candidates(
 895         &self_ty,
 896         &mut table,
 897         traits_in_scope,
 898         name,
 899         None,
 900         None,
 901         callback,
 902     )
 903 }
 904
 905 fn iterate_trait_method_candidates(
 906     self_ty: &Ty,
 907     table: &mut InferenceTable<'_>,
 908     traits_in_scope: &FxHashSet<TraitId>,
 909     name: Option<&Name>,
 910     receiver_ty: Option<&Ty>,
 911     receiver_adjustments: Option<ReceiverAdjustments>,
 912     callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
 913 ) -> ControlFlow<()> {
 914     let db = table.db;
 915     let env = table.trait_env.clone();
 916     let self_is_array = matches!(self_ty.kind(Interner), chalk_ir::TyKind::Array(..));
 917
 918     let canonical_self_ty = table.canonicalize(self_ty.clone()).value;
 919
 920     'traits: for &t in traits_in_scope {
 921         let data = db.trait_data(t);
 922
 923         // Traits annotated with `#[rustc_skip_array_during_method_dispatch]` are skipped during
 924         // method resolution, if the receiver is an array, and we're compiling for editions before
 925         // 2021.
 926         // This is to make `[a].into_iter()` not break code with the new `IntoIterator` impl for
 927         // arrays.
 928         if data.skip_array_during_method_dispatch && self_is_array {
 929             // FIXME: this should really be using the edition of the method name's span, in case it
 930             // comes from a macro
 931             if db.crate_graph()[env.krate].edition < Edition::Edition2021 {
 932                 continue;
 933             }
 934         }
 935
 936         // we'll be lazy about checking whether the type implements the
 937         // trait, but if we find out it doesn't, we'll skip the rest of the
 938         // iteration
 939         let mut known_implemented = false;
 940         for &(_, item) in data.items.iter() {
 941             // Don't pass a `visible_from_module` down to `is_valid_candidate`,
 942             // since only inherent methods should be included into visibility checking.
 943             if !is_valid_candidate(table, name, receiver_ty, item, self_ty, None) {
 944                 continue;
 945             }
 946             if !known_implemented {
 947                 let goal = generic_implements_goal(db, env.clone(), t, &canonical_self_ty);
 948                 if db.trait_solve(env.krate, goal.cast(Interner)).is_none() {
 949                     continue 'traits;
 950                 }
 951             }
 952             known_implemented = true;
 953             callback(receiver_adjustments.clone().unwrap_or_default(), item)?;
 954         }
 955     }
 956     ControlFlow::Continue(())
 957 }
 958
 959 fn iterate_inherent_methods(
 960     self_ty: &Ty,
 961     table: &mut InferenceTable<'_>,
 962     name: Option<&Name>,
 963     receiver_ty: Option<&Ty>,
 964     receiver_adjustments: Option<ReceiverAdjustments>,
 965     visible_from_module: VisibleFromModule,
 966     callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
 967 ) -> ControlFlow<()> {
 968     let db = table.db;
 969     let env = table.trait_env.clone();
 970
 971     // For trait object types and placeholder types with trait bounds, the methods of the trait and
 972     // its super traits are considered inherent methods. This matters because these methods have
 973     // higher priority than the other traits' methods, which would be considered in
 974     // `iterate_trait_method_candidates()` only after this function.
 975     match self_ty.kind(Interner) {
 976         TyKind::Placeholder(_) => {
 977             let env = table.trait_env.clone();
 978             let traits = env
 979                 .traits_in_scope_from_clauses(self_ty.clone())
 980                 .flat_map(|t| all_super_traits(db.upcast(), t));
 981             iterate_inherent_trait_methods(
 982                 self_ty,
 983                 table,
 984                 name,
 985                 receiver_ty,
 986                 receiver_adjustments.clone(),
 987                 callback,
 988                 traits,
 989             )?;
 990         }
 991         TyKind::Dyn(_) => {
 992             if let Some(principal_trait) = self_ty.dyn_trait() {
 993                 let traits = all_super_traits(db.upcast(), principal_trait);
 994                 iterate_inherent_trait_methods(
 995                     self_ty,
 996                     table,
 997                     name,
 998                     receiver_ty,
 999                     receiver_adjustments.clone(),
1000                     callback,
1001                     traits.into_iter(),
1002                 )?;
1003             }
1004         }
1005         _ => {}
1006     }
1007
1008     let def_crates = match def_crates(db, self_ty, env.krate) {
1009         Some(k) => k,
1010         None => return ControlFlow::Continue(()),
1011     };
1012
1013     let (module, block) = match visible_from_module {
1014         VisibleFromModule::Filter(module) => (Some(module), module.containing_block()),
1015         VisibleFromModule::IncludeBlock(block) => (None, Some(block)),
1016         VisibleFromModule::None => (None, None),
1017     };
1018
1019     if let Some(block_id) = block {
1020         if let Some(impls) = db.inherent_impls_in_block(block_id) {
1021             impls_for_self_ty(
1022                 &impls,
1023                 self_ty,
1024                 table,
1025                 name,
1026                 receiver_ty,
1027                 receiver_adjustments.clone(),
1028                 module,
1029                 callback,
1030             )?;
1031         }
1032     }
1033
1034     for krate in def_crates {
1035         let impls = db.inherent_impls_in_crate(krate);
1036         impls_for_self_ty(
1037             &impls,
1038             self_ty,
1039             table,
1040             name,
1041             receiver_ty,
1042             receiver_adjustments.clone(),
1043             module,
1044             callback,
1045         )?;
1046     }
1047     return ControlFlow::Continue(());
1048
1049     fn iterate_inherent_trait_methods(
1050         self_ty: &Ty,
1051         table: &mut InferenceTable<'_>,
1052         name: Option<&Name>,
1053         receiver_ty: Option<&Ty>,
1054         receiver_adjustments: Option<ReceiverAdjustments>,
1055         callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
1056         traits: impl Iterator<Item = TraitId>,
1057     ) -> ControlFlow<()> {
1058         let db = table.db;
1059         for t in traits {
1060             let data = db.trait_data(t);
1061             for &(_, item) in data.items.iter() {
1062                 // We don't pass `visible_from_module` as all trait items should be visible.
1063                 if is_valid_candidate(table, name, receiver_ty, item, self_ty, None) {
1064                     callback(receiver_adjustments.clone().unwrap_or_default(), item)?;
1065                 }
1066             }
1067         }
1068         ControlFlow::Continue(())
1069     }
1070
1071     fn impls_for_self_ty(
1072         impls: &InherentImpls,
1073         self_ty: &Ty,
1074         table: &mut InferenceTable<'_>,
1075         name: Option<&Name>,
1076         receiver_ty: Option<&Ty>,
1077         receiver_adjustments: Option<ReceiverAdjustments>,
1078         visible_from_module: Option<ModuleId>,
1079         callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>,
1080     ) -> ControlFlow<()> {
1081         let db = table.db;
1082         let impls_for_self_ty = impls.for_self_ty(self_ty);
1083         for &impl_def in impls_for_self_ty {
1084             for &item in &db.impl_data(impl_def).items {
1085                 if !is_valid_candidate(table, name, receiver_ty, item, self_ty, visible_from_module)
1086                 {
1087                     continue;
1088                 }
1089                 callback(receiver_adjustments.clone().unwrap_or_default(), item)?;
1090             }
1091         }
1092         ControlFlow::Continue(())
1093     }
1094 }
1095
1096 /// Returns the receiver type for the index trait call.
1097 pub fn resolve_indexing_op(
1098     db: &dyn HirDatabase,
1099     env: Arc<TraitEnvironment>,
1100     ty: Canonical<Ty>,
1101     index_trait: TraitId,
1102 ) -> Option<ReceiverAdjustments> {
1103     let mut table = InferenceTable::new(db, env.clone());
1104     let ty = table.instantiate_canonical(ty);
1105     let (deref_chain, adj) = autoderef_method_receiver(&mut table, ty);
1106     for (ty, adj) in deref_chain.into_iter().zip(adj) {
1107         let goal = generic_implements_goal(db, env.clone(), index_trait, &ty);
1108         if db.trait_solve(env.krate, goal.cast(Interner)).is_some() {
1109             return Some(adj);
1110         }
1111     }
1112     None
1113 }
1114
1115 macro_rules! check_that {
1116     ($cond:expr) => {
1117         if !$cond {
1118             return false;
1119         }
1120     };
1121 }
1122
1123 fn is_valid_candidate(
1124     table: &mut InferenceTable<'_>,
1125     name: Option<&Name>,
1126     receiver_ty: Option<&Ty>,
1127     item: AssocItemId,
1128     self_ty: &Ty,
1129     visible_from_module: Option<ModuleId>,
1130 ) -> bool {
1131     let db = table.db;
1132     match item {
1133         AssocItemId::FunctionId(m) => {
1134             is_valid_fn_candidate(table, m, name, receiver_ty, self_ty, visible_from_module)
1135         }
1136         AssocItemId::ConstId(c) => {
1137             let data = db.const_data(c);
1138             check_that!(receiver_ty.is_none());
1139
1140             check_that!(name.map_or(true, |n| data.name.as_ref() == Some(n)));
1141             check_that!(visible_from_module.map_or(true, |from_module| {
1142                 let v = db.const_visibility(c).is_visible_from(db.upcast(), from_module);
1143                 if !v {
1144                     cov_mark::hit!(const_candidate_not_visible);
1145                 }
1146                 v
1147             }));
1148             if let ItemContainerId::ImplId(impl_id) = c.lookup(db.upcast()).container {
1149                 let self_ty_matches = table.run_in_snapshot(|table| {
1150                     let subst =
1151                         TyBuilder::subst_for_def(db, c).fill_with_inference_vars(table).build();
1152                     let expected_self_ty =
1153                         subst.apply(db.impl_self_ty(impl_id).skip_binders().clone(), Interner);
1154                     table.unify(&expected_self_ty, &self_ty)
1155                 });
1156                 if !self_ty_matches {
1157                     cov_mark::hit!(const_candidate_self_type_mismatch);
1158                     return false;
1159                 }
1160             }
1161             true
1162         }
1163         _ => false,
1164     }
1165 }
1166
1167 fn is_valid_fn_candidate(
1168     table: &mut InferenceTable<'_>,
1169     fn_id: FunctionId,
1170     name: Option<&Name>,
1171     receiver_ty: Option<&Ty>,
1172     self_ty: &Ty,
1173     visible_from_module: Option<ModuleId>,
1174 ) -> bool {
1175     let db = table.db;
1176     let data = db.function_data(fn_id);
1177
1178     check_that!(name.map_or(true, |n| n == &data.name));
1179     check_that!(visible_from_module.map_or(true, |from_module| {
1180         let v = db.function_visibility(fn_id).is_visible_from(db.upcast(), from_module);
1181         if !v {
1182             cov_mark::hit!(autoderef_candidate_not_visible);
1183         }
1184         v
1185     }));
1186
1187     table.run_in_snapshot(|table| {
1188         let container = fn_id.lookup(db.upcast()).container;
1189         let impl_subst = match container {
1190             ItemContainerId::ImplId(it) => {
1191                 TyBuilder::subst_for_def(db, it).fill_with_inference_vars(table).build()
1192             }
1193             ItemContainerId::TraitId(it) => {
1194                 TyBuilder::subst_for_def(db, it).fill_with_inference_vars(table).build()
1195             }
1196             _ => unreachable!(),
1197         };
1198
1199         let fn_subst = TyBuilder::subst_for_def(db, fn_id)
1200             .use_parent_substs(&impl_subst)
1201             .fill_with_inference_vars(table)
1202             .build();
1203
1204         let expect_self_ty = match container {
1205             ItemContainerId::TraitId(_) => fn_subst.at(Interner, 0).assert_ty_ref(Interner).clone(),
1206             ItemContainerId::ImplId(impl_id) => {
1207                 fn_subst.apply(db.impl_self_ty(impl_id).skip_binders().clone(), Interner)
1208             }
1209             // We should only get called for associated items (impl/trait)
1210             ItemContainerId::ModuleId(_) | ItemContainerId::ExternBlockId(_) => {
1211                 unreachable!()
1212             }
1213         };
1214         check_that!(table.unify(&expect_self_ty, self_ty));
1215
1216         if let Some(receiver_ty) = receiver_ty {
1217             check_that!(data.has_self_param());
1218
1219             let sig = db.callable_item_signature(fn_id.into());
1220             let expected_receiver =
1221                 sig.map(|s| s.params()[0].clone()).substitute(Interner, &fn_subst);
1222
1223             check_that!(table.unify(&receiver_ty, &expected_receiver));
1224         }
1225
1226         if let ItemContainerId::ImplId(impl_id) = container {
1227             // We need to consider the bounds on the impl to distinguish functions of the same name
1228             // for a type.
1229             let predicates = db.generic_predicates(impl_id.into());
1230             predicates
1231                 .iter()
1232                 .map(|predicate| {
1233                     let (p, b) = predicate
1234                         .clone()
1235                         .substitute(Interner, &impl_subst)
1236                         // Skipping the inner binders is ok, as we don't handle quantified where
1237                         // clauses yet.
1238                         .into_value_and_skipped_binders();
1239                     stdx::always!(b.len(Interner) == 0);
1240                     p
1241                 })
1242                 // It's ok to get ambiguity here, as we may not have enough information to prove
1243                 // obligations. We'll check if the user is calling the selected method properly
1244                 // later anyway.
1245                 .all(|p| table.try_obligation(p.cast(Interner)).is_some())
1246         } else {
1247             // For `ItemContainerId::TraitId`, we check if `self_ty` implements the trait in
1248             // `iterate_trait_method_candidates()`.
1249             // For others, this function shouldn't be called.
1250             true
1251         }
1252     })
1253 }
1254
1255 pub fn implements_trait(
1256     ty: &Canonical<Ty>,
1257     db: &dyn HirDatabase,
1258     env: Arc<TraitEnvironment>,
1259     trait_: TraitId,
1260 ) -> bool {
1261     let goal = generic_implements_goal(db, env.clone(), trait_, ty);
1262     let solution = db.trait_solve(env.krate, goal.cast(Interner));
1263
1264     solution.is_some()
1265 }
1266
1267 pub fn implements_trait_unique(
1268     ty: &Canonical<Ty>,
1269     db: &dyn HirDatabase,
1270     env: Arc<TraitEnvironment>,
1271     trait_: TraitId,
1272 ) -> bool {
1273     let goal = generic_implements_goal(db, env.clone(), trait_, ty);
1274     let solution = db.trait_solve(env.krate, goal.cast(Interner));
1275
1276     matches!(solution, Some(crate::Solution::Unique(_)))
1277 }
1278
1279 /// This creates Substs for a trait with the given Self type and type variables
1280 /// for all other parameters, to query Chalk with it.
1281 fn generic_implements_goal(
1282     db: &dyn HirDatabase,
1283     env: Arc<TraitEnvironment>,
1284     trait_: TraitId,
1285     self_ty: &Canonical<Ty>,
1286 ) -> Canonical<InEnvironment<super::DomainGoal>> {
1287     let mut kinds = self_ty.binders.interned().to_vec();
1288     let trait_ref = TyBuilder::trait_ref(db, trait_)
1289         .push(self_ty.value.clone())
1290         .fill_with_bound_vars(DebruijnIndex::INNERMOST, kinds.len())
1291         .build();
1292     kinds.extend(trait_ref.substitution.iter(Interner).skip(1).map(|x| {
1293         let vk = match x.data(Interner) {
1294             chalk_ir::GenericArgData::Ty(_) => {
1295                 chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General)
1296             }
1297             chalk_ir::GenericArgData::Lifetime(_) => chalk_ir::VariableKind::Lifetime,
1298             chalk_ir::GenericArgData::Const(c) => {
1299                 chalk_ir::VariableKind::Const(c.data(Interner).ty.clone())
1300             }
1301         };
1302         chalk_ir::WithKind::new(vk, UniverseIndex::ROOT)
1303     }));
1304     let obligation = trait_ref.cast(Interner);
1305     Canonical {
1306         binders: CanonicalVarKinds::from_iter(Interner, kinds),
1307         value: InEnvironment::new(&env.env, obligation),
1308     }
1309 }
1310
1311 fn autoderef_method_receiver(
1312     table: &mut InferenceTable<'_>,
1313     ty: Ty,
1314 ) -> (Vec<Canonical<Ty>>, Vec<ReceiverAdjustments>) {
1315     let (mut deref_chain, mut adjustments): (Vec<_>, Vec<_>) = (Vec::new(), Vec::new());
1316     let mut autoderef = autoderef::Autoderef::new(table, ty);
1317     while let Some((ty, derefs)) = autoderef.next() {
1318         deref_chain.push(autoderef.table.canonicalize(ty).value);
1319         adjustments.push(ReceiverAdjustments {
1320             autoref: None,
1321             autoderefs: derefs,
1322             unsize_array: false,
1323         });
1324     }
1325     // As a last step, we can do array unsizing (that's the only unsizing that rustc does for method receivers!)
1326     if let (Some((TyKind::Array(parameters, _), binders)), Some(adj)) = (
1327         deref_chain.last().map(|ty| (ty.value.kind(Interner), ty.binders.clone())),
1328         adjustments.last().cloned(),
1329     ) {
1330         let unsized_ty = TyKind::Slice(parameters.clone()).intern(Interner);
1331         deref_chain.push(Canonical { value: unsized_ty, binders });
1332         adjustments.push(ReceiverAdjustments { unsize_array: true, ..adj });
1333     }
1334     (deref_chain, adjustments)
1335 }