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