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::config;
  65
  66 use middle::def;
  67 use middle::resolve;
  68 use middle::subst;
  69 use middle::subst::VecPerParamSpace;
  70 use middle::ty;
  71 use util::common::time;
  72 use util::ppaux::Repr;
  73 use util::ppaux;
  74 use util::nodemap::{DefIdMap, FnvHashMap};
  75
  76 use std::cell::RefCell;
  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, PartialEq, PartialOrd)]
  90 pub struct param_index {
  91     pub space: subst::ParamSpace,
  92     pub index: uint
  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     pub trait_id: ast::DefId,
 114
 115     // index of the method to be invoked amongst the trait's methods
 116     pub 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     pub param_num: param_index,
 121
 122     // index of the bound for this type parameter which specifies the trait
 123     pub 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     pub trait_id: ast::DefId,
 131
 132     // the actual base trait id of the object
 133     pub object_trait_id: ast::DefId,
 134
 135     // index of the method to be invoked amongst the trait's methods
 136     pub 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     pub real_index: uint,
 143 }
 144
 145 #[deriving(Clone)]
 146 pub struct MethodCallee {
 147     pub origin: MethodOrigin,
 148     pub ty: ty::t,
 149     pub substs: subst::Substs
 150 }
 151
 152 /**
 153  * With method calls, we store some extra information in
 154  * side tables (i.e method_map, vtable_map). We use
 155  * MethodCall as a key to index into these tables instead of
 156  * just directly using the expression's NodeId. The reason
 157  * for this being that we may apply adjustments (coercions)
 158  * with the resulting expression also needing to use the
 159  * side tables. The problem with this is that we don't
 160  * assign a separate NodeId to this new expression
 161  * and so it would clash with the base expression if both
 162  * needed to add to the side tables. Thus to disambiguate
 163  * we also keep track of whether there's an adjustment in
 164  * our key.
 165  */
 166 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
 167 pub struct MethodCall {
 168     pub expr_id: ast::NodeId,
 169     pub adjustment: ExprAdjustment
 170 }
 171
 172 #[deriving(Clone, PartialEq, Eq, Hash, Show, Encodable, Decodable)]
 173 pub enum ExprAdjustment {
 174     NoAdjustment,
 175     AutoDeref(uint),
 176     AutoObject
 177 }
 178
 179 impl MethodCall {
 180     pub fn expr(id: ast::NodeId) -> MethodCall {
 181         MethodCall {
 182             expr_id: id,
 183             adjustment: NoAdjustment
 184         }
 185     }
 186
 187     pub fn autoobject(id: ast::NodeId) -> MethodCall {
 188         MethodCall {
 189             expr_id: id,
 190             adjustment: AutoObject
 191         }
 192     }
 193
 194     pub fn autoderef(expr_id: ast::NodeId, autoderef: uint) -> MethodCall {
 195         MethodCall {
 196             expr_id: expr_id,
 197             adjustment: AutoDeref(1 + autoderef)
 198         }
 199     }
 200 }
 201
 202 // maps from an expression id that corresponds to a method call to the details
 203 // of the method to be invoked
 204 pub type MethodMap = RefCell<FnvHashMap<MethodCall, MethodCallee>>;
 205
 206 pub type vtable_param_res = Vec<vtable_origin>;
 207
 208 // Resolutions for bounds of all parameters, left to right, for a given path.
 209 pub type vtable_res = VecPerParamSpace<vtable_param_res>;
 210
 211 #[deriving(Clone)]
 212 pub enum vtable_origin {
 213     /*
 214       Statically known vtable. def_id gives the class or impl item
 215       from whence comes the vtable, and tys are the type substs.
 216       vtable_res is the vtable itself
 217      */
 218     vtable_static(ast::DefId, subst::Substs, vtable_res),
 219
 220     /*
 221       Dynamic vtable, comes from a parameter that has a bound on it:
 222       fn foo<T:quux,baz,bar>(a: T) -- a's vtable would have a
 223       vtable_param origin
 224
 225       The first argument is the param index (identifying T in the example),
 226       and the second is the bound number (identifying baz)
 227      */
 228     vtable_param(param_index, uint),
 229
 230     /*
 231       Asked to determine the vtable for ty_err. This is the value used
 232       for the vtables of `Self` in a virtual call like `foo.bar()`
 233       where `foo` is of object type. The same value is also used when
 234       type errors occur.
 235      */
 236     vtable_error,
 237 }
 238
 239 impl Repr for vtable_origin {
 240     fn repr(&self, tcx: &ty::ctxt) -> String {
 241         match *self {
 242             vtable_static(def_id, ref tys, ref vtable_res) => {
 243                 format!("vtable_static({:?}:{}, {}, {})",
 244                         def_id,
 245                         ty::item_path_str(tcx, def_id),
 246                         tys.repr(tcx),
 247                         vtable_res.repr(tcx))
 248             }
 249
 250             vtable_param(x, y) => {
 251                 format!("vtable_param({:?}, {:?})", x, y)
 252             }
 253
 254             vtable_error => {
 255                 format!("vtable_error")
 256             }
 257         }
 258     }
 259 }
 260
 261 pub type vtable_map = RefCell<FnvHashMap<MethodCall, vtable_res>>;
 262
 263
 264 pub type impl_vtable_map = RefCell<DefIdMap<vtable_res>>;
 265
 266 pub struct CrateCtxt<'a> {
 267     // A mapping from method call sites to traits that have that method.
 268     trait_map: resolve::TraitMap,
 269     tcx: &'a ty::ctxt
 270 }
 271
 272 // Functions that write types into the node type table
 273 pub fn write_ty_to_tcx(tcx: &ty::ctxt, node_id: ast::NodeId, ty: ty::t) {
 274     debug!("write_ty_to_tcx({}, {})", node_id, ppaux::ty_to_str(tcx, ty));
 275     assert!(!ty::type_needs_infer(ty));
 276     tcx.node_types.borrow_mut().insert(node_id as uint, ty);
 277 }
 278 pub fn write_substs_to_tcx(tcx: &ty::ctxt,
 279                            node_id: ast::NodeId,
 280                            item_substs: ty::ItemSubsts) {
 281     if !item_substs.is_noop() {
 282         debug!("write_substs_to_tcx({}, {})",
 283                node_id,
 284                item_substs.repr(tcx));
 285
 286         assert!(item_substs.substs.types.all(|t| !ty::type_needs_infer(*t)));
 287
 288         tcx.item_substs.borrow_mut().insert(node_id, item_substs);
 289     }
 290 }
 291 pub fn lookup_def_tcx(tcx:&ty::ctxt, sp: Span, id: ast::NodeId) -> def::Def {
 292     match tcx.def_map.borrow().find(&id) {
 293         Some(&x) => x,
 294         _ => {
 295             tcx.sess.span_fatal(sp, "internal error looking up a definition")
 296         }
 297     }
 298 }
 299
 300 pub fn lookup_def_ccx(ccx: &CrateCtxt, sp: Span, id: ast::NodeId)
 301                    -> def::Def {
 302     lookup_def_tcx(ccx.tcx, sp, id)
 303 }
 304
 305 pub fn no_params(t: ty::t) -> ty::ty_param_bounds_and_ty {
 306     ty::ty_param_bounds_and_ty {
 307         generics: ty::Generics {types: VecPerParamSpace::empty(),
 308                                 regions: VecPerParamSpace::empty()},
 309         ty: t
 310     }
 311 }
 312
 313 pub fn require_same_types(tcx: &ty::ctxt,
 314                           maybe_infcx: Option<&infer::InferCtxt>,
 315                           t1_is_expected: bool,
 316                           span: Span,
 317                           t1: ty::t,
 318                           t2: ty::t,
 319                           msg: || -> String)
 320                           -> bool {
 321     let result = match maybe_infcx {
 322         None => {
 323             let infcx = infer::new_infer_ctxt(tcx);
 324             infer::mk_eqty(&infcx, t1_is_expected, infer::Misc(span), t1, t2)
 325         }
 326         Some(infcx) => {
 327             infer::mk_eqty(infcx, t1_is_expected, infer::Misc(span), t1, t2)
 328         }
 329     };
 330
 331     match result {
 332         Ok(_) => true,
 333         Err(ref terr) => {
 334             tcx.sess.span_err(span,
 335                               format!("{}: {}",
 336                                       msg(),
 337                                       ty::type_err_to_str(tcx,
 338                                                           terr)).as_slice());
 339             ty::note_and_explain_type_err(tcx, terr);
 340             false
 341         }
 342     }
 343 }
 344
 345 fn check_main_fn_ty(ccx: &CrateCtxt,
 346                     main_id: ast::NodeId,
 347                     main_span: Span) {
 348     let tcx = ccx.tcx;
 349     let main_t = ty::node_id_to_type(tcx, main_id);
 350     match ty::get(main_t).sty {
 351         ty::ty_bare_fn(..) => {
 352             match tcx.map.find(main_id) {
 353                 Some(ast_map::NodeItem(it)) => {
 354                     match it.node {
 355                         ast::ItemFn(_, _, _, ref ps, _)
 356                         if ps.is_parameterized() => {
 357                             tcx.sess.span_err(
 358                                 main_span,
 359                                 "main function is not allowed to have type parameters");
 360                             return;
 361                         }
 362                         _ => ()
 363                     }
 364                 }
 365                 _ => ()
 366             }
 367             let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
 368                 fn_style: ast::NormalFn,
 369                 abi: abi::Rust,
 370                 sig: ty::FnSig {
 371                     binder_id: main_id,
 372                     inputs: Vec::new(),
 373                     output: ty::mk_nil(),
 374                     variadic: false
 375                 }
 376             });
 377
 378             require_same_types(tcx, None, false, main_span, main_t, se_ty,
 379                 || {
 380                     format!("main function expects type: `{}`",
 381                             ppaux::ty_to_str(ccx.tcx, se_ty))
 382                 });
 383         }
 384         _ => {
 385             tcx.sess.span_bug(main_span,
 386                               format!("main has a non-function type: found \
 387                                        `{}`",
 388                                       ppaux::ty_to_str(tcx,
 389                                                        main_t)).as_slice());
 390         }
 391     }
 392 }
 393
 394 fn check_start_fn_ty(ccx: &CrateCtxt,
 395                      start_id: ast::NodeId,
 396                      start_span: Span) {
 397     let tcx = ccx.tcx;
 398     let start_t = ty::node_id_to_type(tcx, start_id);
 399     match ty::get(start_t).sty {
 400         ty::ty_bare_fn(_) => {
 401             match tcx.map.find(start_id) {
 402                 Some(ast_map::NodeItem(it)) => {
 403                     match it.node {
 404                         ast::ItemFn(_,_,_,ref ps,_)
 405                         if ps.is_parameterized() => {
 406                             tcx.sess.span_err(
 407                                 start_span,
 408                                 "start function is not allowed to have type parameters");
 409                             return;
 410                         }
 411                         _ => ()
 412                     }
 413                 }
 414                 _ => ()
 415             }
 416
 417             let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
 418                 fn_style: ast::NormalFn,
 419                 abi: abi::Rust,
 420                 sig: ty::FnSig {
 421                     binder_id: start_id,
 422                     inputs: vec!(
 423                         ty::mk_int(),
 424                         ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, ty::mk_u8()))
 425                     ),
 426                     output: ty::mk_int(),
 427                     variadic: false
 428                 }
 429             });
 430
 431             require_same_types(tcx, None, false, start_span, start_t, se_ty,
 432                 || {
 433                     format!("start function expects type: `{}`",
 434                             ppaux::ty_to_str(ccx.tcx, se_ty))
 435                 });
 436
 437         }
 438         _ => {
 439             tcx.sess.span_bug(start_span,
 440                               format!("start has a non-function type: found \
 441                                        `{}`",
 442                                       ppaux::ty_to_str(tcx,
 443                                                        start_t)).as_slice());
 444         }
 445     }
 446 }
 447
 448 fn check_for_entry_fn(ccx: &CrateCtxt) {
 449     let tcx = ccx.tcx;
 450     match *tcx.sess.entry_fn.borrow() {
 451         Some((id, sp)) => match tcx.sess.entry_type.get() {
 452             Some(config::EntryMain) => check_main_fn_ty(ccx, id, sp),
 453             Some(config::EntryStart) => check_start_fn_ty(ccx, id, sp),
 454             Some(config::EntryNone) => {}
 455             None => tcx.sess.bug("entry function without a type")
 456         },
 457         None => {}
 458     }
 459 }
 460
 461 pub fn check_crate(tcx: &ty::ctxt,
 462                    trait_map: resolve::TraitMap,
 463                    krate: &ast::Crate) {
 464     let time_passes = tcx.sess.time_passes();
 465     let ccx = CrateCtxt {
 466         trait_map: trait_map,
 467         tcx: tcx
 468     };
 469
 470     time(time_passes, "type collecting", (), |_|
 471         collect::collect_item_types(&ccx, krate));
 472
 473     // this ensures that later parts of type checking can assume that items
 474     // have valid types and not error
 475     tcx.sess.abort_if_errors();
 476
 477     time(time_passes, "variance inference", (), |_|
 478          variance::infer_variance(tcx, krate));
 479
 480     time(time_passes, "coherence checking", (), |_|
 481         coherence::check_coherence(&ccx, krate));
 482
 483     time(time_passes, "type checking", (), |_|
 484         check::check_item_types(&ccx, krate));
 485
 486     check_for_entry_fn(&ccx);
 487     tcx.sess.abort_if_errors();
 488 }