src/librustc_typeck/lib.rs

   1 // Copyright 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 # Note
  61
  62 This API is completely unstable and subject to change.
  63
  64 */
  65
  66 #![crate_name = "rustc_typeck"]
  67 #![experimental]
  68 #![crate_type = "dylib"]
  69 #![crate_type = "rlib"]
  70 #![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
  71       html_favicon_url = "http://www.rust-lang.org/favicon.ico",
  72       html_root_url = "http://doc.rust-lang.org/nightly/")]
  73
  74 #![feature(default_type_params, globs, macro_rules, phase, quote)]
  75 #![feature(slicing_syntax, unsafe_destructor)]
  76 #![feature(rustc_diagnostic_macros)]
  77 #![feature(unboxed_closures)]
  78 #![allow(non_camel_case_types)]
  79
  80 #[phase(plugin, link)] extern crate log;
  81 #[phase(plugin, link)] extern crate syntax;
  82
  83 extern crate arena;
  84 extern crate rustc;
  85
  86 pub use rustc::lint;
  87 pub use rustc::metadata;
  88 pub use rustc::middle;
  89 pub use rustc::session;
  90 pub use rustc::util;
  91
  92 use middle::def;
  93 use middle::infer;
  94 use middle::subst;
  95 use middle::subst::VecPerParamSpace;
  96 use middle::ty::{self, Ty};
  97 use session::config;
  98 use util::common::time;
  99 use util::ppaux::Repr;
 100 use util::ppaux;
 101
 102 use syntax::codemap::Span;
 103 use syntax::print::pprust::*;
 104 use syntax::{ast, ast_map, abi};
 105 use syntax::ast_util::local_def;
 106
 107 mod check;
 108 mod rscope;
 109 mod astconv;
 110 mod collect;
 111 mod coherence;
 112 mod variance;
 113
 114 struct TypeAndSubsts<'tcx> {
 115     pub substs: subst::Substs<'tcx>,
 116     pub ty: Ty<'tcx>,
 117 }
 118
 119 struct CrateCtxt<'a, 'tcx: 'a> {
 120     // A mapping from method call sites to traits that have that method.
 121     trait_map: ty::TraitMap,
 122     tcx: &'a ty::ctxt<'tcx>
 123 }
 124
 125 // Functions that write types into the node type table
 126 fn write_ty_to_tcx<'tcx>(tcx: &ty::ctxt<'tcx>, node_id: ast::NodeId, ty: Ty<'tcx>) {
 127     debug!("write_ty_to_tcx({}, {})", node_id, ppaux::ty_to_string(tcx, ty));
 128     assert!(!ty::type_needs_infer(ty));
 129     tcx.node_types.borrow_mut().insert(node_id, ty);
 130 }
 131
 132 fn write_substs_to_tcx<'tcx>(tcx: &ty::ctxt<'tcx>,
 133                                  node_id: ast::NodeId,
 134                                  item_substs: ty::ItemSubsts<'tcx>) {
 135     if !item_substs.is_noop() {
 136         debug!("write_substs_to_tcx({}, {})",
 137                node_id,
 138                item_substs.repr(tcx));
 139
 140         assert!(item_substs.substs.types.all(|t| !ty::type_needs_infer(*t)));
 141
 142         tcx.item_substs.borrow_mut().insert(node_id, item_substs);
 143     }
 144 }
 145 fn lookup_def_tcx(tcx:&ty::ctxt, sp: Span, id: ast::NodeId) -> def::Def {
 146     match tcx.def_map.borrow().get(&id) {
 147         Some(x) => x.clone(),
 148         _ => {
 149             tcx.sess.span_fatal(sp, "internal error looking up a definition")
 150         }
 151     }
 152 }
 153
 154 fn lookup_def_ccx(ccx: &CrateCtxt, sp: Span, id: ast::NodeId)
 155                    -> def::Def {
 156     lookup_def_tcx(ccx.tcx, sp, id)
 157 }
 158
 159 fn no_params<'tcx>(t: Ty<'tcx>) -> ty::TypeScheme<'tcx> {
 160     ty::TypeScheme {
 161         generics: ty::Generics {
 162             types: VecPerParamSpace::empty(),
 163             regions: VecPerParamSpace::empty(),
 164             predicates: VecPerParamSpace::empty(),
 165         },
 166         ty: t
 167     }
 168 }
 169
 170 fn require_same_types<'a, 'tcx, M>(tcx: &ty::ctxt<'tcx>,
 171                                    maybe_infcx: Option<&infer::InferCtxt<'a, 'tcx>>,
 172                                    t1_is_expected: bool,
 173                                    span: Span,
 174                                    t1: Ty<'tcx>,
 175                                    t2: Ty<'tcx>,
 176                                    msg: M)
 177                                    -> bool where
 178     M: FnOnce() -> String,
 179 {
 180     let result = match maybe_infcx {
 181         None => {
 182             let infcx = infer::new_infer_ctxt(tcx);
 183             infer::mk_eqty(&infcx, t1_is_expected, infer::Misc(span), t1, t2)
 184         }
 185         Some(infcx) => {
 186             infer::mk_eqty(infcx, t1_is_expected, infer::Misc(span), t1, t2)
 187         }
 188     };
 189
 190     match result {
 191         Ok(_) => true,
 192         Err(ref terr) => {
 193             tcx.sess.span_err(span,
 194                               format!("{}: {}",
 195                                       msg(),
 196                                       ty::type_err_to_str(tcx,
 197                                                           terr))[]);
 198             ty::note_and_explain_type_err(tcx, terr);
 199             false
 200         }
 201     }
 202 }
 203
 204 fn check_main_fn_ty(ccx: &CrateCtxt,
 205                     main_id: ast::NodeId,
 206                     main_span: Span) {
 207     let tcx = ccx.tcx;
 208     let main_t = ty::node_id_to_type(tcx, main_id);
 209     match main_t.sty {
 210         ty::ty_bare_fn(..) => {
 211             match tcx.map.find(main_id) {
 212                 Some(ast_map::NodeItem(it)) => {
 213                     match it.node {
 214                         ast::ItemFn(_, _, _, ref ps, _)
 215                         if ps.is_parameterized() => {
 216                             span_err!(ccx.tcx.sess, main_span, E0131,
 217                                       "main function is not allowed to have type parameters");
 218                             return;
 219                         }
 220                         _ => ()
 221                     }
 222                 }
 223                 _ => ()
 224             }
 225             let se_ty = ty::mk_bare_fn(tcx, Some(local_def(main_id)), tcx.mk_bare_fn(ty::BareFnTy {
 226                 unsafety: ast::Unsafety::Normal,
 227                 abi: abi::Rust,
 228                 sig: ty::Binder(ty::FnSig {
 229                     inputs: Vec::new(),
 230                     output: ty::FnConverging(ty::mk_nil(tcx)),
 231                     variadic: false
 232                 })
 233             }));
 234
 235             require_same_types(tcx, None, false, main_span, main_t, se_ty,
 236                 || {
 237                     format!("main function expects type: `{}`",
 238                             ppaux::ty_to_string(ccx.tcx, se_ty))
 239                 });
 240         }
 241         _ => {
 242             tcx.sess.span_bug(main_span,
 243                               format!("main has a non-function type: found \
 244                                        `{}`",
 245                                       ppaux::ty_to_string(tcx,
 246                                                        main_t))[]);
 247         }
 248     }
 249 }
 250
 251 fn check_start_fn_ty(ccx: &CrateCtxt,
 252                      start_id: ast::NodeId,
 253                      start_span: Span) {
 254     let tcx = ccx.tcx;
 255     let start_t = ty::node_id_to_type(tcx, start_id);
 256     match start_t.sty {
 257         ty::ty_bare_fn(..) => {
 258             match tcx.map.find(start_id) {
 259                 Some(ast_map::NodeItem(it)) => {
 260                     match it.node {
 261                         ast::ItemFn(_,_,_,ref ps,_)
 262                         if ps.is_parameterized() => {
 263                             span_err!(tcx.sess, start_span, E0132,
 264                                       "start function is not allowed to have type parameters");
 265                             return;
 266                         }
 267                         _ => ()
 268                     }
 269                 }
 270                 _ => ()
 271             }
 272
 273             let se_ty = ty::mk_bare_fn(tcx, Some(local_def(start_id)), tcx.mk_bare_fn(ty::BareFnTy {
 274                 unsafety: ast::Unsafety::Normal,
 275                 abi: abi::Rust,
 276                 sig: ty::Binder(ty::FnSig {
 277                     inputs: vec!(
 278                         tcx.types.int,
 279                         ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, tcx.types.u8))
 280                     ),
 281                     output: ty::FnConverging(tcx.types.int),
 282                     variadic: false,
 283                 }),
 284             }));
 285
 286             require_same_types(tcx, None, false, start_span, start_t, se_ty,
 287                 || {
 288                     format!("start function expects type: `{}`",
 289                             ppaux::ty_to_string(ccx.tcx, se_ty))
 290                 });
 291
 292         }
 293         _ => {
 294             tcx.sess.span_bug(start_span,
 295                               format!("start has a non-function type: found \
 296                                        `{}`",
 297                                       ppaux::ty_to_string(tcx, start_t))[]);
 298         }
 299     }
 300 }
 301
 302 fn check_for_entry_fn(ccx: &CrateCtxt) {
 303     let tcx = ccx.tcx;
 304     match *tcx.sess.entry_fn.borrow() {
 305         Some((id, sp)) => match tcx.sess.entry_type.get() {
 306             Some(config::EntryMain) => check_main_fn_ty(ccx, id, sp),
 307             Some(config::EntryStart) => check_start_fn_ty(ccx, id, sp),
 308             Some(config::EntryNone) => {}
 309             None => tcx.sess.bug("entry function without a type")
 310         },
 311         None => {}
 312     }
 313 }
 314
 315 pub fn check_crate(tcx: &ty::ctxt, trait_map: ty::TraitMap) {
 316     let time_passes = tcx.sess.time_passes();
 317     let ccx = CrateCtxt {
 318         trait_map: trait_map,
 319         tcx: tcx
 320     };
 321
 322     time(time_passes, "type collecting", (), |_|
 323         collect::collect_item_types(&ccx));
 324
 325     // this ensures that later parts of type checking can assume that items
 326     // have valid types and not error
 327     tcx.sess.abort_if_errors();
 328
 329     time(time_passes, "variance inference", (), |_|
 330          variance::infer_variance(tcx));
 331
 332     time(time_passes, "coherence checking", (), |_|
 333         coherence::check_coherence(&ccx));
 334
 335     time(time_passes, "type checking", (), |_|
 336         check::check_item_types(&ccx));
 337
 338     check_for_entry_fn(&ccx);
 339     tcx.sess.abort_if_errors();
 340 }