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.
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.
13 typeck.rs, an introduction
15 The type checker is responsible for:
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)
22 The main entry point is `check_crate()`. Type checking operates in
25 1. The collect phase first passes over all items and determines their
26 type, without examining their "innards".
28 2. Variance inference then runs to compute the variance of each parameter
30 3. Coherence checks for overlapping or orphaned impls
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.
40 The type checker is defined into various submodules which are documented
43 - astconv: converts the AST representation of types
44 into the `ty` representation
46 - collect: computes the types of each top-level item and enters them into
47 the `cx.tcache` table for later use
49 - coherence: enforces coherence rules, builds some tables
51 - variance: variance inference
53 - check: walks over function bodies and type checks them, inferring types for
54 local variables, type parameters, etc as necessary.
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.
62 This API is completely unstable and subject to change.
66 #![crate_name = "rustc_typeck"]
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/")]
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)]
80 #[phase(plugin, link)] extern crate log;
81 #[phase(plugin, link)] extern crate syntax;
87 pub use rustc::metadata;
88 pub use rustc::middle;
89 pub use rustc::session;
95 use middle::subst::VecPerParamSpace;
96 use middle::ty::{mod, Ty};
98 use util::common::time;
99 use util::ppaux::Repr;
102 use syntax::codemap::Span;
103 use syntax::print::pprust::*;
104 use syntax::{ast, ast_map, abi};
105 use syntax::ast_util::local_def;
114 struct TypeAndSubsts<'tcx> {
115 pub substs: subst::Substs<'tcx>,
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>
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);
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({}, {})",
138 item_substs.repr(tcx));
140 assert!(item_substs.substs.types.all(|t| !ty::type_needs_infer(*t)));
142 tcx.item_substs.borrow_mut().insert(node_id, item_substs);
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(),
149 tcx.sess.span_fatal(sp, "internal error looking up a definition")
154 fn lookup_def_ccx(ccx: &CrateCtxt, sp: Span, id: ast::NodeId)
156 lookup_def_tcx(ccx.tcx, sp, id)
159 fn no_params<'tcx>(t: Ty<'tcx>) -> ty::TypeScheme<'tcx> {
161 generics: ty::Generics {
162 types: VecPerParamSpace::empty(),
163 regions: VecPerParamSpace::empty(),
164 predicates: VecPerParamSpace::empty(),
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,
178 M: FnOnce() -> String,
180 let result = match maybe_infcx {
182 let infcx = infer::new_infer_ctxt(tcx);
183 infer::mk_eqty(&infcx, t1_is_expected, infer::Misc(span), t1, t2)
186 infer::mk_eqty(infcx, t1_is_expected, infer::Misc(span), t1, t2)
193 tcx.sess.span_err(span,
196 ty::type_err_to_str(tcx,
198 ty::note_and_explain_type_err(tcx, terr);
204 fn check_main_fn_ty(ccx: &CrateCtxt,
205 main_id: ast::NodeId,
208 let main_t = ty::node_id_to_type(tcx, main_id);
210 ty::ty_bare_fn(..) => {
211 match tcx.map.find(main_id) {
212 Some(ast_map::NodeItem(it)) => {
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");
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,
228 sig: ty::Binder(ty::FnSig {
230 output: ty::FnConverging(ty::mk_nil(tcx)),
235 require_same_types(tcx, None, false, main_span, main_t, se_ty,
237 format!("main function expects type: `{}`",
238 ppaux::ty_to_string(ccx.tcx, se_ty))
242 tcx.sess.span_bug(main_span,
243 format!("main has a non-function type: found \
245 ppaux::ty_to_string(tcx,
251 fn check_start_fn_ty(ccx: &CrateCtxt,
252 start_id: ast::NodeId,
255 let start_t = ty::node_id_to_type(tcx, start_id);
257 ty::ty_bare_fn(..) => {
258 match tcx.map.find(start_id) {
259 Some(ast_map::NodeItem(it)) => {
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");
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,
276 sig: ty::Binder(ty::FnSig {
279 ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, tcx.types.u8))
281 output: ty::FnConverging(tcx.types.int),
286 require_same_types(tcx, None, false, start_span, start_t, se_ty,
288 format!("start function expects type: `{}`",
289 ppaux::ty_to_string(ccx.tcx, se_ty))
294 tcx.sess.span_bug(start_span,
295 format!("start has a non-function type: found \
297 ppaux::ty_to_string(tcx, start_t))[]);
302 fn check_for_entry_fn(ccx: &CrateCtxt) {
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")
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,
322 time(time_passes, "type collecting", (), |_|
323 collect::collect_item_types(&ccx));
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();
329 time(time_passes, "variance inference", (), |_|
330 variance::infer_variance(tcx));
332 time(time_passes, "coherence checking", (), |_|
333 coherence::check_coherence(&ccx));
335 time(time_passes, "type checking", (), |_|
336 check::check_item_types(&ccx));
338 check_for_entry_fn(&ccx);
339 tcx.sess.abort_if_errors();