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 let tr = ty::mk_trait(tcx, trait_def_id, obj_substs,
281 ty::empty_builtin_bounds());
282 ty::mk_rptr(tcx, r, ty::mt{ ty: tr, mutbl: mt.mutbl })
284 ty::ty_uniq(_) => { // must be SelfUniq
285 let tr = ty::mk_trait(tcx, trait_def_id, obj_substs,
286 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_uniq(ty) | ty_rptr(_, mt {ty, ..}) => match get(ty).sty{
437 ty_trait(box TyTrait { def_id, ref substs, .. }) => {
438 self.push_inherent_candidates_from_object(def_id, substs);
439 self.push_inherent_impl_candidates_for_type(def_id);
443 ty_enum(did, _) | ty_struct(did, _) => {
444 if self.check_traits == CheckTraitsAndInherentMethods {
445 self.push_inherent_impl_candidates_for_type(did);
448 _ => { /* No inherent methods in these types */ }
451 // Don't autoderef if we aren't supposed to.
452 if self.autoderef_receiver == DontAutoderefReceiver {
460 fn push_bound_candidates(&mut self, self_ty: ty::t, restrict_to: Option<DefId>) {
461 let span = self.self_expr.map_or(self.span, |e| e.span);
462 check::autoderef(self.fcx, span, self_ty, None, PreferMutLvalue, |self_ty, _| {
463 match get(self_ty).sty {
465 self.push_inherent_candidates_from_param(self_ty, restrict_to, p);
467 _ => { /* No bound methods in these types */ }
470 // Don't autoderef if we aren't supposed to.
471 if self.autoderef_receiver == DontAutoderefReceiver {
479 fn push_extension_candidate(&mut self, trait_did: DefId) {
480 ty::populate_implementations_for_trait_if_necessary(self.tcx(), trait_did);
482 // Look for explicit implementations.
483 let impl_methods = self.tcx().impl_methods.borrow();
484 for impl_infos in self.tcx().trait_impls.borrow().find(&trait_did).iter() {
485 for impl_did in impl_infos.borrow().iter() {
486 let methods = impl_methods.get(impl_did);
487 self.push_candidates_from_impl(*impl_did, methods.as_slice(), true);
492 fn push_extension_candidates(&mut self, expr_id: ast::NodeId) {
493 // If the method being called is associated with a trait, then
494 // find all the impls of that trait. Each of those are
496 let opt_applicable_traits = self.fcx.ccx.trait_map.find(&expr_id);
497 for applicable_traits in opt_applicable_traits.move_iter() {
498 for trait_did in applicable_traits.iter() {
499 self.push_extension_candidate(*trait_did);
504 fn push_inherent_candidates_from_object(&mut self,
506 substs: &subst::Substs) {
507 debug!("push_inherent_candidates_from_object(did={}, substs={})",
508 self.did_to_str(did),
509 substs.repr(self.tcx()));
510 let _indenter = indenter();
511 let tcx = self.tcx();
512 let span = self.span;
514 // It is illegal to invoke a method on a trait instance that
515 // refers to the `self` type. An error will be reported by
516 // `enforce_object_limitations()` if the method refers
517 // to the `Self` type. Substituting ty_err here allows
518 // compiler to soldier on.
520 // `confirm_candidate()` also relies upon this substitution
522 let rcvr_substs = substs.with_self_ty(ty::mk_err());
523 let trait_ref = Rc::new(TraitRef {
525 substs: rcvr_substs.clone()
528 self.push_inherent_candidates_from_bounds_inner(&[trait_ref.clone()],
529 |new_trait_ref, m, method_num, _bound_num| {
530 let vtable_index = get_method_index(tcx, &*new_trait_ref,
531 trait_ref.clone(), method_num);
532 let mut m = (*m).clone();
533 // We need to fix up the transformed self type.
534 *m.fty.sig.inputs.get_mut(0) =
535 construct_transformed_self_ty_for_object(
536 tcx, span, did, &rcvr_substs, &m);
539 rcvr_match_condition: RcvrMatchesIfObject(did),
540 rcvr_substs: new_trait_ref.substs.clone(),
541 method_ty: Rc::new(m),
542 origin: MethodObject(MethodObject {
543 trait_id: new_trait_ref.def_id,
544 object_trait_id: did,
545 method_num: method_num,
546 real_index: vtable_index
552 fn push_inherent_candidates_from_param(&mut self,
554 restrict_to: Option<DefId>,
556 debug!("push_inherent_candidates_from_param(param_ty={:?})",
558 self.push_inherent_candidates_from_bounds(
563 param_index { space: param_ty.space, index: param_ty.idx });
567 fn push_inherent_candidates_from_bounds(&mut self,
569 space: subst::ParamSpace,
571 restrict_to: Option<DefId>,
572 param: param_index) {
574 self.fcx.inh.param_env.bounds.get(space, index).trait_bounds
576 self.push_inherent_candidates_from_bounds_inner(bounds,
577 |trait_ref, m, method_num, bound_num| {
580 if trait_did != trait_ref.def_id {
587 rcvr_match_condition: RcvrMatchesIfSubtype(self_ty),
588 rcvr_substs: trait_ref.substs.clone(),
590 origin: MethodParam(MethodParam {
591 trait_id: trait_ref.def_id,
592 method_num: method_num,
594 bound_num: bound_num,
600 // Do a search through a list of bounds, using a callback to actually
601 // create the candidates.
602 fn push_inherent_candidates_from_bounds_inner(&mut self,
603 bounds: &[Rc<TraitRef>],
604 mk_cand: |tr: Rc<TraitRef>,
608 -> Option<Candidate>) {
609 let tcx = self.tcx();
610 let mut next_bound_idx = 0; // count only trait bounds
612 ty::each_bound_trait_and_supertraits(tcx, bounds, |bound_trait_ref| {
613 let this_bound_idx = next_bound_idx;
616 let trait_methods = ty::trait_methods(tcx, bound_trait_ref.def_id);
617 match trait_methods.iter().position(|m| {
618 m.explicit_self != ast::SelfStatic &&
619 m.ident.name == self.m_name }) {
621 let method = trait_methods.get(pos).clone();
623 match mk_cand(bound_trait_ref, method, pos, this_bound_idx) {
625 debug!("pushing inherent candidate for param: {}",
626 cand.repr(self.tcx()));
627 self.inherent_candidates.push(cand);
633 debug!("trait doesn't contain method: {:?}",
634 bound_trait_ref.def_id);
635 // check next trait or bound
643 fn push_inherent_impl_candidates_for_type(&mut self, did: DefId) {
644 // Read the inherent implementation candidates for this type from the
645 // metadata if necessary.
646 ty::populate_implementations_for_type_if_necessary(self.tcx(), did);
648 let impl_methods = self.tcx().impl_methods.borrow();
649 for impl_infos in self.tcx().inherent_impls.borrow().find(&did).iter() {
650 for impl_did in impl_infos.borrow().iter() {
651 let methods = impl_methods.get(impl_did);
652 self.push_candidates_from_impl(*impl_did, methods.as_slice(), false);
657 fn push_candidates_from_impl(&mut self,
659 impl_methods: &[DefId],
660 is_extension: bool) {
661 let did = if self.report_statics == ReportStaticMethods {
662 // we only want to report each base trait once
663 match ty::impl_trait_ref(self.tcx(), impl_did) {
664 Some(trait_ref) => trait_ref.def_id,
671 if !self.impl_dups.insert(did) {
672 return; // already visited
675 debug!("push_candidates_from_impl: {} {}",
676 token::get_name(self.m_name),
677 impl_methods.iter().map(|&did| ty::method(self.tcx(), did).ident)
678 .collect::<Vec<ast::Ident>>()
681 let method = match impl_methods.iter().map(|&did| ty::method(self.tcx(), did))
682 .find(|m| m.ident.name == self.m_name) {
683 Some(method) => method,
684 None => { return; } // No method with the right name.
687 // determine the `self` of the impl with fresh
688 // variables for each parameter:
689 let span = self.self_expr.map_or(self.span, |e| e.span);
690 let vcx = self.fcx.vtable_context();
691 let ty::ty_param_substs_and_ty {
694 } = impl_self_ty(&vcx, span, impl_did);
696 let candidates = if is_extension {
697 &mut self.extension_candidates
699 &mut self.inherent_candidates
702 candidates.push(Candidate {
703 rcvr_match_condition: RcvrMatchesIfSubtype(impl_ty),
704 rcvr_substs: impl_substs,
705 origin: MethodStatic(method.def_id),
710 // ______________________________________________________________________
711 // Candidate selection (see comment at start of file)
713 fn search_for_autoderefd_method(&self,
716 -> Option<MethodCallee> {
717 let (self_ty, auto_deref_ref) =
718 self.consider_reborrow(self_ty, autoderefs);
720 // Hacky. For overloaded derefs, there may be an adjustment
721 // added to the expression from the outside context, so we do not store
722 // an explicit adjustment, but rather we hardwire the single deref
723 // that occurs in trans and mem_categorization.
724 let adjustment = match self.self_expr {
725 Some(expr) => Some((expr.id, ty::AutoDerefRef(auto_deref_ref))),
729 match self.search_for_method(self_ty) {
732 debug!("(searching for autoderef'd method) writing \
733 adjustment {:?} for {}", adjustment, self.ty_to_str( self_ty));
735 Some((self_expr_id, adj)) => {
736 self.fcx.write_adjustment(self_expr_id, adj);
745 fn consider_reborrow(&self,
748 -> (ty::t, ty::AutoDerefRef) {
750 * In the event that we are invoking a method with a receiver
751 * of a borrowed type like `&T`, `&mut T`, or `&mut [T]`,
752 * we will "reborrow" the receiver implicitly. For example, if
753 * you have a call `r.inc()` and where `r` has type `&mut T`,
754 * then we treat that like `(&mut *r).inc()`. This avoids
755 * consuming the original pointer.
757 * You might think that this would be a natural byproduct of
758 * the auto-deref/auto-ref process. This is true for `Box<T>`
759 * but not for an `&mut T` receiver. With `Box<T>`, we would
760 * begin by testing for methods with a self type `Box<T>`,
761 * then autoderef to `T`, then autoref to `&mut T`. But with
762 * an `&mut T` receiver the process begins with `&mut T`, only
763 * without any autoadjustments.
766 let tcx = self.tcx();
767 return match ty::get(self_ty).sty {
768 ty::ty_rptr(_, self_mt) if default_method_hack(self_mt) => {
771 autoderefs: autoderefs,
774 ty::ty_rptr(_, self_mt) => {
776 self.infcx().next_region_var(infer::Autoref(self.span));
777 let (extra_derefs, auto) = match ty::get(self_mt.ty).sty {
778 ty::ty_vec(_, None) => (0, ty::AutoBorrowVec(region, self_mt.mutbl)),
779 ty::ty_str => (0, ty::AutoBorrowVec(region, self_mt.mutbl)),
780 ty::ty_trait(..) => (0, ty::AutoBorrowObj(region, self_mt.mutbl)),
781 _ => (1, ty::AutoPtr(region, self_mt.mutbl)),
783 (ty::mk_rptr(tcx, region, self_mt),
785 autoderefs: autoderefs + extra_derefs,
786 autoref: Some(auto)})
791 autoderefs: autoderefs,
796 fn default_method_hack(self_mt: ty::mt) -> bool {
797 // FIXME(#6129). Default methods can't deal with autoref.
799 // I am a horrible monster and I pray for death. Currently
800 // the default method code fails when you try to reborrow
801 // because it is not handling types correctly. In lieu of
802 // fixing that, I am introducing this horrible hack. - ndm
803 self_mt.mutbl == MutImmutable && ty::type_is_self(self_mt.ty)
807 fn auto_slice_vec(&self, mt: ty::mt, autoderefs: uint) -> Option<MethodCallee> {
808 let tcx = self.tcx();
809 debug!("auto_slice_vec {}", ppaux::ty_to_str(tcx, mt.ty));
811 // First try to borrow to a slice
812 let entry = self.search_for_some_kind_of_autorefd_method(
813 AutoBorrowVec, autoderefs, [MutImmutable, MutMutable],
814 |m,r| ty::mk_slice(tcx, r,
815 ty::mt {ty:mt.ty, mutbl:m}));
821 // Then try to borrow to a slice *and* borrow a pointer.
822 self.search_for_some_kind_of_autorefd_method(
823 AutoBorrowVecRef, autoderefs, [MutImmutable, MutMutable],
825 let slice_ty = ty::mk_slice(tcx, r,
826 ty::mt {ty:mt.ty, mutbl:m});
827 // NB: we do not try to autoref to a mutable
828 // pointer. That would be creating a pointer
829 // to a temporary pointer (the borrowed
830 // slice), so any update the callee makes to
831 // it can't be observed.
832 ty::mk_rptr(tcx, r, ty::mt {ty:slice_ty, mutbl:MutImmutable})
837 fn auto_slice_str(&self, autoderefs: uint) -> Option<MethodCallee> {
838 let tcx = self.tcx();
839 debug!("auto_slice_str");
841 let entry = self.search_for_some_kind_of_autorefd_method(
842 AutoBorrowVec, autoderefs, [MutImmutable],
843 |_m,r| ty::mk_str_slice(tcx, r, MutImmutable));
849 self.search_for_some_kind_of_autorefd_method(
850 AutoBorrowVecRef, autoderefs, [MutImmutable],
852 let slice_ty = ty::mk_str_slice(tcx, r, m);
853 ty::mk_rptr(tcx, r, ty::mt {ty:slice_ty, mutbl:m})
857 // Coerce Box/&Trait instances to &Trait.
858 fn auto_slice_trait(&self, ty: ty::t, autoderefs: uint) -> Option<MethodCallee> {
859 match ty::get(ty).sty {
860 ty_trait(box ty::TyTrait {
862 substs: ref trt_substs,
865 let tcx = self.tcx();
866 self.search_for_some_kind_of_autorefd_method(
867 AutoBorrowObj, autoderefs, [MutImmutable, MutMutable],
869 let tr = ty::mk_trait(tcx, trt_did, trt_substs.clone(), b);
870 ty::mk_rptr(tcx, r, ty::mt{ ty: tr, mutbl: m })
873 _ => fail!("Expected ty_trait in auto_slice_trait")
877 fn search_for_autosliced_method(&self,
880 -> Option<MethodCallee> {
882 * Searches for a candidate by converting things like
886 debug!("search_for_autosliced_method {}", ppaux::ty_to_str(self.tcx(), self_ty));
888 let sty = ty::get(self_ty).sty.clone();
890 ty_rptr(_, mt) => match ty::get(mt.ty).sty {
891 ty_vec(mt, None) => self.auto_slice_vec(mt, autoderefs),
892 ty_trait(..) => self.auto_slice_trait(mt.ty, autoderefs),
895 ty_uniq(t) => match ty::get(t).sty {
896 ty_vec(mt, None) => self.auto_slice_vec(mt, autoderefs),
897 ty_str => self.auto_slice_str(autoderefs),
898 ty_trait(..) => self.auto_slice_trait(t, autoderefs),
901 ty_vec(mt, Some(_)) => self.auto_slice_vec(mt, autoderefs),
904 // This case should probably be handled similarly to
913 fn search_for_autoptrd_method(&self, self_ty: ty::t, autoderefs: uint)
914 -> Option<MethodCallee> {
917 * Converts any type `T` to `&M T` where `M` is an
918 * appropriate mutability.
921 let tcx = self.tcx();
922 match ty::get(self_ty).sty {
923 ty_bare_fn(..) | ty_box(..) | ty_uniq(..) | ty_rptr(..) |
924 ty_infer(IntVar(_)) |
925 ty_infer(FloatVar(_)) |
926 ty_param(..) | ty_nil | ty_bot | ty_bool |
927 ty_char | ty_int(..) | ty_uint(..) |
928 ty_float(..) | ty_enum(..) | ty_ptr(..) | ty_struct(..) | ty_tup(..) |
929 ty_str | ty_vec(..) | ty_trait(..) | ty_closure(..) => {
930 self.search_for_some_kind_of_autorefd_method(
931 AutoPtr, autoderefs, [MutImmutable, MutMutable],
932 |m,r| ty::mk_rptr(tcx, r, ty::mt {ty:self_ty, mutbl:m}))
937 ty_infer(TyVar(_)) => {
938 self.bug(format!("unexpected type: {}",
939 self.ty_to_str(self_ty)).as_slice());
944 fn search_for_some_kind_of_autorefd_method(
946 kind: |Region, ast::Mutability| -> ty::AutoRef,
948 mutbls: &[ast::Mutability],
949 mk_autoref_ty: |ast::Mutability, ty::Region| -> ty::t)
950 -> Option<MethodCallee> {
951 // Hacky. For overloaded derefs, there may be an adjustment
952 // added to the expression from the outside context, so we do not store
953 // an explicit adjustment, but rather we hardwire the single deref
954 // that occurs in trans and mem_categorization.
955 let self_expr_id = match self.self_expr {
956 Some(expr) => Some(expr.id),
958 assert_eq!(autoderefs, 0);
959 assert_eq!(kind(ty::ReEmpty, ast::MutImmutable),
960 ty::AutoPtr(ty::ReEmpty, ast::MutImmutable));
965 // This is hokey. We should have mutability inference as a
966 // variable. But for now, try &const, then &, then &mut:
968 self.infcx().next_region_var(infer::Autoref(self.span));
969 for mutbl in mutbls.iter() {
970 let autoref_ty = mk_autoref_ty(*mutbl, region);
971 match self.search_for_method(autoref_ty) {
975 Some(self_expr_id) => {
976 self.fcx.write_adjustment(
978 ty::AutoDerefRef(ty::AutoDerefRef {
979 autoderefs: autoderefs,
980 autoref: Some(kind(region, *mutbl))
992 fn search_for_method(&self, rcvr_ty: ty::t) -> Option<MethodCallee> {
993 debug!("search_for_method(rcvr_ty={})", self.ty_to_str(rcvr_ty));
994 let _indenter = indenter();
996 // I am not sure that inherent methods should have higher
997 // priority, but it is necessary ATM to handle some of the
1000 debug!("searching inherent candidates");
1001 match self.consider_candidates(rcvr_ty, self.inherent_candidates.as_slice()) {
1008 debug!("searching extension candidates");
1009 self.consider_candidates(rcvr_ty, self.extension_candidates.as_slice())
1012 fn consider_candidates(&self, rcvr_ty: ty::t,
1013 candidates: &[Candidate])
1014 -> Option<MethodCallee> {
1015 let relevant_candidates = self.filter_candidates(rcvr_ty, candidates);
1017 if relevant_candidates.len() == 0 {
1021 if self.report_statics == ReportStaticMethods {
1022 // lookup should only be called with ReportStaticMethods if a regular lookup failed
1023 assert!(relevant_candidates.iter().all(|c| c.method_ty.explicit_self == SelfStatic));
1025 self.tcx().sess.fileline_note(self.span,
1026 "found defined static methods, maybe a `self` is missing?");
1028 for (idx, candidate) in relevant_candidates.iter().enumerate() {
1029 self.report_candidate(idx, &candidate.origin);
1032 // return something so we don't get errors for every mutability
1033 return Some(MethodCallee {
1034 origin: relevant_candidates.get(0).origin,
1036 substs: subst::Substs::empty()
1040 if relevant_candidates.len() > 1 {
1041 self.tcx().sess.span_err(
1043 "multiple applicable methods in scope");
1044 for (idx, candidate) in relevant_candidates.iter().enumerate() {
1045 self.report_candidate(idx, &candidate.origin);
1049 Some(self.confirm_candidate(rcvr_ty, relevant_candidates.get(0)))
1052 fn filter_candidates(&self, rcvr_ty: ty::t, candidates: &[Candidate]) -> Vec<Candidate> {
1053 let mut relevant_candidates: Vec<Candidate> = Vec::new();
1055 for candidate_a in candidates.iter().filter(|&c| self.is_relevant(rcvr_ty, c)) {
1056 // Skip this one if we already have one like it
1057 if !relevant_candidates.iter().any(|candidate_b| {
1058 debug!("attempting to merge {} and {}",
1059 candidate_a.repr(self.tcx()),
1060 candidate_b.repr(self.tcx()));
1061 match (&candidate_a.origin, &candidate_b.origin) {
1062 (&MethodParam(ref p1), &MethodParam(ref p2)) => {
1063 let same_trait = p1.trait_id == p2.trait_id;
1064 let same_method = p1.method_num == p2.method_num;
1065 let same_param = p1.param_num == p2.param_num;
1066 // The bound number may be different because
1067 // multiple bounds may lead to the same trait
1069 same_trait && same_method && same_param
1074 relevant_candidates.push(candidate_a.clone());
1081 fn confirm_candidate(&self, rcvr_ty: ty::t, candidate: &Candidate)
1084 // This method performs two sets of substitutions, one after the other:
1085 // 1. Substitute values for any type/lifetime parameters from the impl and
1086 // method declaration into the method type. This is the function type
1087 // before it is called; it may still include late bound region variables.
1088 // 2. Instantiate any late bound lifetime parameters in the method itself
1089 // with fresh region variables.
1091 let tcx = self.tcx();
1093 debug!("confirm_candidate(rcvr_ty={}, candidate={})",
1094 self.ty_to_str(rcvr_ty),
1095 candidate.repr(self.tcx()));
1097 self.enforce_object_limitations(candidate);
1098 self.enforce_drop_trait_limitations(candidate);
1100 // static methods should never have gotten this far:
1101 assert!(candidate.method_ty.explicit_self != SelfStatic);
1103 // Determine the values for the generic parameters of the method.
1104 // If they were not explicitly supplied, just construct fresh
1106 let num_supplied_tps = self.supplied_tps.len();
1107 let num_method_tps = candidate.method_ty.generics.types.len(subst::FnSpace);
1109 if num_supplied_tps == 0u {
1110 self.fcx.infcx().next_ty_vars(num_method_tps)
1111 } else if num_method_tps == 0u {
1114 "this method does not take type parameters");
1115 self.fcx.infcx().next_ty_vars(num_method_tps)
1116 } else if num_supplied_tps != num_method_tps {
1119 "incorrect number of type parameters given for this method");
1120 self.fcx.infcx().next_ty_vars(num_method_tps)
1122 Vec::from_slice(self.supplied_tps)
1126 // Create subst for early-bound lifetime parameters, combining
1127 // parameters from the type and those from the method.
1129 // FIXME -- permit users to manually specify lifetimes
1131 self.fcx.infcx().region_vars_for_defs(
1133 candidate.method_ty.generics.regions.get_vec(subst::FnSpace));
1135 let all_substs = candidate.rcvr_substs.clone().with_method(m_types, m_regions);
1137 let ref bare_fn_ty = candidate.method_ty.fty;
1139 // Compute the method type with type parameters substituted
1140 debug!("fty={} all_substs={}",
1141 bare_fn_ty.repr(tcx),
1142 all_substs.repr(tcx));
1144 let fn_sig = &bare_fn_ty.sig;
1145 let inputs = match candidate.origin {
1146 MethodObject(..) => {
1147 // For annoying reasons, we've already handled the
1148 // substitution of self for object calls.
1149 let args = fn_sig.inputs.slice_from(1).iter().map(|t| {
1150 t.subst(tcx, &all_substs)
1152 Some(*fn_sig.inputs.get(0)).move_iter().chain(args).collect()
1154 _ => fn_sig.inputs.subst(tcx, &all_substs)
1156 let fn_sig = ty::FnSig {
1157 binder_id: fn_sig.binder_id,
1159 output: fn_sig.output.subst(tcx, &all_substs),
1160 variadic: fn_sig.variadic
1163 debug!("after subst, fty={}", fn_sig.repr(tcx));
1165 // Replace any bound regions that appear in the function
1166 // signature with region variables
1167 let (_, fn_sig) = replace_late_bound_regions_in_fn_sig(
1169 |br| self.fcx.infcx().next_region_var(
1170 infer::LateBoundRegion(self.span, br)));
1171 let transformed_self_ty = *fn_sig.inputs.get(0);
1172 let fty = ty::mk_bare_fn(tcx, ty::BareFnTy {
1174 fn_style: bare_fn_ty.fn_style,
1175 abi: bare_fn_ty.abi.clone(),
1177 debug!("after replacing bound regions, fty={}", self.ty_to_str(fty));
1179 // Before, we only checked whether self_ty could be a subtype
1180 // of rcvr_ty; now we actually make it so (this may cause
1181 // variables to unify etc). Since we checked beforehand, and
1182 // nothing has changed in the meantime, this unification
1183 // should never fail.
1184 let span = self.self_expr.map_or(self.span, |e| e.span);
1185 match self.fcx.mk_subty(false, infer::Misc(span),
1186 rcvr_ty, transformed_self_ty) {
1190 "{} was a subtype of {} but now is not?",
1191 self.ty_to_str(rcvr_ty),
1192 self.ty_to_str(transformed_self_ty)).as_slice());
1197 origin: candidate.origin,
1203 fn enforce_object_limitations(&self, candidate: &Candidate) {
1205 * There are some limitations to calling functions through an
1206 * object, because (a) the self type is not known
1207 * (that's the whole point of a trait instance, after all, to
1208 * obscure the self type) and (b) the call must go through a
1209 * vtable and hence cannot be monomorphized.
1212 match candidate.origin {
1213 MethodStatic(..) | MethodParam(..) => {
1214 return; // not a call to a trait instance
1216 MethodObject(..) => {}
1219 match candidate.method_ty.explicit_self {
1220 ast::SelfStatic => { // reason (a) above
1221 self.tcx().sess.span_err(
1223 "cannot call a method without a receiver \
1224 through an object");
1227 ast::SelfValue => { // reason (a) above
1228 self.tcx().sess.span_err(
1230 "cannot call a method with a by-value receiver \
1231 through an object");
1234 ast::SelfRegion(..) | ast::SelfUniq => {}
1238 let check_for_self_ty = |ty| {
1239 if ty::type_has_self(ty) {
1240 self.tcx().sess.span_err(
1242 "cannot call a method whose type contains a \
1243 self-type through an object");
1249 let ref sig = candidate.method_ty.fty.sig;
1250 let mut found_self_ty = false;
1251 for &input_ty in sig.inputs.iter() {
1252 if check_for_self_ty(input_ty) {
1253 found_self_ty = true;
1258 check_for_self_ty(sig.output);
1261 if candidate.method_ty.generics.has_type_params(subst::FnSpace) {
1263 self.tcx().sess.span_err(
1265 "cannot call a generic method through an object");
1269 fn enforce_drop_trait_limitations(&self, candidate: &Candidate) {
1270 // No code can call the finalize method explicitly.
1272 match candidate.origin {
1273 MethodStatic(method_id) => {
1274 bad = self.tcx().destructors.borrow().contains(&method_id);
1276 // FIXME: does this properly enforce this on everything now
1277 // that self has been merged in? -sully
1278 MethodParam(MethodParam { trait_id: trait_id, .. }) |
1279 MethodObject(MethodObject { trait_id: trait_id, .. }) => {
1280 bad = self.tcx().destructor_for_type.borrow()
1281 .contains_key(&trait_id);
1286 self.tcx().sess.span_err(self.span,
1287 "explicit call to destructor");
1291 // `rcvr_ty` is the type of the expression. It may be a subtype of a
1292 // candidate method's `self_ty`.
1293 fn is_relevant(&self, rcvr_ty: ty::t, candidate: &Candidate) -> bool {
1294 debug!("is_relevant(rcvr_ty={}, candidate={})",
1295 self.ty_to_str(rcvr_ty), candidate.repr(self.tcx()));
1297 return match candidate.method_ty.explicit_self {
1299 debug!("(is relevant?) explicit self is static");
1300 self.report_statics == ReportStaticMethods
1304 rcvr_matches_ty(self.fcx, rcvr_ty, candidate)
1307 SelfRegion(_, m) => {
1308 debug!("(is relevant?) explicit self is a region");
1309 match ty::get(rcvr_ty).sty {
1310 ty::ty_rptr(_, mt) => {
1311 match ty::get(mt.ty).sty {
1312 ty::ty_vec(_, None) | ty::ty_str => false,
1313 ty::ty_trait(box ty::TyTrait { def_id: self_did, .. }) => {
1314 mutability_matches(mt.mutbl, m) &&
1315 rcvr_matches_object(self_did, candidate)
1317 _ => mutability_matches(mt.mutbl, m) &&
1318 rcvr_matches_ty(self.fcx, mt.ty, candidate),
1328 debug!("(is relevant?) explicit self is a unique pointer");
1329 match ty::get(rcvr_ty).sty {
1330 ty::ty_uniq(typ) => {
1331 match ty::get(typ).sty {
1332 ty::ty_vec(_, None) | ty::ty_str => false,
1333 ty::ty_trait(box ty::TyTrait { def_id: self_did, .. }) => {
1334 rcvr_matches_object(self_did, candidate)
1336 _ => rcvr_matches_ty(self.fcx, typ, candidate),
1345 fn rcvr_matches_object(self_did: ast::DefId,
1346 candidate: &Candidate) -> bool {
1347 match candidate.rcvr_match_condition {
1348 RcvrMatchesIfObject(desired_did) => {
1349 self_did == desired_did
1351 RcvrMatchesIfSubtype(_) => {
1357 fn rcvr_matches_ty(fcx: &FnCtxt,
1359 candidate: &Candidate) -> bool {
1360 match candidate.rcvr_match_condition {
1361 RcvrMatchesIfObject(_) => {
1364 RcvrMatchesIfSubtype(of_type) => {
1365 fcx.can_mk_subty(rcvr_ty, of_type).is_ok()
1370 fn mutability_matches(self_mutbl: ast::Mutability,
1371 candidate_mutbl: ast::Mutability)
1373 //! True if `self_mutbl <: candidate_mutbl`
1374 self_mutbl == candidate_mutbl
1378 fn report_candidate(&self, idx: uint, origin: &MethodOrigin) {
1380 MethodStatic(impl_did) => {
1381 let did = if self.report_statics == ReportStaticMethods {
1382 // If we're reporting statics, we want to report the trait
1383 // definition if possible, rather than an impl
1384 match ty::trait_method_of_method(self.tcx(), impl_did) {
1385 None => {debug!("(report candidate) No trait method found"); impl_did},
1386 Some(trait_did) => {debug!("(report candidate) Found trait ref"); trait_did}
1389 // If it is an instantiated default method, use the original
1390 // default method for error reporting.
1391 match provided_source(self.tcx(), impl_did) {
1396 self.report_static_candidate(idx, did)
1398 MethodParam(ref mp) => {
1399 self.report_param_candidate(idx, (*mp).trait_id)
1401 MethodObject(ref mo) => {
1402 self.report_trait_candidate(idx, mo.trait_id)
1407 fn report_static_candidate(&self, idx: uint, did: DefId) {
1408 let span = if did.krate == ast::LOCAL_CRATE {
1409 self.tcx().map.span(did.node)
1413 self.tcx().sess.span_note(
1415 format!("candidate #{} is `{}`",
1417 ty::item_path_str(self.tcx(), did)).as_slice());
1420 fn report_param_candidate(&self, idx: uint, did: DefId) {
1421 self.tcx().sess.span_note(
1423 format!("candidate #{} derives from the bound `{}`",
1425 ty::item_path_str(self.tcx(), did)).as_slice());
1428 fn report_trait_candidate(&self, idx: uint, did: DefId) {
1429 self.tcx().sess.span_note(
1431 format!("candidate #{} derives from the type of the receiver, \
1432 which is the trait `{}`",
1434 ty::item_path_str(self.tcx(), did)).as_slice());
1437 fn infcx(&'a self) -> &'a infer::InferCtxt<'a> {
1441 fn tcx(&self) -> &'a ty::ctxt {
1445 fn ty_to_str(&self, t: ty::t) -> String {
1446 self.fcx.infcx().ty_to_str(t)
1449 fn did_to_str(&self, did: DefId) -> String {
1450 ty::item_path_str(self.tcx(), did)
1453 fn bug(&self, s: &str) -> ! {
1454 self.tcx().sess.span_bug(self.span, s)
1458 impl Repr for Candidate {
1459 fn repr(&self, tcx: &ty::ctxt) -> String {
1460 format!("Candidate(rcvr_ty={}, rcvr_substs={}, method_ty={}, \
1462 self.rcvr_match_condition.repr(tcx),
1463 self.rcvr_substs.repr(tcx),
1464 self.method_ty.repr(tcx),
1469 impl Repr for RcvrMatchCondition {
1470 fn repr(&self, tcx: &ty::ctxt) -> String {
1472 RcvrMatchesIfObject(d) => {
1473 format!("RcvrMatchesIfObject({})", d.repr(tcx))
1475 RcvrMatchesIfSubtype(t) => {
1476 format!("RcvrMatchesIfSubtype({})", t.repr(tcx))