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
;
20 use rustc
::ty
::subst
::Subst
;
22 use rustc
::ty
::{self, Ty, ToPolyTraitRef, TraitRef, TypeFoldable}
;
23 use rustc
::infer
::{InferOk, TypeOrigin}
;
25 use syntax_pos
::{Span, DUMMY_SP}
;
27 use std
::collections
::HashSet
;
32 use self::CandidateKind
::*;
33 pub use self::PickKind
::*;
35 struct ProbeContext
<'a
, 'gcx
: 'a
+'tcx
, 'tcx
: 'a
> {
36 fcx
: &'a FnCtxt
<'a
, 'gcx
, 'tcx
>,
40 steps
: Rc
<Vec
<CandidateStep
<'tcx
>>>,
41 opt_simplified_steps
: Option
<Vec
<ty
::fast_reject
::SimplifiedType
>>,
42 inherent_candidates
: Vec
<Candidate
<'tcx
>>,
43 extension_candidates
: Vec
<Candidate
<'tcx
>>,
44 impl_dups
: HashSet
<DefId
>,
45 import_id
: Option
<ast
::NodeId
>,
47 /// Collects near misses when the candidate functions are missing a `self` keyword and is only
48 /// used for error reporting
49 static_candidates
: Vec
<CandidateSource
>,
51 /// Some(candidate) if there is a private candidate
52 private_candidate
: Option
<Def
>,
54 /// Collects near misses when trait bounds for type parameters are unsatisfied and is only used
55 /// for error reporting
56 unsatisfied_predicates
: Vec
<TraitRef
<'tcx
>>
59 impl<'a
, 'gcx
, 'tcx
> Deref
for ProbeContext
<'a
, 'gcx
, 'tcx
> {
60 type Target
= FnCtxt
<'a
, 'gcx
, 'tcx
>;
61 fn deref(&self) -> &Self::Target
{
67 struct CandidateStep
<'tcx
> {
74 struct Candidate
<'tcx
> {
75 xform_self_ty
: Ty
<'tcx
>,
76 item
: ty
::ImplOrTraitItem
<'tcx
>,
77 kind
: CandidateKind
<'tcx
>,
78 import_id
: Option
<ast
::NodeId
>,
82 enum CandidateKind
<'tcx
> {
83 InherentImplCandidate(subst
::Substs
<'tcx
>,
84 /* Normalize obligations */ Vec
<traits
::PredicateObligation
<'tcx
>>),
85 ExtensionImplCandidate(/* Impl */ DefId
, subst
::Substs
<'tcx
>,
86 /* Normalize obligations */ Vec
<traits
::PredicateObligation
<'tcx
>>),
89 WhereClauseCandidate(/* Trait */ ty
::PolyTraitRef
<'tcx
>),
93 pub struct Pick
<'tcx
> {
94 pub item
: ty
::ImplOrTraitItem
<'tcx
>,
95 pub kind
: PickKind
<'tcx
>,
96 pub import_id
: Option
<ast
::NodeId
>,
98 // Indicates that the source expression should be autoderef'd N times
100 // A = expr | *expr | **expr | ...
101 pub autoderefs
: usize,
103 // Indicates that an autoref is applied after the optional autoderefs
105 // B = A | &A | &mut A
106 pub autoref
: Option
<hir
::Mutability
>,
108 // Indicates that the source expression should be "unsized" to a
109 // target type. This should probably eventually go away in favor
110 // of just coercing method receivers.
113 pub unsize
: Option
<Ty
<'tcx
>>,
116 #[derive(Clone,Debug)]
117 pub enum PickKind
<'tcx
> {
119 ExtensionImplPick(/* Impl */ DefId
),
122 WhereClausePick(/* Trait */ ty
::PolyTraitRef
<'tcx
>),
125 pub type PickResult
<'tcx
> = Result
<Pick
<'tcx
>, MethodError
<'tcx
>>;
127 #[derive(PartialEq, Eq, Copy, Clone, Debug)]
129 // An expression of the form `receiver.method_name(...)`.
130 // Autoderefs are performed on `receiver`, lookup is done based on the
131 // `self` argument of the method, and static methods aren't considered.
133 // An expression of the form `Type::item` or `<T>::item`.
134 // No autoderefs are performed, lookup is done based on the type each
135 // implementation is for, and static methods are included.
139 impl<'a
, 'gcx
, 'tcx
> FnCtxt
<'a
, 'gcx
, 'tcx
> {
140 pub fn probe_method(&self,
143 item_name
: ast
::Name
,
145 scope_expr_id
: ast
::NodeId
)
148 debug
!("probe(self_ty={:?}, item_name={}, scope_expr_id={})",
153 // FIXME(#18741) -- right now, creating the steps involves evaluating the
154 // `*` operator, which registers obligations that then escape into
155 // the global fulfillment context and thus has global
156 // side-effects. This is a bit of a pain to refactor. So just let
157 // it ride, although it's really not great, and in fact could I
158 // think cause spurious errors. Really though this part should
159 // take place in the `self.probe` below.
160 let steps
= if mode
== Mode
::MethodCall
{
161 match self.create_steps(span
, self_ty
) {
162 Some(steps
) => steps
,
163 None
=>return Err(MethodError
::NoMatch(NoMatchData
::new(Vec
::new(), Vec
::new(),
174 // Create a list of simplified self types, if we can.
175 let mut simplified_steps
= Vec
::new();
177 match ty
::fast_reject
::simplify_type(self.tcx
, step
.self_ty
, true) {
179 Some(simplified_type
) => { simplified_steps.push(simplified_type); }
182 let opt_simplified_steps
=
183 if simplified_steps
.len() < steps
.len() {
184 None
// failed to convert at least one of the steps
186 Some(simplified_steps
)
189 debug
!("ProbeContext: steps for self_ty={:?} are {:?}",
193 // this creates one big transaction so that all type variables etc
194 // that we create during the probe process are removed later
196 let mut probe_cx
= ProbeContext
::new(self,
201 opt_simplified_steps
);
202 probe_cx
.assemble_inherent_candidates();
203 probe_cx
.assemble_extension_candidates_for_traits_in_scope(scope_expr_id
)?
;
208 fn create_steps(&self,
211 -> Option
<Vec
<CandidateStep
<'tcx
>>>
213 // FIXME: we don't need to create the entire steps in one pass
215 let mut autoderef
= self.autoderef(span
, self_ty
);
216 let mut steps
: Vec
<_
> = autoderef
.by_ref().map(|(ty
, d
)| CandidateStep
{
222 let final_ty
= autoderef
.unambiguous_final_ty();
224 ty
::TyArray(elem_ty
, _
) => {
225 let dereferences
= steps
.len() - 1;
227 steps
.push(CandidateStep
{
228 self_ty
: self.tcx
.mk_slice(elem_ty
),
229 autoderefs
: dereferences
,
233 ty
::TyError
=> return None
,
237 debug
!("create_steps: steps={:?}", steps
);
243 impl<'a
, 'gcx
, 'tcx
> ProbeContext
<'a
, 'gcx
, 'tcx
> {
244 fn new(fcx
: &'a FnCtxt
<'a
, 'gcx
, 'tcx
>,
247 item_name
: ast
::Name
,
248 steps
: Vec
<CandidateStep
<'tcx
>>,
249 opt_simplified_steps
: Option
<Vec
<ty
::fast_reject
::SimplifiedType
>>)
250 -> ProbeContext
<'a
, 'gcx
, 'tcx
>
256 item_name
: item_name
,
257 inherent_candidates
: Vec
::new(),
258 extension_candidates
: Vec
::new(),
259 impl_dups
: HashSet
::new(),
261 steps
: Rc
::new(steps
),
262 opt_simplified_steps
: opt_simplified_steps
,
263 static_candidates
: Vec
::new(),
264 private_candidate
: None
,
265 unsatisfied_predicates
: Vec
::new(),
269 fn reset(&mut self) {
270 self.inherent_candidates
.clear();
271 self.extension_candidates
.clear();
272 self.impl_dups
.clear();
273 self.static_candidates
.clear();
274 self.private_candidate
= None
;
277 ///////////////////////////////////////////////////////////////////////////
278 // CANDIDATE ASSEMBLY
280 fn assemble_inherent_candidates(&mut self) {
281 let steps
= self.steps
.clone();
282 for step
in steps
.iter() {
283 self.assemble_probe(step
.self_ty
);
287 fn assemble_probe(&mut self, self_ty
: Ty
<'tcx
>) {
288 debug
!("assemble_probe: self_ty={:?}",
292 ty
::TyTrait(box ref data
) => {
293 self.assemble_inherent_candidates_from_object(self_ty
, data
);
294 self.assemble_inherent_impl_candidates_for_type(data
.principal_def_id());
297 ty
::TyStruct(def
, _
) => {
298 self.assemble_inherent_impl_candidates_for_type(def
.did
);
301 if let Some(box_did
) = self.tcx
.lang_items
.owned_box() {
302 self.assemble_inherent_impl_candidates_for_type(box_did
);
306 self.assemble_inherent_candidates_from_param(self_ty
, p
);
309 let lang_def_id
= self.tcx
.lang_items
.char_impl();
310 self.assemble_inherent_impl_for_primitive(lang_def_id
);
313 let lang_def_id
= self.tcx
.lang_items
.str_impl();
314 self.assemble_inherent_impl_for_primitive(lang_def_id
);
317 let lang_def_id
= self.tcx
.lang_items
.slice_impl();
318 self.assemble_inherent_impl_for_primitive(lang_def_id
);
320 ty
::TyRawPtr(ty
::TypeAndMut { ty: _, mutbl: hir::MutImmutable }
) => {
321 let lang_def_id
= self.tcx
.lang_items
.const_ptr_impl();
322 self.assemble_inherent_impl_for_primitive(lang_def_id
);
324 ty
::TyRawPtr(ty
::TypeAndMut { ty: _, mutbl: hir::MutMutable }
) => {
325 let lang_def_id
= self.tcx
.lang_items
.mut_ptr_impl();
326 self.assemble_inherent_impl_for_primitive(lang_def_id
);
328 ty
::TyInt(ast
::IntTy
::I8
) => {
329 let lang_def_id
= self.tcx
.lang_items
.i8_impl();
330 self.assemble_inherent_impl_for_primitive(lang_def_id
);
332 ty
::TyInt(ast
::IntTy
::I16
) => {
333 let lang_def_id
= self.tcx
.lang_items
.i16_impl();
334 self.assemble_inherent_impl_for_primitive(lang_def_id
);
336 ty
::TyInt(ast
::IntTy
::I32
) => {
337 let lang_def_id
= self.tcx
.lang_items
.i32_impl();
338 self.assemble_inherent_impl_for_primitive(lang_def_id
);
340 ty
::TyInt(ast
::IntTy
::I64
) => {
341 let lang_def_id
= self.tcx
.lang_items
.i64_impl();
342 self.assemble_inherent_impl_for_primitive(lang_def_id
);
344 ty
::TyInt(ast
::IntTy
::Is
) => {
345 let lang_def_id
= self.tcx
.lang_items
.isize_impl();
346 self.assemble_inherent_impl_for_primitive(lang_def_id
);
348 ty
::TyUint(ast
::UintTy
::U8
) => {
349 let lang_def_id
= self.tcx
.lang_items
.u8_impl();
350 self.assemble_inherent_impl_for_primitive(lang_def_id
);
352 ty
::TyUint(ast
::UintTy
::U16
) => {
353 let lang_def_id
= self.tcx
.lang_items
.u16_impl();
354 self.assemble_inherent_impl_for_primitive(lang_def_id
);
356 ty
::TyUint(ast
::UintTy
::U32
) => {
357 let lang_def_id
= self.tcx
.lang_items
.u32_impl();
358 self.assemble_inherent_impl_for_primitive(lang_def_id
);
360 ty
::TyUint(ast
::UintTy
::U64
) => {
361 let lang_def_id
= self.tcx
.lang_items
.u64_impl();
362 self.assemble_inherent_impl_for_primitive(lang_def_id
);
364 ty
::TyUint(ast
::UintTy
::Us
) => {
365 let lang_def_id
= self.tcx
.lang_items
.usize_impl();
366 self.assemble_inherent_impl_for_primitive(lang_def_id
);
368 ty
::TyFloat(ast
::FloatTy
::F32
) => {
369 let lang_def_id
= self.tcx
.lang_items
.f32_impl();
370 self.assemble_inherent_impl_for_primitive(lang_def_id
);
372 ty
::TyFloat(ast
::FloatTy
::F64
) => {
373 let lang_def_id
= self.tcx
.lang_items
.f64_impl();
374 self.assemble_inherent_impl_for_primitive(lang_def_id
);
381 fn assemble_inherent_impl_for_primitive(&mut self, lang_def_id
: Option
<DefId
>) {
382 if let Some(impl_def_id
) = lang_def_id
{
383 self.tcx
.populate_implementations_for_primitive_if_necessary(impl_def_id
);
385 self.assemble_inherent_impl_probe(impl_def_id
);
389 fn assemble_inherent_impl_candidates_for_type(&mut self, def_id
: DefId
) {
390 // Read the inherent implementation candidates for this type from the
391 // metadata if necessary.
392 self.tcx
.populate_inherent_implementations_for_type_if_necessary(def_id
);
394 if let Some(impl_infos
) = self.tcx
.inherent_impls
.borrow().get(&def_id
) {
395 for &impl_def_id
in impl_infos
.iter() {
396 self.assemble_inherent_impl_probe(impl_def_id
);
401 fn assemble_inherent_impl_probe(&mut self, impl_def_id
: DefId
) {
402 if !self.impl_dups
.insert(impl_def_id
) {
403 return; // already visited
406 debug
!("assemble_inherent_impl_probe {:?}", impl_def_id
);
408 let item
= match self.impl_item(impl_def_id
) {
410 None
=> { return; }
// No method with correct name on this impl
413 if !self.has_applicable_self(&item
) {
414 // No receiver declared. Not a candidate.
415 return self.record_static_candidate(ImplSource(impl_def_id
));
418 if !item
.vis().is_accessible_from(self.body_id
, &self.tcx
.map
) {
419 self.private_candidate
= Some(item
.def());
423 let (impl_ty
, impl_substs
) = self.impl_ty_and_substs(impl_def_id
);
424 let impl_ty
= impl_ty
.subst(self.tcx
, &impl_substs
);
426 // Determine the receiver type that the method itself expects.
427 let xform_self_ty
= self.xform_self_ty(&item
, impl_ty
, &impl_substs
);
429 // We can't use normalize_associated_types_in as it will pollute the
430 // fcx's fulfillment context after this probe is over.
431 let cause
= traits
::ObligationCause
::misc(self.span
, self.body_id
);
432 let mut selcx
= &mut traits
::SelectionContext
::new(self.fcx
);
433 let traits
::Normalized { value: xform_self_ty, obligations }
=
434 traits
::normalize(selcx
, cause
, &xform_self_ty
);
435 debug
!("assemble_inherent_impl_probe: xform_self_ty = {:?}",
438 self.inherent_candidates
.push(Candidate
{
439 xform_self_ty
: xform_self_ty
,
441 kind
: InherentImplCandidate(impl_substs
, obligations
),
442 import_id
: self.import_id
,
446 fn assemble_inherent_candidates_from_object(&mut self,
448 data
: &ty
::TraitTy
<'tcx
>) {
449 debug
!("assemble_inherent_candidates_from_object(self_ty={:?})",
452 // It is illegal to invoke a method on a trait instance that
453 // refers to the `Self` type. An error will be reported by
454 // `enforce_object_limitations()` if the method refers to the
455 // `Self` type anywhere other than the receiver. Here, we use
456 // a substitution that replaces `Self` with the object type
457 // itself. Hence, a `&self` method will wind up with an
458 // argument type like `&Trait`.
459 let trait_ref
= data
.principal_trait_ref_with_self_ty(self.tcx
, self_ty
);
460 self.elaborate_bounds(&[trait_ref
], |this
, new_trait_ref
, item
| {
461 let new_trait_ref
= this
.erase_late_bound_regions(&new_trait_ref
);
463 let xform_self_ty
= this
.xform_self_ty(&item
,
464 new_trait_ref
.self_ty(),
465 new_trait_ref
.substs
);
467 this
.inherent_candidates
.push(Candidate
{
468 xform_self_ty
: xform_self_ty
,
470 kind
: ObjectCandidate
,
471 import_id
: this
.import_id
,
476 fn assemble_inherent_candidates_from_param(&mut self,
478 param_ty
: ty
::ParamTy
) {
479 // FIXME -- Do we want to commit to this behavior for param bounds?
482 self.parameter_environment
.caller_bounds
484 .filter_map(|predicate
| {
486 ty
::Predicate
::Trait(ref trait_predicate
) => {
487 match trait_predicate
.0.trait_ref
.self_ty().sty
{
488 ty
::TyParam(ref p
) if *p
== param_ty
=> {
489 Some(trait_predicate
.to_poly_trait_ref())
494 ty
::Predicate
::Equate(..) |
495 ty
::Predicate
::Projection(..) |
496 ty
::Predicate
::RegionOutlives(..) |
497 ty
::Predicate
::WellFormed(..) |
498 ty
::Predicate
::ObjectSafe(..) |
499 ty
::Predicate
::ClosureKind(..) |
500 ty
::Predicate
::Rfc1592(..) |
501 ty
::Predicate
::TypeOutlives(..) => {
508 self.elaborate_bounds(&bounds
, |this
, poly_trait_ref
, item
| {
510 this
.erase_late_bound_regions(&poly_trait_ref
);
513 this
.xform_self_ty(&item
,
517 if let Some(ref m
) = item
.as_opt_method() {
518 debug
!("found match: trait_ref={:?} substs={:?} m={:?}",
522 assert_eq
!(m
.generics
.types
.get_slice(subst
::TypeSpace
).len(),
523 trait_ref
.substs
.types
.get_slice(subst
::TypeSpace
).len());
524 assert_eq
!(m
.generics
.regions
.get_slice(subst
::TypeSpace
).len(),
525 trait_ref
.substs
.regions
.get_slice(subst
::TypeSpace
).len());
526 assert_eq
!(m
.generics
.types
.get_slice(subst
::SelfSpace
).len(),
527 trait_ref
.substs
.types
.get_slice(subst
::SelfSpace
).len());
528 assert_eq
!(m
.generics
.regions
.get_slice(subst
::SelfSpace
).len(),
529 trait_ref
.substs
.regions
.get_slice(subst
::SelfSpace
).len());
532 // Because this trait derives from a where-clause, it
533 // should not contain any inference variables or other
534 // artifacts. This means it is safe to put into the
535 // `WhereClauseCandidate` and (eventually) into the
536 // `WhereClausePick`.
537 assert
!(!trait_ref
.substs
.types
.needs_infer());
539 this
.inherent_candidates
.push(Candidate
{
540 xform_self_ty
: xform_self_ty
,
542 kind
: WhereClauseCandidate(poly_trait_ref
),
543 import_id
: this
.import_id
,
548 // Do a search through a list of bounds, using a callback to actually
549 // create the candidates.
550 fn elaborate_bounds
<F
>(
552 bounds
: &[ty
::PolyTraitRef
<'tcx
>],
556 &mut ProbeContext
<'b
, 'gcx
, 'tcx
>,
557 ty
::PolyTraitRef
<'tcx
>,
558 ty
::ImplOrTraitItem
<'tcx
>,
561 debug
!("elaborate_bounds(bounds={:?})", bounds
);
564 for bound_trait_ref
in traits
::transitive_bounds(tcx
, bounds
) {
565 let item
= match self.trait_item(bound_trait_ref
.def_id()) {
567 None
=> { continue; }
570 if !self.has_applicable_self(&item
) {
571 self.record_static_candidate(TraitSource(bound_trait_ref
.def_id()));
573 mk_cand(self, bound_trait_ref
, item
);
578 fn assemble_extension_candidates_for_traits_in_scope(&mut self,
579 expr_id
: ast
::NodeId
)
580 -> Result
<(), MethodError
<'tcx
>>
582 let mut duplicates
= HashSet
::new();
583 let opt_applicable_traits
= self.tcx
.trait_map
.get(&expr_id
);
584 if let Some(applicable_traits
) = opt_applicable_traits
{
585 for trait_candidate
in applicable_traits
{
586 let trait_did
= trait_candidate
.def_id
;
587 if duplicates
.insert(trait_did
) {
588 self.import_id
= trait_candidate
.import_id
;
589 let result
= self.assemble_extension_candidates_for_trait(trait_did
);
590 self.import_id
= None
;
598 fn assemble_extension_candidates_for_all_traits(&mut self) -> Result
<(), MethodError
<'tcx
>> {
599 let mut duplicates
= HashSet
::new();
600 for trait_info
in suggest
::all_traits(self.ccx
) {
601 if duplicates
.insert(trait_info
.def_id
) {
602 self.assemble_extension_candidates_for_trait(trait_info
.def_id
)?
;
608 fn assemble_extension_candidates_for_trait(&mut self,
610 -> Result
<(), MethodError
<'tcx
>>
612 debug
!("assemble_extension_candidates_for_trait(trait_def_id={:?})",
615 // Check whether `trait_def_id` defines a method with suitable name:
617 self.tcx
.trait_items(trait_def_id
);
620 .find(|item
| item
.name() == self.item_name
);
621 let item
= match maybe_item
{
623 None
=> { return Ok(()); }
626 // Check whether `trait_def_id` defines a method with suitable name:
627 if !self.has_applicable_self(item
) {
628 debug
!("method has inapplicable self");
629 self.record_static_candidate(TraitSource(trait_def_id
));
633 self.assemble_extension_candidates_for_trait_impls(trait_def_id
, item
.clone());
635 self.assemble_closure_candidates(trait_def_id
, item
.clone())?
;
637 self.assemble_projection_candidates(trait_def_id
, item
.clone());
639 self.assemble_where_clause_candidates(trait_def_id
, item
.clone());
644 fn assemble_extension_candidates_for_trait_impls(&mut self,
646 item
: ty
::ImplOrTraitItem
<'tcx
>)
648 let trait_def
= self.tcx
.lookup_trait_def(trait_def_id
);
650 // FIXME(arielb1): can we use for_each_relevant_impl here?
651 trait_def
.for_each_impl(self.tcx
, |impl_def_id
| {
652 debug
!("assemble_extension_candidates_for_trait_impl: trait_def_id={:?} \
657 if !self.impl_can_possibly_match(impl_def_id
) {
661 let (_
, impl_substs
) = self.impl_ty_and_substs(impl_def_id
);
663 debug
!("impl_substs={:?}", impl_substs
);
666 self.tcx
.impl_trait_ref(impl_def_id
)
667 .unwrap() // we know this is a trait impl
668 .subst(self.tcx
, &impl_substs
);
670 debug
!("impl_trait_ref={:?}", impl_trait_ref
);
672 // Determine the receiver type that the method itself expects.
674 self.xform_self_ty(&item
,
675 impl_trait_ref
.self_ty(),
676 impl_trait_ref
.substs
);
678 // Normalize the receiver. We can't use normalize_associated_types_in
679 // as it will pollute the fcx's fulfillment context after this probe
681 let cause
= traits
::ObligationCause
::misc(self.span
, self.body_id
);
682 let mut selcx
= &mut traits
::SelectionContext
::new(self.fcx
);
683 let traits
::Normalized { value: xform_self_ty, obligations }
=
684 traits
::normalize(selcx
, cause
, &xform_self_ty
);
686 debug
!("xform_self_ty={:?}", xform_self_ty
);
688 self.extension_candidates
.push(Candidate
{
689 xform_self_ty
: xform_self_ty
,
691 kind
: ExtensionImplCandidate(impl_def_id
, impl_substs
, obligations
),
692 import_id
: self.import_id
,
697 fn impl_can_possibly_match(&self, impl_def_id
: DefId
) -> bool
{
698 let simplified_steps
= match self.opt_simplified_steps
{
699 Some(ref simplified_steps
) => simplified_steps
,
700 None
=> { return true; }
703 let impl_type
= self.tcx
.lookup_item_type(impl_def_id
);
704 let impl_simplified_type
=
705 match ty
::fast_reject
::simplify_type(self.tcx
, impl_type
.ty
, false) {
706 Some(simplified_type
) => simplified_type
,
707 None
=> { return true; }
710 simplified_steps
.contains(&impl_simplified_type
)
713 fn assemble_closure_candidates(&mut self,
715 item
: ty
::ImplOrTraitItem
<'tcx
>)
716 -> Result
<(), MethodError
<'tcx
>>
718 // Check if this is one of the Fn,FnMut,FnOnce traits.
720 let kind
= if Some(trait_def_id
) == tcx
.lang_items
.fn_trait() {
722 } else if Some(trait_def_id
) == tcx
.lang_items
.fn_mut_trait() {
723 ty
::ClosureKind
::FnMut
724 } else if Some(trait_def_id
) == tcx
.lang_items
.fn_once_trait() {
725 ty
::ClosureKind
::FnOnce
730 // Check if there is an unboxed-closure self-type in the list of receivers.
731 // If so, add "synthetic impls".
732 let steps
= self.steps
.clone();
733 for step
in steps
.iter() {
734 let closure_def_id
= match step
.self_ty
.sty
{
735 ty
::TyClosure(a
, _
) => a
,
739 let closure_kinds
= &self.tables
.borrow().closure_kinds
;
740 let closure_kind
= match closure_kinds
.get(&closure_def_id
) {
743 return Err(MethodError
::ClosureAmbiguity(trait_def_id
));
747 // this closure doesn't implement the right kind of `Fn` trait
748 if !closure_kind
.extends(kind
) {
752 // create some substitutions for the argument/return type;
753 // for the purposes of our method lookup, we only take
754 // receiver type into account, so we can just substitute
755 // fresh types here to use during substitution and subtyping.
756 let trait_def
= self.tcx
.lookup_trait_def(trait_def_id
);
757 let substs
= self.fresh_substs_for_trait(self.span
,
761 let xform_self_ty
= self.xform_self_ty(&item
,
764 self.inherent_candidates
.push(Candidate
{
765 xform_self_ty
: xform_self_ty
,
767 kind
: TraitCandidate
,
768 import_id
: self.import_id
,
775 fn assemble_projection_candidates(&mut self,
777 item
: ty
::ImplOrTraitItem
<'tcx
>)
779 debug
!("assemble_projection_candidates(\
785 for step
in self.steps
.iter() {
786 debug
!("assemble_projection_candidates: step={:?}",
789 let (def_id
, substs
) = match step
.self_ty
.sty
{
790 ty
::TyProjection(ref data
) => {
791 (data
.trait_ref
.def_id
, data
.trait_ref
.substs
)
793 ty
::TyAnon(def_id
, substs
) => (def_id
, substs
),
797 debug
!("assemble_projection_candidates: def_id={:?} substs={:?}",
800 let trait_predicates
= self.tcx
.lookup_predicates(def_id
);
801 let bounds
= trait_predicates
.instantiate(self.tcx
, substs
);
802 let predicates
= bounds
.predicates
.into_vec();
803 debug
!("assemble_projection_candidates: predicates={:?}",
806 traits
::elaborate_predicates(self.tcx
, predicates
)
807 .filter_map(|p
| p
.to_opt_poly_trait_ref())
808 .filter(|b
| b
.def_id() == trait_def_id
)
810 let bound
= self.erase_late_bound_regions(&poly_bound
);
812 debug
!("assemble_projection_candidates: def_id={:?} substs={:?} bound={:?}",
813 def_id
, substs
, bound
);
815 if self.can_equate(&step
.self_ty
, &bound
.self_ty()).is_ok() {
816 let xform_self_ty
= self.xform_self_ty(&item
,
820 debug
!("assemble_projection_candidates: bound={:?} xform_self_ty={:?}",
824 self.extension_candidates
.push(Candidate
{
825 xform_self_ty
: xform_self_ty
,
827 kind
: TraitCandidate
,
828 import_id
: self.import_id
,
835 fn assemble_where_clause_candidates(&mut self,
837 item
: ty
::ImplOrTraitItem
<'tcx
>)
839 debug
!("assemble_where_clause_candidates(trait_def_id={:?})",
842 let caller_predicates
= self.parameter_environment
.caller_bounds
.clone();
843 for poly_bound
in traits
::elaborate_predicates(self.tcx
, caller_predicates
)
844 .filter_map(|p
| p
.to_opt_poly_trait_ref())
845 .filter(|b
| b
.def_id() == trait_def_id
)
847 let bound
= self.erase_late_bound_regions(&poly_bound
);
848 let xform_self_ty
= self.xform_self_ty(&item
,
852 debug
!("assemble_where_clause_candidates: bound={:?} xform_self_ty={:?}",
856 self.extension_candidates
.push(Candidate
{
857 xform_self_ty
: xform_self_ty
,
859 kind
: WhereClauseCandidate(poly_bound
),
860 import_id
: self.import_id
,
865 ///////////////////////////////////////////////////////////////////////////
868 fn pick(mut self) -> PickResult
<'tcx
> {
869 if let Some(r
) = self.pick_core() {
873 let static_candidates
= mem
::replace(&mut self.static_candidates
, vec
![]);
874 let private_candidate
= mem
::replace(&mut self.private_candidate
, None
);
875 let unsatisfied_predicates
= mem
::replace(&mut self.unsatisfied_predicates
, vec
![]);
877 // things failed, so lets look at all traits, for diagnostic purposes now:
880 let span
= self.span
;
883 self.assemble_extension_candidates_for_all_traits()?
;
885 let out_of_scope_traits
= match self.pick_core() {
886 Some(Ok(p
)) => vec
![p
.item
.container().id()],
887 Some(Err(MethodError
::Ambiguity(v
))) => v
.into_iter().map(|source
| {
889 TraitSource(id
) => id
,
890 ImplSource(impl_id
) => {
891 match tcx
.trait_id_of_impl(impl_id
) {
895 "found inherent method when looking at traits")
900 Some(Err(MethodError
::NoMatch(NoMatchData { out_of_scope_traits: others, .. }
))) => {
901 assert
!(others
.is_empty());
904 Some(Err(MethodError
::ClosureAmbiguity(..))) => {
905 // this error only occurs when assembling candidates
906 span_bug
!(span
, "encountered ClosureAmbiguity from pick_core");
911 if let Some(def
) = private_candidate
{
912 return Err(MethodError
::PrivateMatch(def
));
915 Err(MethodError
::NoMatch(NoMatchData
::new(static_candidates
, unsatisfied_predicates
,
916 out_of_scope_traits
, self.mode
)))
919 fn pick_core(&mut self) -> Option
<PickResult
<'tcx
>> {
920 let steps
= self.steps
.clone();
922 // find the first step that works
923 steps
.iter().filter_map(|step
| self.pick_step(step
)).next()
926 fn pick_step(&mut self, step
: &CandidateStep
<'tcx
>) -> Option
<PickResult
<'tcx
>> {
927 debug
!("pick_step: step={:?}", step
);
929 if step
.self_ty
.references_error() {
933 if let Some(result
) = self.pick_by_value_method(step
) {
937 self.pick_autorefd_method(step
)
940 fn pick_by_value_method(&mut self,
941 step
: &CandidateStep
<'tcx
>)
942 -> Option
<PickResult
<'tcx
>>
945 * For each type `T` in the step list, this attempts to find a
946 * method where the (transformed) self type is exactly `T`. We
947 * do however do one transformation on the adjustment: if we
948 * are passing a region pointer in, we will potentially
949 * *reborrow* it to a shorter lifetime. This allows us to
950 * transparently pass `&mut` pointers, in particular, without
951 * consuming them for their entire lifetime.
958 self.pick_method(step
.self_ty
).map(|r
| r
.map(|mut pick
| {
959 pick
.autoderefs
= step
.autoderefs
;
961 // Insert a `&*` or `&mut *` if this is a reference type:
962 if let ty
::TyRef(_
, mt
) = step
.self_ty
.sty
{
963 pick
.autoderefs
+= 1;
964 pick
.autoref
= Some(mt
.mutbl
);
971 fn pick_autorefd_method(&mut self,
972 step
: &CandidateStep
<'tcx
>)
973 -> Option
<PickResult
<'tcx
>>
977 // In general, during probing we erase regions. See
978 // `impl_self_ty()` for an explanation.
979 let region
= tcx
.mk_region(ty
::ReErased
);
981 // Search through mutabilities in order to find one where pick works:
982 [hir
::MutImmutable
, hir
::MutMutable
].iter().filter_map(|&m
| {
983 let autoref_ty
= tcx
.mk_ref(region
, ty
::TypeAndMut
{
987 self.pick_method(autoref_ty
).map(|r
| r
.map(|mut pick
| {
988 pick
.autoderefs
= step
.autoderefs
;
989 pick
.autoref
= Some(m
);
990 pick
.unsize
= if step
.unsize
{
1000 fn pick_method(&mut self, self_ty
: Ty
<'tcx
>) -> Option
<PickResult
<'tcx
>> {
1001 debug
!("pick_method(self_ty={})", self.ty_to_string(self_ty
));
1003 let mut possibly_unsatisfied_predicates
= Vec
::new();
1005 debug
!("searching inherent candidates");
1006 if let Some(pick
) = self.consider_candidates(self_ty
,
1007 &self.inherent_candidates
,
1008 &mut possibly_unsatisfied_predicates
) {
1012 debug
!("searching extension candidates");
1013 let res
= self.consider_candidates(self_ty
, &self.extension_candidates
,
1014 &mut possibly_unsatisfied_predicates
);
1016 self.unsatisfied_predicates
.extend(possibly_unsatisfied_predicates
);
1021 fn consider_candidates(&self,
1023 probes
: &[Candidate
<'tcx
>],
1024 possibly_unsatisfied_predicates
: &mut Vec
<TraitRef
<'tcx
>>)
1025 -> Option
<PickResult
<'tcx
>> {
1026 let mut applicable_candidates
: Vec
<_
> =
1028 .filter(|&probe
| self.consider_probe(self_ty
,
1029 probe
,possibly_unsatisfied_predicates
))
1032 debug
!("applicable_candidates: {:?}", applicable_candidates
);
1034 if applicable_candidates
.len() > 1 {
1035 match self.collapse_candidates_to_trait_pick(&applicable_candidates
[..]) {
1036 Some(pick
) => { return Some(Ok(pick)); }
1041 if applicable_candidates
.len() > 1 {
1042 let sources
= probes
.iter().map(|p
| p
.to_source()).collect();
1043 return Some(Err(MethodError
::Ambiguity(sources
)));
1046 applicable_candidates
.pop().map(|probe
| {
1047 Ok(probe
.to_unadjusted_pick())
1051 fn consider_probe(&self, self_ty
: Ty
<'tcx
>, probe
: &Candidate
<'tcx
>,
1052 possibly_unsatisfied_predicates
: &mut Vec
<TraitRef
<'tcx
>>) -> bool
{
1053 debug
!("consider_probe: self_ty={:?} probe={:?}",
1058 // First check that the self type can be related.
1059 match self.sub_types(false, TypeOrigin
::Misc(DUMMY_SP
),
1060 self_ty
, probe
.xform_self_ty
) {
1061 Ok(InferOk { obligations, .. }
) => {
1062 // FIXME(#32730) propagate obligations
1063 assert
!(obligations
.is_empty())
1066 debug
!("--> cannot relate self-types");
1071 // If so, impls may carry other conditions (e.g., where
1072 // clauses) that must be considered. Make sure that those
1073 // match as well (or at least may match, sometimes we
1074 // don't have enough information to fully evaluate).
1075 let (impl_def_id
, substs
, ref_obligations
) = match probe
.kind
{
1076 InherentImplCandidate(ref substs
, ref ref_obligations
) => {
1077 (probe
.item
.container().id(), substs
, ref_obligations
)
1080 ExtensionImplCandidate(impl_def_id
, ref substs
, ref ref_obligations
) => {
1081 (impl_def_id
, substs
, ref_obligations
)
1086 WhereClauseCandidate(..) => {
1087 // These have no additional conditions to check.
1092 let selcx
= &mut traits
::SelectionContext
::new(self);
1093 let cause
= traits
::ObligationCause
::misc(self.span
, self.body_id
);
1095 // Check whether the impl imposes obligations we have to worry about.
1096 let impl_bounds
= self.tcx
.lookup_predicates(impl_def_id
);
1097 let impl_bounds
= impl_bounds
.instantiate(self.tcx
, substs
);
1098 let traits
::Normalized
{ value
: impl_bounds
,
1099 obligations
: norm_obligations
} =
1100 traits
::normalize(selcx
, cause
.clone(), &impl_bounds
);
1102 // Convert the bounds into obligations.
1104 traits
::predicates_for_generics(cause
.clone(),
1106 debug
!("impl_obligations={:?}", obligations
);
1108 // Evaluate those obligations to see if they might possibly hold.
1109 let mut all_true
= true;
1110 for o
in obligations
.iter()
1111 .chain(norm_obligations
.iter())
1112 .chain(ref_obligations
.iter()) {
1113 if !selcx
.evaluate_obligation(o
) {
1115 if let &ty
::Predicate
::Trait(ref pred
) = &o
.predicate
{
1116 possibly_unsatisfied_predicates
.push(pred
.0.trait_ref
);
1124 /// Sometimes we get in a situation where we have multiple probes that are all impls of the
1125 /// same trait, but we don't know which impl to use. In this case, since in all cases the
1126 /// external interface of the method can be determined from the trait, it's ok not to decide.
1127 /// We can basically just collapse all of the probes for various impls into one where-clause
1128 /// probe. This will result in a pending obligation so when more type-info is available we can
1129 /// make the final decision.
1131 /// Example (`src/test/run-pass/method-two-trait-defer-resolution-1.rs`):
1134 /// trait Foo { ... }
1135 /// impl Foo for Vec<int> { ... }
1136 /// impl Foo for Vec<usize> { ... }
1139 /// Now imagine the receiver is `Vec<_>`. It doesn't really matter at this time which impl we
1140 /// use, so it's ok to just commit to "using the method from the trait Foo".
1141 fn collapse_candidates_to_trait_pick(&self,
1142 probes
: &[&Candidate
<'tcx
>])
1143 -> Option
<Pick
<'tcx
>> {
1144 // Do all probes correspond to the same trait?
1145 let container
= probes
[0].item
.container();
1147 ty
::TraitContainer(_
) => {}
1148 ty
::ImplContainer(_
) => return None
1150 if probes
[1..].iter().any(|p
| p
.item
.container() != container
) {
1154 // If so, just use this trait and call it a day.
1156 item
: probes
[0].item
.clone(),
1158 import_id
: probes
[0].import_id
,
1165 ///////////////////////////////////////////////////////////////////////////
1167 fn has_applicable_self(&self, item
: &ty
::ImplOrTraitItem
) -> bool
{
1168 // "fast track" -- check for usage of sugar
1170 ty
::ImplOrTraitItem
::MethodTraitItem(ref method
) =>
1171 match method
.explicit_self
{
1172 ty
::ExplicitSelfCategory
::Static
=> self.mode
== Mode
::Path
,
1173 ty
::ExplicitSelfCategory
::ByValue
|
1174 ty
::ExplicitSelfCategory
::ByReference(..) |
1175 ty
::ExplicitSelfCategory
::ByBox
=> true,
1177 ty
::ImplOrTraitItem
::ConstTraitItem(..) => self.mode
== Mode
::Path
,
1180 // FIXME -- check for types that deref to `Self`,
1181 // like `Rc<Self>` and so on.
1183 // Note also that the current code will break if this type
1184 // includes any of the type parameters defined on the method
1185 // -- but this could be overcome.
1188 fn record_static_candidate(&mut self, source
: CandidateSource
) {
1189 self.static_candidates
.push(source
);
1192 fn xform_self_ty(&self,
1193 item
: &ty
::ImplOrTraitItem
<'tcx
>,
1195 substs
: &subst
::Substs
<'tcx
>)
1198 match item
.as_opt_method() {
1199 Some(ref method
) => self.xform_method_self_ty(method
, impl_ty
,
1205 fn xform_method_self_ty(&self,
1206 method
: &Rc
<ty
::Method
<'tcx
>>,
1208 substs
: &subst
::Substs
<'tcx
>)
1211 debug
!("xform_self_ty(impl_ty={:?}, self_ty={:?}, substs={:?})",
1213 method
.fty
.sig
.0.inputs
.get(0),
1216 assert
!(!substs
.has_escaping_regions());
1218 // It is possible for type parameters or early-bound lifetimes
1219 // to appear in the signature of `self`. The substitutions we
1220 // are given do not include type/lifetime parameters for the
1221 // method yet. So create fresh variables here for those too,
1222 // if there are any.
1223 assert_eq
!(substs
.types
.len(subst
::FnSpace
), 0);
1224 assert_eq
!(substs
.regions
.len(subst
::FnSpace
), 0);
1226 if self.mode
== Mode
::Path
{
1230 let mut placeholder
;
1231 let mut substs
= substs
;
1233 !method
.generics
.types
.is_empty_in(subst
::FnSpace
) ||
1234 !method
.generics
.regions
.is_empty_in(subst
::FnSpace
)
1236 // In general, during probe we erase regions. See
1237 // `impl_self_ty()` for an explanation.
1238 let method_regions
=
1239 method
.generics
.regions
.get_slice(subst
::FnSpace
)
1241 .map(|_
| ty
::ReErased
)
1244 placeholder
= (*substs
).clone().with_method(Vec
::new(), method_regions
);
1246 self.type_vars_for_defs(
1250 method
.generics
.types
.get_slice(subst
::FnSpace
));
1252 substs
= &placeholder
;
1255 // Erase any late-bound regions from the method and substitute
1256 // in the values from the substitution.
1257 let xform_self_ty
= method
.fty
.sig
.input(0);
1258 let xform_self_ty
= self.erase_late_bound_regions(&xform_self_ty
);
1259 let xform_self_ty
= xform_self_ty
.subst(self.tcx
, substs
);
1264 /// Get the type of an impl and generate substitutions with placeholders.
1265 fn impl_ty_and_substs(&self,
1267 -> (Ty
<'tcx
>, subst
::Substs
<'tcx
>)
1269 let impl_pty
= self.tcx
.lookup_item_type(impl_def_id
);
1272 impl_pty
.generics
.types
.map(
1273 |_
| self.next_ty_var());
1275 let region_placeholders
=
1276 impl_pty
.generics
.regions
.map(
1277 |_
| ty
::ReErased
); // see erase_late_bound_regions() for an expl of why 'erased
1279 let substs
= subst
::Substs
::new(type_vars
, region_placeholders
);
1280 (impl_pty
.ty
, substs
)
1283 /// Replace late-bound-regions bound by `value` with `'static` using
1284 /// `ty::erase_late_bound_regions`.
1286 /// This is only a reasonable thing to do during the *probe* phase, not the *confirm* phase, of
1287 /// method matching. It is reasonable during the probe phase because we don't consider region
1288 /// relationships at all. Therefore, we can just replace all the region variables with 'static
1289 /// rather than creating fresh region variables. This is nice for two reasons:
1291 /// 1. Because the numbers of the region variables would otherwise be fairly unique to this
1292 /// particular method call, it winds up creating fewer types overall, which helps for memory
1293 /// usage. (Admittedly, this is a rather small effect, though measureable.)
1295 /// 2. It makes it easier to deal with higher-ranked trait bounds, because we can replace any
1296 /// late-bound regions with 'static. Otherwise, if we were going to replace late-bound
1297 /// regions with actual region variables as is proper, we'd have to ensure that the same
1298 /// region got replaced with the same variable, which requires a bit more coordination
1299 /// and/or tracking the substitution and
1301 fn erase_late_bound_regions
<T
>(&self, value
: &ty
::Binder
<T
>) -> T
1302 where T
: TypeFoldable
<'tcx
>
1304 self.tcx
.erase_late_bound_regions(value
)
1307 fn impl_item(&self, impl_def_id
: DefId
)
1308 -> Option
<ty
::ImplOrTraitItem
<'tcx
>>
1310 self.fcx
.impl_item(impl_def_id
, self.item_name
)
1313 /// Find item with name `item_name` defined in `trait_def_id`
1314 /// and return it, or `None`, if no such item.
1315 fn trait_item(&self, trait_def_id
: DefId
)
1316 -> Option
<ty
::ImplOrTraitItem
<'tcx
>>
1318 self.fcx
.trait_item(trait_def_id
, self.item_name
)
1322 impl<'tcx
> Candidate
<'tcx
> {
1323 fn to_unadjusted_pick(&self) -> Pick
<'tcx
> {
1325 item
: self.item
.clone(),
1326 kind
: match self.kind
{
1327 InherentImplCandidate(_
, _
) => InherentImplPick
,
1328 ExtensionImplCandidate(def_id
, _
, _
) => {
1329 ExtensionImplPick(def_id
)
1331 ObjectCandidate
=> ObjectPick
,
1332 TraitCandidate
=> TraitPick
,
1333 WhereClauseCandidate(ref trait_ref
) => {
1334 // Only trait derived from where-clauses should
1335 // appear here, so they should not contain any
1336 // inference variables or other artifacts. This
1337 // means they are safe to put into the
1338 // `WhereClausePick`.
1339 assert
!(!trait_ref
.substs().types
.needs_infer());
1341 WhereClausePick(trait_ref
.clone())
1344 import_id
: self.import_id
,
1351 fn to_source(&self) -> CandidateSource
{
1353 InherentImplCandidate(_
, _
) => {
1354 ImplSource(self.item
.container().id())
1356 ExtensionImplCandidate(def_id
, _
, _
) => ImplSource(def_id
),
1359 WhereClauseCandidate(_
) => TraitSource(self.item
.container().id()),