src/librustc/middle/typeck/check/method/mod.rs

   1 // Copyright 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.
   4 //
   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.
  10
  11 /*! Method lookup: the secret sauce of Rust. See `doc.rs`. */
  12
  13 use middle::subst;
  14 use middle::subst::{Subst};
  15 use middle::traits;
  16 use middle::ty::*;
  17 use middle::ty;
  18 use middle::typeck::astconv::AstConv;
  19 use middle::typeck::check::{FnCtxt};
  20 use middle::typeck::check::{impl_self_ty};
  21 use middle::typeck::check::vtable;
  22 use middle::typeck::check::vtable::select_new_fcx_obligations;
  23 use middle::typeck::infer;
  24 use middle::typeck::{MethodCallee};
  25 use middle::typeck::{MethodParam, MethodTypeParam};
  26 use util::ppaux::{Repr, UserString};
  27
  28 use std::rc::Rc;
  29 use syntax::ast::{DefId};
  30 use syntax::ast;
  31 use syntax::codemap::Span;
  32
  33 pub use self::MethodError::*;
  34 pub use self::CandidateSource::*;
  35
  36 mod confirm;
  37 mod doc;
  38 mod probe;
  39
  40 pub enum MethodError {
  41     // Did not find an applicable method, but we did find various
  42     // static methods that may apply.
  43     NoMatch(Vec<CandidateSource>),
  44
  45     // Multiple methods might apply.
  46     Ambiguity(Vec<CandidateSource>),
  47 }
  48
  49 // A pared down enum describing just the places from which a method
  50 // candidate can arise. Used for error reporting only.
  51 #[deriving(PartialOrd, Ord, PartialEq, Eq)]
  52 pub enum CandidateSource {
  53     ImplSource(ast::DefId),
  54     TraitSource(/* trait id */ ast::DefId),
  55 }
  56
  57 type MethodIndex = uint; // just for doc purposes
  58
  59 pub fn exists<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
  60                         span: Span,
  61                         method_name: ast::Name,
  62                         self_ty: Ty<'tcx>,
  63                         call_expr_id: ast::NodeId)
  64                         -> bool
  65 {
  66     /*!
  67      * Determines whether the type `self_ty` supports a method name `method_name` or not.
  68      */
  69
  70     match probe::probe(fcx, span, method_name, self_ty, call_expr_id) {
  71         Ok(_) => true,
  72         Err(NoMatch(_)) => false,
  73         Err(Ambiguity(_)) => true,
  74     }
  75 }
  76
  77 pub fn lookup<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
  78                         span: Span,
  79                         method_name: ast::Name,
  80                         self_ty: Ty<'tcx>,
  81                         supplied_method_types: Vec<Ty<'tcx>>,
  82                         call_expr: &ast::Expr,
  83                         self_expr: &ast::Expr)
  84                         -> Result<MethodCallee<'tcx>, MethodError>
  85 {
  86     /*!
  87      * Performs method lookup. If lookup is successful, it will return the callee
  88      * and store an appropriate adjustment for the self-expr. In some cases it may
  89      * report an error (e.g., invoking the `drop` method).
  90      *
  91      * # Arguments
  92      *
  93      * Given a method call like `foo.bar::<T1,...Tn>(...)`:
  94      *
  95      * - `fcx`:                   the surrounding `FnCtxt` (!)
  96      * - `span`:                  the span for the method call
  97      * - `method_name`:           the name of the method being called (`bar`)
  98      * - `self_ty`:               the (unadjusted) type of the self expression (`foo`)
  99      * - `supplied_method_types`: the explicit method type parameters, if any (`T1..Tn`)
 100      * - `self_expr`:             the self expression (`foo`)
 101      */
 102
 103     debug!("lookup(method_name={}, self_ty={}, call_expr={}, self_expr={})",
 104            method_name.repr(fcx.tcx()),
 105            self_ty.repr(fcx.tcx()),
 106            call_expr.repr(fcx.tcx()),
 107            self_expr.repr(fcx.tcx()));
 108
 109     let pick = try!(probe::probe(fcx, span, method_name, self_ty, call_expr.id));
 110     Ok(confirm::confirm(fcx, span, self_expr, call_expr, self_ty, pick, supplied_method_types))
 111 }
 112
 113 pub fn lookup_in_trait<'a, 'tcx>(fcx: &'a FnCtxt<'a, 'tcx>,
 114                                  span: Span,
 115                                  self_expr: Option<&'a ast::Expr>,
 116                                  m_name: ast::Name,
 117                                  trait_def_id: DefId,
 118                                  self_ty: Ty<'tcx>,
 119                                  opt_input_types: Option<Vec<Ty<'tcx>>>)
 120                                  -> Option<MethodCallee<'tcx>>
 121 {
 122     lookup_in_trait_adjusted(fcx, span, self_expr, m_name, trait_def_id,
 123                              ty::AutoDerefRef { autoderefs: 0, autoref: None },
 124                              self_ty, opt_input_types)
 125 }
 126
 127 pub fn lookup_in_trait_adjusted<'a, 'tcx>(fcx: &'a FnCtxt<'a, 'tcx>,
 128                                           span: Span,
 129                                           self_expr: Option<&'a ast::Expr>,
 130                                           m_name: ast::Name,
 131                                           trait_def_id: DefId,
 132                                           autoderefref: ty::AutoDerefRef<'tcx>,
 133                                           self_ty: Ty<'tcx>,
 134                                           opt_input_types: Option<Vec<Ty<'tcx>>>)
 135                                           -> Option<MethodCallee<'tcx>>
 136 {
 137     /*!
 138      * `lookup_in_trait_adjusted` is used for overloaded operators. It
 139      * does a very narrow slice of what the normal probe/confirm path
 140      * does. In particular, it doesn't really do any probing: it
 141      * simply constructs an obligation for a particular trait with the
 142      * given self-type and checks whether that trait is implemented.
 143      *
 144      * FIXME(#18741) -- It seems likely that we can consolidate some of this
 145      * code with the other method-lookup code. In particular,
 146      * autoderef on index is basically identical to autoderef with
 147      * normal probes, except that the test also looks for built-in
 148      * indexing. Also, the second half of this method is basically
 149      * the same as confirmation.
 150      */
 151
 152     debug!("lookup_in_trait_adjusted(self_ty={}, self_expr={}, m_name={}, trait_def_id={})",
 153            self_ty.repr(fcx.tcx()),
 154            self_expr.repr(fcx.tcx()),
 155            m_name.repr(fcx.tcx()),
 156            trait_def_id.repr(fcx.tcx()));
 157
 158     let trait_def = ty::lookup_trait_def(fcx.tcx(), trait_def_id);
 159
 160     let expected_number_of_input_types = trait_def.generics.types.len(subst::TypeSpace);
 161     let input_types = match opt_input_types {
 162         Some(input_types) => {
 163             assert_eq!(expected_number_of_input_types, input_types.len());
 164             input_types
 165         }
 166
 167         None => {
 168             fcx.inh.infcx.next_ty_vars(expected_number_of_input_types)
 169         }
 170     };
 171
 172     let number_assoc_types = trait_def.generics.types.len(subst::AssocSpace);
 173     let assoc_types = fcx.inh.infcx.next_ty_vars(number_assoc_types);
 174
 175     assert_eq!(trait_def.generics.types.len(subst::FnSpace), 0);
 176     assert!(trait_def.generics.regions.is_empty());
 177
 178     // Construct a trait-reference `self_ty : Trait<input_tys>`
 179     let substs = subst::Substs::new_trait(input_types, Vec::new(), assoc_types, self_ty);
 180     let trait_ref = Rc::new(ty::TraitRef::new(trait_def_id, substs));
 181
 182     // Construct an obligation
 183     let obligation = traits::Obligation::misc(span, trait_ref.clone());
 184
 185     // Now we want to know if this can be matched
 186     let mut selcx = traits::SelectionContext::new(fcx.infcx(),
 187                                                   &fcx.inh.param_env,
 188                                                   fcx);
 189     if !selcx.evaluate_obligation(&obligation) {
 190         debug!("--> Cannot match obligation");
 191         return None; // Cannot be matched, no such method resolution is possible.
 192     }
 193
 194     // Trait must have a method named `m_name` and it should not have
 195     // type parameters or early-bound regions.
 196     let tcx = fcx.tcx();
 197     let (method_num, method_ty) = trait_method(tcx, trait_def_id, m_name).unwrap();
 198     assert_eq!(method_ty.generics.types.len(subst::FnSpace), 0);
 199     assert_eq!(method_ty.generics.regions.len(subst::FnSpace), 0);
 200
 201     // Substitute the trait parameters into the method type and
 202     // instantiate late-bound regions to get the actual method type.
 203     //
 204     // Note that as the method comes from a trait, it can only have
 205     // late-bound regions from the fn itself, not the impl.
 206     let ref bare_fn_ty = method_ty.fty;
 207     let fn_sig = bare_fn_ty.sig.subst(tcx, &trait_ref.substs);
 208     let fn_sig = fcx.infcx().replace_late_bound_regions_with_fresh_var(span,
 209                                                                        infer::FnCall,
 210                                                                        &fn_sig).0;
 211     let transformed_self_ty = fn_sig.inputs[0];
 212     let fty = ty::mk_bare_fn(tcx, ty::BareFnTy {
 213         sig: fn_sig,
 214         fn_style: bare_fn_ty.fn_style,
 215         abi: bare_fn_ty.abi.clone(),
 216     });
 217
 218     debug!("matched method fty={} obligation={}",
 219            fty.repr(fcx.tcx()),
 220            obligation.repr(fcx.tcx()));
 221
 222     // Register obligations for the parameters.  This will include the
 223     // `Self` parameter, which in turn has a bound of the main trait,
 224     // so this also effectively registers `obligation` as well.  (We
 225     // used to register `obligation` explicitly, but that resulted in
 226     // double error messages being reported.)
 227     //
 228     // Note that as the method comes from a trait, it should not have
 229     // any late-bound regions appearing in its bounds.
 230     let method_bounds = method_ty.generics.to_bounds(fcx.tcx(), &trait_ref.substs);
 231     assert!(!method_bounds.has_escaping_regions());
 232     fcx.add_obligations_for_parameters(
 233         traits::ObligationCause::misc(span),
 234         &trait_ref.substs,
 235         &method_bounds);
 236
 237     // FIXME(#18653) -- Try to resolve obligations, giving us more
 238     // typing information, which can sometimes be needed to avoid
 239     // pathological region inference failures.
 240     vtable::select_new_fcx_obligations(fcx);
 241
 242     // Insert any adjustments needed (always an autoref of some mutability).
 243     match self_expr {
 244         None => { }
 245
 246         Some(self_expr) => {
 247             debug!("inserting adjustment if needed (self-id = {}, \
 248                    base adjustment = {}, explicit self = {})",
 249                    self_expr.id, autoderefref, method_ty.explicit_self);
 250
 251             match method_ty.explicit_self {
 252                 ty::ByValueExplicitSelfCategory => {
 253                     // Trait method is fn(self), no transformation needed.
 254                     if !autoderefref.is_identity() {
 255                         fcx.write_adjustment(
 256                             self_expr.id,
 257                             span,
 258                             ty::AdjustDerefRef(autoderefref));
 259                     }
 260                 }
 261
 262                 ty::ByReferenceExplicitSelfCategory(..) => {
 263                     // Trait method is fn(&self) or fn(&mut self), need an
 264                     // autoref. Pull the region etc out of the type of first argument.
 265                     match transformed_self_ty.sty {
 266                         ty::ty_rptr(region, ty::mt { mutbl, ty: _ }) => {
 267                             let ty::AutoDerefRef { autoderefs, autoref } = autoderefref;
 268                             let autoref = autoref.map(|r| box r);
 269                             fcx.write_adjustment(
 270                                 self_expr.id,
 271                                 span,
 272                                 ty::AdjustDerefRef(ty::AutoDerefRef {
 273                                     autoderefs: autoderefs,
 274                                     autoref: Some(ty::AutoPtr(region, mutbl, autoref))
 275                                 }));
 276                         }
 277
 278                         _ => {
 279                             fcx.tcx().sess.span_bug(
 280                                 span,
 281                                 format!(
 282                                     "trait method is &self but first arg is: {}",
 283                                     transformed_self_ty.repr(fcx.tcx())).as_slice());
 284                         }
 285                     }
 286                 }
 287
 288                 _ => {
 289                     fcx.tcx().sess.span_bug(
 290                         span,
 291                         format!(
 292                             "unexpected explicit self type in operator method: {}",
 293                             method_ty.explicit_self).as_slice());
 294                 }
 295             }
 296         }
 297     }
 298
 299     let callee = MethodCallee {
 300         origin: MethodTypeParam(MethodParam{trait_ref: trait_ref.clone(),
 301                                             method_num: method_num}),
 302         ty: fty,
 303         substs: trait_ref.substs.clone()
 304     };
 305
 306     debug!("callee = {}", callee.repr(fcx.tcx()));
 307
 308     Some(callee)
 309 }
 310
 311 pub fn report_error<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 312                               span: Span,
 313                               rcvr_ty: Ty<'tcx>,
 314                               method_name: ast::Name,
 315                               error: MethodError)
 316 {
 317     match error {
 318         NoMatch(static_sources) => {
 319             let cx = fcx.tcx();
 320             let method_ustring = method_name.user_string(cx);
 321
 322             // True if the type is a struct and contains a field with
 323             // the same name as the not-found method
 324             let is_field = match rcvr_ty.sty {
 325                 ty_struct(did, _) =>
 326                     ty::lookup_struct_fields(cx, did)
 327                         .iter()
 328                         .any(|f| f.name.user_string(cx) == method_ustring),
 329                 _ => false
 330             };
 331
 332             fcx.type_error_message(
 333                 span,
 334                 |actual| {
 335                     format!("type `{}` does not implement any \
 336                              method in scope named `{}`",
 337                             actual,
 338                             method_ustring)
 339                 },
 340                 rcvr_ty,
 341                 None);
 342
 343             // If the method has the name of a field, give a help note
 344             if is_field {
 345                 cx.sess.span_note(span,
 346                     format!("use `(s.{0})(...)` if you meant to call the \
 347                             function stored in the `{0}` field", method_ustring).as_slice());
 348             }
 349
 350             if static_sources.len() > 0 {
 351                 fcx.tcx().sess.fileline_note(
 352                     span,
 353                     "found defined static methods, maybe a `self` is missing?");
 354
 355                 report_candidates(fcx, span, method_name, static_sources);
 356             }
 357         }
 358
 359         Ambiguity(sources) => {
 360             span_err!(fcx.sess(), span, E0034,
 361                       "multiple applicable methods in scope");
 362
 363             report_candidates(fcx, span, method_name, sources);
 364         }
 365     }
 366
 367     fn report_candidates(fcx: &FnCtxt,
 368                          span: Span,
 369                          method_name: ast::Name,
 370                          mut sources: Vec<CandidateSource>) {
 371         sources.sort();
 372         sources.dedup();
 373
 374         for (idx, source) in sources.iter().enumerate() {
 375             match *source {
 376                 ImplSource(impl_did) => {
 377                     // Provide the best span we can. Use the method, if local to crate, else
 378                     // the impl, if local to crate (method may be defaulted), else the call site.
 379                     let method = impl_method(fcx.tcx(), impl_did, method_name).unwrap();
 380                     let impl_span = fcx.tcx().map.def_id_span(impl_did, span);
 381                     let method_span = fcx.tcx().map.def_id_span(method.def_id, impl_span);
 382
 383                     let impl_ty = impl_self_ty(fcx, span, impl_did).ty;
 384
 385                     let insertion = match impl_trait_ref(fcx.tcx(), impl_did) {
 386                         None => format!(""),
 387                         Some(trait_ref) => format!(" of the trait `{}`",
 388                                                    ty::item_path_str(fcx.tcx(),
 389                                                                      trait_ref.def_id)),
 390                     };
 391
 392                     span_note!(fcx.sess(), method_span,
 393                                "candidate #{} is defined in an impl{} for the type `{}`",
 394                                idx + 1u,
 395                                insertion,
 396                                impl_ty.user_string(fcx.tcx()));
 397                 }
 398                 TraitSource(trait_did) => {
 399                     let (_, method) = trait_method(fcx.tcx(), trait_did, method_name).unwrap();
 400                     let method_span = fcx.tcx().map.def_id_span(method.def_id, span);
 401                     span_note!(fcx.sess(), method_span,
 402                                "candidate #{} is defined in the trait `{}`",
 403                                idx + 1u,
 404                                ty::item_path_str(fcx.tcx(), trait_did));
 405                 }
 406             }
 407         }
 408     }
 409 }
 410
 411 fn trait_method<'tcx>(tcx: &ty::ctxt<'tcx>,
 412                       trait_def_id: ast::DefId,
 413                       method_name: ast::Name)
 414                       -> Option<(uint, Rc<ty::Method<'tcx>>)>
 415 {
 416     /*!
 417      * Find method with name `method_name` defined in `trait_def_id` and return it,
 418      * along with its index (or `None`, if no such method).
 419      */
 420
 421     let trait_items = ty::trait_items(tcx, trait_def_id);
 422     trait_items
 423         .iter()
 424         .enumerate()
 425         .find(|&(_, ref item)| item.name() == method_name)
 426         .and_then(|(idx, item)| item.as_opt_method().map(|m| (idx, m)))
 427 }
 428
 429 fn impl_method<'tcx>(tcx: &ty::ctxt<'tcx>,
 430                      impl_def_id: ast::DefId,
 431                      method_name: ast::Name)
 432                      -> Option<Rc<ty::Method<'tcx>>>
 433 {
 434     let impl_items = tcx.impl_items.borrow();
 435     let impl_items = impl_items.get(&impl_def_id).unwrap();
 436     impl_items
 437         .iter()
 438         .map(|&did| ty::impl_or_trait_item(tcx, did.def_id()))
 439         .find(|m| m.name() == method_name)
 440         .and_then(|item| item.as_opt_method())
 441 }
 442