1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use super::MethodError
;
12 use super::NoMatchData
;
13 use super::{CandidateSource, ImplSource, TraitSource}
;
17 use hir
::def_id
::DefId
;
19 use namespace
::Namespace
;
20 use rustc
::ty
::subst
::{Subst, Substs}
;
21 use rustc
::traits
::{self, ObligationCause}
;
22 use rustc
::ty
::{self, Ty, ToPolyTraitRef, ToPredicate, TraitRef, TypeFoldable}
;
23 use rustc
::infer
::type_variable
::TypeVariableOrigin
;
24 use rustc
::util
::nodemap
::FxHashSet
;
25 use rustc
::infer
::{self, InferOk}
;
27 use syntax
::util
::lev_distance
::{lev_distance, find_best_match_for_name}
;
35 use self::CandidateKind
::*;
36 pub use self::PickKind
::*;
38 /// Boolean flag used to indicate if this search is for a suggestion
39 /// or not. If true, we can allow ambiguity and so forth.
40 pub struct IsSuggestion(pub bool
);
42 struct ProbeContext
<'a
, 'gcx
: 'a
+ 'tcx
, 'tcx
: 'a
> {
43 fcx
: &'a FnCtxt
<'a
, 'gcx
, 'tcx
>,
46 method_name
: Option
<ast
::Name
>,
47 return_type
: Option
<Ty
<'tcx
>>,
48 steps
: Rc
<Vec
<CandidateStep
<'tcx
>>>,
49 inherent_candidates
: Vec
<Candidate
<'tcx
>>,
50 extension_candidates
: Vec
<Candidate
<'tcx
>>,
51 impl_dups
: FxHashSet
<DefId
>,
53 /// Collects near misses when the candidate functions are missing a `self` keyword and is only
54 /// used for error reporting
55 static_candidates
: Vec
<CandidateSource
>,
57 /// When probing for names, include names that are close to the
58 /// requested name (by Levensthein distance)
59 allow_similar_names
: bool
,
61 /// Some(candidate) if there is a private candidate
62 private_candidate
: Option
<Def
>,
64 /// Collects near misses when trait bounds for type parameters are unsatisfied and is only used
65 /// for error reporting
66 unsatisfied_predicates
: Vec
<TraitRef
<'tcx
>>,
69 impl<'a
, 'gcx
, 'tcx
> Deref
for ProbeContext
<'a
, 'gcx
, 'tcx
> {
70 type Target
= FnCtxt
<'a
, 'gcx
, 'tcx
>;
71 fn deref(&self) -> &Self::Target
{
77 struct CandidateStep
<'tcx
> {
84 struct Candidate
<'tcx
> {
85 xform_self_ty
: Ty
<'tcx
>,
86 xform_ret_ty
: Option
<Ty
<'tcx
>>,
87 item
: ty
::AssociatedItem
,
88 kind
: CandidateKind
<'tcx
>,
89 import_id
: Option
<ast
::NodeId
>,
93 enum CandidateKind
<'tcx
> {
94 InherentImplCandidate(&'tcx Substs
<'tcx
>,
95 // Normalize obligations
96 Vec
<traits
::PredicateObligation
<'tcx
>>),
98 TraitCandidate(ty
::TraitRef
<'tcx
>),
99 WhereClauseCandidate(// Trait
100 ty
::PolyTraitRef
<'tcx
>),
103 #[derive(Debug, PartialEq, Eq, Copy, Clone)]
110 #[derive(Debug, PartialEq, Eq, Clone)]
111 pub struct Pick
<'tcx
> {
112 pub item
: ty
::AssociatedItem
,
113 pub kind
: PickKind
<'tcx
>,
114 pub import_id
: Option
<ast
::NodeId
>,
116 // Indicates that the source expression should be autoderef'd N times
118 // A = expr | *expr | **expr | ...
119 pub autoderefs
: usize,
121 // Indicates that an autoref is applied after the optional autoderefs
123 // B = A | &A | &mut A
124 pub autoref
: Option
<hir
::Mutability
>,
126 // Indicates that the source expression should be "unsized" to a
127 // target type. This should probably eventually go away in favor
128 // of just coercing method receivers.
131 pub unsize
: Option
<Ty
<'tcx
>>,
134 #[derive(Clone, Debug, PartialEq, Eq)]
135 pub enum PickKind
<'tcx
> {
139 WhereClausePick(// Trait
140 ty
::PolyTraitRef
<'tcx
>),
143 pub type PickResult
<'tcx
> = Result
<Pick
<'tcx
>, MethodError
<'tcx
>>;
145 #[derive(PartialEq, Eq, Copy, Clone, Debug)]
147 // An expression of the form `receiver.method_name(...)`.
148 // Autoderefs are performed on `receiver`, lookup is done based on the
149 // `self` argument of the method, and static methods aren't considered.
151 // An expression of the form `Type::item` or `<T>::item`.
152 // No autoderefs are performed, lookup is done based on the type each
153 // implementation is for, and static methods are included.
157 #[derive(PartialEq, Eq, Copy, Clone, Debug)]
158 pub enum ProbeScope
{
159 // Assemble candidates coming only from traits in scope.
162 // Assemble candidates coming from all traits.
166 impl<'a
, 'gcx
, 'tcx
> FnCtxt
<'a
, 'gcx
, 'tcx
> {
167 /// This is used to offer suggestions to users. It returns methods
168 /// that could have been called which have the desired return
169 /// type. Some effort is made to rule out methods that, if called,
170 /// would result in an error (basically, the same criteria we
171 /// would use to decide if a method is a plausible fit for
172 /// ambiguity purposes).
173 pub fn probe_for_return_type(&self,
176 return_type
: Ty
<'tcx
>,
178 scope_expr_id
: ast
::NodeId
)
179 -> Vec
<ty
::AssociatedItem
> {
180 debug
!("probe(self_ty={:?}, return_type={}, scope_expr_id={})",
185 self.probe_op(span
, mode
, None
, Some(return_type
), IsSuggestion(true),
186 self_ty
, scope_expr_id
, ProbeScope
::TraitsInScope
,
187 |probe_cx
| Ok(probe_cx
.candidate_method_names()))
191 .flat_map(|&method_name
| {
193 span
, mode
, Some(method_name
), Some(return_type
),
194 IsSuggestion(true), self_ty
, scope_expr_id
,
195 ProbeScope
::TraitsInScope
, |probe_cx
| probe_cx
.pick()
196 ).ok().map(|pick
| pick
.item
)
201 pub fn probe_for_name(&self,
204 item_name
: ast
::Name
,
205 is_suggestion
: IsSuggestion
,
207 scope_expr_id
: ast
::NodeId
,
209 -> PickResult
<'tcx
> {
210 debug
!("probe(self_ty={:?}, item_name={}, scope_expr_id={})",
222 |probe_cx
| probe_cx
.pick())
225 fn probe_op
<OP
,R
>(&'a
self,
228 method_name
: Option
<ast
::Name
>,
229 return_type
: Option
<Ty
<'tcx
>>,
230 is_suggestion
: IsSuggestion
,
232 scope_expr_id
: ast
::NodeId
,
235 -> Result
<R
, MethodError
<'tcx
>>
236 where OP
: FnOnce(ProbeContext
<'a
, 'gcx
, 'tcx
>) -> Result
<R
, MethodError
<'tcx
>>
238 // FIXME(#18741) -- right now, creating the steps involves evaluating the
239 // `*` operator, which registers obligations that then escape into
240 // the global fulfillment context and thus has global
241 // side-effects. This is a bit of a pain to refactor. So just let
242 // it ride, although it's really not great, and in fact could I
243 // think cause spurious errors. Really though this part should
244 // take place in the `self.probe` below.
245 let steps
= if mode
== Mode
::MethodCall
{
246 match self.create_steps(span
, self_ty
, is_suggestion
) {
247 Some(steps
) => steps
,
249 return Err(MethodError
::NoMatch(NoMatchData
::new(Vec
::new(),
264 debug
!("ProbeContext: steps for self_ty={:?} are {:?}",
268 // this creates one big transaction so that all type variables etc
269 // that we create during the probe process are removed later
272 ProbeContext
::new(self, span
, mode
, method_name
, return_type
, Rc
::new(steps
));
274 probe_cx
.assemble_inherent_candidates();
276 ProbeScope
::TraitsInScope
=>
277 probe_cx
.assemble_extension_candidates_for_traits_in_scope(scope_expr_id
)?
,
278 ProbeScope
::AllTraits
=>
279 probe_cx
.assemble_extension_candidates_for_all_traits()?
,
285 fn create_steps(&self,
288 is_suggestion
: IsSuggestion
)
289 -> Option
<Vec
<CandidateStep
<'tcx
>>> {
290 // FIXME: we don't need to create the entire steps in one pass
292 let mut autoderef
= self.autoderef(span
, self_ty
);
293 let mut steps
: Vec
<_
> = autoderef
.by_ref()
303 let final_ty
= autoderef
.maybe_ambiguous_final_ty();
305 ty
::TyInfer(ty
::TyVar(_
)) => {
306 // Ended in an inference variable. If we are doing
307 // a real method lookup, this is a hard error (it's an
308 // ambiguity and we can't make progress).
309 if !is_suggestion
.0 {
310 let t
= self.structurally_resolved_type(span
, final_ty
);
311 assert_eq
!(t
, self.tcx
.types
.err
);
314 // If we're just looking for suggestions,
315 // though, ambiguity is no big thing, we can
319 ty
::TyArray(elem_ty
, _
) => {
320 let dereferences
= steps
.len() - 1;
322 steps
.push(CandidateStep
{
323 self_ty
: self.tcx
.mk_slice(elem_ty
),
324 autoderefs
: dereferences
,
328 ty
::TyError
=> return None
,
332 debug
!("create_steps: steps={:?}", steps
);
338 impl<'a
, 'gcx
, 'tcx
> ProbeContext
<'a
, 'gcx
, 'tcx
> {
339 fn new(fcx
: &'a FnCtxt
<'a
, 'gcx
, 'tcx
>,
342 method_name
: Option
<ast
::Name
>,
343 return_type
: Option
<Ty
<'tcx
>>,
344 steps
: Rc
<Vec
<CandidateStep
<'tcx
>>>)
345 -> ProbeContext
<'a
, 'gcx
, 'tcx
> {
352 inherent_candidates
: Vec
::new(),
353 extension_candidates
: Vec
::new(),
354 impl_dups
: FxHashSet(),
356 static_candidates
: Vec
::new(),
357 allow_similar_names
: false,
358 private_candidate
: None
,
359 unsatisfied_predicates
: Vec
::new(),
363 fn reset(&mut self) {
364 self.inherent_candidates
.clear();
365 self.extension_candidates
.clear();
366 self.impl_dups
.clear();
367 self.static_candidates
.clear();
368 self.private_candidate
= None
;
371 ///////////////////////////////////////////////////////////////////////////
372 // CANDIDATE ASSEMBLY
374 fn push_candidate(&mut self,
375 candidate
: Candidate
<'tcx
>,
378 let is_accessible
= if let Some(name
) = self.method_name
{
379 let item
= candidate
.item
;
380 let def_scope
= self.tcx
.adjust(name
, item
.container
.id(), self.body_id
).1;
381 item
.vis
.is_accessible_from(def_scope
, self.tcx
)
387 self.inherent_candidates
.push(candidate
);
389 self.extension_candidates
.push(candidate
);
391 } else if self.private_candidate
.is_none() {
392 self.private_candidate
= Some(candidate
.item
.def());
396 fn assemble_inherent_candidates(&mut self) {
397 let steps
= self.steps
.clone();
398 for step
in steps
.iter() {
399 self.assemble_probe(step
.self_ty
);
403 fn assemble_probe(&mut self, self_ty
: Ty
<'tcx
>) {
404 debug
!("assemble_probe: self_ty={:?}", self_ty
);
405 let lang_items
= self.tcx
.lang_items();
408 ty
::TyDynamic(ref data
, ..) => {
409 if let Some(p
) = data
.principal() {
410 self.assemble_inherent_candidates_from_object(self_ty
, p
);
411 self.assemble_inherent_impl_candidates_for_type(p
.def_id());
414 ty
::TyAdt(def
, _
) => {
415 self.assemble_inherent_impl_candidates_for_type(def
.did
);
417 ty
::TyForeign(did
) => {
418 self.assemble_inherent_impl_candidates_for_type(did
);
421 self.assemble_inherent_candidates_from_param(self_ty
, p
);
424 let lang_def_id
= lang_items
.char_impl();
425 self.assemble_inherent_impl_for_primitive(lang_def_id
);
428 let lang_def_id
= lang_items
.str_impl();
429 self.assemble_inherent_impl_for_primitive(lang_def_id
);
432 let lang_def_id
= lang_items
.slice_impl();
433 self.assemble_inherent_impl_for_primitive(lang_def_id
);
435 let lang_def_id
= lang_items
.slice_u8_impl();
436 self.assemble_inherent_impl_for_primitive(lang_def_id
);
438 ty
::TyRawPtr(ty
::TypeAndMut { ty: _, mutbl: hir::MutImmutable }
) => {
439 let lang_def_id
= lang_items
.const_ptr_impl();
440 self.assemble_inherent_impl_for_primitive(lang_def_id
);
442 ty
::TyRawPtr(ty
::TypeAndMut { ty: _, mutbl: hir::MutMutable }
) => {
443 let lang_def_id
= lang_items
.mut_ptr_impl();
444 self.assemble_inherent_impl_for_primitive(lang_def_id
);
446 ty
::TyInt(ast
::IntTy
::I8
) => {
447 let lang_def_id
= lang_items
.i8_impl();
448 self.assemble_inherent_impl_for_primitive(lang_def_id
);
450 ty
::TyInt(ast
::IntTy
::I16
) => {
451 let lang_def_id
= lang_items
.i16_impl();
452 self.assemble_inherent_impl_for_primitive(lang_def_id
);
454 ty
::TyInt(ast
::IntTy
::I32
) => {
455 let lang_def_id
= lang_items
.i32_impl();
456 self.assemble_inherent_impl_for_primitive(lang_def_id
);
458 ty
::TyInt(ast
::IntTy
::I64
) => {
459 let lang_def_id
= lang_items
.i64_impl();
460 self.assemble_inherent_impl_for_primitive(lang_def_id
);
462 ty
::TyInt(ast
::IntTy
::I128
) => {
463 let lang_def_id
= lang_items
.i128_impl();
464 self.assemble_inherent_impl_for_primitive(lang_def_id
);
466 ty
::TyInt(ast
::IntTy
::Is
) => {
467 let lang_def_id
= lang_items
.isize_impl();
468 self.assemble_inherent_impl_for_primitive(lang_def_id
);
470 ty
::TyUint(ast
::UintTy
::U8
) => {
471 let lang_def_id
= lang_items
.u8_impl();
472 self.assemble_inherent_impl_for_primitive(lang_def_id
);
474 ty
::TyUint(ast
::UintTy
::U16
) => {
475 let lang_def_id
= lang_items
.u16_impl();
476 self.assemble_inherent_impl_for_primitive(lang_def_id
);
478 ty
::TyUint(ast
::UintTy
::U32
) => {
479 let lang_def_id
= lang_items
.u32_impl();
480 self.assemble_inherent_impl_for_primitive(lang_def_id
);
482 ty
::TyUint(ast
::UintTy
::U64
) => {
483 let lang_def_id
= lang_items
.u64_impl();
484 self.assemble_inherent_impl_for_primitive(lang_def_id
);
486 ty
::TyUint(ast
::UintTy
::U128
) => {
487 let lang_def_id
= lang_items
.u128_impl();
488 self.assemble_inherent_impl_for_primitive(lang_def_id
);
490 ty
::TyUint(ast
::UintTy
::Us
) => {
491 let lang_def_id
= lang_items
.usize_impl();
492 self.assemble_inherent_impl_for_primitive(lang_def_id
);
494 ty
::TyFloat(ast
::FloatTy
::F32
) => {
495 let lang_def_id
= lang_items
.f32_impl();
496 self.assemble_inherent_impl_for_primitive(lang_def_id
);
498 ty
::TyFloat(ast
::FloatTy
::F64
) => {
499 let lang_def_id
= lang_items
.f64_impl();
500 self.assemble_inherent_impl_for_primitive(lang_def_id
);
506 fn assemble_inherent_impl_for_primitive(&mut self, lang_def_id
: Option
<DefId
>) {
507 if let Some(impl_def_id
) = lang_def_id
{
508 self.assemble_inherent_impl_probe(impl_def_id
);
512 fn assemble_inherent_impl_candidates_for_type(&mut self, def_id
: DefId
) {
513 let impl_def_ids
= self.tcx
.at(self.span
).inherent_impls(def_id
);
514 for &impl_def_id
in impl_def_ids
.iter() {
515 self.assemble_inherent_impl_probe(impl_def_id
);
519 fn assemble_inherent_impl_probe(&mut self, impl_def_id
: DefId
) {
520 if !self.impl_dups
.insert(impl_def_id
) {
521 return; // already visited
524 debug
!("assemble_inherent_impl_probe {:?}", impl_def_id
);
526 for item
in self.impl_or_trait_item(impl_def_id
) {
527 if !self.has_applicable_self(&item
) {
528 // No receiver declared. Not a candidate.
529 self.record_static_candidate(ImplSource(impl_def_id
));
533 let (impl_ty
, impl_substs
) = self.impl_ty_and_substs(impl_def_id
);
534 let impl_ty
= impl_ty
.subst(self.tcx
, impl_substs
);
536 // Determine the receiver type that the method itself expects.
537 let xform_tys
= self.xform_self_ty(&item
, impl_ty
, impl_substs
);
539 // We can't use normalize_associated_types_in as it will pollute the
540 // fcx's fulfillment context after this probe is over.
541 let cause
= traits
::ObligationCause
::misc(self.span
, self.body_id
);
542 let selcx
= &mut traits
::SelectionContext
::new(self.fcx
);
543 let traits
::Normalized { value: (xform_self_ty, xform_ret_ty), obligations }
=
544 traits
::normalize(selcx
, self.param_env
, cause
, &xform_tys
);
545 debug
!("assemble_inherent_impl_probe: xform_self_ty = {:?}/{:?}",
546 xform_self_ty
, xform_ret_ty
);
548 self.push_candidate(Candidate
{
549 xform_self_ty
, xform_ret_ty
, item
,
550 kind
: InherentImplCandidate(impl_substs
, obligations
),
556 fn assemble_inherent_candidates_from_object(&mut self,
558 principal
: ty
::PolyExistentialTraitRef
<'tcx
>) {
559 debug
!("assemble_inherent_candidates_from_object(self_ty={:?})",
562 // It is illegal to invoke a method on a trait instance that
563 // refers to the `Self` type. An error will be reported by
564 // `enforce_object_limitations()` if the method refers to the
565 // `Self` type anywhere other than the receiver. Here, we use
566 // a substitution that replaces `Self` with the object type
567 // itself. Hence, a `&self` method will wind up with an
568 // argument type like `&Trait`.
569 let trait_ref
= principal
.with_self_ty(self.tcx
, self_ty
);
570 self.elaborate_bounds(&[trait_ref
], |this
, new_trait_ref
, item
| {
571 let new_trait_ref
= this
.erase_late_bound_regions(&new_trait_ref
);
573 let (xform_self_ty
, xform_ret_ty
) =
574 this
.xform_self_ty(&item
, new_trait_ref
.self_ty(), new_trait_ref
.substs
);
575 this
.push_candidate(Candidate
{
576 xform_self_ty
, xform_ret_ty
, item
,
577 kind
: ObjectCandidate
,
583 fn assemble_inherent_candidates_from_param(&mut self,
585 param_ty
: ty
::ParamTy
) {
586 // FIXME -- Do we want to commit to this behavior for param bounds?
588 let bounds
: Vec
<_
> = self.param_env
591 .filter_map(|predicate
| {
593 ty
::Predicate
::Trait(ref trait_predicate
) => {
594 match trait_predicate
.0.trait_ref
.self_ty().sty
{
595 ty
::TyParam(ref p
) if *p
== param_ty
=> {
596 Some(trait_predicate
.to_poly_trait_ref())
601 ty
::Predicate
::Equate(..) |
602 ty
::Predicate
::Subtype(..) |
603 ty
::Predicate
::Projection(..) |
604 ty
::Predicate
::RegionOutlives(..) |
605 ty
::Predicate
::WellFormed(..) |
606 ty
::Predicate
::ObjectSafe(..) |
607 ty
::Predicate
::ClosureKind(..) |
608 ty
::Predicate
::TypeOutlives(..) |
609 ty
::Predicate
::ConstEvaluatable(..) => None
,
614 self.elaborate_bounds(&bounds
, |this
, poly_trait_ref
, item
| {
615 let trait_ref
= this
.erase_late_bound_regions(&poly_trait_ref
);
617 let (xform_self_ty
, xform_ret_ty
) =
618 this
.xform_self_ty(&item
, trait_ref
.self_ty(), trait_ref
.substs
);
620 // Because this trait derives from a where-clause, it
621 // should not contain any inference variables or other
622 // artifacts. This means it is safe to put into the
623 // `WhereClauseCandidate` and (eventually) into the
624 // `WhereClausePick`.
625 assert
!(!trait_ref
.substs
.needs_infer());
627 this
.push_candidate(Candidate
{
628 xform_self_ty
, xform_ret_ty
, item
,
629 kind
: WhereClauseCandidate(poly_trait_ref
),
635 // Do a search through a list of bounds, using a callback to actually
636 // create the candidates.
637 fn elaborate_bounds
<F
>(&mut self, bounds
: &[ty
::PolyTraitRef
<'tcx
>], mut mk_cand
: F
)
638 where F
: for<'b
> FnMut(&mut ProbeContext
<'b
, 'gcx
, 'tcx
>,
639 ty
::PolyTraitRef
<'tcx
>,
642 debug
!("elaborate_bounds(bounds={:?})", bounds
);
645 for bound_trait_ref
in traits
::transitive_bounds(tcx
, bounds
) {
646 for item
in self.impl_or_trait_item(bound_trait_ref
.def_id()) {
647 if !self.has_applicable_self(&item
) {
648 self.record_static_candidate(TraitSource(bound_trait_ref
.def_id()));
650 mk_cand(self, bound_trait_ref
, item
);
656 fn assemble_extension_candidates_for_traits_in_scope(&mut self,
657 expr_id
: ast
::NodeId
)
658 -> Result
<(), MethodError
<'tcx
>> {
659 if expr_id
== ast
::DUMMY_NODE_ID
{
662 let mut duplicates
= FxHashSet();
663 let expr_hir_id
= self.tcx
.hir
.node_to_hir_id(expr_id
);
664 let opt_applicable_traits
= self.tcx
.in_scope_traits(expr_hir_id
);
665 if let Some(applicable_traits
) = opt_applicable_traits
{
666 for trait_candidate
in applicable_traits
.iter() {
667 let trait_did
= trait_candidate
.def_id
;
668 if duplicates
.insert(trait_did
) {
669 let import_id
= trait_candidate
.import_id
;
670 let result
= self.assemble_extension_candidates_for_trait(import_id
, trait_did
);
678 fn assemble_extension_candidates_for_all_traits(&mut self) -> Result
<(), MethodError
<'tcx
>> {
679 let mut duplicates
= FxHashSet();
680 for trait_info
in suggest
::all_traits(self.tcx
) {
681 if duplicates
.insert(trait_info
.def_id
) {
682 self.assemble_extension_candidates_for_trait(None
, trait_info
.def_id
)?
;
688 pub fn matches_return_type(&self,
689 method
: &ty
::AssociatedItem
,
690 self_ty
: Option
<Ty
<'tcx
>>,
691 expected
: Ty
<'tcx
>) -> bool
{
693 Def
::Method(def_id
) => {
694 let fty
= self.tcx
.fn_sig(def_id
);
696 let substs
= self.fresh_substs_for_item(self.span
, method
.def_id
);
697 let fty
= fty
.subst(self.tcx
, substs
);
698 let (fty
, _
) = self.replace_late_bound_regions_with_fresh_var(
699 self.span
, infer
::FnCall
, &fty
);
701 if let Some(self_ty
) = self_ty
{
702 if let Err(_
) = self.at(&ObligationCause
::dummy(), self.param_env
)
703 .sup(fty
.inputs()[0], self_ty
)
708 self.can_sub(self.param_env
, fty
.output(), expected
).is_ok()
715 fn assemble_extension_candidates_for_trait(&mut self,
716 import_id
: Option
<ast
::NodeId
>,
718 -> Result
<(), MethodError
<'tcx
>> {
719 debug
!("assemble_extension_candidates_for_trait(trait_def_id={:?})",
721 let trait_substs
= self.fresh_item_substs(trait_def_id
);
722 let trait_ref
= ty
::TraitRef
::new(trait_def_id
, trait_substs
);
724 for item
in self.impl_or_trait_item(trait_def_id
) {
725 // Check whether `trait_def_id` defines a method with suitable name:
726 if !self.has_applicable_self(&item
) {
727 debug
!("method has inapplicable self");
728 self.record_static_candidate(TraitSource(trait_def_id
));
732 let (xform_self_ty
, xform_ret_ty
) =
733 self.xform_self_ty(&item
, trait_ref
.self_ty(), trait_substs
);
734 self.push_candidate(Candidate
{
735 xform_self_ty
, xform_ret_ty
, item
, import_id
,
736 kind
: TraitCandidate(trait_ref
),
742 fn candidate_method_names(&self) -> Vec
<ast
::Name
> {
743 let mut set
= FxHashSet();
744 let mut names
: Vec
<_
> = self.inherent_candidates
746 .chain(&self.extension_candidates
)
747 .filter(|candidate
| {
748 if let Some(return_ty
) = self.return_type
{
749 self.matches_return_type(&candidate
.item
, None
, return_ty
)
754 .map(|candidate
| candidate
.item
.name
)
755 .filter(|&name
| set
.insert(name
))
758 // sort them by the name so we have a stable result
759 names
.sort_by_key(|n
| n
.as_str());
763 ///////////////////////////////////////////////////////////////////////////
766 fn pick(mut self) -> PickResult
<'tcx
> {
767 assert
!(self.method_name
.is_some());
769 if let Some(r
) = self.pick_core() {
773 let static_candidates
= mem
::replace(&mut self.static_candidates
, vec
![]);
774 let private_candidate
= mem
::replace(&mut self.private_candidate
, None
);
775 let unsatisfied_predicates
= mem
::replace(&mut self.unsatisfied_predicates
, vec
![]);
777 // things failed, so lets look at all traits, for diagnostic purposes now:
780 let span
= self.span
;
783 self.assemble_extension_candidates_for_all_traits()?
;
785 let out_of_scope_traits
= match self.pick_core() {
786 Some(Ok(p
)) => vec
![p
.item
.container
.id()],
787 //Some(Ok(p)) => p.iter().map(|p| p.item.container().id()).collect(),
788 Some(Err(MethodError
::Ambiguity(v
))) => {
792 TraitSource(id
) => id
,
793 ImplSource(impl_id
) => {
794 match tcx
.trait_id_of_impl(impl_id
) {
798 "found inherent method when looking at traits")
806 Some(Err(MethodError
::NoMatch(NoMatchData { out_of_scope_traits: others, .. }
))) => {
807 assert
!(others
.is_empty());
813 if let Some(def
) = private_candidate
{
814 return Err(MethodError
::PrivateMatch(def
, out_of_scope_traits
));
816 let lev_candidate
= self.probe_for_lev_candidate()?
;
818 Err(MethodError
::NoMatch(NoMatchData
::new(static_candidates
,
819 unsatisfied_predicates
,
825 fn pick_core(&mut self) -> Option
<PickResult
<'tcx
>> {
826 let steps
= self.steps
.clone();
828 // find the first step that works
832 debug
!("pick_core: step={:?}", step
);
833 !step
.self_ty
.references_error()
835 self.pick_by_value_method(step
).or_else(|| {
836 self.pick_autorefd_method(step
, hir
::MutImmutable
).or_else(|| {
837 self.pick_autorefd_method(step
, hir
::MutMutable
)
842 fn pick_by_value_method(&mut self, step
: &CandidateStep
<'tcx
>) -> Option
<PickResult
<'tcx
>> {
843 //! For each type `T` in the step list, this attempts to find a
844 //! method where the (transformed) self type is exactly `T`. We
845 //! do however do one transformation on the adjustment: if we
846 //! are passing a region pointer in, we will potentially
847 //! *reborrow* it to a shorter lifetime. This allows us to
848 //! transparently pass `&mut` pointers, in particular, without
849 //! consuming them for their entire lifetime.
855 self.pick_method(step
.self_ty
).map(|r
| {
857 pick
.autoderefs
= step
.autoderefs
;
859 // Insert a `&*` or `&mut *` if this is a reference type:
860 if let ty
::TyRef(_
, mt
) = step
.self_ty
.sty
{
861 pick
.autoderefs
+= 1;
862 pick
.autoref
= Some(mt
.mutbl
);
870 fn pick_autorefd_method(&mut self, step
: &CandidateStep
<'tcx
>, mutbl
: hir
::Mutability
)
871 -> Option
<PickResult
<'tcx
>> {
874 // In general, during probing we erase regions. See
875 // `impl_self_ty()` for an explanation.
876 let region
= tcx
.types
.re_erased
;
878 let autoref_ty
= tcx
.mk_ref(region
,
880 ty
: step
.self_ty
, mutbl
882 self.pick_method(autoref_ty
).map(|r
| {
884 pick
.autoderefs
= step
.autoderefs
;
885 pick
.autoref
= Some(mutbl
);
886 pick
.unsize
= if step
.unsize
{
896 fn pick_method(&mut self, self_ty
: Ty
<'tcx
>) -> Option
<PickResult
<'tcx
>> {
897 debug
!("pick_method(self_ty={})", self.ty_to_string(self_ty
));
899 let mut possibly_unsatisfied_predicates
= Vec
::new();
901 debug
!("searching inherent candidates");
902 if let Some(pick
) = self.consider_candidates(self_ty
,
903 &self.inherent_candidates
,
904 &mut possibly_unsatisfied_predicates
) {
908 debug
!("searching extension candidates");
909 let res
= self.consider_candidates(self_ty
,
910 &self.extension_candidates
,
911 &mut possibly_unsatisfied_predicates
);
913 self.unsatisfied_predicates
.extend(possibly_unsatisfied_predicates
);
918 fn consider_candidates(&self,
920 probes
: &[Candidate
<'tcx
>],
921 possibly_unsatisfied_predicates
: &mut Vec
<TraitRef
<'tcx
>>)
922 -> Option
<PickResult
<'tcx
>> {
923 let mut applicable_candidates
: Vec
<_
> = probes
.iter()
925 (probe
, self.consider_probe(self_ty
, probe
, possibly_unsatisfied_predicates
))
927 .filter(|&(_
, status
)| status
!= ProbeResult
::NoMatch
)
930 debug
!("applicable_candidates: {:?}", applicable_candidates
);
932 if applicable_candidates
.len() > 1 {
933 if let Some(pick
) = self.collapse_candidates_to_trait_pick(&applicable_candidates
[..]) {
934 return Some(Ok(pick
));
938 if applicable_candidates
.len() > 1 {
939 let sources
= probes
.iter()
940 .map(|p
| self.candidate_source(p
, self_ty
))
942 return Some(Err(MethodError
::Ambiguity(sources
)));
945 applicable_candidates
.pop().map(|(probe
, status
)| {
946 if status
== ProbeResult
::Match
{
947 Ok(probe
.to_unadjusted_pick())
949 Err(MethodError
::BadReturnType
)
954 fn select_trait_candidate(&self, trait_ref
: ty
::TraitRef
<'tcx
>)
955 -> traits
::SelectionResult
<'tcx
, traits
::Selection
<'tcx
>>
957 let cause
= traits
::ObligationCause
::misc(self.span
, self.body_id
);
959 trait_ref
.to_poly_trait_ref().to_poly_trait_predicate();
960 let obligation
= traits
::Obligation
::new(cause
, self.param_env
, predicate
);
961 traits
::SelectionContext
::new(self).select(&obligation
)
964 fn candidate_source(&self, candidate
: &Candidate
<'tcx
>, self_ty
: Ty
<'tcx
>)
967 match candidate
.kind
{
968 InherentImplCandidate(..) => ImplSource(candidate
.item
.container
.id()),
970 WhereClauseCandidate(_
) => TraitSource(candidate
.item
.container
.id()),
971 TraitCandidate(trait_ref
) => self.probe(|_
| {
972 let _
= self.at(&ObligationCause
::dummy(), self.param_env
)
973 .sup(candidate
.xform_self_ty
, self_ty
);
974 match self.select_trait_candidate(trait_ref
) {
975 Ok(Some(traits
::Vtable
::VtableImpl(ref impl_data
))) => {
976 // If only a single impl matches, make the error message point
978 ImplSource(impl_data
.impl_def_id
)
981 TraitSource(candidate
.item
.container
.id())
988 fn consider_probe(&self,
990 probe
: &Candidate
<'tcx
>,
991 possibly_unsatisfied_predicates
: &mut Vec
<TraitRef
<'tcx
>>)
993 debug
!("consider_probe: self_ty={:?} probe={:?}", self_ty
, probe
);
996 // First check that the self type can be related.
997 let sub_obligations
= match self.at(&ObligationCause
::dummy(), self.param_env
)
998 .sup(probe
.xform_self_ty
, self_ty
) {
999 Ok(InferOk { obligations, value: () }
) => obligations
,
1001 debug
!("--> cannot relate self-types");
1002 return ProbeResult
::NoMatch
;
1006 let mut result
= ProbeResult
::Match
;
1007 let selcx
= &mut traits
::SelectionContext
::new(self);
1008 let cause
= traits
::ObligationCause
::misc(self.span
, self.body_id
);
1010 // If so, impls may carry other conditions (e.g., where
1011 // clauses) that must be considered. Make sure that those
1012 // match as well (or at least may match, sometimes we
1013 // don't have enough information to fully evaluate).
1014 let candidate_obligations
: Vec
<_
> = match probe
.kind
{
1015 InherentImplCandidate(ref substs
, ref ref_obligations
) => {
1016 // Check whether the impl imposes obligations we have to worry about.
1017 let impl_def_id
= probe
.item
.container
.id();
1018 let impl_bounds
= self.tcx
.predicates_of(impl_def_id
);
1019 let impl_bounds
= impl_bounds
.instantiate(self.tcx
, substs
);
1020 let traits
::Normalized { value: impl_bounds, obligations: norm_obligations }
=
1021 traits
::normalize(selcx
, self.param_env
, cause
.clone(), &impl_bounds
);
1023 // Convert the bounds into obligations.
1024 let impl_obligations
= traits
::predicates_for_generics(
1025 cause
.clone(), self.param_env
, &impl_bounds
);
1027 debug
!("impl_obligations={:?}", impl_obligations
);
1028 impl_obligations
.into_iter()
1029 .chain(norm_obligations
.into_iter())
1030 .chain(ref_obligations
.iter().cloned())
1035 WhereClauseCandidate(..) => {
1036 // These have no additional conditions to check.
1040 TraitCandidate(trait_ref
) => {
1041 let predicate
= trait_ref
.to_predicate();
1043 traits
::Obligation
::new(cause
.clone(), self.param_env
, predicate
);
1044 if !selcx
.evaluate_obligation(&obligation
) {
1045 if self.probe(|_
| self.select_trait_candidate(trait_ref
).is_err()) {
1046 // This candidate's primary obligation doesn't even
1047 // select - don't bother registering anything in
1048 // `potentially_unsatisfied_predicates`.
1049 return ProbeResult
::NoMatch
;
1051 // Some nested subobligation of this predicate
1054 // FIXME: try to find the exact nested subobligation
1055 // and point at it rather than reporting the entire
1057 result
= ProbeResult
::NoMatch
;
1058 let trait_ref
= self.resolve_type_vars_if_possible(&trait_ref
);
1059 possibly_unsatisfied_predicates
.push(trait_ref
);
1066 debug
!("consider_probe - candidate_obligations={:?} sub_obligations={:?}",
1067 candidate_obligations
, sub_obligations
);
1069 // Evaluate those obligations to see if they might possibly hold.
1070 for o
in candidate_obligations
.into_iter().chain(sub_obligations
) {
1071 let o
= self.resolve_type_vars_if_possible(&o
);
1072 if !selcx
.evaluate_obligation(&o
) {
1073 result
= ProbeResult
::NoMatch
;
1074 if let &ty
::Predicate
::Trait(ref pred
) = &o
.predicate
{
1075 possibly_unsatisfied_predicates
.push(pred
.0.trait_ref
);
1080 if let ProbeResult
::Match
= result
{
1081 if let (Some(return_ty
), Some(xform_ret_ty
)) =
1082 (self.return_type
, probe
.xform_ret_ty
)
1084 let xform_ret_ty
= self.resolve_type_vars_if_possible(&xform_ret_ty
);
1085 debug
!("comparing return_ty {:?} with xform ret ty {:?}",
1087 probe
.xform_ret_ty
);
1088 if self.at(&ObligationCause
::dummy(), self.param_env
)
1089 .sup(return_ty
, xform_ret_ty
)
1092 return ProbeResult
::BadReturnType
;
1101 /// Sometimes we get in a situation where we have multiple probes that are all impls of the
1102 /// same trait, but we don't know which impl to use. In this case, since in all cases the
1103 /// external interface of the method can be determined from the trait, it's ok not to decide.
1104 /// We can basically just collapse all of the probes for various impls into one where-clause
1105 /// probe. This will result in a pending obligation so when more type-info is available we can
1106 /// make the final decision.
1108 /// Example (`src/test/run-pass/method-two-trait-defer-resolution-1.rs`):
1111 /// trait Foo { ... }
1112 /// impl Foo for Vec<int> { ... }
1113 /// impl Foo for Vec<usize> { ... }
1116 /// Now imagine the receiver is `Vec<_>`. It doesn't really matter at this time which impl we
1117 /// use, so it's ok to just commit to "using the method from the trait Foo".
1118 fn collapse_candidates_to_trait_pick(&self, probes
: &[(&Candidate
<'tcx
>, ProbeResult
)])
1119 -> Option
<Pick
<'tcx
>>
1121 // Do all probes correspond to the same trait?
1122 let container
= probes
[0].0.item
.container
;
1124 ty
::TraitContainer(_
) => {}
1125 ty
::ImplContainer(_
) => return None
,
1127 if probes
[1..].iter().any(|&(p
, _
)| p
.item
.container
!= container
) {
1131 // FIXME: check the return type here somehow.
1132 // If so, just use this trait and call it a day.
1134 item
: probes
[0].0.item
.clone(),
1136 import_id
: probes
[0].0.import_id
,
1143 /// Similarly to `probe_for_return_type`, this method attempts to find the best matching
1144 /// candidate method where the method name may have been misspelt. Similarly to other
1145 /// Levenshtein based suggestions, we provide at most one such suggestion.
1146 fn probe_for_lev_candidate(&mut self) -> Result
<Option
<ty
::AssociatedItem
>, MethodError
<'tcx
>> {
1147 debug
!("Probing for method names similar to {:?}",
1150 let steps
= self.steps
.clone();
1152 let mut pcx
= ProbeContext
::new(self.fcx
, self.span
, self.mode
, self.method_name
,
1153 self.return_type
, steps
);
1154 pcx
.allow_similar_names
= true;
1155 pcx
.assemble_inherent_candidates();
1156 pcx
.assemble_extension_candidates_for_traits_in_scope(ast
::DUMMY_NODE_ID
)?
;
1158 let method_names
= pcx
.candidate_method_names();
1159 pcx
.allow_similar_names
= false;
1160 let applicable_close_candidates
: Vec
<ty
::AssociatedItem
> = method_names
1162 .filter_map(|&method_name
| {
1164 pcx
.method_name
= Some(method_name
);
1165 pcx
.assemble_inherent_candidates();
1166 pcx
.assemble_extension_candidates_for_traits_in_scope(ast
::DUMMY_NODE_ID
)
1167 .ok().map_or(None
, |_
| {
1169 .and_then(|pick
| pick
.ok())
1170 .and_then(|pick
| Some(pick
.item
))
1175 if applicable_close_candidates
.is_empty() {
1179 let names
= applicable_close_candidates
.iter().map(|cand
| &cand
.name
);
1180 find_best_match_for_name(names
,
1181 &self.method_name
.unwrap().as_str(),
1184 Ok(applicable_close_candidates
1186 .find(|method
| method
.name
== best_name
))
1191 ///////////////////////////////////////////////////////////////////////////
1193 fn has_applicable_self(&self, item
: &ty
::AssociatedItem
) -> bool
{
1194 // "Fast track" -- check for usage of sugar when in method call
1197 // In Path mode (i.e., resolving a value like `T::next`), consider any
1198 // associated value (i.e., methods, constants) but not types.
1200 Mode
::MethodCall
=> item
.method_has_self_argument
,
1201 Mode
::Path
=> match item
.kind
{
1202 ty
::AssociatedKind
::Type
=> false,
1203 ty
::AssociatedKind
::Method
| ty
::AssociatedKind
::Const
=> true
1206 // FIXME -- check for types that deref to `Self`,
1207 // like `Rc<Self>` and so on.
1209 // Note also that the current code will break if this type
1210 // includes any of the type parameters defined on the method
1211 // -- but this could be overcome.
1214 fn record_static_candidate(&mut self, source
: CandidateSource
) {
1215 self.static_candidates
.push(source
);
1218 fn xform_self_ty(&self,
1219 item
: &ty
::AssociatedItem
,
1221 substs
: &Substs
<'tcx
>)
1222 -> (Ty
<'tcx
>, Option
<Ty
<'tcx
>>) {
1223 if item
.kind
== ty
::AssociatedKind
::Method
&& self.mode
== Mode
::MethodCall
{
1224 let sig
= self.xform_method_sig(item
.def_id
, substs
);
1225 (sig
.inputs()[0], Some(sig
.output()))
1231 fn xform_method_sig(&self,
1233 substs
: &Substs
<'tcx
>)
1236 let fn_sig
= self.tcx
.fn_sig(method
);
1237 debug
!("xform_self_ty(fn_sig={:?}, substs={:?})",
1241 assert
!(!substs
.has_escaping_regions());
1243 // It is possible for type parameters or early-bound lifetimes
1244 // to appear in the signature of `self`. The substitutions we
1245 // are given do not include type/lifetime parameters for the
1246 // method yet. So create fresh variables here for those too,
1247 // if there are any.
1248 let generics
= self.tcx
.generics_of(method
);
1249 assert_eq
!(substs
.types().count(), generics
.parent_types
as usize);
1250 assert_eq
!(substs
.regions().count(), generics
.parent_regions
as usize);
1252 // Erase any late-bound regions from the method and substitute
1253 // in the values from the substitution.
1254 let xform_fn_sig
= self.erase_late_bound_regions(&fn_sig
);
1256 if generics
.types
.is_empty() && generics
.regions
.is_empty() {
1257 xform_fn_sig
.subst(self.tcx
, substs
)
1259 let substs
= Substs
::for_item(self.tcx
, method
, |def
, _
| {
1260 let i
= def
.index
as usize;
1261 if i
< substs
.len() {
1264 // In general, during probe we erase regions. See
1265 // `impl_self_ty()` for an explanation.
1266 self.tcx
.types
.re_erased
1268 }, |def
, cur_substs
| {
1269 let i
= def
.index
as usize;
1270 if i
< substs
.len() {
1273 self.type_var_for_def(self.span
, def
, cur_substs
)
1276 xform_fn_sig
.subst(self.tcx
, substs
)
1280 /// Get the type of an impl and generate substitutions with placeholders.
1281 fn impl_ty_and_substs(&self, impl_def_id
: DefId
) -> (Ty
<'tcx
>, &'tcx Substs
<'tcx
>) {
1282 (self.tcx
.type_of(impl_def_id
), self.fresh_item_substs(impl_def_id
))
1285 fn fresh_item_substs(&self, def_id
: DefId
) -> &'tcx Substs
<'tcx
> {
1286 Substs
::for_item(self.tcx
,
1288 |_
, _
| self.tcx
.types
.re_erased
,
1289 |_
, _
| self.next_ty_var(
1290 TypeVariableOrigin
::SubstitutionPlaceholder(
1291 self.tcx
.def_span(def_id
))))
1294 /// Replace late-bound-regions bound by `value` with `'static` using
1295 /// `ty::erase_late_bound_regions`.
1297 /// This is only a reasonable thing to do during the *probe* phase, not the *confirm* phase, of
1298 /// method matching. It is reasonable during the probe phase because we don't consider region
1299 /// relationships at all. Therefore, we can just replace all the region variables with 'static
1300 /// rather than creating fresh region variables. This is nice for two reasons:
1302 /// 1. Because the numbers of the region variables would otherwise be fairly unique to this
1303 /// particular method call, it winds up creating fewer types overall, which helps for memory
1304 /// usage. (Admittedly, this is a rather small effect, though measureable.)
1306 /// 2. It makes it easier to deal with higher-ranked trait bounds, because we can replace any
1307 /// late-bound regions with 'static. Otherwise, if we were going to replace late-bound
1308 /// regions with actual region variables as is proper, we'd have to ensure that the same
1309 /// region got replaced with the same variable, which requires a bit more coordination
1310 /// and/or tracking the substitution and
1312 fn erase_late_bound_regions
<T
>(&self, value
: &ty
::Binder
<T
>) -> T
1313 where T
: TypeFoldable
<'tcx
>
1315 self.tcx
.erase_late_bound_regions(value
)
1318 /// Find the method with the appropriate name (or return type, as the case may be). If
1319 /// `allow_similar_names` is set, find methods with close-matching names.
1320 fn impl_or_trait_item(&self, def_id
: DefId
) -> Vec
<ty
::AssociatedItem
> {
1321 if let Some(name
) = self.method_name
{
1322 if self.allow_similar_names
{
1323 let max_dist
= max(name
.as_str().len(), 3) / 3;
1324 self.tcx
.associated_items(def_id
)
1326 let dist
= lev_distance(&*name
.as_str(), &x
.name
.as_str());
1327 Namespace
::from(x
.kind
) == Namespace
::Value
&& dist
> 0
1333 .associated_item(def_id
, name
, Namespace
::Value
)
1334 .map_or(Vec
::new(), |x
| vec
![x
])
1337 self.tcx
.associated_items(def_id
).collect()
1342 impl<'tcx
> Candidate
<'tcx
> {
1343 fn to_unadjusted_pick(&self) -> Pick
<'tcx
> {
1345 item
: self.item
.clone(),
1346 kind
: match self.kind
{
1347 InherentImplCandidate(..) => InherentImplPick
,
1348 ObjectCandidate
=> ObjectPick
,
1349 TraitCandidate(_
) => TraitPick
,
1350 WhereClauseCandidate(ref trait_ref
) => {
1351 // Only trait derived from where-clauses should
1352 // appear here, so they should not contain any
1353 // inference variables or other artifacts. This
1354 // means they are safe to put into the
1355 // `WhereClausePick`.
1356 assert
!(!trait_ref
.substs().needs_infer());
1358 WhereClausePick(trait_ref
.clone())
1361 import_id
: self.import_id
,