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;
71 use util::nodemap::{DefIdMap, NodeMap};
73 use std::cell::RefCell;
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 MethodOrigin {
96 // fully statically resolved method
97 MethodStatic(ast::DefId),
99 // method invoked on a type parameter with a bounded trait
100 MethodParam(MethodParam),
102 // method invoked on a trait instance
103 MethodObject(MethodObject),
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 MethodParam {
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 MethodObject {
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
145 pub struct MethodCallee {
146 origin: MethodOrigin,
151 // maps from an expression id that corresponds to a method call to the details
152 // of the method to be invoked
153 pub type MethodMap = @RefCell<NodeMap<MethodCallee>>;
155 pub type vtable_param_res = @~[vtable_origin];
156 // Resolutions for bounds of all parameters, left to right, for a given path.
157 pub type vtable_res = @~[vtable_param_res];
160 pub enum vtable_origin {
162 Statically known vtable. def_id gives the class or impl item
163 from whence comes the vtable, and tys are the type substs.
164 vtable_res is the vtable itself
166 vtable_static(ast::DefId, ~[ty::t], vtable_res),
169 Dynamic vtable, comes from a parameter that has a bound on it:
170 fn foo<T:quux,baz,bar>(a: T) -- a's vtable would have a
173 The first argument is the param index (identifying T in the example),
174 and the second is the bound number (identifying baz)
176 vtable_param(param_index, uint),
179 impl Repr for vtable_origin {
180 fn repr(&self, tcx: ty::ctxt) -> ~str {
182 vtable_static(def_id, ref tys, ref vtable_res) => {
183 format!("vtable_static({:?}:{}, {}, {})",
185 ty::item_path_str(tcx, def_id),
187 vtable_res.repr(tcx))
190 vtable_param(x, y) => {
191 format!("vtable_param({:?}, {:?})", x, y)
197 pub type vtable_map = @RefCell<NodeMap<vtable_res>>;
200 // Information about the vtable resolutions for a trait impl.
201 // Mostly the information is important for implementing default
204 pub struct impl_res {
205 // resolutions for any bounded params on the trait definition
206 trait_vtables: vtable_res,
207 // resolutions for the trait /itself/ (and for supertraits)
208 self_vtables: vtable_param_res
211 impl Repr for impl_res {
212 fn repr(&self, tcx: ty::ctxt) -> ~str {
213 format!("impl_res \\{trait_vtables={}, self_vtables={}\\}",
214 self.trait_vtables.repr(tcx),
215 self.self_vtables.repr(tcx))
219 pub type impl_vtable_map = RefCell<DefIdMap<impl_res>>;
221 pub struct CrateCtxt {
222 // A mapping from method call sites to traits that have that method.
223 trait_map: resolve::TraitMap,
224 method_map: MethodMap,
225 vtable_map: vtable_map,
229 // Functions that write types into the node type table
230 pub fn write_ty_to_tcx(tcx: ty::ctxt, node_id: ast::NodeId, ty: ty::t) {
231 debug!("write_ty_to_tcx({}, {})", node_id, ppaux::ty_to_str(tcx, ty));
232 assert!(!ty::type_needs_infer(ty));
233 let mut node_types = tcx.node_types.borrow_mut();
234 node_types.get().insert(node_id as uint, ty);
236 pub fn write_substs_to_tcx(tcx: ty::ctxt,
237 node_id: ast::NodeId,
239 if substs.len() > 0u {
240 debug!("write_substs_to_tcx({}, {:?})", node_id,
241 substs.map(|t| ppaux::ty_to_str(tcx, *t)));
242 assert!(substs.iter().all(|t| !ty::type_needs_infer(*t)));
244 let mut node_type_substs = tcx.node_type_substs.borrow_mut();
245 node_type_substs.get().insert(node_id, substs);
248 pub fn write_tpt_to_tcx(tcx: ty::ctxt,
249 node_id: ast::NodeId,
250 tpt: &ty::ty_param_substs_and_ty) {
251 write_ty_to_tcx(tcx, node_id, tpt.ty);
252 if !tpt.substs.tps.is_empty() {
253 write_substs_to_tcx(tcx, node_id, tpt.substs.tps.clone());
257 pub fn lookup_def_tcx(tcx: ty::ctxt, sp: Span, id: ast::NodeId) -> ast::Def {
258 let def_map = tcx.def_map.borrow();
259 match def_map.get().find(&id) {
262 tcx.sess.span_fatal(sp, "internal error looking up a definition")
267 pub fn lookup_def_ccx(ccx: &CrateCtxt, sp: Span, id: ast::NodeId)
269 lookup_def_tcx(ccx.tcx, sp, id)
272 pub fn no_params(t: ty::t) -> ty::ty_param_bounds_and_ty {
273 ty::ty_param_bounds_and_ty {
274 generics: ty::Generics {type_param_defs: Rc::new(~[]),
275 region_param_defs: Rc::new(~[])},
280 pub fn require_same_types(tcx: ty::ctxt,
281 maybe_infcx: Option<&infer::InferCtxt>,
282 t1_is_expected: bool,
288 let result = match maybe_infcx {
290 let infcx = infer::new_infer_ctxt(tcx);
291 infer::mk_eqty(&infcx, t1_is_expected, infer::Misc(span), t1, t2)
294 infer::mk_eqty(infcx, t1_is_expected, infer::Misc(span), t1, t2)
301 tcx.sess.span_err(span, msg() + ": " +
302 ty::type_err_to_str(tcx, terr));
303 ty::note_and_explain_type_err(tcx, terr);
309 // a list of mapping from in-scope-region-names ("isr") to the
310 // corresponding ty::Region
311 pub type isr_alist = @List<(ty::BoundRegion, ty::Region)>;
313 trait get_region<'a, T:'static> {
314 fn get(&'a self, br: ty::BoundRegion) -> ty::Region;
317 impl<'a, T:'static> get_region <'a, T> for isr_alist {
318 fn get(&'a self, br: ty::BoundRegion) -> ty::Region {
319 let mut region = None;
320 for isr in self.iter() {
321 let (isr_br, isr_r) = *isr;
322 if isr_br == br { region = Some(isr_r); break; }
328 fn check_main_fn_ty(ccx: &CrateCtxt,
329 main_id: ast::NodeId,
332 let main_t = ty::node_id_to_type(tcx, main_id);
333 match ty::get(main_t).sty {
334 ty::ty_bare_fn(..) => {
335 match tcx.map.find(main_id) {
336 Some(ast_map::NodeItem(it)) => {
338 ast::ItemFn(_, _, _, ref ps, _)
339 if ps.is_parameterized() => {
342 "main function is not allowed to have type parameters");
350 let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
351 purity: ast::ImpureFn,
352 abis: abi::AbiSet::Rust(),
356 output: ty::mk_nil(),
361 require_same_types(tcx, None, false, main_span, main_t, se_ty,
362 || format!("main function expects type: `{}`",
363 ppaux::ty_to_str(ccx.tcx, se_ty)));
366 tcx.sess.span_bug(main_span,
367 format!("main has a non-function type: found `{}`",
368 ppaux::ty_to_str(tcx, main_t)));
373 fn check_start_fn_ty(ccx: &CrateCtxt,
374 start_id: ast::NodeId,
377 let start_t = ty::node_id_to_type(tcx, start_id);
378 match ty::get(start_t).sty {
379 ty::ty_bare_fn(_) => {
380 match tcx.map.find(start_id) {
381 Some(ast_map::NodeItem(it)) => {
383 ast::ItemFn(_,_,_,ref ps,_)
384 if ps.is_parameterized() => {
387 "start function is not allowed to have type parameters");
396 let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
397 purity: ast::ImpureFn,
398 abis: abi::AbiSet::Rust(),
403 ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, ty::mk_u8()))
405 output: ty::mk_int(),
410 require_same_types(tcx, None, false, start_span, start_t, se_ty,
411 || format!("start function expects type: `{}`", ppaux::ty_to_str(ccx.tcx, se_ty)));
415 tcx.sess.span_bug(start_span,
416 format!("start has a non-function type: found `{}`",
417 ppaux::ty_to_str(tcx, start_t)));
422 fn check_for_entry_fn(ccx: &CrateCtxt) {
424 if !tcx.sess.building_library.get() {
425 match tcx.sess.entry_fn.get() {
426 Some((id, sp)) => match tcx.sess.entry_type.get() {
427 Some(session::EntryMain) => check_main_fn_ty(ccx, id, sp),
428 Some(session::EntryStart) => check_start_fn_ty(ccx, id, sp),
429 Some(session::EntryNone) => {}
430 None => tcx.sess.bug("entry function without a type")
437 pub fn check_crate(tcx: ty::ctxt,
438 trait_map: resolve::TraitMap,
440 -> (MethodMap, vtable_map) {
441 let time_passes = tcx.sess.time_passes();
442 let ccx = @CrateCtxt {
443 trait_map: trait_map,
444 method_map: @RefCell::new(NodeMap::new()),
445 vtable_map: @RefCell::new(NodeMap::new()),
449 time(time_passes, "type collecting", (), |_|
450 collect::collect_item_types(ccx, krate));
452 // this ensures that later parts of type checking can assume that items
453 // have valid types and not error
454 tcx.sess.abort_if_errors();
456 time(time_passes, "variance inference", (), |_|
457 variance::infer_variance(tcx, krate));
459 time(time_passes, "coherence checking", (), |_|
460 coherence::check_coherence(ccx, krate));
462 time(time_passes, "type checking", (), |_|
463 check::check_item_types(ccx, krate));
465 check_for_entry_fn(ccx);
466 tcx.sess.abort_if_errors();
467 (ccx.method_map, ccx.vtable_map)