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