1 // Copyright 2012 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.
83 use middle::subst::Subst;
86 use middle::typeck::astconv::AstConv;
87 use middle::typeck::check::{FnCtxt, PreferMutLvalue, impl_self_ty};
88 use middle::typeck::check;
89 use middle::typeck::infer;
90 use middle::typeck::MethodCallee;
91 use middle::typeck::{MethodOrigin, MethodParam};
92 use middle::typeck::{MethodStatic, MethodObject};
93 use middle::typeck::{param_numbered, param_self, param_index};
94 use middle::typeck::check::regionmanip::replace_late_bound_regions_in_fn_sig;
95 use util::common::indenter;
97 use util::ppaux::Repr;
99 use collections::HashSet;
101 use syntax::ast::{DefId, SelfValue, SelfRegion};
102 use syntax::ast::{SelfUniq, SelfStatic};
103 use syntax::ast::{MutMutable, MutImmutable};
105 use syntax::codemap::Span;
106 use syntax::parse::token;
107 use syntax::owned_slice::OwnedSlice;
110 pub enum CheckTraitsFlag {
112 CheckTraitsAndInherentMethods,
116 pub enum AutoderefReceiverFlag {
118 DontAutoderefReceiver,
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: &ty::substs,
237 method_ty: &ty::Method)
240 * This is a bit tricky. We have a match against a trait method
241 * being invoked on an object, and we want to generate the
242 * self-type. As an example, consider a trait
245 * fn r_method<'a>(&'a self);
246 * fn u_method(Box<self>);
249 * Now, assuming that `r_method` is being called, we want the
250 * result to be `&'a Foo`. Assuming that `u_method` is being
251 * called, we want the result to be `Box<Foo>`. Of course,
252 * this transformation has already been done as part of
253 * `method_ty.fty.sig.inputs[0]`, but there the type
254 * is expressed in terms of `Self` (i.e., `&'a Self`, `Box<Self>`).
255 * Because objects are not standalone types, we can't just substitute
256 * `s/Self/Foo/`, so we must instead perform this kind of hokey
260 let substs = ty::substs {regions: rcvr_substs.regions.clone(),
262 tps: rcvr_substs.tps.clone()};
263 match method_ty.explicit_self {
265 tcx.sess.span_bug(span, "static method for object type receiver");
268 ty::mk_err() // error reported in `enforce_object_limitations()`
270 ast::SelfRegion(..) | ast::SelfUniq => {
271 let transformed_self_ty = *method_ty.fty.sig.inputs.get(0);
272 match ty::get(transformed_self_ty).sty {
273 ty::ty_rptr(r, mt) => { // must be SelfRegion
274 let r = r.subst(tcx, &substs); // handle Early-Bound lifetime
275 ty::mk_trait(tcx, trait_def_id, substs,
276 RegionTraitStore(r, mt.mutbl),
277 ty::EmptyBuiltinBounds())
279 ty::ty_uniq(_) => { // must be SelfUniq
280 ty::mk_trait(tcx, trait_def_id, substs,
282 ty::EmptyBuiltinBounds())
285 tcx.sess.span_bug(span,
286 format!("'impossible' transformed_self_ty: {}",
287 transformed_self_ty.repr(tcx)).as_slice());
294 struct LookupContext<'a> {
298 // The receiver to the method call. Only `None` in the case of
299 // an overloaded autoderef, where the receiver may be an intermediate
300 // state like "the expression `x` when it has been autoderef'd
302 self_expr: Option<&'a ast::Expr>,
305 supplied_tps: &'a [ty::t],
306 impl_dups: HashSet<DefId>,
307 inherent_candidates: Vec<Candidate>,
308 extension_candidates: Vec<Candidate>,
309 deref_args: check::DerefArgs,
310 check_traits: CheckTraitsFlag,
311 autoderef_receiver: AutoderefReceiverFlag,
312 report_statics: StaticMethodsFlag,
316 * A potential method that might be called, assuming the receiver
317 * is of a suitable type.
321 rcvr_match_condition: RcvrMatchCondition,
322 rcvr_substs: ty::substs,
323 method_ty: Rc<ty::Method>,
324 origin: MethodOrigin,
327 /// This type represents the conditions under which the receiver is
328 /// considered to "match" a given method candidate. Typically the test
329 /// is whether the receiver is of a particular type. However, this
330 /// type is the type of the receiver *after accounting for the
331 /// method's self type* (e.g., if the method is an `Box<self>` method, we
332 /// have *already verified* that the receiver is of some type `Box<T>` and
333 /// now we must check that the type `T` is correct). Unfortunately,
334 /// because traits are not types, this is a pain to do.
336 pub enum RcvrMatchCondition {
337 RcvrMatchesIfObject(ast::DefId),
338 RcvrMatchesIfSubtype(ty::t)
341 impl<'a> LookupContext<'a> {
342 fn search(&self, self_ty: ty::t) -> Option<MethodCallee> {
343 let span = self.self_expr.map_or(self.span, |e| e.span);
344 let self_expr_id = self.self_expr.map(|e| e.id);
346 let (self_ty, autoderefs, result) =
348 self.fcx, span, self_ty, self_expr_id, PreferMutLvalue,
349 |self_ty, autoderefs| self.search_step(self_ty, autoderefs));
352 Some(Some(result)) => Some(result),
354 if self.is_overloaded_deref() {
355 // If we are searching for an overloaded deref, no
356 // need to try coercing a `~[T]` to an `&[T]` and
357 // searching for an overloaded deref on *that*.
360 self.search_for_autosliced_method(self_ty, autoderefs)
366 fn search_step(&self,
369 -> Option<Option<MethodCallee>> {
370 debug!("search_step: self_ty={} autoderefs={}",
371 self.ty_to_str(self_ty), autoderefs);
373 match self.deref_args {
374 check::DontDerefArgs => {
375 match self.search_for_autoderefd_method(self_ty, autoderefs) {
376 Some(result) => return Some(Some(result)),
380 match self.search_for_autoptrd_method(self_ty, autoderefs) {
381 Some(result) => return Some(Some(result)),
385 check::DoDerefArgs => {
386 match self.search_for_autoptrd_method(self_ty, autoderefs) {
387 Some(result) => return Some(Some(result)),
391 match self.search_for_autoderefd_method(self_ty, autoderefs) {
392 Some(result) => return Some(Some(result)),
398 // Don't autoderef if we aren't supposed to.
399 if self.autoderef_receiver == DontAutoderefReceiver {
406 fn is_overloaded_deref(&self) -> bool {
407 self.self_expr.is_none()
410 // ______________________________________________________________________
411 // Candidate collection (see comment at start of file)
413 fn reset_candidates(&mut self) {
414 self.inherent_candidates = Vec::new();
415 self.extension_candidates = Vec::new();
418 fn push_inherent_candidates(&mut self, self_ty: ty::t) {
420 * Collect all inherent candidates into
421 * `self.inherent_candidates`. See comment at the start of
422 * the file. To find the inherent candidates, we repeatedly
423 * deref the self-ty to find the "base-type". So, for
424 * example, if the receiver is Box<Box<C>> where `C` is a struct type,
425 * we'll want to find the inherent impls for `C`.
428 let span = self.self_expr.map_or(self.span, |e| e.span);
429 check::autoderef(self.fcx, span, self_ty, None, PreferMutLvalue, |self_ty, _| {
430 match get(self_ty).sty {
431 ty_trait(box TyTrait { def_id, ref substs, .. }) => {
432 self.push_inherent_candidates_from_object(def_id, substs);
433 self.push_inherent_impl_candidates_for_type(def_id);
435 ty_enum(did, _) | ty_struct(did, _) => {
436 if self.check_traits == CheckTraitsAndInherentMethods {
437 self.push_inherent_impl_candidates_for_type(did);
440 _ => { /* No inherent methods in these types */ }
443 // Don't autoderef if we aren't supposed to.
444 if self.autoderef_receiver == DontAutoderefReceiver {
452 fn push_bound_candidates(&mut self, self_ty: ty::t, restrict_to: Option<DefId>) {
453 let span = self.self_expr.map_or(self.span, |e| e.span);
454 check::autoderef(self.fcx, span, self_ty, None, PreferMutLvalue, |self_ty, _| {
455 match get(self_ty).sty {
457 self.push_inherent_candidates_from_param(self_ty, restrict_to, p);
460 // Call is of the form "self.foo()" and appears in one
461 // of a trait's default method implementations.
462 self.push_inherent_candidates_from_self(self_ty, restrict_to);
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: &ty::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 {
520 self_ty: Some(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>,
555 param_ty: param_ty) {
556 debug!("push_inherent_candidates_from_param(param_ty={:?})",
558 let i = param_ty.idx;
559 match self.fcx.inh.param_env.type_param_bounds.as_slice().get(i) {
560 Some(b) => self.push_inherent_candidates_from_bounds(
561 rcvr_ty, b.trait_bounds.as_slice(), restrict_to,
562 param_numbered(param_ty.idx)),
568 fn push_inherent_candidates_from_self(&mut self,
570 restrict_to: Option<DefId>) {
571 debug!("push_inherent_candidates_from_self()");
572 self.push_inherent_candidates_from_bounds(
574 [self.fcx.inh.param_env.self_param_bound.clone().unwrap()],
579 fn push_inherent_candidates_from_bounds(&mut self,
581 bounds: &[Rc<TraitRef>],
582 restrict_to: Option<DefId>,
583 param: param_index) {
584 self.push_inherent_candidates_from_bounds_inner(bounds,
585 |trait_ref, m, method_num, bound_num| {
588 if trait_did != trait_ref.def_id {
595 rcvr_match_condition: RcvrMatchesIfSubtype(self_ty),
596 rcvr_substs: trait_ref.substs.clone(),
598 origin: MethodParam(MethodParam {
599 trait_id: trait_ref.def_id,
600 method_num: method_num,
602 bound_num: bound_num,
608 // Do a search through a list of bounds, using a callback to actually
609 // create the candidates.
610 fn push_inherent_candidates_from_bounds_inner(&mut self,
611 bounds: &[Rc<TraitRef>],
612 mk_cand: |tr: Rc<TraitRef>,
616 -> Option<Candidate>) {
617 let tcx = self.tcx();
618 let mut next_bound_idx = 0; // count only trait bounds
620 ty::each_bound_trait_and_supertraits(tcx, bounds, |bound_trait_ref| {
621 let this_bound_idx = next_bound_idx;
624 let trait_methods = ty::trait_methods(tcx, bound_trait_ref.def_id);
625 match trait_methods.iter().position(|m| {
626 m.explicit_self != ast::SelfStatic &&
627 m.ident.name == self.m_name }) {
629 let method = trait_methods.get(pos).clone();
631 match mk_cand(bound_trait_ref, method, pos, this_bound_idx) {
633 debug!("pushing inherent candidate for param: {}",
634 cand.repr(self.tcx()));
635 self.inherent_candidates.push(cand);
641 debug!("trait doesn't contain method: {:?}",
642 bound_trait_ref.def_id);
643 // check next trait or bound
651 fn push_inherent_impl_candidates_for_type(&mut self, did: DefId) {
652 // Read the inherent implementation candidates for this type from the
653 // metadata if necessary.
654 ty::populate_implementations_for_type_if_necessary(self.tcx(), did);
656 let impl_methods = self.tcx().impl_methods.borrow();
657 for impl_infos in self.tcx().inherent_impls.borrow().find(&did).iter() {
658 for impl_did in impl_infos.borrow().iter() {
659 let methods = impl_methods.get(impl_did);
660 self.push_candidates_from_impl(*impl_did, methods.as_slice(), false);
665 fn push_candidates_from_impl(&mut self,
667 impl_methods: &[DefId],
668 is_extension: bool) {
669 let did = if self.report_statics == ReportStaticMethods {
670 // we only want to report each base trait once
671 match ty::impl_trait_ref(self.tcx(), impl_did) {
672 Some(trait_ref) => trait_ref.def_id,
679 if !self.impl_dups.insert(did) {
680 return; // already visited
683 debug!("push_candidates_from_impl: {} {}",
684 token::get_name(self.m_name),
685 impl_methods.iter().map(|&did| ty::method(self.tcx(), did).ident)
686 .collect::<Vec<ast::Ident>>()
689 let method = match impl_methods.iter().map(|&did| ty::method(self.tcx(), did))
690 .find(|m| m.ident.name == self.m_name) {
691 Some(method) => method,
692 None => { return; } // No method with the right name.
695 // determine the `self` of the impl with fresh
696 // variables for each parameter:
697 let span = self.self_expr.map_or(self.span, |e| e.span);
698 let vcx = self.fcx.vtable_context();
699 let ty::ty_param_substs_and_ty {
702 } = impl_self_ty(&vcx, span, impl_did);
704 let candidates = if is_extension {
705 &mut self.extension_candidates
707 &mut self.inherent_candidates
710 candidates.push(Candidate {
711 rcvr_match_condition: RcvrMatchesIfSubtype(impl_ty),
712 rcvr_substs: impl_substs,
713 origin: MethodStatic(method.def_id),
718 // ______________________________________________________________________
719 // Candidate selection (see comment at start of file)
721 fn search_for_autoderefd_method(&self,
724 -> Option<MethodCallee> {
725 let (self_ty, auto_deref_ref) =
726 self.consider_reborrow(self_ty, autoderefs);
728 // Hacky. For overloaded derefs, there may be an adjustment
729 // added to the expression from the outside context, so we do not store
730 // an explicit adjustment, but rather we hardwire the single deref
731 // that occurs in trans and mem_categorization.
732 let adjustment = match self.self_expr {
733 Some(expr) => Some((expr.id, ty::AutoDerefRef(auto_deref_ref))),
737 match self.search_for_method(self_ty) {
740 debug!("(searching for autoderef'd method) writing \
741 adjustment {:?} for {}", adjustment, self.ty_to_str( self_ty));
743 Some((self_expr_id, adj)) => {
744 self.fcx.write_adjustment(self_expr_id, adj);
753 fn consider_reborrow(&self,
756 -> (ty::t, ty::AutoDerefRef) {
758 * In the event that we are invoking a method with a receiver
759 * of a borrowed type like `&T`, `&mut T`, or `&mut [T]`,
760 * we will "reborrow" the receiver implicitly. For example, if
761 * you have a call `r.inc()` and where `r` has type `&mut T`,
762 * then we treat that like `(&mut *r).inc()`. This avoids
763 * consuming the original pointer.
765 * You might think that this would be a natural byproduct of
766 * the auto-deref/auto-ref process. This is true for `Box<T>`
767 * but not for an `&mut T` receiver. With `Box<T>`, we would
768 * begin by testing for methods with a self type `Box<T>`,
769 * then autoderef to `T`, then autoref to `&mut T`. But with
770 * an `&mut T` receiver the process begins with `&mut T`, only
771 * without any autoadjustments.
774 let tcx = self.tcx();
775 return match ty::get(self_ty).sty {
776 ty::ty_rptr(_, self_mt) if default_method_hack(self_mt) => {
779 autoderefs: autoderefs,
782 ty::ty_rptr(_, self_mt) => {
784 self.infcx().next_region_var(infer::Autoref(self.span));
785 let (extra_derefs, auto) = match ty::get(self_mt.ty).sty {
786 ty::ty_vec(_, None) => (0, ty::AutoBorrowVec(region, self_mt.mutbl)),
787 ty::ty_str => (0, ty::AutoBorrowVec(region, self_mt.mutbl)),
788 _ => (1, ty::AutoPtr(region, self_mt.mutbl)),
790 (ty::mk_rptr(tcx, region, self_mt),
792 autoderefs: autoderefs + extra_derefs,
793 autoref: Some(auto)})
796 ty::ty_trait(box ty::TyTrait {
797 def_id, ref substs, store: ty::RegionTraitStore(_, mutbl), bounds
800 self.infcx().next_region_var(infer::Autoref(self.span));
801 (ty::mk_trait(tcx, def_id, substs.clone(),
802 ty::RegionTraitStore(region, mutbl), bounds),
804 autoderefs: autoderefs,
805 autoref: Some(ty::AutoBorrowObj(region, mutbl))})
810 autoderefs: autoderefs,
815 fn default_method_hack(self_mt: ty::mt) -> bool {
816 // FIXME(#6129). Default methods can't deal with autoref.
818 // I am a horrible monster and I pray for death. Currently
819 // the default method code fails when you try to reborrow
820 // because it is not handling types correctly. In lieu of
821 // fixing that, I am introducing this horrible hack. - ndm
822 self_mt.mutbl == MutImmutable && ty::type_is_self(self_mt.ty)
826 fn auto_slice_vec(&self, mt: ty::mt, autoderefs: uint) -> Option<MethodCallee> {
827 let tcx = self.tcx();
828 debug!("auto_slice_vec {}", ppaux::ty_to_str(tcx, mt.ty));
830 // First try to borrow to a slice
831 let entry = self.search_for_some_kind_of_autorefd_method(
832 AutoBorrowVec, autoderefs, [MutImmutable, MutMutable],
833 |m,r| ty::mk_slice(tcx, r,
834 ty::mt {ty:mt.ty, mutbl:m}));
840 // Then try to borrow to a slice *and* borrow a pointer.
841 self.search_for_some_kind_of_autorefd_method(
842 AutoBorrowVecRef, autoderefs, [MutImmutable, MutMutable],
844 let slice_ty = ty::mk_slice(tcx, r,
845 ty::mt {ty:mt.ty, mutbl:m});
846 // NB: we do not try to autoref to a mutable
847 // pointer. That would be creating a pointer
848 // to a temporary pointer (the borrowed
849 // slice), so any update the callee makes to
850 // it can't be observed.
851 ty::mk_rptr(tcx, r, ty::mt {ty:slice_ty, mutbl:MutImmutable})
856 fn auto_slice_str(&self, autoderefs: uint) -> Option<MethodCallee> {
857 let tcx = self.tcx();
858 debug!("auto_slice_str");
860 let entry = self.search_for_some_kind_of_autorefd_method(
861 AutoBorrowVec, autoderefs, [MutImmutable],
862 |_m,r| ty::mk_str_slice(tcx, r, MutImmutable));
868 self.search_for_some_kind_of_autorefd_method(
869 AutoBorrowVecRef, autoderefs, [MutImmutable],
871 let slice_ty = ty::mk_str_slice(tcx, r, m);
872 ty::mk_rptr(tcx, r, ty::mt {ty:slice_ty, mutbl:m})
876 fn search_for_autosliced_method(&self,
879 -> Option<MethodCallee> {
881 * Searches for a candidate by converting things like
885 let tcx = self.tcx();
886 debug!("search_for_autosliced_method {}", ppaux::ty_to_str(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),
894 ty_uniq(t) => match ty::get(t).sty {
895 ty_vec(mt, None) => self.auto_slice_vec(mt, autoderefs),
896 ty_str => self.auto_slice_str(autoderefs),
899 ty_vec(mt, Some(_)) => self.auto_slice_vec(mt, autoderefs),
901 ty_trait(box ty::TyTrait {
907 // Coerce Box/&Trait instances to &Trait.
909 self.search_for_some_kind_of_autorefd_method(
910 AutoBorrowObj, autoderefs, [MutImmutable, MutMutable],
912 ty::mk_trait(tcx, trt_did, trt_substs.clone(),
913 RegionTraitStore(r, m), b)
918 // This case should probably be handled similarly to
927 fn search_for_autoptrd_method(&self, self_ty: ty::t, autoderefs: uint)
928 -> Option<MethodCallee> {
931 * Converts any type `T` to `&M T` where `M` is an
932 * appropriate mutability.
935 let tcx = self.tcx();
936 match ty::get(self_ty).sty {
937 ty_bare_fn(..) | ty_box(..) | ty_uniq(..) | ty_rptr(..) |
938 ty_infer(IntVar(_)) |
939 ty_infer(FloatVar(_)) |
940 ty_self(_) | ty_param(..) | ty_nil | ty_bot | ty_bool |
941 ty_char | ty_int(..) | ty_uint(..) |
942 ty_float(..) | ty_enum(..) | ty_ptr(..) | ty_struct(..) | ty_tup(..) |
943 ty_str | ty_vec(..) | ty_trait(..) | ty_closure(..) => {
944 self.search_for_some_kind_of_autorefd_method(
945 AutoPtr, autoderefs, [MutImmutable, MutMutable],
946 |m,r| ty::mk_rptr(tcx, r, ty::mt {ty:self_ty, mutbl:m}))
951 ty_infer(TyVar(_)) => {
952 self.bug(format!("unexpected type: {}",
953 self.ty_to_str(self_ty)).as_slice());
958 fn search_for_some_kind_of_autorefd_method(
960 kind: |Region, ast::Mutability| -> ty::AutoRef,
962 mutbls: &[ast::Mutability],
963 mk_autoref_ty: |ast::Mutability, ty::Region| -> ty::t)
964 -> Option<MethodCallee> {
965 // Hacky. For overloaded derefs, there may be an adjustment
966 // added to the expression from the outside context, so we do not store
967 // an explicit adjustment, but rather we hardwire the single deref
968 // that occurs in trans and mem_categorization.
969 let self_expr_id = match self.self_expr {
970 Some(expr) => Some(expr.id),
972 assert_eq!(autoderefs, 0);
973 assert_eq!(kind(ty::ReEmpty, ast::MutImmutable),
974 ty::AutoPtr(ty::ReEmpty, ast::MutImmutable));
979 // This is hokey. We should have mutability inference as a
980 // variable. But for now, try &const, then &, then &mut:
982 self.infcx().next_region_var(infer::Autoref(self.span));
983 for mutbl in mutbls.iter() {
984 let autoref_ty = mk_autoref_ty(*mutbl, region);
985 match self.search_for_method(autoref_ty) {
989 Some(self_expr_id) => {
990 self.fcx.write_adjustment(
992 ty::AutoDerefRef(ty::AutoDerefRef {
993 autoderefs: autoderefs,
994 autoref: Some(kind(region, *mutbl))
1006 fn search_for_method(&self, rcvr_ty: ty::t) -> Option<MethodCallee> {
1007 debug!("search_for_method(rcvr_ty={})", self.ty_to_str(rcvr_ty));
1008 let _indenter = indenter();
1010 // I am not sure that inherent methods should have higher
1011 // priority, but it is necessary ATM to handle some of the
1014 debug!("searching inherent candidates");
1015 match self.consider_candidates(rcvr_ty, self.inherent_candidates.as_slice()) {
1022 debug!("searching extension candidates");
1023 self.consider_candidates(rcvr_ty, self.extension_candidates.as_slice())
1026 fn consider_candidates(&self, rcvr_ty: ty::t,
1027 candidates: &[Candidate])
1028 -> Option<MethodCallee> {
1029 // FIXME(pcwalton): Do we need to clone here?
1030 let relevant_candidates: Vec<Candidate> =
1031 candidates.iter().map(|c| (*c).clone()).
1032 filter(|c| self.is_relevant(rcvr_ty, c)).collect();
1034 let relevant_candidates =
1035 self.merge_candidates(relevant_candidates.as_slice());
1037 if relevant_candidates.len() == 0 {
1041 if self.report_statics == ReportStaticMethods {
1042 // lookup should only be called with ReportStaticMethods if a regular lookup failed
1043 assert!(relevant_candidates.iter().all(|c| c.method_ty.explicit_self == SelfStatic));
1045 self.tcx().sess.fileline_note(self.span,
1046 "found defined static methods, maybe a `self` is missing?");
1048 for (idx, candidate) in relevant_candidates.iter().enumerate() {
1049 self.report_candidate(idx, &candidate.origin);
1052 // return something so we don't get errors for every mutability
1053 return Some(MethodCallee {
1054 origin: relevant_candidates.get(0).origin,
1056 substs: substs::empty()
1060 if relevant_candidates.len() > 1 {
1061 self.tcx().sess.span_err(
1063 "multiple applicable methods in scope");
1064 for (idx, candidate) in relevant_candidates.iter().enumerate() {
1065 self.report_candidate(idx, &candidate.origin);
1069 Some(self.confirm_candidate(rcvr_ty, relevant_candidates.get(0)))
1072 fn merge_candidates(&self, candidates: &[Candidate]) -> Vec<Candidate> {
1073 let mut merged = Vec::new();
1075 while i < candidates.len() {
1076 let candidate_a = &candidates[i];
1078 let mut skip = false;
1081 while j < candidates.len() {
1082 let candidate_b = &candidates[j];
1083 debug!("attempting to merge {} and {}",
1084 candidate_a.repr(self.tcx()),
1085 candidate_b.repr(self.tcx()));
1086 let candidates_same = match (&candidate_a.origin,
1087 &candidate_b.origin) {
1088 (&MethodParam(ref p1), &MethodParam(ref p2)) => {
1089 let same_trait = p1.trait_id == p2.trait_id;
1090 let same_method = p1.method_num == p2.method_num;
1091 let same_param = p1.param_num == p2.param_num;
1092 // The bound number may be different because
1093 // multiple bounds may lead to the same trait
1095 same_trait && same_method && same_param
1099 if candidates_same {
1109 // There are more than one of these and we need only one
1112 merged.push(candidate_a.clone());
1119 fn confirm_candidate(&self, rcvr_ty: ty::t, candidate: &Candidate)
1121 // This method performs two sets of substitutions, one after the other:
1122 // 1. Substitute values for any type/lifetime parameters from the impl and
1123 // method declaration into the method type. This is the function type
1124 // before it is called; it may still include late bound region variables.
1125 // 2. Instantiate any late bound lifetime parameters in the method itself
1126 // with fresh region variables.
1128 let tcx = self.tcx();
1130 debug!("confirm_candidate(rcvr_ty={}, candidate={})",
1131 self.ty_to_str(rcvr_ty),
1132 candidate.repr(self.tcx()));
1134 self.enforce_object_limitations(candidate);
1135 self.enforce_drop_trait_limitations(candidate);
1137 // static methods should never have gotten this far:
1138 assert!(candidate.method_ty.explicit_self != SelfStatic);
1140 // Determine the values for the generic parameters of the method.
1141 // If they were not explicitly supplied, just construct fresh
1143 let num_supplied_tps = self.supplied_tps.len();
1144 let num_method_tps = candidate.method_ty.generics.type_param_defs().len();
1146 if num_supplied_tps == 0u {
1147 self.fcx.infcx().next_ty_vars(num_method_tps)
1148 } else if num_method_tps == 0u {
1151 "this method does not take type parameters");
1152 self.fcx.infcx().next_ty_vars(num_method_tps)
1153 } else if num_supplied_tps != num_method_tps {
1156 "incorrect number of type \
1157 parameters given for this method");
1158 self.fcx.infcx().next_ty_vars(num_method_tps)
1160 Vec::from_slice(self.supplied_tps)
1164 // Determine values for the early-bound lifetime parameters.
1165 // FIXME -- permit users to manually specify lifetimes
1166 let mut all_regions: Vec<Region> = match candidate.rcvr_substs.regions {
1167 NonerasedRegions(ref v) => v.iter().map(|r| r.clone()).collect(),
1168 ErasedRegions => tcx.sess.span_bug(self.span, "ErasedRegions")
1171 self.fcx.infcx().region_vars_for_defs(
1173 candidate.method_ty.generics.region_param_defs.as_slice());
1174 for &r in m_regions.iter() {
1175 all_regions.push(r);
1178 // Construct the full set of type parameters for the method,
1179 // which is equal to the class tps + the method tps.
1180 let all_substs = substs {
1181 tps: candidate.rcvr_substs.tps.clone().append(m_substs.as_slice()),
1182 regions: NonerasedRegions(OwnedSlice::from_vec(all_regions)),
1183 self_ty: candidate.rcvr_substs.self_ty,
1186 let ref bare_fn_ty = candidate.method_ty.fty;
1188 // Compute the method type with type parameters substituted
1189 debug!("fty={} all_substs={}",
1190 bare_fn_ty.repr(tcx),
1191 ty::substs_to_str(tcx, &all_substs));
1193 let fn_sig = &bare_fn_ty.sig;
1194 let inputs = match candidate.origin {
1195 MethodObject(..) => {
1196 // For annoying reasons, we've already handled the
1197 // substitution of self for object calls.
1198 let args = fn_sig.inputs.slice_from(1).iter().map(|t| {
1199 t.subst(tcx, &all_substs)
1201 Some(*fn_sig.inputs.get(0)).move_iter().chain(args).collect()
1203 _ => fn_sig.inputs.subst(tcx, &all_substs)
1205 let fn_sig = ty::FnSig {
1206 binder_id: fn_sig.binder_id,
1208 output: fn_sig.output.subst(tcx, &all_substs),
1209 variadic: fn_sig.variadic
1212 debug!("after subst, fty={}", fn_sig.repr(tcx));
1214 // Replace any bound regions that appear in the function
1215 // signature with region variables
1216 let (_, fn_sig) = replace_late_bound_regions_in_fn_sig(
1218 |br| self.fcx.infcx().next_region_var(
1219 infer::LateBoundRegion(self.span, br)));
1220 let transformed_self_ty = *fn_sig.inputs.get(0);
1221 let fty = ty::mk_bare_fn(tcx, ty::BareFnTy {
1223 fn_style: bare_fn_ty.fn_style,
1224 abi: bare_fn_ty.abi.clone(),
1226 debug!("after replacing bound regions, fty={}", self.ty_to_str(fty));
1228 // Before, we only checked whether self_ty could be a subtype
1229 // of rcvr_ty; now we actually make it so (this may cause
1230 // variables to unify etc). Since we checked beforehand, and
1231 // nothing has changed in the meantime, this unification
1232 // should never fail.
1233 let span = self.self_expr.map_or(self.span, |e| e.span);
1234 match self.fcx.mk_subty(false, infer::Misc(span),
1235 rcvr_ty, transformed_self_ty) {
1239 "{} was a subtype of {} but now is not?",
1240 self.ty_to_str(rcvr_ty),
1241 self.ty_to_str(transformed_self_ty)).as_slice());
1246 origin: candidate.origin,
1252 fn enforce_object_limitations(&self, candidate: &Candidate) {
1254 * There are some limitations to calling functions through an
1255 * object, because (a) the self type is not known
1256 * (that's the whole point of a trait instance, after all, to
1257 * obscure the self type) and (b) the call must go through a
1258 * vtable and hence cannot be monomorphized.
1261 match candidate.origin {
1262 MethodStatic(..) | MethodParam(..) => {
1263 return; // not a call to a trait instance
1265 MethodObject(..) => {}
1268 match candidate.method_ty.explicit_self {
1269 ast::SelfStatic => { // reason (a) above
1270 self.tcx().sess.span_err(
1272 "cannot call a method without a receiver \
1273 through an object");
1276 ast::SelfValue => { // reason (a) above
1277 self.tcx().sess.span_err(
1279 "cannot call a method with a by-value receiver \
1280 through an object");
1283 ast::SelfRegion(..) | ast::SelfUniq => {}
1287 let check_for_self_ty = |ty| {
1288 if ty::type_has_self(ty) {
1289 self.tcx().sess.span_err(
1291 "cannot call a method whose type contains a \
1292 self-type through an object");
1298 let ref sig = candidate.method_ty.fty.sig;
1299 let mut found_self_ty = false;
1300 for &input_ty in sig.inputs.iter() {
1301 if check_for_self_ty(input_ty) {
1302 found_self_ty = true;
1307 check_for_self_ty(sig.output);
1310 if candidate.method_ty.generics.has_type_params() { // reason (b) above
1311 self.tcx().sess.span_err(
1313 "cannot call a generic method through an object");
1317 fn enforce_drop_trait_limitations(&self, candidate: &Candidate) {
1318 // No code can call the finalize method explicitly.
1320 match candidate.origin {
1321 MethodStatic(method_id) => {
1322 bad = self.tcx().destructors.borrow().contains(&method_id);
1324 // FIXME: does this properly enforce this on everything now
1325 // that self has been merged in? -sully
1326 MethodParam(MethodParam { trait_id: trait_id, .. }) |
1327 MethodObject(MethodObject { trait_id: trait_id, .. }) => {
1328 bad = self.tcx().destructor_for_type.borrow()
1329 .contains_key(&trait_id);
1334 self.tcx().sess.span_err(self.span,
1335 "explicit call to destructor");
1339 // `rcvr_ty` is the type of the expression. It may be a subtype of a
1340 // candidate method's `self_ty`.
1341 fn is_relevant(&self, rcvr_ty: ty::t, candidate: &Candidate) -> bool {
1342 debug!("is_relevant(rcvr_ty={}, candidate={})",
1343 self.ty_to_str(rcvr_ty), candidate.repr(self.tcx()));
1345 return match candidate.method_ty.explicit_self {
1347 debug!("(is relevant?) explicit self is static");
1348 self.report_statics == ReportStaticMethods
1352 rcvr_matches_ty(self.fcx, rcvr_ty, candidate)
1355 SelfRegion(_, m) => {
1356 debug!("(is relevant?) explicit self is a region");
1357 match ty::get(rcvr_ty).sty {
1358 ty::ty_rptr(_, mt) => {
1359 match ty::get(mt.ty).sty {
1360 ty::ty_vec(_, None) | ty::ty_str => false,
1361 _ => mutability_matches(mt.mutbl, m) &&
1362 rcvr_matches_ty(self.fcx, mt.ty, candidate),
1366 ty::ty_trait(box ty::TyTrait {
1367 def_id: self_did, store: RegionTraitStore(_, self_m), ..
1369 mutability_matches(self_m, m) &&
1370 rcvr_matches_object(self_did, candidate)
1378 debug!("(is relevant?) explicit self is a unique pointer");
1379 match ty::get(rcvr_ty).sty {
1380 ty::ty_uniq(typ) => {
1381 match ty::get(typ).sty {
1382 ty::ty_vec(_, None) | ty::ty_str => false,
1383 _ => rcvr_matches_ty(self.fcx, typ, candidate),
1387 ty::ty_trait(box ty::TyTrait {
1388 def_id: self_did, store: UniqTraitStore, ..
1390 rcvr_matches_object(self_did, candidate)
1398 fn rcvr_matches_object(self_did: ast::DefId,
1399 candidate: &Candidate) -> bool {
1400 match candidate.rcvr_match_condition {
1401 RcvrMatchesIfObject(desired_did) => {
1402 self_did == desired_did
1404 RcvrMatchesIfSubtype(_) => {
1410 fn rcvr_matches_ty(fcx: &FnCtxt,
1412 candidate: &Candidate) -> bool {
1413 match candidate.rcvr_match_condition {
1414 RcvrMatchesIfObject(_) => {
1417 RcvrMatchesIfSubtype(of_type) => {
1418 fcx.can_mk_subty(rcvr_ty, of_type).is_ok()
1423 fn mutability_matches(self_mutbl: ast::Mutability,
1424 candidate_mutbl: ast::Mutability)
1426 //! True if `self_mutbl <: candidate_mutbl`
1427 self_mutbl == candidate_mutbl
1431 fn report_candidate(&self, idx: uint, origin: &MethodOrigin) {
1433 MethodStatic(impl_did) => {
1434 let did = if self.report_statics == ReportStaticMethods {
1435 // If we're reporting statics, we want to report the trait
1436 // definition if possible, rather than an impl
1437 match ty::trait_method_of_method(self.tcx(), impl_did) {
1438 None => {debug!("(report candidate) No trait method found"); impl_did},
1439 Some(trait_did) => {debug!("(report candidate) Found trait ref"); trait_did}
1442 // If it is an instantiated default method, use the original
1443 // default method for error reporting.
1444 match provided_source(self.tcx(), impl_did) {
1449 self.report_static_candidate(idx, did)
1451 MethodParam(ref mp) => {
1452 self.report_param_candidate(idx, (*mp).trait_id)
1454 MethodObject(ref mo) => {
1455 self.report_trait_candidate(idx, mo.trait_id)
1460 fn report_static_candidate(&self, idx: uint, did: DefId) {
1461 let span = if did.krate == ast::LOCAL_CRATE {
1462 self.tcx().map.span(did.node)
1466 self.tcx().sess.span_note(
1468 format!("candidate \\#{} is `{}`",
1470 ty::item_path_str(self.tcx(), did)).as_slice());
1473 fn report_param_candidate(&self, idx: uint, did: DefId) {
1474 self.tcx().sess.span_note(
1476 format!("candidate \\#{} derives from the bound `{}`",
1478 ty::item_path_str(self.tcx(), did)).as_slice());
1481 fn report_trait_candidate(&self, idx: uint, did: DefId) {
1482 self.tcx().sess.span_note(
1484 format!("candidate \\#{} derives from the type of the receiver, \
1485 which is the trait `{}`",
1487 ty::item_path_str(self.tcx(), did)).as_slice());
1490 fn infcx(&'a self) -> &'a infer::InferCtxt<'a> {
1494 fn tcx(&self) -> &'a ty::ctxt {
1498 fn ty_to_str(&self, t: ty::t) -> String {
1499 self.fcx.infcx().ty_to_str(t)
1502 fn did_to_str(&self, did: DefId) -> String {
1503 ty::item_path_str(self.tcx(), did)
1506 fn bug(&self, s: &str) -> ! {
1507 self.tcx().sess.span_bug(self.span, s)
1511 impl Repr for Candidate {
1512 fn repr(&self, tcx: &ty::ctxt) -> String {
1513 format_strbuf!("Candidate(rcvr_ty={}, rcvr_substs={}, method_ty={}, \
1515 self.rcvr_match_condition.repr(tcx),
1516 self.rcvr_substs.repr(tcx),
1517 self.method_ty.repr(tcx),
1522 impl Repr for RcvrMatchCondition {
1523 fn repr(&self, tcx: &ty::ctxt) -> String {
1525 RcvrMatchesIfObject(d) => {
1526 format_strbuf!("RcvrMatchesIfObject({})", d.repr(tcx))
1528 RcvrMatchesIfSubtype(t) => {
1529 format_strbuf!("RcvrMatchesIfSubtype({})", t.repr(tcx))