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 let tr = ty::mk_trait(tcx, trait_def_id, obj_substs,
275 ty::empty_builtin_bounds());
278 ast::SelfRegion(..) | ast::SelfUniq => {
279 let transformed_self_ty = *method_ty.fty.sig.inputs.get(0);
280 match ty::get(transformed_self_ty).sty {
281 ty::ty_rptr(r, mt) => { // must be SelfRegion
282 let r = r.subst(tcx, rcvr_substs); // handle Early-Bound lifetime
283 let tr = ty::mk_trait(tcx, trait_def_id, obj_substs,
284 ty::empty_builtin_bounds());
285 ty::mk_rptr(tcx, r, ty::mt{ ty: tr, mutbl: mt.mutbl })
287 ty::ty_uniq(_) => { // must be SelfUniq
288 let tr = ty::mk_trait(tcx, trait_def_id, obj_substs,
289 ty::empty_builtin_bounds());
293 tcx.sess.span_bug(span,
294 format!("'impossible' transformed_self_ty: {}",
295 transformed_self_ty.repr(tcx)).as_slice());
302 struct LookupContext<'a> {
306 // The receiver to the method call. Only `None` in the case of
307 // an overloaded autoderef, where the receiver may be an intermediate
308 // state like "the expression `x` when it has been autoderef'd
310 self_expr: Option<&'a ast::Expr>,
313 supplied_tps: &'a [ty::t],
314 impl_dups: HashSet<DefId>,
315 inherent_candidates: Vec<Candidate>,
316 extension_candidates: Vec<Candidate>,
317 deref_args: check::DerefArgs,
318 check_traits: CheckTraitsFlag,
319 autoderef_receiver: AutoderefReceiverFlag,
320 report_statics: StaticMethodsFlag,
324 * A potential method that might be called, assuming the receiver
325 * is of a suitable type.
329 rcvr_match_condition: RcvrMatchCondition,
330 rcvr_substs: subst::Substs,
331 method_ty: Rc<ty::Method>,
332 origin: MethodOrigin,
335 /// This type represents the conditions under which the receiver is
336 /// considered to "match" a given method candidate. Typically the test
337 /// is whether the receiver is of a particular type. However, this
338 /// type is the type of the receiver *after accounting for the
339 /// method's self type* (e.g., if the method is an `Box<self>` method, we
340 /// have *already verified* that the receiver is of some type `Box<T>` and
341 /// now we must check that the type `T` is correct). Unfortunately,
342 /// because traits are not types, this is a pain to do.
344 pub enum RcvrMatchCondition {
345 RcvrMatchesIfObject(ast::DefId),
346 RcvrMatchesIfSubtype(ty::t)
349 impl<'a> LookupContext<'a> {
350 fn search(&self, self_ty: ty::t) -> Option<MethodCallee> {
351 let span = self.self_expr.map_or(self.span, |e| e.span);
352 let self_expr_id = self.self_expr.map(|e| e.id);
354 let (self_ty, autoderefs, result) =
356 self.fcx, span, self_ty, self_expr_id, PreferMutLvalue,
357 |self_ty, autoderefs| self.search_step(self_ty, autoderefs));
360 Some(Some(result)) => Some(result),
362 if self.is_overloaded_deref() {
363 // If we are searching for an overloaded deref, no
364 // need to try coercing a `~[T]` to an `&[T]` and
365 // searching for an overloaded deref on *that*.
368 self.search_for_autosliced_method(self_ty, autoderefs)
374 fn search_step(&self,
377 -> Option<Option<MethodCallee>> {
378 debug!("search_step: self_ty={} autoderefs={}",
379 self.ty_to_str(self_ty), autoderefs);
381 match self.deref_args {
382 check::DontDerefArgs => {
383 match self.search_for_autoderefd_method(self_ty, autoderefs) {
384 Some(result) => return Some(Some(result)),
388 match self.search_for_autoptrd_method(self_ty, autoderefs) {
389 Some(result) => return Some(Some(result)),
393 check::DoDerefArgs => {
394 match self.search_for_autoptrd_method(self_ty, autoderefs) {
395 Some(result) => return Some(Some(result)),
399 match self.search_for_autoderefd_method(self_ty, autoderefs) {
400 Some(result) => return Some(Some(result)),
406 // Don't autoderef if we aren't supposed to.
407 if self.autoderef_receiver == DontAutoderefReceiver {
414 fn is_overloaded_deref(&self) -> bool {
415 self.self_expr.is_none()
418 // ______________________________________________________________________
419 // Candidate collection (see comment at start of file)
421 fn reset_candidates(&mut self) {
422 self.inherent_candidates = Vec::new();
423 self.extension_candidates = Vec::new();
426 fn push_inherent_candidates(&mut self, self_ty: ty::t) {
428 * Collect all inherent candidates into
429 * `self.inherent_candidates`. See comment at the start of
430 * the file. To find the inherent candidates, we repeatedly
431 * deref the self-ty to find the "base-type". So, for
432 * example, if the receiver is Box<Box<C>> where `C` is a struct type,
433 * we'll want to find the inherent impls for `C`.
436 let span = self.self_expr.map_or(self.span, |e| e.span);
437 check::autoderef(self.fcx, span, self_ty, None, PreferMutLvalue, |self_ty, _| {
438 match get(self_ty).sty {
439 ty_uniq(ty) | ty_rptr(_, mt {ty, ..}) => match get(ty).sty{
440 ty_trait(box TyTrait { def_id, ref substs, .. }) => {
441 self.push_inherent_candidates_from_object(def_id, substs);
442 self.push_inherent_impl_candidates_for_type(def_id);
446 ty_enum(did, _) | ty_struct(did, _) => {
447 if self.check_traits == CheckTraitsAndInherentMethods {
448 self.push_inherent_impl_candidates_for_type(did);
451 _ => { /* No inherent methods in these types */ }
454 // Don't autoderef if we aren't supposed to.
455 if self.autoderef_receiver == DontAutoderefReceiver {
463 fn push_bound_candidates(&mut self, self_ty: ty::t, restrict_to: Option<DefId>) {
464 let span = self.self_expr.map_or(self.span, |e| e.span);
465 check::autoderef(self.fcx, span, self_ty, None, PreferMutLvalue, |self_ty, _| {
466 match get(self_ty).sty {
468 self.push_inherent_candidates_from_param(self_ty, restrict_to, p);
470 _ => { /* No bound methods in these types */ }
473 // Don't autoderef if we aren't supposed to.
474 if self.autoderef_receiver == DontAutoderefReceiver {
482 fn push_extension_candidate(&mut self, trait_did: DefId) {
483 ty::populate_implementations_for_trait_if_necessary(self.tcx(), trait_did);
485 // Look for explicit implementations.
486 let impl_methods = self.tcx().impl_methods.borrow();
487 for impl_infos in self.tcx().trait_impls.borrow().find(&trait_did).iter() {
488 for impl_did in impl_infos.borrow().iter() {
489 let methods = impl_methods.get(impl_did);
490 self.push_candidates_from_impl(*impl_did, methods.as_slice(), true);
495 fn push_extension_candidates(&mut self, expr_id: ast::NodeId) {
496 // If the method being called is associated with a trait, then
497 // find all the impls of that trait. Each of those are
499 let opt_applicable_traits = self.fcx.ccx.trait_map.find(&expr_id);
500 for applicable_traits in opt_applicable_traits.move_iter() {
501 for trait_did in applicable_traits.iter() {
502 self.push_extension_candidate(*trait_did);
507 fn push_inherent_candidates_from_object(&mut self,
509 substs: &subst::Substs) {
510 debug!("push_inherent_candidates_from_object(did={}, substs={})",
511 self.did_to_str(did),
512 substs.repr(self.tcx()));
513 let _indenter = indenter();
514 let tcx = self.tcx();
515 let span = self.span;
517 // It is illegal to invoke a method on a trait instance that
518 // refers to the `self` type. An error will be reported by
519 // `enforce_object_limitations()` if the method refers
520 // to the `Self` type. Substituting ty_err here allows
521 // compiler to soldier on.
523 // `confirm_candidate()` also relies upon this substitution
525 let rcvr_substs = substs.with_self_ty(ty::mk_err());
526 let trait_ref = Rc::new(TraitRef {
528 substs: rcvr_substs.clone()
531 self.push_inherent_candidates_from_bounds_inner(&[trait_ref.clone()],
532 |new_trait_ref, m, method_num, _bound_num| {
533 let vtable_index = get_method_index(tcx, &*new_trait_ref,
534 trait_ref.clone(), method_num);
535 let mut m = (*m).clone();
536 // We need to fix up the transformed self type.
537 *m.fty.sig.inputs.get_mut(0) =
538 construct_transformed_self_ty_for_object(
539 tcx, span, did, &rcvr_substs, &m);
542 rcvr_match_condition: RcvrMatchesIfObject(did),
543 rcvr_substs: new_trait_ref.substs.clone(),
544 method_ty: Rc::new(m),
545 origin: MethodObject(MethodObject {
546 trait_id: new_trait_ref.def_id,
547 object_trait_id: did,
548 method_num: method_num,
549 real_index: vtable_index
555 fn push_inherent_candidates_from_param(&mut self,
557 restrict_to: Option<DefId>,
559 debug!("push_inherent_candidates_from_param(param_ty={:?})",
561 self.push_inherent_candidates_from_bounds(
566 param_index { space: param_ty.space, index: param_ty.idx });
570 fn push_inherent_candidates_from_bounds(&mut self,
572 space: subst::ParamSpace,
574 restrict_to: Option<DefId>,
575 param: param_index) {
577 self.fcx.inh.param_env.bounds.get(space, index).trait_bounds
579 self.push_inherent_candidates_from_bounds_inner(bounds,
580 |trait_ref, m, method_num, bound_num| {
583 if trait_did != trait_ref.def_id {
590 rcvr_match_condition: RcvrMatchesIfSubtype(self_ty),
591 rcvr_substs: trait_ref.substs.clone(),
593 origin: MethodParam(MethodParam {
594 trait_id: trait_ref.def_id,
595 method_num: method_num,
597 bound_num: bound_num,
603 // Do a search through a list of bounds, using a callback to actually
604 // create the candidates.
605 fn push_inherent_candidates_from_bounds_inner(&mut self,
606 bounds: &[Rc<TraitRef>],
607 mk_cand: |tr: Rc<TraitRef>,
611 -> Option<Candidate>) {
612 let tcx = self.tcx();
613 let mut next_bound_idx = 0; // count only trait bounds
615 ty::each_bound_trait_and_supertraits(tcx, bounds, |bound_trait_ref| {
616 let this_bound_idx = next_bound_idx;
619 let trait_methods = ty::trait_methods(tcx, bound_trait_ref.def_id);
620 match trait_methods.iter().position(|m| {
621 m.explicit_self != ast::SelfStatic &&
622 m.ident.name == self.m_name }) {
624 let method = trait_methods.get(pos).clone();
626 match mk_cand(bound_trait_ref, method, pos, this_bound_idx) {
628 debug!("pushing inherent candidate for param: {}",
629 cand.repr(self.tcx()));
630 self.inherent_candidates.push(cand);
636 debug!("trait doesn't contain method: {:?}",
637 bound_trait_ref.def_id);
638 // check next trait or bound
646 fn push_inherent_impl_candidates_for_type(&mut self, did: DefId) {
647 // Read the inherent implementation candidates for this type from the
648 // metadata if necessary.
649 ty::populate_implementations_for_type_if_necessary(self.tcx(), did);
651 let impl_methods = self.tcx().impl_methods.borrow();
652 for impl_infos in self.tcx().inherent_impls.borrow().find(&did).iter() {
653 for impl_did in impl_infos.borrow().iter() {
654 let methods = impl_methods.get(impl_did);
655 self.push_candidates_from_impl(*impl_did, methods.as_slice(), false);
660 fn push_candidates_from_impl(&mut self,
662 impl_methods: &[DefId],
663 is_extension: bool) {
664 let did = if self.report_statics == ReportStaticMethods {
665 // we only want to report each base trait once
666 match ty::impl_trait_ref(self.tcx(), impl_did) {
667 Some(trait_ref) => trait_ref.def_id,
674 if !self.impl_dups.insert(did) {
675 return; // already visited
678 debug!("push_candidates_from_impl: {} {}",
679 token::get_name(self.m_name),
680 impl_methods.iter().map(|&did| ty::method(self.tcx(), did).ident)
681 .collect::<Vec<ast::Ident>>()
684 let method = match impl_methods.iter().map(|&did| ty::method(self.tcx(), did))
685 .find(|m| m.ident.name == self.m_name) {
686 Some(method) => method,
687 None => { return; } // No method with the right name.
690 // determine the `self` of the impl with fresh
691 // variables for each parameter:
692 let span = self.self_expr.map_or(self.span, |e| e.span);
693 let vcx = self.fcx.vtable_context();
697 } = impl_self_ty(&vcx, span, impl_did);
699 let candidates = if is_extension {
700 &mut self.extension_candidates
702 &mut self.inherent_candidates
705 candidates.push(Candidate {
706 rcvr_match_condition: RcvrMatchesIfSubtype(impl_ty),
707 rcvr_substs: impl_substs,
708 origin: MethodStatic(method.def_id),
713 // ______________________________________________________________________
714 // Candidate selection (see comment at start of file)
716 fn search_for_autoderefd_method(&self,
719 -> Option<MethodCallee> {
720 let (self_ty, auto_deref_ref) =
721 self.consider_reborrow(self_ty, autoderefs);
723 // Hacky. For overloaded derefs, there may be an adjustment
724 // added to the expression from the outside context, so we do not store
725 // an explicit adjustment, but rather we hardwire the single deref
726 // that occurs in trans and mem_categorization.
727 let adjustment = match self.self_expr {
728 Some(expr) => Some((expr.id, ty::AutoDerefRef(auto_deref_ref))),
732 match self.search_for_method(self_ty) {
735 debug!("(searching for autoderef'd method) writing \
736 adjustment {:?} for {}", adjustment, self.ty_to_str( self_ty));
738 Some((self_expr_id, adj)) => {
739 self.fcx.write_adjustment(self_expr_id, adj);
748 fn consider_reborrow(&self,
751 -> (ty::t, ty::AutoDerefRef) {
753 * In the event that we are invoking a method with a receiver
754 * of a borrowed type like `&T`, `&mut T`, or `&mut [T]`,
755 * we will "reborrow" the receiver implicitly. For example, if
756 * you have a call `r.inc()` and where `r` has type `&mut T`,
757 * then we treat that like `(&mut *r).inc()`. This avoids
758 * consuming the original pointer.
760 * You might think that this would be a natural byproduct of
761 * the auto-deref/auto-ref process. This is true for `Box<T>`
762 * but not for an `&mut T` receiver. With `Box<T>`, we would
763 * begin by testing for methods with a self type `Box<T>`,
764 * then autoderef to `T`, then autoref to `&mut T`. But with
765 * an `&mut T` receiver the process begins with `&mut T`, only
766 * without any autoadjustments.
769 let tcx = self.tcx();
770 return match ty::get(self_ty).sty {
771 ty::ty_rptr(_, self_mt) if default_method_hack(self_mt) => {
774 autoderefs: autoderefs,
777 ty::ty_rptr(_, self_mt) => {
779 self.infcx().next_region_var(infer::Autoref(self.span));
780 let (extra_derefs, auto) = match ty::get(self_mt.ty).sty {
781 ty::ty_vec(_, None) => (0, ty::AutoBorrowVec(region, self_mt.mutbl)),
782 ty::ty_str => (0, ty::AutoBorrowVec(region, self_mt.mutbl)),
783 ty::ty_trait(..) => (0, ty::AutoBorrowObj(region, self_mt.mutbl)),
784 _ => (1, ty::AutoPtr(region, self_mt.mutbl)),
786 (ty::mk_rptr(tcx, region, self_mt),
788 autoderefs: autoderefs + extra_derefs,
789 autoref: Some(auto)})
794 autoderefs: autoderefs,
799 fn default_method_hack(self_mt: ty::mt) -> bool {
800 // FIXME(#6129). Default methods can't deal with autoref.
802 // I am a horrible monster and I pray for death. Currently
803 // the default method code fails when you try to reborrow
804 // because it is not handling types correctly. In lieu of
805 // fixing that, I am introducing this horrible hack. - ndm
806 self_mt.mutbl == MutImmutable && ty::type_is_self(self_mt.ty)
810 fn auto_slice_vec(&self, mt: ty::mt, autoderefs: uint) -> Option<MethodCallee> {
811 let tcx = self.tcx();
812 debug!("auto_slice_vec {}", ppaux::ty_to_str(tcx, mt.ty));
814 // First try to borrow to a slice
815 let entry = self.search_for_some_kind_of_autorefd_method(
816 AutoBorrowVec, autoderefs, [MutImmutable, MutMutable],
817 |m,r| ty::mk_slice(tcx, r,
818 ty::mt {ty:mt.ty, mutbl:m}));
824 // Then try to borrow to a slice *and* borrow a pointer.
825 self.search_for_some_kind_of_autorefd_method(
826 AutoBorrowVecRef, autoderefs, [MutImmutable, MutMutable],
828 let slice_ty = ty::mk_slice(tcx, r,
829 ty::mt {ty:mt.ty, mutbl:m});
830 // NB: we do not try to autoref to a mutable
831 // pointer. That would be creating a pointer
832 // to a temporary pointer (the borrowed
833 // slice), so any update the callee makes to
834 // it can't be observed.
835 ty::mk_rptr(tcx, r, ty::mt {ty:slice_ty, mutbl:MutImmutable})
840 fn auto_slice_str(&self, autoderefs: uint) -> Option<MethodCallee> {
841 let tcx = self.tcx();
842 debug!("auto_slice_str");
844 let entry = self.search_for_some_kind_of_autorefd_method(
845 AutoBorrowVec, autoderefs, [MutImmutable],
846 |_m,r| ty::mk_str_slice(tcx, r, MutImmutable));
852 self.search_for_some_kind_of_autorefd_method(
853 AutoBorrowVecRef, autoderefs, [MutImmutable],
855 let slice_ty = ty::mk_str_slice(tcx, r, m);
856 ty::mk_rptr(tcx, r, ty::mt {ty:slice_ty, mutbl:m})
860 // Coerce Box/&Trait instances to &Trait.
861 fn auto_slice_trait(&self, ty: ty::t, autoderefs: uint) -> Option<MethodCallee> {
862 match ty::get(ty).sty {
863 ty_trait(box ty::TyTrait {
865 substs: ref trt_substs,
868 let tcx = self.tcx();
869 self.search_for_some_kind_of_autorefd_method(
870 AutoBorrowObj, autoderefs, [MutImmutable, MutMutable],
872 let tr = ty::mk_trait(tcx, trt_did, trt_substs.clone(), b);
873 ty::mk_rptr(tcx, r, ty::mt{ ty: tr, mutbl: m })
876 _ => fail!("Expected ty_trait in auto_slice_trait")
880 fn search_for_autosliced_method(&self,
883 -> Option<MethodCallee> {
885 * Searches for a candidate by converting things like
889 debug!("search_for_autosliced_method {}", ppaux::ty_to_str(self.tcx(), self_ty));
891 let sty = ty::get(self_ty).sty.clone();
893 ty_rptr(_, mt) => match ty::get(mt.ty).sty {
894 ty_vec(mt, None) => self.auto_slice_vec(mt, autoderefs),
895 ty_trait(..) => self.auto_slice_trait(mt.ty, autoderefs),
898 ty_uniq(t) => match ty::get(t).sty {
899 ty_vec(mt, None) => self.auto_slice_vec(mt, autoderefs),
900 ty_str => self.auto_slice_str(autoderefs),
901 ty_trait(..) => self.auto_slice_trait(t, autoderefs),
904 ty_vec(mt, Some(_)) => self.auto_slice_vec(mt, autoderefs),
907 // This case should probably be handled similarly to
916 fn search_for_autoptrd_method(&self, self_ty: ty::t, autoderefs: uint)
917 -> Option<MethodCallee> {
920 * Converts any type `T` to `&M T` where `M` is an
921 * appropriate mutability.
924 let tcx = self.tcx();
925 match ty::get(self_ty).sty {
926 ty_bare_fn(..) | ty_box(..) | ty_uniq(..) | ty_rptr(..) |
927 ty_infer(IntVar(_)) |
928 ty_infer(FloatVar(_)) |
929 ty_param(..) | ty_nil | ty_bot | ty_bool |
930 ty_char | ty_int(..) | ty_uint(..) |
931 ty_float(..) | ty_enum(..) | ty_ptr(..) | ty_struct(..) | ty_tup(..) |
932 ty_str | ty_vec(..) | ty_trait(..) | ty_closure(..) => {
933 self.search_for_some_kind_of_autorefd_method(
934 AutoPtr, autoderefs, [MutImmutable, MutMutable],
935 |m,r| ty::mk_rptr(tcx, r, ty::mt {ty:self_ty, mutbl:m}))
940 ty_infer(TyVar(_)) => {
941 self.bug(format!("unexpected type: {}",
942 self.ty_to_str(self_ty)).as_slice());
947 fn search_for_some_kind_of_autorefd_method(
949 kind: |Region, ast::Mutability| -> ty::AutoRef,
951 mutbls: &[ast::Mutability],
952 mk_autoref_ty: |ast::Mutability, ty::Region| -> ty::t)
953 -> Option<MethodCallee> {
954 // Hacky. For overloaded derefs, there may be an adjustment
955 // added to the expression from the outside context, so we do not store
956 // an explicit adjustment, but rather we hardwire the single deref
957 // that occurs in trans and mem_categorization.
958 let self_expr_id = match self.self_expr {
959 Some(expr) => Some(expr.id),
961 assert_eq!(autoderefs, 0);
962 assert_eq!(kind(ty::ReEmpty, ast::MutImmutable),
963 ty::AutoPtr(ty::ReEmpty, ast::MutImmutable));
968 // This is hokey. We should have mutability inference as a
969 // variable. But for now, try &const, then &, then &mut:
971 self.infcx().next_region_var(infer::Autoref(self.span));
972 for mutbl in mutbls.iter() {
973 let autoref_ty = mk_autoref_ty(*mutbl, region);
974 match self.search_for_method(autoref_ty) {
978 Some(self_expr_id) => {
979 self.fcx.write_adjustment(
981 ty::AutoDerefRef(ty::AutoDerefRef {
982 autoderefs: autoderefs,
983 autoref: Some(kind(region, *mutbl))
995 fn search_for_method(&self, rcvr_ty: ty::t) -> Option<MethodCallee> {
996 debug!("search_for_method(rcvr_ty={})", self.ty_to_str(rcvr_ty));
997 let _indenter = indenter();
999 // I am not sure that inherent methods should have higher
1000 // priority, but it is necessary ATM to handle some of the
1003 debug!("searching inherent candidates");
1004 match self.consider_candidates(rcvr_ty, self.inherent_candidates.as_slice()) {
1011 debug!("searching extension candidates");
1012 self.consider_candidates(rcvr_ty, self.extension_candidates.as_slice())
1015 fn consider_candidates(&self, rcvr_ty: ty::t,
1016 candidates: &[Candidate])
1017 -> Option<MethodCallee> {
1018 let relevant_candidates = self.filter_candidates(rcvr_ty, candidates);
1020 if relevant_candidates.len() == 0 {
1024 if self.report_statics == ReportStaticMethods {
1025 // lookup should only be called with ReportStaticMethods if a regular lookup failed
1026 assert!(relevant_candidates.iter().all(|c| c.method_ty.explicit_self == SelfStatic));
1028 self.tcx().sess.fileline_note(self.span,
1029 "found defined static methods, maybe a `self` is missing?");
1031 for (idx, candidate) in relevant_candidates.iter().enumerate() {
1032 self.report_candidate(idx, &candidate.origin);
1035 // return something so we don't get errors for every mutability
1036 return Some(MethodCallee {
1037 origin: relevant_candidates.get(0).origin,
1039 substs: subst::Substs::empty()
1043 if relevant_candidates.len() > 1 {
1044 self.tcx().sess.span_err(
1046 "multiple applicable methods in scope");
1047 for (idx, candidate) in relevant_candidates.iter().enumerate() {
1048 self.report_candidate(idx, &candidate.origin);
1052 Some(self.confirm_candidate(rcvr_ty, relevant_candidates.get(0)))
1055 fn filter_candidates(&self, rcvr_ty: ty::t, candidates: &[Candidate]) -> Vec<Candidate> {
1056 let mut relevant_candidates: Vec<Candidate> = Vec::new();
1058 for candidate_a in candidates.iter().filter(|&c| self.is_relevant(rcvr_ty, c)) {
1059 // Skip this one if we already have one like it
1060 if !relevant_candidates.iter().any(|candidate_b| {
1061 debug!("attempting to merge {} and {}",
1062 candidate_a.repr(self.tcx()),
1063 candidate_b.repr(self.tcx()));
1064 match (&candidate_a.origin, &candidate_b.origin) {
1065 (&MethodParam(ref p1), &MethodParam(ref p2)) => {
1066 let same_trait = p1.trait_id == p2.trait_id;
1067 let same_method = p1.method_num == p2.method_num;
1068 let same_param = p1.param_num == p2.param_num;
1069 // The bound number may be different because
1070 // multiple bounds may lead to the same trait
1072 same_trait && same_method && same_param
1077 relevant_candidates.push(candidate_a.clone());
1084 fn confirm_candidate(&self, rcvr_ty: ty::t, candidate: &Candidate)
1087 // This method performs two sets of substitutions, one after the other:
1088 // 1. Substitute values for any type/lifetime parameters from the impl and
1089 // method declaration into the method type. This is the function type
1090 // before it is called; it may still include late bound region variables.
1091 // 2. Instantiate any late bound lifetime parameters in the method itself
1092 // with fresh region variables.
1094 let tcx = self.tcx();
1096 debug!("confirm_candidate(rcvr_ty={}, candidate={})",
1097 self.ty_to_str(rcvr_ty),
1098 candidate.repr(self.tcx()));
1100 self.enforce_object_limitations(candidate);
1101 self.enforce_drop_trait_limitations(candidate);
1103 // static methods should never have gotten this far:
1104 assert!(candidate.method_ty.explicit_self != SelfStatic);
1106 // Determine the values for the generic parameters of the method.
1107 // If they were not explicitly supplied, just construct fresh
1109 let num_supplied_tps = self.supplied_tps.len();
1110 let num_method_tps = candidate.method_ty.generics.types.len(subst::FnSpace);
1112 if num_supplied_tps == 0u {
1113 self.fcx.infcx().next_ty_vars(num_method_tps)
1114 } else if num_method_tps == 0u {
1117 "this method does not take type parameters");
1118 self.fcx.infcx().next_ty_vars(num_method_tps)
1119 } else if num_supplied_tps != num_method_tps {
1122 "incorrect number of type parameters given for this method");
1123 self.fcx.infcx().next_ty_vars(num_method_tps)
1125 Vec::from_slice(self.supplied_tps)
1129 // Create subst for early-bound lifetime parameters, combining
1130 // parameters from the type and those from the method.
1132 // FIXME -- permit users to manually specify lifetimes
1134 self.fcx.infcx().region_vars_for_defs(
1136 candidate.method_ty.generics.regions.get_vec(subst::FnSpace));
1138 let all_substs = candidate.rcvr_substs.clone().with_method(m_types, m_regions);
1140 let ref bare_fn_ty = candidate.method_ty.fty;
1142 // Compute the method type with type parameters substituted
1143 debug!("fty={} all_substs={}",
1144 bare_fn_ty.repr(tcx),
1145 all_substs.repr(tcx));
1147 let fn_sig = &bare_fn_ty.sig;
1148 let inputs = match candidate.origin {
1149 MethodObject(..) => {
1150 // For annoying reasons, we've already handled the
1151 // substitution of self for object calls.
1152 let args = fn_sig.inputs.slice_from(1).iter().map(|t| {
1153 t.subst(tcx, &all_substs)
1155 Some(*fn_sig.inputs.get(0)).move_iter().chain(args).collect()
1157 _ => fn_sig.inputs.subst(tcx, &all_substs)
1159 let fn_sig = ty::FnSig {
1160 binder_id: fn_sig.binder_id,
1162 output: fn_sig.output.subst(tcx, &all_substs),
1163 variadic: fn_sig.variadic
1166 debug!("after subst, fty={}", fn_sig.repr(tcx));
1168 // Replace any bound regions that appear in the function
1169 // signature with region variables
1170 let (_, fn_sig) = replace_late_bound_regions_in_fn_sig(
1172 |br| self.fcx.infcx().next_region_var(
1173 infer::LateBoundRegion(self.span, br)));
1174 let transformed_self_ty = *fn_sig.inputs.get(0);
1175 let fty = ty::mk_bare_fn(tcx, ty::BareFnTy {
1177 fn_style: bare_fn_ty.fn_style,
1178 abi: bare_fn_ty.abi.clone(),
1180 debug!("after replacing bound regions, fty={}", self.ty_to_str(fty));
1182 // Before, we only checked whether self_ty could be a subtype
1183 // of rcvr_ty; now we actually make it so (this may cause
1184 // variables to unify etc). Since we checked beforehand, and
1185 // nothing has changed in the meantime, this unification
1186 // should never fail.
1187 let span = self.self_expr.map_or(self.span, |e| e.span);
1188 match self.fcx.mk_subty(false, infer::Misc(span),
1189 rcvr_ty, transformed_self_ty) {
1193 "{} was a subtype of {} but now is not?",
1194 self.ty_to_str(rcvr_ty),
1195 self.ty_to_str(transformed_self_ty)).as_slice());
1200 origin: candidate.origin,
1206 fn enforce_object_limitations(&self, candidate: &Candidate) {
1208 * There are some limitations to calling functions through an
1209 * object, because (a) the self type is not known
1210 * (that's the whole point of a trait instance, after all, to
1211 * obscure the self type) and (b) the call must go through a
1212 * vtable and hence cannot be monomorphized.
1215 match candidate.origin {
1216 MethodStatic(..) | MethodParam(..) => {
1217 return; // not a call to a trait instance
1219 MethodObject(..) => {}
1222 match candidate.method_ty.explicit_self {
1223 ast::SelfStatic => { // reason (a) above
1224 self.tcx().sess.span_err(
1226 "cannot call a method without a receiver \
1227 through an object");
1230 ast::SelfValue | ast::SelfRegion(..) | ast::SelfUniq => {}
1234 let check_for_self_ty = |ty| {
1235 if ty::type_has_self(ty) {
1236 self.tcx().sess.span_err(
1238 "cannot call a method whose type contains a \
1239 self-type through an object");
1245 let ref sig = candidate.method_ty.fty.sig;
1246 let mut found_self_ty = false;
1247 for &input_ty in sig.inputs.iter() {
1248 if check_for_self_ty(input_ty) {
1249 found_self_ty = true;
1254 check_for_self_ty(sig.output);
1257 if candidate.method_ty.generics.has_type_params(subst::FnSpace) {
1259 self.tcx().sess.span_err(
1261 "cannot call a generic method through an object");
1265 fn enforce_drop_trait_limitations(&self, candidate: &Candidate) {
1266 // No code can call the finalize method explicitly.
1268 match candidate.origin {
1269 MethodStatic(method_id) => {
1270 bad = self.tcx().destructors.borrow().contains(&method_id);
1272 // FIXME: does this properly enforce this on everything now
1273 // that self has been merged in? -sully
1274 MethodParam(MethodParam { trait_id: trait_id, .. }) |
1275 MethodObject(MethodObject { trait_id: trait_id, .. }) => {
1276 bad = self.tcx().destructor_for_type.borrow()
1277 .contains_key(&trait_id);
1282 self.tcx().sess.span_err(self.span,
1283 "explicit call to destructor");
1287 // `rcvr_ty` is the type of the expression. It may be a subtype of a
1288 // candidate method's `self_ty`.
1289 fn is_relevant(&self, rcvr_ty: ty::t, candidate: &Candidate) -> bool {
1290 debug!("is_relevant(rcvr_ty={}, candidate={})",
1291 self.ty_to_str(rcvr_ty), candidate.repr(self.tcx()));
1293 return match candidate.method_ty.explicit_self {
1295 debug!("(is relevant?) explicit self is static");
1296 self.report_statics == ReportStaticMethods
1300 debug!("(is relevant?) explicit self is by-value");
1301 match ty::get(rcvr_ty).sty {
1302 ty::ty_uniq(typ) => {
1303 match ty::get(typ).sty {
1304 ty::ty_trait(box ty::TyTrait {
1308 rcvr_matches_object(self_did, candidate) ||
1309 rcvr_matches_ty(self.fcx,
1314 rcvr_matches_ty(self.fcx, rcvr_ty, candidate)
1318 _ => rcvr_matches_ty(self.fcx, rcvr_ty, candidate)
1322 SelfRegion(_, m) => {
1323 debug!("(is relevant?) explicit self is a region");
1324 match ty::get(rcvr_ty).sty {
1325 ty::ty_rptr(_, mt) => {
1326 match ty::get(mt.ty).sty {
1327 ty::ty_vec(_, None) | ty::ty_str => false,
1328 ty::ty_trait(box ty::TyTrait { def_id: self_did, .. }) => {
1329 mutability_matches(mt.mutbl, m) &&
1330 rcvr_matches_object(self_did, candidate)
1332 _ => mutability_matches(mt.mutbl, m) &&
1333 rcvr_matches_ty(self.fcx, mt.ty, candidate),
1343 debug!("(is relevant?) explicit self is a unique pointer");
1344 match ty::get(rcvr_ty).sty {
1345 ty::ty_uniq(typ) => {
1346 match ty::get(typ).sty {
1347 ty::ty_vec(_, None) | ty::ty_str => false,
1348 ty::ty_trait(box ty::TyTrait { def_id: self_did, .. }) => {
1349 rcvr_matches_object(self_did, candidate)
1351 _ => rcvr_matches_ty(self.fcx, typ, candidate),
1360 fn rcvr_matches_object(self_did: ast::DefId,
1361 candidate: &Candidate) -> bool {
1362 match candidate.rcvr_match_condition {
1363 RcvrMatchesIfObject(desired_did) => {
1364 self_did == desired_did
1366 RcvrMatchesIfSubtype(_) => {
1372 fn rcvr_matches_ty(fcx: &FnCtxt,
1374 candidate: &Candidate) -> bool {
1375 match candidate.rcvr_match_condition {
1376 RcvrMatchesIfObject(_) => {
1379 RcvrMatchesIfSubtype(of_type) => {
1380 fcx.can_mk_subty(rcvr_ty, of_type).is_ok()
1385 fn mutability_matches(self_mutbl: ast::Mutability,
1386 candidate_mutbl: ast::Mutability)
1388 //! True if `self_mutbl <: candidate_mutbl`
1389 self_mutbl == candidate_mutbl
1393 fn report_candidate(&self, idx: uint, origin: &MethodOrigin) {
1395 MethodStatic(impl_did) => {
1396 let did = if self.report_statics == ReportStaticMethods {
1397 // If we're reporting statics, we want to report the trait
1398 // definition if possible, rather than an impl
1399 match ty::trait_method_of_method(self.tcx(), impl_did) {
1400 None => {debug!("(report candidate) No trait method found"); impl_did},
1401 Some(trait_did) => {debug!("(report candidate) Found trait ref"); trait_did}
1404 // If it is an instantiated default method, use the original
1405 // default method for error reporting.
1406 match provided_source(self.tcx(), impl_did) {
1411 self.report_static_candidate(idx, did)
1413 MethodParam(ref mp) => {
1414 self.report_param_candidate(idx, (*mp).trait_id)
1416 MethodObject(ref mo) => {
1417 self.report_trait_candidate(idx, mo.trait_id)
1422 fn report_static_candidate(&self, idx: uint, did: DefId) {
1423 let span = if did.krate == ast::LOCAL_CRATE {
1424 self.tcx().map.span(did.node)
1428 self.tcx().sess.span_note(
1430 format!("candidate #{} is `{}`",
1432 ty::item_path_str(self.tcx(), did)).as_slice());
1435 fn report_param_candidate(&self, idx: uint, did: DefId) {
1436 self.tcx().sess.span_note(
1438 format!("candidate #{} derives from the bound `{}`",
1440 ty::item_path_str(self.tcx(), did)).as_slice());
1443 fn report_trait_candidate(&self, idx: uint, did: DefId) {
1444 self.tcx().sess.span_note(
1446 format!("candidate #{} derives from the type of the receiver, \
1447 which is the trait `{}`",
1449 ty::item_path_str(self.tcx(), did)).as_slice());
1452 fn infcx(&'a self) -> &'a infer::InferCtxt<'a> {
1456 fn tcx(&self) -> &'a ty::ctxt {
1460 fn ty_to_str(&self, t: ty::t) -> String {
1461 self.fcx.infcx().ty_to_str(t)
1464 fn did_to_str(&self, did: DefId) -> String {
1465 ty::item_path_str(self.tcx(), did)
1468 fn bug(&self, s: &str) -> ! {
1469 self.tcx().sess.span_bug(self.span, s)
1473 impl Repr for Candidate {
1474 fn repr(&self, tcx: &ty::ctxt) -> String {
1475 format!("Candidate(rcvr_ty={}, rcvr_substs={}, method_ty={}, \
1477 self.rcvr_match_condition.repr(tcx),
1478 self.rcvr_substs.repr(tcx),
1479 self.method_ty.repr(tcx),
1484 impl Repr for RcvrMatchCondition {
1485 fn repr(&self, tcx: &ty::ctxt) -> String {
1487 RcvrMatchesIfObject(d) => {
1488 format!("RcvrMatchesIfObject({})", d.repr(tcx))
1490 RcvrMatchesIfSubtype(t) => {
1491 format!("RcvrMatchesIfSubtype({})", t.repr(tcx))