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