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;
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<NodeMap<MethodCallee>>;
156 pub type vtable_param_res = @Vec<vtable_origin> ;
157 // Resolutions for bounds of all parameters, left to right, for a given path.
158 pub type vtable_res = @Vec<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, Vec<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<NodeMap<vtable_res>>;
201 // Information about the vtable resolutions 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<DefIdMap<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,
239 substs: Vec<ty::t> ) {
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(Vec::new()),
276 region_param_defs: Rc::new(Vec::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_region<'a, T:'static> {
315 fn get(&'a self, br: ty::BoundRegion) -> ty::Region;
318 impl<'a, T:'static> get_region <'a, T> for isr_alist {
319 fn get(&'a self, br: ty::BoundRegion) -> ty::Region {
320 let mut region = None;
321 for isr in self.iter() {
322 let (isr_br, isr_r) = *isr;
323 if isr_br == br { region = Some(isr_r); break; }
329 fn check_main_fn_ty(ccx: &CrateCtxt,
330 main_id: ast::NodeId,
333 let main_t = ty::node_id_to_type(tcx, main_id);
334 match ty::get(main_t).sty {
335 ty::ty_bare_fn(..) => {
336 match tcx.map.find(main_id) {
337 Some(ast_map::NodeItem(it)) => {
339 ast::ItemFn(_, _, _, ref ps, _)
340 if ps.is_parameterized() => {
343 "main function is not allowed to have type parameters");
351 let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
352 purity: ast::ImpureFn,
353 abis: abi::AbiSet::Rust(),
357 output: ty::mk_nil(),
362 require_same_types(tcx, None, false, main_span, main_t, se_ty,
363 || format!("main function expects type: `{}`",
364 ppaux::ty_to_str(ccx.tcx, se_ty)));
367 tcx.sess.span_bug(main_span,
368 format!("main has a non-function type: found `{}`",
369 ppaux::ty_to_str(tcx, main_t)));
374 fn check_start_fn_ty(ccx: &CrateCtxt,
375 start_id: ast::NodeId,
378 let start_t = ty::node_id_to_type(tcx, start_id);
379 match ty::get(start_t).sty {
380 ty::ty_bare_fn(_) => {
381 match tcx.map.find(start_id) {
382 Some(ast_map::NodeItem(it)) => {
384 ast::ItemFn(_,_,_,ref ps,_)
385 if ps.is_parameterized() => {
388 "start function is not allowed to have type parameters");
397 let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
398 purity: ast::ImpureFn,
399 abis: abi::AbiSet::Rust(),
404 ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, ty::mk_u8()))
406 output: ty::mk_int(),
411 require_same_types(tcx, None, false, start_span, start_t, se_ty,
412 || format!("start function expects type: `{}`", ppaux::ty_to_str(ccx.tcx, se_ty)));
416 tcx.sess.span_bug(start_span,
417 format!("start has a non-function type: found `{}`",
418 ppaux::ty_to_str(tcx, start_t)));
423 fn check_for_entry_fn(ccx: &CrateCtxt) {
425 if !tcx.sess.building_library.get() {
426 match tcx.sess.entry_fn.get() {
427 Some((id, sp)) => match tcx.sess.entry_type.get() {
428 Some(session::EntryMain) => check_main_fn_ty(ccx, id, sp),
429 Some(session::EntryStart) => check_start_fn_ty(ccx, id, sp),
430 Some(session::EntryNone) => {}
431 None => tcx.sess.bug("entry function without a type")
438 pub fn check_crate(tcx: ty::ctxt,
439 trait_map: resolve::TraitMap,
441 -> (MethodMap, vtable_map) {
442 let time_passes = tcx.sess.time_passes();
443 let ccx = @CrateCtxt {
444 trait_map: trait_map,
445 method_map: @RefCell::new(NodeMap::new()),
446 vtable_map: @RefCell::new(NodeMap::new()),
450 time(time_passes, "type collecting", (), |_|
451 collect::collect_item_types(ccx, krate));
453 // this ensures that later parts of type checking can assume that items
454 // have valid types and not error
455 tcx.sess.abort_if_errors();
457 time(time_passes, "variance inference", (), |_|
458 variance::infer_variance(tcx, krate));
460 time(time_passes, "coherence checking", (), |_|
461 coherence::check_coherence(ccx, krate));
463 time(time_passes, "type checking", (), |_|
464 check::check_item_types(ccx, krate));
466 check_for_entry_fn(ccx);
467 tcx.sess.abort_if_errors();
468 (ccx.method_map, ccx.vtable_map)