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