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