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