crates/hir_ty/src/method_resolution.rs

   1 //! This module is concerned with finding methods that a given type provides.
   2 //! For details about how this works in rustc, see the method lookup page in the
   3 //! [rustc guide](https://rust-lang.github.io/rustc-guide/method-lookup.html)
   4 //! and the corresponding code mostly in librustc_typeck/check/method/probe.rs.
   5 use std::{iter, sync::Arc};
   6
   7 use arrayvec::ArrayVec;
   8 use base_db::CrateId;
   9 use hir_def::{
  10     builtin_type::{IntBitness, Signedness},
  11     lang_item::LangItemTarget,
  12     type_ref::Mutability,
  13     AssocContainerId, AssocItemId, FunctionId, HasModule, ImplId, Lookup, TraitId,
  14 };
  15 use hir_expand::name::Name;
  16 use rustc_hash::{FxHashMap, FxHashSet};
  17
  18 use super::Substs;
  19 use crate::{
  20     autoderef,
  21     db::HirDatabase,
  22     primitive::{FloatBitness, FloatTy, IntTy},
  23     utils::all_super_traits,
  24     ApplicationTy, Canonical, DebruijnIndex, InEnvironment, TraitEnvironment, TraitRef, Ty, TyKind,
  25     TypeCtor, TypeWalk,
  26 };
  27
  28 /// This is used as a key for indexing impls.
  29 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
  30 pub enum TyFingerprint {
  31     Apply(TypeCtor),
  32 }
  33
  34 impl TyFingerprint {
  35     /// Creates a TyFingerprint for looking up an impl. Only certain types can
  36     /// have impls: if we have some `struct S`, we can have an `impl S`, but not
  37     /// `impl &S`. Hence, this will return `None` for reference types and such.
  38     pub(crate) fn for_impl(ty: &Ty) -> Option<TyFingerprint> {
  39         match ty {
  40             Ty::Apply(a_ty) => Some(TyFingerprint::Apply(a_ty.ctor)),
  41             _ => None,
  42         }
  43     }
  44 }
  45
  46 pub(crate) const ALL_INT_FPS: [TyFingerprint; 12] = [
  47     TyFingerprint::Apply(TypeCtor::Int(IntTy {
  48         signedness: Signedness::Unsigned,
  49         bitness: IntBitness::X8,
  50     })),
  51     TyFingerprint::Apply(TypeCtor::Int(IntTy {
  52         signedness: Signedness::Unsigned,
  53         bitness: IntBitness::X16,
  54     })),
  55     TyFingerprint::Apply(TypeCtor::Int(IntTy {
  56         signedness: Signedness::Unsigned,
  57         bitness: IntBitness::X32,
  58     })),
  59     TyFingerprint::Apply(TypeCtor::Int(IntTy {
  60         signedness: Signedness::Unsigned,
  61         bitness: IntBitness::X64,
  62     })),
  63     TyFingerprint::Apply(TypeCtor::Int(IntTy {
  64         signedness: Signedness::Unsigned,
  65         bitness: IntBitness::X128,
  66     })),
  67     TyFingerprint::Apply(TypeCtor::Int(IntTy {
  68         signedness: Signedness::Unsigned,
  69         bitness: IntBitness::Xsize,
  70     })),
  71     TyFingerprint::Apply(TypeCtor::Int(IntTy {
  72         signedness: Signedness::Signed,
  73         bitness: IntBitness::X8,
  74     })),
  75     TyFingerprint::Apply(TypeCtor::Int(IntTy {
  76         signedness: Signedness::Signed,
  77         bitness: IntBitness::X16,
  78     })),
  79     TyFingerprint::Apply(TypeCtor::Int(IntTy {
  80         signedness: Signedness::Signed,
  81         bitness: IntBitness::X32,
  82     })),
  83     TyFingerprint::Apply(TypeCtor::Int(IntTy {
  84         signedness: Signedness::Signed,
  85         bitness: IntBitness::X64,
  86     })),
  87     TyFingerprint::Apply(TypeCtor::Int(IntTy {
  88         signedness: Signedness::Signed,
  89         bitness: IntBitness::X128,
  90     })),
  91     TyFingerprint::Apply(TypeCtor::Int(IntTy {
  92         signedness: Signedness::Signed,
  93         bitness: IntBitness::Xsize,
  94     })),
  95 ];
  96
  97 pub(crate) const ALL_FLOAT_FPS: [TyFingerprint; 2] = [
  98     TyFingerprint::Apply(TypeCtor::Float(FloatTy { bitness: FloatBitness::X32 })),
  99     TyFingerprint::Apply(TypeCtor::Float(FloatTy { bitness: FloatBitness::X64 })),
 100 ];
 101
 102 /// Trait impls defined or available in some crate.
 103 #[derive(Debug, Eq, PartialEq)]
 104 pub struct TraitImpls {
 105     // If the `Option<TyFingerprint>` is `None`, the impl may apply to any self type.
 106     map: FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Vec<ImplId>>>,
 107 }
 108
 109 impl TraitImpls {
 110     pub(crate) fn trait_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
 111         let _p = profile::span("trait_impls_in_crate_query");
 112         let mut impls = Self { map: FxHashMap::default() };
 113
 114         let crate_def_map = db.crate_def_map(krate);
 115         for (_module_id, module_data) in crate_def_map.modules.iter() {
 116             for impl_id in module_data.scope.impls() {
 117                 let target_trait = match db.impl_trait(impl_id) {
 118                     Some(tr) => tr.value.trait_,
 119                     None => continue,
 120                 };
 121                 let self_ty = db.impl_self_ty(impl_id);
 122                 let self_ty_fp = TyFingerprint::for_impl(&self_ty.value);
 123                 impls
 124                     .map
 125                     .entry(target_trait)
 126                     .or_default()
 127                     .entry(self_ty_fp)
 128                     .or_default()
 129                     .push(impl_id);
 130             }
 131         }
 132
 133         Arc::new(impls)
 134     }
 135
 136     pub(crate) fn trait_impls_in_deps_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
 137         let _p = profile::span("trait_impls_in_deps_query");
 138         let crate_graph = db.crate_graph();
 139         let mut res = Self { map: FxHashMap::default() };
 140
 141         for krate in crate_graph.transitive_deps(krate) {
 142             res.merge(&db.trait_impls_in_crate(krate));
 143         }
 144
 145         Arc::new(res)
 146     }
 147
 148     fn merge(&mut self, other: &Self) {
 149         for (trait_, other_map) in &other.map {
 150             let map = self.map.entry(*trait_).or_default();
 151             for (fp, impls) in other_map {
 152                 let vec = map.entry(*fp).or_default();
 153                 vec.extend(impls);
 154             }
 155         }
 156     }
 157
 158     /// Queries all impls of the given trait.
 159     pub fn for_trait(&self, trait_: TraitId) -> impl Iterator<Item = ImplId> + '_ {
 160         self.map
 161             .get(&trait_)
 162             .into_iter()
 163             .flat_map(|map| map.values().flat_map(|v| v.iter().copied()))
 164     }
 165
 166     /// Queries all impls of `trait_` that may apply to `self_ty`.
 167     pub fn for_trait_and_self_ty(
 168         &self,
 169         trait_: TraitId,
 170         self_ty: TyFingerprint,
 171     ) -> impl Iterator<Item = ImplId> + '_ {
 172         self.map
 173             .get(&trait_)
 174             .into_iter()
 175             .flat_map(move |map| map.get(&None).into_iter().chain(map.get(&Some(self_ty))))
 176             .flat_map(|v| v.iter().copied())
 177     }
 178
 179     pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ {
 180         self.map.values().flat_map(|map| map.values().flat_map(|v| v.iter().copied()))
 181     }
 182 }
 183
 184 /// Inherent impls defined in some crate.
 185 ///
 186 /// Inherent impls can only be defined in the crate that also defines the self type of the impl
 187 /// (note that some primitives are considered to be defined by both libcore and liballoc).
 188 ///
 189 /// This makes inherent impl lookup easier than trait impl lookup since we only have to consider a
 190 /// single crate.
 191 #[derive(Debug, Eq, PartialEq)]
 192 pub struct InherentImpls {
 193     map: FxHashMap<TyFingerprint, Vec<ImplId>>,
 194 }
 195
 196 impl InherentImpls {
 197     pub(crate) fn inherent_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
 198         let mut map: FxHashMap<_, Vec<_>> = FxHashMap::default();
 199
 200         let crate_def_map = db.crate_def_map(krate);
 201         for (_module_id, module_data) in crate_def_map.modules.iter() {
 202             for impl_id in module_data.scope.impls() {
 203                 let data = db.impl_data(impl_id);
 204                 if data.target_trait.is_some() {
 205                     continue;
 206                 }
 207
 208                 let self_ty = db.impl_self_ty(impl_id);
 209                 if let Some(fp) = TyFingerprint::for_impl(&self_ty.value) {
 210                     map.entry(fp).or_default().push(impl_id);
 211                 }
 212             }
 213         }
 214
 215         Arc::new(Self { map })
 216     }
 217
 218     pub fn for_self_ty(&self, self_ty: &Ty) -> &[ImplId] {
 219         match TyFingerprint::for_impl(self_ty) {
 220             Some(fp) => self.map.get(&fp).map(|vec| vec.as_ref()).unwrap_or(&[]),
 221             None => &[],
 222         }
 223     }
 224
 225     pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ {
 226         self.map.values().flat_map(|v| v.iter().copied())
 227     }
 228 }
 229
 230 impl Ty {
 231     pub fn def_crates(
 232         &self,
 233         db: &dyn HirDatabase,
 234         cur_crate: CrateId,
 235     ) -> Option<ArrayVec<[CrateId; 2]>> {
 236         // Types like slice can have inherent impls in several crates, (core and alloc).
 237         // The corresponding impls are marked with lang items, so we can use them to find the required crates.
 238         macro_rules! lang_item_crate {
 239             ($($name:expr),+ $(,)?) => {{
 240                 let mut v = ArrayVec::<[LangItemTarget; 2]>::new();
 241                 $(
 242                     v.extend(db.lang_item(cur_crate, $name.into()));
 243                 )+
 244                 v
 245             }};
 246         }
 247
 248         let lang_item_targets = match self {
 249             Ty::Apply(a_ty) => match a_ty.ctor {
 250                 TypeCtor::Adt(def_id) => {
 251                     return Some(std::iter::once(def_id.module(db.upcast()).krate).collect())
 252                 }
 253                 TypeCtor::ForeignType(type_alias_id) => {
 254                     return Some(
 255                         std::iter::once(
 256                             type_alias_id.lookup(db.upcast()).module(db.upcast()).krate,
 257                         )
 258                         .collect(),
 259                     )
 260                 }
 261                 TypeCtor::Bool => lang_item_crate!("bool"),
 262                 TypeCtor::Char => lang_item_crate!("char"),
 263                 TypeCtor::Float(f) => match f.bitness {
 264                     // There are two lang items: one in libcore (fXX) and one in libstd (fXX_runtime)
 265                     FloatBitness::X32 => lang_item_crate!("f32", "f32_runtime"),
 266                     FloatBitness::X64 => lang_item_crate!("f64", "f64_runtime"),
 267                 },
 268                 TypeCtor::Int(i) => lang_item_crate!(i.ty_to_string()),
 269                 TypeCtor::Str => lang_item_crate!("str_alloc", "str"),
 270                 TypeCtor::Slice => lang_item_crate!("slice_alloc", "slice"),
 271                 TypeCtor::RawPtr(Mutability::Shared) => lang_item_crate!("const_ptr"),
 272                 TypeCtor::RawPtr(Mutability::Mut) => lang_item_crate!("mut_ptr"),
 273                 _ => return None,
 274             },
 275             _ => return None,
 276         };
 277         let res = lang_item_targets
 278             .into_iter()
 279             .filter_map(|it| match it {
 280                 LangItemTarget::ImplDefId(it) => Some(it),
 281                 _ => None,
 282             })
 283             .map(|it| it.lookup(db.upcast()).container.module(db.upcast()).krate)
 284             .collect();
 285         Some(res)
 286     }
 287 }
 288 /// Look up the method with the given name, returning the actual autoderefed
 289 /// receiver type (but without autoref applied yet).
 290 pub(crate) fn lookup_method(
 291     ty: &Canonical<Ty>,
 292     db: &dyn HirDatabase,
 293     env: Arc<TraitEnvironment>,
 294     krate: CrateId,
 295     traits_in_scope: &FxHashSet<TraitId>,
 296     name: &Name,
 297 ) -> Option<(Ty, FunctionId)> {
 298     iterate_method_candidates(
 299         ty,
 300         db,
 301         env,
 302         krate,
 303         &traits_in_scope,
 304         Some(name),
 305         LookupMode::MethodCall,
 306         |ty, f| match f {
 307             AssocItemId::FunctionId(f) => Some((ty.clone(), f)),
 308             _ => None,
 309         },
 310     )
 311 }
 312
 313 /// Whether we're looking up a dotted method call (like `v.len()`) or a path
 314 /// (like `Vec::new`).
 315 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 316 pub enum LookupMode {
 317     /// Looking up a method call like `v.len()`: We only consider candidates
 318     /// that have a `self` parameter, and do autoderef.
 319     MethodCall,
 320     /// Looking up a path like `Vec::new` or `Vec::default`: We consider all
 321     /// candidates including associated constants, but don't do autoderef.
 322     Path,
 323 }
 324
 325 // This would be nicer if it just returned an iterator, but that runs into
 326 // lifetime problems, because we need to borrow temp `CrateImplDefs`.
 327 // FIXME add a context type here?
 328 pub fn iterate_method_candidates<T>(
 329     ty: &Canonical<Ty>,
 330     db: &dyn HirDatabase,
 331     env: Arc<TraitEnvironment>,
 332     krate: CrateId,
 333     traits_in_scope: &FxHashSet<TraitId>,
 334     name: Option<&Name>,
 335     mode: LookupMode,
 336     mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
 337 ) -> Option<T> {
 338     let mut slot = None;
 339     iterate_method_candidates_impl(
 340         ty,
 341         db,
 342         env,
 343         krate,
 344         traits_in_scope,
 345         name,
 346         mode,
 347         &mut |ty, item| {
 348             assert!(slot.is_none());
 349             slot = callback(ty, item);
 350             slot.is_some()
 351         },
 352     );
 353     slot
 354 }
 355
 356 fn iterate_method_candidates_impl(
 357     ty: &Canonical<Ty>,
 358     db: &dyn HirDatabase,
 359     env: Arc<TraitEnvironment>,
 360     krate: CrateId,
 361     traits_in_scope: &FxHashSet<TraitId>,
 362     name: Option<&Name>,
 363     mode: LookupMode,
 364     callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool,
 365 ) -> bool {
 366     match mode {
 367         LookupMode::MethodCall => {
 368             // For method calls, rust first does any number of autoderef, and then one
 369             // autoref (i.e. when the method takes &self or &mut self). We just ignore
 370             // the autoref currently -- when we find a method matching the given name,
 371             // we assume it fits.
 372
 373             // Also note that when we've got a receiver like &S, even if the method we
 374             // find in the end takes &self, we still do the autoderef step (just as
 375             // rustc does an autoderef and then autoref again).
 376             let ty = InEnvironment { value: ty.clone(), environment: env.clone() };
 377
 378             // We have to be careful about the order we're looking at candidates
 379             // in here. Consider the case where we're resolving `x.clone()`
 380             // where `x: &Vec<_>`. This resolves to the clone method with self
 381             // type `Vec<_>`, *not* `&_`. I.e. we need to consider methods where
 382             // the receiver type exactly matches before cases where we have to
 383             // do autoref. But in the autoderef steps, the `&_` self type comes
 384             // up *before* the `Vec<_>` self type.
 385             //
 386             // On the other hand, we don't want to just pick any by-value method
 387             // before any by-autoref method; it's just that we need to consider
 388             // the methods by autoderef order of *receiver types*, not *self
 389             // types*.
 390
 391             let deref_chain = autoderef_method_receiver(db, krate, ty);
 392             for i in 0..deref_chain.len() {
 393                 if iterate_method_candidates_with_autoref(
 394                     &deref_chain[i..],
 395                     db,
 396                     env.clone(),
 397                     krate,
 398                     traits_in_scope,
 399                     name,
 400                     callback,
 401                 ) {
 402                     return true;
 403                 }
 404             }
 405             false
 406         }
 407         LookupMode::Path => {
 408             // No autoderef for path lookups
 409             iterate_method_candidates_for_self_ty(
 410                 &ty,
 411                 db,
 412                 env,
 413                 krate,
 414                 traits_in_scope,
 415                 name,
 416                 callback,
 417             )
 418         }
 419     }
 420 }
 421
 422 fn iterate_method_candidates_with_autoref(
 423     deref_chain: &[Canonical<Ty>],
 424     db: &dyn HirDatabase,
 425     env: Arc<TraitEnvironment>,
 426     krate: CrateId,
 427     traits_in_scope: &FxHashSet<TraitId>,
 428     name: Option<&Name>,
 429     mut callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool,
 430 ) -> bool {
 431     if iterate_method_candidates_by_receiver(
 432         &deref_chain[0],
 433         &deref_chain[1..],
 434         db,
 435         env.clone(),
 436         krate,
 437         &traits_in_scope,
 438         name,
 439         &mut callback,
 440     ) {
 441         return true;
 442     }
 443     let refed = Canonical {
 444         kinds: deref_chain[0].kinds.clone(),
 445         value: Ty::apply_one(TypeCtor::Ref(Mutability::Shared), deref_chain[0].value.clone()),
 446     };
 447     if iterate_method_candidates_by_receiver(
 448         &refed,
 449         deref_chain,
 450         db,
 451         env.clone(),
 452         krate,
 453         &traits_in_scope,
 454         name,
 455         &mut callback,
 456     ) {
 457         return true;
 458     }
 459     let ref_muted = Canonical {
 460         kinds: deref_chain[0].kinds.clone(),
 461         value: Ty::apply_one(TypeCtor::Ref(Mutability::Mut), deref_chain[0].value.clone()),
 462     };
 463     if iterate_method_candidates_by_receiver(
 464         &ref_muted,
 465         deref_chain,
 466         db,
 467         env,
 468         krate,
 469         &traits_in_scope,
 470         name,
 471         &mut callback,
 472     ) {
 473         return true;
 474     }
 475     false
 476 }
 477
 478 fn iterate_method_candidates_by_receiver(
 479     receiver_ty: &Canonical<Ty>,
 480     rest_of_deref_chain: &[Canonical<Ty>],
 481     db: &dyn HirDatabase,
 482     env: Arc<TraitEnvironment>,
 483     krate: CrateId,
 484     traits_in_scope: &FxHashSet<TraitId>,
 485     name: Option<&Name>,
 486     mut callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool,
 487 ) -> bool {
 488     // We're looking for methods with *receiver* type receiver_ty. These could
 489     // be found in any of the derefs of receiver_ty, so we have to go through
 490     // that.
 491     for self_ty in std::iter::once(receiver_ty).chain(rest_of_deref_chain) {
 492         if iterate_inherent_methods(self_ty, db, name, Some(receiver_ty), krate, &mut callback) {
 493             return true;
 494         }
 495     }
 496     for self_ty in std::iter::once(receiver_ty).chain(rest_of_deref_chain) {
 497         if iterate_trait_method_candidates(
 498             self_ty,
 499             db,
 500             env.clone(),
 501             krate,
 502             &traits_in_scope,
 503             name,
 504             Some(receiver_ty),
 505             &mut callback,
 506         ) {
 507             return true;
 508         }
 509     }
 510     false
 511 }
 512
 513 fn iterate_method_candidates_for_self_ty(
 514     self_ty: &Canonical<Ty>,
 515     db: &dyn HirDatabase,
 516     env: Arc<TraitEnvironment>,
 517     krate: CrateId,
 518     traits_in_scope: &FxHashSet<TraitId>,
 519     name: Option<&Name>,
 520     mut callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool,
 521 ) -> bool {
 522     if iterate_inherent_methods(self_ty, db, name, None, krate, &mut callback) {
 523         return true;
 524     }
 525     iterate_trait_method_candidates(self_ty, db, env, krate, traits_in_scope, name, None, callback)
 526 }
 527
 528 fn iterate_trait_method_candidates(
 529     self_ty: &Canonical<Ty>,
 530     db: &dyn HirDatabase,
 531     env: Arc<TraitEnvironment>,
 532     krate: CrateId,
 533     traits_in_scope: &FxHashSet<TraitId>,
 534     name: Option<&Name>,
 535     receiver_ty: Option<&Canonical<Ty>>,
 536     callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool,
 537 ) -> bool {
 538     // if ty is `dyn Trait`, the trait doesn't need to be in scope
 539     let inherent_trait =
 540         self_ty.value.dyn_trait().into_iter().flat_map(|t| all_super_traits(db.upcast(), t));
 541     let env_traits = if let Ty::Placeholder(_) = self_ty.value {
 542         // if we have `T: Trait` in the param env, the trait doesn't need to be in scope
 543         env.trait_predicates_for_self_ty(&self_ty.value)
 544             .map(|tr| tr.trait_)
 545             .flat_map(|t| all_super_traits(db.upcast(), t))
 546             .collect()
 547     } else {
 548         Vec::new()
 549     };
 550     let traits =
 551         inherent_trait.chain(env_traits.into_iter()).chain(traits_in_scope.iter().copied());
 552     'traits: for t in traits {
 553         let data = db.trait_data(t);
 554
 555         // we'll be lazy about checking whether the type implements the
 556         // trait, but if we find out it doesn't, we'll skip the rest of the
 557         // iteration
 558         let mut known_implemented = false;
 559         for (_name, item) in data.items.iter() {
 560             if !is_valid_candidate(db, name, receiver_ty, *item, self_ty) {
 561                 continue;
 562             }
 563             if !known_implemented {
 564                 let goal = generic_implements_goal(db, env.clone(), t, self_ty.clone());
 565                 if db.trait_solve(krate, goal).is_none() {
 566                     continue 'traits;
 567                 }
 568             }
 569             known_implemented = true;
 570             if callback(&self_ty.value, *item) {
 571                 return true;
 572             }
 573         }
 574     }
 575     false
 576 }
 577
 578 fn iterate_inherent_methods(
 579     self_ty: &Canonical<Ty>,
 580     db: &dyn HirDatabase,
 581     name: Option<&Name>,
 582     receiver_ty: Option<&Canonical<Ty>>,
 583     krate: CrateId,
 584     callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool,
 585 ) -> bool {
 586     let def_crates = match self_ty.value.def_crates(db, krate) {
 587         Some(k) => k,
 588         None => return false,
 589     };
 590     for krate in def_crates {
 591         let impls = db.inherent_impls_in_crate(krate);
 592
 593         for &impl_def in impls.for_self_ty(&self_ty.value) {
 594             for &item in db.impl_data(impl_def).items.iter() {
 595                 if !is_valid_candidate(db, name, receiver_ty, item, self_ty) {
 596                     continue;
 597                 }
 598                 // we have to check whether the self type unifies with the type
 599                 // that the impl is for. If we have a receiver type, this
 600                 // already happens in `is_valid_candidate` above; if not, we
 601                 // check it here
 602                 if receiver_ty.is_none() && inherent_impl_substs(db, impl_def, self_ty).is_none() {
 603                     test_utils::mark::hit!(impl_self_type_match_without_receiver);
 604                     continue;
 605                 }
 606                 if callback(&self_ty.value, item) {
 607                     return true;
 608                 }
 609             }
 610         }
 611     }
 612     false
 613 }
 614
 615 /// Returns the self type for the index trait call.
 616 pub fn resolve_indexing_op(
 617     db: &dyn HirDatabase,
 618     ty: &Canonical<Ty>,
 619     env: Arc<TraitEnvironment>,
 620     krate: CrateId,
 621     index_trait: TraitId,
 622 ) -> Option<Canonical<Ty>> {
 623     let ty = InEnvironment { value: ty.clone(), environment: env.clone() };
 624     let deref_chain = autoderef_method_receiver(db, krate, ty);
 625     for ty in deref_chain {
 626         let goal = generic_implements_goal(db, env.clone(), index_trait, ty.clone());
 627         if db.trait_solve(krate, goal).is_some() {
 628             return Some(ty);
 629         }
 630     }
 631     None
 632 }
 633
 634 fn is_valid_candidate(
 635     db: &dyn HirDatabase,
 636     name: Option<&Name>,
 637     receiver_ty: Option<&Canonical<Ty>>,
 638     item: AssocItemId,
 639     self_ty: &Canonical<Ty>,
 640 ) -> bool {
 641     match item {
 642         AssocItemId::FunctionId(m) => {
 643             let data = db.function_data(m);
 644             if let Some(name) = name {
 645                 if &data.name != name {
 646                     return false;
 647                 }
 648             }
 649             if let Some(receiver_ty) = receiver_ty {
 650                 if !data.has_self_param {
 651                     return false;
 652                 }
 653                 let transformed_receiver_ty = match transform_receiver_ty(db, m, self_ty) {
 654                     Some(ty) => ty,
 655                     None => return false,
 656                 };
 657                 if transformed_receiver_ty != receiver_ty.value {
 658                     return false;
 659                 }
 660             }
 661             true
 662         }
 663         AssocItemId::ConstId(c) => {
 664             let data = db.const_data(c);
 665             name.map_or(true, |name| data.name.as_ref() == Some(name)) && receiver_ty.is_none()
 666         }
 667         _ => false,
 668     }
 669 }
 670
 671 pub(crate) fn inherent_impl_substs(
 672     db: &dyn HirDatabase,
 673     impl_id: ImplId,
 674     self_ty: &Canonical<Ty>,
 675 ) -> Option<Substs> {
 676     // we create a var for each type parameter of the impl; we need to keep in
 677     // mind here that `self_ty` might have vars of its own
 678     let vars = Substs::build_for_def(db, impl_id)
 679         .fill_with_bound_vars(DebruijnIndex::INNERMOST, self_ty.kinds.len())
 680         .build();
 681     let self_ty_with_vars = db.impl_self_ty(impl_id).subst(&vars);
 682     let mut kinds = self_ty.kinds.to_vec();
 683     kinds.extend(iter::repeat(TyKind::General).take(vars.len()));
 684     let tys = Canonical { kinds: kinds.into(), value: (self_ty_with_vars, self_ty.value.clone()) };
 685     let substs = super::infer::unify(&tys);
 686     // We only want the substs for the vars we added, not the ones from self_ty.
 687     // Also, if any of the vars we added are still in there, we replace them by
 688     // Unknown. I think this can only really happen if self_ty contained
 689     // Unknown, and in that case we want the result to contain Unknown in those
 690     // places again.
 691     substs.map(|s| fallback_bound_vars(s.suffix(vars.len()), self_ty.kinds.len()))
 692 }
 693
 694 /// This replaces any 'free' Bound vars in `s` (i.e. those with indices past
 695 /// num_vars_to_keep) by `Ty::Unknown`.
 696 fn fallback_bound_vars(s: Substs, num_vars_to_keep: usize) -> Substs {
 697     s.fold_binders(
 698         &mut |ty, binders| {
 699             if let Ty::Bound(bound) = &ty {
 700                 if bound.index >= num_vars_to_keep && bound.debruijn >= binders {
 701                     Ty::Unknown
 702                 } else {
 703                     ty
 704                 }
 705             } else {
 706                 ty
 707             }
 708         },
 709         DebruijnIndex::INNERMOST,
 710     )
 711 }
 712
 713 fn transform_receiver_ty(
 714     db: &dyn HirDatabase,
 715     function_id: FunctionId,
 716     self_ty: &Canonical<Ty>,
 717 ) -> Option<Ty> {
 718     let substs = match function_id.lookup(db.upcast()).container {
 719         AssocContainerId::TraitId(_) => Substs::build_for_def(db, function_id)
 720             .push(self_ty.value.clone())
 721             .fill_with_unknown()
 722             .build(),
 723         AssocContainerId::ImplId(impl_id) => {
 724             let impl_substs = inherent_impl_substs(db, impl_id, &self_ty)?;
 725             Substs::build_for_def(db, function_id)
 726                 .use_parent_substs(&impl_substs)
 727                 .fill_with_unknown()
 728                 .build()
 729         }
 730         AssocContainerId::ContainerId(_) => unreachable!(),
 731     };
 732     let sig = db.callable_item_signature(function_id.into());
 733     Some(sig.value.params()[0].clone().subst_bound_vars(&substs))
 734 }
 735
 736 pub fn implements_trait(
 737     ty: &Canonical<Ty>,
 738     db: &dyn HirDatabase,
 739     env: Arc<TraitEnvironment>,
 740     krate: CrateId,
 741     trait_: TraitId,
 742 ) -> bool {
 743     let goal = generic_implements_goal(db, env, trait_, ty.clone());
 744     let solution = db.trait_solve(krate, goal);
 745
 746     solution.is_some()
 747 }
 748
 749 pub fn implements_trait_unique(
 750     ty: &Canonical<Ty>,
 751     db: &dyn HirDatabase,
 752     env: Arc<TraitEnvironment>,
 753     krate: CrateId,
 754     trait_: TraitId,
 755 ) -> bool {
 756     let goal = generic_implements_goal(db, env, trait_, ty.clone());
 757     let solution = db.trait_solve(krate, goal);
 758
 759     matches!(solution, Some(crate::traits::Solution::Unique(_)))
 760 }
 761
 762 /// This creates Substs for a trait with the given Self type and type variables
 763 /// for all other parameters, to query Chalk with it.
 764 fn generic_implements_goal(
 765     db: &dyn HirDatabase,
 766     env: Arc<TraitEnvironment>,
 767     trait_: TraitId,
 768     self_ty: Canonical<Ty>,
 769 ) -> Canonical<InEnvironment<super::Obligation>> {
 770     let mut kinds = self_ty.kinds.to_vec();
 771     let substs = super::Substs::build_for_def(db, trait_)
 772         .push(self_ty.value)
 773         .fill_with_bound_vars(DebruijnIndex::INNERMOST, kinds.len())
 774         .build();
 775     kinds.extend(iter::repeat(TyKind::General).take(substs.len() - 1));
 776     let trait_ref = TraitRef { trait_, substs };
 777     let obligation = super::Obligation::Trait(trait_ref);
 778     Canonical { kinds: kinds.into(), value: InEnvironment::new(env, obligation) }
 779 }
 780
 781 fn autoderef_method_receiver(
 782     db: &dyn HirDatabase,
 783     krate: CrateId,
 784     ty: InEnvironment<Canonical<Ty>>,
 785 ) -> Vec<Canonical<Ty>> {
 786     let mut deref_chain: Vec<_> = autoderef::autoderef(db, Some(krate), ty).collect();
 787     // As a last step, we can do array unsizing (that's the only unsizing that rustc does for method receivers!)
 788     if let Some(Ty::Apply(ApplicationTy { ctor: TypeCtor::Array, parameters })) =
 789         deref_chain.last().map(|ty| &ty.value)
 790     {
 791         let kinds = deref_chain.last().unwrap().kinds.clone();
 792         let unsized_ty = Ty::apply(TypeCtor::Slice, parameters.clone());
 793         deref_chain.push(Canonical { value: unsized_ty, kinds })
 794     }
 795     deref_chain
 796 }