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_numbered, param_self, 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)
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 = subst::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: subst::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: &subst::Substs) {
504 debug!("push_inherent_candidates_from_object(did={}, substs={})",
505 self.did_to_str(did),
506 substs.repr(self.tcx()));
507 let _indenter = indenter();
508 let tcx = self.tcx();
509 let span = self.span;
511 // It is illegal to invoke a method on a trait instance that
512 // refers to the `self` type. An error will be reported by
513 // `enforce_object_limitations()` if the method refers
514 // to the `Self` type. Substituting ty_err here allows
515 // compiler to soldier on.
517 // `confirm_candidate()` also relies upon this substitution
519 let rcvr_substs = subst::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: subst::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 subst::NonerasedRegions(ref v) => {
1144 v.iter().map(|r| r.clone()).collect()
1146 subst::ErasedRegions => tcx.sess.span_bug(self.span, "ErasedRegions")
1149 self.fcx.infcx().region_vars_for_defs(
1151 candidate.method_ty.generics.region_param_defs.as_slice());
1152 for &r in m_regions.iter() {
1153 all_regions.push(r);
1156 // Construct the full set of type parameters for the method,
1157 // which is equal to the class tps + the method tps.
1158 let all_substs = subst::Substs {
1159 tps: candidate.rcvr_substs.tps.clone().append(m_substs.as_slice()),
1160 regions: subst::NonerasedRegions(all_regions),
1161 self_ty: candidate.rcvr_substs.self_ty,
1164 let ref bare_fn_ty = candidate.method_ty.fty;
1166 // Compute the method type with type parameters substituted
1167 debug!("fty={} all_substs={}",
1168 bare_fn_ty.repr(tcx),
1169 all_substs.repr(tcx));
1171 let fn_sig = &bare_fn_ty.sig;
1172 let inputs = match candidate.origin {
1173 MethodObject(..) => {
1174 // For annoying reasons, we've already handled the
1175 // substitution of self for object calls.
1176 let args = fn_sig.inputs.slice_from(1).iter().map(|t| {
1177 t.subst(tcx, &all_substs)
1179 Some(*fn_sig.inputs.get(0)).move_iter().chain(args).collect()
1181 _ => fn_sig.inputs.subst(tcx, &all_substs)
1183 let fn_sig = ty::FnSig {
1184 binder_id: fn_sig.binder_id,
1186 output: fn_sig.output.subst(tcx, &all_substs),
1187 variadic: fn_sig.variadic
1190 debug!("after subst, fty={}", fn_sig.repr(tcx));
1192 // Replace any bound regions that appear in the function
1193 // signature with region variables
1194 let (_, fn_sig) = replace_late_bound_regions_in_fn_sig(
1196 |br| self.fcx.infcx().next_region_var(
1197 infer::LateBoundRegion(self.span, br)));
1198 let transformed_self_ty = *fn_sig.inputs.get(0);
1199 let fty = ty::mk_bare_fn(tcx, ty::BareFnTy {
1201 fn_style: bare_fn_ty.fn_style,
1202 abi: bare_fn_ty.abi.clone(),
1204 debug!("after replacing bound regions, fty={}", self.ty_to_str(fty));
1206 // Before, we only checked whether self_ty could be a subtype
1207 // of rcvr_ty; now we actually make it so (this may cause
1208 // variables to unify etc). Since we checked beforehand, and
1209 // nothing has changed in the meantime, this unification
1210 // should never fail.
1211 let span = self.self_expr.map_or(self.span, |e| e.span);
1212 match self.fcx.mk_subty(false, infer::Misc(span),
1213 rcvr_ty, transformed_self_ty) {
1217 "{} was a subtype of {} but now is not?",
1218 self.ty_to_str(rcvr_ty),
1219 self.ty_to_str(transformed_self_ty)).as_slice());
1224 origin: candidate.origin,
1230 fn enforce_object_limitations(&self, candidate: &Candidate) {
1232 * There are some limitations to calling functions through an
1233 * object, because (a) the self type is not known
1234 * (that's the whole point of a trait instance, after all, to
1235 * obscure the self type) and (b) the call must go through a
1236 * vtable and hence cannot be monomorphized.
1239 match candidate.origin {
1240 MethodStatic(..) | MethodParam(..) => {
1241 return; // not a call to a trait instance
1243 MethodObject(..) => {}
1246 match candidate.method_ty.explicit_self {
1247 ast::SelfStatic => { // reason (a) above
1248 self.tcx().sess.span_err(
1250 "cannot call a method without a receiver \
1251 through an object");
1254 ast::SelfValue => { // reason (a) above
1255 self.tcx().sess.span_err(
1257 "cannot call a method with a by-value receiver \
1258 through an object");
1261 ast::SelfRegion(..) | ast::SelfUniq => {}
1265 let check_for_self_ty = |ty| {
1266 if ty::type_has_self(ty) {
1267 self.tcx().sess.span_err(
1269 "cannot call a method whose type contains a \
1270 self-type through an object");
1276 let ref sig = candidate.method_ty.fty.sig;
1277 let mut found_self_ty = false;
1278 for &input_ty in sig.inputs.iter() {
1279 if check_for_self_ty(input_ty) {
1280 found_self_ty = true;
1285 check_for_self_ty(sig.output);
1288 if candidate.method_ty.generics.has_type_params() { // reason (b) above
1289 self.tcx().sess.span_err(
1291 "cannot call a generic method through an object");
1295 fn enforce_drop_trait_limitations(&self, candidate: &Candidate) {
1296 // No code can call the finalize method explicitly.
1298 match candidate.origin {
1299 MethodStatic(method_id) => {
1300 bad = self.tcx().destructors.borrow().contains(&method_id);
1302 // FIXME: does this properly enforce this on everything now
1303 // that self has been merged in? -sully
1304 MethodParam(MethodParam { trait_id: trait_id, .. }) |
1305 MethodObject(MethodObject { trait_id: trait_id, .. }) => {
1306 bad = self.tcx().destructor_for_type.borrow()
1307 .contains_key(&trait_id);
1312 self.tcx().sess.span_err(self.span,
1313 "explicit call to destructor");
1317 // `rcvr_ty` is the type of the expression. It may be a subtype of a
1318 // candidate method's `self_ty`.
1319 fn is_relevant(&self, rcvr_ty: ty::t, candidate: &Candidate) -> bool {
1320 debug!("is_relevant(rcvr_ty={}, candidate={})",
1321 self.ty_to_str(rcvr_ty), candidate.repr(self.tcx()));
1323 return match candidate.method_ty.explicit_self {
1325 debug!("(is relevant?) explicit self is static");
1326 self.report_statics == ReportStaticMethods
1330 rcvr_matches_ty(self.fcx, rcvr_ty, candidate)
1333 SelfRegion(_, m) => {
1334 debug!("(is relevant?) explicit self is a region");
1335 match ty::get(rcvr_ty).sty {
1336 ty::ty_rptr(_, mt) => {
1337 match ty::get(mt.ty).sty {
1338 ty::ty_vec(_, None) | ty::ty_str => false,
1339 _ => mutability_matches(mt.mutbl, m) &&
1340 rcvr_matches_ty(self.fcx, mt.ty, candidate),
1344 ty::ty_trait(box ty::TyTrait {
1345 def_id: self_did, store: RegionTraitStore(_, self_m), ..
1347 mutability_matches(self_m, m) &&
1348 rcvr_matches_object(self_did, candidate)
1356 debug!("(is relevant?) explicit self is a unique pointer");
1357 match ty::get(rcvr_ty).sty {
1358 ty::ty_uniq(typ) => {
1359 match ty::get(typ).sty {
1360 ty::ty_vec(_, None) | ty::ty_str => false,
1361 _ => rcvr_matches_ty(self.fcx, typ, candidate),
1365 ty::ty_trait(box ty::TyTrait {
1366 def_id: self_did, store: UniqTraitStore, ..
1368 rcvr_matches_object(self_did, candidate)
1376 fn rcvr_matches_object(self_did: ast::DefId,
1377 candidate: &Candidate) -> bool {
1378 match candidate.rcvr_match_condition {
1379 RcvrMatchesIfObject(desired_did) => {
1380 self_did == desired_did
1382 RcvrMatchesIfSubtype(_) => {
1388 fn rcvr_matches_ty(fcx: &FnCtxt,
1390 candidate: &Candidate) -> bool {
1391 match candidate.rcvr_match_condition {
1392 RcvrMatchesIfObject(_) => {
1395 RcvrMatchesIfSubtype(of_type) => {
1396 fcx.can_mk_subty(rcvr_ty, of_type).is_ok()
1401 fn mutability_matches(self_mutbl: ast::Mutability,
1402 candidate_mutbl: ast::Mutability)
1404 //! True if `self_mutbl <: candidate_mutbl`
1405 self_mutbl == candidate_mutbl
1409 fn report_candidate(&self, idx: uint, origin: &MethodOrigin) {
1411 MethodStatic(impl_did) => {
1412 let did = if self.report_statics == ReportStaticMethods {
1413 // If we're reporting statics, we want to report the trait
1414 // definition if possible, rather than an impl
1415 match ty::trait_method_of_method(self.tcx(), impl_did) {
1416 None => {debug!("(report candidate) No trait method found"); impl_did},
1417 Some(trait_did) => {debug!("(report candidate) Found trait ref"); trait_did}
1420 // If it is an instantiated default method, use the original
1421 // default method for error reporting.
1422 match provided_source(self.tcx(), impl_did) {
1427 self.report_static_candidate(idx, did)
1429 MethodParam(ref mp) => {
1430 self.report_param_candidate(idx, (*mp).trait_id)
1432 MethodObject(ref mo) => {
1433 self.report_trait_candidate(idx, mo.trait_id)
1438 fn report_static_candidate(&self, idx: uint, did: DefId) {
1439 let span = if did.krate == ast::LOCAL_CRATE {
1440 self.tcx().map.span(did.node)
1444 self.tcx().sess.span_note(
1446 format!("candidate \\#{} is `{}`",
1448 ty::item_path_str(self.tcx(), did)).as_slice());
1451 fn report_param_candidate(&self, idx: uint, did: DefId) {
1452 self.tcx().sess.span_note(
1454 format!("candidate \\#{} derives from the bound `{}`",
1456 ty::item_path_str(self.tcx(), did)).as_slice());
1459 fn report_trait_candidate(&self, idx: uint, did: DefId) {
1460 self.tcx().sess.span_note(
1462 format!("candidate \\#{} derives from the type of the receiver, \
1463 which is the trait `{}`",
1465 ty::item_path_str(self.tcx(), did)).as_slice());
1468 fn infcx(&'a self) -> &'a infer::InferCtxt<'a> {
1472 fn tcx(&self) -> &'a ty::ctxt {
1476 fn ty_to_str(&self, t: ty::t) -> String {
1477 self.fcx.infcx().ty_to_str(t)
1480 fn did_to_str(&self, did: DefId) -> String {
1481 ty::item_path_str(self.tcx(), did)
1484 fn bug(&self, s: &str) -> ! {
1485 self.tcx().sess.span_bug(self.span, s)
1489 impl Repr for Candidate {
1490 fn repr(&self, tcx: &ty::ctxt) -> String {
1491 format!("Candidate(rcvr_ty={}, rcvr_substs={}, method_ty={}, \
1493 self.rcvr_match_condition.repr(tcx),
1494 self.rcvr_substs.repr(tcx),
1495 self.method_ty.repr(tcx),
1500 impl Repr for RcvrMatchCondition {
1501 fn repr(&self, tcx: &ty::ctxt) -> String {
1503 RcvrMatchesIfObject(d) => {
1504 format!("RcvrMatchesIfObject({})", d.repr(tcx))
1506 RcvrMatchesIfSubtype(t) => {
1507 format!("RcvrMatchesIfSubtype({})", t.repr(tcx))