1 // Copyright 2012-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 #[allow(non_camel_case_types)];
68 use util::common::time;
69 use util::ppaux::Repr;
72 use std::cell::RefCell;
73 use collections::HashMap;
75 use collections::List;
76 use collections::list;
77 use syntax::codemap::Span;
78 use syntax::print::pprust::*;
79 use syntax::{ast, ast_map, abi};
89 #[deriving(Clone, Encodable, Decodable, Eq, Ord)]
90 pub enum param_index {
95 #[deriving(Clone, Encodable, Decodable)]
96 pub enum MethodOrigin {
97 // fully statically resolved method
98 MethodStatic(ast::DefId),
100 // method invoked on a type parameter with a bounded trait
101 MethodParam(MethodParam),
103 // method invoked on a trait instance
104 MethodObject(MethodObject),
108 // details for a method invoked with a receiver whose type is a type parameter
109 // with a bounded trait.
110 #[deriving(Clone, Encodable, Decodable)]
111 pub struct MethodParam {
112 // the trait containing the method to be invoked
113 trait_id: ast::DefId,
115 // index of the method to be invoked amongst the trait's methods
118 // index of the type parameter (from those that are in scope) that is
119 // the type of the receiver
120 param_num: param_index,
122 // index of the bound for this type parameter which specifies the trait
126 // details for a method invoked with a receiver whose type is an object
127 #[deriving(Clone, Encodable, Decodable)]
128 pub struct MethodObject {
129 // the (super)trait containing the method to be invoked
130 trait_id: ast::DefId,
132 // the actual base trait id of the object
133 object_trait_id: ast::DefId,
135 // index of the method to be invoked amongst the trait's methods
138 // index into the actual runtime vtable.
139 // the vtable is formed by concatenating together the method lists of
140 // the base object trait and all supertraits; this is the index into
145 // maps from an expression id that corresponds to a method call to the details
146 // of the method to be invoked
147 pub type method_map = @RefCell<HashMap<ast::NodeId, method_origin>>;
149 pub type vtable_param_res = @~[vtable_origin];
150 // Resolutions for bounds of all parameters, left to right, for a given path.
151 pub type vtable_res = @~[vtable_param_res];
154 pub enum vtable_origin {
156 Statically known vtable. def_id gives the class or impl item
157 from whence comes the vtable, and tys are the type substs.
158 vtable_res is the vtable itself
160 vtable_static(ast::DefId, ~[ty::t], vtable_res),
163 Dynamic vtable, comes from a parameter that has a bound on it:
164 fn foo<T:quux,baz,bar>(a: T) -- a's vtable would have a
167 The first argument is the param index (identifying T in the example),
168 and the second is the bound number (identifying baz)
170 vtable_param(param_index, uint),
173 impl Repr for vtable_origin {
174 fn repr(&self, tcx: ty::ctxt) -> ~str {
176 vtable_static(def_id, ref tys, ref vtable_res) => {
177 format!("vtable_static({:?}:{}, {}, {})",
179 ty::item_path_str(tcx, def_id),
181 vtable_res.repr(tcx))
184 vtable_param(x, y) => {
185 format!("vtable_param({:?}, {:?})", x, y)
191 pub type vtable_map = @RefCell<HashMap<ast::NodeId, vtable_res>>;
194 // Information about the vtable resolutions for for a trait impl.
195 // Mostly the information is important for implementing default
198 pub struct impl_res {
199 // resolutions for any bounded params on the trait definition
200 trait_vtables: vtable_res,
201 // resolutions for the trait /itself/ (and for supertraits)
202 self_vtables: vtable_param_res
205 impl Repr for impl_res {
206 fn repr(&self, tcx: ty::ctxt) -> ~str {
207 format!("impl_res \\{trait_vtables={}, self_vtables={}\\}",
208 self.trait_vtables.repr(tcx),
209 self.self_vtables.repr(tcx))
213 pub type impl_vtable_map = RefCell<HashMap<ast::DefId, impl_res>>;
215 pub struct CrateCtxt {
216 // A mapping from method call sites to traits that have that method.
217 trait_map: resolve::TraitMap,
218 method_map: MethodMap,
219 vtable_map: vtable_map,
223 // Functions that write types into the node type table
224 pub fn write_ty_to_tcx(tcx: ty::ctxt, node_id: ast::NodeId, ty: ty::t) {
225 debug!("write_ty_to_tcx({}, {})", node_id, ppaux::ty_to_str(tcx, ty));
226 assert!(!ty::type_needs_infer(ty));
227 let mut node_types = tcx.node_types.borrow_mut();
228 node_types.get().insert(node_id as uint, ty);
230 pub fn write_substs_to_tcx(tcx: ty::ctxt,
231 node_id: ast::NodeId,
233 if substs.len() > 0u {
234 debug!("write_substs_to_tcx({}, {:?})", node_id,
235 substs.map(|t| ppaux::ty_to_str(tcx, *t)));
236 assert!(substs.iter().all(|t| !ty::type_needs_infer(*t)));
238 let mut node_type_substs = tcx.node_type_substs.borrow_mut();
239 node_type_substs.get().insert(node_id, substs);
242 pub fn write_tpt_to_tcx(tcx: ty::ctxt,
243 node_id: ast::NodeId,
244 tpt: &ty::ty_param_substs_and_ty) {
245 write_ty_to_tcx(tcx, node_id, tpt.ty);
246 if !tpt.substs.tps.is_empty() {
247 write_substs_to_tcx(tcx, node_id, tpt.substs.tps.clone());
251 pub fn lookup_def_tcx(tcx: ty::ctxt, sp: Span, id: ast::NodeId) -> ast::Def {
252 let def_map = tcx.def_map.borrow();
253 match def_map.get().find(&id) {
256 tcx.sess.span_fatal(sp, "internal error looking up a definition")
261 pub fn lookup_def_ccx(ccx: &CrateCtxt, sp: Span, id: ast::NodeId)
263 lookup_def_tcx(ccx.tcx, sp, id)
266 pub fn no_params(t: ty::t) -> ty::ty_param_bounds_and_ty {
267 ty::ty_param_bounds_and_ty {
268 generics: ty::Generics {type_param_defs: Rc::new(~[]),
269 region_param_defs: Rc::new(~[])},
274 pub fn require_same_types(tcx: ty::ctxt,
275 maybe_infcx: Option<&infer::InferCtxt>,
276 t1_is_expected: bool,
282 let result = match maybe_infcx {
284 let infcx = infer::new_infer_ctxt(tcx);
285 infer::mk_eqty(&infcx, t1_is_expected, infer::Misc(span), t1, t2)
288 infer::mk_eqty(infcx, t1_is_expected, infer::Misc(span), t1, t2)
295 tcx.sess.span_err(span, msg() + ": " +
296 ty::type_err_to_str(tcx, terr));
297 ty::note_and_explain_type_err(tcx, terr);
303 // a list of mapping from in-scope-region-names ("isr") to the
304 // corresponding ty::Region
305 pub type isr_alist = @List<(ty::BoundRegion, ty::Region)>;
307 trait get_and_find_region {
308 fn get(&self, br: ty::BoundRegion) -> ty::Region;
309 fn find(&self, br: ty::BoundRegion) -> Option<ty::Region>;
312 impl get_and_find_region for isr_alist {
313 fn get(&self, br: ty::BoundRegion) -> ty::Region {
314 self.find(br).unwrap()
317 fn find(&self, br: ty::BoundRegion) -> Option<ty::Region> {
319 list::each(*self, |isr| {
320 let (isr_br, isr_r) = *isr;
321 if isr_br == br { ret = Some(isr_r); false } else { true }
327 fn check_main_fn_ty(ccx: &CrateCtxt,
328 main_id: ast::NodeId,
331 let main_t = ty::node_id_to_type(tcx, main_id);
332 match ty::get(main_t).sty {
333 ty::ty_bare_fn(..) => {
334 match tcx.map.find(main_id) {
335 Some(ast_map::NodeItem(it)) => {
337 ast::ItemFn(_, _, _, ref ps, _)
338 if ps.is_parameterized() => {
341 "main function is not allowed to have type parameters");
349 let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
350 purity: ast::ImpureFn,
351 abis: abi::AbiSet::Rust(),
355 output: ty::mk_nil(),
360 require_same_types(tcx, None, false, main_span, main_t, se_ty,
361 || format!("main function expects type: `{}`",
362 ppaux::ty_to_str(ccx.tcx, se_ty)));
365 tcx.sess.span_bug(main_span,
366 format!("main has a non-function type: found `{}`",
367 ppaux::ty_to_str(tcx, main_t)));
372 fn check_start_fn_ty(ccx: &CrateCtxt,
373 start_id: ast::NodeId,
376 let start_t = ty::node_id_to_type(tcx, start_id);
377 match ty::get(start_t).sty {
378 ty::ty_bare_fn(_) => {
379 match tcx.map.find(start_id) {
380 Some(ast_map::NodeItem(it)) => {
382 ast::ItemFn(_,_,_,ref ps,_)
383 if ps.is_parameterized() => {
386 "start function is not allowed to have type parameters");
395 let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
396 purity: ast::ImpureFn,
397 abis: abi::AbiSet::Rust(),
402 ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, ty::mk_u8()))
404 output: ty::mk_int(),
409 require_same_types(tcx, None, false, start_span, start_t, se_ty,
410 || format!("start function expects type: `{}`", ppaux::ty_to_str(ccx.tcx, se_ty)));
414 tcx.sess.span_bug(start_span,
415 format!("start has a non-function type: found `{}`",
416 ppaux::ty_to_str(tcx, start_t)));
421 fn check_for_entry_fn(ccx: &CrateCtxt) {
423 if !tcx.sess.building_library.get() {
424 match tcx.sess.entry_fn.get() {
425 Some((id, sp)) => match tcx.sess.entry_type.get() {
426 Some(session::EntryMain) => check_main_fn_ty(ccx, id, sp),
427 Some(session::EntryStart) => check_start_fn_ty(ccx, id, sp),
428 Some(session::EntryNone) => {}
429 None => tcx.sess.bug("entry function without a type")
436 pub fn check_crate(tcx: ty::ctxt,
437 trait_map: resolve::TraitMap,
439 -> (MethodMap, vtable_map) {
440 let time_passes = tcx.sess.time_passes();
441 let ccx = @CrateCtxt {
442 trait_map: trait_map,
443 method_map: @RefCell::new(HashMap::new()),
444 vtable_map: @RefCell::new(HashMap::new()),
448 time(time_passes, "type collecting", (), |_|
449 collect::collect_item_types(ccx, krate));
451 // this ensures that later parts of type checking can assume that items
452 // have valid types and not error
453 tcx.sess.abort_if_errors();
455 time(time_passes, "variance inference", (), |_|
456 variance::infer_variance(tcx, krate));
458 time(time_passes, "coherence checking", (), |_|
459 coherence::check_coherence(ccx, krate));
461 time(time_passes, "type checking", (), |_|
462 check::check_item_types(ccx, krate));
464 check_for_entry_fn(ccx);
465 tcx.sess.abort_if_errors();
466 (ccx.method_map, ccx.vtable_map)