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