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::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};
  72
  73 use std::cell::RefCell;
  74 use std::rc::Rc;
  75 use syntax::codemap::Span;
  76 use syntax::print::pprust::*;
  77 use syntax::{ast, ast_map, abi};
  78
  79 pub mod check;
  80 pub mod rscope;
  81 pub mod astconv;
  82 pub mod infer;
  83 pub mod collect;
  84 pub mod coherence;
  85 pub mod variance;
  86
  87 #[deriving(Clone, Encodable, Decodable, Eq, Ord)]
  88 pub enum param_index {
  89     param_numbered(uint),
  90     param_self
  91 }
  92
  93 #[deriving(Clone, Encodable, Decodable)]
  94 pub enum MethodOrigin {
  95     // fully statically resolved method
  96     MethodStatic(ast::DefId),
  97
  98     // method invoked on a type parameter with a bounded trait
  99     MethodParam(MethodParam),
 100
 101     // method invoked on a trait instance
 102     MethodObject(MethodObject),
 103
 104 }
 105
 106 // details for a method invoked with a receiver whose type is a type parameter
 107 // with a bounded trait.
 108 #[deriving(Clone, Encodable, Decodable)]
 109 pub struct MethodParam {
 110     // the trait containing the method to be invoked
 111     pub trait_id: ast::DefId,
 112
 113     // index of the method to be invoked amongst the trait's methods
 114     pub method_num: uint,
 115
 116     // index of the type parameter (from those that are in scope) that is
 117     // the type of the receiver
 118     pub param_num: param_index,
 119
 120     // index of the bound for this type parameter which specifies the trait
 121     pub bound_num: uint,
 122 }
 123
 124 // details for a method invoked with a receiver whose type is an object
 125 #[deriving(Clone, Encodable, Decodable)]
 126 pub struct MethodObject {
 127     // the (super)trait containing the method to be invoked
 128     pub trait_id: ast::DefId,
 129
 130     // the actual base trait id of the object
 131     pub object_trait_id: ast::DefId,
 132
 133     // index of the method to be invoked amongst the trait's methods
 134     pub method_num: uint,
 135
 136     // index into the actual runtime vtable.
 137     // the vtable is formed by concatenating together the method lists of
 138     // the base object trait and all supertraits;  this is the index into
 139     // that vtable
 140     pub real_index: uint,
 141 }
 142
 143 #[deriving(Clone)]
 144 pub struct MethodCallee {
 145     pub origin: MethodOrigin,
 146     pub ty: ty::t,
 147     pub substs: ty::substs
 148 }
 149
 150 #[deriving(Clone, Eq, TotalEq, Hash, Show)]
 151 pub struct MethodCall {
 152     pub expr_id: ast::NodeId,
 153     pub autoderef: u32
 154 }
 155
 156 impl MethodCall {
 157     pub fn expr(id: ast::NodeId) -> MethodCall {
 158         MethodCall {
 159             expr_id: id,
 160             autoderef: 0
 161         }
 162     }
 163
 164     pub fn autoderef(expr_id: ast::NodeId, autoderef: u32) -> MethodCall {
 165         MethodCall {
 166             expr_id: expr_id,
 167             autoderef: 1 + autoderef
 168         }
 169     }
 170 }
 171
 172 // maps from an expression id that corresponds to a method call to the details
 173 // of the method to be invoked
 174 pub type MethodMap = RefCell<FnvHashMap<MethodCall, MethodCallee>>;
 175
 176 pub type vtable_param_res = Vec<vtable_origin>;
 177 // Resolutions for bounds of all parameters, left to right, for a given path.
 178 pub type vtable_res = Vec<vtable_param_res>;
 179
 180 #[deriving(Clone)]
 181 pub enum vtable_origin {
 182     /*
 183       Statically known vtable. def_id gives the class or impl item
 184       from whence comes the vtable, and tys are the type substs.
 185       vtable_res is the vtable itself
 186      */
 187     vtable_static(ast::DefId, ty::substs, vtable_res),
 188
 189     /*
 190       Dynamic vtable, comes from a parameter that has a bound on it:
 191       fn foo<T:quux,baz,bar>(a: T) -- a's vtable would have a
 192       vtable_param origin
 193
 194       The first argument is the param index (identifying T in the example),
 195       and the second is the bound number (identifying baz)
 196      */
 197     vtable_param(param_index, uint),
 198 }
 199
 200 impl Repr for vtable_origin {
 201     fn repr(&self, tcx: &ty::ctxt) -> String {
 202         match *self {
 203             vtable_static(def_id, ref tys, ref vtable_res) => {
 204                 format_strbuf!("vtable_static({:?}:{}, {}, {})",
 205                                def_id,
 206                                ty::item_path_str(tcx, def_id),
 207                                tys.repr(tcx),
 208                                vtable_res.repr(tcx))
 209             }
 210
 211             vtable_param(x, y) => {
 212                 format_strbuf!("vtable_param({:?}, {:?})", x, y)
 213             }
 214         }
 215     }
 216 }
 217
 218 pub type vtable_map = RefCell<FnvHashMap<MethodCall, vtable_res>>;
 219
 220
 221 // Information about the vtable resolutions for a trait impl.
 222 // Mostly the information is important for implementing default
 223 // methods.
 224 #[deriving(Clone)]
 225 pub struct impl_res {
 226     // resolutions for any bounded params on the trait definition
 227     pub trait_vtables: vtable_res,
 228     // resolutions for the trait /itself/ (and for supertraits)
 229     pub self_vtables: vtable_param_res
 230 }
 231
 232 impl Repr for impl_res {
 233     fn repr(&self, tcx: &ty::ctxt) -> String {
 234         format_strbuf!("impl_res \\{trait_vtables={}, self_vtables={}\\}",
 235                        self.trait_vtables.repr(tcx),
 236                        self.self_vtables.repr(tcx))
 237     }
 238 }
 239
 240 pub type impl_vtable_map = RefCell<DefIdMap<impl_res>>;
 241
 242 pub struct CrateCtxt<'a> {
 243     // A mapping from method call sites to traits that have that method.
 244     trait_map: resolve::TraitMap,
 245     tcx: &'a ty::ctxt
 246 }
 247
 248 // Functions that write types into the node type table
 249 pub fn write_ty_to_tcx(tcx: &ty::ctxt, node_id: ast::NodeId, ty: ty::t) {
 250     debug!("write_ty_to_tcx({}, {})", node_id, ppaux::ty_to_str(tcx, ty));
 251     assert!(!ty::type_needs_infer(ty));
 252     tcx.node_types.borrow_mut().insert(node_id as uint, ty);
 253 }
 254 pub fn write_substs_to_tcx(tcx: &ty::ctxt,
 255                            node_id: ast::NodeId,
 256                            item_substs: ty::ItemSubsts) {
 257     if !item_substs.is_noop() {
 258         debug!("write_substs_to_tcx({}, {})",
 259                node_id,
 260                item_substs.repr(tcx));
 261
 262         assert!(item_substs.substs.tps.iter().
 263                 all(|t| !ty::type_needs_infer(*t)));
 264
 265         tcx.item_substs.borrow_mut().insert(node_id, item_substs);
 266     }
 267 }
 268 pub fn lookup_def_tcx(tcx:&ty::ctxt, sp: Span, id: ast::NodeId) -> ast::Def {
 269     match tcx.def_map.borrow().find(&id) {
 270         Some(&x) => x,
 271         _ => {
 272             tcx.sess.span_fatal(sp, "internal error looking up a definition")
 273         }
 274     }
 275 }
 276
 277 pub fn lookup_def_ccx(ccx: &CrateCtxt, sp: Span, id: ast::NodeId)
 278                    -> ast::Def {
 279     lookup_def_tcx(ccx.tcx, sp, id)
 280 }
 281
 282 pub fn no_params(t: ty::t) -> ty::ty_param_bounds_and_ty {
 283     ty::ty_param_bounds_and_ty {
 284         generics: ty::Generics {type_param_defs: Rc::new(Vec::new()),
 285                                 region_param_defs: Rc::new(Vec::new())},
 286         ty: t
 287     }
 288 }
 289
 290 pub fn require_same_types(tcx: &ty::ctxt,
 291                           maybe_infcx: Option<&infer::InferCtxt>,
 292                           t1_is_expected: bool,
 293                           span: Span,
 294                           t1: ty::t,
 295                           t2: ty::t,
 296                           msg: || -> String)
 297                           -> bool {
 298     let result = match maybe_infcx {
 299         None => {
 300             let infcx = infer::new_infer_ctxt(tcx);
 301             infer::mk_eqty(&infcx, t1_is_expected, infer::Misc(span), t1, t2)
 302         }
 303         Some(infcx) => {
 304             infer::mk_eqty(infcx, t1_is_expected, infer::Misc(span), t1, t2)
 305         }
 306     };
 307
 308     match result {
 309         Ok(_) => true,
 310         Err(ref terr) => {
 311             tcx.sess.span_err(span,
 312                               format!("{}: {}",
 313                                       msg(),
 314                                       ty::type_err_to_str(tcx,
 315                                                           terr)).as_slice());
 316             ty::note_and_explain_type_err(tcx, terr);
 317             false
 318         }
 319     }
 320 }
 321
 322 fn check_main_fn_ty(ccx: &CrateCtxt,
 323                     main_id: ast::NodeId,
 324                     main_span: Span) {
 325     let tcx = ccx.tcx;
 326     let main_t = ty::node_id_to_type(tcx, main_id);
 327     match ty::get(main_t).sty {
 328         ty::ty_bare_fn(..) => {
 329             match tcx.map.find(main_id) {
 330                 Some(ast_map::NodeItem(it)) => {
 331                     match it.node {
 332                         ast::ItemFn(_, _, _, ref ps, _)
 333                         if ps.is_parameterized() => {
 334                             tcx.sess.span_err(
 335                                 main_span,
 336                                 "main function is not allowed to have type parameters");
 337                             return;
 338                         }
 339                         _ => ()
 340                     }
 341                 }
 342                 _ => ()
 343             }
 344             let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
 345                 fn_style: ast::NormalFn,
 346                 abi: abi::Rust,
 347                 sig: ty::FnSig {
 348                     binder_id: main_id,
 349                     inputs: Vec::new(),
 350                     output: ty::mk_nil(),
 351                     variadic: false
 352                 }
 353             });
 354
 355             require_same_types(tcx, None, false, main_span, main_t, se_ty,
 356                 || {
 357                     format_strbuf!("main function expects type: `{}`",
 358                                    ppaux::ty_to_str(ccx.tcx, se_ty))
 359                 });
 360         }
 361         _ => {
 362             tcx.sess.span_bug(main_span,
 363                               format!("main has a non-function type: found \
 364                                        `{}`",
 365                                       ppaux::ty_to_str(tcx,
 366                                                        main_t)).as_slice());
 367         }
 368     }
 369 }
 370
 371 fn check_start_fn_ty(ccx: &CrateCtxt,
 372                      start_id: ast::NodeId,
 373                      start_span: Span) {
 374     let tcx = ccx.tcx;
 375     let start_t = ty::node_id_to_type(tcx, start_id);
 376     match ty::get(start_t).sty {
 377         ty::ty_bare_fn(_) => {
 378             match tcx.map.find(start_id) {
 379                 Some(ast_map::NodeItem(it)) => {
 380                     match it.node {
 381                         ast::ItemFn(_,_,_,ref ps,_)
 382                         if ps.is_parameterized() => {
 383                             tcx.sess.span_err(
 384                                 start_span,
 385                                 "start function is not allowed to have type parameters");
 386                             return;
 387                         }
 388                         _ => ()
 389                     }
 390                 }
 391                 _ => ()
 392             }
 393
 394             let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
 395                 fn_style: ast::NormalFn,
 396                 abi: abi::Rust,
 397                 sig: ty::FnSig {
 398                     binder_id: start_id,
 399                     inputs: vec!(
 400                         ty::mk_int(),
 401                         ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, ty::mk_u8()))
 402                     ),
 403                     output: ty::mk_int(),
 404                     variadic: false
 405                 }
 406             });
 407
 408             require_same_types(tcx, None, false, start_span, start_t, se_ty,
 409                 || {
 410                     format_strbuf!("start function expects type: `{}`",
 411                                    ppaux::ty_to_str(ccx.tcx, se_ty))
 412                 });
 413
 414         }
 415         _ => {
 416             tcx.sess.span_bug(start_span,
 417                               format!("start has a non-function type: found \
 418                                        `{}`",
 419                                       ppaux::ty_to_str(tcx,
 420                                                        start_t)).as_slice());
 421         }
 422     }
 423 }
 424
 425 fn check_for_entry_fn(ccx: &CrateCtxt) {
 426     let tcx = ccx.tcx;
 427     match *tcx.sess.entry_fn.borrow() {
 428         Some((id, sp)) => match tcx.sess.entry_type.get() {
 429             Some(config::EntryMain) => check_main_fn_ty(ccx, id, sp),
 430             Some(config::EntryStart) => check_start_fn_ty(ccx, id, sp),
 431             Some(config::EntryNone) => {}
 432             None => tcx.sess.bug("entry function without a type")
 433         },
 434         None => {}
 435     }
 436 }
 437
 438 pub fn check_crate(tcx: &ty::ctxt,
 439                    trait_map: resolve::TraitMap,
 440                    krate: &ast::Crate) {
 441     let time_passes = tcx.sess.time_passes();
 442     let ccx = CrateCtxt {
 443         trait_map: trait_map,
 444         tcx: tcx
 445     };
 446
 447     time(time_passes, "type collecting", (), |_|
 448         collect::collect_item_types(&ccx, krate));
 449
 450     // this ensures that later parts of type checking can assume that items
 451     // have valid types and not error
 452     tcx.sess.abort_if_errors();
 453
 454     time(time_passes, "variance inference", (), |_|
 455          variance::infer_variance(tcx, krate));
 456
 457     time(time_passes, "coherence checking", (), |_|
 458         coherence::check_coherence(&ccx, krate));
 459
 460     time(time_passes, "type checking", (), |_|
 461         check::check_item_types(&ccx, krate));
 462
 463     check_for_entry_fn(&ccx);
 464     tcx.sess.abort_if_errors();
 465 }