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