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, FnvHashMap, NodeMap};
73 use std::cell::RefCell;
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 #[deriving(Clone, Eq, Hash)]
153 pub struct MethodCall {
154 expr_id: ast::NodeId,
159 pub fn expr(id: ast::NodeId) -> MethodCall {
166 pub fn autoderef(expr_id: ast::NodeId, autoderef: u32) -> MethodCall {
169 autoderef: 1 + autoderef
174 // maps from an expression id that corresponds to a method call to the details
175 // of the method to be invoked
176 pub type MethodMap = @RefCell<FnvHashMap<MethodCall, MethodCallee>>;
178 pub type vtable_param_res = @Vec<vtable_origin> ;
179 // Resolutions for bounds of all parameters, left to right, for a given path.
180 pub type vtable_res = @Vec<vtable_param_res> ;
183 pub enum vtable_origin {
185 Statically known vtable. def_id gives the class or impl item
186 from whence comes the vtable, and tys are the type substs.
187 vtable_res is the vtable itself
189 vtable_static(ast::DefId, Vec<ty::t> , vtable_res),
192 Dynamic vtable, comes from a parameter that has a bound on it:
193 fn foo<T:quux,baz,bar>(a: T) -- a's vtable would have a
196 The first argument is the param index (identifying T in the example),
197 and the second is the bound number (identifying baz)
199 vtable_param(param_index, uint),
202 impl Repr for vtable_origin {
203 fn repr(&self, tcx: &ty::ctxt) -> ~str {
205 vtable_static(def_id, ref tys, ref vtable_res) => {
206 format!("vtable_static({:?}:{}, {}, {})",
208 ty::item_path_str(tcx, def_id),
210 vtable_res.repr(tcx))
213 vtable_param(x, y) => {
214 format!("vtable_param({:?}, {:?})", x, y)
220 pub type vtable_map = @RefCell<NodeMap<vtable_res>>;
223 // Information about the vtable resolutions for a trait impl.
224 // Mostly the information is important for implementing default
227 pub struct impl_res {
228 // resolutions for any bounded params on the trait definition
229 trait_vtables: vtable_res,
230 // resolutions for the trait /itself/ (and for supertraits)
231 self_vtables: vtable_param_res
234 impl Repr for impl_res {
235 fn repr(&self, tcx: &ty::ctxt) -> ~str {
236 format!("impl_res \\{trait_vtables={}, self_vtables={}\\}",
237 self.trait_vtables.repr(tcx),
238 self.self_vtables.repr(tcx))
242 pub type impl_vtable_map = RefCell<DefIdMap<impl_res>>;
244 pub struct CrateCtxt<'a> {
245 // A mapping from method call sites to traits that have that method.
246 trait_map: resolve::TraitMap,
247 method_map: MethodMap,
248 vtable_map: vtable_map,
252 // Functions that write types into the node type table
253 pub fn write_ty_to_tcx(tcx: &ty::ctxt, node_id: ast::NodeId, ty: ty::t) {
254 debug!("write_ty_to_tcx({}, {})", node_id, ppaux::ty_to_str(tcx, ty));
255 assert!(!ty::type_needs_infer(ty));
256 let mut node_types = tcx.node_types.borrow_mut();
257 node_types.get().insert(node_id as uint, ty);
259 pub fn write_substs_to_tcx(tcx: &ty::ctxt,
260 node_id: ast::NodeId,
261 substs: Vec<ty::t> ) {
262 if substs.len() > 0u {
263 debug!("write_substs_to_tcx({}, {:?})", node_id,
264 substs.map(|t| ppaux::ty_to_str(tcx, *t)));
265 assert!(substs.iter().all(|t| !ty::type_needs_infer(*t)));
267 let mut node_type_substs = tcx.node_type_substs.borrow_mut();
268 node_type_substs.get().insert(node_id, substs);
271 pub fn write_tpt_to_tcx(tcx: &ty::ctxt,
272 node_id: ast::NodeId,
273 tpt: &ty::ty_param_substs_and_ty) {
274 write_ty_to_tcx(tcx, node_id, tpt.ty);
275 if !tpt.substs.tps.is_empty() {
276 write_substs_to_tcx(tcx, node_id, tpt.substs.tps.clone());
280 pub fn lookup_def_tcx(tcx:&ty::ctxt, sp: Span, id: ast::NodeId) -> ast::Def {
281 let def_map = tcx.def_map.borrow();
282 match def_map.get().find(&id) {
285 tcx.sess.span_fatal(sp, "internal error looking up a definition")
290 pub fn lookup_def_ccx(ccx: &CrateCtxt, sp: Span, id: ast::NodeId)
292 lookup_def_tcx(ccx.tcx, sp, id)
295 pub fn no_params(t: ty::t) -> ty::ty_param_bounds_and_ty {
296 ty::ty_param_bounds_and_ty {
297 generics: ty::Generics {type_param_defs: Rc::new(Vec::new()),
298 region_param_defs: Rc::new(Vec::new())},
303 pub fn require_same_types(tcx: &ty::ctxt,
304 maybe_infcx: Option<&infer::InferCtxt>,
305 t1_is_expected: bool,
311 let result = match maybe_infcx {
313 let infcx = infer::new_infer_ctxt(tcx);
314 infer::mk_eqty(&infcx, t1_is_expected, infer::Misc(span), t1, t2)
317 infer::mk_eqty(infcx, t1_is_expected, infer::Misc(span), t1, t2)
324 tcx.sess.span_err(span, msg() + ": " +
325 ty::type_err_to_str(tcx, terr));
326 ty::note_and_explain_type_err(tcx, terr);
332 // a list of mapping from in-scope-region-names ("isr") to the
333 // corresponding ty::Region
334 pub type isr_alist = @List<(ty::BoundRegion, ty::Region)>;
336 trait get_region<'a, T:'static> {
337 fn get(&'a self, br: ty::BoundRegion) -> ty::Region;
340 impl<'a, T:'static> get_region <'a, T> for isr_alist {
341 fn get(&'a self, br: ty::BoundRegion) -> ty::Region {
342 let mut region = None;
343 for isr in self.iter() {
344 let (isr_br, isr_r) = *isr;
345 if isr_br == br { region = Some(isr_r); break; }
351 fn check_main_fn_ty(ccx: &CrateCtxt,
352 main_id: ast::NodeId,
355 let main_t = ty::node_id_to_type(tcx, main_id);
356 match ty::get(main_t).sty {
357 ty::ty_bare_fn(..) => {
358 match tcx.map.find(main_id) {
359 Some(ast_map::NodeItem(it)) => {
361 ast::ItemFn(_, _, _, ref ps, _)
362 if ps.is_parameterized() => {
365 "main function is not allowed to have type parameters");
373 let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
374 purity: ast::ImpureFn,
375 abis: abi::AbiSet::Rust(),
379 output: ty::mk_nil(),
384 require_same_types(tcx, None, false, main_span, main_t, se_ty,
385 || format!("main function expects type: `{}`",
386 ppaux::ty_to_str(ccx.tcx, se_ty)));
389 tcx.sess.span_bug(main_span,
390 format!("main has a non-function type: found `{}`",
391 ppaux::ty_to_str(tcx, main_t)));
396 fn check_start_fn_ty(ccx: &CrateCtxt,
397 start_id: ast::NodeId,
400 let start_t = ty::node_id_to_type(tcx, start_id);
401 match ty::get(start_t).sty {
402 ty::ty_bare_fn(_) => {
403 match tcx.map.find(start_id) {
404 Some(ast_map::NodeItem(it)) => {
406 ast::ItemFn(_,_,_,ref ps,_)
407 if ps.is_parameterized() => {
410 "start function is not allowed to have type parameters");
419 let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
420 purity: ast::ImpureFn,
421 abis: abi::AbiSet::Rust(),
426 ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, ty::mk_u8()))
428 output: ty::mk_int(),
433 require_same_types(tcx, None, false, start_span, start_t, se_ty,
434 || format!("start function expects type: `{}`", ppaux::ty_to_str(ccx.tcx, se_ty)));
438 tcx.sess.span_bug(start_span,
439 format!("start has a non-function type: found `{}`",
440 ppaux::ty_to_str(tcx, start_t)));
445 fn check_for_entry_fn(ccx: &CrateCtxt) {
447 if !tcx.sess.building_library.get() {
448 match tcx.sess.entry_fn.get() {
449 Some((id, sp)) => match tcx.sess.entry_type.get() {
450 Some(session::EntryMain) => check_main_fn_ty(ccx, id, sp),
451 Some(session::EntryStart) => check_start_fn_ty(ccx, id, sp),
452 Some(session::EntryNone) => {}
453 None => tcx.sess.bug("entry function without a type")
460 pub fn check_crate(tcx: &ty::ctxt,
461 trait_map: resolve::TraitMap,
463 -> (MethodMap, vtable_map) {
464 let time_passes = tcx.sess.time_passes();
465 let ccx = CrateCtxt {
466 trait_map: trait_map,
467 method_map: @RefCell::new(FnvHashMap::new()),
468 vtable_map: @RefCell::new(NodeMap::new()),
472 time(time_passes, "type collecting", (), |_|
473 collect::collect_item_types(&ccx, krate));
475 // this ensures that later parts of type checking can assume that items
476 // have valid types and not error
477 tcx.sess.abort_if_errors();
479 time(time_passes, "variance inference", (), |_|
480 variance::infer_variance(tcx, krate));
482 time(time_passes, "coherence checking", (), |_|
483 coherence::check_coherence(&ccx, krate));
485 time(time_passes, "type checking", (), |_|
486 check::check_item_types(&ccx, krate));
488 check_for_entry_fn(&ccx);
489 tcx.sess.abort_if_errors();
490 (ccx.method_map, ccx.vtable_map)