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"]
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/")]
75 #![allow(unknown_features)]
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)]
83 #[macro_use] extern crate log;
84 #[macro_use] extern crate syntax;
87 extern crate fmt_macros;
91 pub use rustc::metadata;
92 pub use rustc::middle;
93 pub use rustc::session;
99 use middle::subst::VecPerParamSpace;
100 use middle::ty::{self, Ty};
102 use util::common::time;
103 use util::ppaux::Repr;
106 use syntax::codemap::Span;
107 use syntax::print::pprust::*;
108 use syntax::{ast, ast_map, abi};
109 use syntax::ast_util::local_def;
118 struct TypeAndSubsts<'tcx> {
119 pub substs: subst::Substs<'tcx>,
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>,
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);
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({}, {})",
142 item_substs.repr(tcx));
144 assert!(item_substs.substs.types.all(|t| !ty::type_needs_infer(*t)));
146 tcx.item_substs.borrow_mut().insert(node_id, item_substs);
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(),
153 tcx.sess.span_fatal(sp, "internal error looking up a definition")
158 fn lookup_def_ccx(ccx: &CrateCtxt, sp: Span, id: ast::NodeId)
160 lookup_def_tcx(ccx.tcx, sp, id)
163 fn no_params<'tcx>(t: Ty<'tcx>) -> ty::TypeScheme<'tcx> {
165 generics: ty::Generics {
166 types: VecPerParamSpace::empty(),
167 regions: VecPerParamSpace::empty(),
168 predicates: VecPerParamSpace::empty(),
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,
182 M: FnOnce() -> String,
184 let result = match maybe_infcx {
186 let infcx = infer::new_infer_ctxt(tcx);
187 infer::mk_eqty(&infcx, t1_is_expected, infer::Misc(span), t1, t2)
190 infer::mk_eqty(infcx, t1_is_expected, infer::Misc(span), t1, t2)
197 tcx.sess.span_err(span,
200 ty::type_err_to_str(tcx,
202 ty::note_and_explain_type_err(tcx, terr);
208 fn check_main_fn_ty(ccx: &CrateCtxt,
209 main_id: ast::NodeId,
212 let main_t = ty::node_id_to_type(tcx, main_id);
214 ty::ty_bare_fn(..) => {
215 match tcx.map.find(main_id) {
216 Some(ast_map::NodeItem(it)) => {
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");
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,
232 sig: ty::Binder(ty::FnSig {
234 output: ty::FnConverging(ty::mk_nil(tcx)),
239 require_same_types(tcx, None, false, main_span, main_t, se_ty,
241 format!("main function expects type: `{}`",
242 ppaux::ty_to_string(ccx.tcx, se_ty))
246 tcx.sess.span_bug(main_span,
247 &format!("main has a non-function type: found \
249 ppaux::ty_to_string(tcx,
255 fn check_start_fn_ty(ccx: &CrateCtxt,
256 start_id: ast::NodeId,
259 let start_t = ty::node_id_to_type(tcx, start_id);
261 ty::ty_bare_fn(..) => {
262 match tcx.map.find(start_id) {
263 Some(ast_map::NodeItem(it)) => {
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");
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,
280 sig: ty::Binder(ty::FnSig {
283 ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, tcx.types.u8))
285 output: ty::FnConverging(tcx.types.int),
290 require_same_types(tcx, None, false, start_span, start_t, se_ty,
292 format!("start function expects type: `{}`",
293 ppaux::ty_to_string(ccx.tcx, se_ty))
298 tcx.sess.span_bug(start_span,
299 &format!("start has a non-function type: found \
301 ppaux::ty_to_string(tcx, start_t))[]);
306 fn check_for_entry_fn(ccx: &CrateCtxt) {
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")
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,
326 time(time_passes, "type collecting", (), |_|
327 collect::collect_item_types(tcx));
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();
333 time(time_passes, "variance inference", (), |_|
334 variance::infer_variance(tcx));
336 time(time_passes, "coherence checking", (), |_|
337 coherence::check_coherence(&ccx));
339 time(time_passes, "type checking", (), |_|
340 check::check_item_types(&ccx));
342 check_for_entry_fn(&ccx);
343 tcx.sess.abort_if_errors();