1 // Copyright 2012-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.
15 Method lookup can be rather complex due to the interaction of a number
16 of factors, such as self types, autoderef, trait lookup, etc. The
17 algorithm is divided into two parts: candidate collection and
20 ## Candidate collection
22 A `Candidate` is a method item that might plausibly be the method
23 being invoked. Candidates are grouped into two kinds, inherent and
24 extension. Inherent candidates are those that are derived from the
25 type of the receiver itself. So, if you have a receiver of some
26 nominal type `Foo` (e.g., a struct), any methods defined within an
27 impl like `impl Foo` are inherent methods. Nothing needs to be
28 imported to use an inherent method, they are associated with the type
29 itself (note that inherent impls can only be defined in the same
30 module as the type itself).
32 Inherent candidates are not always derived from impls. If you have a
33 trait instance, such as a value of type `Box<ToStr>`, then the trait
34 methods (`to_str()`, in this case) are inherently associated with it.
35 Another case is type parameters, in which case the methods of their
38 Extension candidates are derived from imported traits. If I have the
39 trait `ToStr` imported, and I call `to_str()` on a value of type `T`,
40 then we will go off to find out whether there is an impl of `ToStr`
41 for `T`. These kinds of method calls are called "extension methods".
42 They can be defined in any module, not only the one that defined `T`.
43 Furthermore, you must import the trait to call such a method.
45 For better or worse, we currently give weight to inherent methods over
46 extension methods during candidate selection (below).
48 ## Candidate selection
50 Once we know the set of candidates, we can go off and try to select
51 which one is actually being called. We do this by taking the type of
52 the receiver, let's call it R, and checking whether it matches against
53 the expected receiver type for each of the collected candidates. We
54 first check for inherent candidates and see whether we get exactly one
55 match (zero means keep searching, more than one is an error). If so,
56 we return that as the candidate. Otherwise we search the extension
57 candidates in the same way.
59 If find no matching candidate at all, we proceed to auto-deref the
60 receiver type and search again. We keep doing that until we cannot
61 auto-deref any longer. At each step, we also check for candidates
62 based on "autoptr", which if the current type is `T`, checks for `&mut
63 T`, `&const T`, and `&T` receivers. Finally, at the very end, we will
64 also try autoslice, which converts `~[]` to `&[]` (there is no point
65 at trying autoslice earlier, because no autoderefable type is also
70 You might wonder why we first collect the candidates and then select.
71 Both the inherent candidate collection and the candidate selection
72 proceed by progressively deref'ing the receiver type, after all. The
73 answer is that two phases are needed to elegantly deal with explicit
74 self. After all, if there is an impl for the type `Foo`, it can
75 define a method with the type `Box<self>`, which means that it expects a
76 receiver of type `Box<Foo>`. If we have a receiver of type `Box<Foo>`, but we
77 waited to search for that impl until we have deref'd the `Box` away and
78 obtained the type `Foo`, we would never match this method.
84 use middle::subst::Subst;
87 use middle::typeck::astconv::AstConv;
88 use middle::typeck::check::{FnCtxt, PreferMutLvalue, impl_self_ty};
89 use middle::typeck::check;
90 use middle::typeck::infer;
91 use middle::typeck::MethodCallee;
92 use middle::typeck::{MethodOrigin, MethodParam};
93 use middle::typeck::{MethodStatic, MethodObject};
94 use middle::typeck::{param_index};
95 use middle::typeck::check::regionmanip::replace_late_bound_regions_in_fn_sig;
96 use util::common::indenter;
98 use util::ppaux::Repr;
100 use std::collections::HashSet;
102 use syntax::ast::{DefId, SelfValue, SelfRegion};
103 use syntax::ast::{SelfUniq, SelfStatic};
104 use syntax::ast::{MutMutable, MutImmutable};
106 use syntax::codemap::Span;
107 use syntax::parse::token;
109 #[deriving(PartialEq)]
110 pub enum CheckTraitsFlag {
112 CheckTraitsAndInherentMethods,
115 #[deriving(PartialEq)]
116 pub enum AutoderefReceiverFlag {
118 DontAutoderefReceiver,
121 #[deriving(PartialEq)]
122 pub enum StaticMethodsFlag {
130 // In a call `a.b::<X, Y, ...>(...)`:
131 expr: &ast::Expr, // The expression `a.b(...)`.
132 self_expr: &'a ast::Expr, // The expression `a`.
133 m_name: ast::Name, // The name `b`.
134 self_ty: ty::t, // The type of `a`.
135 supplied_tps: &'a [ty::t], // The list of types X, Y, ... .
136 deref_args: check::DerefArgs, // Whether we autopointer first.
137 check_traits: CheckTraitsFlag, // Whether we check traits only.
138 autoderef_receiver: AutoderefReceiverFlag,
139 report_statics: StaticMethodsFlag)
140 -> Option<MethodCallee> {
141 let mut lcx = LookupContext {
144 self_expr: Some(self_expr),
146 supplied_tps: supplied_tps,
147 impl_dups: HashSet::new(),
148 inherent_candidates: Vec::new(),
149 extension_candidates: Vec::new(),
150 deref_args: deref_args,
151 check_traits: check_traits,
152 autoderef_receiver: autoderef_receiver,
153 report_statics: report_statics,
156 debug!("method lookup(self_ty={}, expr={}, self_expr={})",
157 self_ty.repr(fcx.tcx()), expr.repr(fcx.tcx()),
158 self_expr.repr(fcx.tcx()));
160 debug!("searching inherent candidates");
161 lcx.push_inherent_candidates(self_ty);
162 let mme = lcx.search(self_ty);
167 debug!("searching extension candidates");
168 lcx.reset_candidates();
169 lcx.push_bound_candidates(self_ty, None);
170 lcx.push_extension_candidates(expr.id);
174 pub fn lookup_in_trait<'a>(
177 // In a call `a.b::<X, Y, ...>(...)`:
178 span: Span, // The expression `a.b(...)`'s span.
179 self_expr: Option<&'a ast::Expr>, // The expression `a`, if available.
180 m_name: ast::Name, // The name `b`.
181 trait_did: DefId, // The trait to limit the lookup to.
182 self_ty: ty::t, // The type of `a`.
183 supplied_tps: &'a [ty::t], // The list of types X, Y, ... .
184 autoderef_receiver: AutoderefReceiverFlag,
185 report_statics: StaticMethodsFlag)
186 -> Option<MethodCallee> {
187 let mut lcx = LookupContext {
190 self_expr: self_expr,
192 supplied_tps: supplied_tps,
193 impl_dups: HashSet::new(),
194 inherent_candidates: Vec::new(),
195 extension_candidates: Vec::new(),
196 deref_args: check::DoDerefArgs,
197 check_traits: CheckTraitsOnly,
198 autoderef_receiver: autoderef_receiver,
199 report_statics: report_statics,
202 debug!("method lookup_in_trait(self_ty={}, self_expr={})",
203 self_ty.repr(fcx.tcx()), self_expr.map(|e| e.repr(fcx.tcx())));
205 lcx.push_bound_candidates(self_ty, Some(trait_did));
206 lcx.push_extension_candidate(trait_did);
210 // Determine the index of a method in the list of all methods belonging
211 // to a trait and its supertraits.
212 fn get_method_index(tcx: &ty::ctxt,
213 trait_ref: &TraitRef,
214 subtrait: Rc<TraitRef>,
215 n_method: uint) -> uint {
216 // We need to figure the "real index" of the method in a
217 // listing of all the methods of an object. We do this by
218 // iterating down the supertraits of the object's trait until
219 // we find the trait the method came from, counting up the
220 // methods from them.
221 let mut method_count = 0;
222 ty::each_bound_trait_and_supertraits(tcx, &[subtrait], |bound_ref| {
223 if bound_ref.def_id == trait_ref.def_id { false }
225 method_count += ty::trait_methods(tcx, bound_ref.def_id).len();
229 method_count + n_method
232 fn construct_transformed_self_ty_for_object(
235 trait_def_id: ast::DefId,
236 rcvr_substs: &subst::Substs,
237 method_ty: &ty::Method)
241 * This is a bit tricky. We have a match against a trait method
242 * being invoked on an object, and we want to generate the
243 * self-type. As an example, consider a trait
246 * fn r_method<'a>(&'a self);
247 * fn u_method(Box<self>);
250 * Now, assuming that `r_method` is being called, we want the
251 * result to be `&'a Foo`. Assuming that `u_method` is being
252 * called, we want the result to be `Box<Foo>`. Of course,
253 * this transformation has already been done as part of
254 * `method_ty.fty.sig.inputs[0]`, but there the type
255 * is expressed in terms of `Self` (i.e., `&'a Self`, `Box<Self>`).
256 * Because objects are not standalone types, we can't just substitute
257 * `s/Self/Foo/`, so we must instead perform this kind of hokey
261 let mut obj_substs = rcvr_substs.clone();
263 // The subst we get in has Err as the "Self" type. For an object
264 // type, we don't put any type into the Self paramspace, so let's
265 // make a copy of rcvr_substs that has the Self paramspace empty.
266 obj_substs.types.get_mut_vec(subst::SelfSpace).pop().unwrap();
268 match method_ty.explicit_self {
270 tcx.sess.span_bug(span, "static method for object type receiver");
273 ty::mk_err() // error reported in `enforce_object_limitations()`
275 ast::SelfRegion(..) | ast::SelfUniq => {
276 let transformed_self_ty = *method_ty.fty.sig.inputs.get(0);
277 match ty::get(transformed_self_ty).sty {
278 ty::ty_rptr(r, mt) => { // must be SelfRegion
279 let r = r.subst(tcx, rcvr_substs); // handle Early-Bound lifetime
280 ty::mk_trait(tcx, trait_def_id, obj_substs,
281 RegionTraitStore(r, mt.mutbl),
282 ty::empty_builtin_bounds())
284 ty::ty_uniq(_) => { // must be SelfUniq
285 ty::mk_trait(tcx, trait_def_id, obj_substs,
287 ty::empty_builtin_bounds())
290 tcx.sess.span_bug(span,
291 format!("'impossible' transformed_self_ty: {}",
292 transformed_self_ty.repr(tcx)).as_slice());
299 struct LookupContext<'a> {
303 // The receiver to the method call. Only `None` in the case of
304 // an overloaded autoderef, where the receiver may be an intermediate
305 // state like "the expression `x` when it has been autoderef'd
307 self_expr: Option<&'a ast::Expr>,
310 supplied_tps: &'a [ty::t],
311 impl_dups: HashSet<DefId>,
312 inherent_candidates: Vec<Candidate>,
313 extension_candidates: Vec<Candidate>,
314 deref_args: check::DerefArgs,
315 check_traits: CheckTraitsFlag,
316 autoderef_receiver: AutoderefReceiverFlag,
317 report_statics: StaticMethodsFlag,
321 * A potential method that might be called, assuming the receiver
322 * is of a suitable type.
326 rcvr_match_condition: RcvrMatchCondition,
327 rcvr_substs: subst::Substs,
328 method_ty: Rc<ty::Method>,
329 origin: MethodOrigin,
332 /// This type represents the conditions under which the receiver is
333 /// considered to "match" a given method candidate. Typically the test
334 /// is whether the receiver is of a particular type. However, this
335 /// type is the type of the receiver *after accounting for the
336 /// method's self type* (e.g., if the method is an `Box<self>` method, we
337 /// have *already verified* that the receiver is of some type `Box<T>` and
338 /// now we must check that the type `T` is correct). Unfortunately,
339 /// because traits are not types, this is a pain to do.
341 pub enum RcvrMatchCondition {
342 RcvrMatchesIfObject(ast::DefId),
343 RcvrMatchesIfSubtype(ty::t)
346 impl<'a> LookupContext<'a> {
347 fn search(&self, self_ty: ty::t) -> Option<MethodCallee> {
348 let span = self.self_expr.map_or(self.span, |e| e.span);
349 let self_expr_id = self.self_expr.map(|e| e.id);
351 let (self_ty, autoderefs, result) =
353 self.fcx, span, self_ty, self_expr_id, PreferMutLvalue,
354 |self_ty, autoderefs| self.search_step(self_ty, autoderefs));
357 Some(Some(result)) => Some(result),
359 if self.is_overloaded_deref() {
360 // If we are searching for an overloaded deref, no
361 // need to try coercing a `~[T]` to an `&[T]` and
362 // searching for an overloaded deref on *that*.
365 self.search_for_autosliced_method(self_ty, autoderefs)
371 fn search_step(&self,
374 -> Option<Option<MethodCallee>> {
375 debug!("search_step: self_ty={} autoderefs={}",
376 self.ty_to_str(self_ty), autoderefs);
378 match self.deref_args {
379 check::DontDerefArgs => {
380 match self.search_for_autoderefd_method(self_ty, autoderefs) {
381 Some(result) => return Some(Some(result)),
385 match self.search_for_autoptrd_method(self_ty, autoderefs) {
386 Some(result) => return Some(Some(result)),
390 check::DoDerefArgs => {
391 match self.search_for_autoptrd_method(self_ty, autoderefs) {
392 Some(result) => return Some(Some(result)),
396 match self.search_for_autoderefd_method(self_ty, autoderefs) {
397 Some(result) => return Some(Some(result)),
403 // Don't autoderef if we aren't supposed to.
404 if self.autoderef_receiver == DontAutoderefReceiver {
411 fn is_overloaded_deref(&self) -> bool {
412 self.self_expr.is_none()
415 // ______________________________________________________________________
416 // Candidate collection (see comment at start of file)
418 fn reset_candidates(&mut self) {
419 self.inherent_candidates = Vec::new();
420 self.extension_candidates = Vec::new();
423 fn push_inherent_candidates(&mut self, self_ty: ty::t) {
425 * Collect all inherent candidates into
426 * `self.inherent_candidates`. See comment at the start of
427 * the file. To find the inherent candidates, we repeatedly
428 * deref the self-ty to find the "base-type". So, for
429 * example, if the receiver is Box<Box<C>> where `C` is a struct type,
430 * we'll want to find the inherent impls for `C`.
433 let span = self.self_expr.map_or(self.span, |e| e.span);
434 check::autoderef(self.fcx, span, self_ty, None, PreferMutLvalue, |self_ty, _| {
435 match get(self_ty).sty {
436 ty_trait(box TyTrait { def_id, ref substs, .. }) => {
437 self.push_inherent_candidates_from_object(def_id, substs);
438 self.push_inherent_impl_candidates_for_type(def_id);
440 ty_enum(did, _) | ty_struct(did, _) => {
441 if self.check_traits == CheckTraitsAndInherentMethods {
442 self.push_inherent_impl_candidates_for_type(did);
445 _ => { /* No inherent methods in these types */ }
448 // Don't autoderef if we aren't supposed to.
449 if self.autoderef_receiver == DontAutoderefReceiver {
457 fn push_bound_candidates(&mut self, self_ty: ty::t, restrict_to: Option<DefId>) {
458 let span = self.self_expr.map_or(self.span, |e| e.span);
459 check::autoderef(self.fcx, span, self_ty, None, PreferMutLvalue, |self_ty, _| {
460 match get(self_ty).sty {
462 self.push_inherent_candidates_from_param(self_ty, restrict_to, p);
464 _ => { /* No bound methods in these types */ }
467 // Don't autoderef if we aren't supposed to.
468 if self.autoderef_receiver == DontAutoderefReceiver {
476 fn push_extension_candidate(&mut self, trait_did: DefId) {
477 ty::populate_implementations_for_trait_if_necessary(self.tcx(), trait_did);
479 // Look for explicit implementations.
480 let impl_methods = self.tcx().impl_methods.borrow();
481 for impl_infos in self.tcx().trait_impls.borrow().find(&trait_did).iter() {
482 for impl_did in impl_infos.borrow().iter() {
483 let methods = impl_methods.get(impl_did);
484 self.push_candidates_from_impl(*impl_did, methods.as_slice(), true);
489 fn push_extension_candidates(&mut self, expr_id: ast::NodeId) {
490 // If the method being called is associated with a trait, then
491 // find all the impls of that trait. Each of those are
493 let opt_applicable_traits = self.fcx.ccx.trait_map.find(&expr_id);
494 for applicable_traits in opt_applicable_traits.move_iter() {
495 for trait_did in applicable_traits.iter() {
496 self.push_extension_candidate(*trait_did);
501 fn push_inherent_candidates_from_object(&mut self,
503 substs: &subst::Substs) {
504 debug!("push_inherent_candidates_from_object(did={}, substs={})",
505 self.did_to_str(did),
506 substs.repr(self.tcx()));
507 let _indenter = indenter();
508 let tcx = self.tcx();
509 let span = self.span;
511 // It is illegal to invoke a method on a trait instance that
512 // refers to the `self` type. An error will be reported by
513 // `enforce_object_limitations()` if the method refers
514 // to the `Self` type. Substituting ty_err here allows
515 // compiler to soldier on.
517 // `confirm_candidate()` also relies upon this substitution
519 let rcvr_substs = substs.with_self_ty(ty::mk_err());
520 let trait_ref = Rc::new(TraitRef {
522 substs: rcvr_substs.clone()
525 self.push_inherent_candidates_from_bounds_inner(&[trait_ref.clone()],
526 |new_trait_ref, m, method_num, _bound_num| {
527 let vtable_index = get_method_index(tcx, &*new_trait_ref,
528 trait_ref.clone(), method_num);
529 let mut m = (*m).clone();
530 // We need to fix up the transformed self type.
531 *m.fty.sig.inputs.get_mut(0) =
532 construct_transformed_self_ty_for_object(
533 tcx, span, did, &rcvr_substs, &m);
536 rcvr_match_condition: RcvrMatchesIfObject(did),
537 rcvr_substs: new_trait_ref.substs.clone(),
538 method_ty: Rc::new(m),
539 origin: MethodObject(MethodObject {
540 trait_id: new_trait_ref.def_id,
541 object_trait_id: did,
542 method_num: method_num,
543 real_index: vtable_index
549 fn push_inherent_candidates_from_param(&mut self,
551 restrict_to: Option<DefId>,
553 debug!("push_inherent_candidates_from_param(param_ty={:?})",
555 self.push_inherent_candidates_from_bounds(
560 param_index { space: param_ty.space, index: param_ty.idx });
564 fn push_inherent_candidates_from_bounds(&mut self,
566 space: subst::ParamSpace,
568 restrict_to: Option<DefId>,
569 param: param_index) {
571 self.fcx.inh.param_env.bounds.get(space, index).trait_bounds
573 self.push_inherent_candidates_from_bounds_inner(bounds,
574 |trait_ref, m, method_num, bound_num| {
577 if trait_did != trait_ref.def_id {
584 rcvr_match_condition: RcvrMatchesIfSubtype(self_ty),
585 rcvr_substs: trait_ref.substs.clone(),
587 origin: MethodParam(MethodParam {
588 trait_id: trait_ref.def_id,
589 method_num: method_num,
591 bound_num: bound_num,
597 // Do a search through a list of bounds, using a callback to actually
598 // create the candidates.
599 fn push_inherent_candidates_from_bounds_inner(&mut self,
600 bounds: &[Rc<TraitRef>],
601 mk_cand: |tr: Rc<TraitRef>,
605 -> Option<Candidate>) {
606 let tcx = self.tcx();
607 let mut next_bound_idx = 0; // count only trait bounds
609 ty::each_bound_trait_and_supertraits(tcx, bounds, |bound_trait_ref| {
610 let this_bound_idx = next_bound_idx;
613 let trait_methods = ty::trait_methods(tcx, bound_trait_ref.def_id);
614 match trait_methods.iter().position(|m| {
615 m.explicit_self != ast::SelfStatic &&
616 m.ident.name == self.m_name }) {
618 let method = trait_methods.get(pos).clone();
620 match mk_cand(bound_trait_ref, method, pos, this_bound_idx) {
622 debug!("pushing inherent candidate for param: {}",
623 cand.repr(self.tcx()));
624 self.inherent_candidates.push(cand);
630 debug!("trait doesn't contain method: {:?}",
631 bound_trait_ref.def_id);
632 // check next trait or bound
640 fn push_inherent_impl_candidates_for_type(&mut self, did: DefId) {
641 // Read the inherent implementation candidates for this type from the
642 // metadata if necessary.
643 ty::populate_implementations_for_type_if_necessary(self.tcx(), did);
645 let impl_methods = self.tcx().impl_methods.borrow();
646 for impl_infos in self.tcx().inherent_impls.borrow().find(&did).iter() {
647 for impl_did in impl_infos.borrow().iter() {
648 let methods = impl_methods.get(impl_did);
649 self.push_candidates_from_impl(*impl_did, methods.as_slice(), false);
654 fn push_candidates_from_impl(&mut self,
656 impl_methods: &[DefId],
657 is_extension: bool) {
658 let did = if self.report_statics == ReportStaticMethods {
659 // we only want to report each base trait once
660 match ty::impl_trait_ref(self.tcx(), impl_did) {
661 Some(trait_ref) => trait_ref.def_id,
668 if !self.impl_dups.insert(did) {
669 return; // already visited
672 debug!("push_candidates_from_impl: {} {}",
673 token::get_name(self.m_name),
674 impl_methods.iter().map(|&did| ty::method(self.tcx(), did).ident)
675 .collect::<Vec<ast::Ident>>()
678 let method = match impl_methods.iter().map(|&did| ty::method(self.tcx(), did))
679 .find(|m| m.ident.name == self.m_name) {
680 Some(method) => method,
681 None => { return; } // No method with the right name.
684 // determine the `self` of the impl with fresh
685 // variables for each parameter:
686 let span = self.self_expr.map_or(self.span, |e| e.span);
687 let vcx = self.fcx.vtable_context();
688 let ty::ty_param_substs_and_ty {
691 } = impl_self_ty(&vcx, span, impl_did);
693 let candidates = if is_extension {
694 &mut self.extension_candidates
696 &mut self.inherent_candidates
699 candidates.push(Candidate {
700 rcvr_match_condition: RcvrMatchesIfSubtype(impl_ty),
701 rcvr_substs: impl_substs,
702 origin: MethodStatic(method.def_id),
707 // ______________________________________________________________________
708 // Candidate selection (see comment at start of file)
710 fn search_for_autoderefd_method(&self,
713 -> Option<MethodCallee> {
714 let (self_ty, auto_deref_ref) =
715 self.consider_reborrow(self_ty, autoderefs);
717 // Hacky. For overloaded derefs, there may be an adjustment
718 // added to the expression from the outside context, so we do not store
719 // an explicit adjustment, but rather we hardwire the single deref
720 // that occurs in trans and mem_categorization.
721 let adjustment = match self.self_expr {
722 Some(expr) => Some((expr.id, ty::AutoDerefRef(auto_deref_ref))),
726 match self.search_for_method(self_ty) {
729 debug!("(searching for autoderef'd method) writing \
730 adjustment {:?} for {}", adjustment, self.ty_to_str( self_ty));
732 Some((self_expr_id, adj)) => {
733 self.fcx.write_adjustment(self_expr_id, adj);
742 fn consider_reborrow(&self,
745 -> (ty::t, ty::AutoDerefRef) {
747 * In the event that we are invoking a method with a receiver
748 * of a borrowed type like `&T`, `&mut T`, or `&mut [T]`,
749 * we will "reborrow" the receiver implicitly. For example, if
750 * you have a call `r.inc()` and where `r` has type `&mut T`,
751 * then we treat that like `(&mut *r).inc()`. This avoids
752 * consuming the original pointer.
754 * You might think that this would be a natural byproduct of
755 * the auto-deref/auto-ref process. This is true for `Box<T>`
756 * but not for an `&mut T` receiver. With `Box<T>`, we would
757 * begin by testing for methods with a self type `Box<T>`,
758 * then autoderef to `T`, then autoref to `&mut T`. But with
759 * an `&mut T` receiver the process begins with `&mut T`, only
760 * without any autoadjustments.
763 let tcx = self.tcx();
764 return match ty::get(self_ty).sty {
765 ty::ty_rptr(_, self_mt) if default_method_hack(self_mt) => {
768 autoderefs: autoderefs,
771 ty::ty_rptr(_, self_mt) => {
773 self.infcx().next_region_var(infer::Autoref(self.span));
774 let (extra_derefs, auto) = match ty::get(self_mt.ty).sty {
775 ty::ty_vec(_, None) => (0, ty::AutoBorrowVec(region, self_mt.mutbl)),
776 ty::ty_str => (0, ty::AutoBorrowVec(region, self_mt.mutbl)),
777 _ => (1, ty::AutoPtr(region, self_mt.mutbl)),
779 (ty::mk_rptr(tcx, region, self_mt),
781 autoderefs: autoderefs + extra_derefs,
782 autoref: Some(auto)})
785 ty::ty_trait(box ty::TyTrait {
786 def_id, ref substs, store: ty::RegionTraitStore(_, mutbl), bounds
789 self.infcx().next_region_var(infer::Autoref(self.span));
790 (ty::mk_trait(tcx, def_id, substs.clone(),
791 ty::RegionTraitStore(region, mutbl), bounds),
793 autoderefs: autoderefs,
794 autoref: Some(ty::AutoBorrowObj(region, mutbl))})
799 autoderefs: autoderefs,
804 fn default_method_hack(self_mt: ty::mt) -> bool {
805 // FIXME(#6129). Default methods can't deal with autoref.
807 // I am a horrible monster and I pray for death. Currently
808 // the default method code fails when you try to reborrow
809 // because it is not handling types correctly. In lieu of
810 // fixing that, I am introducing this horrible hack. - ndm
811 self_mt.mutbl == MutImmutable && ty::type_is_self(self_mt.ty)
815 fn auto_slice_vec(&self, mt: ty::mt, autoderefs: uint) -> Option<MethodCallee> {
816 let tcx = self.tcx();
817 debug!("auto_slice_vec {}", ppaux::ty_to_str(tcx, mt.ty));
819 // First try to borrow to a slice
820 let entry = self.search_for_some_kind_of_autorefd_method(
821 AutoBorrowVec, autoderefs, [MutImmutable, MutMutable],
822 |m,r| ty::mk_slice(tcx, r,
823 ty::mt {ty:mt.ty, mutbl:m}));
829 // Then try to borrow to a slice *and* borrow a pointer.
830 self.search_for_some_kind_of_autorefd_method(
831 AutoBorrowVecRef, autoderefs, [MutImmutable, MutMutable],
833 let slice_ty = ty::mk_slice(tcx, r,
834 ty::mt {ty:mt.ty, mutbl:m});
835 // NB: we do not try to autoref to a mutable
836 // pointer. That would be creating a pointer
837 // to a temporary pointer (the borrowed
838 // slice), so any update the callee makes to
839 // it can't be observed.
840 ty::mk_rptr(tcx, r, ty::mt {ty:slice_ty, mutbl:MutImmutable})
845 fn auto_slice_str(&self, autoderefs: uint) -> Option<MethodCallee> {
846 let tcx = self.tcx();
847 debug!("auto_slice_str");
849 let entry = self.search_for_some_kind_of_autorefd_method(
850 AutoBorrowVec, autoderefs, [MutImmutable],
851 |_m,r| ty::mk_str_slice(tcx, r, MutImmutable));
857 self.search_for_some_kind_of_autorefd_method(
858 AutoBorrowVecRef, autoderefs, [MutImmutable],
860 let slice_ty = ty::mk_str_slice(tcx, r, m);
861 ty::mk_rptr(tcx, r, ty::mt {ty:slice_ty, mutbl:m})
865 fn search_for_autosliced_method(&self,
868 -> Option<MethodCallee> {
870 * Searches for a candidate by converting things like
874 let tcx = self.tcx();
875 debug!("search_for_autosliced_method {}", ppaux::ty_to_str(tcx, self_ty));
877 let sty = ty::get(self_ty).sty.clone();
879 ty_rptr(_, mt) => match ty::get(mt.ty).sty {
880 ty_vec(mt, None) => self.auto_slice_vec(mt, autoderefs),
883 ty_uniq(t) => match ty::get(t).sty {
884 ty_vec(mt, None) => self.auto_slice_vec(mt, autoderefs),
885 ty_str => self.auto_slice_str(autoderefs),
888 ty_vec(mt, Some(_)) => self.auto_slice_vec(mt, autoderefs),
890 ty_trait(box ty::TyTrait {
896 // Coerce Box/&Trait instances to &Trait.
898 self.search_for_some_kind_of_autorefd_method(
899 AutoBorrowObj, autoderefs, [MutImmutable, MutMutable],
901 ty::mk_trait(tcx, trt_did, trt_substs.clone(),
902 RegionTraitStore(r, m), b)
907 // This case should probably be handled similarly to
916 fn search_for_autoptrd_method(&self, self_ty: ty::t, autoderefs: uint)
917 -> Option<MethodCallee> {
920 * Converts any type `T` to `&M T` where `M` is an
921 * appropriate mutability.
924 let tcx = self.tcx();
925 match ty::get(self_ty).sty {
926 ty_bare_fn(..) | ty_box(..) | ty_uniq(..) | ty_rptr(..) |
927 ty_infer(IntVar(_)) |
928 ty_infer(FloatVar(_)) |
929 ty_param(..) | ty_nil | ty_bot | ty_bool |
930 ty_char | ty_int(..) | ty_uint(..) |
931 ty_float(..) | ty_enum(..) | ty_ptr(..) | ty_struct(..) | ty_tup(..) |
932 ty_str | ty_vec(..) | ty_trait(..) | ty_closure(..) => {
933 self.search_for_some_kind_of_autorefd_method(
934 AutoPtr, autoderefs, [MutImmutable, MutMutable],
935 |m,r| ty::mk_rptr(tcx, r, ty::mt {ty:self_ty, mutbl:m}))
940 ty_infer(TyVar(_)) => {
941 self.bug(format!("unexpected type: {}",
942 self.ty_to_str(self_ty)).as_slice());
947 fn search_for_some_kind_of_autorefd_method(
949 kind: |Region, ast::Mutability| -> ty::AutoRef,
951 mutbls: &[ast::Mutability],
952 mk_autoref_ty: |ast::Mutability, ty::Region| -> ty::t)
953 -> Option<MethodCallee> {
954 // Hacky. For overloaded derefs, there may be an adjustment
955 // added to the expression from the outside context, so we do not store
956 // an explicit adjustment, but rather we hardwire the single deref
957 // that occurs in trans and mem_categorization.
958 let self_expr_id = match self.self_expr {
959 Some(expr) => Some(expr.id),
961 assert_eq!(autoderefs, 0);
962 assert_eq!(kind(ty::ReEmpty, ast::MutImmutable),
963 ty::AutoPtr(ty::ReEmpty, ast::MutImmutable));
968 // This is hokey. We should have mutability inference as a
969 // variable. But for now, try &const, then &, then &mut:
971 self.infcx().next_region_var(infer::Autoref(self.span));
972 for mutbl in mutbls.iter() {
973 let autoref_ty = mk_autoref_ty(*mutbl, region);
974 match self.search_for_method(autoref_ty) {
978 Some(self_expr_id) => {
979 self.fcx.write_adjustment(
981 ty::AutoDerefRef(ty::AutoDerefRef {
982 autoderefs: autoderefs,
983 autoref: Some(kind(region, *mutbl))
995 fn search_for_method(&self, rcvr_ty: ty::t) -> Option<MethodCallee> {
996 debug!("search_for_method(rcvr_ty={})", self.ty_to_str(rcvr_ty));
997 let _indenter = indenter();
999 // I am not sure that inherent methods should have higher
1000 // priority, but it is necessary ATM to handle some of the
1003 debug!("searching inherent candidates");
1004 match self.consider_candidates(rcvr_ty, self.inherent_candidates.as_slice()) {
1011 debug!("searching extension candidates");
1012 self.consider_candidates(rcvr_ty, self.extension_candidates.as_slice())
1015 fn consider_candidates(&self, rcvr_ty: ty::t,
1016 candidates: &[Candidate])
1017 -> Option<MethodCallee> {
1018 let relevant_candidates = self.filter_candidates(rcvr_ty, candidates);
1020 if relevant_candidates.len() == 0 {
1024 if self.report_statics == ReportStaticMethods {
1025 // lookup should only be called with ReportStaticMethods if a regular lookup failed
1026 assert!(relevant_candidates.iter().all(|c| c.method_ty.explicit_self == SelfStatic));
1028 self.tcx().sess.fileline_note(self.span,
1029 "found defined static methods, maybe a `self` is missing?");
1031 for (idx, candidate) in relevant_candidates.iter().enumerate() {
1032 self.report_candidate(idx, &candidate.origin);
1035 // return something so we don't get errors for every mutability
1036 return Some(MethodCallee {
1037 origin: relevant_candidates.get(0).origin,
1039 substs: subst::Substs::empty()
1043 if relevant_candidates.len() > 1 {
1044 self.tcx().sess.span_err(
1046 "multiple applicable methods in scope");
1047 for (idx, candidate) in relevant_candidates.iter().enumerate() {
1048 self.report_candidate(idx, &candidate.origin);
1052 Some(self.confirm_candidate(rcvr_ty, relevant_candidates.get(0)))
1055 fn filter_candidates(&self, rcvr_ty: ty::t, candidates: &[Candidate]) -> Vec<Candidate> {
1056 let mut relevant_candidates: Vec<Candidate> = Vec::new();
1058 for candidate_a in candidates.iter().filter(|&c| self.is_relevant(rcvr_ty, c)) {
1059 // Skip this one if we already have one like it
1060 if !relevant_candidates.iter().any(|candidate_b| {
1061 debug!("attempting to merge {} and {}",
1062 candidate_a.repr(self.tcx()),
1063 candidate_b.repr(self.tcx()));
1064 match (&candidate_a.origin, &candidate_b.origin) {
1065 (&MethodParam(ref p1), &MethodParam(ref p2)) => {
1066 let same_trait = p1.trait_id == p2.trait_id;
1067 let same_method = p1.method_num == p2.method_num;
1068 let same_param = p1.param_num == p2.param_num;
1069 // The bound number may be different because
1070 // multiple bounds may lead to the same trait
1072 same_trait && same_method && same_param
1077 relevant_candidates.push(candidate_a.clone());
1084 fn confirm_candidate(&self, rcvr_ty: ty::t, candidate: &Candidate)
1087 // This method performs two sets of substitutions, one after the other:
1088 // 1. Substitute values for any type/lifetime parameters from the impl and
1089 // method declaration into the method type. This is the function type
1090 // before it is called; it may still include late bound region variables.
1091 // 2. Instantiate any late bound lifetime parameters in the method itself
1092 // with fresh region variables.
1094 let tcx = self.tcx();
1096 debug!("confirm_candidate(rcvr_ty={}, candidate={})",
1097 self.ty_to_str(rcvr_ty),
1098 candidate.repr(self.tcx()));
1100 self.enforce_object_limitations(candidate);
1101 self.enforce_drop_trait_limitations(candidate);
1103 // static methods should never have gotten this far:
1104 assert!(candidate.method_ty.explicit_self != SelfStatic);
1106 // Determine the values for the generic parameters of the method.
1107 // If they were not explicitly supplied, just construct fresh
1109 let num_supplied_tps = self.supplied_tps.len();
1110 let num_method_tps = candidate.method_ty.generics.types.len(subst::FnSpace);
1112 if num_supplied_tps == 0u {
1113 self.fcx.infcx().next_ty_vars(num_method_tps)
1114 } else if num_method_tps == 0u {
1117 "this method does not take type parameters");
1118 self.fcx.infcx().next_ty_vars(num_method_tps)
1119 } else if num_supplied_tps != num_method_tps {
1122 "incorrect number of type parameters given for this method");
1123 self.fcx.infcx().next_ty_vars(num_method_tps)
1125 Vec::from_slice(self.supplied_tps)
1129 // Create subst for early-bound lifetime parameters, combining
1130 // parameters from the type and those from the method.
1132 // FIXME -- permit users to manually specify lifetimes
1134 self.fcx.infcx().region_vars_for_defs(
1136 candidate.method_ty.generics.regions.get_vec(subst::FnSpace));
1138 let all_substs = candidate.rcvr_substs.clone().with_method(m_types, m_regions);
1140 let ref bare_fn_ty = candidate.method_ty.fty;
1142 // Compute the method type with type parameters substituted
1143 debug!("fty={} all_substs={}",
1144 bare_fn_ty.repr(tcx),
1145 all_substs.repr(tcx));
1147 let fn_sig = &bare_fn_ty.sig;
1148 let inputs = match candidate.origin {
1149 MethodObject(..) => {
1150 // For annoying reasons, we've already handled the
1151 // substitution of self for object calls.
1152 let args = fn_sig.inputs.slice_from(1).iter().map(|t| {
1153 t.subst(tcx, &all_substs)
1155 Some(*fn_sig.inputs.get(0)).move_iter().chain(args).collect()
1157 _ => fn_sig.inputs.subst(tcx, &all_substs)
1159 let fn_sig = ty::FnSig {
1160 binder_id: fn_sig.binder_id,
1162 output: fn_sig.output.subst(tcx, &all_substs),
1163 variadic: fn_sig.variadic
1166 debug!("after subst, fty={}", fn_sig.repr(tcx));
1168 // Replace any bound regions that appear in the function
1169 // signature with region variables
1170 let (_, fn_sig) = replace_late_bound_regions_in_fn_sig(
1172 |br| self.fcx.infcx().next_region_var(
1173 infer::LateBoundRegion(self.span, br)));
1174 let transformed_self_ty = *fn_sig.inputs.get(0);
1175 let fty = ty::mk_bare_fn(tcx, ty::BareFnTy {
1177 fn_style: bare_fn_ty.fn_style,
1178 abi: bare_fn_ty.abi.clone(),
1180 debug!("after replacing bound regions, fty={}", self.ty_to_str(fty));
1182 // Before, we only checked whether self_ty could be a subtype
1183 // of rcvr_ty; now we actually make it so (this may cause
1184 // variables to unify etc). Since we checked beforehand, and
1185 // nothing has changed in the meantime, this unification
1186 // should never fail.
1187 let span = self.self_expr.map_or(self.span, |e| e.span);
1188 match self.fcx.mk_subty(false, infer::Misc(span),
1189 rcvr_ty, transformed_self_ty) {
1193 "{} was a subtype of {} but now is not?",
1194 self.ty_to_str(rcvr_ty),
1195 self.ty_to_str(transformed_self_ty)).as_slice());
1200 origin: candidate.origin,
1206 fn enforce_object_limitations(&self, candidate: &Candidate) {
1208 * There are some limitations to calling functions through an
1209 * object, because (a) the self type is not known
1210 * (that's the whole point of a trait instance, after all, to
1211 * obscure the self type) and (b) the call must go through a
1212 * vtable and hence cannot be monomorphized.
1215 match candidate.origin {
1216 MethodStatic(..) | MethodParam(..) => {
1217 return; // not a call to a trait instance
1219 MethodObject(..) => {}
1222 match candidate.method_ty.explicit_self {
1223 ast::SelfStatic => { // reason (a) above
1224 self.tcx().sess.span_err(
1226 "cannot call a method without a receiver \
1227 through an object");
1230 ast::SelfValue => { // reason (a) above
1231 self.tcx().sess.span_err(
1233 "cannot call a method with a by-value receiver \
1234 through an object");
1237 ast::SelfRegion(..) | ast::SelfUniq => {}
1241 let check_for_self_ty = |ty| {
1242 if ty::type_has_self(ty) {
1243 self.tcx().sess.span_err(
1245 "cannot call a method whose type contains a \
1246 self-type through an object");
1252 let ref sig = candidate.method_ty.fty.sig;
1253 let mut found_self_ty = false;
1254 for &input_ty in sig.inputs.iter() {
1255 if check_for_self_ty(input_ty) {
1256 found_self_ty = true;
1261 check_for_self_ty(sig.output);
1264 if candidate.method_ty.generics.has_type_params(subst::FnSpace) {
1266 self.tcx().sess.span_err(
1268 "cannot call a generic method through an object");
1272 fn enforce_drop_trait_limitations(&self, candidate: &Candidate) {
1273 // No code can call the finalize method explicitly.
1275 match candidate.origin {
1276 MethodStatic(method_id) => {
1277 bad = self.tcx().destructors.borrow().contains(&method_id);
1279 // FIXME: does this properly enforce this on everything now
1280 // that self has been merged in? -sully
1281 MethodParam(MethodParam { trait_id: trait_id, .. }) |
1282 MethodObject(MethodObject { trait_id: trait_id, .. }) => {
1283 bad = self.tcx().destructor_for_type.borrow()
1284 .contains_key(&trait_id);
1289 self.tcx().sess.span_err(self.span,
1290 "explicit call to destructor");
1294 // `rcvr_ty` is the type of the expression. It may be a subtype of a
1295 // candidate method's `self_ty`.
1296 fn is_relevant(&self, rcvr_ty: ty::t, candidate: &Candidate) -> bool {
1297 debug!("is_relevant(rcvr_ty={}, candidate={})",
1298 self.ty_to_str(rcvr_ty), candidate.repr(self.tcx()));
1300 return match candidate.method_ty.explicit_self {
1302 debug!("(is relevant?) explicit self is static");
1303 self.report_statics == ReportStaticMethods
1307 rcvr_matches_ty(self.fcx, rcvr_ty, candidate)
1310 SelfRegion(_, m) => {
1311 debug!("(is relevant?) explicit self is a region");
1312 match ty::get(rcvr_ty).sty {
1313 ty::ty_rptr(_, mt) => {
1314 match ty::get(mt.ty).sty {
1315 ty::ty_vec(_, None) | ty::ty_str => false,
1316 _ => mutability_matches(mt.mutbl, m) &&
1317 rcvr_matches_ty(self.fcx, mt.ty, candidate),
1321 ty::ty_trait(box ty::TyTrait {
1322 def_id: self_did, store: RegionTraitStore(_, self_m), ..
1324 mutability_matches(self_m, m) &&
1325 rcvr_matches_object(self_did, candidate)
1333 debug!("(is relevant?) explicit self is a unique pointer");
1334 match ty::get(rcvr_ty).sty {
1335 ty::ty_uniq(typ) => {
1336 match ty::get(typ).sty {
1337 ty::ty_vec(_, None) | ty::ty_str => false,
1338 _ => rcvr_matches_ty(self.fcx, typ, candidate),
1342 ty::ty_trait(box ty::TyTrait {
1343 def_id: self_did, store: UniqTraitStore, ..
1345 rcvr_matches_object(self_did, candidate)
1353 fn rcvr_matches_object(self_did: ast::DefId,
1354 candidate: &Candidate) -> bool {
1355 match candidate.rcvr_match_condition {
1356 RcvrMatchesIfObject(desired_did) => {
1357 self_did == desired_did
1359 RcvrMatchesIfSubtype(_) => {
1365 fn rcvr_matches_ty(fcx: &FnCtxt,
1367 candidate: &Candidate) -> bool {
1368 match candidate.rcvr_match_condition {
1369 RcvrMatchesIfObject(_) => {
1372 RcvrMatchesIfSubtype(of_type) => {
1373 fcx.can_mk_subty(rcvr_ty, of_type).is_ok()
1378 fn mutability_matches(self_mutbl: ast::Mutability,
1379 candidate_mutbl: ast::Mutability)
1381 //! True if `self_mutbl <: candidate_mutbl`
1382 self_mutbl == candidate_mutbl
1386 fn report_candidate(&self, idx: uint, origin: &MethodOrigin) {
1388 MethodStatic(impl_did) => {
1389 let did = if self.report_statics == ReportStaticMethods {
1390 // If we're reporting statics, we want to report the trait
1391 // definition if possible, rather than an impl
1392 match ty::trait_method_of_method(self.tcx(), impl_did) {
1393 None => {debug!("(report candidate) No trait method found"); impl_did},
1394 Some(trait_did) => {debug!("(report candidate) Found trait ref"); trait_did}
1397 // If it is an instantiated default method, use the original
1398 // default method for error reporting.
1399 match provided_source(self.tcx(), impl_did) {
1404 self.report_static_candidate(idx, did)
1406 MethodParam(ref mp) => {
1407 self.report_param_candidate(idx, (*mp).trait_id)
1409 MethodObject(ref mo) => {
1410 self.report_trait_candidate(idx, mo.trait_id)
1416 fn report_static_candidate(&self, idx: uint, did: DefId) {
1417 let span = if did.krate == ast::LOCAL_CRATE {
1418 self.tcx().map.span(did.node)
1422 self.tcx().sess.span_note(
1424 format!("candidate \\#{} is `{}`",
1426 ty::item_path_str(self.tcx(), did)).as_slice());
1430 fn report_param_candidate(&self, idx: uint, did: DefId) {
1431 self.tcx().sess.span_note(
1433 format!("candidate \\#{} derives from the bound `{}`",
1435 ty::item_path_str(self.tcx(), did)).as_slice());
1439 fn report_trait_candidate(&self, idx: uint, did: DefId) {
1440 self.tcx().sess.span_note(
1442 format!("candidate \\#{} derives from the type of the receiver, \
1443 which is the trait `{}`",
1445 ty::item_path_str(self.tcx(), did)).as_slice());
1449 fn report_static_candidate(&self, idx: uint, did: DefId) {
1450 let span = if did.krate == ast::LOCAL_CRATE {
1451 self.tcx().map.span(did.node)
1455 self.tcx().sess.span_note(
1457 format!("candidate #{} is `{}`",
1459 ty::item_path_str(self.tcx(), did)).as_slice());
1463 fn report_param_candidate(&self, idx: uint, did: DefId) {
1464 self.tcx().sess.span_note(
1466 format!("candidate #{} derives from the bound `{}`",
1468 ty::item_path_str(self.tcx(), did)).as_slice());
1472 fn report_trait_candidate(&self, idx: uint, did: DefId) {
1473 self.tcx().sess.span_note(
1475 format!("candidate #{} derives from the type of the receiver, \
1476 which is the trait `{}`",
1478 ty::item_path_str(self.tcx(), did)).as_slice());
1481 fn infcx(&'a self) -> &'a infer::InferCtxt<'a> {
1485 fn tcx(&self) -> &'a ty::ctxt {
1489 fn ty_to_str(&self, t: ty::t) -> String {
1490 self.fcx.infcx().ty_to_str(t)
1493 fn did_to_str(&self, did: DefId) -> String {
1494 ty::item_path_str(self.tcx(), did)
1497 fn bug(&self, s: &str) -> ! {
1498 self.tcx().sess.span_bug(self.span, s)
1502 impl Repr for Candidate {
1503 fn repr(&self, tcx: &ty::ctxt) -> String {
1504 format!("Candidate(rcvr_ty={}, rcvr_substs={}, method_ty={}, \
1506 self.rcvr_match_condition.repr(tcx),
1507 self.rcvr_substs.repr(tcx),
1508 self.method_ty.repr(tcx),
1513 impl Repr for RcvrMatchCondition {
1514 fn repr(&self, tcx: &ty::ctxt) -> String {
1516 RcvrMatchesIfObject(d) => {
1517 format!("RcvrMatchesIfObject({})", d.repr(tcx))
1519 RcvrMatchesIfSubtype(t) => {
1520 format!("RcvrMatchesIfSubtype({})", t.repr(tcx))