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