1 // Copyright 2012 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.
67 use util::common::time;
68 use util::ppaux::Repr;
71 use std::cell::RefCell;
72 use std::hashmap::HashMap;
74 use collections::List;
75 use collections::list;
76 use syntax::codemap::Span;
77 use syntax::print::pprust::*;
78 use syntax::{ast, ast_map, abi};
88 #[deriving(Clone, Encodable, Decodable, Eq, Ord)]
89 pub enum param_index {
94 #[deriving(Clone, Encodable, Decodable)]
95 pub enum method_origin {
96 // fully statically resolved method
97 method_static(ast::DefId),
99 // method invoked on a type parameter with a bounded trait
100 method_param(method_param),
102 // method invoked on a trait instance
103 method_object(method_object),
107 // details for a method invoked with a receiver whose type is a type parameter
108 // with a bounded trait.
109 #[deriving(Clone, Encodable, Decodable)]
110 pub struct method_param {
111 // the trait containing the method to be invoked
112 trait_id: ast::DefId,
114 // index of the method to be invoked amongst the trait's methods
117 // index of the type parameter (from those that are in scope) that is
118 // the type of the receiver
119 param_num: param_index,
121 // index of the bound for this type parameter which specifies the trait
125 // details for a method invoked with a receiver whose type is an object
126 #[deriving(Clone, Encodable, Decodable)]
127 pub struct method_object {
128 // the (super)trait containing the method to be invoked
129 trait_id: ast::DefId,
131 // the actual base trait id of the object
132 object_trait_id: ast::DefId,
134 // index of the method to be invoked amongst the trait's methods
137 // index into the actual runtime vtable.
138 // the vtable is formed by concatenating together the method lists of
139 // the base object trait and all supertraits; this is the index into
144 // maps from an expression id that corresponds to a method call to the details
145 // of the method to be invoked
146 pub type method_map = @RefCell<HashMap<ast::NodeId, method_origin>>;
148 pub type vtable_param_res = @~[vtable_origin];
149 // Resolutions for bounds of all parameters, left to right, for a given path.
150 pub type vtable_res = @~[vtable_param_res];
153 pub enum vtable_origin {
155 Statically known vtable. def_id gives the class or impl item
156 from whence comes the vtable, and tys are the type substs.
157 vtable_res is the vtable itself
159 vtable_static(ast::DefId, ~[ty::t], vtable_res),
162 Dynamic vtable, comes from a parameter that has a bound on it:
163 fn foo<T:quux,baz,bar>(a: T) -- a's vtable would have a
166 The first argument is the param index (identifying T in the example),
167 and the second is the bound number (identifying baz)
169 vtable_param(param_index, uint),
172 impl Repr for vtable_origin {
173 fn repr(&self, tcx: ty::ctxt) -> ~str {
175 vtable_static(def_id, ref tys, ref vtable_res) => {
176 format!("vtable_static({:?}:{}, {}, {})",
178 ty::item_path_str(tcx, def_id),
180 vtable_res.repr(tcx))
183 vtable_param(x, y) => {
184 format!("vtable_param({:?}, {:?})", x, y)
190 pub type vtable_map = @RefCell<HashMap<ast::NodeId, vtable_res>>;
193 // Information about the vtable resolutions for for a trait impl.
194 // Mostly the information is important for implementing default
197 pub struct impl_res {
198 // resolutions for any bounded params on the trait definition
199 trait_vtables: vtable_res,
200 // resolutions for the trait /itself/ (and for supertraits)
201 self_vtables: vtable_param_res
204 impl Repr for impl_res {
205 fn repr(&self, tcx: ty::ctxt) -> ~str {
206 format!("impl_res \\{trait_vtables={}, self_vtables={}\\}",
207 self.trait_vtables.repr(tcx),
208 self.self_vtables.repr(tcx))
212 pub type impl_vtable_map = RefCell<HashMap<ast::DefId, impl_res>>;
214 pub struct CrateCtxt {
215 // A mapping from method call sites to traits that have that method.
216 trait_map: resolve::TraitMap,
217 method_map: method_map,
218 vtable_map: vtable_map,
222 // Functions that write types into the node type table
223 pub fn write_ty_to_tcx(tcx: ty::ctxt, node_id: ast::NodeId, ty: ty::t) {
224 debug!("write_ty_to_tcx({}, {})", node_id, ppaux::ty_to_str(tcx, ty));
225 assert!(!ty::type_needs_infer(ty));
226 let mut node_types = tcx.node_types.borrow_mut();
227 node_types.get().insert(node_id as uint, ty);
229 pub fn write_substs_to_tcx(tcx: ty::ctxt,
230 node_id: ast::NodeId,
232 if substs.len() > 0u {
233 debug!("write_substs_to_tcx({}, {:?})", node_id,
234 substs.map(|t| ppaux::ty_to_str(tcx, *t)));
235 assert!(substs.iter().all(|t| !ty::type_needs_infer(*t)));
237 let mut node_type_substs = tcx.node_type_substs.borrow_mut();
238 node_type_substs.get().insert(node_id, substs);
241 pub fn write_tpt_to_tcx(tcx: ty::ctxt,
242 node_id: ast::NodeId,
243 tpt: &ty::ty_param_substs_and_ty) {
244 write_ty_to_tcx(tcx, node_id, tpt.ty);
245 if !tpt.substs.tps.is_empty() {
246 write_substs_to_tcx(tcx, node_id, tpt.substs.tps.clone());
250 pub fn lookup_def_tcx(tcx: ty::ctxt, sp: Span, id: ast::NodeId) -> ast::Def {
251 let def_map = tcx.def_map.borrow();
252 match def_map.get().find(&id) {
255 tcx.sess.span_fatal(sp, "internal error looking up a definition")
260 pub fn lookup_def_ccx(ccx: &CrateCtxt, sp: Span, id: ast::NodeId)
262 lookup_def_tcx(ccx.tcx, sp, id)
265 pub fn no_params(t: ty::t) -> ty::ty_param_bounds_and_ty {
266 ty::ty_param_bounds_and_ty {
267 generics: ty::Generics {type_param_defs: Rc::new(~[]),
268 region_param_defs: Rc::new(~[])},
273 pub fn require_same_types(tcx: ty::ctxt,
274 maybe_infcx: Option<&infer::InferCtxt>,
275 t1_is_expected: bool,
281 let result = match maybe_infcx {
283 let infcx = infer::new_infer_ctxt(tcx);
284 infer::mk_eqty(&infcx, t1_is_expected, infer::Misc(span), t1, t2)
287 infer::mk_eqty(infcx, t1_is_expected, infer::Misc(span), t1, t2)
294 tcx.sess.span_err(span, msg() + ": " +
295 ty::type_err_to_str(tcx, terr));
296 ty::note_and_explain_type_err(tcx, terr);
302 // a list of mapping from in-scope-region-names ("isr") to the
303 // corresponding ty::Region
304 pub type isr_alist = @List<(ty::BoundRegion, ty::Region)>;
306 trait get_and_find_region {
307 fn get(&self, br: ty::BoundRegion) -> ty::Region;
308 fn find(&self, br: ty::BoundRegion) -> Option<ty::Region>;
311 impl get_and_find_region for isr_alist {
312 fn get(&self, br: ty::BoundRegion) -> ty::Region {
313 self.find(br).unwrap()
316 fn find(&self, br: ty::BoundRegion) -> Option<ty::Region> {
318 list::each(*self, |isr| {
319 let (isr_br, isr_r) = *isr;
320 if isr_br == br { ret = Some(isr_r); false } else { true }
326 fn check_main_fn_ty(ccx: &CrateCtxt,
327 main_id: ast::NodeId,
330 let main_t = ty::node_id_to_type(tcx, main_id);
331 match ty::get(main_t).sty {
332 ty::ty_bare_fn(..) => {
333 match tcx.map.find(main_id) {
334 Some(ast_map::NodeItem(it)) => {
336 ast::ItemFn(_, _, _, ref ps, _)
337 if ps.is_parameterized() => {
340 "main function is not allowed to have type parameters");
348 let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
349 purity: ast::ImpureFn,
350 abis: abi::AbiSet::Rust(),
354 output: ty::mk_nil(),
359 require_same_types(tcx, None, false, main_span, main_t, se_ty,
360 || format!("main function expects type: `{}`",
361 ppaux::ty_to_str(ccx.tcx, se_ty)));
364 tcx.sess.span_bug(main_span,
365 format!("main has a non-function type: found `{}`",
366 ppaux::ty_to_str(tcx, main_t)));
371 fn check_start_fn_ty(ccx: &CrateCtxt,
372 start_id: ast::NodeId,
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)) => {
381 ast::ItemFn(_,_,_,ref ps,_)
382 if ps.is_parameterized() => {
385 "start function is not allowed to have type parameters");
394 let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
395 purity: ast::ImpureFn,
396 abis: abi::AbiSet::Rust(),
401 ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, ty::mk_u8()))
403 output: ty::mk_int(),
408 require_same_types(tcx, None, false, start_span, start_t, se_ty,
409 || format!("start function expects type: `{}`", ppaux::ty_to_str(ccx.tcx, se_ty)));
413 tcx.sess.span_bug(start_span,
414 format!("start has a non-function type: found `{}`",
415 ppaux::ty_to_str(tcx, start_t)));
420 fn check_for_entry_fn(ccx: &CrateCtxt) {
422 if !tcx.sess.building_library.get() {
423 match tcx.sess.entry_fn.get() {
424 Some((id, sp)) => match tcx.sess.entry_type.get() {
425 Some(session::EntryMain) => check_main_fn_ty(ccx, id, sp),
426 Some(session::EntryStart) => check_start_fn_ty(ccx, id, sp),
427 Some(session::EntryNone) => {}
428 None => tcx.sess.bug("entry function without a type")
435 pub fn check_crate(tcx: ty::ctxt,
436 trait_map: resolve::TraitMap,
438 -> (method_map, vtable_map) {
439 let time_passes = tcx.sess.time_passes();
440 let ccx = @CrateCtxt {
441 trait_map: trait_map,
442 method_map: @RefCell::new(HashMap::new()),
443 vtable_map: @RefCell::new(HashMap::new()),
447 time(time_passes, "type collecting", (), |_|
448 collect::collect_item_types(ccx, krate));
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();
454 time(time_passes, "variance inference", (), |_|
455 variance::infer_variance(tcx, krate));
457 time(time_passes, "coherence checking", (), |_|
458 coherence::check_coherence(ccx, krate));
460 time(time_passes, "type checking", (), |_|
461 check::check_item_types(ccx, krate));
463 check_for_entry_fn(ccx);
464 tcx.sess.abort_if_errors();
465 (ccx.method_map, ccx.vtable_map)