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