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.
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;
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: &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::empty_builtin_bounds())
279 ty::ty_uniq(_) => { // must be SelfUniq
280 ty::mk_trait(tcx, trait_def_id, substs,
282 ty::empty_builtin_bounds())
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 let relevant_candidates = self.filter_candidates(rcvr_ty, candidates);
1031 if relevant_candidates.len() == 0 {
1035 if self.report_statics == ReportStaticMethods {
1036 // lookup should only be called with ReportStaticMethods if a regular lookup failed
1037 assert!(relevant_candidates.iter().all(|c| c.method_ty.explicit_self == SelfStatic));
1039 self.tcx().sess.fileline_note(self.span,
1040 "found defined static methods, maybe a `self` is missing?");
1042 for (idx, candidate) in relevant_candidates.iter().enumerate() {
1043 self.report_candidate(idx, &candidate.origin);
1046 // return something so we don't get errors for every mutability
1047 return Some(MethodCallee {
1048 origin: relevant_candidates.get(0).origin,
1050 substs: substs::empty()
1054 if relevant_candidates.len() > 1 {
1055 self.tcx().sess.span_err(
1057 "multiple applicable methods in scope");
1058 for (idx, candidate) in relevant_candidates.iter().enumerate() {
1059 self.report_candidate(idx, &candidate.origin);
1063 Some(self.confirm_candidate(rcvr_ty, relevant_candidates.get(0)))
1066 fn filter_candidates(&self, rcvr_ty: ty::t, candidates: &[Candidate]) -> Vec<Candidate> {
1067 let mut relevant_candidates: Vec<Candidate> = Vec::new();
1069 for candidate_a in candidates.iter().filter(|&c| self.is_relevant(rcvr_ty, c)) {
1070 // Skip this one if we already have one like it
1071 if !relevant_candidates.iter().any(|candidate_b| {
1072 debug!("attempting to merge {} and {}",
1073 candidate_a.repr(self.tcx()),
1074 candidate_b.repr(self.tcx()));
1075 match (&candidate_a.origin, &candidate_b.origin) {
1076 (&MethodParam(ref p1), &MethodParam(ref p2)) => {
1077 let same_trait = p1.trait_id == p2.trait_id;
1078 let same_method = p1.method_num == p2.method_num;
1079 let same_param = p1.param_num == p2.param_num;
1080 // The bound number may be different because
1081 // multiple bounds may lead to the same trait
1083 same_trait && same_method && same_param
1088 relevant_candidates.push(candidate_a.clone());
1095 fn confirm_candidate(&self, rcvr_ty: ty::t, candidate: &Candidate)
1097 // This method performs two sets of substitutions, one after the other:
1098 // 1. Substitute values for any type/lifetime parameters from the impl and
1099 // method declaration into the method type. This is the function type
1100 // before it is called; it may still include late bound region variables.
1101 // 2. Instantiate any late bound lifetime parameters in the method itself
1102 // with fresh region variables.
1104 let tcx = self.tcx();
1106 debug!("confirm_candidate(rcvr_ty={}, candidate={})",
1107 self.ty_to_str(rcvr_ty),
1108 candidate.repr(self.tcx()));
1110 self.enforce_object_limitations(candidate);
1111 self.enforce_drop_trait_limitations(candidate);
1113 // static methods should never have gotten this far:
1114 assert!(candidate.method_ty.explicit_self != SelfStatic);
1116 // Determine the values for the generic parameters of the method.
1117 // If they were not explicitly supplied, just construct fresh
1119 let num_supplied_tps = self.supplied_tps.len();
1120 let num_method_tps = candidate.method_ty.generics.type_param_defs().len();
1122 if num_supplied_tps == 0u {
1123 self.fcx.infcx().next_ty_vars(num_method_tps)
1124 } else if num_method_tps == 0u {
1127 "this method does not take type parameters");
1128 self.fcx.infcx().next_ty_vars(num_method_tps)
1129 } else if num_supplied_tps != num_method_tps {
1132 "incorrect number of type \
1133 parameters given for this method");
1134 self.fcx.infcx().next_ty_vars(num_method_tps)
1136 Vec::from_slice(self.supplied_tps)
1140 // Determine values for the early-bound lifetime parameters.
1141 // FIXME -- permit users to manually specify lifetimes
1142 let mut all_regions: Vec<Region> = match candidate.rcvr_substs.regions {
1143 NonerasedRegions(ref v) => v.iter().map(|r| r.clone()).collect(),
1144 ErasedRegions => tcx.sess.span_bug(self.span, "ErasedRegions")
1147 self.fcx.infcx().region_vars_for_defs(
1149 candidate.method_ty.generics.region_param_defs.as_slice());
1150 for &r in m_regions.iter() {
1151 all_regions.push(r);
1154 // Construct the full set of type parameters for the method,
1155 // which is equal to the class tps + the method tps.
1156 let all_substs = substs {
1157 tps: candidate.rcvr_substs.tps.clone().append(m_substs.as_slice()),
1158 regions: NonerasedRegions(OwnedSlice::from_vec(all_regions)),
1159 self_ty: candidate.rcvr_substs.self_ty,
1162 let ref bare_fn_ty = candidate.method_ty.fty;
1164 // Compute the method type with type parameters substituted
1165 debug!("fty={} all_substs={}",
1166 bare_fn_ty.repr(tcx),
1167 ty::substs_to_str(tcx, &all_substs));
1169 let fn_sig = &bare_fn_ty.sig;
1170 let inputs = match candidate.origin {
1171 MethodObject(..) => {
1172 // For annoying reasons, we've already handled the
1173 // substitution of self for object calls.
1174 let args = fn_sig.inputs.slice_from(1).iter().map(|t| {
1175 t.subst(tcx, &all_substs)
1177 Some(*fn_sig.inputs.get(0)).move_iter().chain(args).collect()
1179 _ => fn_sig.inputs.subst(tcx, &all_substs)
1181 let fn_sig = ty::FnSig {
1182 binder_id: fn_sig.binder_id,
1184 output: fn_sig.output.subst(tcx, &all_substs),
1185 variadic: fn_sig.variadic
1188 debug!("after subst, fty={}", fn_sig.repr(tcx));
1190 // Replace any bound regions that appear in the function
1191 // signature with region variables
1192 let (_, fn_sig) = replace_late_bound_regions_in_fn_sig(
1194 |br| self.fcx.infcx().next_region_var(
1195 infer::LateBoundRegion(self.span, br)));
1196 let transformed_self_ty = *fn_sig.inputs.get(0);
1197 let fty = ty::mk_bare_fn(tcx, ty::BareFnTy {
1199 fn_style: bare_fn_ty.fn_style,
1200 abi: bare_fn_ty.abi.clone(),
1202 debug!("after replacing bound regions, fty={}", self.ty_to_str(fty));
1204 // Before, we only checked whether self_ty could be a subtype
1205 // of rcvr_ty; now we actually make it so (this may cause
1206 // variables to unify etc). Since we checked beforehand, and
1207 // nothing has changed in the meantime, this unification
1208 // should never fail.
1209 let span = self.self_expr.map_or(self.span, |e| e.span);
1210 match self.fcx.mk_subty(false, infer::Misc(span),
1211 rcvr_ty, transformed_self_ty) {
1215 "{} was a subtype of {} but now is not?",
1216 self.ty_to_str(rcvr_ty),
1217 self.ty_to_str(transformed_self_ty)).as_slice());
1222 origin: candidate.origin,
1228 fn enforce_object_limitations(&self, candidate: &Candidate) {
1230 * There are some limitations to calling functions through an
1231 * object, because (a) the self type is not known
1232 * (that's the whole point of a trait instance, after all, to
1233 * obscure the self type) and (b) the call must go through a
1234 * vtable and hence cannot be monomorphized.
1237 match candidate.origin {
1238 MethodStatic(..) | MethodParam(..) => {
1239 return; // not a call to a trait instance
1241 MethodObject(..) => {}
1244 match candidate.method_ty.explicit_self {
1245 ast::SelfStatic => { // reason (a) above
1246 self.tcx().sess.span_err(
1248 "cannot call a method without a receiver \
1249 through an object");
1252 ast::SelfValue => { // reason (a) above
1253 self.tcx().sess.span_err(
1255 "cannot call a method with a by-value receiver \
1256 through an object");
1259 ast::SelfRegion(..) | ast::SelfUniq => {}
1263 let check_for_self_ty = |ty| {
1264 if ty::type_has_self(ty) {
1265 self.tcx().sess.span_err(
1267 "cannot call a method whose type contains a \
1268 self-type through an object");
1274 let ref sig = candidate.method_ty.fty.sig;
1275 let mut found_self_ty = false;
1276 for &input_ty in sig.inputs.iter() {
1277 if check_for_self_ty(input_ty) {
1278 found_self_ty = true;
1283 check_for_self_ty(sig.output);
1286 if candidate.method_ty.generics.has_type_params() { // reason (b) above
1287 self.tcx().sess.span_err(
1289 "cannot call a generic method through an object");
1293 fn enforce_drop_trait_limitations(&self, candidate: &Candidate) {
1294 // No code can call the finalize method explicitly.
1296 match candidate.origin {
1297 MethodStatic(method_id) => {
1298 bad = self.tcx().destructors.borrow().contains(&method_id);
1300 // FIXME: does this properly enforce this on everything now
1301 // that self has been merged in? -sully
1302 MethodParam(MethodParam { trait_id: trait_id, .. }) |
1303 MethodObject(MethodObject { trait_id: trait_id, .. }) => {
1304 bad = self.tcx().destructor_for_type.borrow()
1305 .contains_key(&trait_id);
1310 self.tcx().sess.span_err(self.span,
1311 "explicit call to destructor");
1315 // `rcvr_ty` is the type of the expression. It may be a subtype of a
1316 // candidate method's `self_ty`.
1317 fn is_relevant(&self, rcvr_ty: ty::t, candidate: &Candidate) -> bool {
1318 debug!("is_relevant(rcvr_ty={}, candidate={})",
1319 self.ty_to_str(rcvr_ty), candidate.repr(self.tcx()));
1321 return match candidate.method_ty.explicit_self {
1323 debug!("(is relevant?) explicit self is static");
1324 self.report_statics == ReportStaticMethods
1328 rcvr_matches_ty(self.fcx, rcvr_ty, candidate)
1331 SelfRegion(_, m) => {
1332 debug!("(is relevant?) explicit self is a region");
1333 match ty::get(rcvr_ty).sty {
1334 ty::ty_rptr(_, mt) => {
1335 match ty::get(mt.ty).sty {
1336 ty::ty_vec(_, None) | ty::ty_str => false,
1337 _ => mutability_matches(mt.mutbl, m) &&
1338 rcvr_matches_ty(self.fcx, mt.ty, candidate),
1342 ty::ty_trait(box ty::TyTrait {
1343 def_id: self_did, store: RegionTraitStore(_, self_m), ..
1345 mutability_matches(self_m, m) &&
1346 rcvr_matches_object(self_did, candidate)
1354 debug!("(is relevant?) explicit self is a unique pointer");
1355 match ty::get(rcvr_ty).sty {
1356 ty::ty_uniq(typ) => {
1357 match ty::get(typ).sty {
1358 ty::ty_vec(_, None) | ty::ty_str => false,
1359 _ => rcvr_matches_ty(self.fcx, typ, candidate),
1363 ty::ty_trait(box ty::TyTrait {
1364 def_id: self_did, store: UniqTraitStore, ..
1366 rcvr_matches_object(self_did, candidate)
1374 fn rcvr_matches_object(self_did: ast::DefId,
1375 candidate: &Candidate) -> bool {
1376 match candidate.rcvr_match_condition {
1377 RcvrMatchesIfObject(desired_did) => {
1378 self_did == desired_did
1380 RcvrMatchesIfSubtype(_) => {
1386 fn rcvr_matches_ty(fcx: &FnCtxt,
1388 candidate: &Candidate) -> bool {
1389 match candidate.rcvr_match_condition {
1390 RcvrMatchesIfObject(_) => {
1393 RcvrMatchesIfSubtype(of_type) => {
1394 fcx.can_mk_subty(rcvr_ty, of_type).is_ok()
1399 fn mutability_matches(self_mutbl: ast::Mutability,
1400 candidate_mutbl: ast::Mutability)
1402 //! True if `self_mutbl <: candidate_mutbl`
1403 self_mutbl == candidate_mutbl
1407 fn report_candidate(&self, idx: uint, origin: &MethodOrigin) {
1409 MethodStatic(impl_did) => {
1410 let did = if self.report_statics == ReportStaticMethods {
1411 // If we're reporting statics, we want to report the trait
1412 // definition if possible, rather than an impl
1413 match ty::trait_method_of_method(self.tcx(), impl_did) {
1414 None => {debug!("(report candidate) No trait method found"); impl_did},
1415 Some(trait_did) => {debug!("(report candidate) Found trait ref"); trait_did}
1418 // If it is an instantiated default method, use the original
1419 // default method for error reporting.
1420 match provided_source(self.tcx(), impl_did) {
1425 self.report_static_candidate(idx, did)
1427 MethodParam(ref mp) => {
1428 self.report_param_candidate(idx, (*mp).trait_id)
1430 MethodObject(ref mo) => {
1431 self.report_trait_candidate(idx, mo.trait_id)
1436 fn report_static_candidate(&self, idx: uint, did: DefId) {
1437 let span = if did.krate == ast::LOCAL_CRATE {
1438 self.tcx().map.span(did.node)
1442 self.tcx().sess.span_note(
1444 format!("candidate \\#{} is `{}`",
1446 ty::item_path_str(self.tcx(), did)).as_slice());
1449 fn report_param_candidate(&self, idx: uint, did: DefId) {
1450 self.tcx().sess.span_note(
1452 format!("candidate \\#{} derives from the bound `{}`",
1454 ty::item_path_str(self.tcx(), did)).as_slice());
1457 fn report_trait_candidate(&self, idx: uint, did: DefId) {
1458 self.tcx().sess.span_note(
1460 format!("candidate \\#{} derives from the type of the receiver, \
1461 which is the trait `{}`",
1463 ty::item_path_str(self.tcx(), did)).as_slice());
1466 fn infcx(&'a self) -> &'a infer::InferCtxt<'a> {
1470 fn tcx(&self) -> &'a ty::ctxt {
1474 fn ty_to_str(&self, t: ty::t) -> String {
1475 self.fcx.infcx().ty_to_str(t)
1478 fn did_to_str(&self, did: DefId) -> String {
1479 ty::item_path_str(self.tcx(), did)
1482 fn bug(&self, s: &str) -> ! {
1483 self.tcx().sess.span_bug(self.span, s)
1487 impl Repr for Candidate {
1488 fn repr(&self, tcx: &ty::ctxt) -> String {
1489 format!("Candidate(rcvr_ty={}, rcvr_substs={}, method_ty={}, \
1491 self.rcvr_match_condition.repr(tcx),
1492 self.rcvr_substs.repr(tcx),
1493 self.method_ty.repr(tcx),
1498 impl Repr for RcvrMatchCondition {
1499 fn repr(&self, tcx: &ty::ctxt) -> String {
1501 RcvrMatchesIfObject(d) => {
1502 format!("RcvrMatchesIfObject({})", d.repr(tcx))
1504 RcvrMatchesIfSubtype(t) => {
1505 format!("RcvrMatchesIfSubtype({})", t.repr(tcx))