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