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
  72 use std::cell::RefCell;
  73 use collections::HashMap;
  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 // maps from an expression id that corresponds to a method call to the details
 152 // of the method to be invoked
 153 pub type MethodMap = @RefCell<HashMap<ast::NodeId, MethodCallee>>;
 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 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: MethodMap,
 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_region<'a, T:'static> {
 314     fn get(&'a self, br: ty::BoundRegion) -> ty::Region;
 315 }
 316
 317 impl<'a, T:'static> get_region <'a, T> for isr_alist {
 318     fn get(&'a self, br: ty::BoundRegion) -> ty::Region {
 319         let mut region = None;
 320         for isr in self.iter() {
 321             let (isr_br, isr_r) = *isr;
 322             if isr_br == br { region = Some(isr_r); break; }
 323         };
 324         region.unwrap()
 325     }
 326 }
 327
 328 fn check_main_fn_ty(ccx: &CrateCtxt,
 329                     main_id: ast::NodeId,
 330                     main_span: Span) {
 331     let tcx = ccx.tcx;
 332     let main_t = ty::node_id_to_type(tcx, main_id);
 333     match ty::get(main_t).sty {
 334         ty::ty_bare_fn(..) => {
 335             match tcx.map.find(main_id) {
 336                 Some(ast_map::NodeItem(it)) => {
 337                     match it.node {
 338                         ast::ItemFn(_, _, _, ref ps, _)
 339                         if ps.is_parameterized() => {
 340                             tcx.sess.span_err(
 341                                 main_span,
 342                                 "main function is not allowed to have type parameters");
 343                             return;
 344                         }
 345                         _ => ()
 346                     }
 347                 }
 348                 _ => ()
 349             }
 350             let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
 351                 purity: ast::ImpureFn,
 352                 abis: abi::AbiSet::Rust(),
 353                 sig: ty::FnSig {
 354                     binder_id: main_id,
 355                     inputs: ~[],
 356                     output: ty::mk_nil(),
 357                     variadic: false
 358                 }
 359             });
 360
 361             require_same_types(tcx, None, false, main_span, main_t, se_ty,
 362                 || format!("main function expects type: `{}`",
 363                         ppaux::ty_to_str(ccx.tcx, se_ty)));
 364         }
 365         _ => {
 366             tcx.sess.span_bug(main_span,
 367                               format!("main has a non-function type: found `{}`",
 368                                    ppaux::ty_to_str(tcx, main_t)));
 369         }
 370     }
 371 }
 372
 373 fn check_start_fn_ty(ccx: &CrateCtxt,
 374                      start_id: ast::NodeId,
 375                      start_span: Span) {
 376     let tcx = ccx.tcx;
 377     let start_t = ty::node_id_to_type(tcx, start_id);
 378     match ty::get(start_t).sty {
 379         ty::ty_bare_fn(_) => {
 380             match tcx.map.find(start_id) {
 381                 Some(ast_map::NodeItem(it)) => {
 382                     match it.node {
 383                         ast::ItemFn(_,_,_,ref ps,_)
 384                         if ps.is_parameterized() => {
 385                             tcx.sess.span_err(
 386                                 start_span,
 387                                 "start function is not allowed to have type parameters");
 388                             return;
 389                         }
 390                         _ => ()
 391                     }
 392                 }
 393                 _ => ()
 394             }
 395
 396             let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
 397                 purity: ast::ImpureFn,
 398                 abis: abi::AbiSet::Rust(),
 399                 sig: ty::FnSig {
 400                     binder_id: start_id,
 401                     inputs: ~[
 402                         ty::mk_int(),
 403                         ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, ty::mk_u8()))
 404                     ],
 405                     output: ty::mk_int(),
 406                     variadic: false
 407                 }
 408             });
 409
 410             require_same_types(tcx, None, false, start_span, start_t, se_ty,
 411                 || format!("start function expects type: `{}`", ppaux::ty_to_str(ccx.tcx, se_ty)));
 412
 413         }
 414         _ => {
 415             tcx.sess.span_bug(start_span,
 416                               format!("start has a non-function type: found `{}`",
 417                                    ppaux::ty_to_str(tcx, start_t)));
 418         }
 419     }
 420 }
 421
 422 fn check_for_entry_fn(ccx: &CrateCtxt) {
 423     let tcx = ccx.tcx;
 424     if !tcx.sess.building_library.get() {
 425         match tcx.sess.entry_fn.get() {
 426           Some((id, sp)) => match tcx.sess.entry_type.get() {
 427               Some(session::EntryMain) => check_main_fn_ty(ccx, id, sp),
 428               Some(session::EntryStart) => check_start_fn_ty(ccx, id, sp),
 429               Some(session::EntryNone) => {}
 430               None => tcx.sess.bug("entry function without a type")
 431           },
 432           None => {}
 433         }
 434     }
 435 }
 436
 437 pub fn check_crate(tcx: ty::ctxt,
 438                    trait_map: resolve::TraitMap,
 439                    krate: &ast::Crate)
 440                 -> (MethodMap, vtable_map) {
 441     let time_passes = tcx.sess.time_passes();
 442     let ccx = @CrateCtxt {
 443         trait_map: trait_map,
 444         method_map: @RefCell::new(HashMap::new()),
 445         vtable_map: @RefCell::new(HashMap::new()),
 446         tcx: tcx
 447     };
 448
 449     time(time_passes, "type collecting", (), |_|
 450         collect::collect_item_types(ccx, krate));
 451
 452     // this ensures that later parts of type checking can assume that items
 453     // have valid types and not error
 454     tcx.sess.abort_if_errors();
 455
 456     time(time_passes, "variance inference", (), |_|
 457          variance::infer_variance(tcx, krate));
 458
 459     time(time_passes, "coherence checking", (), |_|
 460         coherence::check_coherence(ccx, krate));
 461
 462     time(time_passes, "type checking", (), |_|
 463         check::check_item_types(ccx, krate));
 464
 465     check_for_entry_fn(ccx);
 466     tcx.sess.abort_if_errors();
 467     (ccx.method_map, ccx.vtable_map)
 468 }