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