]> git.lizzy.rs Git - rust.git/blob - src/librustc/middle/trans/closure.rs
auto merge of #15762 : nham/rust/ringbuf_docs, r=alexcrichton
[rust.git] / 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 llvm::ValueRef;
16 use middle::def;
17 use middle::freevars;
18 use middle::lang_items::ClosureExchangeMallocFnLangItem;
19 use middle::trans::adt;
20 use middle::trans::base::*;
21 use middle::trans::build::*;
22 use middle::trans::common::*;
23 use middle::trans::datum::{Datum, DatumBlock, Expr, Lvalue, rvalue_scratch_datum};
24 use middle::trans::debuginfo;
25 use middle::trans::expr;
26 use middle::trans::machine::llsize_of;
27 use middle::trans::type_of::*;
28 use middle::trans::type_::Type;
29 use middle::ty;
30 use util::ppaux::Repr;
31 use util::ppaux::ty_to_string;
32
33 use arena::TypedArena;
34 use syntax::ast;
35 use syntax::ast_util;
36
37 // ___Good to know (tm)__________________________________________________
38 //
39 // The layout of a closure environment in memory is
40 // roughly as follows:
41 //
42 // struct rust_opaque_box {         // see rust_internal.h
43 //   unsigned ref_count;            // obsolete (part of @T's header)
44 //   fn(void*) *drop_glue;          // destructor (for proc)
45 //   rust_opaque_box *prev;         // obsolete (part of @T's header)
46 //   rust_opaque_box *next;         // obsolete (part of @T's header)
47 //   struct closure_data {
48 //       upvar1_t upvar1;
49 //       ...
50 //       upvarN_t upvarN;
51 //    }
52 // };
53 //
54 // Note that the closure is itself a rust_opaque_box.  This is true
55 // even for ~fn and ||, 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
61 // the stack.
62 //
63 // ## Opaque closures and the embedded type descriptor ##
64 //
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
70 // closure".
71 //
72 // Typically an opaque closure suffices because we only manipulate it
73 // by ptr.  The routine Type::at_box().ptr_to() returns an appropriate
74 // type for such an opaque closure; it allows access to the box fields,
75 // but not the closure_data itself.
76 //
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.
81 //
82 // ## Subtleties concerning alignment ##
83 //
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 multiple of 16-bytes, which is
90 // the maximum alignment requirement we ever have to worry about.
91 //
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.
100 //
101 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
102
103 pub struct EnvValue {
104     action: freevars::CaptureMode,
105     datum: Datum<Lvalue>
106 }
107
108 impl EnvValue {
109     pub fn to_string(&self, ccx: &CrateContext) -> String {
110         format!("{}({})", self.action, self.datum.to_string(ccx))
111     }
112 }
113
114 // Given a closure ty, emits a corresponding tuple ty
115 pub fn mk_closure_tys(tcx: &ty::ctxt,
116                       bound_values: &[EnvValue])
117                    -> ty::t {
118     // determine the types of the values in the env.  Note that this
119     // is the actual types that will be stored in the map, not the
120     // logical types as the user sees them, so by-ref upvars must be
121     // converted to ptrs.
122     let bound_tys = bound_values.iter().map(|bv| {
123         match bv.action {
124             freevars::CaptureByValue => bv.datum.ty,
125             freevars::CaptureByRef => ty::mk_mut_ptr(tcx, bv.datum.ty)
126         }
127     }).collect();
128     let cdata_ty = ty::mk_tup(tcx, bound_tys);
129     debug!("cdata_ty={}", ty_to_string(tcx, cdata_ty));
130     return cdata_ty;
131 }
132
133 fn tuplify_box_ty(tcx: &ty::ctxt, t: ty::t) -> ty::t {
134     let ptr = ty::mk_imm_ptr(tcx, ty::mk_i8());
135     ty::mk_tup(tcx, vec!(ty::mk_uint(), ty::mk_nil_ptr(tcx), ptr, ptr, t))
136 }
137
138 fn allocate_cbox<'a>(bcx: &'a Block<'a>,
139                      store: ty::TraitStore,
140                      cdata_ty: ty::t)
141                      -> Result<'a> {
142     let _icx = push_ctxt("closure::allocate_cbox");
143     let tcx = bcx.tcx();
144
145     // Allocate and initialize the box:
146     match store {
147         ty::UniqTraitStore => {
148             let ty = type_of(bcx.ccx(), cdata_ty);
149             let size = llsize_of(bcx.ccx(), ty);
150             // we treat proc as @ here, which isn't ideal
151             malloc_raw_dyn_managed(bcx, cdata_ty, ClosureExchangeMallocFnLangItem, size)
152         }
153         ty::RegionTraitStore(..) => {
154             let cbox_ty = tuplify_box_ty(tcx, cdata_ty);
155             let llbox = alloc_ty(bcx, cbox_ty, "__closure");
156             Result::new(bcx, llbox)
157         }
158     }
159 }
160
161 pub struct ClosureResult<'a> {
162     llbox: ValueRef,    // llvalue of ptr to closure
163     cdata_ty: ty::t,    // type of the closure data
164     bcx: &'a Block<'a>  // final bcx
165 }
166
167 // Given a block context and a list of tydescs and values to bind
168 // construct a closure out of them. If copying is true, it is a
169 // heap allocated closure that copies the upvars into environment.
170 // Otherwise, it is stack allocated and copies pointers to the upvars.
171 pub fn store_environment<'a>(
172                          bcx: &'a Block<'a>,
173                          bound_values: Vec<EnvValue> ,
174                          store: ty::TraitStore)
175                          -> ClosureResult<'a> {
176     let _icx = push_ctxt("closure::store_environment");
177     let ccx = bcx.ccx();
178     let tcx = ccx.tcx();
179
180     // compute the type of the closure
181     let cdata_ty = mk_closure_tys(tcx, bound_values.as_slice());
182
183     // cbox_ty has the form of a tuple: (a, b, c) we want a ptr to a
184     // tuple.  This could be a ptr in uniq or a box or on stack,
185     // whatever.
186     let cbox_ty = tuplify_box_ty(tcx, cdata_ty);
187     let cboxptr_ty = ty::mk_ptr(tcx, ty::mt {ty:cbox_ty, mutbl:ast::MutImmutable});
188     let llboxptr_ty = type_of(ccx, cboxptr_ty);
189
190     // If there are no bound values, no point in allocating anything.
191     if bound_values.is_empty() {
192         return ClosureResult {llbox: C_null(llboxptr_ty),
193                               cdata_ty: cdata_ty,
194                               bcx: bcx};
195     }
196
197     // allocate closure in the heap
198     let Result {bcx: bcx, val: llbox} = allocate_cbox(bcx, store, cdata_ty);
199
200     let llbox = PointerCast(bcx, llbox, llboxptr_ty);
201     debug!("tuplify_box_ty = {}", ty_to_string(tcx, cbox_ty));
202
203     // Copy expr values into boxed bindings.
204     let mut bcx = bcx;
205     for (i, bv) in bound_values.move_iter().enumerate() {
206         debug!("Copy {} into closure", bv.to_string(ccx));
207
208         if ccx.sess().asm_comments() {
209             add_comment(bcx, format!("Copy {} into closure",
210                                      bv.to_string(ccx)).as_slice());
211         }
212
213         let bound_data = GEPi(bcx, llbox, [0u, abi::box_field_body, i]);
214
215         match bv.action {
216             freevars::CaptureByValue => {
217                 bcx = bv.datum.store_to(bcx, bound_data);
218             }
219             freevars::CaptureByRef => {
220                 Store(bcx, bv.datum.to_llref(), bound_data);
221             }
222         }
223     }
224
225     ClosureResult { llbox: llbox, cdata_ty: cdata_ty, bcx: bcx }
226 }
227
228 // Given a context and a list of upvars, build a closure. This just
229 // collects the upvars and packages them up for store_environment.
230 fn build_closure<'a>(bcx0: &'a Block<'a>,
231                      freevar_mode: freevars::CaptureMode,
232                      freevars: &Vec<freevars::freevar_entry>,
233                      store: ty::TraitStore)
234                      -> ClosureResult<'a>
235 {
236     let _icx = push_ctxt("closure::build_closure");
237
238     // If we need to, package up the iterator body to call
239     let bcx = bcx0;
240
241     // Package up the captured upvars
242     let mut env_vals = Vec::new();
243     for freevar in freevars.iter() {
244         let datum = expr::trans_local_var(bcx, freevar.def);
245         env_vals.push(EnvValue {action: freevar_mode, datum: datum});
246     }
247
248     store_environment(bcx, env_vals, store)
249 }
250
251 // Given an enclosing block context, a new function context, a closure type,
252 // and a list of upvars, generate code to load and populate the environment
253 // with the upvars and type descriptors.
254 fn load_environment<'a>(bcx: &'a Block<'a>,
255                         cdata_ty: ty::t,
256                         freevars: &Vec<freevars::freevar_entry>,
257                         store: ty::TraitStore)
258                         -> &'a Block<'a> {
259     let _icx = push_ctxt("closure::load_environment");
260
261     // Don't bother to create the block if there's nothing to load
262     if freevars.len() == 0 {
263         return bcx;
264     }
265
266     // Load a pointer to the closure data, skipping over the box header:
267     let llcdata = at_box_body(bcx, cdata_ty, bcx.fcx.llenv.unwrap());
268
269     // Store the pointer to closure data in an alloca for debug info because that's what the
270     // llvm.dbg.declare intrinsic expects
271     let env_pointer_alloca = if bcx.sess().opts.debuginfo == FullDebugInfo {
272         let alloc = alloc_ty(bcx, ty::mk_mut_ptr(bcx.tcx(), cdata_ty), "__debuginfo_env_ptr");
273         Store(bcx, llcdata, alloc);
274         Some(alloc)
275     } else {
276         None
277     };
278
279     // Populate the upvars from the environment
280     let mut i = 0u;
281     for freevar in freevars.iter() {
282         let mut upvarptr = GEPi(bcx, llcdata, [0u, i]);
283         match store {
284             ty::RegionTraitStore(..) => { upvarptr = Load(bcx, upvarptr); }
285             ty::UniqTraitStore => {}
286         }
287         let def_id = freevar.def.def_id();
288
289         bcx.fcx.llupvars.borrow_mut().insert(def_id.node, upvarptr);
290         for &env_pointer_alloca in env_pointer_alloca.iter() {
291             debuginfo::create_captured_var_metadata(
292                 bcx,
293                 def_id.node,
294                 cdata_ty,
295                 env_pointer_alloca,
296                 i,
297                 store,
298                 freevar.span);
299         }
300
301         i += 1u;
302     }
303
304     bcx
305 }
306
307 fn load_unboxed_closure_environment<'a>(
308                                     bcx: &'a Block<'a>,
309                                     freevars: &Vec<freevars::freevar_entry>)
310                                     -> &'a Block<'a> {
311     let _icx = push_ctxt("closure::load_environment");
312
313     if freevars.len() == 0 {
314         return bcx
315     }
316
317     let llenv = bcx.fcx.llenv.unwrap();
318     for (i, freevar) in freevars.iter().enumerate() {
319         let upvar_ptr = GEPi(bcx, llenv, [0, i]);
320         let def_id = freevar.def.def_id();
321         bcx.fcx.llupvars.borrow_mut().insert(def_id.node, upvar_ptr);
322     }
323
324     bcx
325 }
326
327 fn fill_fn_pair(bcx: &Block, pair: ValueRef, llfn: ValueRef, llenvptr: ValueRef) {
328     Store(bcx, llfn, GEPi(bcx, pair, [0u, abi::fn_field_code]));
329     let llenvptr = PointerCast(bcx, llenvptr, Type::i8p(bcx.ccx()));
330     Store(bcx, llenvptr, GEPi(bcx, pair, [0u, abi::fn_field_box]));
331 }
332
333 pub fn trans_expr_fn<'a>(
334                      bcx: &'a Block<'a>,
335                      store: ty::TraitStore,
336                      decl: &ast::FnDecl,
337                      body: &ast::Block,
338                      id: ast::NodeId,
339                      dest: expr::Dest)
340                      -> &'a Block<'a> {
341     /*!
342      *
343      * Translates the body of a closure expression.
344      *
345      * - `store`
346      * - `decl`
347      * - `body`
348      * - `id`: The id of the closure expression.
349      * - `cap_clause`: information about captured variables, if any.
350      * - `dest`: where to write the closure value, which must be a
351          (fn ptr, env) pair
352      */
353
354     let _icx = push_ctxt("closure::trans_expr_fn");
355
356     let dest_addr = match dest {
357         expr::SaveIn(p) => p,
358         expr::Ignore => {
359             return bcx; // closure construction is non-side-effecting
360         }
361     };
362
363     let ccx = bcx.ccx();
364     let tcx = bcx.tcx();
365     let fty = node_id_type(bcx, id);
366     let s = tcx.map.with_path(id, |path| {
367         mangle_internal_name_by_path_and_seq(path, "closure")
368     });
369     let llfn = decl_internal_rust_fn(ccx, fty, s.as_slice());
370
371     // set an inline hint for all closures
372     set_inline_hint(llfn);
373
374     let freevar_mode = freevars::get_capture_mode(tcx, id);
375     let freevars: Vec<freevars::freevar_entry> =
376         freevars::with_freevars(tcx,
377                                 id,
378                                 |fv| fv.iter().map(|&fv| fv).collect());
379
380     let ClosureResult {
381         llbox,
382         cdata_ty,
383         bcx
384     } = build_closure(bcx, freevar_mode, &freevars, store);
385     trans_closure(ccx,
386                   decl,
387                   body,
388                   llfn,
389                   bcx.fcx.param_substs,
390                   id,
391                   [],
392                   ty::ty_fn_args(fty),
393                   ty::ty_fn_ret(fty),
394                   ty::ty_fn_abi(fty),
395                   true,
396                   NotUnboxedClosure,
397                   |bcx| load_environment(bcx, cdata_ty, &freevars, store));
398     fill_fn_pair(bcx, dest_addr, llfn, llbox);
399     bcx
400 }
401
402 /// Returns the LLVM function declaration for an unboxed closure, creating it
403 /// if necessary. If the ID does not correspond to a closure ID, returns None.
404 pub fn get_or_create_declaration_if_unboxed_closure(ccx: &CrateContext,
405                                                     closure_id: ast::DefId)
406                                                     -> Option<ValueRef> {
407     if !ccx.tcx.unboxed_closure_types.borrow().contains_key(&closure_id) {
408         // Not an unboxed closure.
409         return None
410     }
411
412     match ccx.unboxed_closure_vals.borrow().find(&closure_id) {
413         Some(llfn) => {
414             debug!("get_or_create_declaration_if_unboxed_closure(): found \
415                     closure");
416             return Some(*llfn)
417         }
418         None => {}
419     }
420
421     let function_type = ty::mk_unboxed_closure(&ccx.tcx, closure_id);
422     let symbol = ccx.tcx.map.with_path(closure_id.node, |path| {
423         mangle_internal_name_by_path_and_seq(path, "unboxed_closure")
424     });
425
426     let llfn = decl_internal_rust_fn(ccx, function_type, symbol.as_slice());
427
428     // set an inline hint for all closures
429     set_inline_hint(llfn);
430
431     debug!("get_or_create_declaration_if_unboxed_closure(): inserting new \
432             closure {} (type {})",
433            closure_id,
434            ccx.tn.type_to_string(val_ty(llfn)));
435     ccx.unboxed_closure_vals.borrow_mut().insert(closure_id, llfn);
436
437     Some(llfn)
438 }
439
440 pub fn trans_unboxed_closure<'a>(
441                              mut bcx: &'a Block<'a>,
442                              decl: &ast::FnDecl,
443                              body: &ast::Block,
444                              id: ast::NodeId,
445                              dest: expr::Dest)
446                              -> &'a Block<'a> {
447     let _icx = push_ctxt("closure::trans_unboxed_closure");
448
449     debug!("trans_unboxed_closure()");
450
451     let closure_id = ast_util::local_def(id);
452     let llfn = get_or_create_declaration_if_unboxed_closure(
453         bcx.ccx(),
454         closure_id).unwrap();
455
456     // Untuple the arguments.
457     let unboxed_closure_types = bcx.tcx().unboxed_closure_types.borrow();
458     let /*mut*/ function_type = (*unboxed_closure_types.get(&closure_id)).clone();
459     /*function_type.sig.inputs =
460         match ty::get(*function_type.sig.inputs.get(0)).sty {
461             ty::ty_tup(ref tuple_types) => {
462                 tuple_types.iter().map(|x| (*x).clone()).collect()
463             }
464             _ => {
465                 bcx.tcx().sess.span_bug(body.span,
466                                         "unboxed closure wasn't a tuple?!")
467             }
468         };*/
469     let function_type = ty::mk_closure(bcx.tcx(), function_type);
470
471     let freevars: Vec<freevars::freevar_entry> =
472         freevars::with_freevars(bcx.tcx(),
473                                 id,
474                                 |fv| fv.iter().map(|&fv| fv).collect());
475     let freevars_ptr = &freevars;
476
477     trans_closure(bcx.ccx(),
478                   decl,
479                   body,
480                   llfn,
481                   bcx.fcx.param_substs,
482                   id,
483                   [],
484                   ty::ty_fn_args(function_type),
485                   ty::ty_fn_ret(function_type),
486                   ty::ty_fn_abi(function_type),
487                   true,
488                   IsUnboxedClosure,
489                   |bcx| load_unboxed_closure_environment(bcx, freevars_ptr));
490
491     // Don't hoist this to the top of the function. It's perfectly legitimate
492     // to have a zero-size unboxed closure (in which case dest will be
493     // `Ignore`) and we must still generate the closure body.
494     let dest_addr = match dest {
495         expr::SaveIn(p) => p,
496         expr::Ignore => {
497             debug!("trans_unboxed_closure() ignoring result");
498             return bcx
499         }
500     };
501
502     let repr = adt::represent_type(bcx.ccx(), node_id_type(bcx, id));
503
504     // Create the closure.
505     for freevar in freevars_ptr.iter() {
506         let datum = expr::trans_local_var(bcx, freevar.def);
507         let upvar_slot_dest = adt::trans_field_ptr(bcx,
508                                                    &*repr,
509                                                    dest_addr,
510                                                    0,
511                                                    0);
512         bcx = datum.store_to(bcx, upvar_slot_dest);
513     }
514     adt::trans_set_discr(bcx, &*repr, dest_addr, 0);
515
516     bcx
517 }
518
519 pub fn get_wrapper_for_bare_fn(ccx: &CrateContext,
520                                closure_ty: ty::t,
521                                def: def::Def,
522                                fn_ptr: ValueRef,
523                                is_local: bool) -> ValueRef {
524
525     let def_id = match def {
526         def::DefFn(did, _) | def::DefStaticMethod(did, _, _) |
527         def::DefVariant(_, did, _) | def::DefStruct(did) => did,
528         _ => {
529             ccx.sess().bug(format!("get_wrapper_for_bare_fn: \
530                                     expected a statically resolved fn, got \
531                                     {:?}",
532                                     def).as_slice());
533         }
534     };
535
536     match ccx.closure_bare_wrapper_cache.borrow().find(&fn_ptr) {
537         Some(&llval) => return llval,
538         None => {}
539     }
540
541     let tcx = ccx.tcx();
542
543     debug!("get_wrapper_for_bare_fn(closure_ty={})", closure_ty.repr(tcx));
544
545     let f = match ty::get(closure_ty).sty {
546         ty::ty_closure(ref f) => f,
547         _ => {
548             ccx.sess().bug(format!("get_wrapper_for_bare_fn: \
549                                     expected a closure ty, got {}",
550                                     closure_ty.repr(tcx)).as_slice());
551         }
552     };
553
554     let name = ty::with_path(tcx, def_id, |path| {
555         mangle_internal_name_by_path_and_seq(path, "as_closure")
556     });
557     let llfn = if is_local {
558         decl_internal_rust_fn(ccx, closure_ty, name.as_slice())
559     } else {
560         decl_rust_fn(ccx, closure_ty, name.as_slice())
561     };
562
563     ccx.closure_bare_wrapper_cache.borrow_mut().insert(fn_ptr, llfn);
564
565     // This is only used by statics inlined from a different crate.
566     if !is_local {
567         // Don't regenerate the wrapper, just reuse the original one.
568         return llfn;
569     }
570
571     let _icx = push_ctxt("closure::get_wrapper_for_bare_fn");
572
573     let arena = TypedArena::new();
574     let empty_param_substs = param_substs::empty();
575     let fcx = new_fn_ctxt(ccx, llfn, -1, true, f.sig.output,
576                           &empty_param_substs, None, &arena);
577     let bcx = init_function(&fcx, true, f.sig.output);
578
579     let args = create_datums_for_fn_args(&fcx,
580                                          ty::ty_fn_args(closure_ty)
581                                             .as_slice());
582     let mut llargs = Vec::new();
583     match fcx.llretptr.get() {
584         Some(llretptr) => {
585             llargs.push(llretptr);
586         }
587         None => {}
588     }
589     llargs.extend(args.iter().map(|arg| arg.val));
590
591     let retval = Call(bcx, fn_ptr, llargs.as_slice(), None);
592     if type_is_zero_size(ccx, f.sig.output) || fcx.llretptr.get().is_some() {
593         RetVoid(bcx);
594     } else {
595         Ret(bcx, retval);
596     }
597
598     // HACK(eddyb) finish_fn cannot be used here, we returned directly.
599     debuginfo::clear_source_location(&fcx);
600     fcx.cleanup();
601
602     llfn
603 }
604
605 pub fn make_closure_from_bare_fn<'a>(bcx: &'a Block<'a>,
606                                      closure_ty: ty::t,
607                                      def: def::Def,
608                                      fn_ptr: ValueRef)
609                                      -> DatumBlock<'a, Expr>  {
610     let scratch = rvalue_scratch_datum(bcx, closure_ty, "__adjust");
611     let wrapper = get_wrapper_for_bare_fn(bcx.ccx(), closure_ty, def, fn_ptr, true);
612     fill_fn_pair(bcx, scratch.val, wrapper, C_null(Type::i8p(bcx.ccx())));
613
614     DatumBlock::new(bcx, scratch.to_expr_datum())
615 }