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 #![unstable]
  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(unknown_features)] #![feature(int_uint)]
  81 #![allow(non_camel_case_types)]
  82 #![allow(unstable)]
  83
  84 #[macro_use] extern crate log;
  85 #[macro_use] extern crate syntax;
  86
  87 extern crate arena;
  88 extern crate fmt_macros;
  89 extern crate rustc;
  90
  91 pub use rustc::lint;
  92 pub use rustc::metadata;
  93 pub use rustc::middle;
  94 pub use rustc::session;
  95 pub use rustc::util;
  96
  97 use middle::def;
  98 use middle::infer;
  99 use middle::subst;
 100 use middle::subst::VecPerParamSpace;
 101 use middle::ty::{self, Ty};
 102 use session::config;
 103 use util::common::time;
 104 use util::ppaux::Repr;
 105 use util::ppaux;
 106
 107 use syntax::codemap::Span;
 108 use syntax::print::pprust::*;
 109 use syntax::{ast, ast_map, abi};
 110 use syntax::ast_util::local_def;
 111
 112 use std::cell::RefCell;
 113
 114 mod check;
 115 mod rscope;
 116 mod astconv;
 117 mod collect;
 118 mod coherence;
 119 mod variance;
 120
 121 struct TypeAndSubsts<'tcx> {
 122     pub substs: subst::Substs<'tcx>,
 123     pub ty: Ty<'tcx>,
 124 }
 125
 126 struct CrateCtxt<'a, 'tcx: 'a> {
 127     // A mapping from method call sites to traits that have that method.
 128     trait_map: ty::TraitMap,
 129     /// A vector of every trait accessible in the whole crate
 130     /// (i.e. including those from subcrates). This is used only for
 131     /// error reporting, and so is lazily initialised and generally
 132     /// shouldn't taint the common path (hence the RefCell).
 133     all_traits: RefCell<Option<check::method::AllTraitsVec>>,
 134     tcx: &'a ty::ctxt<'tcx>,
 135 }
 136
 137 // Functions that write types into the node type table
 138 fn write_ty_to_tcx<'tcx>(tcx: &ty::ctxt<'tcx>, node_id: ast::NodeId, ty: Ty<'tcx>) {
 139     debug!("write_ty_to_tcx({}, {})", node_id, ppaux::ty_to_string(tcx, ty));
 140     assert!(!ty::type_needs_infer(ty));
 141     tcx.node_types.borrow_mut().insert(node_id, ty);
 142 }
 143
 144 fn write_substs_to_tcx<'tcx>(tcx: &ty::ctxt<'tcx>,
 145                                  node_id: ast::NodeId,
 146                                  item_substs: ty::ItemSubsts<'tcx>) {
 147     if !item_substs.is_noop() {
 148         debug!("write_substs_to_tcx({}, {})",
 149                node_id,
 150                item_substs.repr(tcx));
 151
 152         assert!(item_substs.substs.types.all(|t| !ty::type_needs_infer(*t)));
 153
 154         tcx.item_substs.borrow_mut().insert(node_id, item_substs);
 155     }
 156 }
 157 fn lookup_def_tcx(tcx:&ty::ctxt, sp: Span, id: ast::NodeId) -> def::Def {
 158     match tcx.def_map.borrow().get(&id) {
 159         Some(x) => x.clone(),
 160         _ => {
 161             tcx.sess.span_fatal(sp, "internal error looking up a definition")
 162         }
 163     }
 164 }
 165
 166 fn lookup_def_ccx(ccx: &CrateCtxt, sp: Span, id: ast::NodeId)
 167                    -> def::Def {
 168     lookup_def_tcx(ccx.tcx, sp, id)
 169 }
 170
 171 fn no_params<'tcx>(t: Ty<'tcx>) -> ty::TypeScheme<'tcx> {
 172     ty::TypeScheme {
 173         generics: ty::Generics {
 174             types: VecPerParamSpace::empty(),
 175             regions: VecPerParamSpace::empty(),
 176             predicates: VecPerParamSpace::empty(),
 177         },
 178         ty: t
 179     }
 180 }
 181
 182 fn require_same_types<'a, 'tcx, M>(tcx: &ty::ctxt<'tcx>,
 183                                    maybe_infcx: Option<&infer::InferCtxt<'a, 'tcx>>,
 184                                    t1_is_expected: bool,
 185                                    span: Span,
 186                                    t1: Ty<'tcx>,
 187                                    t2: Ty<'tcx>,
 188                                    msg: M)
 189                                    -> bool where
 190     M: FnOnce() -> String,
 191 {
 192     let result = match maybe_infcx {
 193         None => {
 194             let infcx = infer::new_infer_ctxt(tcx);
 195             infer::mk_eqty(&infcx, t1_is_expected, infer::Misc(span), t1, t2)
 196         }
 197         Some(infcx) => {
 198             infer::mk_eqty(infcx, t1_is_expected, infer::Misc(span), t1, t2)
 199         }
 200     };
 201
 202     match result {
 203         Ok(_) => true,
 204         Err(ref terr) => {
 205             tcx.sess.span_err(span,
 206                               &format!("{}: {}",
 207                                       msg(),
 208                                       ty::type_err_to_str(tcx,
 209                                                           terr))[]);
 210             ty::note_and_explain_type_err(tcx, terr);
 211             false
 212         }
 213     }
 214 }
 215
 216 fn check_main_fn_ty(ccx: &CrateCtxt,
 217                     main_id: ast::NodeId,
 218                     main_span: Span) {
 219     let tcx = ccx.tcx;
 220     let main_t = ty::node_id_to_type(tcx, main_id);
 221     match main_t.sty {
 222         ty::ty_bare_fn(..) => {
 223             match tcx.map.find(main_id) {
 224                 Some(ast_map::NodeItem(it)) => {
 225                     match it.node {
 226                         ast::ItemFn(_, _, _, ref ps, _)
 227                         if ps.is_parameterized() => {
 228                             span_err!(ccx.tcx.sess, main_span, E0131,
 229                                       "main function is not allowed to have type parameters");
 230                             return;
 231                         }
 232                         _ => ()
 233                     }
 234                 }
 235                 _ => ()
 236             }
 237             let se_ty = ty::mk_bare_fn(tcx, Some(local_def(main_id)), tcx.mk_bare_fn(ty::BareFnTy {
 238                 unsafety: ast::Unsafety::Normal,
 239                 abi: abi::Rust,
 240                 sig: ty::Binder(ty::FnSig {
 241                     inputs: Vec::new(),
 242                     output: ty::FnConverging(ty::mk_nil(tcx)),
 243                     variadic: false
 244                 })
 245             }));
 246
 247             require_same_types(tcx, None, false, main_span, main_t, se_ty,
 248                 || {
 249                     format!("main function expects type: `{}`",
 250                             ppaux::ty_to_string(ccx.tcx, se_ty))
 251                 });
 252         }
 253         _ => {
 254             tcx.sess.span_bug(main_span,
 255                               &format!("main has a non-function type: found \
 256                                        `{}`",
 257                                       ppaux::ty_to_string(tcx,
 258                                                        main_t))[]);
 259         }
 260     }
 261 }
 262
 263 fn check_start_fn_ty(ccx: &CrateCtxt,
 264                      start_id: ast::NodeId,
 265                      start_span: Span) {
 266     let tcx = ccx.tcx;
 267     let start_t = ty::node_id_to_type(tcx, start_id);
 268     match start_t.sty {
 269         ty::ty_bare_fn(..) => {
 270             match tcx.map.find(start_id) {
 271                 Some(ast_map::NodeItem(it)) => {
 272                     match it.node {
 273                         ast::ItemFn(_,_,_,ref ps,_)
 274                         if ps.is_parameterized() => {
 275                             span_err!(tcx.sess, start_span, E0132,
 276                                       "start function is not allowed to have type parameters");
 277                             return;
 278                         }
 279                         _ => ()
 280                     }
 281                 }
 282                 _ => ()
 283             }
 284
 285             let se_ty = ty::mk_bare_fn(tcx, Some(local_def(start_id)), tcx.mk_bare_fn(ty::BareFnTy {
 286                 unsafety: ast::Unsafety::Normal,
 287                 abi: abi::Rust,
 288                 sig: ty::Binder(ty::FnSig {
 289                     inputs: vec!(
 290                         tcx.types.int,
 291                         ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, tcx.types.u8))
 292                     ),
 293                     output: ty::FnConverging(tcx.types.int),
 294                     variadic: false,
 295                 }),
 296             }));
 297
 298             require_same_types(tcx, None, false, start_span, start_t, se_ty,
 299                 || {
 300                     format!("start function expects type: `{}`",
 301                             ppaux::ty_to_string(ccx.tcx, se_ty))
 302                 });
 303
 304         }
 305         _ => {
 306             tcx.sess.span_bug(start_span,
 307                               &format!("start has a non-function type: found \
 308                                        `{}`",
 309                                       ppaux::ty_to_string(tcx, start_t))[]);
 310         }
 311     }
 312 }
 313
 314 fn check_for_entry_fn(ccx: &CrateCtxt) {
 315     let tcx = ccx.tcx;
 316     match *tcx.sess.entry_fn.borrow() {
 317         Some((id, sp)) => match tcx.sess.entry_type.get() {
 318             Some(config::EntryMain) => check_main_fn_ty(ccx, id, sp),
 319             Some(config::EntryStart) => check_start_fn_ty(ccx, id, sp),
 320             Some(config::EntryNone) => {}
 321             None => tcx.sess.bug("entry function without a type")
 322         },
 323         None => {}
 324     }
 325 }
 326
 327 pub fn check_crate(tcx: &ty::ctxt, trait_map: ty::TraitMap) {
 328     let time_passes = tcx.sess.time_passes();
 329     let ccx = CrateCtxt {
 330         trait_map: trait_map,
 331         all_traits: RefCell::new(None),
 332         tcx: tcx
 333     };
 334
 335     time(time_passes, "type collecting", (), |_|
 336          collect::collect_item_types(tcx));
 337
 338     // this ensures that later parts of type checking can assume that items
 339     // have valid types and not error
 340     tcx.sess.abort_if_errors();
 341
 342     time(time_passes, "variance inference", (), |_|
 343          variance::infer_variance(tcx));
 344
 345     time(time_passes, "coherence checking", (), |_|
 346         coherence::check_coherence(&ccx));
 347
 348     time(time_passes, "type checking", (), |_|
 349         check::check_item_types(&ccx));
 350
 351     check_for_entry_fn(&ccx);
 352     tcx.sess.abort_if_errors();
 353 }