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