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