]>
Commit | Line | Data |
---|---|---|
c34b1796 | 1 | use super::MethodError; |
62682a34 | 2 | use super::NoMatchData; |
62682a34 | 3 | use super::{CandidateSource, ImplSource, TraitSource}; |
85aaf69f | 4 | use super::suggest; |
1a4d82fc | 5 | |
9fa01778 XL |
6 | use crate::check::autoderef::{self, Autoderef}; |
7 | use crate::check::FnCtxt; | |
8 | use crate::hir::def_id::DefId; | |
48663c56 | 9 | use crate::hir::def::DefKind; |
9fa01778 | 10 | use crate::namespace::Namespace; |
0731742a XL |
11 | |
12 | use rustc_data_structures::sync::Lrc; | |
0bf4aa26 XL |
13 | use rustc::hir; |
14 | use rustc::lint; | |
15 | use rustc::session::config::nightly_options; | |
532ac7d7 | 16 | use rustc::ty::subst::{Subst, InternalSubsts, SubstsRef}; |
476ff2be | 17 | use rustc::traits::{self, ObligationCause}; |
0731742a XL |
18 | use rustc::traits::query::{CanonicalTyGoal}; |
19 | use rustc::traits::query::method_autoderef::{CandidateStep, MethodAutoderefStepsResult}; | |
20 | use rustc::traits::query::method_autoderef::{MethodAutoderefBadTy}; | |
21 | use rustc::ty::{self, ParamEnvAnd, Ty, TyCtxt, ToPolyTraitRef, ToPredicate, TraitRef, TypeFoldable}; | |
94b46f34 | 22 | use rustc::ty::GenericParamDefKind; |
dc9dc135 XL |
23 | use rustc::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind}; |
24 | use rustc::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind}; | |
476ff2be | 25 | use rustc::util::nodemap::FxHashSet; |
32a655c1 | 26 | use rustc::infer::{self, InferOk}; |
0731742a XL |
27 | use rustc::infer::canonical::{Canonical, QueryResponse}; |
28 | use rustc::infer::canonical::{OriginalQueryValues}; | |
0531ce1d | 29 | use rustc::middle::stability; |
1a4d82fc | 30 | use syntax::ast; |
ea8adc8c | 31 | use syntax::util::lev_distance::{lev_distance, find_best_match_for_name}; |
0731742a | 32 | use syntax_pos::{DUMMY_SP, Span, symbol::Symbol}; |
a1dfa0c6 | 33 | use std::iter; |
85aaf69f | 34 | use std::mem; |
a7813a04 | 35 | use std::ops::Deref; |
ea8adc8c | 36 | use std::cmp::max; |
1a4d82fc | 37 | |
60c5eb7d XL |
38 | use rustc_error_codes::*; |
39 | ||
48663c56 XL |
40 | use smallvec::{smallvec, SmallVec}; |
41 | ||
1a4d82fc | 42 | use self::CandidateKind::*; |
1a4d82fc JJ |
43 | pub use self::PickKind::*; |
44 | ||
32a655c1 | 45 | /// Boolean flag used to indicate if this search is for a suggestion |
0731742a | 46 | /// or not. If true, we can allow ambiguity and so forth. |
0531ce1d | 47 | #[derive(Clone, Copy)] |
32a655c1 SL |
48 | pub struct IsSuggestion(pub bool); |
49 | ||
dc9dc135 XL |
50 | struct ProbeContext<'a, 'tcx> { |
51 | fcx: &'a FnCtxt<'a, 'tcx>, | |
1a4d82fc | 52 | span: Span, |
c34b1796 | 53 | mode: Mode, |
8faf50e0 | 54 | method_name: Option<ast::Ident>, |
ea8adc8c | 55 | return_type: Option<Ty<'tcx>>, |
0731742a XL |
56 | |
57 | /// This is the OriginalQueryValues for the steps queries | |
58 | /// that are answered in steps. | |
59 | orig_steps_var_values: OriginalQueryValues<'tcx>, | |
dc9dc135 | 60 | steps: Lrc<Vec<CandidateStep<'tcx>>>, |
0731742a | 61 | |
1a4d82fc JJ |
62 | inherent_candidates: Vec<Candidate<'tcx>>, |
63 | extension_candidates: Vec<Candidate<'tcx>>, | |
476ff2be | 64 | impl_dups: FxHashSet<DefId>, |
62682a34 SL |
65 | |
66 | /// Collects near misses when the candidate functions are missing a `self` keyword and is only | |
67 | /// used for error reporting | |
1a4d82fc | 68 | static_candidates: Vec<CandidateSource>, |
62682a34 | 69 | |
ea8adc8c XL |
70 | /// When probing for names, include names that are close to the |
71 | /// requested name (by Levensthein distance) | |
72 | allow_similar_names: bool, | |
73 | ||
54a0048b | 74 | /// Some(candidate) if there is a private candidate |
48663c56 | 75 | private_candidate: Option<(DefKind, DefId)>, |
54a0048b | 76 | |
62682a34 SL |
77 | /// Collects near misses when trait bounds for type parameters are unsatisfied and is only used |
78 | /// for error reporting | |
c30ab7b3 | 79 | unsatisfied_predicates: Vec<TraitRef<'tcx>>, |
0531ce1d XL |
80 | |
81 | is_suggestion: IsSuggestion, | |
1a4d82fc JJ |
82 | } |
83 | ||
dc9dc135 XL |
84 | impl<'a, 'tcx> Deref for ProbeContext<'a, 'tcx> { |
85 | type Target = FnCtxt<'a, 'tcx>; | |
a7813a04 XL |
86 | fn deref(&self) -> &Self::Target { |
87 | &self.fcx | |
88 | } | |
89 | } | |
90 | ||
62682a34 | 91 | #[derive(Debug)] |
1a4d82fc | 92 | struct Candidate<'tcx> { |
0731742a | 93 | // Candidates are (I'm not quite sure, but they are mostly) basically |
dc9dc135 | 94 | // some metadata on top of a `ty::AssocItem` (without substs). |
0731742a XL |
95 | // |
96 | // However, method probing wants to be able to evaluate the predicates | |
97 | // for a function with the substs applied - for example, if a function | |
98 | // has `where Self: Sized`, we don't want to consider it unless `Self` | |
99 | // is actually `Sized`, and similarly, return-type suggestions want | |
100 | // to consider the "actual" return type. | |
101 | // | |
102 | // The way this is handled is through `xform_self_ty`. It contains | |
103 | // the receiver type of this candidate, but `xform_self_ty`, | |
104 | // `xform_ret_ty` and `kind` (which contains the predicates) have the | |
105 | // generic parameters of this candidate substituted with the *same set* | |
106 | // of inference variables, which acts as some weird sort of "query". | |
107 | // | |
108 | // When we check out a candidate, we require `xform_self_ty` to be | |
109 | // a subtype of the passed-in self-type, and this equates the type | |
110 | // variables in the rest of the fields. | |
111 | // | |
112 | // For example, if we have this candidate: | |
113 | // ``` | |
114 | // trait Foo { | |
115 | // fn foo(&self) where Self: Sized; | |
116 | // } | |
117 | // ``` | |
118 | // | |
119 | // Then `xform_self_ty` will be `&'erased ?X` and `kind` will contain | |
120 | // the predicate `?X: Sized`, so if we are evaluating `Foo` for a | |
121 | // the receiver `&T`, we'll do the subtyping which will make `?X` | |
122 | // get the right value, then when we evaluate the predicate we'll check | |
123 | // if `T: Sized`. | |
1a4d82fc | 124 | xform_self_ty: Ty<'tcx>, |
ea8adc8c | 125 | xform_ret_ty: Option<Ty<'tcx>>, |
dc9dc135 | 126 | item: ty::AssocItem, |
1a4d82fc | 127 | kind: CandidateKind<'tcx>, |
48663c56 | 128 | import_ids: SmallVec<[hir::HirId; 1]>, |
1a4d82fc JJ |
129 | } |
130 | ||
62682a34 | 131 | #[derive(Debug)] |
1a4d82fc | 132 | enum CandidateKind<'tcx> { |
532ac7d7 | 133 | InherentImplCandidate(SubstsRef<'tcx>, |
c30ab7b3 SL |
134 | // Normalize obligations |
135 | Vec<traits::PredicateObligation<'tcx>>), | |
c1a9b12d | 136 | ObjectCandidate, |
ea8adc8c | 137 | TraitCandidate(ty::TraitRef<'tcx>), |
c30ab7b3 SL |
138 | WhereClauseCandidate(// Trait |
139 | ty::PolyTraitRef<'tcx>), | |
1a4d82fc JJ |
140 | } |
141 | ||
ea8adc8c XL |
142 | #[derive(Debug, PartialEq, Eq, Copy, Clone)] |
143 | enum ProbeResult { | |
144 | NoMatch, | |
145 | BadReturnType, | |
146 | Match, | |
147 | } | |
148 | ||
8faf50e0 | 149 | #[derive(Debug, PartialEq, Clone)] |
1a4d82fc | 150 | pub struct Pick<'tcx> { |
dc9dc135 | 151 | pub item: ty::AssocItem, |
1a4d82fc | 152 | pub kind: PickKind<'tcx>, |
48663c56 | 153 | pub import_ids: SmallVec<[hir::HirId; 1]>, |
9346a6ac AL |
154 | |
155 | // Indicates that the source expression should be autoderef'd N times | |
156 | // | |
157 | // A = expr | *expr | **expr | ... | |
158 | pub autoderefs: usize, | |
159 | ||
160 | // Indicates that an autoref is applied after the optional autoderefs | |
161 | // | |
162 | // B = A | &A | &mut A | |
e9174d1e | 163 | pub autoref: Option<hir::Mutability>, |
9346a6ac AL |
164 | |
165 | // Indicates that the source expression should be "unsized" to a | |
166 | // target type. This should probably eventually go away in favor | |
167 | // of just coercing method receivers. | |
168 | // | |
169 | // C = B | unsize(B) | |
170 | pub unsize: Option<Ty<'tcx>>, | |
1a4d82fc JJ |
171 | } |
172 | ||
3b2f2976 | 173 | #[derive(Clone, Debug, PartialEq, Eq)] |
1a4d82fc | 174 | pub enum PickKind<'tcx> { |
c1a9b12d | 175 | InherentImplPick, |
c1a9b12d SL |
176 | ObjectPick, |
177 | TraitPick, | |
c30ab7b3 SL |
178 | WhereClausePick(// Trait |
179 | ty::PolyTraitRef<'tcx>), | |
1a4d82fc JJ |
180 | } |
181 | ||
62682a34 | 182 | pub type PickResult<'tcx> = Result<Pick<'tcx>, MethodError<'tcx>>; |
1a4d82fc | 183 | |
d9579d0f | 184 | #[derive(PartialEq, Eq, Copy, Clone, Debug)] |
c34b1796 AL |
185 | pub enum Mode { |
186 | // An expression of the form `receiver.method_name(...)`. | |
187 | // Autoderefs are performed on `receiver`, lookup is done based on the | |
188 | // `self` argument of the method, and static methods aren't considered. | |
189 | MethodCall, | |
d9579d0f | 190 | // An expression of the form `Type::item` or `<T>::item`. |
c34b1796 AL |
191 | // No autoderefs are performed, lookup is done based on the type each |
192 | // implementation is for, and static methods are included. | |
c30ab7b3 | 193 | Path, |
c34b1796 AL |
194 | } |
195 | ||
3b2f2976 XL |
196 | #[derive(PartialEq, Eq, Copy, Clone, Debug)] |
197 | pub enum ProbeScope { | |
198 | // Assemble candidates coming only from traits in scope. | |
199 | TraitsInScope, | |
200 | ||
201 | // Assemble candidates coming from all traits. | |
202 | AllTraits, | |
203 | } | |
204 | ||
dc9dc135 | 205 | impl<'a, 'tcx> FnCtxt<'a, 'tcx> { |
32a655c1 SL |
206 | /// This is used to offer suggestions to users. It returns methods |
207 | /// that could have been called which have the desired return | |
208 | /// type. Some effort is made to rule out methods that, if called, | |
209 | /// would result in an error (basically, the same criteria we | |
210 | /// would use to decide if a method is a plausible fit for | |
211 | /// ambiguity purposes). | |
212 | pub fn probe_for_return_type(&self, | |
213 | span: Span, | |
214 | mode: Mode, | |
215 | return_type: Ty<'tcx>, | |
216 | self_ty: Ty<'tcx>, | |
532ac7d7 | 217 | scope_expr_id: hir::HirId) |
dc9dc135 | 218 | -> Vec<ty::AssocItem> { |
32a655c1 SL |
219 | debug!("probe(self_ty={:?}, return_type={}, scope_expr_id={})", |
220 | self_ty, | |
221 | return_type, | |
222 | scope_expr_id); | |
223 | let method_names = | |
ea8adc8c | 224 | self.probe_op(span, mode, None, Some(return_type), IsSuggestion(true), |
2c00a5a8 | 225 | self_ty, scope_expr_id, ProbeScope::AllTraits, |
32a655c1 SL |
226 | |probe_cx| Ok(probe_cx.candidate_method_names())) |
227 | .unwrap_or(vec![]); | |
ea8adc8c XL |
228 | method_names |
229 | .iter() | |
230 | .flat_map(|&method_name| { | |
231 | self.probe_op( | |
232 | span, mode, Some(method_name), Some(return_type), | |
233 | IsSuggestion(true), self_ty, scope_expr_id, | |
2c00a5a8 | 234 | ProbeScope::AllTraits, |probe_cx| probe_cx.pick() |
ea8adc8c XL |
235 | ).ok().map(|pick| pick.item) |
236 | }) | |
32a655c1 SL |
237 | .collect() |
238 | } | |
239 | ||
240 | pub fn probe_for_name(&self, | |
241 | span: Span, | |
242 | mode: Mode, | |
8faf50e0 | 243 | item_name: ast::Ident, |
32a655c1 SL |
244 | is_suggestion: IsSuggestion, |
245 | self_ty: Ty<'tcx>, | |
532ac7d7 | 246 | scope_expr_id: hir::HirId, |
3b2f2976 | 247 | scope: ProbeScope) |
32a655c1 | 248 | -> PickResult<'tcx> { |
a7813a04 XL |
249 | debug!("probe(self_ty={:?}, item_name={}, scope_expr_id={})", |
250 | self_ty, | |
251 | item_name, | |
252 | scope_expr_id); | |
32a655c1 SL |
253 | self.probe_op(span, |
254 | mode, | |
ea8adc8c XL |
255 | Some(item_name), |
256 | None, | |
32a655c1 SL |
257 | is_suggestion, |
258 | self_ty, | |
259 | scope_expr_id, | |
3b2f2976 | 260 | scope, |
32a655c1 SL |
261 | |probe_cx| probe_cx.pick()) |
262 | } | |
a7813a04 | 263 | |
dc9dc135 XL |
264 | fn probe_op<OP, R>( |
265 | &'a self, | |
266 | span: Span, | |
267 | mode: Mode, | |
268 | method_name: Option<ast::Ident>, | |
269 | return_type: Option<Ty<'tcx>>, | |
270 | is_suggestion: IsSuggestion, | |
271 | self_ty: Ty<'tcx>, | |
272 | scope_expr_id: hir::HirId, | |
273 | scope: ProbeScope, | |
274 | op: OP, | |
275 | ) -> Result<R, MethodError<'tcx>> | |
276 | where | |
277 | OP: FnOnce(ProbeContext<'a, 'tcx>) -> Result<R, MethodError<'tcx>>, | |
32a655c1 | 278 | { |
0731742a XL |
279 | let mut orig_values = OriginalQueryValues::default(); |
280 | let param_env_and_self_ty = | |
281 | self.infcx.canonicalize_query( | |
282 | &ParamEnvAnd { | |
283 | param_env: self.param_env, | |
284 | value: self_ty | |
285 | }, &mut orig_values); | |
286 | ||
a7813a04 | 287 | let steps = if mode == Mode::MethodCall { |
0731742a | 288 | self.tcx.method_autoderef_steps(param_env_and_self_ty) |
1a4d82fc | 289 | } else { |
0731742a XL |
290 | self.infcx.probe(|_| { |
291 | // Mode::Path - the deref steps is "trivial". This turns | |
292 | // our CanonicalQuery into a "trivial" QueryResponse. This | |
293 | // is a bit inefficient, but I don't think that writing | |
294 | // special handling for this "trivial case" is a good idea. | |
295 | ||
296 | let infcx = &self.infcx; | |
297 | let (ParamEnvAnd { | |
298 | param_env: _, | |
299 | value: self_ty | |
300 | }, canonical_inference_vars) = | |
301 | infcx.instantiate_canonical_with_fresh_inference_vars( | |
302 | span, ¶m_env_and_self_ty); | |
303 | debug!("probe_op: Mode::Path, param_env_and_self_ty={:?} self_ty={:?}", | |
304 | param_env_and_self_ty, self_ty); | |
305 | MethodAutoderefStepsResult { | |
306 | steps: Lrc::new(vec![CandidateStep { | |
307 | self_ty: self.make_query_response_ignoring_pending_obligations( | |
308 | canonical_inference_vars, self_ty), | |
309 | autoderefs: 0, | |
310 | from_unsafe_deref: false, | |
311 | unsize: false, | |
312 | }]), | |
313 | opt_bad_ty: None, | |
314 | reached_recursion_limit: false | |
315 | } | |
316 | }) | |
1a4d82fc JJ |
317 | }; |
318 | ||
0731742a XL |
319 | // If our autoderef loop had reached the recursion limit, |
320 | // report an overflow error, but continue going on with | |
321 | // the truncated autoderef list. | |
322 | if steps.reached_recursion_limit { | |
323 | self.probe(|_| { | |
324 | let ty = &steps.steps.last().unwrap_or_else(|| { | |
325 | span_bug!(span, "reached the recursion limit in 0 steps?") | |
326 | }).self_ty; | |
327 | let ty = self.probe_instantiate_query_response(span, &orig_values, ty) | |
328 | .unwrap_or_else(|_| span_bug!(span, "instantiating {:?} failed?", ty)); | |
329 | autoderef::report_autoderef_recursion_limit_error(self.tcx, span, | |
330 | ty.value); | |
331 | }); | |
332 | } | |
333 | ||
334 | ||
335 | // If we encountered an `_` type or an error type during autoderef, this is | |
336 | // ambiguous. | |
337 | if let Some(bad_ty) = &steps.opt_bad_ty { | |
338 | if is_suggestion.0 { | |
339 | // Ambiguity was encountered during a suggestion. Just keep going. | |
340 | debug!("ProbeContext: encountered ambiguity in suggestion"); | |
341 | } else if bad_ty.reached_raw_pointer && !self.tcx.features().arbitrary_self_types { | |
342 | // this case used to be allowed by the compiler, | |
343 | // so we do a future-compat lint here for the 2015 edition | |
344 | // (see https://github.com/rust-lang/rust/issues/46906) | |
345 | if self.tcx.sess.rust_2018() { | |
346 | span_err!(self.tcx.sess, span, E0699, | |
347 | "the type of this value must be known \ | |
348 | to call a method on a raw pointer on it"); | |
349 | } else { | |
532ac7d7 | 350 | self.tcx.lint_hir( |
0731742a XL |
351 | lint::builtin::TYVAR_BEHIND_RAW_POINTER, |
352 | scope_expr_id, | |
353 | span, | |
354 | "type annotations needed"); | |
355 | } | |
356 | } else { | |
357 | // Encountered a real ambiguity, so abort the lookup. If `ty` is not | |
358 | // an `Err`, report the right "type annotations needed" error pointing | |
359 | // to it. | |
360 | let ty = &bad_ty.ty; | |
361 | let ty = self.probe_instantiate_query_response(span, &orig_values, ty) | |
362 | .unwrap_or_else(|_| span_bug!(span, "instantiating {:?} failed?", ty)); | |
363 | let ty = self.structurally_resolved_type(span, ty.value); | |
364 | assert_eq!(ty, self.tcx.types.err); | |
365 | return Err(MethodError::NoMatch(NoMatchData::new(Vec::new(), | |
366 | Vec::new(), | |
367 | Vec::new(), | |
368 | None, | |
369 | mode))); | |
370 | } | |
371 | } | |
372 | ||
a7813a04 XL |
373 | debug!("ProbeContext: steps for self_ty={:?} are {:?}", |
374 | self_ty, | |
375 | steps); | |
376 | ||
0731742a | 377 | |
a7813a04 XL |
378 | // this creates one big transaction so that all type variables etc |
379 | // that we create during the probe process are removed later | |
380 | self.probe(|_| { | |
0531ce1d | 381 | let mut probe_cx = ProbeContext::new( |
0731742a XL |
382 | self, span, mode, method_name, return_type, orig_values, |
383 | steps.steps, is_suggestion, | |
0531ce1d | 384 | ); |
3b2f2976 | 385 | |
a7813a04 | 386 | probe_cx.assemble_inherent_candidates(); |
3b2f2976 XL |
387 | match scope { |
388 | ProbeScope::TraitsInScope => | |
389 | probe_cx.assemble_extension_candidates_for_traits_in_scope(scope_expr_id)?, | |
390 | ProbeScope::AllTraits => | |
391 | probe_cx.assemble_extension_candidates_for_all_traits()?, | |
392 | }; | |
32a655c1 | 393 | op(probe_cx) |
a7813a04 XL |
394 | }) |
395 | } | |
0731742a XL |
396 | } |
397 | ||
9fa01778 | 398 | pub fn provide(providers: &mut ty::query::Providers<'_>) { |
0731742a XL |
399 | providers.method_autoderef_steps = method_autoderef_steps; |
400 | } | |
401 | ||
dc9dc135 XL |
402 | fn method_autoderef_steps<'tcx>( |
403 | tcx: TyCtxt<'tcx>, | |
404 | goal: CanonicalTyGoal<'tcx>, | |
405 | ) -> MethodAutoderefStepsResult<'tcx> { | |
0731742a | 406 | debug!("method_autoderef_steps({:?})", goal); |
85aaf69f | 407 | |
0731742a XL |
408 | tcx.infer_ctxt().enter_with_canonical(DUMMY_SP, &goal, |ref infcx, goal, inference_vars| { |
409 | let ParamEnvAnd { param_env, value: self_ty } = goal; | |
a7813a04 | 410 | |
9fa01778 | 411 | let mut autoderef = Autoderef::new(infcx, param_env, hir::DUMMY_HIR_ID, DUMMY_SP, self_ty) |
0731742a XL |
412 | .include_raw_pointers() |
413 | .silence_errors(); | |
ff7c6d11 | 414 | let mut reached_raw_pointer = false; |
c30ab7b3 SL |
415 | let mut steps: Vec<_> = autoderef.by_ref() |
416 | .map(|(ty, d)| { | |
ff7c6d11 | 417 | let step = CandidateStep { |
0731742a XL |
418 | self_ty: infcx.make_query_response_ignoring_pending_obligations( |
419 | inference_vars.clone(), ty), | |
c30ab7b3 | 420 | autoderefs: d, |
ff7c6d11 | 421 | from_unsafe_deref: reached_raw_pointer, |
c30ab7b3 | 422 | unsize: false, |
ff7c6d11 | 423 | }; |
e74abb32 | 424 | if let ty::RawPtr(_) = ty.kind { |
ff7c6d11 XL |
425 | // all the subsequent steps will be from_unsafe_deref |
426 | reached_raw_pointer = true; | |
c30ab7b3 | 427 | } |
ff7c6d11 | 428 | step |
c30ab7b3 SL |
429 | }) |
430 | .collect(); | |
3157f602 | 431 | |
32a655c1 | 432 | let final_ty = autoderef.maybe_ambiguous_final_ty(); |
e74abb32 | 433 | let opt_bad_ty = match final_ty.kind { |
0731742a XL |
434 | ty::Infer(ty::TyVar(_)) | |
435 | ty::Error => { | |
436 | Some(MethodAutoderefBadTy { | |
437 | reached_raw_pointer, | |
438 | ty: infcx.make_query_response_ignoring_pending_obligations( | |
439 | inference_vars, final_ty) | |
440 | }) | |
32a655c1 | 441 | } |
b7449926 | 442 | ty::Array(elem_ty, _) => { |
3157f602 XL |
443 | let dereferences = steps.len() - 1; |
444 | ||
a7813a04 | 445 | steps.push(CandidateStep { |
0731742a XL |
446 | self_ty: infcx.make_query_response_ignoring_pending_obligations( |
447 | inference_vars, infcx.tcx.mk_slice(elem_ty)), | |
a7813a04 | 448 | autoderefs: dereferences, |
ff7c6d11 XL |
449 | // this could be from an unsafe deref if we had |
450 | // a *mut/const [T; N] | |
451 | from_unsafe_deref: reached_raw_pointer, | |
c30ab7b3 | 452 | unsize: true, |
a7813a04 | 453 | }); |
0731742a XL |
454 | |
455 | None | |
a7813a04 | 456 | } |
0731742a XL |
457 | _ => None |
458 | }; | |
1a4d82fc | 459 | |
0731742a | 460 | debug!("method_autoderef_steps: steps={:?} opt_bad_ty={:?}", steps, opt_bad_ty); |
3157f602 | 461 | |
0731742a XL |
462 | MethodAutoderefStepsResult { |
463 | steps: Lrc::new(steps), | |
464 | opt_bad_ty: opt_bad_ty.map(Lrc::new), | |
465 | reached_recursion_limit: autoderef.reached_recursion_limit() | |
466 | } | |
467 | }) | |
1a4d82fc JJ |
468 | } |
469 | ||
dc9dc135 XL |
470 | impl<'a, 'tcx> ProbeContext<'a, 'tcx> { |
471 | fn new( | |
472 | fcx: &'a FnCtxt<'a, 'tcx>, | |
473 | span: Span, | |
474 | mode: Mode, | |
475 | method_name: Option<ast::Ident>, | |
476 | return_type: Option<Ty<'tcx>>, | |
477 | orig_steps_var_values: OriginalQueryValues<'tcx>, | |
478 | steps: Lrc<Vec<CandidateStep<'tcx>>>, | |
479 | is_suggestion: IsSuggestion, | |
480 | ) -> ProbeContext<'a, 'tcx> { | |
1a4d82fc | 481 | ProbeContext { |
3b2f2976 XL |
482 | fcx, |
483 | span, | |
484 | mode, | |
ea8adc8c XL |
485 | method_name, |
486 | return_type, | |
1a4d82fc JJ |
487 | inherent_candidates: Vec::new(), |
488 | extension_candidates: Vec::new(), | |
0bf4aa26 | 489 | impl_dups: FxHashSet::default(), |
0731742a XL |
490 | orig_steps_var_values, |
491 | steps, | |
1a4d82fc | 492 | static_candidates: Vec::new(), |
ea8adc8c | 493 | allow_similar_names: false, |
54a0048b | 494 | private_candidate: None, |
62682a34 | 495 | unsatisfied_predicates: Vec::new(), |
0531ce1d | 496 | is_suggestion, |
1a4d82fc JJ |
497 | } |
498 | } | |
499 | ||
85aaf69f SL |
500 | fn reset(&mut self) { |
501 | self.inherent_candidates.clear(); | |
502 | self.extension_candidates.clear(); | |
503 | self.impl_dups.clear(); | |
504 | self.static_candidates.clear(); | |
54a0048b | 505 | self.private_candidate = None; |
85aaf69f SL |
506 | } |
507 | ||
1a4d82fc JJ |
508 | /////////////////////////////////////////////////////////////////////////// |
509 | // CANDIDATE ASSEMBLY | |
510 | ||
ea8adc8c XL |
511 | fn push_candidate(&mut self, |
512 | candidate: Candidate<'tcx>, | |
513 | is_inherent: bool) | |
514 | { | |
515 | let is_accessible = if let Some(name) = self.method_name { | |
516 | let item = candidate.item; | |
dc9dc135 XL |
517 | let def_scope = |
518 | self.tcx.adjust_ident_and_get_scope(name, item.container.id(), self.body_id).1; | |
7cac9316 XL |
519 | item.vis.is_accessible_from(def_scope, self.tcx) |
520 | } else { | |
521 | true | |
522 | }; | |
523 | if is_accessible { | |
ea8adc8c XL |
524 | if is_inherent { |
525 | self.inherent_candidates.push(candidate); | |
526 | } else { | |
527 | self.extension_candidates.push(candidate); | |
528 | } | |
7cac9316 | 529 | } else if self.private_candidate.is_none() { |
48663c56 XL |
530 | self.private_candidate = |
531 | Some((candidate.item.def_kind(), candidate.item.def_id)); | |
7cac9316 XL |
532 | } |
533 | } | |
534 | ||
1a4d82fc JJ |
535 | fn assemble_inherent_candidates(&mut self) { |
536 | let steps = self.steps.clone(); | |
62682a34 | 537 | for step in steps.iter() { |
0731742a | 538 | self.assemble_probe(&step.self_ty); |
1a4d82fc JJ |
539 | } |
540 | } | |
541 | ||
dc9dc135 | 542 | fn assemble_probe(&mut self, self_ty: &Canonical<'tcx, QueryResponse<'tcx, Ty<'tcx>>>) { |
c30ab7b3 | 543 | debug!("assemble_probe: self_ty={:?}", self_ty); |
ea8adc8c | 544 | let lang_items = self.tcx.lang_items(); |
1a4d82fc | 545 | |
e74abb32 | 546 | match self_ty.value.value.kind { |
b7449926 | 547 | ty::Dynamic(ref data, ..) => { |
0731742a XL |
548 | if let Some(p) = data.principal() { |
549 | // Subtle: we can't use `instantiate_query_response` here: using it will | |
550 | // commit to all of the type equalities assumed by inference going through | |
551 | // autoderef (see the `method-probe-no-guessing` test). | |
552 | // | |
553 | // However, in this code, it is OK if we end up with an object type that is | |
554 | // "more general" than the object type that we are evaluating. For *every* | |
555 | // object type `MY_OBJECT`, a function call that goes through a trait-ref | |
556 | // of the form `<MY_OBJECT as SuperTraitOf(MY_OBJECT)>::func` is a valid | |
557 | // `ObjectCandidate`, and it should be discoverable "exactly" through one | |
558 | // of the iterations in the autoderef loop, so there is no problem with it | |
559 | // being discoverable in another one of these iterations. | |
560 | // | |
561 | // Using `instantiate_canonical_with_fresh_inference_vars` on our | |
562 | // `Canonical<QueryResponse<Ty<'tcx>>>` and then *throwing away* the | |
563 | // `CanonicalVarValues` will exactly give us such a generalization - it | |
564 | // will still match the original object type, but it won't pollute our | |
565 | // type variables in any form, so just do that! | |
566 | let (QueryResponse { value: generalized_self_ty, .. }, _ignored_var_values) = | |
567 | self.fcx.instantiate_canonical_with_fresh_inference_vars( | |
568 | self.span, &self_ty); | |
569 | ||
570 | self.assemble_inherent_candidates_from_object(generalized_self_ty); | |
571 | self.assemble_inherent_impl_candidates_for_type(p.def_id()); | |
572 | } | |
1a4d82fc | 573 | } |
b7449926 | 574 | ty::Adt(def, _) => { |
e9174d1e | 575 | self.assemble_inherent_impl_candidates_for_type(def.did); |
1a4d82fc | 576 | } |
b7449926 | 577 | ty::Foreign(did) => { |
abe05a73 XL |
578 | self.assemble_inherent_impl_candidates_for_type(did); |
579 | } | |
b7449926 | 580 | ty::Param(p) => { |
0731742a | 581 | self.assemble_inherent_candidates_from_param(p); |
1a4d82fc | 582 | } |
e1599b0c XL |
583 | ty::Bool => { |
584 | let lang_def_id = lang_items.bool_impl(); | |
585 | self.assemble_inherent_impl_for_primitive(lang_def_id); | |
586 | } | |
b7449926 | 587 | ty::Char => { |
ea8adc8c | 588 | let lang_def_id = lang_items.char_impl(); |
c34b1796 AL |
589 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
590 | } | |
b7449926 | 591 | ty::Str => { |
ea8adc8c | 592 | let lang_def_id = lang_items.str_impl(); |
c34b1796 | 593 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
83c7162d XL |
594 | |
595 | let lang_def_id = lang_items.str_alloc_impl(); | |
596 | self.assemble_inherent_impl_for_primitive(lang_def_id); | |
c34b1796 | 597 | } |
b7449926 | 598 | ty::Slice(_) => { |
ea8adc8c | 599 | let lang_def_id = lang_items.slice_impl(); |
c34b1796 | 600 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
abe05a73 XL |
601 | |
602 | let lang_def_id = lang_items.slice_u8_impl(); | |
603 | self.assemble_inherent_impl_for_primitive(lang_def_id); | |
83c7162d XL |
604 | |
605 | let lang_def_id = lang_items.slice_alloc_impl(); | |
606 | self.assemble_inherent_impl_for_primitive(lang_def_id); | |
607 | ||
608 | let lang_def_id = lang_items.slice_u8_alloc_impl(); | |
609 | self.assemble_inherent_impl_for_primitive(lang_def_id); | |
c34b1796 | 610 | } |
60c5eb7d | 611 | ty::RawPtr(ty::TypeAndMut { ty: _, mutbl: hir::Mutability::Immutable }) => { |
ea8adc8c | 612 | let lang_def_id = lang_items.const_ptr_impl(); |
c34b1796 AL |
613 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
614 | } | |
60c5eb7d | 615 | ty::RawPtr(ty::TypeAndMut { ty: _, mutbl: hir::Mutability::Mutable }) => { |
ea8adc8c | 616 | let lang_def_id = lang_items.mut_ptr_impl(); |
c34b1796 AL |
617 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
618 | } | |
b7449926 | 619 | ty::Int(ast::IntTy::I8) => { |
ea8adc8c | 620 | let lang_def_id = lang_items.i8_impl(); |
c34b1796 AL |
621 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
622 | } | |
b7449926 | 623 | ty::Int(ast::IntTy::I16) => { |
ea8adc8c | 624 | let lang_def_id = lang_items.i16_impl(); |
c34b1796 AL |
625 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
626 | } | |
b7449926 | 627 | ty::Int(ast::IntTy::I32) => { |
ea8adc8c | 628 | let lang_def_id = lang_items.i32_impl(); |
c34b1796 AL |
629 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
630 | } | |
b7449926 | 631 | ty::Int(ast::IntTy::I64) => { |
ea8adc8c | 632 | let lang_def_id = lang_items.i64_impl(); |
c34b1796 AL |
633 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
634 | } | |
b7449926 | 635 | ty::Int(ast::IntTy::I128) => { |
ea8adc8c | 636 | let lang_def_id = lang_items.i128_impl(); |
32a655c1 SL |
637 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
638 | } | |
b7449926 | 639 | ty::Int(ast::IntTy::Isize) => { |
ea8adc8c | 640 | let lang_def_id = lang_items.isize_impl(); |
c34b1796 AL |
641 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
642 | } | |
b7449926 | 643 | ty::Uint(ast::UintTy::U8) => { |
ea8adc8c | 644 | let lang_def_id = lang_items.u8_impl(); |
c34b1796 AL |
645 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
646 | } | |
b7449926 | 647 | ty::Uint(ast::UintTy::U16) => { |
ea8adc8c | 648 | let lang_def_id = lang_items.u16_impl(); |
c34b1796 AL |
649 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
650 | } | |
b7449926 | 651 | ty::Uint(ast::UintTy::U32) => { |
ea8adc8c | 652 | let lang_def_id = lang_items.u32_impl(); |
c34b1796 AL |
653 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
654 | } | |
b7449926 | 655 | ty::Uint(ast::UintTy::U64) => { |
ea8adc8c | 656 | let lang_def_id = lang_items.u64_impl(); |
c34b1796 AL |
657 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
658 | } | |
b7449926 | 659 | ty::Uint(ast::UintTy::U128) => { |
ea8adc8c | 660 | let lang_def_id = lang_items.u128_impl(); |
32a655c1 SL |
661 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
662 | } | |
b7449926 | 663 | ty::Uint(ast::UintTy::Usize) => { |
ea8adc8c | 664 | let lang_def_id = lang_items.usize_impl(); |
c34b1796 AL |
665 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
666 | } | |
b7449926 | 667 | ty::Float(ast::FloatTy::F32) => { |
ea8adc8c | 668 | let lang_def_id = lang_items.f32_impl(); |
c34b1796 | 669 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
83c7162d XL |
670 | |
671 | let lang_def_id = lang_items.f32_runtime_impl(); | |
672 | self.assemble_inherent_impl_for_primitive(lang_def_id); | |
c34b1796 | 673 | } |
b7449926 | 674 | ty::Float(ast::FloatTy::F64) => { |
ea8adc8c | 675 | let lang_def_id = lang_items.f64_impl(); |
c34b1796 | 676 | self.assemble_inherent_impl_for_primitive(lang_def_id); |
83c7162d XL |
677 | |
678 | let lang_def_id = lang_items.f64_runtime_impl(); | |
679 | self.assemble_inherent_impl_for_primitive(lang_def_id); | |
c34b1796 | 680 | } |
c30ab7b3 | 681 | _ => {} |
1a4d82fc JJ |
682 | } |
683 | } | |
684 | ||
e9174d1e | 685 | fn assemble_inherent_impl_for_primitive(&mut self, lang_def_id: Option<DefId>) { |
c34b1796 | 686 | if let Some(impl_def_id) = lang_def_id { |
c34b1796 AL |
687 | self.assemble_inherent_impl_probe(impl_def_id); |
688 | } | |
689 | } | |
690 | ||
e9174d1e | 691 | fn assemble_inherent_impl_candidates_for_type(&mut self, def_id: DefId) { |
7cac9316 | 692 | let impl_def_ids = self.tcx.at(self.span).inherent_impls(def_id); |
cc61c64b XL |
693 | for &impl_def_id in impl_def_ids.iter() { |
694 | self.assemble_inherent_impl_probe(impl_def_id); | |
1a4d82fc JJ |
695 | } |
696 | } | |
697 | ||
e9174d1e | 698 | fn assemble_inherent_impl_probe(&mut self, impl_def_id: DefId) { |
1a4d82fc JJ |
699 | if !self.impl_dups.insert(impl_def_id) { |
700 | return; // already visited | |
701 | } | |
702 | ||
703 | debug!("assemble_inherent_impl_probe {:?}", impl_def_id); | |
704 | ||
32a655c1 SL |
705 | for item in self.impl_or_trait_item(impl_def_id) { |
706 | if !self.has_applicable_self(&item) { | |
707 | // No receiver declared. Not a candidate. | |
708 | self.record_static_candidate(ImplSource(impl_def_id)); | |
709 | continue | |
710 | } | |
1a4d82fc | 711 | |
32a655c1 SL |
712 | let (impl_ty, impl_substs) = self.impl_ty_and_substs(impl_def_id); |
713 | let impl_ty = impl_ty.subst(self.tcx, impl_substs); | |
54a0048b | 714 | |
32a655c1 | 715 | // Determine the receiver type that the method itself expects. |
ea8adc8c | 716 | let xform_tys = self.xform_self_ty(&item, impl_ty, impl_substs); |
32a655c1 SL |
717 | |
718 | // We can't use normalize_associated_types_in as it will pollute the | |
719 | // fcx's fulfillment context after this probe is over. | |
720 | let cause = traits::ObligationCause::misc(self.span, self.body_id); | |
3b2f2976 | 721 | let selcx = &mut traits::SelectionContext::new(self.fcx); |
ea8adc8c XL |
722 | let traits::Normalized { value: (xform_self_ty, xform_ret_ty), obligations } = |
723 | traits::normalize(selcx, self.param_env, cause, &xform_tys); | |
724 | debug!("assemble_inherent_impl_probe: xform_self_ty = {:?}/{:?}", | |
725 | xform_self_ty, xform_ret_ty); | |
726 | ||
727 | self.push_candidate(Candidate { | |
728 | xform_self_ty, xform_ret_ty, item, | |
729 | kind: InherentImplCandidate(impl_substs, obligations), | |
48663c56 | 730 | import_ids: smallvec![] |
ea8adc8c | 731 | }, true); |
32a655c1 | 732 | } |
1a4d82fc JJ |
733 | } |
734 | ||
735 | fn assemble_inherent_candidates_from_object(&mut self, | |
0731742a | 736 | self_ty: Ty<'tcx>) { |
62682a34 SL |
737 | debug!("assemble_inherent_candidates_from_object(self_ty={:?})", |
738 | self_ty); | |
1a4d82fc | 739 | |
e74abb32 | 740 | let principal = match self_ty.kind { |
0731742a XL |
741 | ty::Dynamic(ref data, ..) => Some(data), |
742 | _ => None | |
743 | }.and_then(|data| data.principal()).unwrap_or_else(|| { | |
744 | span_bug!(self.span, "non-object {:?} in assemble_inherent_candidates_from_object", | |
745 | self_ty) | |
746 | }); | |
747 | ||
1a4d82fc JJ |
748 | // It is illegal to invoke a method on a trait instance that |
749 | // refers to the `Self` type. An error will be reported by | |
750 | // `enforce_object_limitations()` if the method refers to the | |
751 | // `Self` type anywhere other than the receiver. Here, we use | |
752 | // a substitution that replaces `Self` with the object type | |
753 | // itself. Hence, a `&self` method will wind up with an | |
754 | // argument type like `&Trait`. | |
9e0c209e | 755 | let trait_ref = principal.with_self_ty(self.tcx, self_ty); |
a1dfa0c6 | 756 | self.elaborate_bounds(iter::once(trait_ref), |this, new_trait_ref, item| { |
1a4d82fc JJ |
757 | let new_trait_ref = this.erase_late_bound_regions(&new_trait_ref); |
758 | ||
ea8adc8c | 759 | let (xform_self_ty, xform_ret_ty) = |
c30ab7b3 | 760 | this.xform_self_ty(&item, new_trait_ref.self_ty(), new_trait_ref.substs); |
ea8adc8c XL |
761 | this.push_candidate(Candidate { |
762 | xform_self_ty, xform_ret_ty, item, | |
763 | kind: ObjectCandidate, | |
48663c56 | 764 | import_ids: smallvec![] |
ea8adc8c | 765 | }, true); |
1a4d82fc JJ |
766 | }); |
767 | } | |
768 | ||
48663c56 | 769 | fn assemble_inherent_candidates_from_param(&mut self, param_ty: ty::ParamTy) { |
dc9dc135 | 770 | // FIXME: do we want to commit to this behavior for param bounds? |
1a4d82fc | 771 | |
a1dfa0c6 | 772 | let bounds = self.param_env |
c30ab7b3 | 773 | .caller_bounds |
1a4d82fc JJ |
774 | .iter() |
775 | .filter_map(|predicate| { | |
776 | match *predicate { | |
777 | ty::Predicate::Trait(ref trait_predicate) => { | |
e74abb32 | 778 | match trait_predicate.skip_binder().trait_ref.self_ty().kind { |
b7449926 | 779 | ty::Param(ref p) if *p == param_ty => { |
1a4d82fc JJ |
780 | Some(trait_predicate.to_poly_trait_ref()) |
781 | } | |
c30ab7b3 | 782 | _ => None, |
1a4d82fc JJ |
783 | } |
784 | } | |
cc61c64b | 785 | ty::Predicate::Subtype(..) | |
1a4d82fc JJ |
786 | ty::Predicate::Projection(..) | |
787 | ty::Predicate::RegionOutlives(..) | | |
e9174d1e SL |
788 | ty::Predicate::WellFormed(..) | |
789 | ty::Predicate::ObjectSafe(..) | | |
a7813a04 | 790 | ty::Predicate::ClosureKind(..) | |
ea8adc8c XL |
791 | ty::Predicate::TypeOutlives(..) | |
792 | ty::Predicate::ConstEvaluatable(..) => None, | |
1a4d82fc | 793 | } |
a1dfa0c6 | 794 | }); |
1a4d82fc | 795 | |
a1dfa0c6 | 796 | self.elaborate_bounds(bounds, |this, poly_trait_ref, item| { |
c30ab7b3 | 797 | let trait_ref = this.erase_late_bound_regions(&poly_trait_ref); |
1a4d82fc | 798 | |
ea8adc8c XL |
799 | let (xform_self_ty, xform_ret_ty) = |
800 | this.xform_self_ty(&item, trait_ref.self_ty(), trait_ref.substs); | |
1a4d82fc | 801 | |
1a4d82fc JJ |
802 | // Because this trait derives from a where-clause, it |
803 | // should not contain any inference variables or other | |
804 | // artifacts. This means it is safe to put into the | |
805 | // `WhereClauseCandidate` and (eventually) into the | |
806 | // `WhereClausePick`. | |
9e0c209e | 807 | assert!(!trait_ref.substs.needs_infer()); |
1a4d82fc | 808 | |
ea8adc8c XL |
809 | this.push_candidate(Candidate { |
810 | xform_self_ty, xform_ret_ty, item, | |
811 | kind: WhereClauseCandidate(poly_trait_ref), | |
48663c56 | 812 | import_ids: smallvec![] |
ea8adc8c | 813 | }, true); |
1a4d82fc JJ |
814 | }); |
815 | } | |
816 | ||
817 | // Do a search through a list of bounds, using a callback to actually | |
818 | // create the candidates. | |
dc9dc135 XL |
819 | fn elaborate_bounds<F>( |
820 | &mut self, | |
821 | bounds: impl Iterator<Item = ty::PolyTraitRef<'tcx>>, | |
822 | mut mk_cand: F, | |
823 | ) where | |
824 | F: for<'b> FnMut(&mut ProbeContext<'b, 'tcx>, ty::PolyTraitRef<'tcx>, ty::AssocItem), | |
1a4d82fc | 825 | { |
a7813a04 | 826 | let tcx = self.tcx; |
1a4d82fc | 827 | for bound_trait_ref in traits::transitive_bounds(tcx, bounds) { |
a1dfa0c6 | 828 | debug!("elaborate_bounds(bound_trait_ref={:?})", bound_trait_ref); |
32a655c1 SL |
829 | for item in self.impl_or_trait_item(bound_trait_ref.def_id()) { |
830 | if !self.has_applicable_self(&item) { | |
831 | self.record_static_candidate(TraitSource(bound_trait_ref.def_id())); | |
832 | } else { | |
833 | mk_cand(self, bound_trait_ref, item); | |
c30ab7b3 | 834 | } |
1a4d82fc JJ |
835 | } |
836 | } | |
837 | } | |
838 | ||
839 | fn assemble_extension_candidates_for_traits_in_scope(&mut self, | |
532ac7d7 | 840 | expr_hir_id: hir::HirId) |
c30ab7b3 | 841 | -> Result<(), MethodError<'tcx>> { |
532ac7d7 | 842 | if expr_hir_id == hir::DUMMY_HIR_ID { |
ea8adc8c XL |
843 | return Ok(()) |
844 | } | |
0bf4aa26 | 845 | let mut duplicates = FxHashSet::default(); |
ea8adc8c | 846 | let opt_applicable_traits = self.tcx.in_scope_traits(expr_hir_id); |
85aaf69f | 847 | if let Some(applicable_traits) = opt_applicable_traits { |
ea8adc8c | 848 | for trait_candidate in applicable_traits.iter() { |
a7813a04 | 849 | let trait_did = trait_candidate.def_id; |
1a4d82fc | 850 | if duplicates.insert(trait_did) { |
48663c56 XL |
851 | let import_ids = trait_candidate.import_ids.iter().map(|node_id| |
852 | self.fcx.tcx.hir().node_to_hir_id(*node_id)).collect(); | |
853 | let result = self.assemble_extension_candidates_for_trait(import_ids, | |
854 | trait_did); | |
a7813a04 | 855 | result?; |
1a4d82fc JJ |
856 | } |
857 | } | |
858 | } | |
85aaf69f SL |
859 | Ok(()) |
860 | } | |
861 | ||
62682a34 | 862 | fn assemble_extension_candidates_for_all_traits(&mut self) -> Result<(), MethodError<'tcx>> { |
0bf4aa26 | 863 | let mut duplicates = FxHashSet::default(); |
8bb4bdeb | 864 | for trait_info in suggest::all_traits(self.tcx) { |
85aaf69f | 865 | if duplicates.insert(trait_info.def_id) { |
48663c56 | 866 | self.assemble_extension_candidates_for_trait(smallvec![], trait_info.def_id)?; |
85aaf69f SL |
867 | } |
868 | } | |
869 | Ok(()) | |
1a4d82fc JJ |
870 | } |
871 | ||
ea8adc8c | 872 | pub fn matches_return_type(&self, |
dc9dc135 | 873 | method: &ty::AssocItem, |
ea8adc8c XL |
874 | self_ty: Option<Ty<'tcx>>, |
875 | expected: Ty<'tcx>) -> bool { | |
48663c56 | 876 | match method.kind { |
dc9dc135 | 877 | ty::AssocKind::Method => { |
48663c56 | 878 | let fty = self.tcx.fn_sig(method.def_id); |
32a655c1 SL |
879 | self.probe(|_| { |
880 | let substs = self.fresh_substs_for_item(self.span, method.def_id); | |
ea8adc8c | 881 | let fty = fty.subst(self.tcx, substs); |
a1dfa0c6 XL |
882 | let (fty, _) = self.replace_bound_vars_with_fresh_vars( |
883 | self.span, | |
884 | infer::FnCall, | |
885 | &fty | |
886 | ); | |
ea8adc8c XL |
887 | |
888 | if let Some(self_ty) = self_ty { | |
b7449926 XL |
889 | if self.at(&ObligationCause::dummy(), self.param_env) |
890 | .sup(fty.inputs()[0], self_ty) | |
891 | .is_err() | |
ea8adc8c XL |
892 | { |
893 | return false | |
894 | } | |
895 | } | |
896 | self.can_sub(self.param_env, fty.output(), expected).is_ok() | |
32a655c1 SL |
897 | }) |
898 | } | |
899 | _ => false, | |
900 | } | |
901 | } | |
902 | ||
1a4d82fc | 903 | fn assemble_extension_candidates_for_trait(&mut self, |
48663c56 | 904 | import_ids: SmallVec<[hir::HirId; 1]>, |
e9174d1e | 905 | trait_def_id: DefId) |
c30ab7b3 | 906 | -> Result<(), MethodError<'tcx>> { |
62682a34 SL |
907 | debug!("assemble_extension_candidates_for_trait(trait_def_id={:?})", |
908 | trait_def_id); | |
ea8adc8c XL |
909 | let trait_substs = self.fresh_item_substs(trait_def_id); |
910 | let trait_ref = ty::TraitRef::new(trait_def_id, trait_substs); | |
1a4d82fc | 911 | |
532ac7d7 XL |
912 | if self.tcx.is_trait_alias(trait_def_id) { |
913 | // For trait aliases, assume all super-traits are relevant. | |
914 | let bounds = iter::once(trait_ref.to_poly_trait_ref()); | |
915 | self.elaborate_bounds(bounds, |this, new_trait_ref, item| { | |
916 | let new_trait_ref = this.erase_late_bound_regions(&new_trait_ref); | |
917 | ||
918 | let (xform_self_ty, xform_ret_ty) = | |
919 | this.xform_self_ty(&item, new_trait_ref.self_ty(), new_trait_ref.substs); | |
920 | this.push_candidate(Candidate { | |
48663c56 | 921 | xform_self_ty, xform_ret_ty, item, import_ids: import_ids.clone(), |
532ac7d7 XL |
922 | kind: TraitCandidate(new_trait_ref), |
923 | }, true); | |
924 | }); | |
925 | } else { | |
926 | debug_assert!(self.tcx.is_trait(trait_def_id)); | |
927 | for item in self.impl_or_trait_item(trait_def_id) { | |
928 | // Check whether `trait_def_id` defines a method with suitable name. | |
929 | if !self.has_applicable_self(&item) { | |
930 | debug!("method has inapplicable self"); | |
931 | self.record_static_candidate(TraitSource(trait_def_id)); | |
932 | continue; | |
933 | } | |
1a4d82fc | 934 | |
532ac7d7 XL |
935 | let (xform_self_ty, xform_ret_ty) = |
936 | self.xform_self_ty(&item, trait_ref.self_ty(), trait_substs); | |
937 | self.push_candidate(Candidate { | |
48663c56 | 938 | xform_self_ty, xform_ret_ty, item, import_ids: import_ids.clone(), |
532ac7d7 XL |
939 | kind: TraitCandidate(trait_ref), |
940 | }, false); | |
941 | } | |
32a655c1 | 942 | } |
85aaf69f | 943 | Ok(()) |
1a4d82fc JJ |
944 | } |
945 | ||
8faf50e0 | 946 | fn candidate_method_names(&self) -> Vec<ast::Ident> { |
0bf4aa26 | 947 | let mut set = FxHashSet::default(); |
ea8adc8c XL |
948 | let mut names: Vec<_> = self.inherent_candidates |
949 | .iter() | |
950 | .chain(&self.extension_candidates) | |
951 | .filter(|candidate| { | |
952 | if let Some(return_ty) = self.return_type { | |
953 | self.matches_return_type(&candidate.item, None, return_ty) | |
954 | } else { | |
955 | true | |
956 | } | |
957 | }) | |
8faf50e0 | 958 | .map(|candidate| candidate.item.ident) |
ea8adc8c XL |
959 | .filter(|&name| set.insert(name)) |
960 | .collect(); | |
32a655c1 | 961 | |
532ac7d7 | 962 | // Sort them by the name so we have a stable result. |
83c7162d | 963 | names.sort_by_cached_key(|n| n.as_str()); |
32a655c1 SL |
964 | names |
965 | } | |
966 | ||
1a4d82fc JJ |
967 | /////////////////////////////////////////////////////////////////////////// |
968 | // THE ACTUAL SEARCH | |
969 | ||
970 | fn pick(mut self) -> PickResult<'tcx> { | |
ea8adc8c | 971 | assert!(self.method_name.is_some()); |
32a655c1 | 972 | |
3157f602 XL |
973 | if let Some(r) = self.pick_core() { |
974 | return r; | |
85aaf69f | 975 | } |
1a4d82fc | 976 | |
532ac7d7 XL |
977 | debug!("pick: actual search failed, assemble diagnotics"); |
978 | ||
416331ca | 979 | let static_candidates = mem::take(&mut self.static_candidates); |
a1dfa0c6 | 980 | let private_candidate = self.private_candidate.take(); |
416331ca | 981 | let unsatisfied_predicates = mem::take(&mut self.unsatisfied_predicates); |
85aaf69f SL |
982 | |
983 | // things failed, so lets look at all traits, for diagnostic purposes now: | |
984 | self.reset(); | |
985 | ||
986 | let span = self.span; | |
a7813a04 | 987 | let tcx = self.tcx; |
85aaf69f | 988 | |
54a0048b | 989 | self.assemble_extension_candidates_for_all_traits()?; |
85aaf69f SL |
990 | |
991 | let out_of_scope_traits = match self.pick_core() { | |
476ff2be | 992 | Some(Ok(p)) => vec![p.item.container.id()], |
32a655c1 | 993 | //Some(Ok(p)) => p.iter().map(|p| p.item.container().id()).collect(), |
c30ab7b3 SL |
994 | Some(Err(MethodError::Ambiguity(v))) => { |
995 | v.into_iter() | |
996 | .map(|source| { | |
997 | match source { | |
998 | TraitSource(id) => id, | |
999 | ImplSource(impl_id) => { | |
1000 | match tcx.trait_id_of_impl(impl_id) { | |
1001 | Some(id) => id, | |
1002 | None => { | |
1003 | span_bug!(span, | |
1004 | "found inherent method when looking at traits") | |
1005 | } | |
1006 | } | |
1007 | } | |
85aaf69f | 1008 | } |
c30ab7b3 SL |
1009 | }) |
1010 | .collect() | |
1011 | } | |
62682a34 | 1012 | Some(Err(MethodError::NoMatch(NoMatchData { out_of_scope_traits: others, .. }))) => { |
85aaf69f SL |
1013 | assert!(others.is_empty()); |
1014 | vec![] | |
1a4d82fc | 1015 | } |
54a0048b | 1016 | _ => vec![], |
85aaf69f SL |
1017 | }; |
1018 | ||
48663c56 XL |
1019 | if let Some((kind, def_id)) = private_candidate { |
1020 | return Err(MethodError::PrivateMatch(kind, def_id, out_of_scope_traits)); | |
54a0048b | 1021 | } |
ea8adc8c | 1022 | let lev_candidate = self.probe_for_lev_candidate()?; |
54a0048b | 1023 | |
c30ab7b3 SL |
1024 | Err(MethodError::NoMatch(NoMatchData::new(static_candidates, |
1025 | unsatisfied_predicates, | |
1026 | out_of_scope_traits, | |
ea8adc8c | 1027 | lev_candidate, |
c30ab7b3 | 1028 | self.mode))) |
85aaf69f SL |
1029 | } |
1030 | ||
1031 | fn pick_core(&mut self) -> Option<PickResult<'tcx>> { | |
1032 | let steps = self.steps.clone(); | |
1a4d82fc | 1033 | |
85aaf69f | 1034 | // find the first step that works |
ea8adc8c XL |
1035 | steps |
1036 | .iter() | |
1037 | .filter(|step| { | |
1038 | debug!("pick_core: step={:?}", step); | |
ff7c6d11 XL |
1039 | // skip types that are from a type error or that would require dereferencing |
1040 | // a raw pointer | |
1041 | !step.self_ty.references_error() && !step.from_unsafe_deref | |
ea8adc8c | 1042 | }).flat_map(|step| { |
0731742a XL |
1043 | let InferOk { value: self_ty, obligations: _ } = |
1044 | self.fcx.probe_instantiate_query_response( | |
1045 | self.span, &self.orig_steps_var_values, &step.self_ty | |
1046 | ).unwrap_or_else(|_| { | |
1047 | span_bug!(self.span, "{:?} was applicable but now isn't?", step.self_ty) | |
1048 | }); | |
1049 | self.pick_by_value_method(step, self_ty).or_else(|| { | |
60c5eb7d XL |
1050 | self.pick_autorefd_method(step, self_ty, hir::Mutability::Immutable).or_else(|| { |
1051 | self.pick_autorefd_method(step, self_ty, hir::Mutability::Mutable) | |
ea8adc8c XL |
1052 | })})}) |
1053 | .next() | |
1a4d82fc JJ |
1054 | } |
1055 | ||
dc9dc135 XL |
1056 | fn pick_by_value_method( |
1057 | &mut self, | |
1058 | step: &CandidateStep<'tcx>, | |
1059 | self_ty: Ty<'tcx>, | |
1060 | ) -> Option<PickResult<'tcx>> { | |
c30ab7b3 SL |
1061 | //! For each type `T` in the step list, this attempts to find a |
1062 | //! method where the (transformed) self type is exactly `T`. We | |
1063 | //! do however do one transformation on the adjustment: if we | |
1064 | //! are passing a region pointer in, we will potentially | |
1065 | //! *reborrow* it to a shorter lifetime. This allows us to | |
1066 | //! transparently pass `&mut` pointers, in particular, without | |
1067 | //! consuming them for their entire lifetime. | |
1a4d82fc | 1068 | |
9346a6ac AL |
1069 | if step.unsize { |
1070 | return None; | |
1071 | } | |
1a4d82fc | 1072 | |
0731742a | 1073 | self.pick_method(self_ty).map(|r| { |
c30ab7b3 SL |
1074 | r.map(|mut pick| { |
1075 | pick.autoderefs = step.autoderefs; | |
1a4d82fc | 1076 | |
c30ab7b3 | 1077 | // Insert a `&*` or `&mut *` if this is a reference type: |
e74abb32 | 1078 | if let ty::Ref(_, _, mutbl) = step.self_ty.value.value.kind { |
c30ab7b3 | 1079 | pick.autoderefs += 1; |
94b46f34 | 1080 | pick.autoref = Some(mutbl); |
c30ab7b3 | 1081 | } |
9346a6ac | 1082 | |
c30ab7b3 SL |
1083 | pick |
1084 | }) | |
1085 | }) | |
1a4d82fc JJ |
1086 | } |
1087 | ||
dc9dc135 XL |
1088 | fn pick_autorefd_method( |
1089 | &mut self, | |
1090 | step: &CandidateStep<'tcx>, | |
1091 | self_ty: Ty<'tcx>, | |
1092 | mutbl: hir::Mutability, | |
1093 | ) -> Option<PickResult<'tcx>> { | |
a7813a04 | 1094 | let tcx = self.tcx; |
1a4d82fc | 1095 | |
1a4d82fc JJ |
1096 | // In general, during probing we erase regions. See |
1097 | // `impl_self_ty()` for an explanation. | |
48663c56 | 1098 | let region = tcx.lifetimes.re_erased; |
1a4d82fc | 1099 | |
ea8adc8c XL |
1100 | let autoref_ty = tcx.mk_ref(region, |
1101 | ty::TypeAndMut { | |
0731742a | 1102 | ty: self_ty, mutbl |
ea8adc8c XL |
1103 | }); |
1104 | self.pick_method(autoref_ty).map(|r| { | |
1105 | r.map(|mut pick| { | |
1106 | pick.autoderefs = step.autoderefs; | |
1107 | pick.autoref = Some(mutbl); | |
60c5eb7d | 1108 | pick.unsize = step.unsize.then_some(self_ty); |
ea8adc8c | 1109 | pick |
c30ab7b3 | 1110 | }) |
ea8adc8c | 1111 | }) |
1a4d82fc JJ |
1112 | } |
1113 | ||
1114 | fn pick_method(&mut self, self_ty: Ty<'tcx>) -> Option<PickResult<'tcx>> { | |
a7813a04 | 1115 | debug!("pick_method(self_ty={})", self.ty_to_string(self_ty)); |
1a4d82fc | 1116 | |
62682a34 | 1117 | let mut possibly_unsatisfied_predicates = Vec::new(); |
0531ce1d XL |
1118 | let mut unstable_candidates = Vec::new(); |
1119 | ||
1120 | for (kind, candidates) in &[ | |
1121 | ("inherent", &self.inherent_candidates), | |
1122 | ("extension", &self.extension_candidates), | |
1123 | ] { | |
1124 | debug!("searching {} candidates", kind); | |
1125 | let res = self.consider_candidates( | |
1126 | self_ty, | |
1127 | candidates.iter(), | |
1128 | &mut possibly_unsatisfied_predicates, | |
1129 | Some(&mut unstable_candidates), | |
1130 | ); | |
1131 | if let Some(pick) = res { | |
1132 | if !self.is_suggestion.0 && !unstable_candidates.is_empty() { | |
1133 | if let Ok(p) = &pick { | |
1134 | // Emit a lint if there are unstable candidates alongside the stable ones. | |
1135 | // | |
1136 | // We suppress warning if we're picking the method only because it is a | |
1137 | // suggestion. | |
1138 | self.emit_unstable_name_collision_hint(p, &unstable_candidates); | |
1139 | } | |
1140 | } | |
1141 | return Some(pick); | |
1142 | } | |
1a4d82fc JJ |
1143 | } |
1144 | ||
0531ce1d XL |
1145 | debug!("searching unstable candidates"); |
1146 | let res = self.consider_candidates( | |
1147 | self_ty, | |
1148 | unstable_candidates.into_iter().map(|(c, _)| c), | |
1149 | &mut possibly_unsatisfied_predicates, | |
1150 | None, | |
1151 | ); | |
1152 | if res.is_none() { | |
62682a34 SL |
1153 | self.unsatisfied_predicates.extend(possibly_unsatisfied_predicates); |
1154 | } | |
1155 | res | |
1a4d82fc JJ |
1156 | } |
1157 | ||
0531ce1d XL |
1158 | fn consider_candidates<'b, ProbesIter>( |
1159 | &self, | |
1160 | self_ty: Ty<'tcx>, | |
1161 | probes: ProbesIter, | |
1162 | possibly_unsatisfied_predicates: &mut Vec<TraitRef<'tcx>>, | |
1163 | unstable_candidates: Option<&mut Vec<(&'b Candidate<'tcx>, Symbol)>>, | |
1164 | ) -> Option<PickResult<'tcx>> | |
1165 | where | |
1166 | ProbesIter: Iterator<Item = &'b Candidate<'tcx>> + Clone, | |
1167 | { | |
1168 | let mut applicable_candidates: Vec<_> = probes.clone() | |
ea8adc8c XL |
1169 | .map(|probe| { |
1170 | (probe, self.consider_probe(self_ty, probe, possibly_unsatisfied_predicates)) | |
1171 | }) | |
1172 | .filter(|&(_, status)| status != ProbeResult::NoMatch) | |
c30ab7b3 | 1173 | .collect(); |
1a4d82fc | 1174 | |
62682a34 | 1175 | debug!("applicable_candidates: {:?}", applicable_candidates); |
1a4d82fc JJ |
1176 | |
1177 | if applicable_candidates.len() > 1 { | |
ea8adc8c XL |
1178 | if let Some(pick) = self.collapse_candidates_to_trait_pick(&applicable_candidates[..]) { |
1179 | return Some(Ok(pick)); | |
1a4d82fc JJ |
1180 | } |
1181 | } | |
1182 | ||
0531ce1d XL |
1183 | if let Some(uc) = unstable_candidates { |
1184 | applicable_candidates.retain(|&(p, _)| { | |
1185 | if let stability::EvalResult::Deny { feature, .. } = | |
1186 | self.tcx.eval_stability(p.item.def_id, None, self.span) | |
1187 | { | |
1188 | uc.push((p, feature)); | |
1189 | return false; | |
1190 | } | |
1191 | true | |
1192 | }); | |
1193 | } | |
1194 | ||
1a4d82fc | 1195 | if applicable_candidates.len() > 1 { |
0531ce1d | 1196 | let sources = probes |
ea8adc8c XL |
1197 | .map(|p| self.candidate_source(p, self_ty)) |
1198 | .collect(); | |
85aaf69f | 1199 | return Some(Err(MethodError::Ambiguity(sources))); |
1a4d82fc JJ |
1200 | } |
1201 | ||
ea8adc8c XL |
1202 | applicable_candidates.pop().map(|(probe, status)| { |
1203 | if status == ProbeResult::Match { | |
1204 | Ok(probe.to_unadjusted_pick()) | |
1205 | } else { | |
1206 | Err(MethodError::BadReturnType) | |
1207 | } | |
1208 | }) | |
1209 | } | |
1210 | ||
0531ce1d XL |
1211 | fn emit_unstable_name_collision_hint( |
1212 | &self, | |
9fa01778 | 1213 | stable_pick: &Pick<'_>, |
0531ce1d XL |
1214 | unstable_candidates: &[(&Candidate<'tcx>, Symbol)], |
1215 | ) { | |
9fa01778 | 1216 | let mut diag = self.tcx.struct_span_lint_hir( |
83c7162d | 1217 | lint::builtin::UNSTABLE_NAME_COLLISIONS, |
0531ce1d XL |
1218 | self.fcx.body_id, |
1219 | self.span, | |
1220 | "a method with this name may be added to the standard library in the future", | |
1221 | ); | |
1222 | ||
9fa01778 | 1223 | // FIXME: This should be a `span_suggestion` instead of `help` |
0bf4aa26 | 1224 | // However `self.span` only |
0531ce1d XL |
1225 | // highlights the method name, so we can't use it. Also consider reusing the code from |
1226 | // `report_method_error()`. | |
1227 | diag.help(&format!( | |
1228 | "call with fully qualified syntax `{}(...)` to keep using the current method", | |
532ac7d7 | 1229 | self.tcx.def_path_str(stable_pick.item.def_id), |
0531ce1d XL |
1230 | )); |
1231 | ||
0bf4aa26 | 1232 | if nightly_options::is_nightly_build() { |
0531ce1d | 1233 | for (candidate, feature) in unstable_candidates { |
0bf4aa26 | 1234 | diag.help(&format!( |
416331ca | 1235 | "add `#![feature({})]` to the crate attributes to enable `{}`", |
0531ce1d | 1236 | feature, |
532ac7d7 | 1237 | self.tcx.def_path_str(candidate.item.def_id), |
0531ce1d XL |
1238 | )); |
1239 | } | |
1240 | } | |
1241 | ||
1242 | diag.emit(); | |
1243 | } | |
1244 | ||
ea8adc8c XL |
1245 | fn select_trait_candidate(&self, trait_ref: ty::TraitRef<'tcx>) |
1246 | -> traits::SelectionResult<'tcx, traits::Selection<'tcx>> | |
1247 | { | |
1248 | let cause = traits::ObligationCause::misc(self.span, self.body_id); | |
1249 | let predicate = | |
1250 | trait_ref.to_poly_trait_ref().to_poly_trait_predicate(); | |
1251 | let obligation = traits::Obligation::new(cause, self.param_env, predicate); | |
1252 | traits::SelectionContext::new(self).select(&obligation) | |
1253 | } | |
1254 | ||
1255 | fn candidate_source(&self, candidate: &Candidate<'tcx>, self_ty: Ty<'tcx>) | |
1256 | -> CandidateSource | |
1257 | { | |
1258 | match candidate.kind { | |
1259 | InherentImplCandidate(..) => ImplSource(candidate.item.container.id()), | |
1260 | ObjectCandidate | | |
1261 | WhereClauseCandidate(_) => TraitSource(candidate.item.container.id()), | |
1262 | TraitCandidate(trait_ref) => self.probe(|_| { | |
1263 | let _ = self.at(&ObligationCause::dummy(), self.param_env) | |
1264 | .sup(candidate.xform_self_ty, self_ty); | |
1265 | match self.select_trait_candidate(trait_ref) { | |
1266 | Ok(Some(traits::Vtable::VtableImpl(ref impl_data))) => { | |
1267 | // If only a single impl matches, make the error message point | |
1268 | // to that impl. | |
1269 | ImplSource(impl_data.impl_def_id) | |
1270 | } | |
1271 | _ => { | |
1272 | TraitSource(candidate.item.container.id()) | |
1273 | } | |
1274 | } | |
1275 | }) | |
1276 | } | |
1a4d82fc JJ |
1277 | } |
1278 | ||
c30ab7b3 SL |
1279 | fn consider_probe(&self, |
1280 | self_ty: Ty<'tcx>, | |
1281 | probe: &Candidate<'tcx>, | |
1282 | possibly_unsatisfied_predicates: &mut Vec<TraitRef<'tcx>>) | |
ea8adc8c | 1283 | -> ProbeResult { |
c30ab7b3 | 1284 | debug!("consider_probe: self_ty={:?} probe={:?}", self_ty, probe); |
1a4d82fc | 1285 | |
a7813a04 | 1286 | self.probe(|_| { |
1a4d82fc | 1287 | // First check that the self type can be related. |
7cac9316 XL |
1288 | let sub_obligations = match self.at(&ObligationCause::dummy(), self.param_env) |
1289 | .sup(probe.xform_self_ty, self_ty) { | |
cc61c64b | 1290 | Ok(InferOk { obligations, value: () }) => obligations, |
1a4d82fc JJ |
1291 | Err(_) => { |
1292 | debug!("--> cannot relate self-types"); | |
ea8adc8c | 1293 | return ProbeResult::NoMatch; |
1a4d82fc | 1294 | } |
cc61c64b | 1295 | }; |
1a4d82fc | 1296 | |
ea8adc8c XL |
1297 | let mut result = ProbeResult::Match; |
1298 | let selcx = &mut traits::SelectionContext::new(self); | |
1299 | let cause = traits::ObligationCause::misc(self.span, self.body_id); | |
1300 | ||
1a4d82fc JJ |
1301 | // If so, impls may carry other conditions (e.g., where |
1302 | // clauses) that must be considered. Make sure that those | |
1303 | // match as well (or at least may match, sometimes we | |
1304 | // don't have enough information to fully evaluate). | |
ea8adc8c | 1305 | let candidate_obligations : Vec<_> = match probe.kind { |
c1a9b12d | 1306 | InherentImplCandidate(ref substs, ref ref_obligations) => { |
ea8adc8c XL |
1307 | // Check whether the impl imposes obligations we have to worry about. |
1308 | let impl_def_id = probe.item.container.id(); | |
1309 | let impl_bounds = self.tcx.predicates_of(impl_def_id); | |
1310 | let impl_bounds = impl_bounds.instantiate(self.tcx, substs); | |
1311 | let traits::Normalized { value: impl_bounds, obligations: norm_obligations } = | |
1312 | traits::normalize(selcx, self.param_env, cause.clone(), &impl_bounds); | |
1313 | ||
1314 | // Convert the bounds into obligations. | |
1315 | let impl_obligations = traits::predicates_for_generics( | |
0bf4aa26 | 1316 | cause, self.param_env, &impl_bounds); |
ea8adc8c XL |
1317 | |
1318 | debug!("impl_obligations={:?}", impl_obligations); | |
1319 | impl_obligations.into_iter() | |
1320 | .chain(norm_obligations.into_iter()) | |
1321 | .chain(ref_obligations.iter().cloned()) | |
1322 | .collect() | |
1a4d82fc JJ |
1323 | } |
1324 | ||
92a42be0 | 1325 | ObjectCandidate | |
1a4d82fc JJ |
1326 | WhereClauseCandidate(..) => { |
1327 | // These have no additional conditions to check. | |
ea8adc8c | 1328 | vec![] |
c1a9b12d | 1329 | } |
c1a9b12d | 1330 | |
ea8adc8c XL |
1331 | TraitCandidate(trait_ref) => { |
1332 | let predicate = trait_ref.to_predicate(); | |
1333 | let obligation = | |
0bf4aa26 | 1334 | traits::Obligation::new(cause, self.param_env, predicate); |
83c7162d | 1335 | if !self.predicate_may_hold(&obligation) { |
ea8adc8c XL |
1336 | if self.probe(|_| self.select_trait_candidate(trait_ref).is_err()) { |
1337 | // This candidate's primary obligation doesn't even | |
1338 | // select - don't bother registering anything in | |
1339 | // `potentially_unsatisfied_predicates`. | |
1340 | return ProbeResult::NoMatch; | |
1341 | } else { | |
1342 | // Some nested subobligation of this predicate | |
1343 | // failed. | |
1344 | // | |
1345 | // FIXME: try to find the exact nested subobligation | |
1346 | // and point at it rather than reporting the entire | |
1347 | // trait-ref? | |
1348 | result = ProbeResult::NoMatch; | |
dc9dc135 | 1349 | let trait_ref = self.resolve_vars_if_possible(&trait_ref); |
ea8adc8c XL |
1350 | possibly_unsatisfied_predicates.push(trait_ref); |
1351 | } | |
1352 | } | |
1353 | vec![] | |
1354 | } | |
1355 | }; | |
c1a9b12d | 1356 | |
ea8adc8c XL |
1357 | debug!("consider_probe - candidate_obligations={:?} sub_obligations={:?}", |
1358 | candidate_obligations, sub_obligations); | |
c1a9b12d SL |
1359 | |
1360 | // Evaluate those obligations to see if they might possibly hold. | |
ea8adc8c | 1361 | for o in candidate_obligations.into_iter().chain(sub_obligations) { |
dc9dc135 | 1362 | let o = self.resolve_vars_if_possible(&o); |
83c7162d | 1363 | if !self.predicate_may_hold(&o) { |
ea8adc8c | 1364 | result = ProbeResult::NoMatch; |
c1a9b12d | 1365 | if let &ty::Predicate::Trait(ref pred) = &o.predicate { |
83c7162d | 1366 | possibly_unsatisfied_predicates.push(pred.skip_binder().trait_ref); |
c1a9b12d | 1367 | } |
1a4d82fc JJ |
1368 | } |
1369 | } | |
ea8adc8c XL |
1370 | |
1371 | if let ProbeResult::Match = result { | |
1372 | if let (Some(return_ty), Some(xform_ret_ty)) = | |
1373 | (self.return_type, probe.xform_ret_ty) | |
1374 | { | |
dc9dc135 | 1375 | let xform_ret_ty = self.resolve_vars_if_possible(&xform_ret_ty); |
ea8adc8c XL |
1376 | debug!("comparing return_ty {:?} with xform ret ty {:?}", |
1377 | return_ty, | |
1378 | probe.xform_ret_ty); | |
1379 | if self.at(&ObligationCause::dummy(), self.param_env) | |
1380 | .sup(return_ty, xform_ret_ty) | |
1381 | .is_err() | |
1382 | { | |
1383 | return ProbeResult::BadReturnType; | |
1384 | } | |
1385 | } | |
1386 | } | |
1387 | ||
1388 | result | |
1a4d82fc JJ |
1389 | }) |
1390 | } | |
1391 | ||
1392 | /// Sometimes we get in a situation where we have multiple probes that are all impls of the | |
1393 | /// same trait, but we don't know which impl to use. In this case, since in all cases the | |
1394 | /// external interface of the method can be determined from the trait, it's ok not to decide. | |
1395 | /// We can basically just collapse all of the probes for various impls into one where-clause | |
1396 | /// probe. This will result in a pending obligation so when more type-info is available we can | |
1397 | /// make the final decision. | |
1398 | /// | |
416331ca | 1399 | /// Example (`src/test/ui/method-two-trait-defer-resolution-1.rs`): |
1a4d82fc JJ |
1400 | /// |
1401 | /// ``` | |
1402 | /// trait Foo { ... } | |
1403 | /// impl Foo for Vec<int> { ... } | |
c34b1796 | 1404 | /// impl Foo for Vec<usize> { ... } |
1a4d82fc JJ |
1405 | /// ``` |
1406 | /// | |
1407 | /// Now imagine the receiver is `Vec<_>`. It doesn't really matter at this time which impl we | |
1408 | /// use, so it's ok to just commit to "using the method from the trait Foo". | |
ea8adc8c XL |
1409 | fn collapse_candidates_to_trait_pick(&self, probes: &[(&Candidate<'tcx>, ProbeResult)]) |
1410 | -> Option<Pick<'tcx>> | |
1411 | { | |
1a4d82fc | 1412 | // Do all probes correspond to the same trait? |
ea8adc8c | 1413 | let container = probes[0].0.item.container; |
0bf4aa26 XL |
1414 | if let ty::ImplContainer(_) = container { |
1415 | return None | |
c1a9b12d | 1416 | } |
ea8adc8c | 1417 | if probes[1..].iter().any(|&(p, _)| p.item.container != container) { |
1a4d82fc JJ |
1418 | return None; |
1419 | } | |
1420 | ||
ea8adc8c | 1421 | // FIXME: check the return type here somehow. |
1a4d82fc | 1422 | // If so, just use this trait and call it a day. |
1a4d82fc | 1423 | Some(Pick { |
ea8adc8c | 1424 | item: probes[0].0.item.clone(), |
c1a9b12d | 1425 | kind: TraitPick, |
48663c56 | 1426 | import_ids: probes[0].0.import_ids.clone(), |
9346a6ac AL |
1427 | autoderefs: 0, |
1428 | autoref: None, | |
c30ab7b3 | 1429 | unsize: None, |
1a4d82fc JJ |
1430 | }) |
1431 | } | |
1432 | ||
ea8adc8c XL |
1433 | /// Similarly to `probe_for_return_type`, this method attempts to find the best matching |
1434 | /// candidate method where the method name may have been misspelt. Similarly to other | |
1435 | /// Levenshtein based suggestions, we provide at most one such suggestion. | |
dc9dc135 | 1436 | fn probe_for_lev_candidate(&mut self) -> Result<Option<ty::AssocItem>, MethodError<'tcx>> { |
416331ca | 1437 | debug!("probing for method names similar to {:?}", |
ea8adc8c XL |
1438 | self.method_name); |
1439 | ||
1440 | let steps = self.steps.clone(); | |
1441 | self.probe(|_| { | |
1442 | let mut pcx = ProbeContext::new(self.fcx, self.span, self.mode, self.method_name, | |
0731742a XL |
1443 | self.return_type, |
1444 | self.orig_steps_var_values.clone(), | |
1445 | steps, IsSuggestion(true)); | |
ea8adc8c XL |
1446 | pcx.allow_similar_names = true; |
1447 | pcx.assemble_inherent_candidates(); | |
532ac7d7 | 1448 | pcx.assemble_extension_candidates_for_traits_in_scope(hir::DUMMY_HIR_ID)?; |
ea8adc8c XL |
1449 | |
1450 | let method_names = pcx.candidate_method_names(); | |
1451 | pcx.allow_similar_names = false; | |
dc9dc135 | 1452 | let applicable_close_candidates: Vec<ty::AssocItem> = method_names |
ea8adc8c XL |
1453 | .iter() |
1454 | .filter_map(|&method_name| { | |
1455 | pcx.reset(); | |
1456 | pcx.method_name = Some(method_name); | |
1457 | pcx.assemble_inherent_candidates(); | |
532ac7d7 | 1458 | pcx.assemble_extension_candidates_for_traits_in_scope(hir::DUMMY_HIR_ID) |
60c5eb7d | 1459 | .map_or(None, |_| { |
ea8adc8c XL |
1460 | pcx.pick_core() |
1461 | .and_then(|pick| pick.ok()) | |
1462 | .and_then(|pick| Some(pick.item)) | |
1463 | }) | |
1464 | }) | |
1465 | .collect(); | |
1466 | ||
1467 | if applicable_close_candidates.is_empty() { | |
1468 | Ok(None) | |
1469 | } else { | |
1470 | let best_name = { | |
8faf50e0 | 1471 | let names = applicable_close_candidates.iter().map(|cand| &cand.ident.name); |
ea8adc8c XL |
1472 | find_best_match_for_name(names, |
1473 | &self.method_name.unwrap().as_str(), | |
1474 | None) | |
1475 | }.unwrap(); | |
1476 | Ok(applicable_close_candidates | |
1477 | .into_iter() | |
8faf50e0 | 1478 | .find(|method| method.ident.name == best_name)) |
ea8adc8c XL |
1479 | } |
1480 | }) | |
1481 | } | |
1482 | ||
1a4d82fc JJ |
1483 | /////////////////////////////////////////////////////////////////////////// |
1484 | // MISCELLANY | |
dc9dc135 | 1485 | fn has_applicable_self(&self, item: &ty::AssocItem) -> bool { |
476ff2be SL |
1486 | // "Fast track" -- check for usage of sugar when in method call |
1487 | // mode. | |
1488 | // | |
1489 | // In Path mode (i.e., resolving a value like `T::next`), consider any | |
1490 | // associated value (i.e., methods, constants) but not types. | |
1491 | match self.mode { | |
1492 | Mode::MethodCall => item.method_has_self_argument, | |
1493 | Mode::Path => match item.kind { | |
416331ca | 1494 | ty::AssocKind::OpaqueTy | |
dc9dc135 XL |
1495 | ty::AssocKind::Type => false, |
1496 | ty::AssocKind::Method | ty::AssocKind::Const => true | |
476ff2be | 1497 | }, |
1a4d82fc | 1498 | } |
1a4d82fc JJ |
1499 | // FIXME -- check for types that deref to `Self`, |
1500 | // like `Rc<Self>` and so on. | |
1501 | // | |
1502 | // Note also that the current code will break if this type | |
1503 | // includes any of the type parameters defined on the method | |
1504 | // -- but this could be overcome. | |
1a4d82fc JJ |
1505 | } |
1506 | ||
1507 | fn record_static_candidate(&mut self, source: CandidateSource) { | |
1508 | self.static_candidates.push(source); | |
1509 | } | |
1510 | ||
1511 | fn xform_self_ty(&self, | |
dc9dc135 | 1512 | item: &ty::AssocItem, |
c34b1796 | 1513 | impl_ty: Ty<'tcx>, |
532ac7d7 | 1514 | substs: SubstsRef<'tcx>) |
ea8adc8c | 1515 | -> (Ty<'tcx>, Option<Ty<'tcx>>) { |
dc9dc135 | 1516 | if item.kind == ty::AssocKind::Method && self.mode == Mode::MethodCall { |
ea8adc8c XL |
1517 | let sig = self.xform_method_sig(item.def_id, substs); |
1518 | (sig.inputs()[0], Some(sig.output())) | |
476ff2be | 1519 | } else { |
ea8adc8c | 1520 | (impl_ty, None) |
d9579d0f AL |
1521 | } |
1522 | } | |
1523 | ||
ea8adc8c XL |
1524 | fn xform_method_sig(&self, |
1525 | method: DefId, | |
532ac7d7 | 1526 | substs: SubstsRef<'tcx>) |
ea8adc8c XL |
1527 | -> ty::FnSig<'tcx> |
1528 | { | |
1529 | let fn_sig = self.tcx.fn_sig(method); | |
1530 | debug!("xform_self_ty(fn_sig={:?}, substs={:?})", | |
1531 | fn_sig, | |
62682a34 | 1532 | substs); |
1a4d82fc | 1533 | |
a1dfa0c6 | 1534 | assert!(!substs.has_escaping_bound_vars()); |
1a4d82fc JJ |
1535 | |
1536 | // It is possible for type parameters or early-bound lifetimes | |
1537 | // to appear in the signature of `self`. The substitutions we | |
1538 | // are given do not include type/lifetime parameters for the | |
1539 | // method yet. So create fresh variables here for those too, | |
1540 | // if there are any. | |
7cac9316 | 1541 | let generics = self.tcx.generics_of(method); |
94b46f34 | 1542 | assert_eq!(substs.len(), generics.parent_count as usize); |
c34b1796 | 1543 | |
1a4d82fc JJ |
1544 | // Erase any late-bound regions from the method and substitute |
1545 | // in the values from the substitution. | |
ea8adc8c | 1546 | let xform_fn_sig = self.erase_late_bound_regions(&fn_sig); |
1a4d82fc | 1547 | |
94b46f34 | 1548 | if generics.params.is_empty() { |
ea8adc8c | 1549 | xform_fn_sig.subst(self.tcx, substs) |
9e0c209e | 1550 | } else { |
532ac7d7 | 1551 | let substs = InternalSubsts::for_item(self.tcx, method, |param, _| { |
94b46f34 | 1552 | let i = param.index as usize; |
8bb4bdeb | 1553 | if i < substs.len() { |
94b46f34 | 1554 | substs[i] |
9e0c209e | 1555 | } else { |
94b46f34 XL |
1556 | match param.kind { |
1557 | GenericParamDefKind::Lifetime => { | |
1558 | // In general, during probe we erase regions. See | |
1559 | // `impl_self_ty()` for an explanation. | |
48663c56 | 1560 | self.tcx.lifetimes.re_erased.into() |
94b46f34 | 1561 | } |
532ac7d7 XL |
1562 | GenericParamDefKind::Type { .. } |
1563 | | GenericParamDefKind::Const => { | |
1564 | self.var_for_def(self.span, param) | |
1565 | } | |
94b46f34 | 1566 | } |
9e0c209e SL |
1567 | } |
1568 | }); | |
ea8adc8c | 1569 | xform_fn_sig.subst(self.tcx, substs) |
9e0c209e | 1570 | } |
1a4d82fc JJ |
1571 | } |
1572 | ||
9fa01778 | 1573 | /// Gets the type of an impl and generate substitutions with placeholders. |
532ac7d7 | 1574 | fn impl_ty_and_substs(&self, impl_def_id: DefId) -> (Ty<'tcx>, SubstsRef<'tcx>) { |
ea8adc8c XL |
1575 | (self.tcx.type_of(impl_def_id), self.fresh_item_substs(impl_def_id)) |
1576 | } | |
1a4d82fc | 1577 | |
532ac7d7 XL |
1578 | fn fresh_item_substs(&self, def_id: DefId) -> SubstsRef<'tcx> { |
1579 | InternalSubsts::for_item(self.tcx, def_id, |param, _| { | |
94b46f34 | 1580 | match param.kind { |
48663c56 | 1581 | GenericParamDefKind::Lifetime => self.tcx.lifetimes.re_erased.into(), |
532ac7d7 | 1582 | GenericParamDefKind::Type { .. } => { |
dc9dc135 XL |
1583 | self.next_ty_var(TypeVariableOrigin { |
1584 | kind: TypeVariableOriginKind::SubstitutionPlaceholder, | |
1585 | span: self.tcx.def_span(def_id), | |
1586 | }).into() | |
94b46f34 | 1587 | } |
532ac7d7 | 1588 | GenericParamDefKind::Const { .. } => { |
48663c56 | 1589 | let span = self.tcx.def_span(def_id); |
dc9dc135 XL |
1590 | let origin = ConstVariableOrigin { |
1591 | kind: ConstVariableOriginKind::SubstitutionPlaceholder, | |
1592 | span, | |
1593 | }; | |
48663c56 | 1594 | self.next_const_var(self.tcx.type_of(param.def_id), origin).into() |
532ac7d7 | 1595 | } |
94b46f34 XL |
1596 | } |
1597 | }) | |
1a4d82fc JJ |
1598 | } |
1599 | ||
9fa01778 | 1600 | /// Replaces late-bound-regions bound by `value` with `'static` using |
1a4d82fc JJ |
1601 | /// `ty::erase_late_bound_regions`. |
1602 | /// | |
1603 | /// This is only a reasonable thing to do during the *probe* phase, not the *confirm* phase, of | |
1604 | /// method matching. It is reasonable during the probe phase because we don't consider region | |
1605 | /// relationships at all. Therefore, we can just replace all the region variables with 'static | |
1606 | /// rather than creating fresh region variables. This is nice for two reasons: | |
1607 | /// | |
1608 | /// 1. Because the numbers of the region variables would otherwise be fairly unique to this | |
1609 | /// particular method call, it winds up creating fewer types overall, which helps for memory | |
a1dfa0c6 | 1610 | /// usage. (Admittedly, this is a rather small effect, though measurable.) |
1a4d82fc JJ |
1611 | /// |
1612 | /// 2. It makes it easier to deal with higher-ranked trait bounds, because we can replace any | |
1613 | /// late-bound regions with 'static. Otherwise, if we were going to replace late-bound | |
1614 | /// regions with actual region variables as is proper, we'd have to ensure that the same | |
1615 | /// region got replaced with the same variable, which requires a bit more coordination | |
1616 | /// and/or tracking the substitution and | |
1617 | /// so forth. | |
1618 | fn erase_late_bound_regions<T>(&self, value: &ty::Binder<T>) -> T | |
c30ab7b3 | 1619 | where T: TypeFoldable<'tcx> |
1a4d82fc | 1620 | { |
a7813a04 | 1621 | self.tcx.erase_late_bound_regions(value) |
1a4d82fc | 1622 | } |
1a4d82fc | 1623 | |
9fa01778 | 1624 | /// Finds the method with the appropriate name (or return type, as the case may be). If |
ea8adc8c | 1625 | /// `allow_similar_names` is set, find methods with close-matching names. |
dc9dc135 | 1626 | fn impl_or_trait_item(&self, def_id: DefId) -> Vec<ty::AssocItem> { |
ea8adc8c XL |
1627 | if let Some(name) = self.method_name { |
1628 | if self.allow_similar_names { | |
1629 | let max_dist = max(name.as_str().len(), 3) / 3; | |
1630 | self.tcx.associated_items(def_id) | |
1631 | .filter(|x| { | |
8faf50e0 | 1632 | let dist = lev_distance(&*name.as_str(), &x.ident.as_str()); |
abe05a73 | 1633 | Namespace::from(x.kind) == Namespace::Value && dist > 0 |
0bf4aa26 | 1634 | && dist <= max_dist |
ea8adc8c | 1635 | }) |
32a655c1 | 1636 | .collect() |
ea8adc8c | 1637 | } else { |
abe05a73 XL |
1638 | self.fcx |
1639 | .associated_item(def_id, name, Namespace::Value) | |
1640 | .map_or(Vec::new(), |x| vec![x]) | |
32a655c1 | 1641 | } |
ea8adc8c XL |
1642 | } else { |
1643 | self.tcx.associated_items(def_id).collect() | |
32a655c1 | 1644 | } |
a7813a04 | 1645 | } |
1a4d82fc JJ |
1646 | } |
1647 | ||
1648 | impl<'tcx> Candidate<'tcx> { | |
1649 | fn to_unadjusted_pick(&self) -> Pick<'tcx> { | |
1650 | Pick { | |
d9579d0f | 1651 | item: self.item.clone(), |
1a4d82fc | 1652 | kind: match self.kind { |
9e0c209e | 1653 | InherentImplCandidate(..) => InherentImplPick, |
c1a9b12d | 1654 | ObjectCandidate => ObjectPick, |
ea8adc8c | 1655 | TraitCandidate(_) => TraitPick, |
c1a9b12d | 1656 | WhereClauseCandidate(ref trait_ref) => { |
1a4d82fc JJ |
1657 | // Only trait derived from where-clauses should |
1658 | // appear here, so they should not contain any | |
1659 | // inference variables or other artifacts. This | |
1660 | // means they are safe to put into the | |
1661 | // `WhereClausePick`. | |
83c7162d XL |
1662 | assert!( |
1663 | !trait_ref.skip_binder().substs.needs_infer() | |
a1dfa0c6 | 1664 | && !trait_ref.skip_binder().substs.has_placeholders() |
83c7162d | 1665 | ); |
1a4d82fc | 1666 | |
c1a9b12d | 1667 | WhereClausePick(trait_ref.clone()) |
1a4d82fc | 1668 | } |
9346a6ac | 1669 | }, |
48663c56 | 1670 | import_ids: self.import_ids.clone(), |
9346a6ac AL |
1671 | autoderefs: 0, |
1672 | autoref: None, | |
c30ab7b3 | 1673 | unsize: None, |
1a4d82fc JJ |
1674 | } |
1675 | } | |
1a4d82fc | 1676 | } |