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