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_syntax)]
  78 #![feature(collections)]
  79 #![feature(core)]
  80 #![feature(int_uint)]
  81 #![feature(quote)]
  82 #![feature(rustc_diagnostic_macros)]
  83 #![feature(rustc_private)]
  84 #![feature(slicing_syntax, unsafe_destructor)]
  85 #![feature(staged_api)]
  86 #![feature(std_misc)]
  87
  88 #[macro_use] extern crate log;
  89 #[macro_use] extern crate syntax;
  90
  91 extern crate arena;
  92 extern crate fmt_macros;
  93 extern crate rustc;
  94
  95 pub use rustc::lint;
  96 pub use rustc::metadata;
  97 pub use rustc::middle;
  98 pub use rustc::session;
  99 pub use rustc::util;
 100
 101 use middle::def;
 102 use middle::infer;
 103 use middle::subst;
 104 use middle::subst::VecPerParamSpace;
 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 no_params<'tcx>(t: Ty<'tcx>) -> ty::TypeScheme<'tcx> {
 180     ty::TypeScheme {
 181         generics: ty::Generics {
 182             types: VecPerParamSpace::empty(),
 183             regions: VecPerParamSpace::empty(),
 184             predicates: VecPerParamSpace::empty(),
 185         },
 186         ty: t
 187     }
 188 }
 189
 190 fn require_same_types<'a, 'tcx, M>(tcx: &ty::ctxt<'tcx>,
 191                                    maybe_infcx: Option<&infer::InferCtxt<'a, 'tcx>>,
 192                                    t1_is_expected: bool,
 193                                    span: Span,
 194                                    t1: Ty<'tcx>,
 195                                    t2: Ty<'tcx>,
 196                                    msg: M)
 197                                    -> bool where
 198     M: FnOnce() -> String,
 199 {
 200     let result = match maybe_infcx {
 201         None => {
 202             let infcx = infer::new_infer_ctxt(tcx);
 203             infer::mk_eqty(&infcx, t1_is_expected, infer::Misc(span), t1, t2)
 204         }
 205         Some(infcx) => {
 206             infer::mk_eqty(infcx, t1_is_expected, infer::Misc(span), t1, t2)
 207         }
 208     };
 209
 210     match result {
 211         Ok(_) => true,
 212         Err(ref terr) => {
 213             span_err!(tcx.sess, span, E0211,
 214                               "{}: {}",
 215                                       msg(),
 216                                       ty::type_err_to_str(tcx,
 217                                                           terr));
 218             ty::note_and_explain_type_err(tcx, terr);
 219             false
 220         }
 221     }
 222 }
 223
 224 fn check_main_fn_ty(ccx: &CrateCtxt,
 225                     main_id: ast::NodeId,
 226                     main_span: Span) {
 227     let tcx = ccx.tcx;
 228     let main_t = ty::node_id_to_type(tcx, main_id);
 229     match main_t.sty {
 230         ty::ty_bare_fn(..) => {
 231             match tcx.map.find(main_id) {
 232                 Some(ast_map::NodeItem(it)) => {
 233                     match it.node {
 234                         ast::ItemFn(_, _, _, ref ps, _)
 235                         if ps.is_parameterized() => {
 236                             span_err!(ccx.tcx.sess, main_span, E0131,
 237                                       "main function is not allowed to have type parameters");
 238                             return;
 239                         }
 240                         _ => ()
 241                     }
 242                 }
 243                 _ => ()
 244             }
 245             let se_ty = ty::mk_bare_fn(tcx, Some(local_def(main_id)), tcx.mk_bare_fn(ty::BareFnTy {
 246                 unsafety: ast::Unsafety::Normal,
 247                 abi: abi::Rust,
 248                 sig: ty::Binder(ty::FnSig {
 249                     inputs: Vec::new(),
 250                     output: ty::FnConverging(ty::mk_nil(tcx)),
 251                     variadic: false
 252                 })
 253             }));
 254
 255             require_same_types(tcx, None, false, main_span, main_t, se_ty,
 256                 || {
 257                     format!("main function expects type: `{}`",
 258                             ppaux::ty_to_string(ccx.tcx, se_ty))
 259                 });
 260         }
 261         _ => {
 262             tcx.sess.span_bug(main_span,
 263                               &format!("main has a non-function type: found \
 264                                        `{}`",
 265                                       ppaux::ty_to_string(tcx,
 266                                                        main_t))[]);
 267         }
 268     }
 269 }
 270
 271 fn check_start_fn_ty(ccx: &CrateCtxt,
 272                      start_id: ast::NodeId,
 273                      start_span: Span) {
 274     let tcx = ccx.tcx;
 275     let start_t = ty::node_id_to_type(tcx, start_id);
 276     match start_t.sty {
 277         ty::ty_bare_fn(..) => {
 278             match tcx.map.find(start_id) {
 279                 Some(ast_map::NodeItem(it)) => {
 280                     match it.node {
 281                         ast::ItemFn(_,_,_,ref ps,_)
 282                         if ps.is_parameterized() => {
 283                             span_err!(tcx.sess, start_span, E0132,
 284                                       "start function is not allowed to have type parameters");
 285                             return;
 286                         }
 287                         _ => ()
 288                     }
 289                 }
 290                 _ => ()
 291             }
 292
 293             let se_ty = ty::mk_bare_fn(tcx, Some(local_def(start_id)), tcx.mk_bare_fn(ty::BareFnTy {
 294                 unsafety: ast::Unsafety::Normal,
 295                 abi: abi::Rust,
 296                 sig: ty::Binder(ty::FnSig {
 297                     inputs: vec!(
 298                         tcx.types.int,
 299                         ty::mk_imm_ptr(tcx, ty::mk_imm_ptr(tcx, tcx.types.u8))
 300                     ),
 301                     output: ty::FnConverging(tcx.types.int),
 302                     variadic: false,
 303                 }),
 304             }));
 305
 306             require_same_types(tcx, None, false, start_span, start_t, se_ty,
 307                 || {
 308                     format!("start function expects type: `{}`",
 309                             ppaux::ty_to_string(ccx.tcx, se_ty))
 310                 });
 311
 312         }
 313         _ => {
 314             tcx.sess.span_bug(start_span,
 315                               &format!("start has a non-function type: found \
 316                                        `{}`",
 317                                       ppaux::ty_to_string(tcx, start_t))[]);
 318         }
 319     }
 320 }
 321
 322 fn check_for_entry_fn(ccx: &CrateCtxt) {
 323     let tcx = ccx.tcx;
 324     match *tcx.sess.entry_fn.borrow() {
 325         Some((id, sp)) => match tcx.sess.entry_type.get() {
 326             Some(config::EntryMain) => check_main_fn_ty(ccx, id, sp),
 327             Some(config::EntryStart) => check_start_fn_ty(ccx, id, sp),
 328             Some(config::EntryNone) => {}
 329             None => tcx.sess.bug("entry function without a type")
 330         },
 331         None => {}
 332     }
 333 }
 334
 335 pub fn check_crate(tcx: &ty::ctxt, trait_map: ty::TraitMap) {
 336     let time_passes = tcx.sess.time_passes();
 337     let ccx = CrateCtxt {
 338         trait_map: trait_map,
 339         all_traits: RefCell::new(None),
 340         tcx: tcx
 341     };
 342
 343     time(time_passes, "type collecting", (), |_|
 344          collect::collect_item_types(tcx));
 345
 346     // this ensures that later parts of type checking can assume that items
 347     // have valid types and not error
 348     tcx.sess.abort_if_errors();
 349
 350     time(time_passes, "variance inference", (), |_|
 351          variance::infer_variance(tcx));
 352
 353     time(time_passes, "coherence checking", (), |_|
 354         coherence::check_coherence(&ccx));
 355
 356     time(time_passes, "type checking", (), |_|
 357         check::check_item_types(&ccx));
 358
 359     check_for_entry_fn(&ccx);
 360     tcx.sess.abort_if_errors();
 361 }