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
146 pub struct MethodCallee {
147 origin: MethodOrigin,
152 // maps from an expression id that corresponds to a method call to the details
153 // of the method to be invoked
154 pub type MethodMap = @RefCell<HashMap<ast::NodeId, MethodCallee>>;
156 pub type vtable_param_res = @~[vtable_origin];
157 // Resolutions for bounds of all parameters, left to right, for a given path.
158 pub type vtable_res = @~[vtable_param_res];
161 pub enum vtable_origin {
163 Statically known vtable. def_id gives the class or impl item
164 from whence comes the vtable, and tys are the type substs.
165 vtable_res is the vtable itself
167 vtable_static(ast::DefId, ~[ty::t], vtable_res),
170 Dynamic vtable, comes from a parameter that has a bound on it:
171 fn foo<T:quux,baz,bar>(a: T) -- a's vtable would have a
174 The first argument is the param index (identifying T in the example),
175 and the second is the bound number (identifying baz)
177 vtable_param(param_index, uint),
180 impl Repr for vtable_origin {
181 fn repr(&self, tcx: ty::ctxt) -> ~str {
183 vtable_static(def_id, ref tys, ref vtable_res) => {
184 format!("vtable_static({:?}:{}, {}, {})",
186 ty::item_path_str(tcx, def_id),
188 vtable_res.repr(tcx))
191 vtable_param(x, y) => {
192 format!("vtable_param({:?}, {:?})", x, y)
198 pub type vtable_map = @RefCell<HashMap<ast::NodeId, vtable_res>>;
201 // Information about the vtable resolutions for for a trait impl.
202 // Mostly the information is important for implementing default
205 pub struct impl_res {
206 // resolutions for any bounded params on the trait definition
207 trait_vtables: vtable_res,
208 // resolutions for the trait /itself/ (and for supertraits)
209 self_vtables: vtable_param_res
212 impl Repr for impl_res {
213 fn repr(&self, tcx: ty::ctxt) -> ~str {
214 format!("impl_res \\{trait_vtables={}, self_vtables={}\\}",
215 self.trait_vtables.repr(tcx),
216 self.self_vtables.repr(tcx))
220 pub type impl_vtable_map = RefCell<HashMap<ast::DefId, impl_res>>;
222 pub struct CrateCtxt {
223 // A mapping from method call sites to traits that have that method.
224 trait_map: resolve::TraitMap,
225 method_map: MethodMap,
226 vtable_map: vtable_map,
230 // Functions that write types into the node type table
231 pub fn write_ty_to_tcx(tcx: ty::ctxt, node_id: ast::NodeId, ty: ty::t) {
232 debug!("write_ty_to_tcx({}, {})", node_id, ppaux::ty_to_str(tcx, ty));
233 assert!(!ty::type_needs_infer(ty));
234 let mut node_types = tcx.node_types.borrow_mut();
235 node_types.get().insert(node_id as uint, ty);
237 pub fn write_substs_to_tcx(tcx: ty::ctxt,
238 node_id: ast::NodeId,
240 if substs.len() > 0u {
241 debug!("write_substs_to_tcx({}, {:?})", node_id,
242 substs.map(|t| ppaux::ty_to_str(tcx, *t)));
243 assert!(substs.iter().all(|t| !ty::type_needs_infer(*t)));
245 let mut node_type_substs = tcx.node_type_substs.borrow_mut();
246 node_type_substs.get().insert(node_id, substs);
249 pub fn write_tpt_to_tcx(tcx: ty::ctxt,
250 node_id: ast::NodeId,
251 tpt: &ty::ty_param_substs_and_ty) {
252 write_ty_to_tcx(tcx, node_id, tpt.ty);
253 if !tpt.substs.tps.is_empty() {
254 write_substs_to_tcx(tcx, node_id, tpt.substs.tps.clone());
258 pub fn lookup_def_tcx(tcx: ty::ctxt, sp: Span, id: ast::NodeId) -> ast::Def {
259 let def_map = tcx.def_map.borrow();
260 match def_map.get().find(&id) {
263 tcx.sess.span_fatal(sp, "internal error looking up a definition")
268 pub fn lookup_def_ccx(ccx: &CrateCtxt, sp: Span, id: ast::NodeId)
270 lookup_def_tcx(ccx.tcx, sp, id)
273 pub fn no_params(t: ty::t) -> ty::ty_param_bounds_and_ty {
274 ty::ty_param_bounds_and_ty {
275 generics: ty::Generics {type_param_defs: Rc::new(~[]),
276 region_param_defs: Rc::new(~[])},
281 pub fn require_same_types(tcx: ty::ctxt,
282 maybe_infcx: Option<&infer::InferCtxt>,
283 t1_is_expected: bool,
289 let result = match maybe_infcx {
291 let infcx = infer::new_infer_ctxt(tcx);
292 infer::mk_eqty(&infcx, t1_is_expected, infer::Misc(span), t1, t2)
295 infer::mk_eqty(infcx, t1_is_expected, infer::Misc(span), t1, t2)
302 tcx.sess.span_err(span, msg() + ": " +
303 ty::type_err_to_str(tcx, terr));
304 ty::note_and_explain_type_err(tcx, terr);
310 // a list of mapping from in-scope-region-names ("isr") to the
311 // corresponding ty::Region
312 pub type isr_alist = @List<(ty::BoundRegion, ty::Region)>;
314 trait get_and_find_region {
315 fn get(&self, br: ty::BoundRegion) -> ty::Region;
316 fn find(&self, br: ty::BoundRegion) -> Option<ty::Region>;
319 impl get_and_find_region for isr_alist {
320 fn get(&self, br: ty::BoundRegion) -> ty::Region {
321 self.find(br).unwrap()
324 fn find(&self, br: ty::BoundRegion) -> Option<ty::Region> {
326 list::each(*self, |isr| {
327 let (isr_br, isr_r) = *isr;
328 if isr_br == br { ret = Some(isr_r); false } else { true }
334 fn check_main_fn_ty(ccx: &CrateCtxt,
335 main_id: ast::NodeId,
338 let main_t = ty::node_id_to_type(tcx, main_id);
339 match ty::get(main_t).sty {
340 ty::ty_bare_fn(..) => {
341 match tcx.map.find(main_id) {
342 Some(ast_map::NodeItem(it)) => {
344 ast::ItemFn(_, _, _, ref ps, _)
345 if ps.is_parameterized() => {
348 "main function is not allowed to have type parameters");
356 let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
357 purity: ast::ImpureFn,
358 abis: abi::AbiSet::Rust(),
362 output: ty::mk_nil(),
367 require_same_types(tcx, None, false, main_span, main_t, se_ty,
368 || format!("main function expects type: `{}`",
369 ppaux::ty_to_str(ccx.tcx, se_ty)));
372 tcx.sess.span_bug(main_span,
373 format!("main has a non-function type: found `{}`",
374 ppaux::ty_to_str(tcx, main_t)));
379 fn check_start_fn_ty(ccx: &CrateCtxt,
380 start_id: ast::NodeId,
383 let start_t = ty::node_id_to_type(tcx, start_id);
384 match ty::get(start_t).sty {
385 ty::ty_bare_fn(_) => {
386 match tcx.map.find(start_id) {
387 Some(ast_map::NodeItem(it)) => {
389 ast::ItemFn(_,_,_,ref ps,_)
390 if ps.is_parameterized() => {
393 "start function is not allowed to have type parameters");
402 let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
403 purity: ast::ImpureFn,
404 abis: abi::AbiSet::Rust(),
409 ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, ty::mk_u8()))
411 output: ty::mk_int(),
416 require_same_types(tcx, None, false, start_span, start_t, se_ty,
417 || format!("start function expects type: `{}`", ppaux::ty_to_str(ccx.tcx, se_ty)));
421 tcx.sess.span_bug(start_span,
422 format!("start has a non-function type: found `{}`",
423 ppaux::ty_to_str(tcx, start_t)));
428 fn check_for_entry_fn(ccx: &CrateCtxt) {
430 if !tcx.sess.building_library.get() {
431 match tcx.sess.entry_fn.get() {
432 Some((id, sp)) => match tcx.sess.entry_type.get() {
433 Some(session::EntryMain) => check_main_fn_ty(ccx, id, sp),
434 Some(session::EntryStart) => check_start_fn_ty(ccx, id, sp),
435 Some(session::EntryNone) => {}
436 None => tcx.sess.bug("entry function without a type")
443 pub fn check_crate(tcx: ty::ctxt,
444 trait_map: resolve::TraitMap,
446 -> (MethodMap, vtable_map) {
447 let time_passes = tcx.sess.time_passes();
448 let ccx = @CrateCtxt {
449 trait_map: trait_map,
450 method_map: @RefCell::new(HashMap::new()),
451 vtable_map: @RefCell::new(HashMap::new()),
455 time(time_passes, "type collecting", (), |_|
456 collect::collect_item_types(ccx, krate));
458 // this ensures that later parts of type checking can assume that items
459 // have valid types and not error
460 tcx.sess.abort_if_errors();
462 time(time_passes, "variance inference", (), |_|
463 variance::infer_variance(tcx, krate));
465 time(time_passes, "coherence checking", (), |_|
466 coherence::check_coherence(ccx, krate));
468 time(time_passes, "type checking", (), |_|
469 check::check_item_types(ccx, krate));
471 check_for_entry_fn(ccx);
472 tcx.sess.abort_if_errors();
473 (ccx.method_map, ccx.vtable_map)