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