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,Ambiguity,NoMatch};
12 use super::MethodIndex;
13 use super::{CandidateSource,ImplSource,TraitSource};
16 use check::{FnCtxt, NoPreference};
17 use middle::fast_reject;
19 use middle::subst::Subst;
21 use middle::ty::{self, RegionEscape, Ty, ToPolyTraitRef};
22 use middle::ty_fold::TypeFoldable;
24 use middle::infer::InferCtxt;
26 use syntax::codemap::{Span, DUMMY_SP};
27 use std::collections::HashSet;
29 use util::ppaux::Repr;
31 use self::CandidateKind::*;
32 pub use self::PickAdjustment::*;
33 pub use self::PickKind::*;
35 struct ProbeContext<'a, 'tcx:'a> {
36 fcx: &'a FnCtxt<'a, 'tcx>,
38 method_name: ast::Name,
39 steps: Rc<Vec<CandidateStep<'tcx>>>,
40 opt_simplified_steps: Option<Vec<fast_reject::SimplifiedType>>,
41 inherent_candidates: Vec<Candidate<'tcx>>,
42 extension_candidates: Vec<Candidate<'tcx>>,
43 impl_dups: HashSet<ast::DefId>,
44 static_candidates: Vec<CandidateSource>,
47 struct CandidateStep<'tcx> {
49 adjustment: PickAdjustment,
52 struct Candidate<'tcx> {
53 xform_self_ty: Ty<'tcx>,
54 method_ty: Rc<ty::Method<'tcx>>,
55 kind: CandidateKind<'tcx>,
58 enum CandidateKind<'tcx> {
59 InherentImplCandidate(/* Impl */ ast::DefId, subst::Substs<'tcx>),
60 ObjectCandidate(/* Trait */ ast::DefId, /* method_num */ uint, /* real_index */ uint),
61 ExtensionImplCandidate(/* Impl */ ast::DefId, Rc<ty::TraitRef<'tcx>>,
62 subst::Substs<'tcx>, MethodIndex),
63 UnboxedClosureCandidate(/* Trait */ ast::DefId, MethodIndex),
64 WhereClauseCandidate(ty::PolyTraitRef<'tcx>, MethodIndex),
65 ProjectionCandidate(ast::DefId, MethodIndex),
68 pub struct Pick<'tcx> {
69 pub method_ty: Rc<ty::Method<'tcx>>,
70 pub adjustment: PickAdjustment,
71 pub kind: PickKind<'tcx>,
75 pub enum PickKind<'tcx> {
76 InherentImplPick(/* Impl */ ast::DefId),
77 ObjectPick(/* Trait */ ast::DefId, /* method_num */ uint, /* real_index */ uint),
78 ExtensionImplPick(/* Impl */ ast::DefId, MethodIndex),
79 TraitPick(/* Trait */ ast::DefId, MethodIndex),
80 WhereClausePick(/* Trait */ ty::PolyTraitRef<'tcx>, MethodIndex),
83 pub type PickResult<'tcx> = Result<Pick<'tcx>, MethodError>;
85 // This is a kind of "abstracted" version of ty::AutoAdjustment. The
86 // difference is that it doesn't embed any regions or other
87 // specifics. The "confirmation" step recreates those details as
90 pub enum PickAdjustment {
91 // Indicates that the source expression should be autoderef'd N times
93 // A = expr | *expr | **expr
96 // Indicates that the source expression should be autoderef'd N
97 // times and then "unsized". This should probably eventually go
98 // away in favor of just coercing method receivers.
100 // A = unsize(expr | *expr | **expr)
101 AutoUnsizeLength(/* number of autoderefs */ uint, /* length*/ uint),
103 // Indicates that an autoref is applied after some number of other adjustments
106 AutoRef(ast::Mutability, Box<PickAdjustment>),
109 pub fn probe<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
111 method_name: ast::Name,
113 call_expr_id: ast::NodeId)
116 debug!("probe(self_ty={}, method_name={}, call_expr_id={})",
117 self_ty.repr(fcx.tcx()),
121 // FIXME(#18741) -- right now, creating the steps involves evaluating the
122 // `*` operator, which registers obligations that then escape into
123 // the global fulfillment context and thus has global
124 // side-effects. This is a bit of a pain to refactor. So just let
125 // it ride, although it's really not great, and in fact could I
126 // think cause spurious errors. Really though this part should
127 // take place in the `fcx.infcx().probe` below.
128 let steps = match create_steps(fcx, span, self_ty) {
129 Some(steps) => steps,
130 None => return Err(NoMatch(Vec::new())),
133 // Create a list of simplified self types, if we can.
134 let mut simplified_steps = Vec::new();
135 for step in steps.iter() {
136 match fast_reject::simplify_type(fcx.tcx(), step.self_ty, true) {
138 Some(simplified_type) => { simplified_steps.push(simplified_type); }
141 let opt_simplified_steps =
142 if simplified_steps.len() < steps.len() {
143 None // failed to convert at least one of the steps
145 Some(simplified_steps)
148 debug!("ProbeContext: steps for self_ty={} are {}",
149 self_ty.repr(fcx.tcx()),
150 steps.repr(fcx.tcx()));
152 // this creates one big transaction so that all type variables etc
153 // that we create during the probe process are removed later
154 let mut dummy = Some((steps, opt_simplified_steps)); // FIXME(#18101) need once closures
155 fcx.infcx().probe(|_| {
156 let (steps, opt_simplified_steps) = dummy.take().unwrap();
157 let mut probe_cx = ProbeContext::new(fcx, span, method_name, steps, opt_simplified_steps);
158 probe_cx.assemble_inherent_candidates();
159 probe_cx.assemble_extension_candidates_for_traits_in_scope(call_expr_id);
164 fn create_steps<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
167 -> Option<Vec<CandidateStep<'tcx>>> {
168 let mut steps = Vec::new();
170 let (fully_dereferenced_ty, dereferences, _) =
172 fcx, span, self_ty, None, NoPreference,
174 let adjustment = AutoDeref(d);
175 steps.push(CandidateStep { self_ty: t, adjustment: adjustment });
176 None::<()> // keep iterating until we can't anymore
179 match fully_dereferenced_ty.sty {
180 ty::ty_vec(elem_ty, Some(len)) => {
181 steps.push(CandidateStep {
182 self_ty: ty::mk_vec(fcx.tcx(), elem_ty, None),
183 adjustment: AutoUnsizeLength(dereferences, len),
186 ty::ty_err => return None,
193 impl<'a,'tcx> ProbeContext<'a,'tcx> {
194 fn new(fcx: &'a FnCtxt<'a,'tcx>,
196 method_name: ast::Name,
197 steps: Vec<CandidateStep<'tcx>>,
198 opt_simplified_steps: Option<Vec<fast_reject::SimplifiedType>>)
199 -> ProbeContext<'a,'tcx>
204 method_name: method_name,
205 inherent_candidates: Vec::new(),
206 extension_candidates: Vec::new(),
207 impl_dups: HashSet::new(),
208 steps: Rc::new(steps),
209 opt_simplified_steps: opt_simplified_steps,
210 static_candidates: Vec::new(),
214 fn tcx(&self) -> &'a ty::ctxt<'tcx> {
218 fn infcx(&self) -> &'a InferCtxt<'a, 'tcx> {
222 ///////////////////////////////////////////////////////////////////////////
223 // CANDIDATE ASSEMBLY
225 fn assemble_inherent_candidates(&mut self) {
226 let steps = self.steps.clone();
227 for step in steps.iter() {
228 self.assemble_probe(step.self_ty);
232 fn assemble_probe(&mut self, self_ty: Ty<'tcx>) {
233 debug!("assemble_probe: self_ty={}",
234 self_ty.repr(self.tcx()));
237 ty::ty_trait(box ref data) => {
238 self.assemble_inherent_candidates_from_object(self_ty, data);
239 self.assemble_inherent_impl_candidates_for_type(data.principal_def_id());
241 ty::ty_enum(did, _) |
242 ty::ty_struct(did, _) |
243 ty::ty_unboxed_closure(did, _, _) => {
244 self.assemble_inherent_impl_candidates_for_type(did);
247 self.assemble_inherent_candidates_from_param(self_ty, p);
254 fn assemble_inherent_impl_candidates_for_type(&mut self, def_id: ast::DefId) {
255 // Read the inherent implementation candidates for this type from the
256 // metadata if necessary.
257 ty::populate_implementations_for_type_if_necessary(self.tcx(), def_id);
259 for impl_infos in self.tcx().inherent_impls.borrow().get(&def_id).iter() {
260 for &impl_def_id in impl_infos.iter() {
261 self.assemble_inherent_impl_probe(impl_def_id);
266 fn assemble_inherent_impl_probe(&mut self, impl_def_id: ast::DefId) {
267 if !self.impl_dups.insert(impl_def_id) {
268 return; // already visited
271 debug!("assemble_inherent_impl_probe {:?}", impl_def_id);
273 let method = match impl_method(self.tcx(), impl_def_id, self.method_name) {
275 None => { return; } // No method with correct name on this impl
278 if !self.has_applicable_self(&*method) {
279 // No receiver declared. Not a candidate.
280 return self.record_static_candidate(ImplSource(impl_def_id));
283 let impl_substs = self.impl_substs(impl_def_id);
285 // Determine the receiver type that the method itself expects.
287 self.xform_self_ty(&method, &impl_substs);
289 self.inherent_candidates.push(Candidate {
290 xform_self_ty: xform_self_ty,
292 kind: InherentImplCandidate(impl_def_id, impl_substs)
296 fn assemble_inherent_candidates_from_object(&mut self,
298 data: &ty::TyTrait<'tcx>) {
299 debug!("assemble_inherent_candidates_from_object(self_ty={})",
300 self_ty.repr(self.tcx()));
302 let tcx = self.tcx();
304 // It is illegal to invoke a method on a trait instance that
305 // refers to the `Self` type. An error will be reported by
306 // `enforce_object_limitations()` if the method refers to the
307 // `Self` type anywhere other than the receiver. Here, we use
308 // a substitution that replaces `Self` with the object type
309 // itself. Hence, a `&self` method will wind up with an
310 // argument type like `&Trait`.
311 let trait_ref = data.principal_trait_ref_with_self_ty(self.tcx(), self_ty);
312 self.elaborate_bounds(&[trait_ref.clone()], false, |this, new_trait_ref, m, method_num| {
313 let new_trait_ref = this.erase_late_bound_regions(&new_trait_ref);
316 traits::get_vtable_index_of_object_method(tcx,
318 new_trait_ref.def_id,
321 let xform_self_ty = this.xform_self_ty(&m, new_trait_ref.substs);
323 this.inherent_candidates.push(Candidate {
324 xform_self_ty: xform_self_ty,
326 kind: ObjectCandidate(new_trait_ref.def_id, method_num, vtable_index)
331 fn assemble_inherent_candidates_from_param(&mut self,
333 param_ty: ty::ParamTy) {
334 // FIXME -- Do we want to commit to this behavior for param bounds?
337 self.fcx.inh.param_env.caller_bounds.predicates
339 .filter_map(|predicate| {
341 ty::Predicate::Trait(ref trait_predicate) => {
342 match trait_predicate.0.trait_ref.self_ty().sty {
343 ty::ty_param(ref p) if *p == param_ty => {
344 Some(trait_predicate.to_poly_trait_ref())
349 ty::Predicate::Equate(..) |
350 ty::Predicate::Projection(..) |
351 ty::Predicate::RegionOutlives(..) |
352 ty::Predicate::TypeOutlives(..) => {
359 self.elaborate_bounds(bounds.as_slice(), true, |this, poly_trait_ref, m, method_num| {
361 this.erase_late_bound_regions(&poly_trait_ref);
364 this.xform_self_ty(&m, trait_ref.substs);
366 debug!("found match: trait_ref={} substs={} m={}",
367 trait_ref.repr(this.tcx()),
368 trait_ref.substs.repr(this.tcx()),
370 assert_eq!(m.generics.types.get_slice(subst::TypeSpace).len(),
371 trait_ref.substs.types.get_slice(subst::TypeSpace).len());
372 assert_eq!(m.generics.regions.get_slice(subst::TypeSpace).len(),
373 trait_ref.substs.regions().get_slice(subst::TypeSpace).len());
374 assert_eq!(m.generics.types.get_slice(subst::SelfSpace).len(),
375 trait_ref.substs.types.get_slice(subst::SelfSpace).len());
376 assert_eq!(m.generics.regions.get_slice(subst::SelfSpace).len(),
377 trait_ref.substs.regions().get_slice(subst::SelfSpace).len());
379 // Because this trait derives from a where-clause, it
380 // should not contain any inference variables or other
381 // artifacts. This means it is safe to put into the
382 // `WhereClauseCandidate` and (eventually) into the
383 // `WhereClausePick`.
384 assert!(trait_ref.substs.types.iter().all(|&t| !ty::type_needs_infer(t)));
386 this.inherent_candidates.push(Candidate {
387 xform_self_ty: xform_self_ty,
389 kind: WhereClauseCandidate(poly_trait_ref, method_num)
394 // Do a search through a list of bounds, using a callback to actually
395 // create the candidates.
396 fn elaborate_bounds<F>(
398 bounds: &[ty::PolyTraitRef<'tcx>],
399 num_includes_types: bool,
403 &mut ProbeContext<'b, 'tcx>,
404 ty::PolyTraitRef<'tcx>,
405 Rc<ty::Method<'tcx>>,
409 debug!("elaborate_bounds(bounds={})", bounds.repr(self.tcx()));
411 let tcx = self.tcx();
412 let mut cache = HashSet::new();
413 for bound_trait_ref in traits::transitive_bounds(tcx, bounds) {
414 // Already visited this trait, skip it.
415 if !cache.insert(bound_trait_ref.def_id()) {
419 let (pos, method) = match trait_method(tcx,
420 bound_trait_ref.def_id(),
422 num_includes_types) {
424 None => { continue; }
427 if !self.has_applicable_self(&*method) {
428 self.record_static_candidate(TraitSource(bound_trait_ref.def_id()));
430 mk_cand(self, bound_trait_ref, method, pos);
435 fn assemble_extension_candidates_for_traits_in_scope(&mut self,
436 expr_id: ast::NodeId)
438 let mut duplicates = HashSet::new();
439 let opt_applicable_traits = self.fcx.ccx.trait_map.get(&expr_id);
440 for applicable_traits in opt_applicable_traits.into_iter() {
441 for &trait_did in applicable_traits.iter() {
442 if duplicates.insert(trait_did) {
443 self.assemble_extension_candidates_for_trait(trait_did);
449 fn assemble_extension_candidates_for_trait(&mut self,
450 trait_def_id: ast::DefId) {
451 debug!("assemble_extension_candidates_for_trait(trait_def_id={})",
452 trait_def_id.repr(self.tcx()));
454 // Check whether `trait_def_id` defines a method with suitable name:
456 ty::trait_items(self.tcx(), trait_def_id);
459 .position(|item| item.name() == self.method_name);
460 let matching_index = match matching_index {
464 let method = match (&*trait_items)[matching_index].as_opt_method() {
469 // Check whether `trait_def_id` defines a method with suitable name:
470 if !self.has_applicable_self(&*method) {
471 debug!("method has inapplicable self");
472 return self.record_static_candidate(TraitSource(trait_def_id));
475 self.assemble_extension_candidates_for_trait_impls(trait_def_id,
479 self.assemble_unboxed_closure_candidates(trait_def_id,
483 self.assemble_projection_candidates(trait_def_id,
487 self.assemble_where_clause_candidates(trait_def_id,
492 fn assemble_extension_candidates_for_trait_impls(&mut self,
493 trait_def_id: ast::DefId,
494 method: Rc<ty::Method<'tcx>>,
497 ty::populate_implementations_for_trait_if_necessary(self.tcx(),
500 let trait_impls = self.tcx().trait_impls.borrow();
501 let impl_def_ids = match trait_impls.get(&trait_def_id) {
503 Some(impls) => impls,
506 for &impl_def_id in impl_def_ids.borrow().iter() {
507 debug!("assemble_extension_candidates_for_trait_impl: trait_def_id={} impl_def_id={}",
508 trait_def_id.repr(self.tcx()),
509 impl_def_id.repr(self.tcx()));
511 if !self.impl_can_possibly_match(impl_def_id) {
515 let impl_substs = self.impl_substs(impl_def_id);
517 debug!("impl_substs={}", impl_substs.repr(self.tcx()));
520 ty::impl_trait_ref(self.tcx(), impl_def_id)
521 .unwrap() // we know this is a trait impl
522 .subst(self.tcx(), &impl_substs);
524 debug!("impl_trait_ref={}", impl_trait_ref.repr(self.tcx()));
526 // Determine the receiver type that the method itself expects.
528 self.xform_self_ty(&method, impl_trait_ref.substs);
530 debug!("xform_self_ty={}", xform_self_ty.repr(self.tcx()));
532 self.extension_candidates.push(Candidate {
533 xform_self_ty: xform_self_ty,
534 method_ty: method.clone(),
535 kind: ExtensionImplCandidate(impl_def_id, impl_trait_ref, impl_substs, method_index)
540 fn impl_can_possibly_match(&self, impl_def_id: ast::DefId) -> bool {
541 let simplified_steps = match self.opt_simplified_steps {
542 Some(ref simplified_steps) => simplified_steps,
543 None => { return true; }
546 let impl_type = ty::lookup_item_type(self.tcx(), impl_def_id);
547 let impl_simplified_type =
548 match fast_reject::simplify_type(self.tcx(), impl_type.ty, false) {
549 Some(simplified_type) => simplified_type,
550 None => { return true; }
553 simplified_steps.contains(&impl_simplified_type)
556 fn assemble_unboxed_closure_candidates(&mut self,
557 trait_def_id: ast::DefId,
558 method_ty: Rc<ty::Method<'tcx>>,
561 // Check if this is one of the Fn,FnMut,FnOnce traits.
562 let tcx = self.tcx();
563 let kind = if Some(trait_def_id) == tcx.lang_items.fn_trait() {
564 ty::FnUnboxedClosureKind
565 } else if Some(trait_def_id) == tcx.lang_items.fn_mut_trait() {
566 ty::FnMutUnboxedClosureKind
567 } else if Some(trait_def_id) == tcx.lang_items.fn_once_trait() {
568 ty::FnOnceUnboxedClosureKind
573 // Check if there is an unboxed-closure self-type in the list of receivers.
574 // If so, add "synthetic impls".
575 let steps = self.steps.clone();
576 for step in steps.iter() {
577 let (closure_def_id, _, _) = match step.self_ty.sty {
578 ty::ty_unboxed_closure(a, b, ref c) => (a, b, c),
582 let unboxed_closures = self.fcx.inh.unboxed_closures.borrow();
583 let closure_data = match unboxed_closures.get(&closure_def_id) {
586 self.tcx().sess.span_bug(
588 &format!("No entry for unboxed closure: {}",
589 closure_def_id.repr(self.tcx()))[]);
593 // this closure doesn't implement the right kind of `Fn` trait
594 if closure_data.kind != kind {
598 // create some substitutions for the argument/return type;
599 // for the purposes of our method lookup, we only take
600 // receiver type into account, so we can just substitute
601 // fresh types here to use during substitution and subtyping.
602 let trait_def = ty::lookup_trait_def(self.tcx(), trait_def_id);
603 let substs = self.infcx().fresh_substs_for_trait(self.span,
607 let xform_self_ty = self.xform_self_ty(&method_ty, &substs);
608 self.inherent_candidates.push(Candidate {
609 xform_self_ty: xform_self_ty,
610 method_ty: method_ty.clone(),
611 kind: UnboxedClosureCandidate(trait_def_id, method_index)
616 fn assemble_projection_candidates(&mut self,
617 trait_def_id: ast::DefId,
618 method: Rc<ty::Method<'tcx>>,
621 debug!("assemble_projection_candidates(\
625 trait_def_id.repr(self.tcx()),
626 method.repr(self.tcx()),
629 for step in self.steps.iter() {
630 debug!("assemble_projection_candidates: step={}",
631 step.repr(self.tcx()));
633 let projection_trait_ref = match step.self_ty.sty {
634 ty::ty_projection(ref data) => &data.trait_ref,
638 debug!("assemble_projection_candidates: projection_trait_ref={}",
639 projection_trait_ref.repr(self.tcx()));
641 let trait_def = ty::lookup_trait_def(self.tcx(), projection_trait_ref.def_id);
642 let bounds = trait_def.generics.to_bounds(self.tcx(), projection_trait_ref.substs);
643 let predicates = bounds.predicates.into_vec();
644 debug!("assemble_projection_candidates: predicates={}",
645 predicates.repr(self.tcx()));
647 traits::elaborate_predicates(self.tcx(), predicates)
648 .filter_map(|p| p.to_opt_poly_trait_ref())
649 .filter(|b| b.def_id() == trait_def_id)
651 let bound = self.erase_late_bound_regions(&poly_bound);
653 debug!("assemble_projection_candidates: projection_trait_ref={} bound={}",
654 projection_trait_ref.repr(self.tcx()),
655 bound.repr(self.tcx()));
657 if self.infcx().can_equate(&step.self_ty, &bound.self_ty()).is_ok() {
658 let xform_self_ty = self.xform_self_ty(&method, bound.substs);
660 debug!("assemble_projection_candidates: bound={} xform_self_ty={}",
661 bound.repr(self.tcx()),
662 xform_self_ty.repr(self.tcx()));
664 self.extension_candidates.push(Candidate {
665 xform_self_ty: xform_self_ty,
666 method_ty: method.clone(),
667 kind: ProjectionCandidate(trait_def_id, method_index)
674 fn assemble_where_clause_candidates(&mut self,
675 trait_def_id: ast::DefId,
676 method_ty: Rc<ty::Method<'tcx>>,
679 debug!("assemble_where_clause_candidates(trait_def_id={})",
680 trait_def_id.repr(self.tcx()));
682 let caller_predicates =
683 self.fcx.inh.param_env.caller_bounds.predicates.as_slice().to_vec();
684 for poly_bound in traits::elaborate_predicates(self.tcx(), caller_predicates)
685 .filter_map(|p| p.to_opt_poly_trait_ref())
686 .filter(|b| b.def_id() == trait_def_id)
688 let bound = self.erase_late_bound_regions(&poly_bound);
689 let xform_self_ty = self.xform_self_ty(&method_ty, bound.substs);
691 debug!("assemble_where_clause_candidates: bound={} xform_self_ty={}",
692 bound.repr(self.tcx()),
693 xform_self_ty.repr(self.tcx()));
695 self.extension_candidates.push(Candidate {
696 xform_self_ty: xform_self_ty,
697 method_ty: method_ty.clone(),
698 kind: WhereClauseCandidate(poly_bound, method_index)
703 ///////////////////////////////////////////////////////////////////////////
706 fn pick(mut self) -> PickResult<'tcx> {
707 let steps = self.steps.clone();
709 for step in steps.iter() {
710 match self.pick_step(step) {
718 Err(NoMatch(self.static_candidates))
721 fn pick_step(&mut self, step: &CandidateStep<'tcx>) -> Option<PickResult<'tcx>> {
722 debug!("pick_step: step={}", step.repr(self.tcx()));
724 if ty::type_is_error(step.self_ty) {
728 match self.pick_by_value_method(step) {
729 Some(result) => return Some(result),
733 self.pick_autorefd_method(step)
736 fn pick_by_value_method(&mut self,
737 step: &CandidateStep<'tcx>)
738 -> Option<PickResult<'tcx>>
741 * For each type `T` in the step list, this attempts to find a
742 * method where the (transformed) self type is exactly `T`. We
743 * do however do one transformation on the adjustment: if we
744 * are passing a region pointer in, we will potentially
745 * *reborrow* it to a shorter lifetime. This allows us to
746 * transparently pass `&mut` pointers, in particular, without
747 * consuming them for their entire lifetime.
750 let adjustment = match step.adjustment {
751 AutoDeref(d) => consider_reborrow(step.self_ty, d),
752 AutoUnsizeLength(..) | AutoRef(..) => step.adjustment.clone(),
755 return self.pick_method(step.self_ty).map(|r| self.adjust(r, adjustment.clone()));
757 fn consider_reborrow(ty: Ty, d: uint) -> PickAdjustment {
758 // Insert a `&*` or `&mut *` if this is a reference type:
760 ty::ty_rptr(_, ref mt) => AutoRef(mt.mutbl, box AutoDeref(d+1)),
766 fn pick_autorefd_method(&mut self,
767 step: &CandidateStep<'tcx>)
768 -> Option<PickResult<'tcx>>
770 let tcx = self.tcx();
771 self.search_mutabilities(
772 |m| AutoRef(m, box step.adjustment.clone()),
773 |m,r| ty::mk_rptr(tcx, tcx.mk_region(r), ty::mt {ty:step.self_ty, mutbl:m}))
776 fn search_mutabilities<F, G>(&mut self,
777 mut mk_adjustment: F,
778 mut mk_autoref_ty: G)
779 -> Option<PickResult<'tcx>> where
780 F: FnMut(ast::Mutability) -> PickAdjustment,
781 G: FnMut(ast::Mutability, ty::Region) -> Ty<'tcx>,
783 // In general, during probing we erase regions. See
784 // `impl_self_ty()` for an explanation.
785 let region = ty::ReStatic;
787 // Search through mutabilities in order to find one where pick works:
788 [ast::MutImmutable, ast::MutMutable]
791 let autoref_ty = mk_autoref_ty(m, region);
792 self.pick_method(autoref_ty)
793 .map(|r| self.adjust(r, mk_adjustment(m)))
800 result: PickResult<'tcx>,
801 adjustment: PickAdjustment)
802 -> PickResult<'tcx> {
806 pick.adjustment = adjustment;
812 fn pick_method(&mut self, self_ty: Ty<'tcx>) -> Option<PickResult<'tcx>> {
813 debug!("pick_method(self_ty={})", self.infcx().ty_to_string(self_ty));
815 debug!("searching inherent candidates");
816 match self.consider_candidates(self_ty, &self.inherent_candidates[]) {
823 debug!("searching extension candidates");
824 self.consider_candidates(self_ty, &self.extension_candidates[])
827 fn consider_candidates(&self,
829 probes: &[Candidate<'tcx>])
830 -> Option<PickResult<'tcx>> {
831 let mut applicable_candidates: Vec<_> =
833 .filter(|&probe| self.consider_probe(self_ty, probe))
836 debug!("applicable_candidates: {}", applicable_candidates.repr(self.tcx()));
838 if applicable_candidates.len() > 1 {
839 match self.collapse_candidates_to_trait_pick(&applicable_candidates[]) {
840 Some(pick) => { return Some(Ok(pick)); }
845 if applicable_candidates.len() > 1 {
846 let sources = probes.iter().map(|p| p.to_source()).collect();
847 return Some(Err(Ambiguity(sources)));
850 applicable_candidates.pop().map(|probe| {
851 let pick = probe.to_unadjusted_pick();
856 fn consider_probe(&self, self_ty: Ty<'tcx>, probe: &Candidate<'tcx>) -> bool {
857 debug!("consider_probe: self_ty={} probe={}",
858 self_ty.repr(self.tcx()),
859 probe.repr(self.tcx()));
861 self.infcx().probe(|_| {
862 // First check that the self type can be related.
863 match self.make_sub_ty(self_ty, probe.xform_self_ty) {
866 debug!("--> cannot relate self-types");
871 // If so, impls may carry other conditions (e.g., where
872 // clauses) that must be considered. Make sure that those
873 // match as well (or at least may match, sometimes we
874 // don't have enough information to fully evaluate).
876 InherentImplCandidate(impl_def_id, ref substs) |
877 ExtensionImplCandidate(impl_def_id, _, ref substs, _) => {
878 let selcx = &mut traits::SelectionContext::new(self.infcx(), self.fcx);
879 let cause = traits::ObligationCause::misc(self.span, self.fcx.body_id);
881 // Check whether the impl imposes obligations we have to worry about.
882 let impl_generics = ty::lookup_item_type(self.tcx(), impl_def_id).generics;
883 let impl_bounds = impl_generics.to_bounds(self.tcx(), substs);
884 let traits::Normalized { value: impl_bounds,
885 obligations: norm_obligations } =
886 traits::normalize(selcx, cause.clone(), &impl_bounds);
888 // Convert the bounds into obligations.
890 traits::predicates_for_generics(self.tcx(),
893 debug!("impl_obligations={}", obligations.repr(self.tcx()));
895 // Evaluate those obligations to see if they might possibly hold.
896 obligations.all(|o| selcx.evaluate_obligation(o)) &&
897 norm_obligations.iter().all(|o| selcx.evaluate_obligation(o))
900 ProjectionCandidate(..) |
901 ObjectCandidate(..) |
902 UnboxedClosureCandidate(..) |
903 WhereClauseCandidate(..) => {
904 // These have no additional conditions to check.
911 /// Sometimes we get in a situation where we have multiple probes that are all impls of the
912 /// same trait, but we don't know which impl to use. In this case, since in all cases the
913 /// external interface of the method can be determined from the trait, it's ok not to decide.
914 /// We can basically just collapse all of the probes for various impls into one where-clause
915 /// probe. This will result in a pending obligation so when more type-info is available we can
916 /// make the final decision.
918 /// Example (`src/test/run-pass/method-two-trait-defer-resolution-1.rs`):
921 /// trait Foo { ... }
922 /// impl Foo for Vec<int> { ... }
923 /// impl Foo for Vec<uint> { ... }
926 /// Now imagine the receiver is `Vec<_>`. It doesn't really matter at this time which impl we
927 /// use, so it's ok to just commit to "using the method from the trait Foo".
928 fn collapse_candidates_to_trait_pick(&self,
929 probes: &[&Candidate<'tcx>])
930 -> Option<Pick<'tcx>> {
931 // Do all probes correspond to the same trait?
932 let trait_data = match probes[0].to_trait_data() {
936 if probes[1..].iter().any(|p| p.to_trait_data() != Some(trait_data)) {
940 // If so, just use this trait and call it a day.
941 let (trait_def_id, method_num) = trait_data;
942 let method_ty = probes[0].method_ty.clone();
944 method_ty: method_ty,
945 adjustment: AutoDeref(0),
946 kind: TraitPick(trait_def_id, method_num)
950 ///////////////////////////////////////////////////////////////////////////
953 fn make_sub_ty(&self, sub: Ty<'tcx>, sup: Ty<'tcx>) -> infer::ures<'tcx> {
954 self.infcx().sub_types(false, infer::Misc(DUMMY_SP), sub, sup)
957 fn has_applicable_self(&self, method: &ty::Method) -> bool {
958 // "fast track" -- check for usage of sugar
959 match method.explicit_self {
960 ty::StaticExplicitSelfCategory => {
963 ty::ByValueExplicitSelfCategory |
964 ty::ByReferenceExplicitSelfCategory(..) |
965 ty::ByBoxExplicitSelfCategory => {
970 // FIXME -- check for types that deref to `Self`,
971 // like `Rc<Self>` and so on.
973 // Note also that the current code will break if this type
974 // includes any of the type parameters defined on the method
975 // -- but this could be overcome.
979 fn record_static_candidate(&mut self, source: CandidateSource) {
980 self.static_candidates.push(source);
983 fn xform_self_ty(&self,
984 method: &Rc<ty::Method<'tcx>>,
985 substs: &subst::Substs<'tcx>)
988 debug!("xform_self_ty(self_ty={}, substs={})",
989 method.fty.sig.0.inputs[0].repr(self.tcx()),
990 substs.repr(self.tcx()));
992 assert!(!substs.has_escaping_regions());
994 // It is possible for type parameters or early-bound lifetimes
995 // to appear in the signature of `self`. The substitutions we
996 // are given do not include type/lifetime parameters for the
997 // method yet. So create fresh variables here for those too,
999 assert_eq!(substs.types.len(subst::FnSpace), 0);
1000 assert_eq!(substs.regions().len(subst::FnSpace), 0);
1001 let mut substs = substs;
1004 !method.generics.types.is_empty_in(subst::FnSpace) ||
1005 !method.generics.regions.is_empty_in(subst::FnSpace)
1008 self.infcx().next_ty_vars(
1009 method.generics.types.len(subst::FnSpace));
1011 // In general, during probe we erase regions. See
1012 // `impl_self_ty()` for an explanation.
1013 let method_regions =
1014 method.generics.regions.get_slice(subst::FnSpace)
1016 .map(|_| ty::ReStatic)
1019 placeholder = (*substs).clone().with_method(method_types, method_regions);
1020 substs = &placeholder;
1023 // Erase any late-bound regions from the method and substitute
1024 // in the values from the substitution.
1025 let xform_self_ty = method.fty.sig.input(0);
1026 let xform_self_ty = self.erase_late_bound_regions(&xform_self_ty);
1027 let xform_self_ty = xform_self_ty.subst(self.tcx(), substs);
1032 fn impl_substs(&self,
1033 impl_def_id: ast::DefId)
1034 -> subst::Substs<'tcx>
1036 let impl_pty = ty::lookup_item_type(self.tcx(), impl_def_id);
1039 impl_pty.generics.types.map(
1040 |_| self.infcx().next_ty_var());
1042 let region_placeholders =
1043 impl_pty.generics.regions.map(
1044 |_| ty::ReStatic); // see erase_late_bound_regions() for an expl of why 'static
1046 subst::Substs::new(type_vars, region_placeholders)
1049 /// Replace late-bound-regions bound by `value` with `'static` using
1050 /// `ty::erase_late_bound_regions`.
1052 /// This is only a reasonable thing to do during the *probe* phase, not the *confirm* phase, of
1053 /// method matching. It is reasonable during the probe phase because we don't consider region
1054 /// relationships at all. Therefore, we can just replace all the region variables with 'static
1055 /// rather than creating fresh region variables. This is nice for two reasons:
1057 /// 1. Because the numbers of the region variables would otherwise be fairly unique to this
1058 /// particular method call, it winds up creating fewer types overall, which helps for memory
1059 /// usage. (Admittedly, this is a rather small effect, though measureable.)
1061 /// 2. It makes it easier to deal with higher-ranked trait bounds, because we can replace any
1062 /// late-bound regions with 'static. Otherwise, if we were going to replace late-bound
1063 /// regions with actual region variables as is proper, we'd have to ensure that the same
1064 /// region got replaced with the same variable, which requires a bit more coordination
1065 /// and/or tracking the substitution and
1067 fn erase_late_bound_regions<T>(&self, value: &ty::Binder<T>) -> T
1068 where T : TypeFoldable<'tcx> + Repr<'tcx>
1070 ty::erase_late_bound_regions(self.tcx(), value)
1074 fn impl_method<'tcx>(tcx: &ty::ctxt<'tcx>,
1075 impl_def_id: ast::DefId,
1076 method_name: ast::Name)
1077 -> Option<Rc<ty::Method<'tcx>>>
1079 let impl_items = tcx.impl_items.borrow();
1080 let impl_items = impl_items.get(&impl_def_id).unwrap();
1083 .map(|&did| ty::impl_or_trait_item(tcx, did.def_id()))
1084 .find(|m| m.name() == method_name)
1085 .and_then(|item| item.as_opt_method())
1088 /// Find method with name `method_name` defined in `trait_def_id` and return it, along with its
1089 /// index (or `None`, if no such method).
1090 fn trait_method<'tcx>(tcx: &ty::ctxt<'tcx>,
1091 trait_def_id: ast::DefId,
1092 method_name: ast::Name,
1093 num_includes_types: bool)
1094 -> Option<(uint, Rc<ty::Method<'tcx>>)>
1096 let trait_items = ty::trait_items(tcx, trait_def_id);
1097 debug!("trait_method; items: {:?}", trait_items);
1101 num_includes_types || match *item {
1102 &ty::MethodTraitItem(_) => true,
1103 &ty::TypeTraitItem(_) => false
1106 .find(|&(_, ref item)| item.name() == method_name)
1107 .and_then(|(idx, item)| item.as_opt_method().map(|m| (idx, m)))
1110 impl<'tcx> Candidate<'tcx> {
1111 fn to_unadjusted_pick(&self) -> Pick<'tcx> {
1113 method_ty: self.method_ty.clone(),
1114 adjustment: AutoDeref(0),
1115 kind: match self.kind {
1116 InherentImplCandidate(def_id, _) => {
1117 InherentImplPick(def_id)
1119 ObjectCandidate(def_id, method_num, real_index) => {
1120 ObjectPick(def_id, method_num, real_index)
1122 ExtensionImplCandidate(def_id, _, _, index) => {
1123 ExtensionImplPick(def_id, index)
1125 UnboxedClosureCandidate(trait_def_id, index) => {
1126 TraitPick(trait_def_id, index)
1128 WhereClauseCandidate(ref trait_ref, index) => {
1129 // Only trait derived from where-clauses should
1130 // appear here, so they should not contain any
1131 // inference variables or other artifacts. This
1132 // means they are safe to put into the
1133 // `WhereClausePick`.
1134 assert!(trait_ref.substs().types.iter().all(|&t| !ty::type_needs_infer(t)));
1136 WhereClausePick((*trait_ref).clone(), index)
1138 ProjectionCandidate(def_id, index) => {
1139 TraitPick(def_id, index)
1145 fn to_source(&self) -> CandidateSource {
1147 InherentImplCandidate(def_id, _) => ImplSource(def_id),
1148 ObjectCandidate(def_id, _, _) => TraitSource(def_id),
1149 ExtensionImplCandidate(def_id, _, _, _) => ImplSource(def_id),
1150 UnboxedClosureCandidate(trait_def_id, _) => TraitSource(trait_def_id),
1151 WhereClauseCandidate(ref trait_ref, _) => TraitSource(trait_ref.def_id()),
1152 ProjectionCandidate(trait_def_id, _) => TraitSource(trait_def_id),
1156 fn to_trait_data(&self) -> Option<(ast::DefId,MethodIndex)> {
1158 InherentImplCandidate(..) |
1159 ObjectCandidate(..) => {
1162 UnboxedClosureCandidate(trait_def_id, method_num) => {
1163 Some((trait_def_id, method_num))
1165 ExtensionImplCandidate(_, ref trait_ref, _, method_num) => {
1166 Some((trait_ref.def_id, method_num))
1168 WhereClauseCandidate(ref trait_ref, method_num) => {
1169 Some((trait_ref.def_id(), method_num))
1171 ProjectionCandidate(trait_def_id, method_num) => {
1172 Some((trait_def_id, method_num))
1178 impl<'tcx> Repr<'tcx> for Candidate<'tcx> {
1179 fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1180 format!("Candidate(xform_self_ty={}, kind={})",
1181 self.xform_self_ty.repr(tcx),
1182 self.kind.repr(tcx))
1186 impl<'tcx> Repr<'tcx> for CandidateKind<'tcx> {
1187 fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1189 InherentImplCandidate(ref a, ref b) =>
1190 format!("InherentImplCandidate({},{})", a.repr(tcx), b.repr(tcx)),
1191 ObjectCandidate(a, b, c) =>
1192 format!("ObjectCandidate({},{},{})", a.repr(tcx), b, c),
1193 ExtensionImplCandidate(ref a, ref b, ref c, ref d) =>
1194 format!("ExtensionImplCandidate({},{},{},{})", a.repr(tcx), b.repr(tcx),
1196 UnboxedClosureCandidate(ref a, ref b) =>
1197 format!("UnboxedClosureCandidate({},{})", a.repr(tcx), b),
1198 WhereClauseCandidate(ref a, ref b) =>
1199 format!("WhereClauseCandidate({},{})", a.repr(tcx), b),
1200 ProjectionCandidate(ref a, ref b) =>
1201 format!("ProjectionCandidate({},{})", a.repr(tcx), b),
1206 impl<'tcx> Repr<'tcx> for CandidateStep<'tcx> {
1207 fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1208 format!("CandidateStep({},{:?})",
1209 self.self_ty.repr(tcx),
1214 impl<'tcx> Repr<'tcx> for PickAdjustment {
1215 fn repr(&self, _tcx: &ty::ctxt) -> String {
1216 format!("{:?}", self)
1220 impl<'tcx> Repr<'tcx> for PickKind<'tcx> {
1221 fn repr(&self, _tcx: &ty::ctxt) -> String {
1222 format!("{:?}", self)
1226 impl<'tcx> Repr<'tcx> for Pick<'tcx> {
1227 fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1228 format!("Pick(method_ty={}, adjustment={:?}, kind={:?})",
1229 self.method_ty.repr(tcx),