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", issue = "27812")]
  68 #![crate_type = "dylib"]
  69 #![crate_type = "rlib"]
  70 #![doc(html_logo_url = "https://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
  71       html_favicon_url = "https://doc.rust-lang.org/favicon.ico",
  72       html_root_url = "https://doc.rust-lang.org/nightly/")]
  73 #![cfg_attr(not(stage0), deny(warnings))]
  74
  75 #![allow(non_camel_case_types)]
  76
  77 #![feature(box_patterns)]
  78 #![feature(box_syntax)]
  79 #![feature(quote)]
  80 #![feature(rustc_diagnostic_macros)]
  81 #![feature(rustc_private)]
  82 #![feature(staged_api)]
  83 #![feature(question_mark)]
  84
  85 #[macro_use] extern crate log;
  86 #[macro_use] extern crate syntax;
  87 extern crate syntax_pos;
  88
  89 extern crate arena;
  90 extern crate fmt_macros;
  91 #[macro_use] extern crate rustc;
  92 extern crate rustc_platform_intrinsics as intrinsics;
  93 extern crate rustc_back;
  94 extern crate rustc_const_math;
  95 extern crate rustc_const_eval;
  96 extern crate rustc_errors as errors;
  97
  98 pub use rustc::dep_graph;
  99 pub use rustc::hir;
 100 pub use rustc::lint;
 101 pub use rustc::middle;
 102 pub use rustc::session;
 103 pub use rustc::util;
 104
 105 use dep_graph::DepNode;
 106 use hir::map as hir_map;
 107 use rustc::infer::TypeOrigin;
 108 use rustc::ty::subst::Substs;
 109 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
 110 use rustc::traits::{self, Reveal};
 111 use session::{config, CompileResult};
 112 use util::common::time;
 113
 114 use syntax::ast;
 115 use syntax::abi::Abi;
 116 use syntax_pos::Span;
 117
 118 use std::cell::RefCell;
 119 use util::nodemap::NodeMap;
 120
 121 // NB: This module needs to be declared first so diagnostics are
 122 // registered before they are used.
 123 pub mod diagnostics;
 124
 125 pub mod check;
 126 pub mod check_unused;
 127 mod rscope;
 128 mod astconv;
 129 pub mod collect;
 130 mod constrained_type_params;
 131 pub mod coherence;
 132 pub mod variance;
 133
 134 pub struct TypeAndSubsts<'tcx> {
 135     pub substs: Substs<'tcx>,
 136     pub ty: Ty<'tcx>,
 137 }
 138
 139 pub struct CrateCtxt<'a, 'tcx: 'a> {
 140     ast_ty_to_ty_cache: RefCell<NodeMap<Ty<'tcx>>>,
 141
 142     /// A vector of every trait accessible in the whole crate
 143     /// (i.e. including those from subcrates). This is used only for
 144     /// error reporting, and so is lazily initialised and generally
 145     /// shouldn't taint the common path (hence the RefCell).
 146     pub all_traits: RefCell<Option<check::method::AllTraitsVec>>,
 147
 148     /// This stack is used to identify cycles in the user's source.
 149     /// Note that these cycles can cross multiple items.
 150     pub stack: RefCell<Vec<collect::AstConvRequest>>,
 151
 152     pub tcx: TyCtxt<'a, 'tcx, 'tcx>,
 153
 154     /// Obligations which will have to be checked at the end of
 155     /// type-checking, after all functions have been inferred.
 156     /// The key is the NodeId of the item the obligations were from.
 157     pub deferred_obligations: RefCell<NodeMap<Vec<traits::DeferredObligation<'tcx>>>>,
 158 }
 159
 160 // Functions that write types into the node type table
 161 fn write_ty_to_tcx<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, node_id: ast::NodeId, ty: Ty<'tcx>) {
 162     debug!("write_ty_to_tcx({}, {:?})", node_id,  ty);
 163     assert!(!ty.needs_infer());
 164     ccx.tcx.node_type_insert(node_id, ty);
 165 }
 166
 167 fn write_substs_to_tcx<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 168                                  node_id: ast::NodeId,
 169                                  item_substs: ty::ItemSubsts<'tcx>) {
 170     if !item_substs.is_noop() {
 171         debug!("write_substs_to_tcx({}, {:?})",
 172                node_id,
 173                item_substs);
 174
 175         assert!(!item_substs.substs.types.needs_infer());
 176
 177         ccx.tcx.tables.borrow_mut().item_substs.insert(node_id, item_substs);
 178     }
 179 }
 180
 181 fn require_c_abi_if_variadic(tcx: TyCtxt,
 182                              decl: &hir::FnDecl,
 183                              abi: Abi,
 184                              span: Span) {
 185     if decl.variadic && abi != Abi::C {
 186         let mut err = struct_span_err!(tcx.sess, span, E0045,
 187                   "variadic function must have C calling convention");
 188         err.span_label(span, &("variadics require C calling conventions").to_string())
 189             .emit();
 190     }
 191 }
 192
 193 fn require_same_types<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 194                                 origin: TypeOrigin,
 195                                 t1: Ty<'tcx>,
 196                                 t2: Ty<'tcx>)
 197                                 -> bool {
 198     ccx.tcx.infer_ctxt(None, None, Reveal::NotSpecializable).enter(|infcx| {
 199         if let Err(err) = infcx.eq_types(false, origin.clone(), t1, t2) {
 200             infcx.report_mismatched_types(origin, t1, t2, err);
 201             false
 202         } else {
 203             true
 204         }
 205     })
 206 }
 207
 208 fn check_main_fn_ty(ccx: &CrateCtxt,
 209                     main_id: ast::NodeId,
 210                     main_span: Span) {
 211     let tcx = ccx.tcx;
 212     let main_t = tcx.node_id_to_type(main_id);
 213     match main_t.sty {
 214         ty::TyFnDef(..) => {
 215             match tcx.map.find(main_id) {
 216                 Some(hir_map::NodeItem(it)) => {
 217                     match it.node {
 218                         hir::ItemFn(_, _, _, _, ref generics, _) => {
 219                             if let Some(gen_span) = generics.span() {
 220                                 struct_span_err!(ccx.tcx.sess, gen_span, E0131,
 221                                          "main function is not allowed to have type parameters")
 222                                     .span_label(gen_span,
 223                                                 &format!("main cannot have type parameters"))
 224                                     .emit();
 225                                 return;
 226                             }
 227                         }
 228                         _ => ()
 229                     }
 230                 }
 231                 _ => ()
 232             }
 233             let main_def_id = tcx.map.local_def_id(main_id);
 234             let substs = tcx.mk_substs(Substs::empty());
 235             let se_ty = tcx.mk_fn_def(main_def_id, substs,
 236                                       tcx.mk_bare_fn(ty::BareFnTy {
 237                 unsafety: hir::Unsafety::Normal,
 238                 abi: Abi::Rust,
 239                 sig: ty::Binder(ty::FnSig {
 240                     inputs: Vec::new(),
 241                     output: ty::FnConverging(tcx.mk_nil()),
 242                     variadic: false
 243                 })
 244             }));
 245
 246             require_same_types(
 247                 ccx,
 248                 TypeOrigin::MainFunctionType(main_span),
 249                 main_t,
 250                 se_ty);
 251         }
 252         _ => {
 253             span_bug!(main_span,
 254                       "main has a non-function type: found `{}`",
 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 = tcx.node_id_to_type(start_id);
 265     match start_t.sty {
 266         ty::TyFnDef(..) => {
 267             match tcx.map.find(start_id) {
 268                 Some(hir_map::NodeItem(it)) => {
 269                     match it.node {
 270                         hir::ItemFn(_,_,_,_,ref ps,_)
 271                         if ps.is_parameterized() => {
 272                             let sp = if let Some(sp) = ps.span() { sp } else { start_span };
 273                             struct_span_err!(tcx.sess, sp, E0132,
 274                                 "start function is not allowed to have type parameters")
 275                                 .span_label(sp,
 276                                             &format!("start function cannot have type parameters"))
 277                                 .emit();
 278                             return;
 279                         }
 280                         _ => ()
 281                     }
 282                 }
 283                 _ => ()
 284             }
 285
 286             let start_def_id = ccx.tcx.map.local_def_id(start_id);
 287             let substs = tcx.mk_substs(Substs::empty());
 288             let se_ty = tcx.mk_fn_def(start_def_id, substs,
 289                                       tcx.mk_bare_fn(ty::BareFnTy {
 290                 unsafety: hir::Unsafety::Normal,
 291                 abi: Abi::Rust,
 292                 sig: ty::Binder(ty::FnSig {
 293                     inputs: vec!(
 294                         tcx.types.isize,
 295                         tcx.mk_imm_ptr(tcx.mk_imm_ptr(tcx.types.u8))
 296                     ),
 297                     output: ty::FnConverging(tcx.types.isize),
 298                     variadic: false,
 299                 }),
 300             }));
 301
 302             require_same_types(
 303                 ccx,
 304                 TypeOrigin::StartFunctionType(start_span),
 305                 start_t,
 306                 se_ty);
 307         }
 308         _ => {
 309             span_bug!(start_span,
 310                       "start has a non-function type: found `{}`",
 311                       start_t);
 312         }
 313     }
 314 }
 315
 316 fn check_for_entry_fn(ccx: &CrateCtxt) {
 317     let tcx = ccx.tcx;
 318     let _task = tcx.dep_graph.in_task(DepNode::CheckEntryFn);
 319     if let Some((id, sp)) = *tcx.sess.entry_fn.borrow() {
 320         match tcx.sess.entry_type.get() {
 321             Some(config::EntryMain) => check_main_fn_ty(ccx, id, sp),
 322             Some(config::EntryStart) => check_start_fn_ty(ccx, id, sp),
 323             Some(config::EntryNone) => {}
 324             None => bug!("entry function without a type")
 325         }
 326     }
 327 }
 328
 329 pub fn check_crate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>)
 330                              -> CompileResult {
 331     let time_passes = tcx.sess.time_passes();
 332     let ccx = CrateCtxt {
 333         ast_ty_to_ty_cache: RefCell::new(NodeMap()),
 334         all_traits: RefCell::new(None),
 335         stack: RefCell::new(Vec::new()),
 336         tcx: tcx,
 337         deferred_obligations: RefCell::new(NodeMap()),
 338     };
 339
 340     // this ensures that later parts of type checking can assume that items
 341     // have valid types and not error
 342     tcx.sess.track_errors(|| {
 343         time(time_passes, "type collecting", ||
 344              collect::collect_item_types(&ccx));
 345
 346     })?;
 347
 348     time(time_passes, "variance inference", ||
 349          variance::infer_variance(tcx));
 350
 351     tcx.sess.track_errors(|| {
 352       time(time_passes, "coherence checking", ||
 353           coherence::check_coherence(&ccx));
 354     })?;
 355
 356     time(time_passes, "wf checking", || check::check_wf_new(&ccx))?;
 357
 358     time(time_passes, "item-types checking", || check::check_item_types(&ccx))?;
 359
 360     time(time_passes, "item-bodies checking", || check::check_item_bodies(&ccx))?;
 361
 362     time(time_passes, "drop-impl checking", || check::check_drop_impls(&ccx))?;
 363
 364     check_unused::check_crate(tcx);
 365     check_for_entry_fn(&ccx);
 366
 367     let err_count = tcx.sess.err_count();
 368     if err_count == 0 {
 369         Ok(())
 370     } else {
 371         Err(err_count)
 372     }
 373 }
 374
 375 __build_diagnostic_array! { librustc_typeck, DIAGNOSTICS }