src/librustc/middle/trans/closure.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 use back::abi;
  13 use back::link::mangle_internal_name_by_path_and_seq;
  14 use driver::session::FullDebugInfo;
  15 use lib::llvm::ValueRef;
  16 use middle::moves;
  17 use middle::trans::base::*;
  18 use middle::trans::build::*;
  19 use middle::trans::common::*;
  20 use middle::trans::datum::{Datum, DatumBlock, Expr, Lvalue, rvalue_scratch_datum};
  21 use middle::trans::debuginfo;
  22 use middle::trans::expr;
  23 use middle::trans::type_of::*;
  24 use middle::trans::type_::Type;
  25 use middle::ty;
  26 use util::ppaux::Repr;
  27 use util::ppaux::ty_to_str;
  28
  29 use arena::TypedArena;
  30 use syntax::ast;
  31 use syntax::ast_util;
  32
  33 // ___Good to know (tm)__________________________________________________
  34 //
  35 // The layout of a closure environment in memory is
  36 // roughly as follows:
  37 //
  38 // struct rust_opaque_box {         // see rust_internal.h
  39 //   unsigned ref_count;            // only used for @fn()
  40 //   type_desc *tydesc;             // describes closure_data struct
  41 //   rust_opaque_box *prev;         // (used internally by memory alloc)
  42 //   rust_opaque_box *next;         // (used internally by memory alloc)
  43 //   struct closure_data {
  44 //       type_desc *bound_tdescs[]; // bound descriptors
  45 //       struct {
  46 //         upvar1_t upvar1;
  47 //         ...
  48 //         upvarN_t upvarN;
  49 //       } bound_data;
  50 //    }
  51 // };
  52 //
  53 // Note that the closure is itself a rust_opaque_box.  This is true
  54 // even for ~fn and ||, because we wish to keep binary compatibility
  55 // between all kinds of closures.  The allocation strategy for this
  56 // closure depends on the closure type.  For a sendfn, the closure
  57 // (and the referenced type descriptors) will be allocated in the
  58 // exchange heap.  For a fn, the closure is allocated in the task heap
  59 // and is reference counted.  For a block, the closure is allocated on
  60 // the stack.
  61 //
  62 // ## Opaque closures and the embedded type descriptor ##
  63 //
  64 // One interesting part of closures is that they encapsulate the data
  65 // that they close over.  So when I have a ptr to a closure, I do not
  66 // know how many type descriptors it contains nor what upvars are
  67 // captured within.  That means I do not know precisely how big it is
  68 // nor where its fields are located.  This is called an "opaque
  69 // closure".
  70 //
  71 // Typically an opaque closure suffices because we only manipulate it
  72 // by ptr.  The routine Type::at_box().ptr_to() returns an appropriate
  73 // type for such an opaque closure; it allows access to the box fields,
  74 // but not the closure_data itself.
  75 //
  76 // But sometimes, such as when cloning or freeing a closure, we need
  77 // to know the full information.  That is where the type descriptor
  78 // that defines the closure comes in handy.  We can use its take and
  79 // drop glue functions to allocate/free data as needed.
  80 //
  81 // ## Subtleties concerning alignment ##
  82 //
  83 // It is important that we be able to locate the closure data *without
  84 // knowing the kind of data that is being bound*.  This can be tricky
  85 // because the alignment requirements of the bound data affects the
  86 // alignment requires of the closure_data struct as a whole.  However,
  87 // right now this is a non-issue in any case, because the size of the
  88 // rust_opaque_box header is always a mutiple of 16-bytes, which is
  89 // the maximum alignment requirement we ever have to worry about.
  90 //
  91 // The only reason alignment matters is that, in order to learn what data
  92 // is bound, we would normally first load the type descriptors: but their
  93 // location is ultimately depend on their content!  There is, however, a
  94 // workaround.  We can load the tydesc from the rust_opaque_box, which
  95 // describes the closure_data struct and has self-contained derived type
  96 // descriptors, and read the alignment from there.   It's just annoying to
  97 // do.  Hopefully should this ever become an issue we'll have monomorphized
  98 // and type descriptors will all be a bad dream.
  99 //
 100 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 101
 102 pub enum EnvAction {
 103     /// Copy the value from this llvm ValueRef into the environment.
 104     EnvCopy,
 105
 106     /// Move the value from this llvm ValueRef into the environment.
 107     EnvMove,
 108
 109     /// Access by reference (used for stack closures).
 110     EnvRef
 111 }
 112
 113 pub struct EnvValue {
 114     action: EnvAction,
 115     datum: Datum<Lvalue>
 116 }
 117
 118 impl EnvAction {
 119     pub fn to_str(&self) -> ~str {
 120         match *self {
 121             EnvCopy => ~"EnvCopy",
 122             EnvMove => ~"EnvMove",
 123             EnvRef => ~"EnvRef"
 124         }
 125     }
 126 }
 127
 128 impl EnvValue {
 129     pub fn to_str(&self, ccx: &CrateContext) -> ~str {
 130         format!("{}({})", self.action.to_str(), self.datum.to_str(ccx))
 131     }
 132 }
 133
 134 // Given a closure ty, emits a corresponding tuple ty
 135 pub fn mk_closure_tys(tcx: &ty::ctxt,
 136                       bound_values: &[EnvValue])
 137                    -> ty::t {
 138     // determine the types of the values in the env.  Note that this
 139     // is the actual types that will be stored in the map, not the
 140     // logical types as the user sees them, so by-ref upvars must be
 141     // converted to ptrs.
 142     let bound_tys = bound_values.iter().map(|bv| {
 143         match bv.action {
 144             EnvCopy | EnvMove => bv.datum.ty,
 145             EnvRef => ty::mk_mut_ptr(tcx, bv.datum.ty)
 146         }
 147     }).collect();
 148     let cdata_ty = ty::mk_tup(tcx, bound_tys);
 149     debug!("cdata_ty={}", ty_to_str(tcx, cdata_ty));
 150     return cdata_ty;
 151 }
 152
 153 fn tuplify_box_ty(tcx: &ty::ctxt, t: ty::t) -> ty::t {
 154     let ptr = ty::mk_imm_ptr(tcx, ty::mk_i8());
 155     ty::mk_tup(tcx, vec!(ty::mk_uint(), ty::mk_nil_ptr(tcx), ptr, ptr, t))
 156 }
 157
 158 fn allocate_cbox<'a>(bcx: &'a Block<'a>,
 159                      sigil: ast::Sigil,
 160                      cdata_ty: ty::t)
 161                      -> Result<'a> {
 162     let _icx = push_ctxt("closure::allocate_cbox");
 163     let tcx = bcx.tcx();
 164
 165     // Allocate and initialize the box:
 166     match sigil {
 167         ast::ManagedSigil => {
 168             tcx.sess.bug("trying to trans allocation of @fn")
 169         }
 170         ast::OwnedSigil => {
 171             malloc_raw(bcx, cdata_ty, heap_exchange_closure)
 172         }
 173         ast::BorrowedSigil => {
 174             let cbox_ty = tuplify_box_ty(tcx, cdata_ty);
 175             let llbox = alloc_ty(bcx, cbox_ty, "__closure");
 176             rslt(bcx, llbox)
 177         }
 178     }
 179 }
 180
 181 pub struct ClosureResult<'a> {
 182     llbox: ValueRef,    // llvalue of ptr to closure
 183     cdata_ty: ty::t,    // type of the closure data
 184     bcx: &'a Block<'a>  // final bcx
 185 }
 186
 187 // Given a block context and a list of tydescs and values to bind
 188 // construct a closure out of them. If copying is true, it is a
 189 // heap allocated closure that copies the upvars into environment.
 190 // Otherwise, it is stack allocated and copies pointers to the upvars.
 191 pub fn store_environment<'a>(
 192                          bcx: &'a Block<'a>,
 193                          bound_values: Vec<EnvValue> ,
 194                          sigil: ast::Sigil)
 195                          -> ClosureResult<'a> {
 196     let _icx = push_ctxt("closure::store_environment");
 197     let ccx = bcx.ccx();
 198     let tcx = ccx.tcx();
 199
 200     // compute the type of the closure
 201     let cdata_ty = mk_closure_tys(tcx, bound_values.as_slice());
 202
 203     // cbox_ty has the form of a tuple: (a, b, c) we want a ptr to a
 204     // tuple.  This could be a ptr in uniq or a box or on stack,
 205     // whatever.
 206     let cbox_ty = tuplify_box_ty(tcx, cdata_ty);
 207     let cboxptr_ty = ty::mk_ptr(tcx, ty::mt {ty:cbox_ty, mutbl:ast::MutImmutable});
 208     let llboxptr_ty = type_of(ccx, cboxptr_ty);
 209
 210     // If there are no bound values, no point in allocating anything.
 211     if bound_values.is_empty() {
 212         return ClosureResult {llbox: C_null(llboxptr_ty),
 213                               cdata_ty: cdata_ty,
 214                               bcx: bcx};
 215     }
 216
 217     // allocate closure in the heap
 218     let Result {bcx: bcx, val: llbox} = allocate_cbox(bcx, sigil, cdata_ty);
 219
 220     let llbox = PointerCast(bcx, llbox, llboxptr_ty);
 221     debug!("tuplify_box_ty = {}", ty_to_str(tcx, cbox_ty));
 222
 223     // Copy expr values into boxed bindings.
 224     let mut bcx = bcx;
 225     for (i, bv) in bound_values.move_iter().enumerate() {
 226         debug!("Copy {} into closure", bv.to_str(ccx));
 227
 228         if ccx.sess().asm_comments() {
 229             add_comment(bcx, format!("Copy {} into closure",
 230                                   bv.to_str(ccx)));
 231         }
 232
 233         let bound_data = GEPi(bcx, llbox, [0u, abi::box_field_body, i]);
 234
 235         match bv.action {
 236             EnvCopy | EnvMove => {
 237                 bcx = bv.datum.store_to(bcx, bound_data);
 238             }
 239             EnvRef => {
 240                 Store(bcx, bv.datum.to_llref(), bound_data);
 241             }
 242         }
 243     }
 244
 245     ClosureResult { llbox: llbox, cdata_ty: cdata_ty, bcx: bcx }
 246 }
 247
 248 // Given a context and a list of upvars, build a closure. This just
 249 // collects the upvars and packages them up for store_environment.
 250 fn build_closure<'a>(bcx0: &'a Block<'a>,
 251                      cap_vars: &[moves::CaptureVar],
 252                      sigil: ast::Sigil)
 253                      -> ClosureResult<'a> {
 254     let _icx = push_ctxt("closure::build_closure");
 255
 256     // If we need to, package up the iterator body to call
 257     let bcx = bcx0;
 258
 259     // Package up the captured upvars
 260     let mut env_vals = Vec::new();
 261     for cap_var in cap_vars.iter() {
 262         debug!("Building closure: captured variable {:?}", *cap_var);
 263         let datum = expr::trans_local_var(bcx, cap_var.def);
 264         match cap_var.mode {
 265             moves::CapRef => {
 266                 assert_eq!(sigil, ast::BorrowedSigil);
 267                 env_vals.push(EnvValue {action: EnvRef,
 268                                         datum: datum});
 269             }
 270             moves::CapCopy => {
 271                 env_vals.push(EnvValue {action: EnvCopy,
 272                                         datum: datum});
 273             }
 274             moves::CapMove => {
 275                 env_vals.push(EnvValue {action: EnvMove,
 276                                         datum: datum});
 277             }
 278         }
 279     }
 280
 281     return store_environment(bcx, env_vals, sigil);
 282 }
 283
 284 // Given an enclosing block context, a new function context, a closure type,
 285 // and a list of upvars, generate code to load and populate the environment
 286 // with the upvars and type descriptors.
 287 fn load_environment<'a>(bcx: &'a Block<'a>, cdata_ty: ty::t,
 288                         cap_vars: &[moves::CaptureVar],
 289                         sigil: ast::Sigil) -> &'a Block<'a> {
 290     let _icx = push_ctxt("closure::load_environment");
 291
 292     // Don't bother to create the block if there's nothing to load
 293     if cap_vars.len() == 0 {
 294         return bcx;
 295     }
 296
 297     // Load a pointer to the closure data, skipping over the box header:
 298     let llcdata = at_box_body(bcx, cdata_ty, bcx.fcx.llenv.unwrap());
 299
 300     // Store the pointer to closure data in an alloca for debug info because that's what the
 301     // llvm.dbg.declare intrinsic expects
 302     let env_pointer_alloca = if bcx.sess().opts.debuginfo == FullDebugInfo {
 303         let alloc = alloc_ty(bcx, ty::mk_mut_ptr(bcx.tcx(), cdata_ty), "__debuginfo_env_ptr");
 304         Store(bcx, llcdata, alloc);
 305         Some(alloc)
 306     } else {
 307         None
 308     };
 309
 310     // Populate the upvars from the environment
 311     let mut i = 0u;
 312     for cap_var in cap_vars.iter() {
 313         let mut upvarptr = GEPi(bcx, llcdata, [0u, i]);
 314         match sigil {
 315             ast::BorrowedSigil => { upvarptr = Load(bcx, upvarptr); }
 316             ast::ManagedSigil | ast::OwnedSigil => {}
 317         }
 318         let def_id = ast_util::def_id_of_def(cap_var.def);
 319
 320         {
 321             let mut llupvars = bcx.fcx.llupvars.borrow_mut();
 322             llupvars.get().insert(def_id.node, upvarptr);
 323         }
 324
 325         for &env_pointer_alloca in env_pointer_alloca.iter() {
 326             debuginfo::create_captured_var_metadata(
 327                 bcx,
 328                 def_id.node,
 329                 cdata_ty,
 330                 env_pointer_alloca,
 331                 i,
 332                 sigil,
 333                 cap_var.span);
 334         }
 335
 336         i += 1u;
 337     }
 338
 339     bcx
 340 }
 341
 342 fn fill_fn_pair(bcx: &Block, pair: ValueRef, llfn: ValueRef, llenvptr: ValueRef) {
 343     Store(bcx, llfn, GEPi(bcx, pair, [0u, abi::fn_field_code]));
 344     let llenvptr = PointerCast(bcx, llenvptr, Type::i8p(bcx.ccx()));
 345     Store(bcx, llenvptr, GEPi(bcx, pair, [0u, abi::fn_field_box]));
 346 }
 347
 348 pub fn trans_expr_fn<'a>(
 349                      bcx: &'a Block<'a>,
 350                      sigil: ast::Sigil,
 351                      decl: &ast::FnDecl,
 352                      body: &ast::Block,
 353                      id: ast::NodeId,
 354                      dest: expr::Dest)
 355                      -> &'a Block<'a> {
 356     /*!
 357      *
 358      * Translates the body of a closure expression.
 359      *
 360      * - `sigil`
 361      * - `decl`
 362      * - `body`
 363      * - `id`: The id of the closure expression.
 364      * - `cap_clause`: information about captured variables, if any.
 365      * - `dest`: where to write the closure value, which must be a
 366          (fn ptr, env) pair
 367      */
 368
 369     let _icx = push_ctxt("closure::trans_expr_fn");
 370
 371     let dest_addr = match dest {
 372         expr::SaveIn(p) => p,
 373         expr::Ignore => {
 374             return bcx; // closure construction is non-side-effecting
 375         }
 376     };
 377
 378     let ccx = bcx.ccx();
 379     let fty = node_id_type(bcx, id);
 380     let f = match ty::get(fty).sty {
 381         ty::ty_closure(ref f) => f,
 382         _ => fail!("expected closure")
 383     };
 384
 385     let tcx = bcx.tcx();
 386     let s = tcx.map.with_path(id, |path| {
 387         mangle_internal_name_by_path_and_seq(path, "closure")
 388     });
 389     let llfn = decl_internal_rust_fn(ccx,
 390                                      true,
 391                                      f.sig.inputs.as_slice(),
 392                                      f.sig.output,
 393                                      s);
 394
 395     // set an inline hint for all closures
 396     set_inline_hint(llfn);
 397
 398     let cap_vars = ccx.maps.capture_map.borrow().get().get_copy(&id);
 399     let ClosureResult {llbox, cdata_ty, bcx} =
 400         build_closure(bcx, cap_vars.deref().as_slice(), sigil);
 401     trans_closure(ccx, decl, body, llfn,
 402                   bcx.fcx.param_substs, id,
 403                   [], ty::ty_fn_ret(fty),
 404                   |bcx| load_environment(bcx, cdata_ty, cap_vars.deref().as_slice(), sigil));
 405     fill_fn_pair(bcx, dest_addr, llfn, llbox);
 406
 407     bcx
 408 }
 409
 410 pub fn get_wrapper_for_bare_fn(ccx: &CrateContext,
 411                                closure_ty: ty::t,
 412                                def: ast::Def,
 413                                fn_ptr: ValueRef,
 414                                is_local: bool) -> ValueRef {
 415
 416     let def_id = match def {
 417         ast::DefFn(did, _) | ast::DefStaticMethod(did, _, _) |
 418         ast::DefVariant(_, did, _) | ast::DefStruct(did) => did,
 419         _ => {
 420             ccx.sess().bug(format!("get_wrapper_for_bare_fn: \
 421                                     expected a statically resolved fn, got {:?}",
 422                                     def));
 423         }
 424     };
 425
 426     {
 427         let cache = ccx.closure_bare_wrapper_cache.borrow();
 428         match cache.get().find(&fn_ptr) {
 429             Some(&llval) => return llval,
 430             None => {}
 431         }
 432     }
 433
 434     let tcx = ccx.tcx();
 435
 436     debug!("get_wrapper_for_bare_fn(closure_ty={})", closure_ty.repr(tcx));
 437
 438     let f = match ty::get(closure_ty).sty {
 439         ty::ty_closure(ref f) => f,
 440         _ => {
 441             ccx.sess().bug(format!("get_wrapper_for_bare_fn: \
 442                                     expected a closure ty, got {}",
 443                                     closure_ty.repr(tcx)));
 444         }
 445     };
 446
 447     let name = ty::with_path(tcx, def_id, |path| {
 448         mangle_internal_name_by_path_and_seq(path, "as_closure")
 449     });
 450     let llfn = if is_local {
 451         decl_internal_rust_fn(ccx,
 452                               true,
 453                               f.sig.inputs.as_slice(),
 454                               f.sig.output,
 455                               name)
 456     } else {
 457         decl_rust_fn(ccx, true, f.sig.inputs.as_slice(), f.sig.output, name)
 458     };
 459
 460     {
 461         let mut cache = ccx.closure_bare_wrapper_cache.borrow_mut();
 462         cache.get().insert(fn_ptr, llfn);
 463     }
 464
 465     // This is only used by statics inlined from a different crate.
 466     if !is_local {
 467         // Don't regenerate the wrapper, just reuse the original one.
 468         return llfn;
 469     }
 470
 471     let _icx = push_ctxt("closure::get_wrapper_for_bare_fn");
 472
 473     let arena = TypedArena::new();
 474     let fcx = new_fn_ctxt(ccx, llfn, -1, true, f.sig.output, None, None, &arena);
 475     init_function(&fcx, true, f.sig.output, None);
 476     let bcx = fcx.entry_bcx.get().unwrap();
 477
 478     let args = create_datums_for_fn_args(&fcx,
 479                                          ty::ty_fn_args(closure_ty)
 480                                             .as_slice());
 481     let mut llargs = Vec::new();
 482     match fcx.llretptr.get() {
 483         Some(llretptr) => {
 484             llargs.push(llretptr);
 485         }
 486         None => {}
 487     }
 488     llargs.extend(&mut args.iter().map(|arg| arg.val));
 489
 490     let retval = Call(bcx, fn_ptr, llargs.as_slice(), []);
 491     if type_is_zero_size(ccx, f.sig.output) || fcx.llretptr.get().is_some() {
 492         RetVoid(bcx);
 493     } else {
 494         Ret(bcx, retval);
 495     }
 496
 497     // HACK(eddyb) finish_fn cannot be used here, we returned directly.
 498     debuginfo::clear_source_location(&fcx);
 499     fcx.cleanup();
 500
 501     llfn
 502 }
 503
 504 pub fn make_closure_from_bare_fn<'a>(bcx: &'a Block<'a>,
 505                                      closure_ty: ty::t,
 506                                      def: ast::Def,
 507                                      fn_ptr: ValueRef)
 508                                      -> DatumBlock<'a, Expr>  {
 509     let scratch = rvalue_scratch_datum(bcx, closure_ty, "__adjust");
 510     let wrapper = get_wrapper_for_bare_fn(bcx.ccx(), closure_ty, def, fn_ptr, true);
 511     fill_fn_pair(bcx, scratch.val, wrapper, C_null(Type::i8p(bcx.ccx())));
 512
 513     DatumBlock(bcx, scratch.to_expr_datum())
 514 }