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