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

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