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 pub struct TypeAndSubsts {
 180     pub substs: subst::Substs,
 181     pub ty: ty::t,
 182 }
 183
 184 impl MethodCall {
 185     pub fn expr(id: ast::NodeId) -> MethodCall {
 186         MethodCall {
 187             expr_id: id,
 188             adjustment: NoAdjustment
 189         }
 190     }
 191
 192     pub fn autoobject(id: ast::NodeId) -> MethodCall {
 193         MethodCall {
 194             expr_id: id,
 195             adjustment: AutoObject
 196         }
 197     }
 198
 199     pub fn autoderef(expr_id: ast::NodeId, autoderef: uint) -> MethodCall {
 200         MethodCall {
 201             expr_id: expr_id,
 202             adjustment: AutoDeref(1 + autoderef)
 203         }
 204     }
 205 }
 206
 207 // maps from an expression id that corresponds to a method call to the details
 208 // of the method to be invoked
 209 pub type MethodMap = RefCell<FnvHashMap<MethodCall, MethodCallee>>;
 210
 211 pub type vtable_param_res = Vec<vtable_origin>;
 212
 213 // Resolutions for bounds of all parameters, left to right, for a given path.
 214 pub type vtable_res = VecPerParamSpace<vtable_param_res>;
 215
 216 #[deriving(Clone)]
 217 pub enum vtable_origin {
 218     /*
 219       Statically known vtable. def_id gives the class or impl item
 220       from whence comes the vtable, and tys are the type substs.
 221       vtable_res is the vtable itself
 222      */
 223     vtable_static(ast::DefId, subst::Substs, vtable_res),
 224
 225     /*
 226       Dynamic vtable, comes from a parameter that has a bound on it:
 227       fn foo<T:quux,baz,bar>(a: T) -- a's vtable would have a
 228       vtable_param origin
 229
 230       The first argument is the param index (identifying T in the example),
 231       and the second is the bound number (identifying baz)
 232      */
 233     vtable_param(param_index, uint),
 234
 235     /*
 236       Asked to determine the vtable for ty_err. This is the value used
 237       for the vtables of `Self` in a virtual call like `foo.bar()`
 238       where `foo` is of object type. The same value is also used when
 239       type errors occur.
 240      */
 241     vtable_error,
 242 }
 243
 244 impl Repr for vtable_origin {
 245     fn repr(&self, tcx: &ty::ctxt) -> String {
 246         match *self {
 247             vtable_static(def_id, ref tys, ref vtable_res) => {
 248                 format!("vtable_static({:?}:{}, {}, {})",
 249                         def_id,
 250                         ty::item_path_str(tcx, def_id),
 251                         tys.repr(tcx),
 252                         vtable_res.repr(tcx))
 253             }
 254
 255             vtable_param(x, y) => {
 256                 format!("vtable_param({:?}, {:?})", x, y)
 257             }
 258
 259             vtable_error => {
 260                 format!("vtable_error")
 261             }
 262         }
 263     }
 264 }
 265
 266 pub type vtable_map = RefCell<FnvHashMap<MethodCall, vtable_res>>;
 267
 268
 269 pub type impl_vtable_map = RefCell<DefIdMap<vtable_res>>;
 270
 271 pub struct CrateCtxt<'a> {
 272     // A mapping from method call sites to traits that have that method.
 273     trait_map: resolve::TraitMap,
 274     tcx: &'a ty::ctxt
 275 }
 276
 277 // Functions that write types into the node type table
 278 pub fn write_ty_to_tcx(tcx: &ty::ctxt, node_id: ast::NodeId, ty: ty::t) {
 279     debug!("write_ty_to_tcx({}, {})", node_id, ppaux::ty_to_str(tcx, ty));
 280     assert!(!ty::type_needs_infer(ty));
 281     tcx.node_types.borrow_mut().insert(node_id as uint, ty);
 282 }
 283 pub fn write_substs_to_tcx(tcx: &ty::ctxt,
 284                            node_id: ast::NodeId,
 285                            item_substs: ty::ItemSubsts) {
 286     if !item_substs.is_noop() {
 287         debug!("write_substs_to_tcx({}, {})",
 288                node_id,
 289                item_substs.repr(tcx));
 290
 291         assert!(item_substs.substs.types.all(|t| !ty::type_needs_infer(*t)));
 292
 293         tcx.item_substs.borrow_mut().insert(node_id, item_substs);
 294     }
 295 }
 296 pub fn lookup_def_tcx(tcx:&ty::ctxt, sp: Span, id: ast::NodeId) -> def::Def {
 297     match tcx.def_map.borrow().find(&id) {
 298         Some(&x) => x,
 299         _ => {
 300             tcx.sess.span_fatal(sp, "internal error looking up a definition")
 301         }
 302     }
 303 }
 304
 305 pub fn lookup_def_ccx(ccx: &CrateCtxt, sp: Span, id: ast::NodeId)
 306                    -> def::Def {
 307     lookup_def_tcx(ccx.tcx, sp, id)
 308 }
 309
 310 pub fn no_params(t: ty::t) -> ty::Polytype {
 311     ty::Polytype {
 312         generics: ty::Generics {types: VecPerParamSpace::empty(),
 313                                 regions: VecPerParamSpace::empty()},
 314         ty: t
 315     }
 316 }
 317
 318 pub fn require_same_types(tcx: &ty::ctxt,
 319                           maybe_infcx: Option<&infer::InferCtxt>,
 320                           t1_is_expected: bool,
 321                           span: Span,
 322                           t1: ty::t,
 323                           t2: ty::t,
 324                           msg: || -> String)
 325                           -> bool {
 326     let result = match maybe_infcx {
 327         None => {
 328             let infcx = infer::new_infer_ctxt(tcx);
 329             infer::mk_eqty(&infcx, t1_is_expected, infer::Misc(span), t1, t2)
 330         }
 331         Some(infcx) => {
 332             infer::mk_eqty(infcx, t1_is_expected, infer::Misc(span), t1, t2)
 333         }
 334     };
 335
 336     match result {
 337         Ok(_) => true,
 338         Err(ref terr) => {
 339             tcx.sess.span_err(span,
 340                               format!("{}: {}",
 341                                       msg(),
 342                                       ty::type_err_to_str(tcx,
 343                                                           terr)).as_slice());
 344             ty::note_and_explain_type_err(tcx, terr);
 345             false
 346         }
 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                 fn_style: ast::NormalFn,
 374                 abi: abi::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                 || {
 385                     format!("main function expects type: `{}`",
 386                             ppaux::ty_to_str(ccx.tcx, se_ty))
 387                 });
 388         }
 389         _ => {
 390             tcx.sess.span_bug(main_span,
 391                               format!("main has a non-function type: found \
 392                                        `{}`",
 393                                       ppaux::ty_to_str(tcx,
 394                                                        main_t)).as_slice());
 395         }
 396     }
 397 }
 398
 399 fn check_start_fn_ty(ccx: &CrateCtxt,
 400                      start_id: ast::NodeId,
 401                      start_span: Span) {
 402     let tcx = ccx.tcx;
 403     let start_t = ty::node_id_to_type(tcx, start_id);
 404     match ty::get(start_t).sty {
 405         ty::ty_bare_fn(_) => {
 406             match tcx.map.find(start_id) {
 407                 Some(ast_map::NodeItem(it)) => {
 408                     match it.node {
 409                         ast::ItemFn(_,_,_,ref ps,_)
 410                         if ps.is_parameterized() => {
 411                             tcx.sess.span_err(
 412                                 start_span,
 413                                 "start function is not allowed to have type parameters");
 414                             return;
 415                         }
 416                         _ => ()
 417                     }
 418                 }
 419                 _ => ()
 420             }
 421
 422             let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
 423                 fn_style: ast::NormalFn,
 424                 abi: abi::Rust,
 425                 sig: ty::FnSig {
 426                     binder_id: start_id,
 427                     inputs: vec!(
 428                         ty::mk_int(),
 429                         ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, ty::mk_u8()))
 430                     ),
 431                     output: ty::mk_int(),
 432                     variadic: false
 433                 }
 434             });
 435
 436             require_same_types(tcx, None, false, start_span, start_t, se_ty,
 437                 || {
 438                     format!("start function expects type: `{}`",
 439                             ppaux::ty_to_str(ccx.tcx, se_ty))
 440                 });
 441
 442         }
 443         _ => {
 444             tcx.sess.span_bug(start_span,
 445                               format!("start has a non-function type: found \
 446                                        `{}`",
 447                                       ppaux::ty_to_str(tcx,
 448                                                        start_t)).as_slice());
 449         }
 450     }
 451 }
 452
 453 fn check_for_entry_fn(ccx: &CrateCtxt) {
 454     let tcx = ccx.tcx;
 455     match *tcx.sess.entry_fn.borrow() {
 456         Some((id, sp)) => match tcx.sess.entry_type.get() {
 457             Some(config::EntryMain) => check_main_fn_ty(ccx, id, sp),
 458             Some(config::EntryStart) => check_start_fn_ty(ccx, id, sp),
 459             Some(config::EntryNone) => {}
 460             None => tcx.sess.bug("entry function without a type")
 461         },
 462         None => {}
 463     }
 464 }
 465
 466 pub fn check_crate(tcx: &ty::ctxt,
 467                    trait_map: resolve::TraitMap,
 468                    krate: &ast::Crate) {
 469     let time_passes = tcx.sess.time_passes();
 470     let ccx = CrateCtxt {
 471         trait_map: trait_map,
 472         tcx: tcx
 473     };
 474
 475     time(time_passes, "type collecting", (), |_|
 476         collect::collect_item_types(&ccx, krate));
 477
 478     // this ensures that later parts of type checking can assume that items
 479     // have valid types and not error
 480     tcx.sess.abort_if_errors();
 481
 482     time(time_passes, "variance inference", (), |_|
 483          variance::infer_variance(tcx, krate));
 484
 485     time(time_passes, "coherence checking", (), |_|
 486         coherence::check_coherence(&ccx, krate));
 487
 488     time(time_passes, "type checking", (), |_|
 489         check::check_item_types(&ccx, krate));
 490
 491     check_for_entry_fn(&ccx);
 492     tcx.sess.abort_if_errors();
 493 }