src/librustc_typeck/lib.rs

   1 // Copyright 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.
   4 //
   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.
  10
  11 /*!
  12
  13 typeck.rs, an introduction
  14
  15 The type checker is responsible for:
  16
  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)
  21
  22 The main entry point is `check_crate()`.  Type checking operates in
  23 several major phases:
  24
  25 1. The collect phase first passes over all items and determines their
  26    type, without examining their "innards".
  27
  28 2. Variance inference then runs to compute the variance of each parameter
  29
  30 3. Coherence checks for overlapping or orphaned impls
  31
  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.
  39
  40 The type checker is defined into various submodules which are documented
  41 independently:
  42
  43 - astconv: converts the AST representation of types
  44   into the `ty` representation
  45
  46 - collect: computes the types of each top-level item and enters them into
  47   the `cx.tcache` table for later use
  48
  49 - coherence: enforces coherence rules, builds some tables
  50
  51 - variance: variance inference
  52
  53 - check: walks over function bodies and type checks them, inferring types for
  54   local variables, type parameters, etc as necessary.
  55
  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.
  59
  60 # Note
  61
  62 This API is completely unstable and subject to change.
  63
  64 */
  65
  66 #![crate_name = "rustc_typeck"]
  67 #![experimental]
  68 #![staged_api]
  69 #![crate_type = "dylib"]
  70 #![crate_type = "rlib"]
  71 #![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
  72       html_favicon_url = "http://www.rust-lang.org/favicon.ico",
  73       html_root_url = "http://doc.rust-lang.org/nightly/")]
  74
  75 #![allow(unknown_features)]
  76 #![feature(quote)]
  77 #![feature(slicing_syntax, unsafe_destructor)]
  78 #![feature(box_syntax)]
  79 #![feature(rustc_diagnostic_macros)]
  80 #![allow(non_camel_case_types)]
  81
  82 #[macro_use] extern crate log;
  83 #[macro_use] extern crate syntax;
  84
  85 extern crate arena;
  86 extern crate rustc;
  87
  88 pub use rustc::lint;
  89 pub use rustc::metadata;
  90 pub use rustc::middle;
  91 pub use rustc::session;
  92 pub use rustc::util;
  93
  94 use middle::def;
  95 use middle::infer;
  96 use middle::subst;
  97 use middle::subst::VecPerParamSpace;
  98 use middle::ty::{self, Ty};
  99 use session::config;
 100 use util::common::time;
 101 use util::ppaux::Repr;
 102 use util::ppaux;
 103
 104 use syntax::codemap::Span;
 105 use syntax::print::pprust::*;
 106 use syntax::{ast, ast_map, abi};
 107 use syntax::ast_util::local_def;
 108
 109 mod check;
 110 mod rscope;
 111 mod astconv;
 112 mod collect;
 113 mod coherence;
 114 mod variance;
 115
 116 struct TypeAndSubsts<'tcx> {
 117     pub substs: subst::Substs<'tcx>,
 118     pub ty: Ty<'tcx>,
 119 }
 120
 121 struct CrateCtxt<'a, 'tcx: 'a> {
 122     // A mapping from method call sites to traits that have that method.
 123     trait_map: ty::TraitMap,
 124     tcx: &'a ty::ctxt<'tcx>,
 125 }
 126
 127 // Functions that write types into the node type table
 128 fn write_ty_to_tcx<'tcx>(tcx: &ty::ctxt<'tcx>, node_id: ast::NodeId, ty: Ty<'tcx>) {
 129     debug!("write_ty_to_tcx({}, {})", node_id, ppaux::ty_to_string(tcx, ty));
 130     assert!(!ty::type_needs_infer(ty));
 131     tcx.node_types.borrow_mut().insert(node_id, ty);
 132 }
 133
 134 fn write_substs_to_tcx<'tcx>(tcx: &ty::ctxt<'tcx>,
 135                                  node_id: ast::NodeId,
 136                                  item_substs: ty::ItemSubsts<'tcx>) {
 137     if !item_substs.is_noop() {
 138         debug!("write_substs_to_tcx({}, {})",
 139                node_id,
 140                item_substs.repr(tcx));
 141
 142         assert!(item_substs.substs.types.all(|t| !ty::type_needs_infer(*t)));
 143
 144         tcx.item_substs.borrow_mut().insert(node_id, item_substs);
 145     }
 146 }
 147 fn lookup_def_tcx(tcx:&ty::ctxt, sp: Span, id: ast::NodeId) -> def::Def {
 148     match tcx.def_map.borrow().get(&id) {
 149         Some(x) => x.clone(),
 150         _ => {
 151             tcx.sess.span_fatal(sp, "internal error looking up a definition")
 152         }
 153     }
 154 }
 155
 156 fn lookup_def_ccx(ccx: &CrateCtxt, sp: Span, id: ast::NodeId)
 157                    -> def::Def {
 158     lookup_def_tcx(ccx.tcx, sp, id)
 159 }
 160
 161 fn no_params<'tcx>(t: Ty<'tcx>) -> ty::TypeScheme<'tcx> {
 162     ty::TypeScheme {
 163         generics: ty::Generics {
 164             types: VecPerParamSpace::empty(),
 165             regions: VecPerParamSpace::empty(),
 166             predicates: VecPerParamSpace::empty(),
 167         },
 168         ty: t
 169     }
 170 }
 171
 172 fn require_same_types<'a, 'tcx, M>(tcx: &ty::ctxt<'tcx>,
 173                                    maybe_infcx: Option<&infer::InferCtxt<'a, 'tcx>>,
 174                                    t1_is_expected: bool,
 175                                    span: Span,
 176                                    t1: Ty<'tcx>,
 177                                    t2: Ty<'tcx>,
 178                                    msg: M)
 179                                    -> bool where
 180     M: FnOnce() -> String,
 181 {
 182     let result = match maybe_infcx {
 183         None => {
 184             let infcx = infer::new_infer_ctxt(tcx);
 185             infer::mk_eqty(&infcx, t1_is_expected, infer::Misc(span), t1, t2)
 186         }
 187         Some(infcx) => {
 188             infer::mk_eqty(infcx, t1_is_expected, infer::Misc(span), t1, t2)
 189         }
 190     };
 191
 192     match result {
 193         Ok(_) => true,
 194         Err(ref terr) => {
 195             tcx.sess.span_err(span,
 196                               &format!("{}: {}",
 197                                       msg(),
 198                                       ty::type_err_to_str(tcx,
 199                                                           terr))[]);
 200             ty::note_and_explain_type_err(tcx, terr);
 201             false
 202         }
 203     }
 204 }
 205
 206 fn check_main_fn_ty(ccx: &CrateCtxt,
 207                     main_id: ast::NodeId,
 208                     main_span: Span) {
 209     let tcx = ccx.tcx;
 210     let main_t = ty::node_id_to_type(tcx, main_id);
 211     match main_t.sty {
 212         ty::ty_bare_fn(..) => {
 213             match tcx.map.find(main_id) {
 214                 Some(ast_map::NodeItem(it)) => {
 215                     match it.node {
 216                         ast::ItemFn(_, _, _, ref ps, _)
 217                         if ps.is_parameterized() => {
 218                             span_err!(ccx.tcx.sess, main_span, E0131,
 219                                       "main function is not allowed to have type parameters");
 220                             return;
 221                         }
 222                         _ => ()
 223                     }
 224                 }
 225                 _ => ()
 226             }
 227             let se_ty = ty::mk_bare_fn(tcx, Some(local_def(main_id)), tcx.mk_bare_fn(ty::BareFnTy {
 228                 unsafety: ast::Unsafety::Normal,
 229                 abi: abi::Rust,
 230                 sig: ty::Binder(ty::FnSig {
 231                     inputs: Vec::new(),
 232                     output: ty::FnConverging(ty::mk_nil(tcx)),
 233                     variadic: false
 234                 })
 235             }));
 236
 237             require_same_types(tcx, None, false, main_span, main_t, se_ty,
 238                 || {
 239                     format!("main function expects type: `{}`",
 240                             ppaux::ty_to_string(ccx.tcx, se_ty))
 241                 });
 242         }
 243         _ => {
 244             tcx.sess.span_bug(main_span,
 245                               &format!("main has a non-function type: found \
 246                                        `{}`",
 247                                       ppaux::ty_to_string(tcx,
 248                                                        main_t))[]);
 249         }
 250     }
 251 }
 252
 253 fn check_start_fn_ty(ccx: &CrateCtxt,
 254                      start_id: ast::NodeId,
 255                      start_span: Span) {
 256     let tcx = ccx.tcx;
 257     let start_t = ty::node_id_to_type(tcx, start_id);
 258     match start_t.sty {
 259         ty::ty_bare_fn(..) => {
 260             match tcx.map.find(start_id) {
 261                 Some(ast_map::NodeItem(it)) => {
 262                     match it.node {
 263                         ast::ItemFn(_,_,_,ref ps,_)
 264                         if ps.is_parameterized() => {
 265                             span_err!(tcx.sess, start_span, E0132,
 266                                       "start function is not allowed to have type parameters");
 267                             return;
 268                         }
 269                         _ => ()
 270                     }
 271                 }
 272                 _ => ()
 273             }
 274
 275             let se_ty = ty::mk_bare_fn(tcx, Some(local_def(start_id)), tcx.mk_bare_fn(ty::BareFnTy {
 276                 unsafety: ast::Unsafety::Normal,
 277                 abi: abi::Rust,
 278                 sig: ty::Binder(ty::FnSig {
 279                     inputs: vec!(
 280                         tcx.types.int,
 281                         ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, tcx.types.u8))
 282                     ),
 283                     output: ty::FnConverging(tcx.types.int),
 284                     variadic: false,
 285                 }),
 286             }));
 287
 288             require_same_types(tcx, None, false, start_span, start_t, se_ty,
 289                 || {
 290                     format!("start function expects type: `{}`",
 291                             ppaux::ty_to_string(ccx.tcx, se_ty))
 292                 });
 293
 294         }
 295         _ => {
 296             tcx.sess.span_bug(start_span,
 297                               &format!("start has a non-function type: found \
 298                                        `{}`",
 299                                       ppaux::ty_to_string(tcx, start_t))[]);
 300         }
 301     }
 302 }
 303
 304 fn check_for_entry_fn(ccx: &CrateCtxt) {
 305     let tcx = ccx.tcx;
 306     match *tcx.sess.entry_fn.borrow() {
 307         Some((id, sp)) => match tcx.sess.entry_type.get() {
 308             Some(config::EntryMain) => check_main_fn_ty(ccx, id, sp),
 309             Some(config::EntryStart) => check_start_fn_ty(ccx, id, sp),
 310             Some(config::EntryNone) => {}
 311             None => tcx.sess.bug("entry function without a type")
 312         },
 313         None => {}
 314     }
 315 }
 316
 317 pub fn check_crate(tcx: &ty::ctxt, trait_map: ty::TraitMap) {
 318     let time_passes = tcx.sess.time_passes();
 319     let ccx = CrateCtxt {
 320         trait_map: trait_map,
 321         tcx: tcx
 322     };
 323
 324     time(time_passes, "type collecting", (), |_|
 325          collect::collect_item_types(tcx));
 326
 327     // this ensures that later parts of type checking can assume that items
 328     // have valid types and not error
 329     tcx.sess.abort_if_errors();
 330
 331     time(time_passes, "variance inference", (), |_|
 332          variance::infer_variance(tcx));
 333
 334     time(time_passes, "coherence checking", (), |_|
 335         coherence::check_coherence(&ccx));
 336
 337     time(time_passes, "type checking", (), |_|
 338         check::check_item_types(&ccx));
 339
 340     check_for_entry_fn(&ccx);
 341     tcx.sess.abort_if_errors();
 342 }