src/librustc_trans/trans/common.rs

   1 // Copyright 2012-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 #![allow(non_camel_case_types, non_snake_case)]
  12
  13 //! Code that is useful in various trans modules.
  14
  15 pub use self::ExprOrMethodCall::*;
  16
  17 use session::Session;
  18 use llvm;
  19 use llvm::{ValueRef, BasicBlockRef, BuilderRef, ContextRef};
  20 use llvm::{True, False, Bool};
  21 use middle::cfg;
  22 use middle::def;
  23 use middle::infer;
  24 use middle::lang_items::LangItem;
  25 use middle::mem_categorization as mc;
  26 use middle::region;
  27 use middle::subst::{self, Subst, Substs};
  28 use trans::base;
  29 use trans::build;
  30 use trans::cleanup;
  31 use trans::consts;
  32 use trans::datum;
  33 use trans::debuginfo;
  34 use trans::machine;
  35 use trans::monomorphize;
  36 use trans::type_::Type;
  37 use trans::type_of;
  38 use middle::traits;
  39 use middle::ty::{self, HasProjectionTypes, Ty};
  40 use middle::ty_fold;
  41 use middle::ty_fold::{TypeFolder, TypeFoldable};
  42 use util::ppaux::Repr;
  43 use util::nodemap::{FnvHashMap, NodeMap};
  44
  45 use arena::TypedArena;
  46 use libc::{c_uint, c_char};
  47 use std::c_str::ToCStr;
  48 use std::cell::{Cell, RefCell};
  49 use std::vec::Vec;
  50 use syntax::ast::Ident;
  51 use syntax::ast;
  52 use syntax::ast_map::{PathElem, PathName};
  53 use syntax::codemap::Span;
  54 use syntax::parse::token::InternedString;
  55 use syntax::parse::token;
  56 use util::common::memoized;
  57 use util::nodemap::FnvHashSet;
  58
  59 pub use trans::context::CrateContext;
  60
  61 // Is the type's representation size known at compile time?
  62 pub fn type_is_sized<'tcx>(cx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
  63     ty::type_contents(cx, ty).is_sized(cx)
  64 }
  65
  66 pub fn lltype_is_sized<'tcx>(cx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
  67     match ty.sty {
  68         ty::ty_open(_) => true,
  69         _ => type_is_sized(cx, ty),
  70     }
  71 }
  72
  73 pub fn type_is_fat_ptr<'tcx>(cx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
  74     match ty.sty {
  75         ty::ty_ptr(ty::mt{ty, ..}) |
  76         ty::ty_rptr(_, ty::mt{ty, ..}) |
  77         ty::ty_uniq(ty) => {
  78             !type_is_sized(cx, ty)
  79         }
  80         _ => {
  81             false
  82         }
  83     }
  84 }
  85
  86 // Return the smallest part of `ty` which is unsized. Fails if `ty` is sized.
  87 // 'Smallest' here means component of the static representation of the type; not
  88 // the size of an object at runtime.
  89 pub fn unsized_part_of_type<'tcx>(cx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
  90     match ty.sty {
  91         ty::ty_str | ty::ty_trait(..) | ty::ty_vec(..) => ty,
  92         ty::ty_struct(def_id, substs) => {
  93             let unsized_fields: Vec<_> =
  94                 ty::struct_fields(cx, def_id, substs)
  95                 .iter()
  96                 .map(|f| f.mt.ty)
  97                 .filter(|ty| !type_is_sized(cx, *ty))
  98                 .collect();
  99
 100             // Exactly one of the fields must be unsized.
 101             assert!(unsized_fields.len() == 1);
 102
 103             unsized_part_of_type(cx, unsized_fields[0])
 104         }
 105         _ => {
 106             assert!(type_is_sized(cx, ty),
 107                     "unsized_part_of_type failed even though ty is unsized");
 108             panic!("called unsized_part_of_type with sized ty");
 109         }
 110     }
 111 }
 112
 113 // Some things don't need cleanups during unwinding because the
 114 // task can free them all at once later. Currently only things
 115 // that only contain scalars and shared boxes can avoid unwind
 116 // cleanups.
 117 pub fn type_needs_unwind_cleanup<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, ty: Ty<'tcx>) -> bool {
 118     return memoized(ccx.needs_unwind_cleanup_cache(), ty, |ty| {
 119         type_needs_unwind_cleanup_(ccx.tcx(), ty, &mut FnvHashSet::new())
 120     });
 121
 122     fn type_needs_unwind_cleanup_<'tcx>(tcx: &ty::ctxt<'tcx>,
 123                                         ty: Ty<'tcx>,
 124                                         tycache: &mut FnvHashSet<Ty<'tcx>>)
 125                                         -> bool
 126     {
 127         // Prevent infinite recursion
 128         if !tycache.insert(ty) {
 129             return false;
 130         }
 131
 132         let mut needs_unwind_cleanup = false;
 133         ty::maybe_walk_ty(ty, |ty| {
 134             needs_unwind_cleanup |= match ty.sty {
 135                 ty::ty_bool | ty::ty_int(_) | ty::ty_uint(_) |
 136                 ty::ty_float(_) | ty::ty_tup(_) | ty::ty_ptr(_) => false,
 137
 138                 ty::ty_enum(did, substs) =>
 139                     ty::enum_variants(tcx, did).iter().any(|v|
 140                         v.args.iter().any(|&aty| {
 141                             let t = aty.subst(tcx, substs);
 142                             type_needs_unwind_cleanup_(tcx, t, tycache)
 143                         })
 144                     ),
 145
 146                 _ => true
 147             };
 148             !needs_unwind_cleanup
 149         });
 150         needs_unwind_cleanup
 151     }
 152 }
 153
 154 pub fn type_needs_drop<'tcx>(cx: &ty::ctxt<'tcx>,
 155                              ty: Ty<'tcx>)
 156                              -> bool {
 157     ty::type_contents(cx, ty).needs_drop(cx)
 158 }
 159
 160 fn type_is_newtype_immediate<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
 161                                        ty: Ty<'tcx>) -> bool {
 162     match ty.sty {
 163         ty::ty_struct(def_id, substs) => {
 164             let fields = ty::struct_fields(ccx.tcx(), def_id, substs);
 165             fields.len() == 1 &&
 166                 fields[0].name ==
 167                     token::special_idents::unnamed_field.name &&
 168                 type_is_immediate(ccx, fields[0].mt.ty)
 169         }
 170         _ => false
 171     }
 172 }
 173
 174 pub fn type_is_immediate<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, ty: Ty<'tcx>) -> bool {
 175     use trans::machine::llsize_of_alloc;
 176     use trans::type_of::sizing_type_of;
 177
 178     let tcx = ccx.tcx();
 179     let simple = ty::type_is_scalar(ty) ||
 180         ty::type_is_unique(ty) || ty::type_is_region_ptr(ty) ||
 181         type_is_newtype_immediate(ccx, ty) ||
 182         ty::type_is_simd(tcx, ty);
 183     if simple && !type_is_fat_ptr(tcx, ty) {
 184         return true;
 185     }
 186     if !type_is_sized(tcx, ty) {
 187         return false;
 188     }
 189     match ty.sty {
 190         ty::ty_struct(..) | ty::ty_enum(..) | ty::ty_tup(..) |
 191         ty::ty_unboxed_closure(..) => {
 192             let llty = sizing_type_of(ccx, ty);
 193             llsize_of_alloc(ccx, llty) <= llsize_of_alloc(ccx, ccx.int_type())
 194         }
 195         _ => type_is_zero_size(ccx, ty)
 196     }
 197 }
 198
 199 /// Identify types which have size zero at runtime.
 200 pub fn type_is_zero_size<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, ty: Ty<'tcx>) -> bool {
 201     use trans::machine::llsize_of_alloc;
 202     use trans::type_of::sizing_type_of;
 203     let llty = sizing_type_of(ccx, ty);
 204     llsize_of_alloc(ccx, llty) == 0
 205 }
 206
 207 /// Identifies types which we declare to be equivalent to `void` in C for the purpose of function
 208 /// return types. These are `()`, bot, and uninhabited enums. Note that all such types are also
 209 /// zero-size, but not all zero-size types use a `void` return type (in order to aid with C ABI
 210 /// compatibility).
 211 pub fn return_type_is_void(ccx: &CrateContext, ty: Ty) -> bool {
 212     ty::type_is_nil(ty) || ty::type_is_empty(ccx.tcx(), ty)
 213 }
 214
 215 /// Generates a unique symbol based off the name given. This is used to create
 216 /// unique symbols for things like closures.
 217 pub fn gensym_name(name: &str) -> PathElem {
 218     let num = token::gensym(name).uint();
 219     // use one colon which will get translated to a period by the mangler, and
 220     // we're guaranteed that `num` is globally unique for this crate.
 221     PathName(token::gensym(format!("{}:{}", name, num)[]))
 222 }
 223
 224 #[derive(Copy)]
 225 pub struct tydesc_info<'tcx> {
 226     pub ty: Ty<'tcx>,
 227     pub tydesc: ValueRef,
 228     pub size: ValueRef,
 229     pub align: ValueRef,
 230     pub name: ValueRef,
 231 }
 232
 233 /*
 234  * A note on nomenclature of linking: "extern", "foreign", and "upcall".
 235  *
 236  * An "extern" is an LLVM symbol we wind up emitting an undefined external
 237  * reference to. This means "we don't have the thing in this compilation unit,
 238  * please make sure you link it in at runtime". This could be a reference to
 239  * C code found in a C library, or rust code found in a rust crate.
 240  *
 241  * Most "externs" are implicitly declared (automatically) as a result of a
 242  * user declaring an extern _module_ dependency; this causes the rust driver
 243  * to locate an extern crate, scan its compilation metadata, and emit extern
 244  * declarations for any symbols used by the declaring crate.
 245  *
 246  * A "foreign" is an extern that references C (or other non-rust ABI) code.
 247  * There is no metadata to scan for extern references so in these cases either
 248  * a header-digester like bindgen, or manual function prototypes, have to
 249  * serve as declarators. So these are usually given explicitly as prototype
 250  * declarations, in rust code, with ABI attributes on them noting which ABI to
 251  * link via.
 252  *
 253  * An "upcall" is a foreign call generated by the compiler (not corresponding
 254  * to any user-written call in the code) into the runtime library, to perform
 255  * some helper task such as bringing a task to life, allocating memory, etc.
 256  *
 257  */
 258
 259 #[derive(Copy)]
 260 pub struct NodeInfo {
 261     pub id: ast::NodeId,
 262     pub span: Span,
 263 }
 264
 265 pub fn expr_info(expr: &ast::Expr) -> NodeInfo {
 266     NodeInfo { id: expr.id, span: expr.span }
 267 }
 268
 269 pub struct BuilderRef_res {
 270     pub b: BuilderRef,
 271 }
 272
 273 impl Drop for BuilderRef_res {
 274     fn drop(&mut self) {
 275         unsafe {
 276             llvm::LLVMDisposeBuilder(self.b);
 277         }
 278     }
 279 }
 280
 281 pub fn BuilderRef_res(b: BuilderRef) -> BuilderRef_res {
 282     BuilderRef_res {
 283         b: b
 284     }
 285 }
 286
 287 pub type ExternMap = FnvHashMap<String, ValueRef>;
 288
 289 pub fn validate_substs(substs: &Substs) {
 290     assert!(substs.types.all(|t| !ty::type_needs_infer(*t)));
 291 }
 292
 293 // work around bizarre resolve errors
 294 type RvalueDatum<'tcx> = datum::Datum<'tcx, datum::Rvalue>;
 295 type LvalueDatum<'tcx> = datum::Datum<'tcx, datum::Lvalue>;
 296
 297 // Function context.  Every LLVM function we create will have one of
 298 // these.
 299 pub struct FunctionContext<'a, 'tcx: 'a> {
 300     // The ValueRef returned from a call to llvm::LLVMAddFunction; the
 301     // address of the first instruction in the sequence of
 302     // instructions for this function that will go in the .text
 303     // section of the executable we're generating.
 304     pub llfn: ValueRef,
 305
 306     // always an empty parameter-environment
 307     pub param_env: ty::ParameterEnvironment<'a, 'tcx>,
 308
 309     // The environment argument in a closure.
 310     pub llenv: Option<ValueRef>,
 311
 312     // A pointer to where to store the return value. If the return type is
 313     // immediate, this points to an alloca in the function. Otherwise, it's a
 314     // pointer to the hidden first parameter of the function. After function
 315     // construction, this should always be Some.
 316     pub llretslotptr: Cell<Option<ValueRef>>,
 317
 318     // These pub elements: "hoisted basic blocks" containing
 319     // administrative activities that have to happen in only one place in
 320     // the function, due to LLVM's quirks.
 321     // A marker for the place where we want to insert the function's static
 322     // allocas, so that LLVM will coalesce them into a single alloca call.
 323     pub alloca_insert_pt: Cell<Option<ValueRef>>,
 324     pub llreturn: Cell<Option<BasicBlockRef>>,
 325
 326     // If the function has any nested return's, including something like:
 327     // fn foo() -> Option<Foo> { Some(Foo { x: return None }) }, then
 328     // we use a separate alloca for each return
 329     pub needs_ret_allocas: bool,
 330
 331     // The a value alloca'd for calls to upcalls.rust_personality. Used when
 332     // outputting the resume instruction.
 333     pub personality: Cell<Option<ValueRef>>,
 334
 335     // True if the caller expects this fn to use the out pointer to
 336     // return. Either way, your code should write into the slot llretslotptr
 337     // points to, but if this value is false, that slot will be a local alloca.
 338     pub caller_expects_out_pointer: bool,
 339
 340     // Maps the DefId's for local variables to the allocas created for
 341     // them in llallocas.
 342     pub lllocals: RefCell<NodeMap<LvalueDatum<'tcx>>>,
 343
 344     // Same as above, but for closure upvars
 345     pub llupvars: RefCell<NodeMap<ValueRef>>,
 346
 347     // The NodeId of the function, or -1 if it doesn't correspond to
 348     // a user-defined function.
 349     pub id: ast::NodeId,
 350
 351     // If this function is being monomorphized, this contains the type
 352     // substitutions used.
 353     pub param_substs: &'a Substs<'tcx>,
 354
 355     // The source span and nesting context where this function comes from, for
 356     // error reporting and symbol generation.
 357     pub span: Option<Span>,
 358
 359     // The arena that blocks are allocated from.
 360     pub block_arena: &'a TypedArena<BlockS<'a, 'tcx>>,
 361
 362     // This function's enclosing crate context.
 363     pub ccx: &'a CrateContext<'a, 'tcx>,
 364
 365     // Used and maintained by the debuginfo module.
 366     pub debug_context: debuginfo::FunctionDebugContext,
 367
 368     // Cleanup scopes.
 369     pub scopes: RefCell<Vec<cleanup::CleanupScope<'a, 'tcx>>>,
 370
 371     pub cfg: Option<cfg::CFG>,
 372 }
 373
 374 impl<'a, 'tcx> FunctionContext<'a, 'tcx> {
 375     pub fn arg_pos(&self, arg: uint) -> uint {
 376         let arg = self.env_arg_pos() + arg;
 377         if self.llenv.is_some() {
 378             arg + 1
 379         } else {
 380             arg
 381         }
 382     }
 383
 384     pub fn env_arg_pos(&self) -> uint {
 385         if self.caller_expects_out_pointer {
 386             1u
 387         } else {
 388             0u
 389         }
 390     }
 391
 392     pub fn cleanup(&self) {
 393         unsafe {
 394             llvm::LLVMInstructionEraseFromParent(self.alloca_insert_pt
 395                                                      .get()
 396                                                      .unwrap());
 397         }
 398     }
 399
 400     pub fn get_llreturn(&self) -> BasicBlockRef {
 401         if self.llreturn.get().is_none() {
 402
 403             self.llreturn.set(Some(unsafe {
 404                 "return".with_c_str(|buf| {
 405                     llvm::LLVMAppendBasicBlockInContext(self.ccx.llcx(), self.llfn, buf)
 406                 })
 407             }))
 408         }
 409
 410         self.llreturn.get().unwrap()
 411     }
 412
 413     pub fn get_ret_slot(&self, bcx: Block<'a, 'tcx>,
 414                         output: ty::FnOutput<'tcx>,
 415                         name: &str) -> ValueRef {
 416         if self.needs_ret_allocas {
 417             base::alloca_no_lifetime(bcx, match output {
 418                 ty::FnConverging(output_type) => type_of::type_of(bcx.ccx(), output_type),
 419                 ty::FnDiverging => Type::void(bcx.ccx())
 420             }, name)
 421         } else {
 422             self.llretslotptr.get().unwrap()
 423         }
 424     }
 425
 426     pub fn new_block(&'a self,
 427                      is_lpad: bool,
 428                      name: &str,
 429                      opt_node_id: Option<ast::NodeId>)
 430                      -> Block<'a, 'tcx> {
 431         unsafe {
 432             let llbb = name.with_c_str(|buf| {
 433                     llvm::LLVMAppendBasicBlockInContext(self.ccx.llcx(),
 434                                                         self.llfn,
 435                                                         buf)
 436                 });
 437             BlockS::new(llbb, is_lpad, opt_node_id, self)
 438         }
 439     }
 440
 441     pub fn new_id_block(&'a self,
 442                         name: &str,
 443                         node_id: ast::NodeId)
 444                         -> Block<'a, 'tcx> {
 445         self.new_block(false, name, Some(node_id))
 446     }
 447
 448     pub fn new_temp_block(&'a self,
 449                           name: &str)
 450                           -> Block<'a, 'tcx> {
 451         self.new_block(false, name, None)
 452     }
 453
 454     pub fn join_blocks(&'a self,
 455                        id: ast::NodeId,
 456                        in_cxs: &[Block<'a, 'tcx>])
 457                        -> Block<'a, 'tcx> {
 458         let out = self.new_id_block("join", id);
 459         let mut reachable = false;
 460         for bcx in in_cxs.iter() {
 461             if !bcx.unreachable.get() {
 462                 build::Br(*bcx, out.llbb);
 463                 reachable = true;
 464             }
 465         }
 466         if !reachable {
 467             build::Unreachable(out);
 468         }
 469         return out;
 470     }
 471
 472     pub fn monomorphize<T>(&self, value: &T) -> T
 473         where T : TypeFoldable<'tcx> + Repr<'tcx> + HasProjectionTypes + Clone
 474     {
 475         monomorphize::apply_param_substs(self.ccx.tcx(),
 476                                          self.param_substs,
 477                                          value)
 478     }
 479 }
 480
 481 // Basic block context.  We create a block context for each basic block
 482 // (single-entry, single-exit sequence of instructions) we generate from Rust
 483 // code.  Each basic block we generate is attached to a function, typically
 484 // with many basic blocks per function.  All the basic blocks attached to a
 485 // function are organized as a directed graph.
 486 pub struct BlockS<'blk, 'tcx: 'blk> {
 487     // The BasicBlockRef returned from a call to
 488     // llvm::LLVMAppendBasicBlock(llfn, name), which adds a basic
 489     // block to the function pointed to by llfn.  We insert
 490     // instructions into that block by way of this block context.
 491     // The block pointing to this one in the function's digraph.
 492     pub llbb: BasicBlockRef,
 493     pub terminated: Cell<bool>,
 494     pub unreachable: Cell<bool>,
 495
 496     // Is this block part of a landing pad?
 497     pub is_lpad: bool,
 498
 499     // AST node-id associated with this block, if any. Used for
 500     // debugging purposes only.
 501     pub opt_node_id: Option<ast::NodeId>,
 502
 503     // The function context for the function to which this block is
 504     // attached.
 505     pub fcx: &'blk FunctionContext<'blk, 'tcx>,
 506 }
 507
 508 pub type Block<'blk, 'tcx> = &'blk BlockS<'blk, 'tcx>;
 509
 510 impl<'blk, 'tcx> BlockS<'blk, 'tcx> {
 511     pub fn new(llbb: BasicBlockRef,
 512                is_lpad: bool,
 513                opt_node_id: Option<ast::NodeId>,
 514                fcx: &'blk FunctionContext<'blk, 'tcx>)
 515                -> Block<'blk, 'tcx> {
 516         fcx.block_arena.alloc(BlockS {
 517             llbb: llbb,
 518             terminated: Cell::new(false),
 519             unreachable: Cell::new(false),
 520             is_lpad: is_lpad,
 521             opt_node_id: opt_node_id,
 522             fcx: fcx
 523         })
 524     }
 525
 526     pub fn ccx(&self) -> &'blk CrateContext<'blk, 'tcx> {
 527         self.fcx.ccx
 528     }
 529     pub fn tcx(&self) -> &'blk ty::ctxt<'tcx> {
 530         self.fcx.ccx.tcx()
 531     }
 532     pub fn sess(&self) -> &'blk Session { self.fcx.ccx.sess() }
 533
 534     pub fn ident(&self, ident: Ident) -> String {
 535         token::get_ident(ident).get().to_string()
 536     }
 537
 538     pub fn node_id_to_string(&self, id: ast::NodeId) -> String {
 539         self.tcx().map.node_to_string(id).to_string()
 540     }
 541
 542     pub fn expr_to_string(&self, e: &ast::Expr) -> String {
 543         e.repr(self.tcx())
 544     }
 545
 546     pub fn def(&self, nid: ast::NodeId) -> def::Def {
 547         match self.tcx().def_map.borrow().get(&nid) {
 548             Some(v) => v.clone(),
 549             None => {
 550                 self.tcx().sess.bug(format!(
 551                     "no def associated with node id {}", nid)[]);
 552             }
 553         }
 554     }
 555
 556     pub fn val_to_string(&self, val: ValueRef) -> String {
 557         self.ccx().tn().val_to_string(val)
 558     }
 559
 560     pub fn llty_str(&self, ty: Type) -> String {
 561         self.ccx().tn().type_to_string(ty)
 562     }
 563
 564     pub fn ty_to_string(&self, t: Ty<'tcx>) -> String {
 565         t.repr(self.tcx())
 566     }
 567
 568     pub fn to_str(&self) -> String {
 569         format!("[block {:p}]", self)
 570     }
 571
 572     pub fn monomorphize<T>(&self, value: &T) -> T
 573         where T : TypeFoldable<'tcx> + Repr<'tcx> + HasProjectionTypes + Clone
 574     {
 575         monomorphize::apply_param_substs(self.tcx(),
 576                                          self.fcx.param_substs,
 577                                          value)
 578     }
 579 }
 580
 581 impl<'blk, 'tcx> mc::Typer<'tcx> for BlockS<'blk, 'tcx> {
 582     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
 583         self.tcx()
 584     }
 585
 586     fn node_ty(&self, id: ast::NodeId) -> mc::McResult<Ty<'tcx>> {
 587         Ok(node_id_type(self, id))
 588     }
 589
 590     fn expr_ty_adjusted(&self, expr: &ast::Expr) -> mc::McResult<Ty<'tcx>> {
 591         Ok(expr_ty_adjusted(self, expr))
 592     }
 593
 594     fn node_method_ty(&self, method_call: ty::MethodCall) -> Option<Ty<'tcx>> {
 595         self.tcx()
 596             .method_map
 597             .borrow()
 598             .get(&method_call)
 599             .map(|method| monomorphize_type(self, method.ty))
 600     }
 601
 602     fn node_method_origin(&self, method_call: ty::MethodCall)
 603                           -> Option<ty::MethodOrigin<'tcx>>
 604     {
 605         self.tcx()
 606             .method_map
 607             .borrow()
 608             .get(&method_call)
 609             .map(|method| method.origin.clone())
 610     }
 611
 612     fn adjustments<'a>(&'a self) -> &'a RefCell<NodeMap<ty::AutoAdjustment<'tcx>>> {
 613         &self.tcx().adjustments
 614     }
 615
 616     fn is_method_call(&self, id: ast::NodeId) -> bool {
 617         self.tcx().method_map.borrow().contains_key(&ty::MethodCall::expr(id))
 618     }
 619
 620     fn temporary_scope(&self, rvalue_id: ast::NodeId) -> Option<region::CodeExtent> {
 621         self.tcx().region_maps.temporary_scope(rvalue_id)
 622     }
 623
 624     fn upvar_borrow(&self, upvar_id: ty::UpvarId) -> Option<ty::UpvarBorrow> {
 625         Some(self.tcx().upvar_borrow_map.borrow()[upvar_id].clone())
 626     }
 627
 628     fn capture_mode(&self, closure_expr_id: ast::NodeId)
 629                     -> ast::CaptureClause {
 630         self.tcx().capture_modes.borrow()[closure_expr_id].clone()
 631     }
 632
 633     fn type_moves_by_default(&self, span: Span, ty: Ty<'tcx>) -> bool {
 634         self.fcx.param_env.type_moves_by_default(span, ty)
 635     }
 636 }
 637
 638 impl<'blk, 'tcx> ty::UnboxedClosureTyper<'tcx> for BlockS<'blk, 'tcx> {
 639     fn param_env<'a>(&'a self) -> &'a ty::ParameterEnvironment<'a, 'tcx> {
 640         &self.fcx.param_env
 641     }
 642
 643     fn unboxed_closure_kind(&self,
 644                             def_id: ast::DefId)
 645                             -> ty::UnboxedClosureKind
 646     {
 647         let typer = NormalizingUnboxedClosureTyper::new(self.tcx());
 648         typer.unboxed_closure_kind(def_id)
 649     }
 650
 651     fn unboxed_closure_type(&self,
 652                             def_id: ast::DefId,
 653                             substs: &subst::Substs<'tcx>)
 654                             -> ty::ClosureTy<'tcx>
 655     {
 656         let typer = NormalizingUnboxedClosureTyper::new(self.tcx());
 657         typer.unboxed_closure_type(def_id, substs)
 658     }
 659
 660     fn unboxed_closure_upvars(&self,
 661                               def_id: ast::DefId,
 662                               substs: &Substs<'tcx>)
 663                               -> Option<Vec<ty::UnboxedClosureUpvar<'tcx>>>
 664     {
 665         let typer = NormalizingUnboxedClosureTyper::new(self.tcx());
 666         typer.unboxed_closure_upvars(def_id, substs)
 667     }
 668 }
 669
 670 pub struct Result<'blk, 'tcx: 'blk> {
 671     pub bcx: Block<'blk, 'tcx>,
 672     pub val: ValueRef
 673 }
 674
 675 impl<'b, 'tcx> Result<'b, 'tcx> {
 676     pub fn new(bcx: Block<'b, 'tcx>, val: ValueRef) -> Result<'b, 'tcx> {
 677         Result {
 678             bcx: bcx,
 679             val: val,
 680         }
 681     }
 682 }
 683
 684 pub fn val_ty(v: ValueRef) -> Type {
 685     unsafe {
 686         Type::from_ref(llvm::LLVMTypeOf(v))
 687     }
 688 }
 689
 690 // LLVM constant constructors.
 691 pub fn C_null(t: Type) -> ValueRef {
 692     unsafe {
 693         llvm::LLVMConstNull(t.to_ref())
 694     }
 695 }
 696
 697 pub fn C_undef(t: Type) -> ValueRef {
 698     unsafe {
 699         llvm::LLVMGetUndef(t.to_ref())
 700     }
 701 }
 702
 703 pub fn C_integral(t: Type, u: u64, sign_extend: bool) -> ValueRef {
 704     unsafe {
 705         llvm::LLVMConstInt(t.to_ref(), u, sign_extend as Bool)
 706     }
 707 }
 708
 709 pub fn C_floating(s: &str, t: Type) -> ValueRef {
 710     unsafe {
 711         s.with_c_str(|buf| llvm::LLVMConstRealOfString(t.to_ref(), buf))
 712     }
 713 }
 714
 715 pub fn C_nil(ccx: &CrateContext) -> ValueRef {
 716     C_struct(ccx, &[], false)
 717 }
 718
 719 pub fn C_bool(ccx: &CrateContext, val: bool) -> ValueRef {
 720     C_integral(Type::i1(ccx), val as u64, false)
 721 }
 722
 723 pub fn C_i32(ccx: &CrateContext, i: i32) -> ValueRef {
 724     C_integral(Type::i32(ccx), i as u64, true)
 725 }
 726
 727 pub fn C_i64(ccx: &CrateContext, i: i64) -> ValueRef {
 728     C_integral(Type::i64(ccx), i as u64, true)
 729 }
 730
 731 pub fn C_u64(ccx: &CrateContext, i: u64) -> ValueRef {
 732     C_integral(Type::i64(ccx), i, false)
 733 }
 734
 735 pub fn C_int<I: AsI64>(ccx: &CrateContext, i: I) -> ValueRef {
 736     let v = i.as_i64();
 737
 738     match machine::llbitsize_of_real(ccx, ccx.int_type()) {
 739         32 => assert!(v < (1<<31) && v >= -(1<<31)),
 740         64 => {},
 741         n => panic!("unsupported target size: {}", n)
 742     }
 743
 744     C_integral(ccx.int_type(), v as u64, true)
 745 }
 746
 747 pub fn C_uint<I: AsU64>(ccx: &CrateContext, i: I) -> ValueRef {
 748     let v = i.as_u64();
 749
 750     match machine::llbitsize_of_real(ccx, ccx.int_type()) {
 751         32 => assert!(v < (1<<32)),
 752         64 => {},
 753         n => panic!("unsupported target size: {}", n)
 754     }
 755
 756     C_integral(ccx.int_type(), v, false)
 757 }
 758
 759 pub trait AsI64 { fn as_i64(self) -> i64; }
 760 pub trait AsU64 { fn as_u64(self) -> u64; }
 761
 762 // FIXME: remove the intptr conversions, because they
 763 // are host-architecture-dependent
 764 impl AsI64 for i64 { fn as_i64(self) -> i64 { self as i64 }}
 765 impl AsI64 for i32 { fn as_i64(self) -> i64 { self as i64 }}
 766 impl AsI64 for int { fn as_i64(self) -> i64 { self as i64 }}
 767
 768 impl AsU64 for u64  { fn as_u64(self) -> u64 { self as u64 }}
 769 impl AsU64 for u32  { fn as_u64(self) -> u64 { self as u64 }}
 770 impl AsU64 for uint { fn as_u64(self) -> u64 { self as u64 }}
 771
 772 pub fn C_u8(ccx: &CrateContext, i: uint) -> ValueRef {
 773     C_integral(Type::i8(ccx), i as u64, false)
 774 }
 775
 776
 777 // This is a 'c-like' raw string, which differs from
 778 // our boxed-and-length-annotated strings.
 779 pub fn C_cstr(cx: &CrateContext, s: InternedString, null_terminated: bool) -> ValueRef {
 780     unsafe {
 781         match cx.const_cstr_cache().borrow().get(&s) {
 782             Some(&llval) => return llval,
 783             None => ()
 784         }
 785
 786         let sc = llvm::LLVMConstStringInContext(cx.llcx(),
 787                                                 s.get().as_ptr() as *const c_char,
 788                                                 s.get().len() as c_uint,
 789                                                 !null_terminated as Bool);
 790
 791         let gsym = token::gensym("str");
 792         let g = format!("str{}", gsym.uint()).with_c_str(|buf| {
 793             llvm::LLVMAddGlobal(cx.llmod(), val_ty(sc).to_ref(), buf)
 794         });
 795         llvm::LLVMSetInitializer(g, sc);
 796         llvm::LLVMSetGlobalConstant(g, True);
 797         llvm::SetLinkage(g, llvm::InternalLinkage);
 798
 799         cx.const_cstr_cache().borrow_mut().insert(s, g);
 800         g
 801     }
 802 }
 803
 804 // NB: Do not use `do_spill_noroot` to make this into a constant string, or
 805 // you will be kicked off fast isel. See issue #4352 for an example of this.
 806 pub fn C_str_slice(cx: &CrateContext, s: InternedString) -> ValueRef {
 807     let len = s.get().len();
 808     let cs = consts::ptrcast(C_cstr(cx, s, false), Type::i8p(cx));
 809     C_named_struct(cx.tn().find_type("str_slice").unwrap(), &[cs, C_uint(cx, len)])
 810 }
 811
 812 pub fn C_binary_slice(cx: &CrateContext, data: &[u8]) -> ValueRef {
 813     unsafe {
 814         let len = data.len();
 815         let lldata = C_bytes(cx, data);
 816
 817         let gsym = token::gensym("binary");
 818         let g = format!("binary{}", gsym.uint()).with_c_str(|buf| {
 819             llvm::LLVMAddGlobal(cx.llmod(), val_ty(lldata).to_ref(), buf)
 820         });
 821         llvm::LLVMSetInitializer(g, lldata);
 822         llvm::LLVMSetGlobalConstant(g, True);
 823         llvm::SetLinkage(g, llvm::InternalLinkage);
 824
 825         let cs = consts::ptrcast(g, Type::i8p(cx));
 826         C_struct(cx, &[cs, C_uint(cx, len)], false)
 827     }
 828 }
 829
 830 pub fn C_struct(cx: &CrateContext, elts: &[ValueRef], packed: bool) -> ValueRef {
 831     C_struct_in_context(cx.llcx(), elts, packed)
 832 }
 833
 834 pub fn C_struct_in_context(llcx: ContextRef, elts: &[ValueRef], packed: bool) -> ValueRef {
 835     unsafe {
 836         llvm::LLVMConstStructInContext(llcx,
 837                                        elts.as_ptr(), elts.len() as c_uint,
 838                                        packed as Bool)
 839     }
 840 }
 841
 842 pub fn C_named_struct(t: Type, elts: &[ValueRef]) -> ValueRef {
 843     unsafe {
 844         llvm::LLVMConstNamedStruct(t.to_ref(), elts.as_ptr(), elts.len() as c_uint)
 845     }
 846 }
 847
 848 pub fn C_array(ty: Type, elts: &[ValueRef]) -> ValueRef {
 849     unsafe {
 850         return llvm::LLVMConstArray(ty.to_ref(), elts.as_ptr(), elts.len() as c_uint);
 851     }
 852 }
 853
 854 pub fn C_bytes(cx: &CrateContext, bytes: &[u8]) -> ValueRef {
 855     C_bytes_in_context(cx.llcx(), bytes)
 856 }
 857
 858 pub fn C_bytes_in_context(llcx: ContextRef, bytes: &[u8]) -> ValueRef {
 859     unsafe {
 860         let ptr = bytes.as_ptr() as *const c_char;
 861         return llvm::LLVMConstStringInContext(llcx, ptr, bytes.len() as c_uint, True);
 862     }
 863 }
 864
 865 pub fn const_get_elt(cx: &CrateContext, v: ValueRef, us: &[c_uint])
 866                   -> ValueRef {
 867     unsafe {
 868         let r = llvm::LLVMConstExtractValue(v, us.as_ptr(), us.len() as c_uint);
 869
 870         debug!("const_get_elt(v={}, us={}, r={})",
 871                cx.tn().val_to_string(v), us, cx.tn().val_to_string(r));
 872
 873         return r;
 874     }
 875 }
 876
 877 pub fn is_const(v: ValueRef) -> bool {
 878     unsafe {
 879         llvm::LLVMIsConstant(v) == True
 880     }
 881 }
 882
 883 pub fn const_to_int(v: ValueRef) -> i64 {
 884     unsafe {
 885         llvm::LLVMConstIntGetSExtValue(v)
 886     }
 887 }
 888
 889 pub fn const_to_uint(v: ValueRef) -> u64 {
 890     unsafe {
 891         llvm::LLVMConstIntGetZExtValue(v)
 892     }
 893 }
 894
 895 pub fn is_undef(val: ValueRef) -> bool {
 896     unsafe {
 897         llvm::LLVMIsUndef(val) != False
 898     }
 899 }
 900
 901 #[allow(dead_code)] // potentially useful
 902 pub fn is_null(val: ValueRef) -> bool {
 903     unsafe {
 904         llvm::LLVMIsNull(val) != False
 905     }
 906 }
 907
 908 pub fn monomorphize_type<'blk, 'tcx>(bcx: &BlockS<'blk, 'tcx>, t: Ty<'tcx>) -> Ty<'tcx> {
 909     bcx.fcx.monomorphize(&t)
 910 }
 911
 912 pub fn node_id_type<'blk, 'tcx>(bcx: &BlockS<'blk, 'tcx>, id: ast::NodeId) -> Ty<'tcx> {
 913     let tcx = bcx.tcx();
 914     let t = ty::node_id_to_type(tcx, id);
 915     monomorphize_type(bcx, t)
 916 }
 917
 918 pub fn expr_ty<'blk, 'tcx>(bcx: &BlockS<'blk, 'tcx>, ex: &ast::Expr) -> Ty<'tcx> {
 919     node_id_type(bcx, ex.id)
 920 }
 921
 922 pub fn expr_ty_adjusted<'blk, 'tcx>(bcx: &BlockS<'blk, 'tcx>, ex: &ast::Expr) -> Ty<'tcx> {
 923     monomorphize_type(bcx, ty::expr_ty_adjusted(bcx.tcx(), ex))
 924 }
 925
 926 /// Attempts to resolve an obligation. The result is a shallow vtable resolution -- meaning that we
 927 /// do not (necessarily) resolve all nested obligations on the impl. Note that type check should
 928 /// guarantee to us that all nested obligations *could be* resolved if we wanted to.
 929 pub fn fulfill_obligation<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
 930                                     span: Span,
 931                                     trait_ref: ty::PolyTraitRef<'tcx>)
 932                                     -> traits::Vtable<'tcx, ()>
 933 {
 934     let tcx = ccx.tcx();
 935
 936     // Remove any references to regions; this helps improve caching.
 937     let trait_ref = ty_fold::erase_regions(tcx, trait_ref);
 938
 939     // First check the cache.
 940     match ccx.trait_cache().borrow().get(&trait_ref) {
 941         Some(vtable) => {
 942             info!("Cache hit: {}", trait_ref.repr(ccx.tcx()));
 943             return (*vtable).clone();
 944         }
 945         None => { }
 946     }
 947
 948     debug!("trans fulfill_obligation: trait_ref={}", trait_ref.repr(ccx.tcx()));
 949
 950     ty::populate_implementations_for_trait_if_necessary(tcx, trait_ref.def_id());
 951     let infcx = infer::new_infer_ctxt(tcx);
 952
 953     // Do the initial selection for the obligation. This yields the
 954     // shallow result we are looking for -- that is, what specific impl.
 955     let typer = NormalizingUnboxedClosureTyper::new(tcx);
 956     let mut selcx = traits::SelectionContext::new(&infcx, &typer);
 957     let obligation = traits::Obligation::new(traits::ObligationCause::dummy(),
 958                                              trait_ref.to_poly_trait_predicate());
 959     let selection = match selcx.select(&obligation) {
 960         Ok(Some(selection)) => selection,
 961         Ok(None) => {
 962             // Ambiguity can happen when monomorphizing during trans
 963             // expands to some humongo type that never occurred
 964             // statically -- this humongo type can then overflow,
 965             // leading to an ambiguous result. So report this as an
 966             // overflow bug, since I believe this is the only case
 967             // where ambiguity can result.
 968             debug!("Encountered ambiguity selecting `{}` during trans, \
 969                     presuming due to overflow",
 970                    trait_ref.repr(tcx));
 971             ccx.sess().span_fatal(
 972                 span,
 973                 "reached the recursion limit during monomorphization");
 974         }
 975         Err(e) => {
 976             tcx.sess.span_bug(
 977                 span,
 978                 format!("Encountered error `{}` selecting `{}` during trans",
 979                         e.repr(tcx),
 980                         trait_ref.repr(tcx))[])
 981         }
 982     };
 983
 984     // Currently, we use a fulfillment context to completely resolve
 985     // all nested obligations. This is because they can inform the
 986     // inference of the impl's type parameters.
 987     let mut fulfill_cx = traits::FulfillmentContext::new();
 988     let vtable = selection.map_move_nested(|predicate| {
 989         fulfill_cx.register_predicate_obligation(&infcx, predicate);
 990     });
 991     let vtable = drain_fulfillment_cx(span, &infcx, &mut fulfill_cx, &vtable);
 992
 993     info!("Cache miss: {}", trait_ref.repr(ccx.tcx()));
 994     ccx.trait_cache().borrow_mut().insert(trait_ref,
 995                                           vtable.clone());
 996
 997     vtable
 998 }
 999
