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::{ops::ControlFlow, sync::Arc};
   6
   7 use base_db::{CrateId, Edition};
   8 use chalk_ir::{cast::Cast, Mutability, UniverseIndex};
   9 use hir_def::{
  10     data::ImplData, item_scope::ItemScope, nameres::DefMap, AssocItemId, BlockId, ConstId,
  11     FunctionId, HasModule, ImplId, ItemContainerId, Lookup, ModuleDefId, ModuleId, TraitId,
  12 };
  13 use hir_expand::name::Name;
  14 use rustc_hash::{FxHashMap, FxHashSet};
  15 use smallvec::{smallvec, SmallVec};
  16 use stdx::never;
  17
  18 use crate::{
  19     autoderef::{self, AutoderefKind},
  20     db::HirDatabase,
  21     from_foreign_def_id,
  22     infer::{unify::InferenceTable, Adjust, Adjustment, AutoBorrow, OverloadedDeref, PointerCast},
  23     primitive::{FloatTy, IntTy, UintTy},
  24     static_lifetime, to_chalk_trait_id,
  25     utils::all_super_traits,
  26     AdtId, Canonical, CanonicalVarKinds, DebruijnIndex, ForeignDefId, InEnvironment, Interner,
  27     Scalar, Substitution, TraitEnvironment, TraitRef, TraitRefExt, Ty, TyBuilder, TyExt, TyKind,
  28 };
  29
  30 /// This is used as a key for indexing impls.
  31 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
  32 pub enum TyFingerprint {
  33     // These are lang item impls:
  34     Str,
  35     Slice,
  36     Array,
  37     Never,
  38     RawPtr(Mutability),
  39     Scalar(Scalar),
  40     // These can have user-defined impls:
  41     Adt(hir_def::AdtId),
  42     Dyn(TraitId),
  43     ForeignType(ForeignDefId),
  44     // These only exist for trait impls
  45     Unit,
  46     Unnameable,
  47     Function(u32),
  48 }
  49
  50 impl TyFingerprint {
  51     /// Creates a TyFingerprint for looking up an inherent impl. Only certain
  52     /// types can have inherent impls: if we have some `struct S`, we can have
  53     /// an `impl S`, but not `impl &S`. Hence, this will return `None` for
  54     /// reference types and such.
  55     pub fn for_inherent_impl(ty: &Ty) -> Option<TyFingerprint> {
  56         let fp = match ty.kind(Interner) {
  57             TyKind::Str => TyFingerprint::Str,
  58             TyKind::Never => TyFingerprint::Never,
  59             TyKind::Slice(..) => TyFingerprint::Slice,
  60             TyKind::Array(..) => TyFingerprint::Array,
  61             TyKind::Scalar(scalar) => TyFingerprint::Scalar(*scalar),
  62             TyKind::Adt(AdtId(adt), _) => TyFingerprint::Adt(*adt),
  63             TyKind::Raw(mutability, ..) => TyFingerprint::RawPtr(*mutability),
  64             TyKind::Foreign(alias_id, ..) => TyFingerprint::ForeignType(*alias_id),
  65             TyKind::Dyn(_) => ty.dyn_trait().map(TyFingerprint::Dyn)?,
  66             _ => return None,
  67         };
  68         Some(fp)
  69     }
  70
  71     /// Creates a TyFingerprint for looking up a trait impl.
  72     pub fn for_trait_impl(ty: &Ty) -> Option<TyFingerprint> {
  73         let fp = match ty.kind(Interner) {
  74             TyKind::Str => TyFingerprint::Str,
  75             TyKind::Never => TyFingerprint::Never,
  76             TyKind::Slice(..) => TyFingerprint::Slice,
  77             TyKind::Array(..) => TyFingerprint::Array,
  78             TyKind::Scalar(scalar) => TyFingerprint::Scalar(*scalar),
  79             TyKind::Adt(AdtId(adt), _) => TyFingerprint::Adt(*adt),
  80             TyKind::Raw(mutability, ..) => TyFingerprint::RawPtr(*mutability),
  81             TyKind::Foreign(alias_id, ..) => TyFingerprint::ForeignType(*alias_id),
  82             TyKind::Dyn(_) => ty.dyn_trait().map(TyFingerprint::Dyn)?,
  83             TyKind::Ref(_, _, ty) => return TyFingerprint::for_trait_impl(ty),
  84             TyKind::Tuple(_, subst) => {
  85                 let first_ty = subst.interned().get(0).map(|arg| arg.assert_ty_ref(Interner));
  86                 match first_ty {
  87                     Some(ty) => return TyFingerprint::for_trait_impl(ty),
  88                     None => TyFingerprint::Unit,
  89                 }
  90             }
  91             TyKind::AssociatedType(_, _)
  92             | TyKind::OpaqueType(_, _)
  93             | TyKind::FnDef(_, _)
  94             | TyKind::Closure(_, _)
  95             | TyKind::Generator(..)
  96             | TyKind::GeneratorWitness(..) => TyFingerprint::Unnameable,
  97             TyKind::Function(fn_ptr) => {
  98                 TyFingerprint::Function(fn_ptr.substitution.0.len(Interner) as u32)
  99             }
 100             TyKind::Alias(_)
 101             | TyKind::Placeholder(_)
 102             | TyKind::BoundVar(_)
 103             | TyKind::InferenceVar(_, _)
 104             | TyKind::Error => return None,
 105         };
 106         Some(fp)
 107     }
 108 }
 109
 110 pub(crate) const ALL_INT_FPS: [TyFingerprint; 12] = [
 111     TyFingerprint::Scalar(Scalar::Int(IntTy::I8)),
 112     TyFingerprint::Scalar(Scalar::Int(IntTy::I16)),
 113     TyFingerprint::Scalar(Scalar::Int(IntTy::I32)),
 114     TyFingerprint::Scalar(Scalar::Int(IntTy::I64)),
 115     TyFingerprint::Scalar(Scalar::Int(IntTy::I128)),
 116     TyFingerprint::Scalar(Scalar::Int(IntTy::Isize)),
 117     TyFingerprint::Scalar(Scalar::Uint(UintTy::U8)),
 118     TyFingerprint::Scalar(Scalar::Uint(UintTy::U16)),
 119     TyFingerprint::Scalar(Scalar::Uint(UintTy::U32)),
 120     TyFingerprint::Scalar(Scalar::Uint(UintTy::U64)),
 121     TyFingerprint::Scalar(Scalar::Uint(UintTy::U128)),
 122     TyFingerprint::Scalar(Scalar::Uint(UintTy::Usize)),
 123 ];
 124
 125 pub(crate) const ALL_FLOAT_FPS: [TyFingerprint; 2] = [
 126     TyFingerprint::Scalar(Scalar::Float(FloatTy::F32)),
 127     TyFingerprint::Scalar(Scalar::Float(FloatTy::F64)),
 128 ];
 129
 130 /// Trait impls defined or available in some crate.
 131 #[derive(Debug, Eq, PartialEq)]
 132 pub struct TraitImpls {
 133     // If the `Option<TyFingerprint>` is `None`, the impl may apply to any self type.
 134     map: FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Vec<ImplId>>>,
 135 }
 136
 137 impl TraitImpls {
 138     pub(crate) fn trait_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
 139         let _p = profile::span("trait_impls_in_crate_query").detail(|| format!("{krate:?}"));
 140         let mut impls = Self { map: FxHashMap::default() };
 141
 142         let crate_def_map = db.crate_def_map(krate);
 143         impls.collect_def_map(db, &crate_def_map);
 144         impls.shrink_to_fit();
 145
 146         Arc::new(impls)
 147     }
 148
 149     pub(crate) fn trait_impls_in_block_query(
 150         db: &dyn HirDatabase,
 151         block: BlockId,
 152     ) -> Option<Arc<Self>> {
 153         let _p = profile::span("trait_impls_in_block_query");
 154         let mut impls = Self { map: FxHashMap::default() };
 155
 156         let block_def_map = db.block_def_map(block)?;
 157         impls.collect_def_map(db, &block_def_map);
 158         impls.shrink_to_fit();
 159
 160         Some(Arc::new(impls))
 161     }
 162
 163     pub(crate) fn trait_impls_in_deps_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
 164         let _p = profile::span("trait_impls_in_deps_query").detail(|| format!("{krate:?}"));
 165         let crate_graph = db.crate_graph();
 166         let mut res = Self { map: FxHashMap::default() };
 167
 168         for krate in crate_graph.transitive_deps(krate) {
 169             res.merge(&db.trait_impls_in_crate(krate));
 170         }
 171         res.shrink_to_fit();
 172
 173         Arc::new(res)
 174     }
 175
 176     fn shrink_to_fit(&mut self) {
 177         self.map.shrink_to_fit();
 178         self.map.values_mut().for_each(|map| {
 179             map.shrink_to_fit();
 180             map.values_mut().for_each(Vec::shrink_to_fit);
 181         });
 182     }
 183
 184     fn collect_def_map(&mut self, db: &dyn HirDatabase, def_map: &DefMap) {
 185         for (_module_id, module_data) in def_map.modules() {
 186             for impl_id in module_data.scope.impls() {
 187                 let target_trait = match db.impl_trait(impl_id) {
 188                     Some(tr) => tr.skip_binders().hir_trait_id(),
 189                     None => continue,
 190                 };
 191                 let self_ty = db.impl_self_ty(impl_id);
 192                 let self_ty_fp = TyFingerprint::for_trait_impl(self_ty.skip_binders());
 193                 self.map
 194                     .entry(target_trait)
 195                     .or_default()
 196                     .entry(self_ty_fp)
 197                     .or_default()
 198                     .push(impl_id);
 199             }
 200
 201             // To better support custom derives, collect impls in all unnamed const items.
 202             // const _: () = { ... };
 203             for konst in collect_unnamed_consts(db, &module_data.scope) {
 204                 let body = db.body(konst.into());
 205                 for (_, block_def_map) in body.blocks(db.upcast()) {
 206                     self.collect_def_map(db, &block_def_map);
 207                 }
 208             }
 209         }
 210     }
 211
 212     fn merge(&mut self, other: &Self) {
 213         for (trait_, other_map) in &other.map {
 214             let map = self.map.entry(*trait_).or_default();
 215             for (fp, impls) in other_map {
 216                 map.entry(*fp).or_default().extend(impls);
 217             }
 218         }
 219     }
 220
 221     /// Queries all trait impls for the given type.
 222     pub fn for_self_ty_without_blanket_impls(
 223         &self,
 224         fp: TyFingerprint,
 225     ) -> impl Iterator<Item = ImplId> + '_ {
 226         self.map
 227             .values()
 228             .flat_map(move |impls| impls.get(&Some(fp)).into_iter())
 229             .flat_map(|it| it.iter().copied())
 230     }
 231
 232     /// Queries all impls of the given trait.
 233     pub fn for_trait(&self, trait_: TraitId) -> impl Iterator<Item = ImplId> + '_ {
 234         self.map
 235             .get(&trait_)
 236             .into_iter()
 237             .flat_map(|map| map.values().flat_map(|v| v.iter().copied()))
 238     }
 239
 240     /// Queries all impls of `trait_` that may apply to `self_ty`.
 241     pub fn for_trait_and_self_ty(
 242         &self,
 243         trait_: TraitId,
 244         self_ty: TyFingerprint,
 245     ) -> impl Iterator<Item = ImplId> + '_ {
 246         self.map
 247             .get(&trait_)
 248             .into_iter()
 249             .flat_map(move |map| map.get(&Some(self_ty)).into_iter().chain(map.get(&None)))
 250             .flat_map(|v| v.iter().copied())
 251     }
 252
 253     pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ {
 254         self.map.values().flat_map(|map| map.values().flat_map(|v| v.iter().copied()))
 255     }
 256 }
 257
 258 /// Inherent impls defined in some crate.
 259 ///
 260 /// Inherent impls can only be defined in the crate that also defines the self type of the impl
 261 /// (note that some primitives are considered to be defined by both libcore and liballoc).
 262 ///
 263 /// This makes inherent impl lookup easier than trait impl lookup since we only have to consider a
 264 /// single crate.
 265 #[derive(Debug, Eq, PartialEq)]
 266 pub struct InherentImpls {
 267     map: FxHashMap<TyFingerprint, Vec<ImplId>>,
 268 }
 269
 270 impl InherentImpls {
 271     pub(crate) fn inherent_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
 272         let mut impls = Self { map: FxHashMap::default() };
 273
 274         let crate_def_map = db.crate_def_map(krate);
 275         impls.collect_def_map(db, &crate_def_map);
 276         impls.shrink_to_fit();
 277
 278         Arc::new(impls)
 279     }
 280
 281     pub(crate) fn inherent_impls_in_block_query(
 282         db: &dyn HirDatabase,
 283         block: BlockId,
 284     ) -> Option<Arc<Self>> {
 285         let mut impls = Self { map: FxHashMap::default() };
 286         if let Some(block_def_map) = db.block_def_map(block) {
 287             impls.collect_def_map(db, &block_def_map);
 288             impls.shrink_to_fit();
 289             return Some(Arc::new(impls));
 290         }
 291         None
 292     }
 293
 294     fn shrink_to_fit(&mut self) {
 295         self.map.values_mut().for_each(Vec::shrink_to_fit);
 296         self.map.shrink_to_fit();
 297     }
 298
 299     fn collect_def_map(&mut self, db: &dyn HirDatabase, def_map: &DefMap) {
 300         for (_module_id, module_data) in def_map.modules() {
 301             for impl_id in module_data.scope.impls() {
 302                 let data = db.impl_data(impl_id);
 303                 if data.target_trait.is_some() {
 304                     continue;
 305                 }
 306
 307                 let self_ty = db.impl_self_ty(impl_id);
 308                 let fp = TyFingerprint::for_inherent_impl(self_ty.skip_binders());
 309                 if let Some(fp) = fp {
 310                     self.map.entry(fp).or_default().push(impl_id);
 311                 }
 312                 // `fp` should only be `None` in error cases (either erroneous code or incomplete name resolution)
 313             }
 314
 315             // To better support custom derives, collect impls in all unnamed const items.
 316             // const _: () = { ... };
 317             for konst in collect_unnamed_consts(db, &module_data.scope) {
 318                 let body = db.body(konst.into());
 319                 for (_, block_def_map) in body.blocks(db.upcast()) {
 320                     self.collect_def_map(db, &block_def_map);
 321                 }
 322             }
 323         }
 324     }
 325
 326     pub fn for_self_ty(&self, self_ty: &Ty) -> &[ImplId] {
 327         match TyFingerprint::for_inherent_impl(self_ty) {
 328             Some(fp) => self.map.get(&fp).map(|vec| vec.as_ref()).unwrap_or(&[]),
 329             None => &[],
 330         }
 331     }
 332
 333     pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ {
 334         self.map.values().flat_map(|v| v.iter().copied())
 335     }
 336 }
 337
 338 pub(crate) fn incoherent_inherent_impl_crates(
 339     db: &dyn HirDatabase,
 340     krate: CrateId,
 341     fp: TyFingerprint,
 342 ) -> SmallVec<[CrateId; 2]> {
 343     let _p = profile::span("inherent_impl_crates_query");
 344     let mut res = SmallVec::new();
 345     let crate_graph = db.crate_graph();
 346
 347     // should pass crate for finger print and do reverse deps
 348
 349     for krate in crate_graph.transitive_deps(krate) {
 350         let impls = db.inherent_impls_in_crate(krate);
 351         if impls.map.get(&fp).map_or(false, |v| !v.is_empty()) {
 352             res.push(krate);
 353         }
 354     }
 355
 356     res
 357 }
 358
 359 fn collect_unnamed_consts<'a>(
 360     db: &'a dyn HirDatabase,
 361     scope: &'a ItemScope,
 362 ) -> impl Iterator<Item = ConstId> + 'a {
 363     let unnamed_consts = scope.unnamed_consts();
 364
 365     // FIXME: Also treat consts named `_DERIVE_*` as unnamed, since synstructure generates those.
 366     // Should be removed once synstructure stops doing that.
 367     let synstructure_hack_consts = scope.values().filter_map(|(item, _)| match item {
 368         ModuleDefId::ConstId(id) => {
 369             let loc = id.lookup(db.upcast());
 370             let item_tree = loc.id.item_tree(db.upcast());
 371             if item_tree[loc.id.value]
 372                 .name
 373                 .as_ref()
 374                 .map_or(false, |n| n.to_smol_str().starts_with("_DERIVE_"))
 375             {
 376                 Some(id)
 377             } else {
 378                 None
 379             }
 380         }
 381         _ => None,
 382     });
 383
 384     unnamed_consts.chain(synstructure_hack_consts)
 385 }
 386
 387 pub fn def_crates(
 388     db: &dyn HirDatabase,
 389     ty: &Ty,
 390     cur_crate: CrateId,
 391 ) -> Option<SmallVec<[CrateId; 2]>> {
 392     match ty.kind(Interner) {
 393         &TyKind::Adt(AdtId(def_id), _) => {
 394             let rustc_has_incoherent_inherent_impls = match def_id {
 395                 hir_def::AdtId::StructId(id) => {
 396                     db.struct_data(id).rustc_has_incoherent_inherent_impls
 397                 }
 398                 hir_def::AdtId::UnionId(id) => {
 399                     db.union_data(id).rustc_has_incoherent_inherent_impls
 400                 }
 401                 hir_def::AdtId::EnumId(id) => db.enum_data(id).rustc_has_incoherent_inherent_impls,
 402             };
 403             Some(if rustc_has_incoherent_inherent_impls {
 404                 db.incoherent_inherent_impl_crates(cur_crate, TyFingerprint::Adt(def_id))
 405             } else {
 406                 smallvec![def_id.module(db.upcast()).krate()]
 407             })
 408         }
 409         &TyKind::Foreign(id) => {
 410             let alias = from_foreign_def_id(id);
 411             Some(if db.type_alias_data(alias).rustc_has_incoherent_inherent_impls {
 412                 db.incoherent_inherent_impl_crates(cur_crate, TyFingerprint::ForeignType(id))
 413             } else {
 414                 smallvec![alias.module(db.upcast()).krate()]
 415             })
 416         }
 417         TyKind::Dyn(_) => {
 418             let trait_id = ty.dyn_trait()?;
 419             Some(if db.trait_data(trait_id).rustc_has_incoherent_inherent_impls {
 420                 db.incoherent_inherent_impl_crates(cur_crate, TyFingerprint::Dyn(trait_id))
 421             } else {
 422                 smallvec![trait_id.module(db.upcast()).krate()]
 423             })
 424         }
 425         // for primitives, there may be impls in various places (core and alloc
 426         // mostly). We just check the whole crate graph for crates with impls
 427         // (cached behind a query).
 428         TyKind::Scalar(_)
 429         | TyKind::Str
 430         | TyKind::Slice(_)
 431         | TyKind::Array(..)
 432         | TyKind::Raw(..) => Some(db.incoherent_inherent_impl_crates(
 433             cur_crate,
 434             TyFingerprint::for_inherent_impl(ty).expect("fingerprint for primitive"),
 435         )),
 436         _ => None,
 437     }
 438 }
 439
 440 pub fn lang_names_for_bin_op(op: syntax::ast::BinaryOp) -> Option<(Name, Name)> {
 441     use hir_expand::name;
 442     use syntax::ast::{ArithOp, BinaryOp, CmpOp, Ordering};
 443     Some(match op {
 444         BinaryOp::LogicOp(_) => return None,
 445         BinaryOp::ArithOp(aop) => match aop {
 446             ArithOp::Add => (name!(add), name!(add)),
 447             ArithOp::Mul => (name!(mul), name!(mul)),
 448             ArithOp::Sub => (name!(sub), name!(sub)),
 449             ArithOp::Div => (name!(div), name!(div)),
 450             ArithOp::Rem => (name!(rem), name!(rem)),
 451             ArithOp::Shl => (name!(shl), name!(shl)),
 452             ArithOp::Shr => (name!(shr), name!(shr)),
 453             ArithOp::BitXor => (name!(bitxor), name!(bitxor)),
 454             ArithOp::BitOr => (name!(bitor), name!(bitor)),
 455             ArithOp::BitAnd => (name!(bitand), name!(bitand)),
 456         },
 457         BinaryOp::Assignment { op: Some(aop) } => match aop {
 458             ArithOp::Add => (name!(add_assign), name!(add_assign)),
 459             ArithOp::Mul => (name!(mul_assign), name!(mul_assign)),
 460             ArithOp::Sub => (name!(sub_assign), name!(sub_assign)),
 461             ArithOp::Div => (name!(div_assign), name!(div_assign)),
 462             ArithOp::Rem => (name!(rem_assign), name!(rem_assign)),
 463             ArithOp::Shl => (name!(shl_assign), name!(shl_assign)),
 464             ArithOp::Shr => (name!(shr_assign), name!(shr_assign)),
 465             ArithOp::BitXor => (name!(bitxor_assign), name!(bitxor_assign)),
 466             ArithOp::BitOr => (name!(bitor_assign), name!(bitor_assign)),
 467             ArithOp::BitAnd => (name!(bitand_assign), name!(bitand_assign)),
 468         },
 469         BinaryOp::CmpOp(cop) => match cop {
 470             CmpOp::Eq { negated: false } => (name!(eq), name!(eq)),
 471             CmpOp::Eq { negated: true } => (name!(ne), name!(eq)),
 472             CmpOp::Ord { ordering: Ordering::Less, strict: false } => {
 473                 (name!(le), name!(partial_ord))
 474             }
 475             CmpOp::Ord { ordering: Ordering::Less, strict: true } => {
 476                 (name!(lt), name!(partial_ord))
 477             }
 478             CmpOp::Ord { ordering: Ordering::Greater, strict: false } => {
 479                 (name!(ge), name!(partial_ord))
 480             }
 481             CmpOp::Ord { ordering: Ordering::Greater, strict: true } => {
 482                 (name!(gt), name!(partial_ord))
 483             }
 484         },
 485         BinaryOp::Assignment { op: None } => return None,
 486     })
 487 }
 488
 489 /// Look up the method with the given name.
 490 pub(crate) fn lookup_method(
 491     db: &dyn HirDatabase,
 492     ty: &Canonical<Ty>,
 493     env: Arc<TraitEnvironment>,
 494     traits_in_scope: &FxHashSet<TraitId>,
 495     visible_from_module: VisibleFromModule,
 496     name: &Name,
 497 ) -> Option<(ReceiverAdjustments, FunctionId, bool)> {
 498     let mut not_visible = None;
 499     let res = iterate_method_candidates(
 500         ty,
 501         db,
 502         env,
 503         traits_in_scope,
 504         visible_from_module,
 505         Some(name),
 506         LookupMode::MethodCall,
 507         |adjustments, f, visible| match f {
 508             AssocItemId::FunctionId(f) if visible => Some((adjustments, f, true)),
 509             AssocItemId::FunctionId(f) if not_visible.is_none() => {
 510                 not_visible = Some((adjustments, f, false));
 511                 None
 512             }
 513             _ => None,
 514         },
 515     );
 516     res.or(not_visible)
 517 }
 518
 519 /// Whether we're looking up a dotted method call (like `v.len()`) or a path
 520 /// (like `Vec::new`).
 521 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 522 pub enum LookupMode {
 523     /// Looking up a method call like `v.len()`: We only consider candidates
 524     /// that have a `self` parameter, and do autoderef.
 525     MethodCall,
 526     /// Looking up a path like `Vec::new` or `Vec::default`: We consider all
 527     /// candidates including associated constants, but don't do autoderef.
 528     Path,
 529 }
 530
 531 #[derive(Clone, Copy)]
 532 pub enum VisibleFromModule {
 533     /// Filter for results that are visible from the given module
 534     Filter(ModuleId),
 535     /// Include impls from the given block.
 536     IncludeBlock(BlockId),
 537     /// Do nothing special in regards visibility
 538     None,
 539 }
 540
 541 impl From<Option<ModuleId>> for VisibleFromModule {
 542     fn from(module: Option<ModuleId>) -> Self {
 543         match module {
 544             Some(module) => Self::Filter(module),
 545             None => Self::None,
 546         }
 547     }
 548 }
 549
 550 impl From<Option<BlockId>> for VisibleFromModule {
 551     fn from(block: Option<BlockId>) -> Self {
 552         match block {
 553             Some(block) => Self::IncludeBlock(block),
 554             None => Self::None,
 555         }
 556     }
 557 }
 558
 559 #[derive(Debug, Clone, Default)]
 560 pub struct ReceiverAdjustments {
 561     autoref: Option<Mutability>,
 562     autoderefs: usize,
 563     unsize_array: bool,
 564 }
 565
 566 impl ReceiverAdjustments {
 567     pub(crate) fn apply(&self, table: &mut InferenceTable<'_>, ty: Ty) -> (Ty, Vec<Adjustment>) {
 568         let mut ty = table.resolve_ty_shallow(&ty);
 569         let mut adjust = Vec::new();
 570         for _ in 0..self.autoderefs {
 571             match autoderef::autoderef_step(table, ty.clone()) {
 572                 None => {
 573                     never!("autoderef not possible for {:?}", ty);
 574                     ty = TyKind::Error.intern(Interner);
 575                     break;
 576                 }
 577                 Some((kind, new_ty)) => {
 578                     ty = new_ty.clone();
 579                     adjust.push(Adjustment {
 580                         kind: Adjust::Deref(match kind {
 581                             // FIXME should we know the mutability here?
 582                             AutoderefKind::Overloaded => Some(OverloadedDeref(Mutability::Not)),
 583                             AutoderefKind::Builtin => None,
 584                         }),
 585                         target: new_ty,
 586                     });
 587                 }
 588             }
 589         }
 590         if self.unsize_array {
 591             ty = match ty.kind(Interner) {
 592                 TyKind::Array(inner, _) => TyKind::Slice(inner.clone()).intern(Interner),
 593                 _ => {
 594                     never!("unsize_array with non-array {:?}", ty);
 595                     ty
 596                 }
 597             };
 598             // FIXME this is kind of wrong since the unsize needs to happen to a pointer/reference
 599             adjust.push(Adjustment {
 600                 kind: Adjust::Pointer(PointerCast::Unsize),
 601                 target: ty.clone(),
 602             });
 603         }
 604         if let Some(m) = self.autoref {
 605             ty = TyKind::Ref(m, static_lifetime(), ty).intern(Interner);
 606             adjust
 607                 .push(Adjustment { kind: Adjust::Borrow(AutoBorrow::Ref(m)), target: ty.clone() });
 608         }
 609         (ty, adjust)
 610     }
 611
 612     fn with_autoref(&self, m: Mutability) -> ReceiverAdjustments {
 613         Self { autoref: Some(m), ..*self }
 614     }
 615 }
 616
 617 // This would be nicer if it just returned an iterator, but that runs into
 618 // lifetime problems, because we need to borrow temp `CrateImplDefs`.
 619 // FIXME add a context type here?
 620 pub(crate) fn iterate_method_candidates<T>(
 621     ty: &Canonical<Ty>,
 622     db: &dyn HirDatabase,
 623     env: Arc<TraitEnvironment>,
 624     traits_in_scope: &FxHashSet<TraitId>,
 625     visible_from_module: VisibleFromModule,
 626     name: Option<&Name>,
 627     mode: LookupMode,
 628     mut callback: impl FnMut(ReceiverAdjustments, AssocItemId, bool) -> Option<T>,
 629 ) -> Option<T> {
 630     let mut slot = None;
 631     iterate_method_candidates_dyn(
 632         ty,
 633         db,
 634         env,
 635         traits_in_scope,
 636         visible_from_module,
 637         name,
 638         mode,
 639         &mut |adj, item, visible| {
 640             assert!(slot.is_none());
 641             if let Some(it) = callback(adj, item, visible) {
 642                 slot = Some(it);
 643                 return ControlFlow::Break(());
 644             }
 645             ControlFlow::Continue(())
 646         },
 647     );
 648     slot
 649 }
 650
 651 pub fn lookup_impl_const(
 652     db: &dyn HirDatabase,
 653     env: Arc<TraitEnvironment>,
 654     const_id: ConstId,
 655     subs: Substitution,
 656 ) -> ConstId {
 657     let trait_id = match const_id.lookup(db.upcast()).container {
 658         ItemContainerId::TraitId(id) => id,
 659         _ => return const_id,
 660     };
 661     let substitution = Substitution::from_iter(Interner, subs.iter(Interner));
 662     let trait_ref = TraitRef { trait_id: to_chalk_trait_id(trait_id), substitution };
 663
 664     let const_data = db.const_data(const_id);
 665     let name = match const_data.name.as_ref() {
 666         Some(name) => name,
 667         None => return const_id,
 668     };
 669
 670     lookup_impl_assoc_item_for_trait_ref(trait_ref, db, env, name)
 671         .and_then(|assoc| if let AssocItemId::ConstId(id) = assoc { Some(id) } else { None })
 672         .unwrap_or(const_id)
 673 }
 674
 675 /// Looks up the impl method that actually runs for the trait method `func`.
 676 ///
 677 /// Returns `func` if it's not a method defined in a trait or the lookup failed.
 678 pub fn lookup_impl_method(
 679     db: &dyn HirDatabase,
 680     env: Arc<TraitEnvironment>,
 681     func: FunctionId,
 682     fn_subst: Substitution,
 683 ) -> FunctionId {
 684     let trait_id = match func.lookup(db.upcast()).container {
 685         ItemContainerId::TraitId(id) => id,
 686         _ => return func,
 687     };
 688     let trait_params = db.generic_params(trait_id.into()).type_or_consts.len();
 689     let fn_params = fn_subst.len(Interner) - trait_params;
 690     let trait_ref = TraitRef {
 691         trait_id: to_chalk_trait_id(trait_id),
 692         substitution: Substitution::from_iter(Interner, fn_subst.iter(Interner).skip(fn_params)),
 693     };
 694
 695     let name = &db.function_data(func).name;
 696     lookup_impl_assoc_item_for_trait_ref(trait_ref, db, env, name)
 697         .and_then(|assoc| if let AssocItemId::FunctionId(id) = assoc { Some(id) } else { None })
 698         .unwrap_or(func)
 699 }
 700
 701 fn lookup_impl_assoc_item_for_trait_ref(
 702     trait_ref: TraitRef,
 703     db: &dyn HirDatabase,
 704     env: Arc<TraitEnvironment>,
 705     name: &Name,
 706 ) -> Option<AssocItemId> {
 707     let self_ty = trait_ref.self_type_parameter(Interner);
 708     let self_ty_fp = TyFingerprint::for_trait_impl(&self_ty)?;
 709     let impls = db.trait_impls_in_deps(env.krate);
 710     let impls = impls.for_trait_and_self_ty(trait_ref.hir_trait_id(), self_ty_fp);
 711
 712     let table = InferenceTable::new(db, env);
 713
 714     let impl_data = find_matching_impl(impls, table, trait_ref)?;
 715     impl_data.items.iter().find_map(|it| match it {
 716         AssocItemId::FunctionId(f) => {
 717             (db.function_data(*f).name == *name).then_some(AssocItemId::FunctionId(*f))
 718         }
 719         AssocItemId::ConstId(c) => db
 720             .const_data(*c)
 721             .name
 722             .as_ref()
 723             .map(|n| *n == *name)
 724             .and_then(|result| if result { Some(AssocItemId::ConstId(*c)) } else { None }),
 725         _ => None,
 726     })
 727 }
 728
 729 fn find_matching_impl(
 730     mut impls: impl Iterator<Item = ImplId>,
 731     mut table: InferenceTable<'_>,
 732     actual_trait_ref: TraitRef,
 733 ) -> Option<Arc<ImplData>> {
 734     let db = table.db;
 735     loop {
 736         let impl_ = impls.next()?;
 737         let r = table.run_in_snapshot(|table| {
 738             let impl_data = db.impl_data(impl_);
 739             let impl_substs =
 740                 TyBuilder::subst_for_def(db, impl_, None).fill_with_inference_vars(table).build();
 741             let trait_ref = db
 742                 .impl_trait(impl_)
 743                 .expect("non-trait method in find_matching_impl")
 744                 .substitute(Interner, &impl_substs);
 745
 746             if !table.unify(&trait_ref, &actual_trait_ref) {
 747                 return None;
 748             }
 749
 750             let wcs = crate::chalk_db::convert_where_clauses(db, impl_.into(), &impl_substs)
 751                 .into_iter()
 752                 .map(|b| b.cast(Interner));
 753             let goal = crate::Goal::all(Interner, wcs);
 754             table.try_obligation(goal).map(|_| impl_data)
 755         });
 756         if r.is_some() {
 757             break r;
 758         }
 759     }
 760 }
 761
 762 pub fn iterate_path_candidates(
 763     ty: &Canonical<Ty>,
 764     db: &dyn HirDatabase,
 765     env: Arc<TraitEnvironment>,
 766     traits_in_scope: &FxHashSet<TraitId>,
 767     visible_from_module: VisibleFromModule,
 768     name: Option<&Name>,
 769     callback: &mut dyn FnMut(AssocItemId) -> ControlFlow<()>,
 770 ) -> ControlFlow<()> {
 771     iterate_method_candidates_dyn(
 772         ty,
 773         db,
 774         env,
 775         traits_in_scope,
 776         visible_from_module,
 777         name,
 778         LookupMode::Path,
 779         // the adjustments are not relevant for path lookup
 780         &mut |_, id, _| callback(id),
 781     )
 782 }
 783
 784 pub fn iterate_method_candidates_dyn(
 785     ty: &Canonical<Ty>,
 786     db: &dyn HirDatabase,
 787     env: Arc<TraitEnvironment>,
 788     traits_in_scope: &FxHashSet<TraitId>,
 789     visible_from_module: VisibleFromModule,
 790     name: Option<&Name>,
 791     mode: LookupMode,
 792     callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
 793 ) -> ControlFlow<()> {
 794     match mode {
 795         LookupMode::MethodCall => {
 796             // For method calls, rust first does any number of autoderef, and
 797             // then one autoref (i.e. when the method takes &self or &mut self).
 798             // Note that when we've got a receiver like &S, even if the method
 799             // we find in the end takes &self, we still do the autoderef step
 800             // (just as rustc does an autoderef and then autoref again).
 801
 802             // We have to be careful about the order we're looking at candidates
 803             // in here. Consider the case where we're resolving `x.clone()`
 804             // where `x: &Vec<_>`. This resolves to the clone method with self
 805             // type `Vec<_>`, *not* `&_`. I.e. we need to consider methods where
 806             // the receiver type exactly matches before cases where we have to
 807             // do autoref. But in the autoderef steps, the `&_` self type comes
 808             // up *before* the `Vec<_>` self type.
 809             //
 810             // On the other hand, we don't want to just pick any by-value method
 811             // before any by-autoref method; it's just that we need to consider
 812             // the methods by autoderef order of *receiver types*, not *self
 813             // types*.
 814
 815             let mut table = InferenceTable::new(db, env.clone());
 816             let ty = table.instantiate_canonical(ty.clone());
 817             let (deref_chain, adj) = autoderef_method_receiver(&mut table, ty);
 818
 819             let result = deref_chain.into_iter().zip(adj).try_for_each(|(receiver_ty, adj)| {
 820                 iterate_method_candidates_with_autoref(
 821                     &receiver_ty,
 822                     adj,
 823                     db,
 824                     env.clone(),
 825                     traits_in_scope,
 826                     visible_from_module,
 827                     name,
 828                     callback,
 829                 )
 830             });
 831             result
 832         }
 833         LookupMode::Path => {
 834             // No autoderef for path lookups
 835             iterate_method_candidates_for_self_ty(
 836                 ty,
 837                 db,
 838                 env,
 839                 traits_in_scope,
 840                 visible_from_module,
 841                 name,
 842                 callback,
 843             )
 844         }
 845     }
 846 }
 847
 848 fn iterate_method_candidates_with_autoref(
 849     receiver_ty: &Canonical<Ty>,
 850     first_adjustment: ReceiverAdjustments,
 851     db: &dyn HirDatabase,
 852     env: Arc<TraitEnvironment>,
 853     traits_in_scope: &FxHashSet<TraitId>,
 854     visible_from_module: VisibleFromModule,
 855     name: Option<&Name>,
 856     mut callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
 857 ) -> ControlFlow<()> {
 858     if receiver_ty.value.is_general_var(Interner, &receiver_ty.binders) {
 859         // don't try to resolve methods on unknown types
 860         return ControlFlow::Continue(());
 861     }
 862
 863     iterate_method_candidates_by_receiver(
 864         receiver_ty,
 865         first_adjustment.clone(),
 866         db,
 867         env.clone(),
 868         traits_in_scope,
 869         visible_from_module,
 870         name,
 871         &mut callback,
 872     )?;
 873
 874     let refed = Canonical {
 875         value: TyKind::Ref(Mutability::Not, static_lifetime(), receiver_ty.value.clone())
 876             .intern(Interner),
 877         binders: receiver_ty.binders.clone(),
 878     };
 879
 880     iterate_method_candidates_by_receiver(
 881         &refed,
 882         first_adjustment.with_autoref(Mutability::Not),
 883         db,
 884         env.clone(),
 885         traits_in_scope,
 886         visible_from_module,
 887         name,
 888         &mut callback,
 889     )?;
 890
 891     let ref_muted = Canonical {
 892         value: TyKind::Ref(Mutability::Mut, static_lifetime(), receiver_ty.value.clone())
 893             .intern(Interner),
 894         binders: receiver_ty.binders.clone(),
 895     };
 896
 897     iterate_method_candidates_by_receiver(
 898         &ref_muted,
 899         first_adjustment.with_autoref(Mutability::Mut),
 900         db,
 901         env,
 902         traits_in_scope,
 903         visible_from_module,
 904         name,
 905         &mut callback,
 906     )
 907 }
 908
 909 fn iterate_method_candidates_by_receiver(
 910     receiver_ty: &Canonical<Ty>,
 911     receiver_adjustments: ReceiverAdjustments,
 912     db: &dyn HirDatabase,
 913     env: Arc<TraitEnvironment>,
 914     traits_in_scope: &FxHashSet<TraitId>,
 915     visible_from_module: VisibleFromModule,
 916     name: Option<&Name>,
 917     mut callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
 918 ) -> ControlFlow<()> {
 919     let mut table = InferenceTable::new(db, env);
 920     let receiver_ty = table.instantiate_canonical(receiver_ty.clone());
 921     let snapshot = table.snapshot();
 922     // We're looking for methods with *receiver* type receiver_ty. These could
 923     // be found in any of the derefs of receiver_ty, so we have to go through
 924     // that.
 925     let mut autoderef = autoderef::Autoderef::new(&mut table, receiver_ty.clone());
 926     while let Some((self_ty, _)) = autoderef.next() {
 927         iterate_inherent_methods(
 928             &self_ty,
 929             autoderef.table,
 930             name,
 931             Some(&receiver_ty),
 932             Some(receiver_adjustments.clone()),
 933             visible_from_module,
 934             &mut callback,
 935         )?
 936     }
 937
 938     table.rollback_to(snapshot);
 939
 940     let mut autoderef = autoderef::Autoderef::new(&mut table, receiver_ty.clone());
 941     while let Some((self_ty, _)) = autoderef.next() {
 942         iterate_trait_method_candidates(
 943             &self_ty,
 944             autoderef.table,
 945             traits_in_scope,
 946             name,
 947             Some(&receiver_ty),
 948             Some(receiver_adjustments.clone()),
 949             &mut callback,
 950         )?
 951     }
 952
 953     ControlFlow::Continue(())
 954 }
 955
 956 fn iterate_method_candidates_for_self_ty(
 957     self_ty: &Canonical<Ty>,
 958     db: &dyn HirDatabase,
 959     env: Arc<TraitEnvironment>,
 960     traits_in_scope: &FxHashSet<TraitId>,
 961     visible_from_module: VisibleFromModule,
 962     name: Option<&Name>,
 963     mut callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
 964 ) -> ControlFlow<()> {
 965     let mut table = InferenceTable::new(db, env);
 966     let self_ty = table.instantiate_canonical(self_ty.clone());
 967     iterate_inherent_methods(
 968         &self_ty,
 969         &mut table,
 970         name,
 971         None,
 972         None,
 973         visible_from_module,
 974         &mut callback,
 975     )?;
 976     iterate_trait_method_candidates(
 977         &self_ty,
 978         &mut table,
 979         traits_in_scope,
 980         name,
 981         None,
 982         None,
 983         callback,
 984     )
 985 }
 986
 987 fn iterate_trait_method_candidates(
 988     self_ty: &Ty,
 989     table: &mut InferenceTable<'_>,
 990     traits_in_scope: &FxHashSet<TraitId>,
 991     name: Option<&Name>,
 992     receiver_ty: Option<&Ty>,
 993     receiver_adjustments: Option<ReceiverAdjustments>,
 994     callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
 995 ) -> ControlFlow<()> {
 996     let db = table.db;
 997     let env = table.trait_env.clone();
 998     let self_is_array = matches!(self_ty.kind(Interner), chalk_ir::TyKind::Array(..));
 999
1000     let canonical_self_ty = table.canonicalize(self_ty.clone()).value;
1001
1002     'traits: for &t in traits_in_scope {
1003         let data = db.trait_data(t);
1004
1005         // Traits annotated with `#[rustc_skip_array_during_method_dispatch]` are skipped during
1006         // method resolution, if the receiver is an array, and we're compiling for editions before
1007         // 2021.
1008         // This is to make `[a].into_iter()` not break code with the new `IntoIterator` impl for
1009         // arrays.
1010         if data.skip_array_during_method_dispatch && self_is_array {
1011             // FIXME: this should really be using the edition of the method name's span, in case it
1012             // comes from a macro
1013             if db.crate_graph()[env.krate].edition < Edition::Edition2021 {
1014                 continue;
1015             }
1016         }
1017
1018         // we'll be lazy about checking whether the type implements the
1019         // trait, but if we find out it doesn't, we'll skip the rest of the
1020         // iteration
1021         let mut known_implemented = false;
1022         for &(_, item) in data.items.iter() {
1023             // Don't pass a `visible_from_module` down to `is_valid_candidate`,
1024             // since only inherent methods should be included into visibility checking.
1025             let visible = match is_valid_candidate(table, name, receiver_ty, item, self_ty, None) {
1026                 IsValidCandidate::Yes => true,
1027                 IsValidCandidate::NotVisible => false,
1028                 IsValidCandidate::No => continue,
1029             };
1030             if !known_implemented {
1031                 let goal = generic_implements_goal(db, env.clone(), t, &canonical_self_ty);
1032                 if db.trait_solve(env.krate, goal.cast(Interner)).is_none() {
1033                     continue 'traits;
1034                 }
1035             }
1036             known_implemented = true;
1037             callback(receiver_adjustments.clone().unwrap_or_default(), item, visible)?;
1038         }
1039     }
1040     ControlFlow::Continue(())
1041 }
1042
1043 fn iterate_inherent_methods(
1044     self_ty: &Ty,
1045     table: &mut InferenceTable<'_>,
1046     name: Option<&Name>,
1047     receiver_ty: Option<&Ty>,
1048     receiver_adjustments: Option<ReceiverAdjustments>,
1049     visible_from_module: VisibleFromModule,
1050     callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
1051 ) -> ControlFlow<()> {
1052     let db = table.db;
1053     let env = table.trait_env.clone();
1054
1055     // For trait object types and placeholder types with trait bounds, the methods of the trait and
1056     // its super traits are considered inherent methods. This matters because these methods have
1057     // higher priority than the other traits' methods, which would be considered in
1058     // `iterate_trait_method_candidates()` only after this function.
1059     match self_ty.kind(Interner) {
1060         TyKind::Placeholder(_) => {
1061             let env = table.trait_env.clone();
1062             let traits = env
1063                 .traits_in_scope_from_clauses(self_ty.clone())
1064                 .flat_map(|t| all_super_traits(db.upcast(), t));
1065             iterate_inherent_trait_methods(
1066                 self_ty,
1067                 table,
1068                 name,
1069                 receiver_ty,
1070                 receiver_adjustments.clone(),
1071                 callback,
1072                 traits,
1073             )?;
1074         }
1075         TyKind::Dyn(_) => {
1076             if let Some(principal_trait) = self_ty.dyn_trait() {
1077                 let traits = all_super_traits(db.upcast(), principal_trait);
1078                 iterate_inherent_trait_methods(
1079                     self_ty,
1080                     table,
1081                     name,
1082                     receiver_ty,
1083                     receiver_adjustments.clone(),
1084                     callback,
1085                     traits.into_iter(),
1086                 )?;
1087             }
1088         }
1089         _ => {}
1090     }
1091
1092     let def_crates = match def_crates(db, self_ty, env.krate) {
1093         Some(k) => k,
1094         None => return ControlFlow::Continue(()),
1095     };
1096
1097     let (module, block) = match visible_from_module {
1098         VisibleFromModule::Filter(module) => (Some(module), module.containing_block()),
1099         VisibleFromModule::IncludeBlock(block) => (None, Some(block)),
1100         VisibleFromModule::None => (None, None),
1101     };
1102
1103     if let Some(block_id) = block {
1104         if let Some(impls) = db.inherent_impls_in_block(block_id) {
1105             impls_for_self_ty(
1106                 &impls,
1107                 self_ty,
1108                 table,
1109                 name,
1110                 receiver_ty,
1111                 receiver_adjustments.clone(),
1112                 module,
1113                 callback,
1114             )?;
1115         }
1116     }
1117
1118     for krate in def_crates {
1119         let impls = db.inherent_impls_in_crate(krate);
1120         impls_for_self_ty(
1121             &impls,
1122             self_ty,
1123             table,
1124             name,
1125             receiver_ty,
1126             receiver_adjustments.clone(),
1127             module,
1128             callback,
1129         )?;
1130     }
1131     return ControlFlow::Continue(());
1132
1133     fn iterate_inherent_trait_methods(
1134         self_ty: &Ty,
1135         table: &mut InferenceTable<'_>,
1136         name: Option<&Name>,
1137         receiver_ty: Option<&Ty>,
1138         receiver_adjustments: Option<ReceiverAdjustments>,
1139         callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
1140         traits: impl Iterator<Item = TraitId>,
1141     ) -> ControlFlow<()> {
1142         let db = table.db;
1143         for t in traits {
1144             let data = db.trait_data(t);
1145             for &(_, item) in data.items.iter() {
1146                 // We don't pass `visible_from_module` as all trait items should be visible.
1147                 let visible =
1148                     match is_valid_candidate(table, name, receiver_ty, item, self_ty, None) {
1149                         IsValidCandidate::Yes => true,
1150                         IsValidCandidate::NotVisible => false,
1151                         IsValidCandidate::No => continue,
1152                     };
1153                 callback(receiver_adjustments.clone().unwrap_or_default(), item, visible)?;
1154             }
1155         }
1156         ControlFlow::Continue(())
1157     }
1158
1159     fn impls_for_self_ty(
1160         impls: &InherentImpls,
1161         self_ty: &Ty,
1162         table: &mut InferenceTable<'_>,
1163         name: Option<&Name>,
1164         receiver_ty: Option<&Ty>,
1165         receiver_adjustments: Option<ReceiverAdjustments>,
1166         visible_from_module: Option<ModuleId>,
1167         callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>,
1168     ) -> ControlFlow<()> {
1169         let db = table.db;
1170         let impls_for_self_ty = impls.for_self_ty(self_ty);
1171         for &impl_def in impls_for_self_ty {
1172             for &item in &db.impl_data(impl_def).items {
1173                 let visible = match is_valid_candidate(
1174                     table,
1175                     name,
1176                     receiver_ty,
1177                     item,
1178                     self_ty,
1179                     visible_from_module,
1180                 ) {
1181                     IsValidCandidate::Yes => true,
1182                     IsValidCandidate::NotVisible => false,
1183                     IsValidCandidate::No => continue,
1184                 };
1185                 callback(receiver_adjustments.clone().unwrap_or_default(), item, visible)?;
1186             }
1187         }
1188         ControlFlow::Continue(())
1189     }
1190 }
1191
1192 /// Returns the receiver type for the index trait call.
1193 pub fn resolve_indexing_op(
1194     db: &dyn HirDatabase,
1195     env: Arc<TraitEnvironment>,
1196     ty: Canonical<Ty>,
1197     index_trait: TraitId,
1198 ) -> Option<ReceiverAdjustments> {
1199     let mut table = InferenceTable::new(db, env.clone());
1200     let ty = table.instantiate_canonical(ty);
1201     let (deref_chain, adj) = autoderef_method_receiver(&mut table, ty);
1202     for (ty, adj) in deref_chain.into_iter().zip(adj) {
1203         let goal = generic_implements_goal(db, env.clone(), index_trait, &ty);
1204         if db.trait_solve(env.krate, goal.cast(Interner)).is_some() {
1205             return Some(adj);
1206         }
1207     }
1208     None
1209 }
1210
1211 macro_rules! check_that {
1212     ($cond:expr) => {
1213         if !$cond {
1214             return IsValidCandidate::No;
1215         }
1216     };
1217 }
1218
1219 fn is_valid_candidate(
1220     table: &mut InferenceTable<'_>,
1221     name: Option<&Name>,
1222     receiver_ty: Option<&Ty>,
1223     item: AssocItemId,
1224     self_ty: &Ty,
1225     visible_from_module: Option<ModuleId>,
1226 ) -> IsValidCandidate {
1227     let db = table.db;
1228     match item {
1229         AssocItemId::FunctionId(m) => {
1230             is_valid_fn_candidate(table, m, name, receiver_ty, self_ty, visible_from_module)
1231         }
1232         AssocItemId::ConstId(c) => {
1233             let data = db.const_data(c);
1234             check_that!(receiver_ty.is_none());
1235
1236             check_that!(name.map_or(true, |n| data.name.as_ref() == Some(n)));
1237
1238             if let Some(from_module) = visible_from_module {
1239                 if !db.const_visibility(c).is_visible_from(db.upcast(), from_module) {
1240                     cov_mark::hit!(const_candidate_not_visible);
1241                     return IsValidCandidate::NotVisible;
1242                 }
1243             }
1244             if let ItemContainerId::ImplId(impl_id) = c.lookup(db.upcast()).container {
1245                 let self_ty_matches = table.run_in_snapshot(|table| {
1246                     let expected_self_ty = TyBuilder::impl_self_ty(db, impl_id)
1247                         .fill_with_inference_vars(table)
1248                         .build();
1249                     table.unify(&expected_self_ty, self_ty)
1250                 });
1251                 if !self_ty_matches {
1252                     cov_mark::hit!(const_candidate_self_type_mismatch);
1253                     return IsValidCandidate::No;
1254                 }
1255             }
1256             IsValidCandidate::Yes
1257         }
1258         _ => IsValidCandidate::No,
1259     }
1260 }
1261
1262 enum IsValidCandidate {
1263     Yes,
1264     No,
1265     NotVisible,
1266 }
1267
1268 fn is_valid_fn_candidate(
1269     table: &mut InferenceTable<'_>,
1270     fn_id: FunctionId,
1271     name: Option<&Name>,
1272     receiver_ty: Option<&Ty>,
1273     self_ty: &Ty,
1274     visible_from_module: Option<ModuleId>,
1275 ) -> IsValidCandidate {
1276     let db = table.db;
1277     let data = db.function_data(fn_id);
1278
1279     check_that!(name.map_or(true, |n| n == &data.name));
1280     if let Some(from_module) = visible_from_module {
1281         if !db.function_visibility(fn_id).is_visible_from(db.upcast(), from_module) {
1282             cov_mark::hit!(autoderef_candidate_not_visible);
1283             return IsValidCandidate::NotVisible;
1284         }
1285     }
1286     table.run_in_snapshot(|table| {
1287         let container = fn_id.lookup(db.upcast()).container;
1288         let (impl_subst, expect_self_ty) = match container {
1289             ItemContainerId::ImplId(it) => {
1290                 let subst =
1291                     TyBuilder::subst_for_def(db, it, None).fill_with_inference_vars(table).build();
1292                 let self_ty = db.impl_self_ty(it).substitute(Interner, &subst);
1293                 (subst, self_ty)
1294             }
1295             ItemContainerId::TraitId(it) => {
1296                 let subst =
1297                     TyBuilder::subst_for_def(db, it, None).fill_with_inference_vars(table).build();
1298                 let self_ty = subst.at(Interner, 0).assert_ty_ref(Interner).clone();
1299                 (subst, self_ty)
1300             }
1301             _ => unreachable!(),
1302         };
1303
1304         let fn_subst = TyBuilder::subst_for_def(db, fn_id, Some(impl_subst.clone()))
1305             .fill_with_inference_vars(table)
1306             .build();
1307
1308         check_that!(table.unify(&expect_self_ty, self_ty));
1309
1310         if let Some(receiver_ty) = receiver_ty {
1311             check_that!(data.has_self_param());
1312
1313             let sig = db.callable_item_signature(fn_id.into());
1314             let expected_receiver =
1315                 sig.map(|s| s.params()[0].clone()).substitute(Interner, &fn_subst);
1316
1317             check_that!(table.unify(receiver_ty, &expected_receiver));
1318         }
1319
1320         if let ItemContainerId::ImplId(impl_id) = container {
1321             // We need to consider the bounds on the impl to distinguish functions of the same name
1322             // for a type.
1323             let predicates = db.generic_predicates(impl_id.into());
1324             let valid = predicates
1325                 .iter()
1326                 .map(|predicate| {
1327                     let (p, b) = predicate
1328                         .clone()
1329                         .substitute(Interner, &impl_subst)
1330                         // Skipping the inner binders is ok, as we don't handle quantified where
1331                         // clauses yet.
1332                         .into_value_and_skipped_binders();
1333                     stdx::always!(b.len(Interner) == 0);
1334                     p
1335                 })
1336                 // It's ok to get ambiguity here, as we may not have enough information to prove
1337                 // obligations. We'll check if the user is calling the selected method properly
1338                 // later anyway.
1339                 .all(|p| table.try_obligation(p.cast(Interner)).is_some());
1340             match valid {
1341                 true => IsValidCandidate::Yes,
1342                 false => IsValidCandidate::No,
1343             }
1344         } else {
1345             // For `ItemContainerId::TraitId`, we check if `self_ty` implements the trait in
1346             // `iterate_trait_method_candidates()`.
1347             // For others, this function shouldn't be called.
1348             IsValidCandidate::Yes
1349         }
1350     })
1351 }
1352
1353 pub fn implements_trait(
1354     ty: &Canonical<Ty>,
1355     db: &dyn HirDatabase,
1356     env: Arc<TraitEnvironment>,
1357     trait_: TraitId,
1358 ) -> bool {
1359     let goal = generic_implements_goal(db, env.clone(), trait_, ty);
1360     let solution = db.trait_solve(env.krate, goal.cast(Interner));
1361
1362     solution.is_some()
1363 }
1364
1365 pub fn implements_trait_unique(
1366     ty: &Canonical<Ty>,
1367     db: &dyn HirDatabase,
1368     env: Arc<TraitEnvironment>,
1369     trait_: TraitId,
1370 ) -> bool {
1371     let goal = generic_implements_goal(db, env.clone(), trait_, ty);
1372     let solution = db.trait_solve(env.krate, goal.cast(Interner));
1373
1374     matches!(solution, Some(crate::Solution::Unique(_)))
1375 }
1376
1377 /// This creates Substs for a trait with the given Self type and type variables
1378 /// for all other parameters, to query Chalk with it.
1379 fn generic_implements_goal(
1380     db: &dyn HirDatabase,
1381     env: Arc<TraitEnvironment>,
1382     trait_: TraitId,
1383     self_ty: &Canonical<Ty>,
1384 ) -> Canonical<InEnvironment<super::DomainGoal>> {
1385     let mut kinds = self_ty.binders.interned().to_vec();
1386     let trait_ref = TyBuilder::trait_ref(db, trait_)
1387         .push(self_ty.value.clone())
1388         .fill_with_bound_vars(DebruijnIndex::INNERMOST, kinds.len())
1389         .build();
1390     kinds.extend(trait_ref.substitution.iter(Interner).skip(1).map(|x| {
1391         let vk = match x.data(Interner) {
1392             chalk_ir::GenericArgData::Ty(_) => {
1393                 chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General)
1394             }
1395             chalk_ir::GenericArgData::Lifetime(_) => chalk_ir::VariableKind::Lifetime,
1396             chalk_ir::GenericArgData::Const(c) => {
1397                 chalk_ir::VariableKind::Const(c.data(Interner).ty.clone())
1398             }
1399         };
1400         chalk_ir::WithKind::new(vk, UniverseIndex::ROOT)
1401     }));
1402     let obligation = trait_ref.cast(Interner);
1403     Canonical {
1404         binders: CanonicalVarKinds::from_iter(Interner, kinds),
1405         value: InEnvironment::new(&env.env, obligation),
1406     }
1407 }
1408
1409 fn autoderef_method_receiver(
1410     table: &mut InferenceTable<'_>,
1411     ty: Ty,
1412 ) -> (Vec<Canonical<Ty>>, Vec<ReceiverAdjustments>) {
1413     let (mut deref_chain, mut adjustments): (Vec<_>, Vec<_>) = (Vec::new(), Vec::new());
1414     let mut autoderef = autoderef::Autoderef::new(table, ty);
1415     while let Some((ty, derefs)) = autoderef.next() {
1416         deref_chain.push(autoderef.table.canonicalize(ty).value);
1417         adjustments.push(ReceiverAdjustments {
1418             autoref: None,
1419             autoderefs: derefs,
1420             unsize_array: false,
1421         });
1422     }
1423     // As a last step, we can do array unsizing (that's the only unsizing that rustc does for method receivers!)
1424     if let (Some((TyKind::Array(parameters, _), binders)), Some(adj)) = (
1425         deref_chain.last().map(|ty| (ty.value.kind(Interner), ty.binders.clone())),
1426         adjustments.last().cloned(),
1427     ) {
1428         let unsized_ty = TyKind::Slice(parameters.clone()).intern(Interner);
1429         deref_chain.push(Canonical { value: unsized_ty, binders });
1430         adjustments.push(ReceiverAdjustments { unsize_array: true, ..adj });
1431     }
1432     (deref_chain, adjustments)
1433 }