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