src/librustc/middle/typeck/mod.rs

   1 // Copyright 2012 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 /*
  12
  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
  63 use driver::session;
  64
  65 use middle::resolve;
  66 use middle::ty;
  67 use util::common::time;
  68 use util::ppaux::Repr;
  69 use util::ppaux;
  70
  71 use std::cell::RefCell;
  72 use std::hashmap::HashMap;
  73 use std::rc::Rc;
  74 use collections::List;
  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 method_origin {
  96     // fully statically resolved method
  97     method_static(ast::DefId),
  98
  99     // method invoked on a type parameter with a bounded trait
 100     method_param(method_param),
 101
 102     // method invoked on a trait instance
 103     method_object(method_object),
 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 method_param {
 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 method_object {
 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
 145 #[deriving(Clone)]
 146 pub struct method_map_entry {
 147     // method details being invoked
 148     origin: method_origin,
 149 }
 150
 151 // maps from an expression id that corresponds to a method call to the details
 152 // of the method to be invoked
 153 pub type method_map = @RefCell<HashMap<ast::NodeId, method_map_entry>>;
 154
 155 pub type vtable_param_res = @~[vtable_origin];
 156 // Resolutions for bounds of all parameters, left to right, for a given path.
 157 pub type vtable_res = @~[vtable_param_res];
 158
 159 #[deriving(Clone)]
 160 pub enum vtable_origin {
 161     /*
 162       Statically known vtable. def_id gives the class or impl item
 163       from whence comes the vtable, and tys are the type substs.
 164       vtable_res is the vtable itself
 165      */
 166     vtable_static(ast::DefId, ~[ty::t], vtable_res),
 167
 168     /*
 169       Dynamic vtable, comes from a parameter that has a bound on it:
 170       fn foo<T:quux,baz,bar>(a: T) -- a's vtable would have a
 171       vtable_param origin
 172
 173       The first argument is the param index (identifying T in the example),
 174       and the second is the bound number (identifying baz)
 175      */
 176     vtable_param(param_index, uint),
 177 }
 178
 179 impl Repr for vtable_origin {
 180     fn repr(&self, tcx: ty::ctxt) -> ~str {
 181         match *self {
 182             vtable_static(def_id, ref tys, ref vtable_res) => {
 183                 format!("vtable_static({:?}:{}, {}, {})",
 184                      def_id,
 185                      ty::item_path_str(tcx, def_id),
 186                      tys.repr(tcx),
 187                      vtable_res.repr(tcx))
 188             }
 189
 190             vtable_param(x, y) => {
 191                 format!("vtable_param({:?}, {:?})", x, y)
 192             }
 193         }
 194     }
 195 }
 196
 197 pub type vtable_map = @RefCell<HashMap<ast::NodeId, vtable_res>>;
 198
 199
 200 // Information about the vtable resolutions for for a trait impl.
 201 // Mostly the information is important for implementing default
 202 // methods.
 203 #[deriving(Clone)]
 204 pub struct impl_res {
 205     // resolutions for any bounded params on the trait definition
 206     trait_vtables: vtable_res,
 207     // resolutions for the trait /itself/ (and for supertraits)
 208     self_vtables: vtable_param_res
 209 }
 210
 211 impl Repr for impl_res {
 212     fn repr(&self, tcx: ty::ctxt) -> ~str {
 213         format!("impl_res \\{trait_vtables={}, self_vtables={}\\}",
 214              self.trait_vtables.repr(tcx),
 215              self.self_vtables.repr(tcx))
 216     }
 217 }
 218
 219 pub type impl_vtable_map = RefCell<HashMap<ast::DefId, impl_res>>;
 220
 221 pub struct CrateCtxt {
 222     // A mapping from method call sites to traits that have that method.
 223     trait_map: resolve::TraitMap,
 224     method_map: method_map,
 225     vtable_map: vtable_map,
 226     tcx: ty::ctxt
 227 }
 228
 229 // Functions that write types into the node type table
 230 pub fn write_ty_to_tcx(tcx: ty::ctxt, node_id: ast::NodeId, ty: ty::t) {
 231     debug!("write_ty_to_tcx({}, {})", node_id, ppaux::ty_to_str(tcx, ty));
 232     assert!(!ty::type_needs_infer(ty));
 233     let mut node_types = tcx.node_types.borrow_mut();
 234     node_types.get().insert(node_id as uint, ty);
 235 }
 236 pub fn write_substs_to_tcx(tcx: ty::ctxt,
 237                            node_id: ast::NodeId,
 238                            substs: ~[ty::t]) {
 239     if substs.len() > 0u {
 240         debug!("write_substs_to_tcx({}, {:?})", node_id,
 241                substs.map(|t| ppaux::ty_to_str(tcx, *t)));
 242         assert!(substs.iter().all(|t| !ty::type_needs_infer(*t)));
 243
 244         let mut node_type_substs = tcx.node_type_substs.borrow_mut();
 245         node_type_substs.get().insert(node_id, substs);
 246     }
 247 }
 248 pub fn write_tpt_to_tcx(tcx: ty::ctxt,
 249                         node_id: ast::NodeId,
 250                         tpt: &ty::ty_param_substs_and_ty) {
 251     write_ty_to_tcx(tcx, node_id, tpt.ty);
 252     if !tpt.substs.tps.is_empty() {
 253         write_substs_to_tcx(tcx, node_id, tpt.substs.tps.clone());
 254     }
 255 }
 256
 257 pub fn lookup_def_tcx(tcx: ty::ctxt, sp: Span, id: ast::NodeId) -> ast::Def {
 258     let def_map = tcx.def_map.borrow();
 259     match def_map.get().find(&id) {
 260         Some(&x) => x,
 261         _ => {
 262             tcx.sess.span_fatal(sp, "internal error looking up a definition")
 263         }
 264     }
 265 }
 266
 267 pub fn lookup_def_ccx(ccx: &CrateCtxt, sp: Span, id: ast::NodeId)
 268                    -> ast::Def {
 269     lookup_def_tcx(ccx.tcx, sp, id)
 270 }
 271
 272 pub fn no_params(t: ty::t) -> ty::ty_param_bounds_and_ty {
 273     ty::ty_param_bounds_and_ty {
 274         generics: ty::Generics {type_param_defs: Rc::new(~[]),
 275                                 region_param_defs: Rc::new(~[])},
 276         ty: t
 277     }
 278 }
 279
 280 pub fn require_same_types(tcx: ty::ctxt,
 281                           maybe_infcx: Option<&infer::InferCtxt>,
 282                           t1_is_expected: bool,
 283                           span: Span,
 284                           t1: ty::t,
 285                           t2: ty::t,
 286                           msg: || -> ~str)
 287                           -> bool {
 288     let result = match maybe_infcx {
 289         None => {
 290             let infcx = infer::new_infer_ctxt(tcx);
 291             infer::mk_eqty(&infcx, t1_is_expected, infer::Misc(span), t1, t2)
 292         }
 293         Some(infcx) => {
 294             infer::mk_eqty(infcx, t1_is_expected, infer::Misc(span), t1, t2)
 295         }
 296     };
 297
 298     match result {
 299         Ok(_) => true,
 300         Err(ref terr) => {
 301             tcx.sess.span_err(span, msg() + ": " +
 302                               ty::type_err_to_str(tcx, terr));
 303             ty::note_and_explain_type_err(tcx, terr);
 304             false
 305         }
 306     }
 307 }
 308
 309 // a list of mapping from in-scope-region-names ("isr") to the
 310 // corresponding ty::Region
 311 pub type isr_alist = @List<(ty::BoundRegion, ty::Region)>;
 312
 313 trait get_and_find_region {
 314     fn get(&self, br: ty::BoundRegion) -> ty::Region;
 315     fn find(&self, br: ty::BoundRegion) -> Option<ty::Region>;
 316 }
 317
 318 impl get_and_find_region for isr_alist {
 319     fn get(&self, br: ty::BoundRegion) -> ty::Region {
 320         self.find(br).unwrap()
 321     }
 322
 323     fn find(&self, br: ty::BoundRegion) -> Option<ty::Region> {
 324         let mut ret = None;
 325         list::each(*self, |isr| {
 326             let (isr_br, isr_r) = *isr;
 327             if isr_br == br { ret = Some(isr_r); false } else { true }
 328         });
 329         ret
 330     }
 331 }
 332
 333 fn check_main_fn_ty(ccx: &CrateCtxt,
 334                     main_id: ast::NodeId,
 335                     main_span: Span) {
 336     let tcx = ccx.tcx;
 337     let main_t = ty::node_id_to_type(tcx, main_id);
 338     match ty::get(main_t).sty {
 339         ty::ty_bare_fn(..) => {
 340             match tcx.map.find(main_id) {
 341                 Some(ast_map::NodeItem(it)) => {
 342                     match it.node {
 343                         ast::ItemFn(_, _, _, ref ps, _)
 344                         if ps.is_parameterized() => {
 345                             tcx.sess.span_err(
 346                                 main_span,
 347                                 "main function is not allowed to have type parameters");
 348                             return;
 349                         }
 350                         _ => ()
 351                     }
 352                 }
 353                 _ => ()
 354             }
 355             let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
 356                 purity: ast::ImpureFn,
 357                 abis: abi::AbiSet::Rust(),
 358                 sig: ty::FnSig {
 359                     binder_id: main_id,
 360                     inputs: ~[],
 361                     output: ty::mk_nil(),
 362                     variadic: false
 363                 }
 364             });
 365
 366             require_same_types(tcx, None, false, main_span, main_t, se_ty,
 367                 || format!("main function expects type: `{}`",
 368                         ppaux::ty_to_str(ccx.tcx, se_ty)));
 369         }
 370         _ => {
 371             tcx.sess.span_bug(main_span,
 372                               format!("main has a non-function type: found `{}`",
 373                                    ppaux::ty_to_str(tcx, main_t)));
 374         }
 375     }
 376 }
 377
 378 fn check_start_fn_ty(ccx: &CrateCtxt,
 379                      start_id: ast::NodeId,
 380                      start_span: Span) {
 381     let tcx = ccx.tcx;
 382     let start_t = ty::node_id_to_type(tcx, start_id);
 383     match ty::get(start_t).sty {
 384         ty::ty_bare_fn(_) => {
 385             match tcx.map.find(start_id) {
 386                 Some(ast_map::NodeItem(it)) => {
 387                     match it.node {
 388                         ast::ItemFn(_,_,_,ref ps,_)
 389                         if ps.is_parameterized() => {
 390                             tcx.sess.span_err(
 391                                 start_span,
 392                                 "start function is not allowed to have type parameters");
 393                             return;
 394                         }
 395                         _ => ()
 396                     }
 397                 }
 398                 _ => ()
 399             }
 400
 401             let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
 402                 purity: ast::ImpureFn,
 403                 abis: abi::AbiSet::Rust(),
 404                 sig: ty::FnSig {
 405                     binder_id: start_id,
 406                     inputs: ~[
 407                         ty::mk_int(),
 408                         ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, ty::mk_u8()))
 409                     ],
 410                     output: ty::mk_int(),
 411                     variadic: false
 412                 }
 413             });
 414
 415             require_same_types(tcx, None, false, start_span, start_t, se_ty,
 416                 || format!("start function expects type: `{}`", ppaux::ty_to_str(ccx.tcx, se_ty)));
 417
 418         }
 419         _ => {
 420             tcx.sess.span_bug(start_span,
 421                               format!("start has a non-function type: found `{}`",
 422                                    ppaux::ty_to_str(tcx, start_t)));
 423         }
 424     }
 425 }
 426
 427 fn check_for_entry_fn(ccx: &CrateCtxt) {
 428     let tcx = ccx.tcx;
 429     if !tcx.sess.building_library.get() {
 430         match tcx.sess.entry_fn.get() {
 431           Some((id, sp)) => match tcx.sess.entry_type.get() {
 432               Some(session::EntryMain) => check_main_fn_ty(ccx, id, sp),
 433               Some(session::EntryStart) => check_start_fn_ty(ccx, id, sp),
 434               Some(session::EntryNone) => {}
 435               None => tcx.sess.bug("entry function without a type")
 436           },
 437           None => {}
 438         }
 439     }
 440 }
 441
 442 pub fn check_crate(tcx: ty::ctxt,
 443                    trait_map: resolve::TraitMap,
 444                    krate: &ast::Crate)
 445                 -> (method_map, vtable_map) {
 446     let time_passes = tcx.sess.time_passes();
 447     let ccx = @CrateCtxt {
 448         trait_map: trait_map,
 449         method_map: @RefCell::new(HashMap::new()),
 450         vtable_map: @RefCell::new(HashMap::new()),
 451         tcx: tcx
 452     };
 453
 454     time(time_passes, "type collecting", (), |_|
 455         collect::collect_item_types(ccx, krate));
 456
 457     // this ensures that later parts of type checking can assume that items
 458     // have valid types and not error
 459     tcx.sess.abort_if_errors();
 460
 461     time(time_passes, "variance inference", (), |_|
 462          variance::infer_variance(tcx, krate));
 463
 464     time(time_passes, "coherence checking", (), |_|
 465         coherence::check_coherence(ccx, krate));
 466
 467     time(time_passes, "type checking", (), |_|
 468         check::check_item_types(ccx, krate));
 469
 470     check_for_entry_fn(ccx);
 471     tcx.sess.abort_if_errors();
 472     (ccx.method_map, ccx.vtable_map)
 473 }