diff options
author | Seivan Heidari <[email protected]> | 2019-11-28 07:19:14 +0000 |
---|---|---|
committer | Seivan Heidari <[email protected]> | 2019-11-28 07:19:14 +0000 |
commit | 18a0937585b836ec5ed054b9ae48e0156ab6d9ef (patch) | |
tree | 9de2c0267ddcc00df717f90034d0843d751a851b /crates/ra_hir_ty/src/method_resolution.rs | |
parent | a7394b44c870f585eacfeb3036a33471aff49ff8 (diff) | |
parent | 484acc8a61d599662ed63a4cbda091d38a982551 (diff) |
Merge branch 'master' of https://github.com/rust-analyzer/rust-analyzer into feature/themes
Diffstat (limited to 'crates/ra_hir_ty/src/method_resolution.rs')
-rw-r--r-- | crates/ra_hir_ty/src/method_resolution.rs | 353 |
1 files changed, 353 insertions, 0 deletions
diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs new file mode 100644 index 000000000..ee1936b0e --- /dev/null +++ b/crates/ra_hir_ty/src/method_resolution.rs | |||
@@ -0,0 +1,353 @@ | |||
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::sync::Arc; | ||
6 | |||
7 | use arrayvec::ArrayVec; | ||
8 | use hir_def::{ | ||
9 | lang_item::LangItemTarget, resolver::Resolver, type_ref::Mutability, AssocItemId, AstItemDef, | ||
10 | FunctionId, HasModule, ImplId, TraitId, | ||
11 | }; | ||
12 | use hir_expand::name::Name; | ||
13 | use ra_db::CrateId; | ||
14 | use ra_prof::profile; | ||
15 | use rustc_hash::FxHashMap; | ||
16 | |||
17 | use crate::{ | ||
18 | autoderef, | ||
19 | db::HirDatabase, | ||
20 | primitive::{FloatBitness, Uncertain}, | ||
21 | utils::all_super_traits, | ||
22 | Canonical, ImplTy, InEnvironment, TraitEnvironment, TraitRef, Ty, TypeCtor, | ||
23 | }; | ||
24 | |||
25 | /// This is used as a key for indexing impls. | ||
26 | #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] | ||
27 | pub enum TyFingerprint { | ||
28 | Apply(TypeCtor), | ||
29 | } | ||
30 | |||
31 | impl TyFingerprint { | ||
32 | /// Creates a TyFingerprint for looking up an impl. Only certain types can | ||
33 | /// have impls: if we have some `struct S`, we can have an `impl S`, but not | ||
34 | /// `impl &S`. Hence, this will return `None` for reference types and such. | ||
35 | fn for_impl(ty: &Ty) -> Option<TyFingerprint> { | ||
36 | match ty { | ||
37 | Ty::Apply(a_ty) => Some(TyFingerprint::Apply(a_ty.ctor)), | ||
38 | _ => None, | ||
39 | } | ||
40 | } | ||
41 | } | ||
42 | |||
43 | #[derive(Debug, PartialEq, Eq)] | ||
44 | pub struct CrateImplBlocks { | ||
45 | impls: FxHashMap<TyFingerprint, Vec<ImplId>>, | ||
46 | impls_by_trait: FxHashMap<TraitId, Vec<ImplId>>, | ||
47 | } | ||
48 | |||
49 | impl CrateImplBlocks { | ||
50 | pub(crate) fn impls_in_crate_query( | ||
51 | db: &impl HirDatabase, | ||
52 | krate: CrateId, | ||
53 | ) -> Arc<CrateImplBlocks> { | ||
54 | let _p = profile("impls_in_crate_query"); | ||
55 | let mut res = | ||
56 | CrateImplBlocks { impls: FxHashMap::default(), impls_by_trait: FxHashMap::default() }; | ||
57 | |||
58 | let crate_def_map = db.crate_def_map(krate); | ||
59 | for (_module_id, module_data) in crate_def_map.modules.iter() { | ||
60 | for &impl_id in module_data.impls.iter() { | ||
61 | match db.impl_ty(impl_id) { | ||
62 | ImplTy::TraitRef(tr) => { | ||
63 | res.impls_by_trait.entry(tr.trait_).or_default().push(impl_id); | ||
64 | } | ||
65 | ImplTy::Inherent(self_ty) => { | ||
66 | if let Some(self_ty_fp) = TyFingerprint::for_impl(&self_ty) { | ||
67 | res.impls.entry(self_ty_fp).or_default().push(impl_id); | ||
68 | } | ||
69 | } | ||
70 | } | ||
71 | } | ||
72 | } | ||
73 | |||
74 | Arc::new(res) | ||
75 | } | ||
76 | pub fn lookup_impl_blocks(&self, ty: &Ty) -> impl Iterator<Item = ImplId> + '_ { | ||
77 | let fingerprint = TyFingerprint::for_impl(ty); | ||
78 | fingerprint.and_then(|f| self.impls.get(&f)).into_iter().flatten().copied() | ||
79 | } | ||
80 | |||
81 | pub fn lookup_impl_blocks_for_trait(&self, tr: TraitId) -> impl Iterator<Item = ImplId> + '_ { | ||
82 | self.impls_by_trait.get(&tr).into_iter().flatten().copied() | ||
83 | } | ||
84 | |||
85 | pub fn all_impls<'a>(&'a self) -> impl Iterator<Item = ImplId> + 'a { | ||
86 | self.impls.values().chain(self.impls_by_trait.values()).flatten().copied() | ||
87 | } | ||
88 | } | ||
89 | |||
90 | impl Ty { | ||
91 | pub fn def_crates( | ||
92 | &self, | ||
93 | db: &impl HirDatabase, | ||
94 | cur_crate: CrateId, | ||
95 | ) -> Option<ArrayVec<[CrateId; 2]>> { | ||
96 | // Types like slice can have inherent impls in several crates, (core and alloc). | ||
97 | // The corresponding impls are marked with lang items, so we can use them to find the required crates. | ||
98 | macro_rules! lang_item_crate { | ||
99 | ($($name:expr),+ $(,)?) => {{ | ||
100 | let mut v = ArrayVec::<[LangItemTarget; 2]>::new(); | ||
101 | $( | ||
102 | v.extend(db.lang_item(cur_crate, $name.into())); | ||
103 | )+ | ||
104 | v | ||
105 | }}; | ||
106 | } | ||
107 | |||
108 | let lang_item_targets = match self { | ||
109 | Ty::Apply(a_ty) => match a_ty.ctor { | ||
110 | TypeCtor::Adt(def_id) => { | ||
111 | return Some(std::iter::once(def_id.module(db).krate).collect()) | ||
112 | } | ||
113 | TypeCtor::Bool => lang_item_crate!("bool"), | ||
114 | TypeCtor::Char => lang_item_crate!("char"), | ||
115 | TypeCtor::Float(Uncertain::Known(f)) => match f.bitness { | ||
116 | // There are two lang items: one in libcore (fXX) and one in libstd (fXX_runtime) | ||
117 | FloatBitness::X32 => lang_item_crate!("f32", "f32_runtime"), | ||
118 | FloatBitness::X64 => lang_item_crate!("f64", "f64_runtime"), | ||
119 | }, | ||
120 | TypeCtor::Int(Uncertain::Known(i)) => lang_item_crate!(i.ty_to_string()), | ||
121 | TypeCtor::Str => lang_item_crate!("str_alloc", "str"), | ||
122 | TypeCtor::Slice => lang_item_crate!("slice_alloc", "slice"), | ||
123 | TypeCtor::RawPtr(Mutability::Shared) => lang_item_crate!("const_ptr"), | ||
124 | TypeCtor::RawPtr(Mutability::Mut) => lang_item_crate!("mut_ptr"), | ||
125 | _ => return None, | ||
126 | }, | ||
127 | _ => return None, | ||
128 | }; | ||
129 | let res = lang_item_targets | ||
130 | .into_iter() | ||
131 | .filter_map(|it| match it { | ||
132 | LangItemTarget::ImplBlockId(it) => Some(it), | ||
133 | _ => None, | ||
134 | }) | ||
135 | .map(|it| it.module(db).krate) | ||
136 | .collect(); | ||
137 | Some(res) | ||
138 | } | ||
139 | } | ||
140 | /// Look up the method with the given name, returning the actual autoderefed | ||
141 | /// receiver type (but without autoref applied yet). | ||
142 | pub(crate) fn lookup_method( | ||
143 | ty: &Canonical<Ty>, | ||
144 | db: &impl HirDatabase, | ||
145 | name: &Name, | ||
146 | resolver: &Resolver, | ||
147 | ) -> Option<(Ty, FunctionId)> { | ||
148 | iterate_method_candidates(ty, db, resolver, Some(name), LookupMode::MethodCall, |ty, f| match f | ||
149 | { | ||
150 | AssocItemId::FunctionId(f) => Some((ty.clone(), f)), | ||
151 | _ => None, | ||
152 | }) | ||
153 | } | ||
154 | |||
155 | /// Whether we're looking up a dotted method call (like `v.len()`) or a path | ||
156 | /// (like `Vec::new`). | ||
157 | #[derive(Copy, Clone, Debug, PartialEq, Eq)] | ||
158 | pub enum LookupMode { | ||
159 | /// Looking up a method call like `v.len()`: We only consider candidates | ||
160 | /// that have a `self` parameter, and do autoderef. | ||
161 | MethodCall, | ||
162 | /// Looking up a path like `Vec::new` or `Vec::default`: We consider all | ||
163 | /// candidates including associated constants, but don't do autoderef. | ||
164 | Path, | ||
165 | } | ||
166 | |||
167 | // This would be nicer if it just returned an iterator, but that runs into | ||
168 | // lifetime problems, because we need to borrow temp `CrateImplBlocks`. | ||
169 | // FIXME add a context type here? | ||
170 | pub fn iterate_method_candidates<T>( | ||
171 | ty: &Canonical<Ty>, | ||
172 | db: &impl HirDatabase, | ||
173 | resolver: &Resolver, | ||
174 | name: Option<&Name>, | ||
175 | mode: LookupMode, | ||
176 | mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>, | ||
177 | ) -> Option<T> { | ||
178 | let krate = resolver.krate()?; | ||
179 | match mode { | ||
180 | LookupMode::MethodCall => { | ||
181 | // For method calls, rust first does any number of autoderef, and then one | ||
182 | // autoref (i.e. when the method takes &self or &mut self). We just ignore | ||
183 | // the autoref currently -- when we find a method matching the given name, | ||
184 | // we assume it fits. | ||
185 | |||
186 | // Also note that when we've got a receiver like &S, even if the method we | ||
187 | // find in the end takes &self, we still do the autoderef step (just as | ||
188 | // rustc does an autoderef and then autoref again). | ||
189 | let environment = TraitEnvironment::lower(db, resolver); | ||
190 | let ty = InEnvironment { value: ty.clone(), environment }; | ||
191 | for derefed_ty in autoderef::autoderef(db, resolver.krate(), ty) { | ||
192 | if let Some(result) = | ||
193 | iterate_inherent_methods(&derefed_ty, db, name, mode, krate, &mut callback) | ||
194 | { | ||
195 | return Some(result); | ||
196 | } | ||
197 | if let Some(result) = iterate_trait_method_candidates( | ||
198 | &derefed_ty, | ||
199 | db, | ||
200 | resolver, | ||
201 | name, | ||
202 | mode, | ||
203 | &mut callback, | ||
204 | ) { | ||
205 | return Some(result); | ||
206 | } | ||
207 | } | ||
208 | } | ||
209 | LookupMode::Path => { | ||
210 | // No autoderef for path lookups | ||
211 | if let Some(result) = | ||
212 | iterate_inherent_methods(&ty, db, name, mode, krate.into(), &mut callback) | ||
213 | { | ||
214 | return Some(result); | ||
215 | } | ||
216 | if let Some(result) = | ||
217 | iterate_trait_method_candidates(&ty, db, resolver, name, mode, &mut callback) | ||
218 | { | ||
219 | return Some(result); | ||
220 | } | ||
221 | } | ||
222 | } | ||
223 | None | ||
224 | } | ||
225 | |||
226 | fn iterate_trait_method_candidates<T>( | ||
227 | ty: &Canonical<Ty>, | ||
228 | db: &impl HirDatabase, | ||
229 | resolver: &Resolver, | ||
230 | name: Option<&Name>, | ||
231 | mode: LookupMode, | ||
232 | mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>, | ||
233 | ) -> Option<T> { | ||
234 | let krate = resolver.krate()?; | ||
235 | // FIXME: maybe put the trait_env behind a query (need to figure out good input parameters for that) | ||
236 | let env = TraitEnvironment::lower(db, resolver); | ||
237 | // if ty is `impl Trait` or `dyn Trait`, the trait doesn't need to be in scope | ||
238 | let inherent_trait = ty.value.inherent_trait().into_iter(); | ||
239 | // if we have `T: Trait` in the param env, the trait doesn't need to be in scope | ||
240 | let traits_from_env = env | ||
241 | .trait_predicates_for_self_ty(&ty.value) | ||
242 | .map(|tr| tr.trait_) | ||
243 | .flat_map(|t| all_super_traits(db, t)); | ||
244 | let traits = | ||
245 | inherent_trait.chain(traits_from_env).chain(resolver.traits_in_scope(db).into_iter()); | ||
246 | 'traits: for t in traits { | ||
247 | let data = db.trait_data(t); | ||
248 | |||
249 | // we'll be lazy about checking whether the type implements the | ||
250 | // trait, but if we find out it doesn't, we'll skip the rest of the | ||
251 | // iteration | ||
252 | let mut known_implemented = false; | ||
253 | for (_name, item) in data.items.iter() { | ||
254 | if !is_valid_candidate(db, name, mode, (*item).into()) { | ||
255 | continue; | ||
256 | } | ||
257 | if !known_implemented { | ||
258 | let goal = generic_implements_goal(db, env.clone(), t, ty.clone()); | ||
259 | if db.trait_solve(krate.into(), goal).is_none() { | ||
260 | continue 'traits; | ||
261 | } | ||
262 | } | ||
263 | known_implemented = true; | ||
264 | if let Some(result) = callback(&ty.value, (*item).into()) { | ||
265 | return Some(result); | ||
266 | } | ||
267 | } | ||
268 | } | ||
269 | None | ||
270 | } | ||
271 | |||
272 | fn iterate_inherent_methods<T>( | ||
273 | ty: &Canonical<Ty>, | ||
274 | db: &impl HirDatabase, | ||
275 | name: Option<&Name>, | ||
276 | mode: LookupMode, | ||
277 | krate: CrateId, | ||
278 | mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>, | ||
279 | ) -> Option<T> { | ||
280 | for krate in ty.value.def_crates(db, krate)? { | ||
281 | let impls = db.impls_in_crate(krate); | ||
282 | |||
283 | for impl_block in impls.lookup_impl_blocks(&ty.value) { | ||
284 | for &item in db.impl_data(impl_block).items.iter() { | ||
285 | if !is_valid_candidate(db, name, mode, item) { | ||
286 | continue; | ||
287 | } | ||
288 | if let Some(result) = callback(&ty.value, item.into()) { | ||
289 | return Some(result); | ||
290 | } | ||
291 | } | ||
292 | } | ||
293 | } | ||
294 | None | ||
295 | } | ||
296 | |||
297 | fn is_valid_candidate( | ||
298 | db: &impl HirDatabase, | ||
299 | name: Option<&Name>, | ||
300 | mode: LookupMode, | ||
301 | item: AssocItemId, | ||
302 | ) -> bool { | ||
303 | match item { | ||
304 | AssocItemId::FunctionId(m) => { | ||
305 | let data = db.function_data(m); | ||
306 | name.map_or(true, |name| &data.name == name) | ||
307 | && (data.has_self_param || mode == LookupMode::Path) | ||
308 | } | ||
309 | AssocItemId::ConstId(c) => { | ||
310 | let data = db.const_data(c); | ||
311 | name.map_or(true, |name| data.name.as_ref() == Some(name)) && (mode == LookupMode::Path) | ||
312 | } | ||
313 | _ => false, | ||
314 | } | ||
315 | } | ||
316 | |||
317 | pub fn implements_trait( | ||
318 | ty: &Canonical<Ty>, | ||
319 | db: &impl HirDatabase, | ||
320 | resolver: &Resolver, | ||
321 | krate: CrateId, | ||
322 | trait_: TraitId, | ||
323 | ) -> bool { | ||
324 | if ty.value.inherent_trait() == Some(trait_) { | ||
325 | // FIXME this is a bit of a hack, since Chalk should say the same thing | ||
326 | // anyway, but currently Chalk doesn't implement `dyn/impl Trait` yet | ||
327 | return true; | ||
328 | } | ||
329 | let env = TraitEnvironment::lower(db, resolver); | ||
330 | let goal = generic_implements_goal(db, env, trait_, ty.clone()); | ||
331 | let solution = db.trait_solve(krate.into(), goal); | ||
332 | |||
333 | solution.is_some() | ||
334 | } | ||
335 | |||
336 | /// This creates Substs for a trait with the given Self type and type variables | ||
337 | /// for all other parameters, to query Chalk with it. | ||
338 | fn generic_implements_goal( | ||
339 | db: &impl HirDatabase, | ||
340 | env: Arc<TraitEnvironment>, | ||
341 | trait_: TraitId, | ||
342 | self_ty: Canonical<Ty>, | ||
343 | ) -> Canonical<InEnvironment<super::Obligation>> { | ||
344 | let num_vars = self_ty.num_vars; | ||
345 | let substs = super::Substs::build_for_def(db, trait_) | ||
346 | .push(self_ty.value) | ||
347 | .fill_with_bound_vars(num_vars as u32) | ||
348 | .build(); | ||
349 | let num_vars = substs.len() - 1 + self_ty.num_vars; | ||
350 | let trait_ref = TraitRef { trait_, substs }; | ||
351 | let obligation = super::Obligation::Trait(trait_ref); | ||
352 | Canonical { num_vars, value: InEnvironment::new(env, obligation) } | ||
353 | } | ||