src/librustc/middle/typeck/mod.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
  13 typeck.rs, an introduction
  14
  15 The type checker is responsible for:
  16
  17 1. Determining the type of each expression
  18 2. Resolving methods and traits
  19 3. Guaranteeing that most type rules are met ("most?", you say, "why most?"
  20    Well, dear reader, read on)
  21
  22 The main entry point is `check_crate()`.  Type checking operates in
  23 several major phases:
  24
  25 1. The collect phase first passes over all items and determines their
  26    type, without examining their "innards".
  27
  28 2. Variance inference then runs to compute the variance of each parameter
  29
  30 3. Coherence checks for overlapping or orphaned impls
  31
  32 4. Finally, the check phase then checks function bodies and so forth.
  33    Within the check phase, we check each function body one at a time
  34    (bodies of function expressions are checked as part of the
  35    containing function).  Inference is used to supply types wherever
  36    they are unknown. The actual checking of a function itself has
  37    several phases (check, regionck, writeback), as discussed in the
  38    documentation for the `check` module.
  39
  40 The type checker is defined into various submodules which are documented
  41 independently:
  42
  43 - astconv: converts the AST representation of types
  44   into the `ty` representation
  45
  46 - collect: computes the types of each top-level item and enters them into
  47   the `cx.tcache` table for later use
  48
  49 - coherence: enforces coherence rules, builds some tables
  50
  51 - variance: variance inference
  52
  53 - check: walks over function bodies and type checks them, inferring types for
  54   local variables, type parameters, etc as necessary.
  55
  56 - infer: finds the types to use for each type variable such that
  57   all subtyping and assignment constraints are met.  In essence, the check
  58   module specifies the constraints, and the infer module solves them.
  59
  60 */
  61
  62 #![allow(non_camel_case_types)]
  63
  64 use driver::session;
  65
  66 use middle::resolve;
  67 use middle::ty;
  68 use util::common::time;
  69 use util::ppaux::Repr;
  70 use util::ppaux;
  71 use util::nodemap::{DefIdMap, FnvHashMap};
  72
  73 use std::cell::RefCell;
  74 use std::rc::Rc;
  75 use collections::List;
  76 use syntax::codemap::Span;
  77 use syntax::print::pprust::*;
  78 use syntax::{ast, ast_map, abi};
  79
  80 pub mod check;
  81 pub mod rscope;
  82 pub mod astconv;
  83 pub mod infer;
  84 pub mod collect;
  85 pub mod coherence;
  86 pub mod variance;
  87
  88 #[deriving(Clone, Encodable, Decodable, Eq, Ord)]
  89 pub enum param_index {
  90     param_numbered(uint),
  91     param_self
  92 }
  93
  94 #[deriving(Clone, Encodable, Decodable)]
  95 pub enum MethodOrigin {
  96     // fully statically resolved method
  97     MethodStatic(ast::DefId),
  98
  99     // method invoked on a type parameter with a bounded trait
 100     MethodParam(MethodParam),
 101
 102     // method invoked on a trait instance
 103     MethodObject(MethodObject),
 104
 105 }
 106
 107 // details for a method invoked with a receiver whose type is a type parameter
 108 // with a bounded trait.
 109 #[deriving(Clone, Encodable, Decodable)]
 110 pub struct MethodParam {
 111     // the trait containing the method to be invoked
 112     trait_id: ast::DefId,
 113
 114     // index of the method to be invoked amongst the trait's methods
 115     method_num: uint,
 116
 117     // index of the type parameter (from those that are in scope) that is
 118     // the type of the receiver
 119     param_num: param_index,
 120
 121     // index of the bound for this type parameter which specifies the trait
 122     bound_num: uint,
 123 }
 124
 125 // details for a method invoked with a receiver whose type is an object
 126 #[deriving(Clone, Encodable, Decodable)]
 127 pub struct MethodObject {
 128     // the (super)trait containing the method to be invoked
 129     trait_id: ast::DefId,
 130
 131     // the actual base trait id of the object
 132     object_trait_id: ast::DefId,
 133
 134     // index of the method to be invoked amongst the trait's methods
 135     method_num: uint,
 136
 137     // index into the actual runtime vtable.
 138     // the vtable is formed by concatenating together the method lists of
 139     // the base object trait and all supertraits;  this is the index into
 140     // that vtable
 141     real_index: uint,
 142 }
 143
 144 #[deriving(Clone)]
 145 pub struct MethodCallee {
 146     origin: MethodOrigin,
 147     ty: ty::t,
 148     substs: ty::substs
 149 }
 150
 151 #[deriving(Clone, Eq, TotalEq, Hash, Show)]
 152 pub struct MethodCall {
 153     expr_id: ast::NodeId,
 154     autoderef: u32
 155 }
 156
 157 impl MethodCall {
 158     pub fn expr(id: ast::NodeId) -> MethodCall {
 159         MethodCall {
 160             expr_id: id,
 161             autoderef: 0
 162         }
 163     }
 164
 165     pub fn autoderef(expr_id: ast::NodeId, autoderef: u32) -> MethodCall {
 166         MethodCall {
 167             expr_id: expr_id,
 168             autoderef: 1 + autoderef
 169         }
 170     }
 171 }
 172
 173 // maps from an expression id that corresponds to a method call to the details
 174 // of the method to be invoked
 175 pub type MethodMap = @RefCell<FnvHashMap<MethodCall, MethodCallee>>;
 176
 177 pub type vtable_param_res = @Vec<vtable_origin> ;
 178 // Resolutions for bounds of all parameters, left to right, for a given path.
 179 pub type vtable_res = @Vec<vtable_param_res> ;
 180
 181 #[deriving(Clone)]
 182 pub enum vtable_origin {
 183     /*
 184       Statically known vtable. def_id gives the class or impl item
 185       from whence comes the vtable, and tys are the type substs.
 186       vtable_res is the vtable itself
 187      */
 188     vtable_static(ast::DefId, Vec<ty::t> , vtable_res),
 189
 190     /*
 191       Dynamic vtable, comes from a parameter that has a bound on it:
 192       fn foo<T:quux,baz,bar>(a: T) -- a's vtable would have a
 193       vtable_param origin
 194
 195       The first argument is the param index (identifying T in the example),
 196       and the second is the bound number (identifying baz)
 197      */
 198     vtable_param(param_index, uint),
 199 }
 200
 201 impl Repr for vtable_origin {
 202     fn repr(&self, tcx: &ty::ctxt) -> ~str {
 203         match *self {
 204             vtable_static(def_id, ref tys, ref vtable_res) => {
 205                 format!("vtable_static({:?}:{}, {}, {})",
 206                      def_id,
 207                      ty::item_path_str(tcx, def_id),
 208                      tys.repr(tcx),
 209                      vtable_res.repr(tcx))
 210             }
 211
 212             vtable_param(x, y) => {
 213                 format!("vtable_param({:?}, {:?})", x, y)
 214             }
 215         }
 216     }
 217 }
 218
 219 pub type vtable_map = @RefCell<FnvHashMap<MethodCall, vtable_res>>;
 220
 221
 222 // Information about the vtable resolutions for a trait impl.
 223 // Mostly the information is important for implementing default
 224 // methods.
 225 #[deriving(Clone)]
 226 pub struct impl_res {
 227     // resolutions for any bounded params on the trait definition
 228     trait_vtables: vtable_res,
 229     // resolutions for the trait /itself/ (and for supertraits)
 230     self_vtables: vtable_param_res
 231 }
 232
 233 impl Repr for impl_res {
 234     fn repr(&self, tcx: &ty::ctxt) -> ~str {
 235         format!("impl_res \\{trait_vtables={}, self_vtables={}\\}",
 236              self.trait_vtables.repr(tcx),
 237              self.self_vtables.repr(tcx))
 238     }
 239 }
 240
 241 pub type impl_vtable_map = RefCell<DefIdMap<impl_res>>;
 242
 243 pub struct CrateCtxt<'a> {
 244     // A mapping from method call sites to traits that have that method.
 245     trait_map: resolve::TraitMap,
 246     method_map: MethodMap,
 247     vtable_map: vtable_map,
 248     tcx: &'a ty::ctxt
 249 }
 250
 251 // Functions that write types into the node type table
 252 pub fn write_ty_to_tcx(tcx: &ty::ctxt, node_id: ast::NodeId, ty: ty::t) {
 253     debug!("write_ty_to_tcx({}, {})", node_id, ppaux::ty_to_str(tcx, ty));
 254     assert!(!ty::type_needs_infer(ty));
 255     tcx.node_types.borrow_mut().insert(node_id as uint, ty);
 256 }
 257 pub fn write_substs_to_tcx(tcx: &ty::ctxt,
 258                            node_id: ast::NodeId,
 259                            substs: Vec<ty::t> ) {
 260     if substs.len() > 0u {
 261         debug!("write_substs_to_tcx({}, {:?})", node_id,
 262                substs.map(|t| ppaux::ty_to_str(tcx, *t)));
 263         assert!(substs.iter().all(|t| !ty::type_needs_infer(*t)));
 264
 265         tcx.node_type_substs.borrow_mut().insert(node_id, substs);
 266     }
 267 }
 268 pub fn write_tpt_to_tcx(tcx: &ty::ctxt,
 269                         node_id: ast::NodeId,
 270                         tpt: &ty::ty_param_substs_and_ty) {
 271     write_ty_to_tcx(tcx, node_id, tpt.ty);
 272     if !tpt.substs.tps.is_empty() {
 273         write_substs_to_tcx(tcx, node_id, tpt.substs.tps.clone());
 274     }
 275 }
 276
 277 pub fn lookup_def_tcx(tcx:&ty::ctxt, sp: Span, id: ast::NodeId) -> ast::Def {
 278     match tcx.def_map.borrow().find(&id) {
 279         Some(&x) => x,
 280         _ => {
 281             tcx.sess.span_fatal(sp, "internal error looking up a definition")
 282         }
 283     }
 284 }
 285
 286 pub fn lookup_def_ccx(ccx: &CrateCtxt, sp: Span, id: ast::NodeId)
 287                    -> ast::Def {
 288     lookup_def_tcx(ccx.tcx, sp, id)
 289 }
 290
 291 pub fn no_params(t: ty::t) -> ty::ty_param_bounds_and_ty {
 292     ty::ty_param_bounds_and_ty {
 293         generics: ty::Generics {type_param_defs: Rc::new(Vec::new()),
 294                                 region_param_defs: Rc::new(Vec::new())},
 295         ty: t
 296     }
 297 }
 298
 299 pub fn require_same_types(tcx: &ty::ctxt,
 300                           maybe_infcx: Option<&infer::InferCtxt>,
 301                           t1_is_expected: bool,
 302                           span: Span,
 303                           t1: ty::t,
 304                           t2: ty::t,
 305                           msg: || -> ~str)
 306                           -> bool {
 307     let result = match maybe_infcx {
 308         None => {
 309             let infcx = infer::new_infer_ctxt(tcx);
 310             infer::mk_eqty(&infcx, t1_is_expected, infer::Misc(span), t1, t2)
 311         }
 312         Some(infcx) => {
 313             infer::mk_eqty(infcx, t1_is_expected, infer::Misc(span), t1, t2)
 314         }
 315     };
 316
 317     match result {
 318         Ok(_) => true,
 319         Err(ref terr) => {
 320             tcx.sess.span_err(span, msg() + ": " +
 321                               ty::type_err_to_str(tcx, terr));
 322             ty::note_and_explain_type_err(tcx, terr);
 323             false
 324         }
 325     }
 326 }
 327
 328 // a list of mapping from in-scope-region-names ("isr") to the
 329 // corresponding ty::Region
 330 pub type isr_alist = @List<(ty::BoundRegion, ty::Region)>;
 331
 332 trait get_region<'a, T:'static> {
 333     fn get(&'a self, br: ty::BoundRegion) -> ty::Region;
 334 }
 335
 336 impl<'a, T:'static> get_region <'a, T> for isr_alist {
 337     fn get(&'a self, br: ty::BoundRegion) -> ty::Region {
 338         let mut region = None;
 339         for isr in self.iter() {
 340             let (isr_br, isr_r) = *isr;
 341             if isr_br == br { region = Some(isr_r); break; }
 342         };
 343         region.unwrap()
 344     }
 345 }
 346
 347 fn check_main_fn_ty(ccx: &CrateCtxt,
 348                     main_id: ast::NodeId,
 349                     main_span: Span) {
 350     let tcx = ccx.tcx;
 351     let main_t = ty::node_id_to_type(tcx, main_id);
 352     match ty::get(main_t).sty {
 353         ty::ty_bare_fn(..) => {
 354             match tcx.map.find(main_id) {
 355                 Some(ast_map::NodeItem(it)) => {
 356                     match it.node {
 357                         ast::ItemFn(_, _, _, ref ps, _)
 358                         if ps.is_parameterized() => {
 359                             tcx.sess.span_err(
 360                                 main_span,
 361                                 "main function is not allowed to have type parameters");
 362                             return;
 363                         }
 364                         _ => ()
 365                     }
 366                 }
 367                 _ => ()
 368             }
 369             let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
 370                 purity: ast::ImpureFn,
 371                 abis: abi::AbiSet::Rust(),
 372                 sig: ty::FnSig {
 373                     binder_id: main_id,
 374                     inputs: Vec::new(),
 375                     output: ty::mk_nil(),
 376                     variadic: false
 377                 }
 378             });
 379
 380             require_same_types(tcx, None, false, main_span, main_t, se_ty,
 381                 || format!("main function expects type: `{}`",
 382                         ppaux::ty_to_str(ccx.tcx, se_ty)));
 383         }
 384         _ => {
 385             tcx.sess.span_bug(main_span,
 386                               format!("main has a non-function type: found `{}`",
 387                                    ppaux::ty_to_str(tcx, main_t)));
 388         }
 389     }
 390 }
 391
 392 fn check_start_fn_ty(ccx: &CrateCtxt,
 393                      start_id: ast::NodeId,
 394                      start_span: Span) {
 395     let tcx = ccx.tcx;
 396     let start_t = ty::node_id_to_type(tcx, start_id);
 397     match ty::get(start_t).sty {
 398         ty::ty_bare_fn(_) => {
 399             match tcx.map.find(start_id) {
 400                 Some(ast_map::NodeItem(it)) => {
 401                     match it.node {
 402                         ast::ItemFn(_,_,_,ref ps,_)
 403                         if ps.is_parameterized() => {
 404                             tcx.sess.span_err(
 405                                 start_span,
 406                                 "start function is not allowed to have type parameters");
 407                             return;
 408                         }
 409                         _ => ()
 410                     }
 411                 }
 412                 _ => ()
 413             }
 414
 415             let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
 416                 purity: ast::ImpureFn,
 417                 abis: abi::AbiSet::Rust(),
 418                 sig: ty::FnSig {
 419                     binder_id: start_id,
 420                     inputs: vec!(
 421                         ty::mk_int(),
 422                         ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, ty::mk_u8()))
 423                     ),
 424                     output: ty::mk_int(),
 425                     variadic: false
 426                 }
 427             });
 428
 429             require_same_types(tcx, None, false, start_span, start_t, se_ty,
 430                 || format!("start function expects type: `{}`", ppaux::ty_to_str(ccx.tcx, se_ty)));
 431
 432         }
 433         _ => {
 434             tcx.sess.span_bug(start_span,
 435                               format!("start has a non-function type: found `{}`",
 436                                    ppaux::ty_to_str(tcx, start_t)));
 437         }
 438     }
 439 }
 440
 441 fn check_for_entry_fn(ccx: &CrateCtxt) {
 442     let tcx = ccx.tcx;
 443     if !tcx.sess.building_library.get() {
 444         match tcx.sess.entry_fn.get() {
 445           Some((id, sp)) => match tcx.sess.entry_type.get() {
 446               Some(session::EntryMain) => check_main_fn_ty(ccx, id, sp),
 447               Some(session::EntryStart) => check_start_fn_ty(ccx, id, sp),
 448               Some(session::EntryNone) => {}
 449               None => tcx.sess.bug("entry function without a type")
 450           },
 451           None => {}
 452         }
 453     }
 454 }
 455
 456 pub fn check_crate(tcx: &ty::ctxt,
 457                    trait_map: resolve::TraitMap,
 458                    krate: &ast::Crate)
 459                 -> (MethodMap, vtable_map) {
 460     let time_passes = tcx.sess.time_passes();
 461     let ccx = CrateCtxt {
 462         trait_map: trait_map,
 463         method_map: @RefCell::new(FnvHashMap::new()),
 464         vtable_map: @RefCell::new(FnvHashMap::new()),
 465         tcx: tcx
 466     };
 467
 468     time(time_passes, "type collecting", (), |_|
 469         collect::collect_item_types(&ccx, krate));
 470
 471     // this ensures that later parts of type checking can assume that items
 472     // have valid types and not error
 473     tcx.sess.abort_if_errors();
 474
 475     time(time_passes, "variance inference", (), |_|
 476          variance::infer_variance(tcx, krate));
 477
 478     time(time_passes, "coherence checking", (), |_|
 479         coherence::check_coherence(&ccx, krate));
 480
 481     time(time_passes, "type checking", (), |_|
 482         check::check_item_types(&ccx, krate));
 483
 484     check_for_entry_fn(&ccx);
 485     tcx.sess.abort_if_errors();
 486     (ccx.method_map, ccx.vtable_map)
 487 }