1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
15 Method lookup can be rather complex due to the interaction of a number
16 of factors, such as self types, autoderef, trait lookup, etc. The
17 algorithm is divided into two parts: candidate collection and
20 ## Candidate collection
22 A `Candidate` is a method item that might plausibly be the method
23 being invoked. Candidates are grouped into two kinds, inherent and
24 extension. Inherent candidates are those that are derived from the
25 type of the receiver itself. So, if you have a receiver of some
26 nominal type `Foo` (e.g., a struct), any methods defined within an
27 impl like `impl Foo` are inherent methods. Nothing needs to be
28 imported to use an inherent method, they are associated with the type
29 itself (note that inherent impls can only be defined in the same
30 module as the type itself).
32 Inherent candidates are not always derived from impls. If you have a
33 trait instance, such as a value of type `Box<ToStr>`, then the trait
34 methods (`to_str()`, in this case) are inherently associated with it.
35 Another case is type parameters, in which case the methods of their
38 Extension candidates are derived from imported traits. If I have the
39 trait `ToStr` imported, and I call `to_str()` on a value of type `T`,
40 then we will go off to find out whether there is an impl of `ToStr`
41 for `T`. These kinds of method calls are called "extension methods".
42 They can be defined in any module, not only the one that defined `T`.
43 Furthermore, you must import the trait to call such a method.
45 For better or worse, we currently give weight to inherent methods over
46 extension methods during candidate selection (below).
48 ## Candidate selection
50 Once we know the set of candidates, we can go off and try to select
51 which one is actually being called. We do this by taking the type of
52 the receiver, let's call it R, and checking whether it matches against
53 the expected receiver type for each of the collected candidates. We
54 first check for inherent candidates and see whether we get exactly one
55 match (zero means keep searching, more than one is an error). If so,
56 we return that as the candidate. Otherwise we search the extension
57 candidates in the same way.
59 If find no matching candidate at all, we proceed to auto-deref the
60 receiver type and search again. We keep doing that until we cannot
61 auto-deref any longer. At each step, we also check for candidates
62 based on "autoptr", which if the current type is `T`, checks for `&mut
63 T`, `&const T`, and `&T` receivers. Finally, at the very end, we will
64 also try autoslice, which converts `~[]` to `&[]` (there is no point
65 at trying autoslice earlier, because no autoderefable type is also
70 You might wonder why we first collect the candidates and then select.
71 Both the inherent candidate collection and the candidate selection
72 proceed by progressively deref'ing the receiver type, after all. The
73 answer is that two phases are needed to elegantly deal with explicit
74 self. After all, if there is an impl for the type `Foo`, it can
75 define a method with the type `Box<self>`, which means that it expects a
76 receiver of type `Box<Foo>`. If we have a receiver of type `Box<Foo>`, but we
77 waited to search for that impl until we have deref'd the `Box` away and
78 obtained the type `Foo`, we would never match this method.
84 use middle::subst::Subst;
87 use middle::typeck::astconv::AstConv;
88 use middle::typeck::check::{FnCtxt, PreferMutLvalue, impl_self_ty};
89 use middle::typeck::check;
90 use middle::typeck::infer;
91 use middle::typeck::MethodCallee;
92 use middle::typeck::{MethodOrigin, MethodParam};
93 use middle::typeck::{MethodStatic, MethodObject};
94 use middle::typeck::{param_index};
95 use middle::typeck::check::regionmanip::replace_late_bound_regions_in_fn_sig;
96 use middle::typeck::TypeAndSubsts;
97 use util::common::indenter;
99 use util::ppaux::Repr;
101 use std::collections::HashSet;
103 use syntax::ast::{DefId, SelfValue, SelfRegion};
104 use syntax::ast::{SelfUniq, SelfStatic};
105 use syntax::ast::{MutMutable, MutImmutable};
107 use syntax::codemap::Span;
108 use syntax::parse::token;
110 #[deriving(PartialEq)]
111 pub enum CheckTraitsFlag {
113 CheckTraitsAndInherentMethods,
116 #[deriving(PartialEq)]
117 pub enum AutoderefReceiverFlag {
119 DontAutoderefReceiver,
122 #[deriving(PartialEq)]
123 pub enum StaticMethodsFlag {
131 // In a call `a.b::<X, Y, ...>(...)`:
132 expr: &ast::Expr, // The expression `a.b(...)`.
133 self_expr: &'a ast::Expr, // The expression `a`.
134 m_name: ast::Name, // The name `b`.
135 self_ty: ty::t, // The type of `a`.
136 supplied_tps: &'a [ty::t], // The list of types X, Y, ... .
137 deref_args: check::DerefArgs, // Whether we autopointer first.
138 check_traits: CheckTraitsFlag, // Whether we check traits only.
139 autoderef_receiver: AutoderefReceiverFlag,
140 report_statics: StaticMethodsFlag)
141 -> Option<MethodCallee> {
142 let mut lcx = LookupContext {
145 self_expr: Some(self_expr),
147 supplied_tps: supplied_tps,
148 impl_dups: HashSet::new(),
149 inherent_candidates: Vec::new(),
150 extension_candidates: Vec::new(),
151 deref_args: deref_args,
152 check_traits: check_traits,
153 autoderef_receiver: autoderef_receiver,
154 report_statics: report_statics,
157 debug!("method lookup(self_ty={}, expr={}, self_expr={})",
158 self_ty.repr(fcx.tcx()), expr.repr(fcx.tcx()),
159 self_expr.repr(fcx.tcx()));
161 debug!("searching inherent candidates");
162 lcx.push_inherent_candidates(self_ty);
163 let mme = lcx.search(self_ty);
168 debug!("searching extension candidates");
169 lcx.reset_candidates();
170 lcx.push_bound_candidates(self_ty, None);
171 lcx.push_extension_candidates(expr.id);
175 pub fn lookup_in_trait<'a>(
178 // In a call `a.b::<X, Y, ...>(...)`:
179 span: Span, // The expression `a.b(...)`'s span.
180 self_expr: Option<&'a ast::Expr>, // The expression `a`, if available.
181 m_name: ast::Name, // The name `b`.
182 trait_did: DefId, // The trait to limit the lookup to.
183 self_ty: ty::t, // The type of `a`.
184 supplied_tps: &'a [ty::t], // The list of types X, Y, ... .
185 autoderef_receiver: AutoderefReceiverFlag,
186 report_statics: StaticMethodsFlag)
187 -> Option<MethodCallee> {
188 let mut lcx = LookupContext {
191 self_expr: self_expr,
193 supplied_tps: supplied_tps,
194 impl_dups: HashSet::new(),
195 inherent_candidates: Vec::new(),
196 extension_candidates: Vec::new(),
197 deref_args: check::DoDerefArgs,
198 check_traits: CheckTraitsOnly,
199 autoderef_receiver: autoderef_receiver,
200 report_statics: report_statics,
203 debug!("method lookup_in_trait(self_ty={}, self_expr={})",
204 self_ty.repr(fcx.tcx()), self_expr.map(|e| e.repr(fcx.tcx())));
206 lcx.push_bound_candidates(self_ty, Some(trait_did));
207 lcx.push_extension_candidate(trait_did);
211 // Determine the index of a method in the list of all methods belonging
212 // to a trait and its supertraits.
213 fn get_method_index(tcx: &ty::ctxt,
214 trait_ref: &TraitRef,
215 subtrait: Rc<TraitRef>,
216 n_method: uint) -> uint {
217 // We need to figure the "real index" of the method in a
218 // listing of all the methods of an object. We do this by
219 // iterating down the supertraits of the object's trait until
220 // we find the trait the method came from, counting up the
221 // methods from them.
222 let mut method_count = 0;
223 ty::each_bound_trait_and_supertraits(tcx, &[subtrait], |bound_ref| {
224 if bound_ref.def_id == trait_ref.def_id { false }
226 method_count += ty::trait_methods(tcx, bound_ref.def_id).len();
230 method_count + n_method
233 fn construct_transformed_self_ty_for_object(
236 trait_def_id: ast::DefId,
237 rcvr_substs: &subst::Substs,
238 method_ty: &ty::Method)
242 * This is a bit tricky. We have a match against a trait method
243 * being invoked on an object, and we want to generate the
244 * self-type. As an example, consider a trait
247 * fn r_method<'a>(&'a self);
248 * fn u_method(Box<self>);
251 * Now, assuming that `r_method` is being called, we want the
252 * result to be `&'a Foo`. Assuming that `u_method` is being
253 * called, we want the result to be `Box<Foo>`. Of course,
254 * this transformation has already been done as part of
255 * `method_ty.fty.sig.inputs[0]`, but there the type
256 * is expressed in terms of `Self` (i.e., `&'a Self`, `Box<Self>`).
257 * Because objects are not standalone types, we can't just substitute
258 * `s/Self/Foo/`, so we must instead perform this kind of hokey
262 let mut obj_substs = rcvr_substs.clone();
264 // The subst we get in has Err as the "Self" type. For an object
265 // type, we don't put any type into the Self paramspace, so let's
266 // make a copy of rcvr_substs that has the Self paramspace empty.
267 obj_substs.types.get_mut_vec(subst::SelfSpace).pop().unwrap();
269 match method_ty.explicit_self {
271 tcx.sess.span_bug(span, "static method for object type receiver");
274 ty::mk_err() // error reported in `enforce_object_limitations()`
276 ast::SelfRegion(..) | ast::SelfUniq => {
277 let transformed_self_ty = *method_ty.fty.sig.inputs.get(0);
278 match ty::get(transformed_self_ty).sty {
279 ty::ty_rptr(r, mt) => { // must be SelfRegion
280 let r = r.subst(tcx, rcvr_substs); // handle Early-Bound lifetime
281 let tr = ty::mk_trait(tcx, trait_def_id, obj_substs,
282 ty::empty_builtin_bounds());
283 ty::mk_rptr(tcx, r, ty::mt{ ty: tr, mutbl: mt.mutbl })
285 ty::ty_uniq(_) => { // must be SelfUniq
286 let tr = ty::mk_trait(tcx, trait_def_id, obj_substs,
287 ty::empty_builtin_bounds());
291 tcx.sess.span_bug(span,
292 format!("'impossible' transformed_self_ty: {}",
293 transformed_self_ty.repr(tcx)).as_slice());
300 struct LookupContext<'a> {
304 // The receiver to the method call. Only `None` in the case of
305 // an overloaded autoderef, where the receiver may be an intermediate
306 // state like "the expression `x` when it has been autoderef'd
308 self_expr: Option<&'a ast::Expr>,
311 supplied_tps: &'a [ty::t],
312 impl_dups: HashSet<DefId>,
313 inherent_candidates: Vec<Candidate>,
314 extension_candidates: Vec<Candidate>,
315 deref_args: check::DerefArgs,
316 check_traits: CheckTraitsFlag,
317 autoderef_receiver: AutoderefReceiverFlag,
318 report_statics: StaticMethodsFlag,
322 * A potential method that might be called, assuming the receiver
323 * is of a suitable type.
327 rcvr_match_condition: RcvrMatchCondition,
328 rcvr_substs: subst::Substs,
329 method_ty: Rc<ty::Method>,
330 origin: MethodOrigin,
333 /// This type represents the conditions under which the receiver is
334 /// considered to "match" a given method candidate. Typically the test
335 /// is whether the receiver is of a particular type. However, this
336 /// type is the type of the receiver *after accounting for the
337 /// method's self type* (e.g., if the method is an `Box<self>` method, we
338 /// have *already verified* that the receiver is of some type `Box<T>` and
339 /// now we must check that the type `T` is correct). Unfortunately,
340 /// because traits are not types, this is a pain to do.
342 pub enum RcvrMatchCondition {
343 RcvrMatchesIfObject(ast::DefId),
344 RcvrMatchesIfSubtype(ty::t)
347 impl<'a> LookupContext<'a> {
348 fn search(&self, self_ty: ty::t) -> Option<MethodCallee> {
349 let span = self.self_expr.map_or(self.span, |e| e.span);
350 let self_expr_id = self.self_expr.map(|e| e.id);
352 let (self_ty, autoderefs, result) =
354 self.fcx, span, self_ty, self_expr_id, PreferMutLvalue,
355 |self_ty, autoderefs| self.search_step(self_ty, autoderefs));
358 Some(Some(result)) => Some(result),
360 if self.is_overloaded_deref() {
361 // If we are searching for an overloaded deref, no
362 // need to try coercing a `~[T]` to an `&[T]` and
363 // searching for an overloaded deref on *that*.
366 self.search_for_autosliced_method(self_ty, autoderefs)
372 fn search_step(&self,
375 -> Option<Option<MethodCallee>> {
376 debug!("search_step: self_ty={} autoderefs={}",
377 self.ty_to_str(self_ty), autoderefs);
379 match self.deref_args {
380 check::DontDerefArgs => {
381 match self.search_for_autoderefd_method(self_ty, autoderefs) {
382 Some(result) => return Some(Some(result)),
386 match self.search_for_autoptrd_method(self_ty, autoderefs) {
387 Some(result) => return Some(Some(result)),
391 check::DoDerefArgs => {
392 match self.search_for_autoptrd_method(self_ty, autoderefs) {
393 Some(result) => return Some(Some(result)),
397 match self.search_for_autoderefd_method(self_ty, autoderefs) {
398 Some(result) => return Some(Some(result)),
404 // Don't autoderef if we aren't supposed to.
405 if self.autoderef_receiver == DontAutoderefReceiver {
412 fn is_overloaded_deref(&self) -> bool {
413 self.self_expr.is_none()
416 // ______________________________________________________________________
417 // Candidate collection (see comment at start of file)
419 fn reset_candidates(&mut self) {
420 self.inherent_candidates = Vec::new();
421 self.extension_candidates = Vec::new();
424 fn push_inherent_candidates(&mut self, self_ty: ty::t) {
426 * Collect all inherent candidates into
427 * `self.inherent_candidates`. See comment at the start of
428 * the file. To find the inherent candidates, we repeatedly
429 * deref the self-ty to find the "base-type". So, for
430 * example, if the receiver is Box<Box<C>> where `C` is a struct type,
431 * we'll want to find the inherent impls for `C`.
434 let span = self.self_expr.map_or(self.span, |e| e.span);
435 check::autoderef(self.fcx, span, self_ty, None, PreferMutLvalue, |self_ty, _| {
436 match get(self_ty).sty {
437 ty_uniq(ty) | ty_rptr(_, mt {ty, ..}) => match get(ty).sty{
438 ty_trait(box TyTrait { def_id, ref substs, .. }) => {
439 self.push_inherent_candidates_from_object(def_id, substs);
440 self.push_inherent_impl_candidates_for_type(def_id);
444 ty_enum(did, _) | ty_struct(did, _) => {
445 if self.check_traits == CheckTraitsAndInherentMethods {
446 self.push_inherent_impl_candidates_for_type(did);
449 _ => { /* No inherent methods in these types */ }
452 // Don't autoderef if we aren't supposed to.
453 if self.autoderef_receiver == DontAutoderefReceiver {
461 fn push_bound_candidates(&mut self, self_ty: ty::t, restrict_to: Option<DefId>) {
462 let span = self.self_expr.map_or(self.span, |e| e.span);
463 check::autoderef(self.fcx, span, self_ty, None, PreferMutLvalue, |self_ty, _| {
464 match get(self_ty).sty {
466 self.push_inherent_candidates_from_param(self_ty, restrict_to, p);
468 _ => { /* No bound methods in these types */ }
471 // Don't autoderef if we aren't supposed to.
472 if self.autoderef_receiver == DontAutoderefReceiver {
480 fn push_extension_candidate(&mut self, trait_did: DefId) {
481 ty::populate_implementations_for_trait_if_necessary(self.tcx(), trait_did);
483 // Look for explicit implementations.
484 let impl_methods = self.tcx().impl_methods.borrow();
485 for impl_infos in self.tcx().trait_impls.borrow().find(&trait_did).iter() {
486 for impl_did in impl_infos.borrow().iter() {
487 let methods = impl_methods.get(impl_did);
488 self.push_candidates_from_impl(*impl_did, methods.as_slice(), true);
493 fn push_extension_candidates(&mut self, expr_id: ast::NodeId) {
494 // If the method being called is associated with a trait, then
495 // find all the impls of that trait. Each of those are
497 let opt_applicable_traits = self.fcx.ccx.trait_map.find(&expr_id);
498 for applicable_traits in opt_applicable_traits.move_iter() {
499 for trait_did in applicable_traits.iter() {
500 self.push_extension_candidate(*trait_did);
505 fn push_inherent_candidates_from_object(&mut self,
507 substs: &subst::Substs) {
508 debug!("push_inherent_candidates_from_object(did={}, substs={})",
509 self.did_to_str(did),
510 substs.repr(self.tcx()));
511 let _indenter = indenter();
512 let tcx = self.tcx();
513 let span = self.span;
515 // It is illegal to invoke a method on a trait instance that
516 // refers to the `self` type. An error will be reported by
517 // `enforce_object_limitations()` if the method refers
518 // to the `Self` type. Substituting ty_err here allows
519 // compiler to soldier on.
521 // `confirm_candidate()` also relies upon this substitution
523 let rcvr_substs = substs.with_self_ty(ty::mk_err());
524 let trait_ref = Rc::new(TraitRef {
526 substs: rcvr_substs.clone()
529 self.push_inherent_candidates_from_bounds_inner(&[trait_ref.clone()],
530 |new_trait_ref, m, method_num, _bound_num| {
531 let vtable_index = get_method_index(tcx, &*new_trait_ref,
532 trait_ref.clone(), method_num);
533 let mut m = (*m).clone();
534 // We need to fix up the transformed self type.
535 *m.fty.sig.inputs.get_mut(0) =
536 construct_transformed_self_ty_for_object(
537 tcx, span, did, &rcvr_substs, &m);
540 rcvr_match_condition: RcvrMatchesIfObject(did),
541 rcvr_substs: new_trait_ref.substs.clone(),
542 method_ty: Rc::new(m),
543 origin: MethodObject(MethodObject {
544 trait_id: new_trait_ref.def_id,
545 object_trait_id: did,
546 method_num: method_num,
547 real_index: vtable_index
553 fn push_inherent_candidates_from_param(&mut self,
555 restrict_to: Option<DefId>,
557 debug!("push_inherent_candidates_from_param(param_ty={:?})",
559 self.push_inherent_candidates_from_bounds(
564 param_index { space: param_ty.space, index: param_ty.idx });
568 fn push_inherent_candidates_from_bounds(&mut self,
570 space: subst::ParamSpace,
572 restrict_to: Option<DefId>,
573 param: param_index) {
575 self.fcx.inh.param_env.bounds.get(space, index).trait_bounds
577 self.push_inherent_candidates_from_bounds_inner(bounds,
578 |trait_ref, m, method_num, bound_num| {
581 if trait_did != trait_ref.def_id {
588 rcvr_match_condition: RcvrMatchesIfSubtype(self_ty),
589 rcvr_substs: trait_ref.substs.clone(),
591 origin: MethodParam(MethodParam {
592 trait_id: trait_ref.def_id,
593 method_num: method_num,
595 bound_num: bound_num,
601 // Do a search through a list of bounds, using a callback to actually
602 // create the candidates.
603 fn push_inherent_candidates_from_bounds_inner(&mut self,
604 bounds: &[Rc<TraitRef>],
605 mk_cand: |tr: Rc<TraitRef>,
609 -> Option<Candidate>) {
610 let tcx = self.tcx();
611 let mut next_bound_idx = 0; // count only trait bounds
613 ty::each_bound_trait_and_supertraits(tcx, bounds, |bound_trait_ref| {
614 let this_bound_idx = next_bound_idx;
617 let trait_methods = ty::trait_methods(tcx, bound_trait_ref.def_id);
618 match trait_methods.iter().position(|m| {
619 m.explicit_self != ast::SelfStatic &&
620 m.ident.name == self.m_name }) {
622 let method = trait_methods.get(pos).clone();
624 match mk_cand(bound_trait_ref, method, pos, this_bound_idx) {
626 debug!("pushing inherent candidate for param: {}",
627 cand.repr(self.tcx()));
628 self.inherent_candidates.push(cand);
634 debug!("trait doesn't contain method: {:?}",
635 bound_trait_ref.def_id);
636 // check next trait or bound
644 fn push_inherent_impl_candidates_for_type(&mut self, did: DefId) {
645 // Read the inherent implementation candidates for this type from the
646 // metadata if necessary.
647 ty::populate_implementations_for_type_if_necessary(self.tcx(), did);
649 let impl_methods = self.tcx().impl_methods.borrow();
650 for impl_infos in self.tcx().inherent_impls.borrow().find(&did).iter() {
651 for impl_did in impl_infos.borrow().iter() {
652 let methods = impl_methods.get(impl_did);
653 self.push_candidates_from_impl(*impl_did, methods.as_slice(), false);
658 fn push_candidates_from_impl(&mut self,
660 impl_methods: &[DefId],
661 is_extension: bool) {
662 let did = if self.report_statics == ReportStaticMethods {
663 // we only want to report each base trait once
664 match ty::impl_trait_ref(self.tcx(), impl_did) {
665 Some(trait_ref) => trait_ref.def_id,
672 if !self.impl_dups.insert(did) {
673 return; // already visited
676 debug!("push_candidates_from_impl: {} {}",
677 token::get_name(self.m_name),
678 impl_methods.iter().map(|&did| ty::method(self.tcx(), did).ident)
679 .collect::<Vec<ast::Ident>>()
682 let method = match impl_methods.iter().map(|&did| ty::method(self.tcx(), did))
683 .find(|m| m.ident.name == self.m_name) {
684 Some(method) => method,
685 None => { return; } // No method with the right name.
688 // determine the `self` of the impl with fresh
689 // variables for each parameter:
690 let span = self.self_expr.map_or(self.span, |e| e.span);
691 let vcx = self.fcx.vtable_context();
695 } = impl_self_ty(&vcx, span, impl_did);
697 let candidates = if is_extension {
698 &mut self.extension_candidates
700 &mut self.inherent_candidates
703 candidates.push(Candidate {
704 rcvr_match_condition: RcvrMatchesIfSubtype(impl_ty),
705 rcvr_substs: impl_substs,
706 origin: MethodStatic(method.def_id),
711 // ______________________________________________________________________
712 // Candidate selection (see comment at start of file)
714 fn search_for_autoderefd_method(&self,
717 -> Option<MethodCallee> {
718 let (self_ty, auto_deref_ref) =
719 self.consider_reborrow(self_ty, autoderefs);
721 // Hacky. For overloaded derefs, there may be an adjustment
722 // added to the expression from the outside context, so we do not store
723 // an explicit adjustment, but rather we hardwire the single deref
724 // that occurs in trans and mem_categorization.
725 let adjustment = match self.self_expr {
726 Some(expr) => Some((expr.id, ty::AutoDerefRef(auto_deref_ref))),
730 match self.search_for_method(self_ty) {
733 debug!("(searching for autoderef'd method) writing \
734 adjustment {:?} for {}", adjustment, self.ty_to_str( self_ty));
736 Some((self_expr_id, adj)) => {
737 self.fcx.write_adjustment(self_expr_id, adj);
746 fn consider_reborrow(&self,
749 -> (ty::t, ty::AutoDerefRef) {
751 * In the event that we are invoking a method with a receiver
752 * of a borrowed type like `&T`, `&mut T`, or `&mut [T]`,
753 * we will "reborrow" the receiver implicitly. For example, if
754 * you have a call `r.inc()` and where `r` has type `&mut T`,
755 * then we treat that like `(&mut *r).inc()`. This avoids
756 * consuming the original pointer.
758 * You might think that this would be a natural byproduct of
759 * the auto-deref/auto-ref process. This is true for `Box<T>`
760 * but not for an `&mut T` receiver. With `Box<T>`, we would
761 * begin by testing for methods with a self type `Box<T>`,
762 * then autoderef to `T`, then autoref to `&mut T`. But with
763 * an `&mut T` receiver the process begins with `&mut T`, only
764 * without any autoadjustments.
767 let tcx = self.tcx();
768 return match ty::get(self_ty).sty {
769 ty::ty_rptr(_, self_mt) if default_method_hack(self_mt) => {
772 autoderefs: autoderefs,
775 ty::ty_rptr(_, self_mt) => {
777 self.infcx().next_region_var(infer::Autoref(self.span));
778 let (extra_derefs, auto) = match ty::get(self_mt.ty).sty {
779 ty::ty_vec(_, None) => (0, ty::AutoBorrowVec(region, self_mt.mutbl)),
780 ty::ty_str => (0, ty::AutoBorrowVec(region, self_mt.mutbl)),
781 ty::ty_trait(..) => (0, ty::AutoBorrowObj(region, self_mt.mutbl)),
782 _ => (1, ty::AutoPtr(region, self_mt.mutbl)),
784 (ty::mk_rptr(tcx, region, self_mt),
786 autoderefs: autoderefs + extra_derefs,
787 autoref: Some(auto)})
792 autoderefs: autoderefs,
797 fn default_method_hack(self_mt: ty::mt) -> bool {
798 // FIXME(#6129). Default methods can't deal with autoref.
800 // I am a horrible monster and I pray for death. Currently
801 // the default method code fails when you try to reborrow
802 // because it is not handling types correctly. In lieu of
803 // fixing that, I am introducing this horrible hack. - ndm
804 self_mt.mutbl == MutImmutable && ty::type_is_self(self_mt.ty)
808 fn auto_slice_vec(&self, mt: ty::mt, autoderefs: uint) -> Option<MethodCallee> {
809 let tcx = self.tcx();
810 debug!("auto_slice_vec {}", ppaux::ty_to_str(tcx, mt.ty));
812 // First try to borrow to a slice
813 let entry = self.search_for_some_kind_of_autorefd_method(
814 AutoBorrowVec, autoderefs, [MutImmutable, MutMutable],
815 |m,r| ty::mk_slice(tcx, r,
816 ty::mt {ty:mt.ty, mutbl:m}));
822 // Then try to borrow to a slice *and* borrow a pointer.
823 self.search_for_some_kind_of_autorefd_method(
824 AutoBorrowVecRef, autoderefs, [MutImmutable, MutMutable],
826 let slice_ty = ty::mk_slice(tcx, r,
827 ty::mt {ty:mt.ty, mutbl:m});
828 // NB: we do not try to autoref to a mutable
829 // pointer. That would be creating a pointer
830 // to a temporary pointer (the borrowed
831 // slice), so any update the callee makes to
832 // it can't be observed.
833 ty::mk_rptr(tcx, r, ty::mt {ty:slice_ty, mutbl:MutImmutable})
838 fn auto_slice_str(&self, autoderefs: uint) -> Option<MethodCallee> {
839 let tcx = self.tcx();
840 debug!("auto_slice_str");
842 let entry = self.search_for_some_kind_of_autorefd_method(
843 AutoBorrowVec, autoderefs, [MutImmutable],
844 |_m,r| ty::mk_str_slice(tcx, r, MutImmutable));
850 self.search_for_some_kind_of_autorefd_method(
851 AutoBorrowVecRef, autoderefs, [MutImmutable],
853 let slice_ty = ty::mk_str_slice(tcx, r, m);
854 ty::mk_rptr(tcx, r, ty::mt {ty:slice_ty, mutbl:m})
858 // Coerce Box/&Trait instances to &Trait.
859 fn auto_slice_trait(&self, ty: ty::t, autoderefs: uint) -> Option<MethodCallee> {
860 match ty::get(ty).sty {
861 ty_trait(box ty::TyTrait {
863 substs: ref trt_substs,
866 let tcx = self.tcx();
867 self.search_for_some_kind_of_autorefd_method(
868 AutoBorrowObj, autoderefs, [MutImmutable, MutMutable],
870 let tr = ty::mk_trait(tcx, trt_did, trt_substs.clone(), b);
871 ty::mk_rptr(tcx, r, ty::mt{ ty: tr, mutbl: m })
874 _ => fail!("Expected ty_trait in auto_slice_trait")
878 fn search_for_autosliced_method(&self,
881 -> Option<MethodCallee> {
883 * Searches for a candidate by converting things like
887 debug!("search_for_autosliced_method {}", ppaux::ty_to_str(self.tcx(), self_ty));
889 let sty = ty::get(self_ty).sty.clone();
891 ty_rptr(_, mt) => match ty::get(mt.ty).sty {
892 ty_vec(mt, None) => self.auto_slice_vec(mt, autoderefs),
893 ty_trait(..) => self.auto_slice_trait(mt.ty, autoderefs),
896 ty_uniq(t) => match ty::get(t).sty {
897 ty_vec(mt, None) => self.auto_slice_vec(mt, autoderefs),
898 ty_str => self.auto_slice_str(autoderefs),
899 ty_trait(..) => self.auto_slice_trait(t, autoderefs),
902 ty_vec(mt, Some(_)) => self.auto_slice_vec(mt, autoderefs),
905 // This case should probably be handled similarly to
914 fn search_for_autoptrd_method(&self, self_ty: ty::t, autoderefs: uint)
915 -> Option<MethodCallee> {
918 * Converts any type `T` to `&M T` where `M` is an
919 * appropriate mutability.
922 let tcx = self.tcx();
923 match ty::get(self_ty).sty {
924 ty_bare_fn(..) | ty_box(..) | ty_uniq(..) | ty_rptr(..) |
925 ty_infer(IntVar(_)) |
926 ty_infer(FloatVar(_)) |
927 ty_param(..) | ty_nil | ty_bot | ty_bool |
928 ty_char | ty_int(..) | ty_uint(..) |
929 ty_float(..) | ty_enum(..) | ty_ptr(..) | ty_struct(..) | ty_tup(..) |
930 ty_str | ty_vec(..) | ty_trait(..) | ty_closure(..) => {
931 self.search_for_some_kind_of_autorefd_method(
932 AutoPtr, autoderefs, [MutImmutable, MutMutable],
933 |m,r| ty::mk_rptr(tcx, r, ty::mt {ty:self_ty, mutbl:m}))
938 ty_infer(TyVar(_)) => {
939 self.bug(format!("unexpected type: {}",
940 self.ty_to_str(self_ty)).as_slice());
945 fn search_for_some_kind_of_autorefd_method(
947 kind: |Region, ast::Mutability| -> ty::AutoRef,
949 mutbls: &[ast::Mutability],
950 mk_autoref_ty: |ast::Mutability, ty::Region| -> ty::t)
951 -> Option<MethodCallee> {
952 // Hacky. For overloaded derefs, there may be an adjustment
953 // added to the expression from the outside context, so we do not store
954 // an explicit adjustment, but rather we hardwire the single deref
955 // that occurs in trans and mem_categorization.
956 let self_expr_id = match self.self_expr {
957 Some(expr) => Some(expr.id),
959 assert_eq!(autoderefs, 0);
960 assert_eq!(kind(ty::ReEmpty, ast::MutImmutable),
961 ty::AutoPtr(ty::ReEmpty, ast::MutImmutable));
966 // This is hokey. We should have mutability inference as a
967 // variable. But for now, try &const, then &, then &mut:
969 self.infcx().next_region_var(infer::Autoref(self.span));
970 for mutbl in mutbls.iter() {
971 let autoref_ty = mk_autoref_ty(*mutbl, region);
972 match self.search_for_method(autoref_ty) {
976 Some(self_expr_id) => {
977 self.fcx.write_adjustment(
979 ty::AutoDerefRef(ty::AutoDerefRef {
980 autoderefs: autoderefs,
981 autoref: Some(kind(region, *mutbl))
993 fn search_for_method(&self, rcvr_ty: ty::t) -> Option<MethodCallee> {
994 debug!("search_for_method(rcvr_ty={})", self.ty_to_str(rcvr_ty));
995 let _indenter = indenter();
997 // I am not sure that inherent methods should have higher
998 // priority, but it is necessary ATM to handle some of the
1001 debug!("searching inherent candidates");
1002 match self.consider_candidates(rcvr_ty, self.inherent_candidates.as_slice()) {
1009 debug!("searching extension candidates");
1010 self.consider_candidates(rcvr_ty, self.extension_candidates.as_slice())
1013 fn consider_candidates(&self, rcvr_ty: ty::t,
1014 candidates: &[Candidate])
1015 -> Option<MethodCallee> {
1016 let relevant_candidates = self.filter_candidates(rcvr_ty, candidates);
1018 if relevant_candidates.len() == 0 {
1022 if self.report_statics == ReportStaticMethods {
1023 // lookup should only be called with ReportStaticMethods if a regular lookup failed
1024 assert!(relevant_candidates.iter().all(|c| c.method_ty.explicit_self == SelfStatic));
1026 self.tcx().sess.fileline_note(self.span,
1027 "found defined static methods, maybe a `self` is missing?");
1029 for (idx, candidate) in relevant_candidates.iter().enumerate() {
1030 self.report_candidate(idx, &candidate.origin);
1033 // return something so we don't get errors for every mutability
1034 return Some(MethodCallee {
1035 origin: relevant_candidates.get(0).origin,
1037 substs: subst::Substs::empty()
1041 if relevant_candidates.len() > 1 {
1042 self.tcx().sess.span_err(
1044 "multiple applicable methods in scope");
1045 for (idx, candidate) in relevant_candidates.iter().enumerate() {
1046 self.report_candidate(idx, &candidate.origin);
1050 Some(self.confirm_candidate(rcvr_ty, relevant_candidates.get(0)))
1053 fn filter_candidates(&self, rcvr_ty: ty::t, candidates: &[Candidate]) -> Vec<Candidate> {
1054 let mut relevant_candidates: Vec<Candidate> = Vec::new();
1056 for candidate_a in candidates.iter().filter(|&c| self.is_relevant(rcvr_ty, c)) {
1057 // Skip this one if we already have one like it
1058 if !relevant_candidates.iter().any(|candidate_b| {
1059 debug!("attempting to merge {} and {}",
1060 candidate_a.repr(self.tcx()),
1061 candidate_b.repr(self.tcx()));
1062 match (&candidate_a.origin, &candidate_b.origin) {
1063 (&MethodParam(ref p1), &MethodParam(ref p2)) => {
1064 let same_trait = p1.trait_id == p2.trait_id;
1065 let same_method = p1.method_num == p2.method_num;
1066 let same_param = p1.param_num == p2.param_num;
1067 // The bound number may be different because
1068 // multiple bounds may lead to the same trait
1070 same_trait && same_method && same_param
1075 relevant_candidates.push(candidate_a.clone());
1082 fn confirm_candidate(&self, rcvr_ty: ty::t, candidate: &Candidate)
1085 // This method performs two sets of substitutions, one after the other:
1086 // 1. Substitute values for any type/lifetime parameters from the impl and
1087 // method declaration into the method type. This is the function type
1088 // before it is called; it may still include late bound region variables.
1089 // 2. Instantiate any late bound lifetime parameters in the method itself
1090 // with fresh region variables.
1092 let tcx = self.tcx();
1094 debug!("confirm_candidate(rcvr_ty={}, candidate={})",
1095 self.ty_to_str(rcvr_ty),
1096 candidate.repr(self.tcx()));
1098 self.enforce_object_limitations(candidate);
1099 self.enforce_drop_trait_limitations(candidate);
1101 // static methods should never have gotten this far:
1102 assert!(candidate.method_ty.explicit_self != SelfStatic);
1104 // Determine the values for the generic parameters of the method.
1105 // If they were not explicitly supplied, just construct fresh
1107 let num_supplied_tps = self.supplied_tps.len();
1108 let num_method_tps = candidate.method_ty.generics.types.len(subst::FnSpace);
1110 if num_supplied_tps == 0u {
1111 self.fcx.infcx().next_ty_vars(num_method_tps)
1112 } else if num_method_tps == 0u {
1115 "this method does not take type parameters");
1116 self.fcx.infcx().next_ty_vars(num_method_tps)
1117 } else if num_supplied_tps != num_method_tps {
1120 "incorrect number of type parameters given for this method");
1121 self.fcx.infcx().next_ty_vars(num_method_tps)
1123 Vec::from_slice(self.supplied_tps)
1127 // Create subst for early-bound lifetime parameters, combining
1128 // parameters from the type and those from the method.
1130 // FIXME -- permit users to manually specify lifetimes
1132 self.fcx.infcx().region_vars_for_defs(
1134 candidate.method_ty.generics.regions.get_vec(subst::FnSpace));
1136 let all_substs = candidate.rcvr_substs.clone().with_method(m_types, m_regions);
1138 let ref bare_fn_ty = candidate.method_ty.fty;
1140 // Compute the method type with type parameters substituted
1141 debug!("fty={} all_substs={}",
1142 bare_fn_ty.repr(tcx),
1143 all_substs.repr(tcx));
1145 let fn_sig = &bare_fn_ty.sig;
1146 let inputs = match candidate.origin {
1147 MethodObject(..) => {
1148 // For annoying reasons, we've already handled the
1149 // substitution of self for object calls.
1150 let args = fn_sig.inputs.slice_from(1).iter().map(|t| {
1151 t.subst(tcx, &all_substs)
1153 Some(*fn_sig.inputs.get(0)).move_iter().chain(args).collect()
1155 _ => fn_sig.inputs.subst(tcx, &all_substs)
1157 let fn_sig = ty::FnSig {
1158 binder_id: fn_sig.binder_id,
1160 output: fn_sig.output.subst(tcx, &all_substs),
1161 variadic: fn_sig.variadic
1164 debug!("after subst, fty={}", fn_sig.repr(tcx));
1166 // Replace any bound regions that appear in the function
1167 // signature with region variables
1168 let (_, fn_sig) = replace_late_bound_regions_in_fn_sig(
1170 |br| self.fcx.infcx().next_region_var(
1171 infer::LateBoundRegion(self.span, br)));
1172 let transformed_self_ty = *fn_sig.inputs.get(0);
1173 let fty = ty::mk_bare_fn(tcx, ty::BareFnTy {
1175 fn_style: bare_fn_ty.fn_style,
1176 abi: bare_fn_ty.abi.clone(),
1178 debug!("after replacing bound regions, fty={}", self.ty_to_str(fty));
1180 // Before, we only checked whether self_ty could be a subtype
1181 // of rcvr_ty; now we actually make it so (this may cause
1182 // variables to unify etc). Since we checked beforehand, and
1183 // nothing has changed in the meantime, this unification
1184 // should never fail.
1185 let span = self.self_expr.map_or(self.span, |e| e.span);
1186 match self.fcx.mk_subty(false, infer::Misc(span),
1187 rcvr_ty, transformed_self_ty) {
1191 "{} was a subtype of {} but now is not?",
1192 self.ty_to_str(rcvr_ty),
1193 self.ty_to_str(transformed_self_ty)).as_slice());
1198 origin: candidate.origin,
1204 fn enforce_object_limitations(&self, candidate: &Candidate) {
1206 * There are some limitations to calling functions through an
1207 * object, because (a) the self type is not known
1208 * (that's the whole point of a trait instance, after all, to
1209 * obscure the self type) and (b) the call must go through a
1210 * vtable and hence cannot be monomorphized.
1213 match candidate.origin {
1214 MethodStatic(..) | MethodParam(..) => {
1215 return; // not a call to a trait instance
1217 MethodObject(..) => {}
1220 match candidate.method_ty.explicit_self {
1221 ast::SelfStatic => { // reason (a) above
1222 self.tcx().sess.span_err(
1224 "cannot call a method without a receiver \
1225 through an object");
1228 ast::SelfValue => { // reason (a) above
1229 self.tcx().sess.span_err(
1231 "cannot call a method with a by-value receiver \
1232 through an object");
1235 ast::SelfRegion(..) | ast::SelfUniq => {}
1239 let check_for_self_ty = |ty| {
1240 if ty::type_has_self(ty) {
1241 self.tcx().sess.span_err(
1243 "cannot call a method whose type contains a \
1244 self-type through an object");
1250 let ref sig = candidate.method_ty.fty.sig;
1251 let mut found_self_ty = false;
1252 for &input_ty in sig.inputs.iter() {
1253 if check_for_self_ty(input_ty) {
1254 found_self_ty = true;
1259 check_for_self_ty(sig.output);
1262 if candidate.method_ty.generics.has_type_params(subst::FnSpace) {
1264 self.tcx().sess.span_err(
1266 "cannot call a generic method through an object");
1270 fn enforce_drop_trait_limitations(&self, candidate: &Candidate) {
1271 // No code can call the finalize method explicitly.
1273 match candidate.origin {
1274 MethodStatic(method_id) => {
1275 bad = self.tcx().destructors.borrow().contains(&method_id);
1277 // FIXME: does this properly enforce this on everything now
1278 // that self has been merged in? -sully
1279 MethodParam(MethodParam { trait_id: trait_id, .. }) |
1280 MethodObject(MethodObject { trait_id: trait_id, .. }) => {
1281 bad = self.tcx().destructor_for_type.borrow()
1282 .contains_key(&trait_id);
1287 self.tcx().sess.span_err(self.span,
1288 "explicit call to destructor");
1292 // `rcvr_ty` is the type of the expression. It may be a subtype of a
1293 // candidate method's `self_ty`.
1294 fn is_relevant(&self, rcvr_ty: ty::t, candidate: &Candidate) -> bool {
1295 debug!("is_relevant(rcvr_ty={}, candidate={})",
1296 self.ty_to_str(rcvr_ty), candidate.repr(self.tcx()));
1298 return match candidate.method_ty.explicit_self {
1300 debug!("(is relevant?) explicit self is static");
1301 self.report_statics == ReportStaticMethods
1305 rcvr_matches_ty(self.fcx, rcvr_ty, candidate)
1308 SelfRegion(_, m) => {
1309 debug!("(is relevant?) explicit self is a region");
1310 match ty::get(rcvr_ty).sty {
1311 ty::ty_rptr(_, mt) => {
1312 match ty::get(mt.ty).sty {
1313 ty::ty_vec(_, None) | ty::ty_str => false,
1314 ty::ty_trait(box ty::TyTrait { def_id: self_did, .. }) => {
1315 mutability_matches(mt.mutbl, m) &&
1316 rcvr_matches_object(self_did, candidate)
1318 _ => mutability_matches(mt.mutbl, m) &&
1319 rcvr_matches_ty(self.fcx, mt.ty, candidate),
1329 debug!("(is relevant?) explicit self is a unique pointer");
1330 match ty::get(rcvr_ty).sty {
1331 ty::ty_uniq(typ) => {
1332 match ty::get(typ).sty {
1333 ty::ty_vec(_, None) | ty::ty_str => false,
1334 ty::ty_trait(box ty::TyTrait { def_id: self_did, .. }) => {
1335 rcvr_matches_object(self_did, candidate)
1337 _ => rcvr_matches_ty(self.fcx, typ, candidate),
1346 fn rcvr_matches_object(self_did: ast::DefId,
1347 candidate: &Candidate) -> bool {
1348 match candidate.rcvr_match_condition {
1349 RcvrMatchesIfObject(desired_did) => {
1350 self_did == desired_did
1352 RcvrMatchesIfSubtype(_) => {
1358 fn rcvr_matches_ty(fcx: &FnCtxt,
1360 candidate: &Candidate) -> bool {
1361 match candidate.rcvr_match_condition {
1362 RcvrMatchesIfObject(_) => {
1365 RcvrMatchesIfSubtype(of_type) => {
1366 fcx.can_mk_subty(rcvr_ty, of_type).is_ok()
1371 fn mutability_matches(self_mutbl: ast::Mutability,
1372 candidate_mutbl: ast::Mutability)
1374 //! True if `self_mutbl <: candidate_mutbl`
1375 self_mutbl == candidate_mutbl
1379 fn report_candidate(&self, idx: uint, origin: &MethodOrigin) {
1381 MethodStatic(impl_did) => {
1382 let did = if self.report_statics == ReportStaticMethods {
1383 // If we're reporting statics, we want to report the trait
1384 // definition if possible, rather than an impl
1385 match ty::trait_method_of_method(self.tcx(), impl_did) {
1386 None => {debug!("(report candidate) No trait method found"); impl_did},
1387 Some(trait_did) => {debug!("(report candidate) Found trait ref"); trait_did}
1390 // If it is an instantiated default method, use the original
1391 // default method for error reporting.
1392 match provided_source(self.tcx(), impl_did) {
1397 self.report_static_candidate(idx, did)
1399 MethodParam(ref mp) => {
1400 self.report_param_candidate(idx, (*mp).trait_id)
1402 MethodObject(ref mo) => {
1403 self.report_trait_candidate(idx, mo.trait_id)
1408 fn report_static_candidate(&self, idx: uint, did: DefId) {
1409 let span = if did.krate == ast::LOCAL_CRATE {
1410 self.tcx().map.span(did.node)
1414 self.tcx().sess.span_note(
1416 format!("candidate #{} is `{}`",
1418 ty::item_path_str(self.tcx(), did)).as_slice());
1421 fn report_param_candidate(&self, idx: uint, did: DefId) {
1422 self.tcx().sess.span_note(
1424 format!("candidate #{} derives from the bound `{}`",
1426 ty::item_path_str(self.tcx(), did)).as_slice());
1429 fn report_trait_candidate(&self, idx: uint, did: DefId) {
1430 self.tcx().sess.span_note(
1432 format!("candidate #{} derives from the type of the receiver, \
1433 which is the trait `{}`",
1435 ty::item_path_str(self.tcx(), did)).as_slice());
1438 fn infcx(&'a self) -> &'a infer::InferCtxt<'a> {
1442 fn tcx(&self) -> &'a ty::ctxt {
1446 fn ty_to_str(&self, t: ty::t) -> String {
1447 self.fcx.infcx().ty_to_str(t)
1450 fn did_to_str(&self, did: DefId) -> String {
1451 ty::item_path_str(self.tcx(), did)
1454 fn bug(&self, s: &str) -> ! {
1455 self.tcx().sess.span_bug(self.span, s)
1459 impl Repr for Candidate {
1460 fn repr(&self, tcx: &ty::ctxt) -> String {
1461 format!("Candidate(rcvr_ty={}, rcvr_substs={}, method_ty={}, \
1463 self.rcvr_match_condition.repr(tcx),
1464 self.rcvr_substs.repr(tcx),
1465 self.method_ty.repr(tcx),
1470 impl Repr for RcvrMatchCondition {
1471 fn repr(&self, tcx: &ty::ctxt) -> String {
1473 RcvrMatchesIfObject(d) => {
1474 format!("RcvrMatchesIfObject({})", d.repr(tcx))
1476 RcvrMatchesIfSubtype(t) => {
1477 format!("RcvrMatchesIfSubtype({})", t.repr(tcx))