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 `README.md`.
  12
  13 use astconv::AstConv;
  14 use check::FnCtxt;
  15 use middle::def;
  16 use middle::def_id::DefId;
  17 use middle::privacy::{AllPublic, DependsOn, LastPrivate, LastMod};
  18 use middle::subst;
  19 use middle::traits;
  20 use middle::ty::{self, ToPredicate, ToPolyTraitRef, TraitRef};
  21 use middle::infer;
  22
  23 use syntax::ast;
  24 use syntax::codemap::Span;
  25
  26 use rustc_front::hir;
  27
  28 pub use self::MethodError::*;
  29 pub use self::CandidateSource::*;
  30
  31 pub use self::suggest::{report_error, AllTraitsVec};
  32
  33 mod confirm;
  34 mod probe;
  35 mod suggest;
  36
  37 pub enum MethodError<'tcx> {
  38     // Did not find an applicable method, but we did find various near-misses that may work.
  39     NoMatch(NoMatchData<'tcx>),
  40
  41     // Multiple methods might apply.
  42     Ambiguity(Vec<CandidateSource>),
  43
  44     // Using a `Fn`/`FnMut`/etc method on a raw closure type before we have inferred its kind.
  45     ClosureAmbiguity(/* DefId of fn trait */ DefId),
  46 }
  47
  48 // Contains a list of static methods that may apply, a list of unsatisfied trait predicates which
  49 // could lead to matches if satisfied, and a list of not-in-scope traits which may work.
  50 pub struct NoMatchData<'tcx> {
  51     pub static_candidates: Vec<CandidateSource>,
  52     pub unsatisfied_predicates: Vec<TraitRef<'tcx>>,
  53     pub out_of_scope_traits: Vec<DefId>,
  54     pub mode: probe::Mode
  55 }
  56
  57 impl<'tcx> NoMatchData<'tcx> {
  58     pub fn new(static_candidates: Vec<CandidateSource>,
  59                unsatisfied_predicates: Vec<TraitRef<'tcx>>,
  60                out_of_scope_traits: Vec<DefId>,
  61                mode: probe::Mode) -> Self {
  62         NoMatchData {
  63             static_candidates: static_candidates,
  64             unsatisfied_predicates: unsatisfied_predicates,
  65             out_of_scope_traits: out_of_scope_traits,
  66             mode: mode
  67         }
  68     }
  69 }
  70
  71 // A pared down enum describing just the places from which a method
  72 // candidate can arise. Used for error reporting only.
  73 #[derive(Copy, Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
  74 pub enum CandidateSource {
  75     ImplSource(DefId),
  76     TraitSource(/* trait id */ DefId),
  77 }
  78
  79 /// Determines whether the type `self_ty` supports a method name `method_name` or not.
  80 pub fn exists<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
  81                         span: Span,
  82                         method_name: ast::Name,
  83                         self_ty: ty::Ty<'tcx>,
  84                         call_expr_id: ast::NodeId)
  85                         -> bool
  86 {
  87     let mode = probe::Mode::MethodCall;
  88     match probe::probe(fcx, span, mode, method_name, self_ty, call_expr_id) {
  89         Ok(..) => true,
  90         Err(NoMatch(..)) => false,
  91         Err(Ambiguity(..)) => true,
  92         Err(ClosureAmbiguity(..)) => true,
  93     }
  94 }
  95
  96 /// Performs method lookup. If lookup is successful, it will return the callee and store an
  97 /// appropriate adjustment for the self-expr. In some cases it may report an error (e.g., invoking
  98 /// the `drop` method).
  99 ///
 100 /// # Arguments
 101 ///
 102 /// Given a method call like `foo.bar::<T1,...Tn>(...)`:
 103 ///
 104 /// * `fcx`:                   the surrounding `FnCtxt` (!)
 105 /// * `span`:                  the span for the method call
 106 /// * `method_name`:           the name of the method being called (`bar`)
 107 /// * `self_ty`:               the (unadjusted) type of the self expression (`foo`)
 108 /// * `supplied_method_types`: the explicit method type parameters, if any (`T1..Tn`)
 109 /// * `self_expr`:             the self expression (`foo`)
 110 pub fn lookup<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 111                         span: Span,
 112                         method_name: ast::Name,
 113                         self_ty: ty::Ty<'tcx>,
 114                         supplied_method_types: Vec<ty::Ty<'tcx>>,
 115                         call_expr: &'tcx hir::Expr,
 116                         self_expr: &'tcx hir::Expr)
 117                         -> Result<ty::MethodCallee<'tcx>, MethodError<'tcx>>
 118 {
 119     debug!("lookup(method_name={}, self_ty={:?}, call_expr={:?}, self_expr={:?})",
 120            method_name,
 121            self_ty,
 122            call_expr,
 123            self_expr);
 124
 125     let mode = probe::Mode::MethodCall;
 126     let self_ty = fcx.infcx().resolve_type_vars_if_possible(&self_ty);
 127     let pick = try!(probe::probe(fcx, span, mode, method_name, self_ty, call_expr.id));
 128     Ok(confirm::confirm(fcx, span, self_expr, call_expr, self_ty, pick, supplied_method_types))
 129 }
 130
 131 pub fn lookup_in_trait<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 132                                  span: Span,
 133                                  self_expr: Option<&hir::Expr>,
 134                                  m_name: ast::Name,
 135                                  trait_def_id: DefId,
 136                                  self_ty: ty::Ty<'tcx>,
 137                                  opt_input_types: Option<Vec<ty::Ty<'tcx>>>)
 138                                  -> Option<ty::MethodCallee<'tcx>>
 139 {
 140     lookup_in_trait_adjusted(fcx, span, self_expr, m_name, trait_def_id,
 141                              0, false, self_ty, opt_input_types)
 142 }
 143
 144 /// `lookup_in_trait_adjusted` is used for overloaded operators. It does a very narrow slice of
 145 /// what the normal probe/confirm path does. In particular, it doesn't really do any probing: it
 146 /// simply constructs an obligation for a particular trait with the given self-type and checks
 147 /// whether that trait is implemented.
 148 ///
 149 /// FIXME(#18741) -- It seems likely that we can consolidate some of this code with the other
 150 /// method-lookup code. In particular, autoderef on index is basically identical to autoderef with
 151 /// normal probes, except that the test also looks for built-in indexing. Also, the second half of
 152 /// this method is basically the same as confirmation.
 153 pub fn lookup_in_trait_adjusted<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 154                                           span: Span,
 155                                           self_expr: Option<&hir::Expr>,
 156                                           m_name: ast::Name,
 157                                           trait_def_id: DefId,
 158                                           autoderefs: usize,
 159                                           unsize: bool,
 160                                           self_ty: ty::Ty<'tcx>,
 161                                           opt_input_types: Option<Vec<ty::Ty<'tcx>>>)
 162                                           -> Option<ty::MethodCallee<'tcx>>
 163 {
 164     debug!("lookup_in_trait_adjusted(self_ty={:?}, self_expr={:?}, m_name={}, trait_def_id={:?})",
 165            self_ty,
 166            self_expr,
 167            m_name,
 168            trait_def_id);
 169
 170     let trait_def = fcx.tcx().lookup_trait_def(trait_def_id);
 171
 172     let type_parameter_defs = trait_def.generics.types.get_slice(subst::TypeSpace);
 173     let expected_number_of_input_types = type_parameter_defs.len();
 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 mut substs = subst::Substs::new_trait(Vec::new(), Vec::new(), self_ty);
 180
 181     match opt_input_types {
 182         Some(input_types) => {
 183             assert_eq!(expected_number_of_input_types, input_types.len());
 184             substs.types.replace(subst::ParamSpace::TypeSpace, input_types);
 185         }
 186
 187         None => {
 188             fcx.inh.infcx.type_vars_for_defs(
 189                 span,
 190                 subst::ParamSpace::TypeSpace,
 191                 &mut substs,
 192                 type_parameter_defs);
 193         }
 194     }
 195
 196     let trait_ref = ty::TraitRef::new(trait_def_id, fcx.tcx().mk_substs(substs));
 197
 198     // Construct an obligation
 199     let poly_trait_ref = trait_ref.to_poly_trait_ref();
 200     let obligation = traits::Obligation::misc(span,
 201                                               fcx.body_id,
 202                                               poly_trait_ref.to_predicate());
 203
 204     // Now we want to know if this can be matched
 205     let mut selcx = traits::SelectionContext::new(fcx.infcx());
 206     if !selcx.evaluate_obligation(&obligation) {
 207         debug!("--> Cannot match obligation");
 208         return None; // Cannot be matched, no such method resolution is possible.
 209     }
 210
 211     // Trait must have a method named `m_name` and it should not have
 212     // type parameters or early-bound regions.
 213     let tcx = fcx.tcx();
 214     let method_item = trait_item(tcx, trait_def_id, m_name).unwrap();
 215     let method_ty = method_item.as_opt_method().unwrap();
 216     assert_eq!(method_ty.generics.types.len(subst::FnSpace), 0);
 217     assert_eq!(method_ty.generics.regions.len(subst::FnSpace), 0);
 218
 219     debug!("lookup_in_trait_adjusted: method_item={:?} method_ty={:?}",
 220            method_item, method_ty);
 221
 222     // Instantiate late-bound regions and substitute the trait
 223     // parameters into the method type to get the actual method type.
 224     //
 225     // NB: Instantiate late-bound regions first so that
 226     // `instantiate_type_scheme` can normalize associated types that
 227     // may reference those regions.
 228     let fn_sig = fcx.infcx().replace_late_bound_regions_with_fresh_var(span,
 229                                                                        infer::FnCall,
 230                                                                        &method_ty.fty.sig).0;
 231     let fn_sig = fcx.instantiate_type_scheme(span, trait_ref.substs, &fn_sig);
 232     let transformed_self_ty = fn_sig.inputs[0];
 233     let fty = tcx.mk_fn(None, tcx.mk_bare_fn(ty::BareFnTy {
 234         sig: ty::Binder(fn_sig),
 235         unsafety: method_ty.fty.unsafety,
 236         abi: method_ty.fty.abi.clone(),
 237     }));
 238
 239     debug!("lookup_in_trait_adjusted: matched method fty={:?} obligation={:?}",
 240            fty,
 241            obligation);
 242
 243     // Register obligations for the parameters.  This will include the
 244     // `Self` parameter, which in turn has a bound of the main trait,
 245     // so this also effectively registers `obligation` as well.  (We
 246     // used to register `obligation` explicitly, but that resulted in
 247     // double error messages being reported.)
 248     //
 249     // Note that as the method comes from a trait, it should not have
 250     // any late-bound regions appearing in its bounds.
 251     let method_bounds = fcx.instantiate_bounds(span, trait_ref.substs, &method_ty.predicates);
 252     assert!(!method_bounds.has_escaping_regions());
 253     fcx.add_obligations_for_parameters(
 254         traits::ObligationCause::misc(span, fcx.body_id),
 255         &method_bounds);
 256
 257     // FIXME(#18653) -- Try to resolve obligations, giving us more
 258     // typing information, which can sometimes be needed to avoid
 259     // pathological region inference failures.
 260     fcx.select_new_obligations();
 261
 262     // Insert any adjustments needed (always an autoref of some mutability).
 263     match self_expr {
 264         None => { }
 265
 266         Some(self_expr) => {
 267             debug!("lookup_in_trait_adjusted: inserting adjustment if needed \
 268                    (self-id={}, autoderefs={}, unsize={}, explicit_self={:?})",
 269                    self_expr.id, autoderefs, unsize,
 270                    method_ty.explicit_self);
 271
 272             match method_ty.explicit_self {
 273                 ty::ByValueExplicitSelfCategory => {
 274                     // Trait method is fn(self), no transformation needed.
 275                     assert!(!unsize);
 276                     fcx.write_autoderef_adjustment(self_expr.id, autoderefs);
 277                 }
 278
 279                 ty::ByReferenceExplicitSelfCategory(..) => {
 280                     // Trait method is fn(&self) or fn(&mut self), need an
 281                     // autoref. Pull the region etc out of the type of first argument.
 282                     match transformed_self_ty.sty {
 283                         ty::TyRef(region, ty::TypeAndMut { mutbl, ty: _ }) => {
 284                             fcx.write_adjustment(self_expr.id,
 285                                 ty::AdjustDerefRef(ty::AutoDerefRef {
 286                                     autoderefs: autoderefs,
 287                                     autoref: Some(ty::AutoPtr(region, mutbl)),
 288                                     unsize: if unsize {
 289                                         Some(transformed_self_ty)
 290                                     } else {
 291                                         None
 292                                     }
 293                                 }));
 294                         }
 295
 296                         _ => {
 297                             fcx.tcx().sess.span_bug(
 298                                 span,
 299                                 &format!(
 300                                     "trait method is &self but first arg is: {}",
 301                                     transformed_self_ty));
 302                         }
 303                     }
 304                 }
 305
 306                 _ => {
 307                     fcx.tcx().sess.span_bug(
 308                         span,
 309                         &format!(
 310                             "unexpected explicit self type in operator method: {:?}",
 311                             method_ty.explicit_self));
 312                 }
 313             }
 314         }
 315     }
 316
 317     let callee = ty::MethodCallee {
 318         def_id: method_item.def_id(),
 319         ty: fty,
 320         substs: trait_ref.substs
 321     };
 322
 323     debug!("callee = {:?}", callee);
 324
 325     Some(callee)
 326 }
 327
 328 pub fn resolve_ufcs<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 329                               span: Span,
 330                               method_name: ast::Name,
 331                               self_ty: ty::Ty<'tcx>,
 332                               expr_id: ast::NodeId)
 333                               -> Result<(def::Def, LastPrivate), MethodError<'tcx>>
 334 {
 335     let mode = probe::Mode::Path;
 336     let pick = try!(probe::probe(fcx, span, mode, method_name, self_ty, expr_id));
 337     let def_id = pick.item.def_id();
 338     let mut lp = LastMod(AllPublic);
 339     if let probe::InherentImplPick = pick.kind {
 340         if pick.item.vis() != hir::Public {
 341             lp = LastMod(DependsOn(def_id));
 342         }
 343     }
 344     let def_result = match pick.item {
 345         ty::ImplOrTraitItem::MethodTraitItem(..) => def::DefMethod(def_id),
 346         ty::ImplOrTraitItem::ConstTraitItem(..) => def::DefAssociatedConst(def_id),
 347         ty::ImplOrTraitItem::TypeTraitItem(..) => {
 348             fcx.tcx().sess.span_bug(span, "resolve_ufcs: probe picked associated type");
 349         }
 350     };
 351     Ok((def_result, lp))
 352 }
 353
 354
 355 /// Find item with name `item_name` defined in `trait_def_id`
 356 /// and return it, or `None`, if no such item.
 357 fn trait_item<'tcx>(tcx: &ty::ctxt<'tcx>,
 358                     trait_def_id: DefId,
 359                     item_name: ast::Name)
 360                     -> Option<ty::ImplOrTraitItem<'tcx>>
 361 {
 362     let trait_items = tcx.trait_items(trait_def_id);
 363     trait_items.iter()
 364                .find(|item| item.name() == item_name)
 365                .cloned()
 366 }
 367
 368 fn impl_item<'tcx>(tcx: &ty::ctxt<'tcx>,
 369                    impl_def_id: DefId,
 370                    item_name: ast::Name)
 371                    -> Option<ty::ImplOrTraitItem<'tcx>>
 372 {
 373     let impl_items = tcx.impl_items.borrow();
 374     let impl_items = impl_items.get(&impl_def_id).unwrap();
 375     impl_items
 376         .iter()
 377         .map(|&did| tcx.impl_or_trait_item(did.def_id()))
 378         .find(|m| m.name() == item_name)
 379 }