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