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