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.
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.
13 use back::link::{mangle_internal_name_by_path_and_seq};
14 use lib::llvm::ValueRef;
16 use middle::trans::base::*;
17 use middle::trans::build::*;
18 use middle::trans::common::*;
19 use middle::trans::datum::{Datum, INIT, ByRef, ZeroMem};
20 use middle::trans::expr;
21 use middle::trans::glue;
22 use middle::trans::type_of::*;
24 use util::ppaux::ty_to_str;
26 use middle::trans::type_::Type;
30 use syntax::ast_map::path_name;
32 use syntax::parse::token::special_idents;
34 // ___Good to know (tm)__________________________________________________
36 // The layout of a closure environment in memory is
37 // roughly as follows:
39 // struct rust_opaque_box { // see rust_internal.h
40 // unsigned ref_count; // only used for @fn()
41 // type_desc *tydesc; // describes closure_data struct
42 // rust_opaque_box *prev; // (used internally by memory alloc)
43 // rust_opaque_box *next; // (used internally by memory alloc)
44 // struct closure_data {
45 // type_desc *bound_tdescs[]; // bound descriptors
54 // Note that the closure is itself a rust_opaque_box. This is true
55 // even for ~fn and &fn, because we wish to keep binary compatibility
56 // between all kinds of closures. The allocation strategy for this
57 // closure depends on the closure type. For a sendfn, the closure
58 // (and the referenced type descriptors) will be allocated in the
59 // exchange heap. For a fn, the closure is allocated in the task heap
60 // and is reference counted. For a block, the closure is allocated on
63 // ## Opaque closures and the embedded type descriptor ##
65 // One interesting part of closures is that they encapsulate the data
66 // that they close over. So when I have a ptr to a closure, I do not
67 // know how many type descriptors it contains nor what upvars are
68 // captured within. That means I do not know precisely how big it is
69 // nor where its fields are located. This is called an "opaque
72 // Typically an opaque closure suffices because we only manipulate it
73 // by ptr. The routine Type::opaque_box().ptr_to() returns an
74 // appropriate type for such an opaque closure; it allows access to
75 // the box fields, but not the closure_data itself.
77 // But sometimes, such as when cloning or freeing a closure, we need
78 // to know the full information. That is where the type descriptor
79 // that defines the closure comes in handy. We can use its take and
80 // drop glue functions to allocate/free data as needed.
82 // ## Subtleties concerning alignment ##
84 // It is important that we be able to locate the closure data *without
85 // knowing the kind of data that is being bound*. This can be tricky
86 // because the alignment requirements of the bound data affects the
87 // alignment requires of the closure_data struct as a whole. However,
88 // right now this is a non-issue in any case, because the size of the
89 // rust_opaque_box header is always a mutiple of 16-bytes, which is
90 // the maximum alignment requirement we ever have to worry about.
92 // The only reason alignment matters is that, in order to learn what data
93 // is bound, we would normally first load the type descriptors: but their
94 // location is ultimately depend on their content! There is, however, a
95 // workaround. We can load the tydesc from the rust_opaque_box, which
96 // describes the closure_data struct and has self-contained derived type
97 // descriptors, and read the alignment from there. It's just annoying to
98 // do. Hopefully should this ever become an issue we'll have monomorphized
99 // and type descriptors will all be a bad dream.
101 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
104 /// Copy the value from this llvm ValueRef into the environment.
107 /// Move the value from this llvm ValueRef into the environment.
110 /// Access by reference (used for stack closures).
114 pub struct EnvValue {
120 pub fn to_str(&self) -> ~str {
122 EnvCopy => ~"EnvCopy",
123 EnvMove => ~"EnvMove",
130 pub fn to_str(&self, ccx: &CrateContext) -> ~str {
131 fmt!("%s(%s)", self.action.to_str(), self.datum.to_str(ccx))
135 pub fn mk_tuplified_uniq_cbox_ty(tcx: ty::ctxt, cdata_ty: ty::t) -> ty::t {
136 let cbox_ty = tuplify_box_ty(tcx, cdata_ty);
137 return ty::mk_imm_uniq(tcx, cbox_ty);
140 // Given a closure ty, emits a corresponding tuple ty
141 pub fn mk_closure_tys(tcx: ty::ctxt,
142 bound_values: &[EnvValue])
144 // determine the types of the values in the env. Note that this
145 // is the actual types that will be stored in the map, not the
146 // logical types as the user sees them, so by-ref upvars must be
147 // converted to ptrs.
148 let bound_tys = bound_values.map(|bv| {
150 EnvCopy | EnvMove => bv.datum.ty,
151 EnvRef => ty::mk_mut_ptr(tcx, bv.datum.ty)
154 let cdata_ty = ty::mk_tup(tcx, bound_tys);
155 debug!("cdata_ty=%s", ty_to_str(tcx, cdata_ty));
159 fn heap_for_unique_closure(bcx: block, t: ty::t) -> heap {
160 if ty::type_contents(bcx.tcx(), t).contains_managed() {
163 heap_exchange_closure
167 pub fn allocate_cbox(bcx: block, sigil: ast::Sigil, cdata_ty: ty::t)
169 let _icx = push_ctxt("closure::allocate_cbox");
173 // Allocate and initialize the box:
175 ast::ManagedSigil => {
176 malloc_raw(bcx, cdata_ty, heap_managed)
179 malloc_raw(bcx, cdata_ty, heap_for_unique_closure(bcx, cdata_ty))
181 ast::BorrowedSigil => {
182 let cbox_ty = tuplify_box_ty(tcx, cdata_ty);
183 let llbox = alloc_ty(bcx, cbox_ty, "__closure");
189 pub struct ClosureResult {
190 llbox: ValueRef, // llvalue of ptr to closure
191 cdata_ty: ty::t, // type of the closure data
192 bcx: block // final bcx
195 // Given a block context and a list of tydescs and values to bind
196 // construct a closure out of them. If copying is true, it is a
197 // heap allocated closure that copies the upvars into environment.
198 // Otherwise, it is stack allocated and copies pointers to the upvars.
199 pub fn store_environment(bcx: block,
200 bound_values: ~[EnvValue],
201 sigil: ast::Sigil) -> ClosureResult {
202 let _icx = push_ctxt("closure::store_environment");
206 // compute the type of the closure
207 let cdata_ty = mk_closure_tys(tcx, bound_values);
209 // cbox_ty has the form of a tuple: (a, b, c) we want a ptr to a
210 // tuple. This could be a ptr in uniq or a box or on stack,
212 let cbox_ty = tuplify_box_ty(tcx, cdata_ty);
213 let cboxptr_ty = ty::mk_ptr(tcx, ty::mt {ty:cbox_ty, mutbl:ast::m_imm});
214 let llboxptr_ty = type_of(ccx, cboxptr_ty);
216 // If there are no bound values, no point in allocating anything.
217 if bound_values.is_empty() {
218 return ClosureResult {llbox: C_null(llboxptr_ty),
223 // allocate closure in the heap
224 let Result {bcx: bcx, val: llbox} = allocate_cbox(bcx, sigil, cdata_ty);
226 let llbox = PointerCast(bcx, llbox, llboxptr_ty);
227 debug!("tuplify_box_ty = %s", ty_to_str(tcx, cbox_ty));
229 // Copy expr values into boxed bindings.
231 for bound_values.iter().enumerate().advance |(i, bv)| {
232 debug!("Copy %s into closure", bv.to_str(ccx));
234 if ccx.sess.asm_comments() {
235 add_comment(bcx, fmt!("Copy %s into closure",
239 let bound_data = GEPi(bcx, llbox, [0u, abi::box_field_body, i]);
243 bcx = bv.datum.copy_to(bcx, INIT, bound_data);
246 bcx = bv.datum.move_to(bcx, INIT, bound_data);
249 Store(bcx, bv.datum.to_ref_llval(bcx), bound_data);
255 ClosureResult { llbox: llbox, cdata_ty: cdata_ty, bcx: bcx }
258 // Given a context and a list of upvars, build a closure. This just
259 // collects the upvars and packages them up for store_environment.
260 pub fn build_closure(bcx0: block,
261 cap_vars: &[moves::CaptureVar],
263 include_ret_handle: Option<ValueRef>) -> ClosureResult {
264 let _icx = push_ctxt("closure::build_closure");
266 // If we need to, package up the iterator body to call
269 // Package up the captured upvars
270 let mut env_vals = ~[];
271 for cap_vars.iter().advance |cap_var| {
272 debug!("Building closure: captured variable %?", *cap_var);
273 let datum = expr::trans_local_var(bcx, cap_var.def);
276 assert_eq!(sigil, ast::BorrowedSigil);
277 env_vals.push(EnvValue {action: EnvRef,
281 env_vals.push(EnvValue {action: EnvCopy,
285 env_vals.push(EnvValue {action: EnvMove,
291 // If this is a `for` loop body, add two special environment
293 for include_ret_handle.iter().advance |flagptr| {
294 // Flag indicating we have returned (a by-ref bool):
295 let flag_datum = Datum {val: *flagptr, ty: ty::mk_bool(),
296 mode: ByRef(ZeroMem)};
297 env_vals.push(EnvValue {action: EnvRef,
300 // Return value (we just pass a by-ref () and cast it later to
302 let ret_true = match bcx.fcx.loop_ret {
303 Some((_, retptr)) => retptr,
304 None => match bcx.fcx.llretptr {
305 None => C_null(Type::nil().ptr_to()),
306 Some(retptr) => PointerCast(bcx, retptr, Type::nil().ptr_to()),
309 let ret_datum = Datum {val: ret_true, ty: ty::mk_nil(),
310 mode: ByRef(ZeroMem)};
311 env_vals.push(EnvValue {action: EnvRef,
315 return store_environment(bcx, env_vals, sigil);
318 // Given an enclosing block context, a new function context, a closure type,
319 // and a list of upvars, generate code to load and populate the environment
320 // with the upvars and type descriptors.
321 pub fn load_environment(fcx: fn_ctxt,
323 cap_vars: &[moves::CaptureVar],
324 load_ret_handle: bool,
326 let _icx = push_ctxt("closure::load_environment");
328 // Don't bother to create the block if there's nothing to load
329 if cap_vars.len() == 0 && !load_ret_handle {
333 let bcx = fcx.entry_bcx.get();
335 // Load a pointer to the closure data, skipping over the box header:
336 let llcdata = opaque_box_body(bcx, cdata_ty, fcx.llenv);
338 // Populate the upvars from the environment.
340 for cap_vars.iter().advance |cap_var| {
341 let mut upvarptr = GEPi(bcx, llcdata, [0u, i]);
343 ast::BorrowedSigil => { upvarptr = Load(bcx, upvarptr); }
344 ast::ManagedSigil | ast::OwnedSigil => {}
346 let def_id = ast_util::def_id_of_def(cap_var.def);
347 fcx.llupvars.insert(def_id.node, upvarptr);
351 let flagptr = Load(bcx, GEPi(bcx, llcdata, [0u, i]));
352 let retptr = Load(bcx,
353 GEPi(bcx, llcdata, [0u, i+1u]));
354 fcx.loop_ret = Some((flagptr, retptr));
358 pub fn trans_expr_fn(bcx: block,
362 outer_id: ast::node_id,
363 user_id: ast::node_id,
364 is_loop_body: Option<Option<ValueRef>>,
365 dest: expr::Dest) -> block {
368 * Translates the body of a closure expression.
373 * - `outer_id`: The id of the closure expression with the correct
374 * type. This is usually the same as `user_id`, but in the
375 * case of a `for` loop, the `outer_id` will have the return
376 * type of boolean, and the `user_id` will have the return type
378 * - `user_id`: The id of the closure as the user expressed it.
379 Generally the same as `outer_id`
380 * - `cap_clause`: information about captured variables, if any.
381 * - `is_loop_body`: `Some()` if this is part of a `for` loop.
382 * - `dest`: where to write the closure value, which must be a
386 let _icx = push_ctxt("closure::trans_expr_fn");
388 let dest_addr = match dest {
389 expr::SaveIn(p) => p,
391 return bcx; // closure construction is non-side-effecting
396 let fty = node_id_type(bcx, outer_id);
398 let llfnty = type_of_fn_from_ty(ccx, fty);
400 let sub_path = vec::append_one(bcx.fcx.path.clone(),
401 path_name(special_idents::anon));
403 let s = mangle_internal_name_by_path_and_seq(ccx,
406 let llfn = decl_internal_cdecl_fn(ccx.llmod, s, llfnty);
408 // Always mark inline if this is a loop body. This is important for
409 // performance on many programs with tight loops.
410 if is_loop_body.is_some() {
411 set_always_inline(llfn);
414 set_inline_hint(llfn);
417 let real_return_type = if is_loop_body.is_some() {
423 let Result {bcx: bcx, val: closure} = match sigil {
424 ast::BorrowedSigil | ast::ManagedSigil | ast::OwnedSigil => {
425 let cap_vars = ccx.maps.capture_map.get_copy(&user_id);
426 let ret_handle = match is_loop_body {Some(x) => x,
428 let ClosureResult {llbox, cdata_ty, bcx}
429 = build_closure(bcx, cap_vars, sigil, ret_handle);
436 bcx.fcx.param_substs,
440 |fcx| load_environment(fcx, cdata_ty, cap_vars,
441 ret_handle.is_some(), sigil),
443 if is_loop_body.is_some() {
446 bcx.fcx.llretptr.get());
452 fill_fn_pair(bcx, dest_addr, llfn, closure);
457 pub fn make_closure_glue(
461 glue_fn: &fn(block, v: ValueRef, t: ty::t) -> block) -> block {
462 let _icx = push_ctxt("closure::make_closure_glue");
466 let sigil = ty::ty_closure_sigil(t);
468 ast::BorrowedSigil => bcx,
469 ast::OwnedSigil | ast::ManagedSigil => {
470 let box_cell_v = GEPi(cx, v, [0u, abi::fn_field_box]);
471 let box_ptr_v = Load(cx, box_cell_v);
472 do with_cond(cx, IsNotNull(cx, box_ptr_v)) |bcx| {
473 let closure_ty = ty::mk_opaque_closure_ptr(tcx, sigil);
474 glue_fn(bcx, box_cell_v, closure_ty)
480 pub fn make_opaque_cbox_take_glue(
483 cboxptr: ValueRef) // ptr to ptr to the opaque closure
486 let _icx = push_ctxt("closure::make_opaque_cbox_take_glue");
488 ast::BorrowedSigil => {
491 ast::ManagedSigil => {
492 glue::incr_refcnt_of_boxed(bcx, Load(bcx, cboxptr));
496 fail!("unique closures are not copyable")
501 pub fn make_opaque_cbox_drop_glue(
504 cboxptr: ValueRef) // ptr to the opaque closure
506 let _icx = push_ctxt("closure::make_opaque_cbox_drop_glue");
508 ast::BorrowedSigil => bcx,
509 ast::ManagedSigil => {
510 glue::decr_refcnt_maybe_free(
511 bcx, Load(bcx, cboxptr), Some(cboxptr),
512 ty::mk_opaque_closure_ptr(bcx.tcx(), sigil))
517 ty::mk_opaque_closure_ptr(bcx.tcx(), sigil))
522 pub fn make_opaque_cbox_free_glue(
525 cbox: ValueRef) // ptr to ptr to the opaque closure
527 let _icx = push_ctxt("closure::make_opaque_cbox_free_glue");
529 ast::BorrowedSigil => {
532 ast::ManagedSigil | ast::OwnedSigil => {
533 /* hard cases: fallthrough to code below */
538 do with_cond(bcx, IsNotNull(bcx, cbox)) |bcx| {
539 // Load the type descr found in the cbox
540 let lltydescty = ccx.tydesc_type.ptr_to();
541 let cbox = Load(bcx, cbox);
542 let tydescptr = GEPi(bcx, cbox, [0u, abi::box_field_tydesc]);
543 let tydesc = Load(bcx, tydescptr);
544 let tydesc = PointerCast(bcx, tydesc, lltydescty);
546 // Drop the tuple data then free the descriptor
547 let cdata = GEPi(bcx, cbox, [0u, abi::box_field_body]);
548 glue::call_tydesc_glue_full(bcx, cdata, tydesc,
549 abi::tydesc_field_drop_glue, None);
551 // Free the ty descr (if necc) and the box itself
553 ast::ManagedSigil => glue::trans_free(bcx, cbox),
554 ast::OwnedSigil => glue::trans_exchange_free(bcx, cbox),
555 ast::BorrowedSigil => {
556 bcx.sess().bug("impossible")