src/librustc/middle/typeck/mod.rs

   1 // Copyright 2012 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 two major
  23 phases: collect and check.  The collect phase passes over all items and
  24 determines their type, without examining their "innards".  The check phase
  25 then checks function bodies and so forth.
  26
  27 Within the check phase, we check each function body one at a time (bodies of
  28 function expressions are checked as part of the containing function).
  29 Inference is used to supply types wherever they are unknown. The actual
  30 checking of a function itself has several phases (check, regionck, writeback),
  31 as discussed in the documentation for the `check` module.
  32
  33 The type checker is defined into various submodules which are documented
  34 independently:
  35
  36 - astconv: converts the AST representation of types
  37   into the `ty` representation
  38
  39 - collect: computes the types of each top-level item and enters them into
  40   the `cx.tcache` table for later use
  41
  42 - check: walks over function bodies and type checks them, inferring types for
  43   local variables, type parameters, etc as necessary.
  44
  45 - infer: finds the types to use for each type variable such that
  46   all subtyping and assignment constraints are met.  In essence, the check
  47   module specifies the constraints, and the infer module solves them.
  48
  49 */
  50
  51 use driver::session;
  52
  53 use middle::resolve;
  54 use middle::ty;
  55 use util::common::time;
  56 use util::ppaux::Repr;
  57 use util::ppaux;
  58
  59 use core::hashmap::HashMap;
  60 use std::list::List;
  61 use std::list;
  62 use syntax::codemap::span;
  63 use syntax::print::pprust::*;
  64 use syntax::{ast, ast_map, abi};
  65 use syntax::opt_vec;
  66
  67 #[path = "check/mod.rs"]
  68 pub mod check;
  69 pub mod rscope;
  70 pub mod astconv;
  71 #[path = "infer/mod.rs"]
  72 pub mod infer;
  73 pub mod collect;
  74 pub mod coherence;
  75
  76 #[auto_encode]
  77 #[auto_decode]
  78 pub enum method_origin {
  79     // supertrait method invoked on "self" inside a default method
  80     // first field is supertrait ID;
  81     // second field is method index (relative to the *supertrait*
  82     // method list)
  83     method_super(ast::def_id, uint),
  84
  85     // fully statically resolved method
  86     method_static(ast::def_id),
  87
  88     // method invoked on a type parameter with a bounded trait
  89     method_param(method_param),
  90
  91     // method invoked on a trait instance
  92     method_trait(ast::def_id, uint, ty::TraitStore),
  93
  94     // method invoked on "self" inside a default method
  95     method_self(ast::def_id, uint)
  96
  97 }
  98
  99 // details for a method invoked with a receiver whose type is a type parameter
 100 // with a bounded trait.
 101 #[auto_encode]
 102 #[auto_decode]
 103 pub struct method_param {
 104     // the trait containing the method to be invoked
 105     trait_id: ast::def_id,
 106
 107     // index of the method to be invoked amongst the trait's methods
 108     method_num: uint,
 109
 110     // index of the type parameter (from those that are in scope) that is
 111     // the type of the receiver
 112     param_num: uint,
 113
 114     // index of the bound for this type parameter which specifies the trait
 115     bound_num: uint,
 116 }
 117
 118 pub struct method_map_entry {
 119     // the type of the self parameter, which is not reflected in the fn type
 120     // (FIXME #3446)
 121     self_arg: ty::arg,
 122
 123     // the mode of `self`
 124     self_mode: ty::SelfMode,
 125
 126     // the type of explicit self on the method
 127     explicit_self: ast::self_ty_,
 128
 129     // method details being invoked
 130     origin: method_origin,
 131 }
 132
 133 // maps from an expression id that corresponds to a method call to the details
 134 // of the method to be invoked
 135 pub type method_map = @mut HashMap<ast::node_id, method_map_entry>;
 136
 137 // Resolutions for bounds of all parameters, left to right, for a given path.
 138 pub type vtable_res = @~[vtable_origin];
 139
 140 pub enum vtable_origin {
 141     /*
 142       Statically known vtable. def_id gives the class or impl item
 143       from whence comes the vtable, and tys are the type substs.
 144       vtable_res is the vtable itself
 145      */
 146     vtable_static(ast::def_id, ~[ty::t], vtable_res),
 147
 148     /*
 149       Dynamic vtable, comes from a parameter that has a bound on it:
 150       fn foo<T:quux,baz,bar>(a: T) -- a's vtable would have a
 151       vtable_param origin
 152
 153       The first uint is the param number (identifying T in the example),
 154       and the second is the bound number (identifying baz)
 155      */
 156     vtable_param(uint, uint)
 157 }
 158
 159 impl Repr for vtable_origin {
 160     fn repr(&self, tcx: ty::ctxt) -> ~str {
 161         match *self {
 162             vtable_static(def_id, ref tys, ref vtable_res) => {
 163                 fmt!("vtable_static(%?:%s, %s, %s)",
 164                      def_id,
 165                      ty::item_path_str(tcx, def_id),
 166                      tys.repr(tcx),
 167                      vtable_res.repr(tcx))
 168             }
 169
 170             vtable_param(x, y) => {
 171                 fmt!("vtable_param(%?, %?)", x, y)
 172             }
 173         }
 174     }
 175 }
 176
 177 pub type vtable_map = @mut HashMap<ast::node_id, vtable_res>;
 178
 179 pub struct CrateCtxt {
 180     // A mapping from method call sites to traits that have that method.
 181     trait_map: resolve::TraitMap,
 182     method_map: method_map,
 183     vtable_map: vtable_map,
 184     coherence_info: @coherence::CoherenceInfo,
 185     tcx: ty::ctxt
 186 }
 187
 188 // Functions that write types into the node type table
 189 pub fn write_ty_to_tcx(tcx: ty::ctxt, node_id: ast::node_id, ty: ty::t) {
 190     debug!("write_ty_to_tcx(%d, %s)", node_id, ppaux::ty_to_str(tcx, ty));
 191     assert!(!ty::type_needs_infer(ty));
 192     tcx.node_types.insert(node_id as uint, ty);
 193 }
 194 pub fn write_substs_to_tcx(tcx: ty::ctxt,
 195                            node_id: ast::node_id,
 196                            substs: ~[ty::t]) {
 197     if substs.len() > 0u {
 198         debug!("write_substs_to_tcx(%d, %?)", node_id,
 199                substs.map(|t| ppaux::ty_to_str(tcx, *t)));
 200         assert!(substs.all(|t| !ty::type_needs_infer(*t)));
 201         tcx.node_type_substs.insert(node_id, substs);
 202     }
 203 }
 204 pub fn write_tpt_to_tcx(tcx: ty::ctxt,
 205                         node_id: ast::node_id,
 206                         tpt: &ty::ty_param_substs_and_ty) {
 207     write_ty_to_tcx(tcx, node_id, tpt.ty);
 208     if !tpt.substs.tps.is_empty() {
 209         write_substs_to_tcx(tcx, node_id, copy tpt.substs.tps);
 210     }
 211 }
 212
 213 pub fn lookup_def_tcx(tcx: ty::ctxt, sp: span, id: ast::node_id) -> ast::def {
 214     match tcx.def_map.find(&id) {
 215       Some(&x) => x,
 216       _ => {
 217         tcx.sess.span_fatal(sp, ~"internal error looking up a definition")
 218       }
 219     }
 220 }
 221
 222 pub fn lookup_def_ccx(ccx: @mut CrateCtxt, sp: span, id: ast::node_id)
 223                    -> ast::def {
 224     lookup_def_tcx(ccx.tcx, sp, id)
 225 }
 226
 227 pub fn no_params(t: ty::t) -> ty::ty_param_bounds_and_ty {
 228     ty::ty_param_bounds_and_ty {
 229         generics: ty::Generics {type_param_defs: @~[],
 230                                 region_param: None},
 231         ty: t
 232     }
 233 }
 234
 235 pub fn require_same_types(
 236     tcx: ty::ctxt,
 237     maybe_infcx: Option<@mut infer::InferCtxt>,
 238     t1_is_expected: bool,
 239     span: span,
 240     t1: ty::t,
 241     t2: ty::t,
 242     msg: &fn() -> ~str) -> bool {
 243
 244     let l_tcx, l_infcx;
 245     match maybe_infcx {
 246       None => {
 247         l_tcx = tcx;
 248         l_infcx = infer::new_infer_ctxt(tcx);
 249       }
 250       Some(i) => {
 251         l_tcx = i.tcx;
 252         l_infcx = i;
 253       }
 254     }
 255
 256     match infer::mk_eqty(l_infcx, t1_is_expected, span, t1, t2) {
 257         result::Ok(()) => true,
 258         result::Err(ref terr) => {
 259             l_tcx.sess.span_err(span, msg() + ~": " +
 260                                 ty::type_err_to_str(l_tcx, terr));
 261             ty::note_and_explain_type_err(l_tcx, terr);
 262             false
 263         }
 264     }
 265 }
 266
 267 // a list of mapping from in-scope-region-names ("isr") to the
 268 // corresponding ty::Region
 269 pub type isr_alist = @List<(ty::bound_region, ty::Region)>;
 270
 271 trait get_and_find_region {
 272     fn get(&self, br: ty::bound_region) -> ty::Region;
 273     fn find(&self, br: ty::bound_region) -> Option<ty::Region>;
 274 }
 275
 276 impl get_and_find_region for isr_alist {
 277     fn get(&self, br: ty::bound_region) -> ty::Region {
 278         self.find(br).get()
 279     }
 280
 281     fn find(&self, br: ty::bound_region) -> Option<ty::Region> {
 282         for list::each(*self) |isr| {
 283             let (isr_br, isr_r) = *isr;
 284             if isr_br == br { return Some(isr_r); }
 285         }
 286         return None;
 287     }
 288 }
 289
 290 fn check_main_fn_ty(ccx: @mut CrateCtxt,
 291                     main_id: ast::node_id,
 292                     main_span: span) {
 293     let tcx = ccx.tcx;
 294     let main_t = ty::node_id_to_type(tcx, main_id);
 295     match ty::get(main_t).sty {
 296         ty::ty_bare_fn(ref fn_ty) => {
 297             match tcx.items.find(&main_id) {
 298                 Some(&ast_map::node_item(it,_)) => {
 299                     match it.node {
 300                         ast::item_fn(_, _, _, ref ps, _)
 301                         if ps.is_parameterized() => {
 302                             tcx.sess.span_err(
 303                                 main_span,
 304                                 ~"main function is not allowed \
 305                                   to have type parameters");
 306                             return;
 307                         }
 308                         _ => ()
 309                     }
 310                 }
 311                 _ => ()
 312             }
 313             let mut ok = ty::type_is_nil(fn_ty.sig.output);
 314             let num_args = vec::len(fn_ty.sig.inputs);
 315             ok &= num_args == 0u;
 316             if !ok {
 317                 tcx.sess.span_err(
 318                     main_span,
 319                     fmt!("Wrong type in main function: found `%s`, \
 320                           expected `fn() -> ()`",
 321                          ppaux::ty_to_str(tcx, main_t)));
 322             }
 323         }
 324         _ => {
 325             tcx.sess.span_bug(main_span,
 326                               ~"main has a non-function type: found `" +
 327                               ppaux::ty_to_str(tcx, main_t) + ~"`");
 328         }
 329     }
 330 }
 331
 332 fn check_start_fn_ty(ccx: @mut CrateCtxt,
 333                      start_id: ast::node_id,
 334                      start_span: span) {
 335     let tcx = ccx.tcx;
 336     let start_t = ty::node_id_to_type(tcx, start_id);
 337     match ty::get(start_t).sty {
 338         ty::ty_bare_fn(_) => {
 339             match tcx.items.find(&start_id) {
 340                 Some(&ast_map::node_item(it,_)) => {
 341                     match it.node {
 342                         ast::item_fn(_,_,_,ref ps,_)
 343                         if ps.is_parameterized() => {
 344                             tcx.sess.span_err(
 345                                 start_span,
 346                                 ~"start function is not allowed to have type \
 347                                 parameters");
 348                             return;
 349                         }
 350                         _ => ()
 351                     }
 352                 }
 353                 _ => ()
 354             }
 355
 356             fn arg(ty: ty::t) -> ty::arg {
 357                 ty::arg {
 358                     ty: ty
 359                 }
 360             }
 361
 362             let se_ty = ty::mk_bare_fn(tcx, ty::BareFnTy {
 363                 purity: ast::impure_fn,
 364                 abis: abi::AbiSet::Rust(),
 365                 sig: ty::FnSig {
 366                     bound_lifetime_names: opt_vec::Empty,
 367                     inputs: ~[
 368                         arg(ty::mk_int()),
 369                         arg(ty::mk_imm_ptr(tcx,
 370                                            ty::mk_imm_ptr(tcx, ty::mk_u8()))),
 371                         arg(ty::mk_imm_ptr(tcx, ty::mk_u8()))
 372                     ],
 373                     output: ty::mk_int()
 374                 }
 375             });
 376
 377             require_same_types(tcx, None, false, start_span, start_t, se_ty,
 378                 || fmt!("start function expects type: `%s`", ppaux::ty_to_str(ccx.tcx, se_ty)));
 379
 380         }
 381         _ => {
 382             tcx.sess.span_bug(start_span,
 383                               ~"start has a non-function type: found `" +
 384                               ppaux::ty_to_str(tcx, start_t) + ~"`");
 385         }
 386     }
 387 }
 388
 389 fn check_for_entry_fn(ccx: @mut CrateCtxt) {
 390     let tcx = ccx.tcx;
 391     if !*tcx.sess.building_library {
 392         match *tcx.sess.entry_fn {
 393           Some((id, sp)) => match *tcx.sess.entry_type {
 394               Some(session::EntryMain) => check_main_fn_ty(ccx, id, sp),
 395               Some(session::EntryStart) => check_start_fn_ty(ccx, id, sp),
 396               None => tcx.sess.bug(~"entry function without a type")
 397           },
 398           None => tcx.sess.err(~"entry function not found")
 399         }
 400     }
 401 }
 402
 403 pub fn check_crate(tcx: ty::ctxt,
 404                    trait_map: resolve::TraitMap,
 405                    crate: @ast::crate)
 406                 -> (method_map, vtable_map) {
 407     let time_passes = tcx.sess.time_passes();
 408     let ccx = @mut CrateCtxt {
 409         trait_map: trait_map,
 410         method_map: @mut HashMap::new(),
 411         vtable_map: @mut HashMap::new(),
 412         coherence_info: @coherence::CoherenceInfo(),
 413         tcx: tcx
 414     };
 415
 416     time(time_passes, ~"type collecting", ||
 417         collect::collect_item_types(ccx, crate));
 418
 419     time(time_passes, ~"method resolution", ||
 420         coherence::check_coherence(ccx, crate));
 421
 422     time(time_passes, ~"type checking", ||
 423         check::check_item_types(ccx, crate));
 424
 425     check_for_entry_fn(ccx);
 426     tcx.sess.abort_if_errors();
 427     (ccx.method_map, ccx.vtable_map)
 428 }
 429 //
 430 // Local Variables:
 431 // mode: rust
 432 // fill-column: 78;
 433 // indent-tabs-mode: nil
 434 // c-basic-offset: 4
 435 // buffer-file-coding-system: utf-8-unix
 436 // End:
 437 //