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, AsPredicate, 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 type ItemIndex = usize; // just for doc purposes
  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 ast::Expr,
 116                         self_expr: &'tcx ast::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<&ast::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<&ast::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 = ty::lookup_trait_def(fcx.tcx(), trait_def_id);
 171
 172     let expected_number_of_input_types = trait_def.generics.types.len(subst::TypeSpace);
 173     let input_types = match opt_input_types {
 174         Some(input_types) => {
 175             assert_eq!(expected_number_of_input_types, input_types.len());
 176             input_types
 177         }
 178
 179         None => {
 180             fcx.inh.infcx.next_ty_vars(expected_number_of_input_types)
 181         }
 182     };
 183
 184     assert_eq!(trait_def.generics.types.len(subst::FnSpace), 0);
 185     assert!(trait_def.generics.regions.is_empty());
 186
 187     // Construct a trait-reference `self_ty : Trait<input_tys>`
 188     let substs = subst::Substs::new_trait(input_types, Vec::new(), self_ty);
 189     let trait_ref = ty::TraitRef::new(trait_def_id, fcx.tcx().mk_substs(substs));
 190
 191     // Construct an obligation
 192     let poly_trait_ref = trait_ref.to_poly_trait_ref();
 193     let obligation = traits::Obligation::misc(span,
 194                                               fcx.body_id,
 195                                               poly_trait_ref.as_predicate());
 196
 197     // Now we want to know if this can be matched
 198     let mut selcx = traits::SelectionContext::new(fcx.infcx(), fcx);
 199     if !selcx.evaluate_obligation(&obligation) {
 200         debug!("--> Cannot match obligation");
 201         return None; // Cannot be matched, no such method resolution is possible.
 202     }
 203
 204     // Trait must have a method named `m_name` and it should not have
 205     // type parameters or early-bound regions.
 206     let tcx = fcx.tcx();
 207     let (method_num, method_ty) = trait_item(tcx, trait_def_id, m_name)
 208             .and_then(|(idx, item)| item.as_opt_method().map(|m| (idx, m)))
 209             .unwrap();
 210     assert_eq!(method_ty.generics.types.len(subst::FnSpace), 0);
 211     assert_eq!(method_ty.generics.regions.len(subst::FnSpace), 0);
 212
 213     debug!("lookup_in_trait_adjusted: method_num={} method_ty={:?}",
 214            method_num, method_ty);
 215
 216     // Instantiate late-bound regions and substitute the trait
 217     // parameters into the method type to get the actual method type.
 218     //
 219     // NB: Instantiate late-bound regions first so that
 220     // `instantiate_type_scheme` can normalize associated types that
 221     // may reference those regions.
 222     let fn_sig = fcx.infcx().replace_late_bound_regions_with_fresh_var(span,
 223                                                                        infer::FnCall,
 224                                                                        &method_ty.fty.sig).0;
 225     let fn_sig = fcx.instantiate_type_scheme(span, trait_ref.substs, &fn_sig);
 226     let transformed_self_ty = fn_sig.inputs[0];
 227     let fty = ty::mk_bare_fn(tcx, None, tcx.mk_bare_fn(ty::BareFnTy {
 228         sig: ty::Binder(fn_sig),
 229         unsafety: method_ty.fty.unsafety,
 230         abi: method_ty.fty.abi.clone(),
 231     }));
 232
 233     debug!("lookup_in_trait_adjusted: matched method fty={:?} obligation={:?}",
 234            fty,
 235            obligation);
 236
 237     // Register obligations for the parameters.  This will include the
 238     // `Self` parameter, which in turn has a bound of the main trait,
 239     // so this also effectively registers `obligation` as well.  (We
 240     // used to register `obligation` explicitly, but that resulted in
 241     // double error messages being reported.)
 242     //
 243     // Note that as the method comes from a trait, it should not have
 244     // any late-bound regions appearing in its bounds.
 245     let method_bounds = fcx.instantiate_bounds(span, trait_ref.substs, &method_ty.predicates);
 246     assert!(!method_bounds.has_escaping_regions());
 247     fcx.add_obligations_for_parameters(
 248         traits::ObligationCause::misc(span, fcx.body_id),
 249         &method_bounds);
 250
 251     // FIXME(#18653) -- Try to resolve obligations, giving us more
 252     // typing information, which can sometimes be needed to avoid
 253     // pathological region inference failures.
 254     fcx.select_new_obligations();
 255
 256     // Insert any adjustments needed (always an autoref of some mutability).
 257     match self_expr {
 258         None => { }
 259
 260         Some(self_expr) => {
 261             debug!("lookup_in_trait_adjusted: inserting adjustment if needed \
 262                    (self-id={}, autoderefs={}, unsize={}, explicit_self={:?})",
 263                    self_expr.id, autoderefs, unsize,
 264                    method_ty.explicit_self);
 265
 266             match method_ty.explicit_self {
 267                 ty::ByValueExplicitSelfCategory => {
 268                     // Trait method is fn(self), no transformation needed.
 269                     assert!(!unsize);
 270                     fcx.write_autoderef_adjustment(self_expr.id, autoderefs);
 271                 }
 272
 273                 ty::ByReferenceExplicitSelfCategory(..) => {
 274                     // Trait method is fn(&self) or fn(&mut self), need an
 275                     // autoref. Pull the region etc out of the type of first argument.
 276                     match transformed_self_ty.sty {
 277                         ty::TyRef(region, ty::mt { mutbl, ty: _ }) => {
 278                             fcx.write_adjustment(self_expr.id,
 279                                 ty::AdjustDerefRef(ty::AutoDerefRef {
 280                                     autoderefs: autoderefs,
 281                                     autoref: Some(ty::AutoPtr(region, mutbl)),
 282                                     unsize: if unsize {
 283                                         Some(transformed_self_ty)
 284                                     } else {
 285                                         None
 286                                     }
 287                                 }));
 288                         }
 289
 290                         _ => {
 291                             fcx.tcx().sess.span_bug(
 292                                 span,
 293                                 &format!(
 294                                     "trait method is &self but first arg is: {}",
 295                                     transformed_self_ty));
 296                         }
 297                     }
 298                 }
 299
 300                 _ => {
 301                     fcx.tcx().sess.span_bug(
 302                         span,
 303                         &format!(
 304                             "unexpected explicit self type in operator method: {:?}",
 305                             method_ty.explicit_self));
 306                 }
 307             }
 308         }
 309     }
 310
 311     let callee = ty::MethodCallee {
 312         origin: ty::MethodTypeParam(ty::MethodParam{trait_ref: trait_ref.clone(),
 313                                                     method_num: method_num,
 314                                                     impl_def_id: None}),
 315         ty: fty,
 316         substs: trait_ref.substs.clone()
 317     };
 318
 319     debug!("callee = {:?}", callee);
 320
 321     Some(callee)
 322 }
 323
 324 pub fn resolve_ufcs<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 325                               span: Span,
 326                               method_name: ast::Name,
 327                               self_ty: ty::Ty<'tcx>,
 328                               expr_id: ast::NodeId)
 329                               -> Result<(def::Def, LastPrivate), MethodError<'tcx>>
 330 {
 331     let mode = probe::Mode::Path;
 332     let pick = try!(probe::probe(fcx, span, mode, method_name, self_ty, expr_id));
 333     let def_id = pick.item.def_id();
 334     let mut lp = LastMod(AllPublic);
 335     let provenance = match pick.kind {
 336         probe::InherentImplPick(impl_def_id) => {
 337             if pick.item.vis() != ast::Public {
 338                 lp = LastMod(DependsOn(def_id));
 339             }
 340             def::FromImpl(impl_def_id)
 341         }
 342         _ => def::FromTrait(pick.item.container().id())
 343     };
 344     let def_result = match pick.item {
 345         ty::ImplOrTraitItem::MethodTraitItem(..) => def::DefMethod(def_id, provenance),
 346         ty::ImplOrTraitItem::ConstTraitItem(..) => def::DefAssociatedConst(def_id, provenance),
 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` and return it, along with its
 356 /// index (or `None`, if no such item).
 357 fn trait_item<'tcx>(tcx: &ty::ctxt<'tcx>,
 358                     trait_def_id: ast::DefId,
 359                     item_name: ast::Name)
 360                     -> Option<(usize, ty::ImplOrTraitItem<'tcx>)>
 361 {
 362     let trait_items = ty::trait_items(tcx, trait_def_id);
 363     trait_items
 364         .iter()
 365         .enumerate()
 366         .find(|&(_, ref item)| item.name() == item_name)
 367         .map(|(num, item)| (num, (*item).clone()))
 368 }
 369
 370 fn impl_item<'tcx>(tcx: &ty::ctxt<'tcx>,
 371                    impl_def_id: ast::DefId,
 372                    item_name: ast::Name)
 373                    -> Option<ty::ImplOrTraitItem<'tcx>>
 374 {
 375     let impl_items = tcx.impl_items.borrow();
 376     let impl_items = impl_items.get(&impl_def_id).unwrap();
 377     impl_items
 378         .iter()
 379         .map(|&did| ty::impl_or_trait_item(tcx, did.def_id()))
 380         .find(|m| m.name() == item_name)
 381 }