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

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