src/librustc/middle/typeck/check/vtable.rs

   1 // Copyright 2012-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
  12 use middle::ty;
  13 use middle::ty::{AutoAddEnv, AutoDerefRef, AutoObject, param_ty};
  14 use middle::ty_fold::TypeFolder;
  15 use middle::typeck::astconv::AstConv;
  16 use middle::typeck::check::{FnCtxt, impl_self_ty};
  17 use middle::typeck::check::{structurally_resolved_type};
  18 use middle::typeck::infer::fixup_err_to_str;
  19 use middle::typeck::infer::{resolve_and_force_all_but_regions, resolve_type};
  20 use middle::typeck::infer;
  21 use middle::typeck::{vtable_origin, vtable_res, vtable_param_res};
  22 use middle::typeck::{vtable_static, vtable_param, impl_res};
  23 use middle::typeck::{param_numbered, param_self, param_index};
  24 use middle::typeck::MethodCall;
  25 use middle::subst::Subst;
  26 use util::common::indenter;
  27 use util::ppaux;
  28 use util::ppaux::Repr;
  29
  30 use std::rc::Rc;
  31 use collections::HashSet;
  32 use syntax::ast;
  33 use syntax::ast_util;
  34 use syntax::codemap::Span;
  35 use syntax::print::pprust::expr_to_str;
  36 use syntax::visit;
  37 use syntax::visit::Visitor;
  38
  39 // vtable resolution looks for places where trait bounds are
  40 // substituted in and figures out which vtable is used. There is some
  41 // extra complication thrown in to support early "opportunistic"
  42 // vtable resolution. This is a hacky mechanism that is invoked while
  43 // typechecking function calls (after typechecking non-closure
  44 // arguments and before typechecking closure arguments) in the hope of
  45 // solving for the trait parameters from the impl. (For example,
  46 // determining that if a parameter bounded by BaseIter<A> is
  47 // instantiated with Option<int>, that A = int.)
  48 //
  49 // In early resolution mode, no vtables are recorded, and a number of
  50 // errors are ignored. Early resolution only works if a type is
  51 // *fully* resolved. (We could be less restrictive than that, but it
  52 // would require much more care, and this seems to work decently in
  53 // practice.)
  54 //
  55 // While resolution on a single type requires the type to be fully
  56 // resolved, when resolving a substitution against a list of bounds,
  57 // we do not require all of the types to be resolved in advance.
  58 // Furthermore, we process substitutions in reverse order, which
  59 // allows resolution on later parameters to give information on
  60 // earlier params referenced by the typeclass bounds.
  61 // It may be better to do something more clever, like processing fully
  62 // resolved types first.
  63
  64 /// A vtable context includes an inference context, a crate context, and a
  65 /// callback function to call in case of type error.
  66 pub struct VtableContext<'a> {
  67     pub infcx: &'a infer::InferCtxt<'a>,
  68     pub param_env: &'a ty::ParameterEnvironment,
  69 }
  70
  71 impl<'a> VtableContext<'a> {
  72     pub fn tcx(&self) -> &'a ty::ctxt { self.infcx.tcx }
  73 }
  74
  75 fn has_trait_bounds(type_param_defs: &[ty::TypeParameterDef]) -> bool {
  76     type_param_defs.iter().any(
  77         |type_param_def| !type_param_def.bounds.trait_bounds.is_empty())
  78 }
  79
  80 fn lookup_vtables(vcx: &VtableContext,
  81                   span: Span,
  82                   type_param_defs: &[ty::TypeParameterDef],
  83                   substs: &ty::substs,
  84                   is_early: bool) -> vtable_res {
  85     debug!("lookup_vtables(span={:?}, \
  86             type_param_defs={}, \
  87             substs={}",
  88            span,
  89            type_param_defs.repr(vcx.tcx()),
  90            substs.repr(vcx.tcx()));
  91
  92     // We do this backwards for reasons discussed above.
  93     assert_eq!(substs.tps.len(), type_param_defs.len());
  94     let mut result: Vec<vtable_param_res> =
  95         substs.tps.iter()
  96         .rev()
  97         .zip(type_param_defs.iter().rev())
  98         .map(|(ty, def)|
  99             lookup_vtables_for_param(vcx, span, Some(substs),
 100                                      &*def.bounds, *ty, is_early))
 101         .collect();
 102     result.reverse();
 103
 104     assert_eq!(substs.tps.len(), result.len());
 105     debug!("lookup_vtables result(\
 106             span={:?}, \
 107             type_param_defs={}, \
 108             substs={}, \
 109             result={})",
 110            span,
 111            type_param_defs.repr(vcx.tcx()),
 112            substs.repr(vcx.tcx()),
 113            result.repr(vcx.tcx()));
 114     result
 115 }
 116
 117 fn lookup_vtables_for_param(vcx: &VtableContext,
 118                             span: Span,
 119                             // None for substs means the identity
 120                             substs: Option<&ty::substs>,
 121                             type_param_bounds: &ty::ParamBounds,
 122                             ty: ty::t,
 123                             is_early: bool) -> vtable_param_res {
 124     let tcx = vcx.tcx();
 125
 126     // ty is the value supplied for the type parameter A...
 127     let mut param_result = Vec::new();
 128
 129     ty::each_bound_trait_and_supertraits(tcx,
 130                                          type_param_bounds.trait_bounds
 131                                                           .as_slice(),
 132                                          |trait_ref| {
 133         // ...and here trait_ref is each bound that was declared on A,
 134         // expressed in terms of the type parameters.
 135
 136         ty::populate_implementations_for_trait_if_necessary(tcx,
 137                                                             trait_ref.def_id);
 138
 139         // Substitute the values of the type parameters that may
 140         // appear in the bound.
 141         let trait_ref = substs.as_ref().map_or(trait_ref.clone(), |substs| {
 142             debug!("about to subst: {}, {}",
 143                    trait_ref.repr(tcx), substs.repr(tcx));
 144             trait_ref.subst(tcx, *substs)
 145         });
 146
 147         debug!("after subst: {}", trait_ref.repr(tcx));
 148
 149         match lookup_vtable(vcx, span, ty, trait_ref.clone(), is_early) {
 150             Some(vtable) => param_result.push(vtable),
 151             None => {
 152                 vcx.tcx().sess.span_fatal(span,
 153                     format!("failed to find an implementation of \
 154                           trait {} for {}",
 155                          vcx.infcx.trait_ref_to_str(&*trait_ref),
 156                          vcx.infcx.ty_to_str(ty)));
 157             }
 158         }
 159         true
 160     });
 161
 162     debug!("lookup_vtables_for_param result(\
 163             span={:?}, \
 164             type_param_bounds={}, \
 165             ty={}, \
 166             result={})",
 167            span,
 168            type_param_bounds.repr(vcx.tcx()),
 169            ty.repr(vcx.tcx()),
 170            param_result.repr(vcx.tcx()));
 171
 172     param_result
 173 }
 174
 175 fn relate_trait_refs(vcx: &VtableContext,
 176                      span: Span,
 177                      act_trait_ref: Rc<ty::TraitRef>,
 178                      exp_trait_ref: Rc<ty::TraitRef>) {
 179     /*!
 180      *
 181      * Checks that an implementation of `act_trait_ref` is suitable
 182      * for use where `exp_trait_ref` is required and reports an
 183      * error otherwise.
 184      */
 185
 186     match infer::mk_sub_trait_refs(vcx.infcx,
 187                                    false,
 188                                    infer::RelateTraitRefs(span),
 189                                    act_trait_ref.clone(),
 190                                    exp_trait_ref.clone()) {
 191         Ok(()) => {} // Ok.
 192         Err(ref err) => {
 193             // There is an error, but we need to do some work to make
 194             // the message good.
 195             // Resolve any type vars in the trait refs
 196             let r_act_trait_ref =
 197                 vcx.infcx.resolve_type_vars_in_trait_ref_if_possible(&*act_trait_ref);
 198             let r_exp_trait_ref =
 199                 vcx.infcx.resolve_type_vars_in_trait_ref_if_possible(&*exp_trait_ref);
 200             // Only print the message if there aren't any previous type errors
 201             // inside the types.
 202             if !ty::trait_ref_contains_error(&r_act_trait_ref) &&
 203                 !ty::trait_ref_contains_error(&r_exp_trait_ref)
 204             {
 205                 let tcx = vcx.tcx();
 206                 tcx.sess.span_err(span,
 207                     format!("expected {}, but found {} ({})",
 208                          ppaux::trait_ref_to_str(tcx, &r_exp_trait_ref),
 209                          ppaux::trait_ref_to_str(tcx, &r_act_trait_ref),
 210                          ty::type_err_to_str(tcx, err)));
 211             }
 212         }
 213     }
 214 }
 215
 216 // Look up the vtable implementing the trait `trait_ref` at type `t`
 217 fn lookup_vtable(vcx: &VtableContext,
 218                  span: Span,
 219                  ty: ty::t,
 220                  trait_ref: Rc<ty::TraitRef>,
 221                  is_early: bool)
 222                  -> Option<vtable_origin> {
 223     debug!("lookup_vtable(ty={}, trait_ref={})",
 224            vcx.infcx.ty_to_str(ty),
 225            vcx.infcx.trait_ref_to_str(&*trait_ref));
 226     let _i = indenter();
 227
 228     let ty = match fixup_ty(vcx, span, ty, is_early) {
 229         Some(ty) => ty,
 230         None => {
 231             // fixup_ty can only fail if this is early resolution
 232             assert!(is_early);
 233             // The type has unconstrained type variables in it, so we can't
 234             // do early resolution on it. Return some completely bogus vtable
 235             // information: we aren't storing it anyways.
 236             return Some(vtable_param(param_self, 0));
 237         }
 238     };
 239
 240     // If the type is self or a param, we look at the trait/supertrait
 241     // bounds to see if they include the trait we are looking for.
 242     let vtable_opt = match ty::get(ty).sty {
 243         ty::ty_param(param_ty {idx: n, ..}) => {
 244             let env_bounds = &vcx.param_env.type_param_bounds;
 245             if env_bounds.len() > n {
 246                 let type_param_bounds: &[Rc<ty::TraitRef>] =
 247                     env_bounds.get(n).trait_bounds.as_slice();
 248                 lookup_vtable_from_bounds(vcx, span,
 249                                           type_param_bounds,
 250                                           param_numbered(n),
 251                                           trait_ref.clone())
 252             } else {
 253                 None
 254             }
 255         }
 256
 257         ty::ty_self(_) => {
 258             let self_param_bound = vcx.param_env.self_param_bound.clone().unwrap();
 259             lookup_vtable_from_bounds(vcx, span,
 260                                       [self_param_bound],
 261                                       param_self,
 262                                       trait_ref.clone())
 263         }
 264
 265         // Default case just falls through
 266         _ => None
 267     };
 268
 269     if vtable_opt.is_some() { return vtable_opt; }
 270
 271     // If we aren't a self type or param, or it was, but we didn't find it,
 272     // do a search.
 273     search_for_vtable(vcx, span, ty, trait_ref, is_early)
 274 }
 275
 276 // Given a list of bounds on a type, search those bounds to see if any
 277 // of them are the vtable we are looking for.
 278 fn lookup_vtable_from_bounds(vcx: &VtableContext,
 279                              span: Span,
 280                              bounds: &[Rc<ty::TraitRef>],
 281                              param: param_index,
 282                              trait_ref: Rc<ty::TraitRef>)
 283                              -> Option<vtable_origin> {
 284     let tcx = vcx.tcx();
 285
 286     let mut n_bound = 0;
 287     let mut ret = None;
 288     ty::each_bound_trait_and_supertraits(tcx, bounds, |bound_trait_ref| {
 289         debug!("checking bounds trait {}",
 290                bound_trait_ref.repr(vcx.tcx()));
 291
 292         if bound_trait_ref.def_id == trait_ref.def_id {
 293             relate_trait_refs(vcx, span, bound_trait_ref, trait_ref.clone());
 294             let vtable = vtable_param(param, n_bound);
 295             debug!("found param vtable: {:?}",
 296                    vtable);
 297             ret = Some(vtable);
 298             false
 299         } else {
 300             n_bound += 1;
 301             true
 302         }
 303     });
 304     ret
 305 }
 306
 307 fn search_for_vtable(vcx: &VtableContext,
 308                      span: Span,
 309                      ty: ty::t,
 310                      trait_ref: Rc<ty::TraitRef>,
 311                      is_early: bool)
 312                      -> Option<vtable_origin> {
 313     let tcx = vcx.tcx();
 314
 315     let mut found = Vec::new();
 316     let mut impls_seen = HashSet::new();
 317
 318     // Load the implementations from external metadata if necessary.
 319     ty::populate_implementations_for_trait_if_necessary(tcx,
 320                                                         trait_ref.def_id);
 321
 322     let impls = match tcx.trait_impls.borrow().find_copy(&trait_ref.def_id) {
 323         Some(impls) => impls,
 324         None => {
 325             return None;
 326         }
 327     };
 328     // impls is the list of all impls in scope for trait_ref.
 329     for &impl_did in impls.borrow().iter() {
 330         // im is one specific impl of trait_ref.
 331
 332         // First, ensure we haven't processed this impl yet.
 333         if impls_seen.contains(&impl_did) {
 334             continue;
 335         }
 336         impls_seen.insert(impl_did);
 337
 338         // ty::impl_traits gives us the trait im implements.
 339         //
 340         // If foo implements a trait t, and if t is the same trait as
 341         // trait_ref, we need to unify it with trait_ref in order to
 342         // get all the ty vars sorted out.
 343         let r = ty::impl_trait_ref(tcx, impl_did);
 344         let of_trait_ref = r.expect("trait_ref missing on trait impl");
 345         if of_trait_ref.def_id != trait_ref.def_id { continue; }
 346
 347         // At this point, we know that of_trait_ref is the same trait
 348         // as trait_ref, but possibly applied to different substs.
 349         //
 350         // Next, we check whether the "for" ty in the impl is
 351         // compatible with the type that we're casting to a
 352         // trait. That is, if im is:
 353         //
 354         // impl<T> some_trait<T> for self_ty<T> { ... }
 355         //
 356         // we check whether self_ty<T> is the type of the thing that
 357         // we're trying to cast to some_trait.  If not, then we try
 358         // the next impl.
 359         //
 360         // FIXME: document a bit more what this means
 361         //
 362         // FIXME(#5781) this should be mk_eqty not mk_subty
 363         let ty::ty_param_substs_and_ty {
 364             substs: substs,
 365             ty: for_ty
 366         } = impl_self_ty(vcx, span, impl_did);
 367         match infer::mk_subty(vcx.infcx,
 368                               false,
 369                               infer::RelateSelfType(span),
 370                               ty,
 371                               for_ty) {
 372             Err(_) => continue,
 373             Ok(()) => ()
 374         }
 375
 376         // Now, in the previous example, for_ty is bound to
 377         // the type self_ty, and substs is bound to [T].
 378         debug!("The self ty is {} and its substs are {}",
 379                vcx.infcx.ty_to_str(for_ty),
 380                vcx.infcx.tys_to_str(substs.tps.as_slice()));
 381
 382         // Next, we unify trait_ref -- the type that we want to cast
 383         // to -- with of_trait_ref -- the trait that im implements. At
 384         // this point, we require that they be unifiable with each
 385         // other -- that's what relate_trait_refs does.
 386         //
 387         // For example, in the above example, of_trait_ref would be
 388         // some_trait<T>, so we would be unifying trait_ref<U> (for
 389         // some value of U) with some_trait<T>. This would fail if T
 390         // and U weren't compatible.
 391
 392         debug!("(checking vtable) \\#2 relating trait \
 393                 ty {} to of_trait_ref {}",
 394                vcx.infcx.trait_ref_to_str(&*trait_ref),
 395                vcx.infcx.trait_ref_to_str(&*of_trait_ref));
 396
 397         let of_trait_ref = of_trait_ref.subst(tcx, &substs);
 398         relate_trait_refs(vcx, span, of_trait_ref, trait_ref.clone());
 399
 400
 401         // Recall that trait_ref -- the trait type we're casting to --
 402         // is the trait with id trait_ref.def_id applied to the substs
 403         // trait_ref.substs.
 404
 405         // Resolve any sub bounds. Note that there still may be free
 406         // type variables in substs. This might still be OK: the
 407         // process of looking up bounds might constrain some of them.
 408         let im_generics =
 409             ty::lookup_item_type(tcx, impl_did).generics;
 410         let subres = lookup_vtables(vcx, span,
 411                                     im_generics.type_param_defs(), &substs,
 412                                     is_early);
 413
 414
 415         // substs might contain type variables, so we call
 416         // fixup_substs to resolve them.
 417         let substs_f = match fixup_substs(vcx, span,
 418                                           trait_ref.def_id,
 419                                           substs,
 420                                           is_early) {
 421             Some(ref substs) => (*substs).clone(),
 422             None => {
 423                 assert!(is_early);
 424                 // Bail out with a bogus answer
 425                 return Some(vtable_param(param_self, 0));
 426             }
 427         };
 428
 429         debug!("The fixed-up substs are {} - \
 430                 they will be unified with the bounds for \
 431                 the target ty, {}",
 432                vcx.infcx.tys_to_str(substs_f.tps.as_slice()),
 433                vcx.infcx.trait_ref_to_str(&*trait_ref));
 434
 435         // Next, we unify the fixed-up substitutions for the impl self
 436         // ty with the substitutions from the trait type that we're
 437         // trying to cast to. connect_trait_tps requires these lists
 438         // of types to unify pairwise.
 439         // I am a little confused about this, since it seems to be
 440         // very similar to the relate_trait_refs we already do,
 441         // but problems crop up if it is removed, so... -sully
 442         connect_trait_tps(vcx, span, &substs_f, trait_ref.clone(), impl_did);
 443
 444         // Finally, we register that we found a matching impl, and
 445         // record the def ID of the impl as well as the resolved list
 446         // of type substitutions for the target trait.
 447         found.push(vtable_static(impl_did, substs_f.tps.clone(), subres));
 448     }
 449
 450     match found.len() {
 451         0 => { return None }
 452         1 => return Some(found.get(0).clone()),
 453         _ => {
 454             if !is_early {
 455                 vcx.tcx().sess.span_err(span, "multiple applicable methods in scope");
 456             }
 457             return Some(found.get(0).clone());
 458         }
 459     }
 460 }
 461
 462
 463 fn fixup_substs(vcx: &VtableContext,
 464                 span: Span,
 465                 id: ast::DefId,
 466                 substs: ty::substs,
 467                 is_early: bool)
 468                 -> Option<ty::substs> {
 469     let tcx = vcx.tcx();
 470     // use a dummy type just to package up the substs that need fixing up
 471     let t = ty::mk_trait(tcx,
 472                          id, substs,
 473                          ty::RegionTraitStore(ty::ReStatic, ast::MutImmutable),
 474                          ty::EmptyBuiltinBounds());
 475     fixup_ty(vcx, span, t, is_early).map(|t_f| {
 476         match ty::get(t_f).sty {
 477           ty::ty_trait(ref inner) => inner.substs.clone(),
 478           _ => fail!("t_f should be a trait")
 479         }
 480     })
 481 }
 482
 483 fn fixup_ty(vcx: &VtableContext,
 484             span: Span,
 485             ty: ty::t,
 486             is_early: bool)
 487             -> Option<ty::t> {
 488     let tcx = vcx.tcx();
 489     match resolve_type(vcx.infcx, ty, resolve_and_force_all_but_regions) {
 490         Ok(new_type) => Some(new_type),
 491         Err(e) if !is_early => {
 492             tcx.sess.span_fatal(span,
 493                 format!("cannot determine a type \
 494                       for this bounded type parameter: {}",
 495                      fixup_err_to_str(e)))
 496         }
 497         Err(_) => {
 498             None
 499         }
 500     }
 501 }
 502
 503 fn connect_trait_tps(vcx: &VtableContext,
 504                      span: Span,
 505                      impl_substs: &ty::substs,
 506                      trait_ref: Rc<ty::TraitRef>,
 507                      impl_did: ast::DefId) {
 508     let tcx = vcx.tcx();
 509
 510     let impl_trait_ref = match ty::impl_trait_ref(tcx, impl_did) {
 511         Some(t) => t,
 512         None => vcx.tcx().sess.span_bug(span,
 513                                   "connect_trait_tps invoked on a type impl")
 514     };
 515
 516     let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs);
 517     relate_trait_refs(vcx, span, impl_trait_ref, trait_ref);
 518 }
 519
 520 fn insert_vtables(fcx: &FnCtxt, vtable_key: MethodCall, vtables: vtable_res) {
 521     debug!("insert_vtables(vtable_key={}, vtables={:?})",
 522            vtable_key, vtables.repr(fcx.tcx()));
 523     fcx.inh.vtable_map.borrow_mut().insert(vtable_key, vtables);
 524 }
 525
 526 pub fn early_resolve_expr(ex: &ast::Expr, fcx: &FnCtxt, is_early: bool) {
 527     debug!("vtable: early_resolve_expr() ex with id {:?} (early: {}): {}",
 528            ex.id, is_early, expr_to_str(ex));
 529     let _indent = indenter();
 530
 531     let cx = fcx.ccx;
 532     let resolve_object_cast = |src: &ast::Expr, target_ty: ty::t| {
 533       match ty::get(target_ty).sty {
 534           // Bounds of type's contents are not checked here, but in kind.rs.
 535           ty::ty_trait(~ty::TyTrait {
 536               def_id: target_def_id, substs: ref target_substs, store, ..
 537           }) => {
 538               fn mutability_allowed(a_mutbl: ast::Mutability,
 539                                     b_mutbl: ast::Mutability) -> bool {
 540                   a_mutbl == b_mutbl ||
 541                   (a_mutbl == ast::MutMutable && b_mutbl == ast::MutImmutable)
 542               }
 543               // Look up vtables for the type we're casting to,
 544               // passing in the source and target type.  The source
 545               // must be a pointer type suitable to the object sigil,
 546               // e.g.: `&x as &Trait` or `~x as ~Trait`
 547               let ty = structurally_resolved_type(fcx, ex.span,
 548                                                   fcx.expr_ty(src));
 549               match (&ty::get(ty).sty, store) {
 550                   (&ty::ty_rptr(_, mt), ty::RegionTraitStore(_, mutbl))
 551                     if !mutability_allowed(mt.mutbl, mutbl) => {
 552                       fcx.tcx().sess.span_err(ex.span,
 553                                               format!("types differ in mutability"));
 554                   }
 555
 556                   (&ty::ty_uniq(..), ty::UniqTraitStore) |
 557                   (&ty::ty_rptr(..), ty::RegionTraitStore(..)) => {
 558                     let typ = match &ty::get(ty).sty {
 559                         &ty::ty_box(typ) | &ty::ty_uniq(typ) => typ,
 560                         &ty::ty_rptr(_, mt) => mt.ty,
 561                         _ => fail!("shouldn't get here"),
 562                     };
 563
 564                       let vcx = fcx.vtable_context();
 565                       let target_trait_ref = Rc::new(ty::TraitRef {
 566                           def_id: target_def_id,
 567                           substs: ty::substs {
 568                               tps: target_substs.tps.clone(),
 569                               regions: target_substs.regions.clone(),
 570                               self_ty: Some(typ)
 571                           }
 572                       });
 573
 574                       let param_bounds = ty::ParamBounds {
 575                           builtin_bounds: ty::EmptyBuiltinBounds(),
 576                           trait_bounds: vec!(target_trait_ref)
 577                       };
 578                       let vtables =
 579                             lookup_vtables_for_param(&vcx,
 580                                                      ex.span,
 581                                                      None,
 582                                                      &param_bounds,
 583                                                      typ,
 584                                                      is_early);
 585
 586                       if !is_early {
 587                           insert_vtables(fcx, MethodCall::expr(ex.id), vec!(vtables));
 588                       }
 589
 590                       // Now, if this is &trait, we need to link the
 591                       // regions.
 592                       match (&ty::get(ty).sty, store) {
 593                           (&ty::ty_rptr(ra, _),
 594                            ty::RegionTraitStore(rb, _)) => {
 595                               infer::mk_subr(fcx.infcx(),
 596                                              false,
 597                                              infer::RelateObjectBound(
 598                                                  ex.span),
 599                                              rb,
 600                                              ra);
 601                           }
 602                           _ => {}
 603                       }
 604                   }
 605
 606                   (_, ty::UniqTraitStore) => {
 607                       fcx.ccx.tcx.sess.span_err(
 608                           ex.span,
 609                           format!("can only cast an ~-pointer \
 610                                 to a ~-object, not a {}",
 611                                ty::ty_sort_str(fcx.tcx(), ty)));
 612                   }
 613
 614                   (_, ty::RegionTraitStore(..)) => {
 615                       fcx.ccx.tcx.sess.span_err(
 616                           ex.span,
 617                           format!("can only cast an &-pointer \
 618                                 to an &-object, not a {}",
 619                                ty::ty_sort_str(fcx.tcx(), ty)));
 620                   }
 621               }
 622           }
 623           _ => { /* not a cast to a trait; ignore */ }
 624       }
 625     };
 626     match ex.node {
 627       ast::ExprPath(..) => {
 628         fcx.opt_node_ty_substs(ex.id, |substs| {
 629             debug!("vtable resolution on parameter bounds for expr {}",
 630                    ex.repr(fcx.tcx()));
 631             let def = cx.tcx.def_map.borrow().get_copy(&ex.id);
 632             let did = ast_util::def_id_of_def(def);
 633             let item_ty = ty::lookup_item_type(cx.tcx, did);
 634             debug!("early resolve expr: def {:?} {:?}, {:?}, {}", ex.id, did, def,
 635                    fcx.infcx().ty_to_str(item_ty.ty));
 636             if has_trait_bounds(item_ty.generics.type_param_defs()) {
 637                 debug!("early_resolve_expr: looking up vtables for type params {}",
 638                        item_ty.generics.type_param_defs().repr(fcx.tcx()));
 639                 let vcx = fcx.vtable_context();
 640                 let vtbls = lookup_vtables(&vcx, ex.span,
 641                                            item_ty.generics.type_param_defs(),
 642                                            substs, is_early);
 643                 if !is_early {
 644                     insert_vtables(fcx, MethodCall::expr(ex.id), vtbls);
 645                 }
 646             }
 647             true
 648         });
 649       }
 650
 651       // Must resolve bounds on methods with bounded params
 652       ast::ExprBinary(_, _, _) |
 653       ast::ExprUnary(_, _) |
 654       ast::ExprAssignOp(_, _, _) |
 655       ast::ExprIndex(_, _) |
 656       ast::ExprMethodCall(_, _, _) => {
 657         match fcx.inh.method_map.borrow().find(&MethodCall::expr(ex.id)) {
 658           Some(method) => {
 659             debug!("vtable resolution on parameter bounds for method call {}",
 660                    ex.repr(fcx.tcx()));
 661             let type_param_defs = ty::method_call_type_param_defs(cx.tcx, method.origin);
 662             if has_trait_bounds(type_param_defs.as_slice()) {
 663                 let substs = fcx.method_ty_substs(ex.id);
 664                 let vcx = fcx.vtable_context();
 665                 let vtbls = lookup_vtables(&vcx, ex.span,
 666                                            type_param_defs.as_slice(),
 667                                            &substs, is_early);
 668                 if !is_early {
 669                     insert_vtables(fcx, MethodCall::expr(ex.id), vtbls);
 670                 }
 671             }
 672           }
 673           None => {}
 674         }
 675       }
 676       ast::ExprCast(src, _) => {
 677           debug!("vtable resolution on expr {}", ex.repr(fcx.tcx()));
 678           let target_ty = fcx.expr_ty(ex);
 679           resolve_object_cast(src, target_ty);
 680       }
 681       _ => ()
 682     }
 683
 684     // Search for auto-adjustments to find trait coercions
 685     match fcx.inh.adjustments.borrow().find(&ex.id) {
 686         Some(adjustment) => {
 687             match *adjustment {
 688                 AutoDerefRef(adj) => {
 689                     for autoderef in range(0, adj.autoderefs) {
 690                         let method_call = MethodCall::autoderef(ex.id, autoderef as u32);
 691                         match fcx.inh.method_map.borrow().find(&method_call) {
 692                             Some(method) => {
 693                                 debug!("vtable resolution on parameter bounds for autoderef {}",
 694                                        ex.repr(fcx.tcx()));
 695                                 let type_param_defs =
 696                                     ty::method_call_type_param_defs(cx.tcx, method.origin);
 697                                 if has_trait_bounds(type_param_defs.deref().as_slice()) {
 698                                     let vcx = fcx.vtable_context();
 699                                     let vtbls = lookup_vtables(&vcx, ex.span,
 700                                                                type_param_defs.deref()
 701                                                                .as_slice(),
 702                                                                &method.substs, is_early);
 703                                     if !is_early {
 704                                         insert_vtables(fcx, method_call, vtbls);
 705                                     }
 706                                 }
 707                             }
 708                             None => {}
 709                         }
 710                     }
 711                 }
 712                 AutoObject(store,
 713                            bounds,
 714                            def_id,
 715                            ref substs) => {
 716                     debug!("doing trait adjustment for expr {} {} \
 717                             (early? {})",
 718                            ex.id,
 719                            ex.repr(fcx.tcx()),
 720                            is_early);
 721
 722                     let object_ty = ty::mk_trait(cx.tcx, def_id,
 723                                                  substs.clone(),
 724                                                  store, bounds);
 725                     resolve_object_cast(ex, object_ty);
 726                 }
 727                 AutoAddEnv(..) => {}
 728             }
 729         }
 730         None => {}
 731     }
 732 }
 733
 734 pub fn resolve_impl(tcx: &ty::ctxt,
 735                     impl_item: &ast::Item,
 736                     impl_generics: &ty::Generics,
 737                     impl_trait_ref: &ty::TraitRef) {
 738     let param_env = ty::construct_parameter_environment(
 739         tcx,
 740         None,
 741         impl_generics.type_param_defs(),
 742         [],
 743         impl_generics.region_param_defs(),
 744         [],
 745         impl_item.id);
 746
 747     let impl_trait_ref = impl_trait_ref.subst(tcx, &param_env.free_substs);
 748
 749     let infcx = &infer::new_infer_ctxt(tcx);
 750     let vcx = VtableContext { infcx: infcx, param_env: &param_env };
 751
 752     // First, check that the impl implements any trait bounds
 753     // on the trait.
 754     let trait_def = ty::lookup_trait_def(tcx, impl_trait_ref.def_id);
 755     let vtbls = lookup_vtables(&vcx, impl_item.span,
 756                                trait_def.generics.type_param_defs(),
 757                                &impl_trait_ref.substs,
 758                                false);
 759
 760     // Now, locate the vtable for the impl itself. The real
 761     // purpose of this is to check for supertrait impls,
 762     // but that falls out of doing this.
 763     let param_bounds = ty::ParamBounds {
 764         builtin_bounds: ty::EmptyBuiltinBounds(),
 765         trait_bounds: vec!(Rc::new(impl_trait_ref))
 766     };
 767     let t = ty::node_id_to_type(tcx, impl_item.id);
 768     let t = t.subst(tcx, &param_env.free_substs);
 769     debug!("=== Doing a self lookup now.");
 770
 771     // Right now, we don't have any place to store this.
 772     // We will need to make one so we can use this information
 773     // for compiling default methods that refer to supertraits.
 774     let self_vtable_res =
 775         lookup_vtables_for_param(&vcx, impl_item.span, None,
 776                                  &param_bounds, t, false);
 777
 778
 779     let res = impl_res {
 780         trait_vtables: vtbls,
 781         self_vtables: self_vtable_res
 782     };
 783     let impl_def_id = ast_util::local_def(impl_item.id);
 784
 785     tcx.impl_vtables.borrow_mut().insert(impl_def_id, res);
 786 }
 787
 788 /// Resolve vtables for a method call after typeck has finished.
 789 /// Used by trans to monomorphize artificial method callees (e.g. drop).
 790 pub fn trans_resolve_method(tcx: &ty::ctxt, id: ast::NodeId,
 791                             substs: &ty::substs) -> Option<vtable_res> {
 792     let generics = ty::lookup_item_type(tcx, ast_util::local_def(id)).generics;
 793     let type_param_defs = &*generics.type_param_defs;
 794     if has_trait_bounds(type_param_defs.as_slice()) {
 795         let vcx = VtableContext {
 796             infcx: &infer::new_infer_ctxt(tcx),
 797             param_env: &ty::construct_parameter_environment(tcx, None, [], [], [], [], id)
 798         };
 799
 800         Some(lookup_vtables(&vcx,
 801                             tcx.map.span(id),
 802                             type_param_defs.as_slice(),
 803                             substs,
 804                             false))
 805     } else {
 806         None
 807     }
 808 }
 809
 810 impl<'a, 'b> visit::Visitor<()> for &'a FnCtxt<'b> {
 811     fn visit_expr(&mut self, ex: &ast::Expr, _: ()) {
 812         early_resolve_expr(ex, *self, false);
 813         visit::walk_expr(self, ex, ());
 814     }
 815     fn visit_item(&mut self, _: &ast::Item, _: ()) {
 816         // no-op
 817     }
 818 }
 819
 820 // Detect points where a trait-bounded type parameter is
 821 // instantiated, resolve the impls for the parameters.
 822 pub fn resolve_in_block(mut fcx: &FnCtxt, bl: &ast::Block) {
 823     visit::walk_block(&mut fcx, bl, ());
 824 }