1000 pub struct NormalizingUnboxedClosureTyper<'a,'tcx:'a> {
1001     param_env: ty::ParameterEnvironment<'a, 'tcx>
1002 }
1003
1004 impl<'a,'tcx> NormalizingUnboxedClosureTyper<'a,'tcx> {
1005     pub fn new(tcx: &'a ty::ctxt<'tcx>) -> NormalizingUnboxedClosureTyper<'a,'tcx> {
1006         // Parameter environment is used to give details about type parameters,
1007         // but since we are in trans, everything is fully monomorphized.
1008         NormalizingUnboxedClosureTyper { param_env: ty::empty_parameter_environment(tcx) }
1009     }
1010 }
1011
1012 impl<'a,'tcx> ty::UnboxedClosureTyper<'tcx> for NormalizingUnboxedClosureTyper<'a,'tcx> {
1013     fn param_env<'b>(&'b self) -> &'b ty::ParameterEnvironment<'b,'tcx> {
1014         &self.param_env
1015     }
1016
1017     fn unboxed_closure_kind(&self,
1018                             def_id: ast::DefId)
1019                             -> ty::UnboxedClosureKind
1020     {
1021         self.param_env.tcx.unboxed_closure_kind(def_id)
1022     }
1023
1024     fn unboxed_closure_type(&self,
1025                             def_id: ast::DefId,
1026                             substs: &subst::Substs<'tcx>)
1027                             -> ty::ClosureTy<'tcx>
1028     {
1029         // the substitutions in `substs` are already monomorphized,
1030         // but we still must normalize associated types
1031         let closure_ty = self.param_env.tcx.unboxed_closure_type(def_id, substs);
1032         monomorphize::normalize_associated_type(self.param_env.tcx, &closure_ty)
1033     }
1034
1035     fn unboxed_closure_upvars(&self,
1036                               def_id: ast::DefId,
1037                               substs: &Substs<'tcx>)
1038                               -> Option<Vec<ty::UnboxedClosureUpvar<'tcx>>>
1039     {
1040         // the substitutions in `substs` are already monomorphized,
1041         // but we still must normalize associated types
1042         let result = ty::unboxed_closure_upvars(&self.param_env, def_id, substs);
1043         monomorphize::normalize_associated_type(self.param_env.tcx, &result)
1044     }
1045 }
1046
1047 pub fn drain_fulfillment_cx<'a,'tcx,T>(span: Span,
1048                                        infcx: &infer::InferCtxt<'a,'tcx>,
1049                                        fulfill_cx: &mut traits::FulfillmentContext<'tcx>,
1050                                        result: &T)
1051                                        -> T
1052     where T : TypeFoldable<'tcx> + Repr<'tcx>
1053 {
1054     debug!("drain_fulfillment_cx(result={})",
1055            result.repr(infcx.tcx));
1056
1057     // In principle, we only need to do this so long as `result`
1058     // contains unbound type parameters. It could be a slight
1059     // optimization to stop iterating early.
1060     let typer = NormalizingUnboxedClosureTyper::new(infcx.tcx);
1061     match fulfill_cx.select_all_or_error(infcx, &typer) {
1062         Ok(()) => { }
1063         Err(errors) => {
1064             if errors.iter().all(|e| e.is_overflow()) {
1065                 // See Ok(None) case above.
1066                 infcx.tcx.sess.span_fatal(
1067                     span,
1068                     "reached the recursion limit during monomorphization");
1069             } else {
1070                 infcx.tcx.sess.span_bug(
1071                     span,
1072                     format!("Encountered errors `{}` fulfilling during trans",
1073                             errors.repr(infcx.tcx))[]);
1074             }
1075         }
1076     }
1077
1078     // Use freshen to simultaneously replace all type variables with
1079     // their bindings and replace all regions with 'static.  This is
1080     // sort of overkill because we do not expect there to be any
1081     // unbound type variables, hence no `TyFresh` types should ever be
1082     // inserted.
1083     result.fold_with(&mut infcx.freshener())
1084 }
1085
1086 // Key used to lookup values supplied for type parameters in an expr.
1087 #[derive(Copy, PartialEq, Show)]
1088 pub enum ExprOrMethodCall {
1089     // Type parameters for a path like `None::<int>`
1090     ExprId(ast::NodeId),
1091
1092     // Type parameters for a method call like `a.foo::<int>()`
1093     MethodCallKey(ty::MethodCall)
1094 }
1095
1096 pub fn node_id_substs<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
1097                                 node: ExprOrMethodCall,
1098                                 param_substs: &subst::Substs<'tcx>)
1099                                 -> subst::Substs<'tcx> {
1100     let tcx = ccx.tcx();
1101
1102     let substs = match node {
1103         ExprId(id) => {
1104             ty::node_id_item_substs(tcx, id).substs
1105         }
1106         MethodCallKey(method_call) => {
1107             (*tcx.method_map.borrow())[method_call].substs.clone()
1108         }
1109     };
1110
1111     if substs.types.any(|t| ty::type_needs_infer(*t)) {
1112         tcx.sess.bug(format!("type parameters for node {} include inference types: {}",
1113                              node, substs.repr(tcx))[]);
1114     }
1115
1116     monomorphize::apply_param_substs(tcx,
1117                                      param_substs,
1118                                      &substs.erase_regions())
1119 }
1120
1121 pub fn langcall(bcx: Block,
1122                 span: Option<Span>,
1123                 msg: &str,
1124                 li: LangItem)
1125                 -> ast::DefId {
1126     match bcx.tcx().lang_items.require(li) {
1127         Ok(id) => id,
1128         Err(s) => {
1129             let msg = format!("{} {}", msg, s);
1130             match span {
1131                 Some(span) => bcx.tcx().sess.span_fatal(span, msg[]),
1132                 None => bcx.tcx().sess.fatal(msg[]),
1133             }
1134         }
1135     }
1136 }