]> git.lizzy.rs Git - rust.git/blob - src/librustc_trans/trans/closure.rs
Kill RacyCell in favor of marking SyncSender explicitly Send.
[rust.git] / src / librustc_trans / 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 pub use self::ClosureKind::*;
12
13 use back::abi;
14 use back::link::mangle_internal_name_by_path_and_seq;
15 use llvm::ValueRef;
16 use middle::mem_categorization::Typer;
17 use trans::adt;
18 use trans::base::*;
19 use trans::build::*;
20 use trans::cleanup::{CleanupMethods, ScopeId};
21 use trans::common::*;
22 use trans::datum::{Datum, Lvalue, rvalue_scratch_datum};
23 use trans::datum::{Rvalue, ByValue};
24 use trans::debuginfo;
25 use trans::expr;
26 use trans::monomorphize::{self, MonoId};
27 use trans::type_of::*;
28 use trans::type_::Type;
29 use middle::ty::{self, Ty, UnboxedClosureTyper};
30 use middle::subst::{Substs};
31 use session::config::FullDebugInfo;
32 use util::ppaux::ty_to_string;
33
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 #[derive(Copy)]
104 pub struct EnvValue<'tcx> {
105     action: ast::CaptureClause,
106     datum: Datum<'tcx, Lvalue>
107 }
108
109 impl<'tcx> EnvValue<'tcx> {
110     pub fn to_string<'a>(&self, ccx: &CrateContext<'a, 'tcx>) -> String {
111         format!("{:?}({})", self.action, self.datum.to_string(ccx))
112     }
113 }
114
115 // Given a closure ty, emits a corresponding tuple ty
116 pub fn mk_closure_tys<'tcx>(tcx: &ty::ctxt<'tcx>,
117                             bound_values: &[EnvValue<'tcx>])
118                             -> Ty<'tcx> {
119     // determine the types of the values in the env.  Note that this
120     // is the actual types that will be stored in the map, not the
121     // logical types as the user sees them, so by-ref upvars must be
122     // converted to ptrs.
123     let bound_tys = bound_values.iter().map(|bv| {
124         match bv.action {
125             ast::CaptureByValue => bv.datum.ty,
126             ast::CaptureByRef => ty::mk_mut_ptr(tcx, bv.datum.ty)
127         }
128     }).collect();
129     let cdata_ty = ty::mk_tup(tcx, bound_tys);
130     debug!("cdata_ty={}", ty_to_string(tcx, cdata_ty));
131     return cdata_ty;
132 }
133
134 fn tuplify_box_ty<'tcx>(tcx: &ty::ctxt<'tcx>, t: Ty<'tcx>) -> Ty<'tcx> {
135     let ptr = ty::mk_imm_ptr(tcx, tcx.types.i8);
136     ty::mk_tup(tcx, vec!(tcx.types.uint, ty::mk_nil_ptr(tcx), ptr, ptr, t))
137 }
138
139 pub struct ClosureResult<'blk, 'tcx: 'blk> {
140     llbox: ValueRef,        // llvalue of ptr to closure
141     cdata_ty: Ty<'tcx>,     // type of the closure data
142     bcx: Block<'blk, 'tcx>  // final bcx
143 }
144
145 // Given a block context and a list of tydescs and values to bind
146 // construct a closure out of them. If copying is true, it is a
147 // heap allocated closure that copies the upvars into environment.
148 // Otherwise, it is stack allocated and copies pointers to the upvars.
149 pub fn store_environment<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
150                                      bound_values: Vec<EnvValue<'tcx>>)
151                                      -> ClosureResult<'blk, 'tcx> {
152     let _icx = push_ctxt("closure::store_environment");
153     let ccx = bcx.ccx();
154     let tcx = ccx.tcx();
155
156     // compute the type of the closure
157     let cdata_ty = mk_closure_tys(tcx, &bound_values[]);
158
159     // cbox_ty has the form of a tuple: (a, b, c) we want a ptr to a
160     // tuple.  This could be a ptr in uniq or a box or on stack,
161     // whatever.
162     let cbox_ty = tuplify_box_ty(tcx, cdata_ty);
163     let cboxptr_ty = ty::mk_ptr(tcx, ty::mt {ty:cbox_ty, mutbl:ast::MutImmutable});
164     let llboxptr_ty = type_of(ccx, cboxptr_ty);
165
166     // If there are no bound values, no point in allocating anything.
167     if bound_values.is_empty() {
168         return ClosureResult {llbox: C_null(llboxptr_ty),
169                               cdata_ty: cdata_ty,
170                               bcx: bcx};
171     }
172
173     // allocate closure in the heap
174     let llbox = alloc_ty(bcx, cbox_ty, "__closure");
175
176     let llbox = PointerCast(bcx, llbox, llboxptr_ty);
177     debug!("tuplify_box_ty = {}", ty_to_string(tcx, cbox_ty));
178
179     // Copy expr values into boxed bindings.
180     let mut bcx = bcx;
181     for (i, bv) in bound_values.into_iter().enumerate() {
182         debug!("Copy {} into closure", bv.to_string(ccx));
183
184         if ccx.sess().asm_comments() {
185             add_comment(bcx, &format!("Copy {} into closure",
186                                      bv.to_string(ccx))[]);
187         }
188
189         let bound_data = GEPi(bcx, llbox, &[0u, abi::BOX_FIELD_BODY, i]);
190
191         match bv.action {
192             ast::CaptureByValue => {
193                 bcx = bv.datum.store_to(bcx, bound_data);
194             }
195             ast::CaptureByRef => {
196                 Store(bcx, bv.datum.to_llref(), bound_data);
197             }
198         }
199     }
200
201     ClosureResult { llbox: llbox, cdata_ty: cdata_ty, bcx: bcx }
202 }
203
204 // Given a context and a list of upvars, build a closure. This just
205 // collects the upvars and packages them up for store_environment.
206 fn build_closure<'blk, 'tcx>(bcx0: Block<'blk, 'tcx>,
207                              freevar_mode: ast::CaptureClause,
208                              freevars: &Vec<ty::Freevar>)
209                              -> ClosureResult<'blk, 'tcx> {
210     let _icx = push_ctxt("closure::build_closure");
211
212     // If we need to, package up the iterator body to call
213     let bcx = bcx0;
214
215     // Package up the captured upvars
216     let mut env_vals = Vec::new();
217     for freevar in freevars.iter() {
218         let datum = expr::trans_local_var(bcx, freevar.def);
219         env_vals.push(EnvValue {action: freevar_mode, datum: datum});
220     }
221
222     store_environment(bcx, env_vals)
223 }
224
225 // Given an enclosing block context, a new function context, a closure type,
226 // and a list of upvars, generate code to load and populate the environment
227 // with the upvars and type descriptors.
228 fn load_environment<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
229                                 cdata_ty: Ty<'tcx>,
230                                 freevars: &[ty::Freevar],
231                                 store: ty::TraitStore)
232                                 -> Block<'blk, 'tcx> {
233     let _icx = push_ctxt("closure::load_environment");
234
235     // Load a pointer to the closure data, skipping over the box header:
236     let llcdata = at_box_body(bcx, cdata_ty, bcx.fcx.llenv.unwrap());
237
238     // Store the pointer to closure data in an alloca for debug info because that's what the
239     // llvm.dbg.declare intrinsic expects
240     let env_pointer_alloca = if bcx.sess().opts.debuginfo == FullDebugInfo {
241         let alloc = alloc_ty(bcx, ty::mk_mut_ptr(bcx.tcx(), cdata_ty), "__debuginfo_env_ptr");
242         Store(bcx, llcdata, alloc);
243         Some(alloc)
244     } else {
245         None
246     };
247
248     // Populate the upvars from the environment
249     let mut i = 0u;
250     for freevar in freevars.iter() {
251         let mut upvarptr = GEPi(bcx, llcdata, &[0u, i]);
252         let captured_by_ref = match store {
253             ty::RegionTraitStore(..) => {
254                 upvarptr = Load(bcx, upvarptr);
255                 true
256             }
257             ty::UniqTraitStore => false
258         };
259         let def_id = freevar.def.def_id();
260
261         bcx.fcx.llupvars.borrow_mut().insert(def_id.node, upvarptr);
262         if let Some(env_pointer_alloca) = env_pointer_alloca {
263             debuginfo::create_captured_var_metadata(
264                 bcx,
265                 def_id.node,
266                 env_pointer_alloca,
267                 i,
268                 captured_by_ref,
269                 freevar.span);
270         }
271
272         i += 1u;
273     }
274
275     bcx
276 }
277
278 fn load_unboxed_closure_environment<'blk, 'tcx>(
279                                     bcx: Block<'blk, 'tcx>,
280                                     arg_scope_id: ScopeId,
281                                     freevar_mode: ast::CaptureClause,
282                                     freevars: &[ty::Freevar])
283                                     -> Block<'blk, 'tcx> {
284     let _icx = push_ctxt("closure::load_environment");
285
286     // Special case for small by-value selfs.
287     let closure_id = ast_util::local_def(bcx.fcx.id);
288     let self_type = self_type_for_unboxed_closure(bcx.ccx(), closure_id,
289                                                   node_id_type(bcx, closure_id.node));
290     let kind = kind_for_unboxed_closure(bcx.ccx(), closure_id);
291     let llenv = if kind == ty::FnOnceUnboxedClosureKind &&
292             !arg_is_indirect(bcx.ccx(), self_type) {
293         let datum = rvalue_scratch_datum(bcx,
294                                          self_type,
295                                          "unboxed_closure_env");
296         store_ty(bcx, bcx.fcx.llenv.unwrap(), datum.val, self_type);
297         datum.val
298     } else {
299         bcx.fcx.llenv.unwrap()
300     };
301
302     // Store the pointer to closure data in an alloca for debug info because that's what the
303     // llvm.dbg.declare intrinsic expects
304     let env_pointer_alloca = if bcx.sess().opts.debuginfo == FullDebugInfo {
305         let alloc = alloca(bcx, val_ty(llenv), "__debuginfo_env_ptr");
306         Store(bcx, llenv, alloc);
307         Some(alloc)
308     } else {
309         None
310     };
311
312     for (i, freevar) in freevars.iter().enumerate() {
313         let mut upvar_ptr = GEPi(bcx, llenv, &[0, i]);
314         let captured_by_ref = match freevar_mode {
315             ast::CaptureByRef => {
316                 upvar_ptr = Load(bcx, upvar_ptr);
317                 true
318             }
319             ast::CaptureByValue => false
320         };
321         let def_id = freevar.def.def_id();
322         bcx.fcx.llupvars.borrow_mut().insert(def_id.node, upvar_ptr);
323
324         if kind == ty::FnOnceUnboxedClosureKind && freevar_mode == ast::CaptureByValue {
325             bcx.fcx.schedule_drop_mem(arg_scope_id,
326                                       upvar_ptr,
327                                       node_id_type(bcx, def_id.node))
328         }
329
330         if let Some(env_pointer_alloca) = env_pointer_alloca {
331             debuginfo::create_captured_var_metadata(
332                 bcx,
333                 def_id.node,
334                 env_pointer_alloca,
335                 i,
336                 captured_by_ref,
337                 freevar.span);
338         }
339     }
340
341     bcx
342 }
343
344 fn fill_fn_pair(bcx: Block, pair: ValueRef, llfn: ValueRef, llenvptr: ValueRef) {
345     Store(bcx, llfn, GEPi(bcx, pair, &[0u, abi::FAT_PTR_ADDR]));
346     let llenvptr = PointerCast(bcx, llenvptr, Type::i8p(bcx.ccx()));
347     Store(bcx, llenvptr, GEPi(bcx, pair, &[0u, abi::FAT_PTR_EXTRA]));
348 }
349
350 #[derive(PartialEq)]
351 pub enum ClosureKind<'tcx> {
352     NotClosure,
353     // See load_environment.
354     BoxedClosure(Ty<'tcx>, ty::TraitStore),
355     // See load_unboxed_closure_environment.
356     UnboxedClosure(ast::CaptureClause)
357 }
358
359 pub struct ClosureEnv<'a, 'tcx> {
360     freevars: &'a [ty::Freevar],
361     pub kind: ClosureKind<'tcx>
362 }
363
364 impl<'a, 'tcx> ClosureEnv<'a, 'tcx> {
365     pub fn new(freevars: &'a [ty::Freevar], kind: ClosureKind<'tcx>)
366                -> ClosureEnv<'a, 'tcx> {
367         ClosureEnv {
368             freevars: freevars,
369             kind: kind
370         }
371     }
372
373     pub fn load<'blk>(self, bcx: Block<'blk, 'tcx>, arg_scope: ScopeId)
374                       -> Block<'blk, 'tcx> {
375         // Don't bother to create the block if there's nothing to load
376         if self.freevars.is_empty() {
377             return bcx;
378         }
379
380         match self.kind {
381             NotClosure => bcx,
382             BoxedClosure(cdata_ty, store) => {
383                 load_environment(bcx, cdata_ty, self.freevars, store)
384             }
385             UnboxedClosure(freevar_mode) => {
386                 load_unboxed_closure_environment(bcx, arg_scope, freevar_mode, self.freevars)
387             }
388         }
389     }
390 }
391
392 /// Translates the body of a closure expression.
393 ///
394 /// - `store`
395 /// - `decl`
396 /// - `body`
397 /// - `id`: The id of the closure expression.
398 /// - `cap_clause`: information about captured variables, if any.
399 /// - `dest`: where to write the closure value, which must be a
400 ///   (fn ptr, env) pair
401 pub fn trans_expr_fn<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
402                                  store: ty::TraitStore,
403                                  decl: &ast::FnDecl,
404                                  body: &ast::Block,
405                                  id: ast::NodeId,
406                                  dest: expr::Dest)
407                                  -> Block<'blk, 'tcx> {
408     let _icx = push_ctxt("closure::trans_expr_fn");
409
410     let dest_addr = match dest {
411         expr::SaveIn(p) => p,
412         expr::Ignore => {
413             return bcx; // closure construction is non-side-effecting
414         }
415     };
416
417     let ccx = bcx.ccx();
418     let tcx = bcx.tcx();
419     let fty = node_id_type(bcx, id);
420     let s = tcx.map.with_path(id, |path| {
421         mangle_internal_name_by_path_and_seq(path, "closure")
422     });
423     let llfn = decl_internal_rust_fn(ccx, fty, &s[]);
424
425     // set an inline hint for all closures
426     set_inline_hint(llfn);
427
428     let freevar_mode = tcx.capture_mode(id);
429     let freevars: Vec<ty::Freevar> =
430         ty::with_freevars(tcx, id, |fv| fv.iter().map(|&fv| fv).collect());
431
432     let ClosureResult {
433         llbox,
434         cdata_ty,
435         bcx
436     } = build_closure(bcx, freevar_mode, &freevars);
437
438     trans_closure(ccx,
439                   decl,
440                   body,
441                   llfn,
442                   bcx.fcx.param_substs,
443                   id,
444                   &[],
445                   ty::erase_late_bound_regions(ccx.tcx(), &ty::ty_fn_ret(fty)),
446                   ty::ty_fn_abi(fty),
447                   ClosureEnv::new(&freevars[],
448                                   BoxedClosure(cdata_ty, store)));
449     fill_fn_pair(bcx, dest_addr, llfn, llbox);
450     bcx
451 }
452
453 /// Returns the LLVM function declaration for an unboxed closure, creating it
454 /// if necessary. If the ID does not correspond to a closure ID, returns None.
455 pub fn get_or_create_declaration_if_unboxed_closure<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
456                                                               closure_id: ast::DefId,
457                                                               substs: &Substs<'tcx>)
458                                                               -> Option<Datum<'tcx, Rvalue>> {
459     if !ccx.tcx().unboxed_closures.borrow().contains_key(&closure_id) {
460         // Not an unboxed closure.
461         return None
462     }
463
464     let function_type = ty::node_id_to_type(ccx.tcx(), closure_id.node);
465     let function_type = monomorphize::apply_param_substs(ccx.tcx(), substs, &function_type);
466
467     // Normalize type so differences in regions and typedefs don't cause
468     // duplicate declarations
469     let function_type = erase_regions(ccx.tcx(), &function_type);
470     let params = match function_type.sty {
471         ty::ty_unboxed_closure(_, _, ref substs) => substs.types.clone(),
472         _ => unreachable!()
473     };
474     let mono_id = MonoId {
475         def: closure_id,
476         params: params
477     };
478
479     match ccx.unboxed_closure_vals().borrow().get(&mono_id) {
480         Some(&llfn) => {
481             debug!("get_or_create_declaration_if_unboxed_closure(): found \
482                     closure");
483             return Some(Datum::new(llfn, function_type, Rvalue::new(ByValue)))
484         }
485         None => {}
486     }
487
488     let symbol = ccx.tcx().map.with_path(closure_id.node, |path| {
489         mangle_internal_name_by_path_and_seq(path, "unboxed_closure")
490     });
491
492     let llfn = decl_internal_rust_fn(ccx, function_type, &symbol[]);
493
494     // set an inline hint for all closures
495     set_inline_hint(llfn);
496
497     debug!("get_or_create_declaration_if_unboxed_closure(): inserting new \
498             closure {:?} (type {})",
499            mono_id,
500            ccx.tn().type_to_string(val_ty(llfn)));
501     ccx.unboxed_closure_vals().borrow_mut().insert(mono_id, llfn);
502
503     Some(Datum::new(llfn, function_type, Rvalue::new(ByValue)))
504 }
505
506 pub fn trans_unboxed_closure<'blk, 'tcx>(
507                              mut bcx: Block<'blk, 'tcx>,
508                              decl: &ast::FnDecl,
509                              body: &ast::Block,
510                              id: ast::NodeId,
511                              dest: expr::Dest)
512                              -> Block<'blk, 'tcx>
513 {
514     let _icx = push_ctxt("closure::trans_unboxed_closure");
515
516     debug!("trans_unboxed_closure()");
517
518     let closure_id = ast_util::local_def(id);
519     let llfn = get_or_create_declaration_if_unboxed_closure(
520         bcx.ccx(),
521         closure_id,
522         bcx.fcx.param_substs).unwrap();
523
524     // Get the type of this closure. Use the current `param_substs` as
525     // the closure substitutions. This makes sense because the closure
526     // takes the same set of type arguments as the enclosing fn, and
527     // this function (`trans_unboxed_closure`) is invoked at the point
528     // of the closure expression.
529     let typer = NormalizingUnboxedClosureTyper::new(bcx.tcx());
530     let function_type = typer.unboxed_closure_type(closure_id, bcx.fcx.param_substs);
531
532     let freevars: Vec<ty::Freevar> =
533         ty::with_freevars(bcx.tcx(), id, |fv| fv.iter().map(|&fv| fv).collect());
534     let freevar_mode = bcx.tcx().capture_mode(id);
535
536     let sig = ty::erase_late_bound_regions(bcx.tcx(), &function_type.sig);
537
538     trans_closure(bcx.ccx(),
539                   decl,
540                   body,
541                   llfn.val,
542                   bcx.fcx.param_substs,
543                   id,
544                   &[],
545                   sig.output,
546                   function_type.abi,
547                   ClosureEnv::new(&freevars[],
548                                   UnboxedClosure(freevar_mode)));
549
550     // Don't hoist this to the top of the function. It's perfectly legitimate
551     // to have a zero-size unboxed closure (in which case dest will be
552     // `Ignore`) and we must still generate the closure body.
553     let dest_addr = match dest {
554         expr::SaveIn(p) => p,
555         expr::Ignore => {
556             debug!("trans_unboxed_closure() ignoring result");
557             return bcx
558         }
559     };
560
561     let repr = adt::represent_type(bcx.ccx(), node_id_type(bcx, id));
562
563     // Create the closure.
564     for (i, freevar) in freevars.iter().enumerate() {
565         let datum = expr::trans_local_var(bcx, freevar.def);
566         let upvar_slot_dest = adt::trans_field_ptr(bcx,
567                                                    &*repr,
568                                                    dest_addr,
569                                                    0,
570                                                    i);
571         match freevar_mode {
572             ast::CaptureByValue => {
573                 bcx = datum.store_to(bcx, upvar_slot_dest);
574             }
575             ast::CaptureByRef => {
576                 Store(bcx, datum.to_llref(), upvar_slot_dest);
577             }
578         }
579     }
580     adt::trans_set_discr(bcx, &*repr, dest_addr, 0);
581
582     bcx
583 }
584