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.
15 The goal of this file is to compute which
16 expressions/patterns/captures correspond to *moves*. This is
17 generally a function of the context in which the expression appears as
18 well as the expression's type.
22 We will use the following fragment of code to explain the various
23 considerations. Note that in this code `x` is used after it has been
24 moved here. This is not relevant to this pass, though the information
25 we compute would later be used to detect this error (see the section
26 Enforcement of Moves, below).
28 struct Foo { a: int, b: ~int }
30 let w = (x {Read}).a; // Read
31 let y = (x {Move}).b; // Move
32 let z = copy (x {Read}).b; // Read
34 Let's look at these examples one by one. In the first case, `w`, the
35 expression being assigned is `x.a`, which has `int` type. In that
36 case, the value is read, and the container (`x`) is also read.
38 In the second case, `y`, `x.b` is being assigned which has type
39 `~int`. Because this type moves by default, that will be a move
40 reference. Whenever we move from a compound expression like `x.b` (or
41 `x[b]` or `*x` or `{x}[b].c`, etc), this invalidates all containing
42 expressions since we do not currently permit "incomplete" variables
43 where part of them has been moved and part has not. In this case,
44 this means that the reference to `x` is also a move. We'll see later,
45 though, that these kind of "partial moves", where part of the
46 expression has been moved, are classified and stored somewhat
49 The final example (`z`) is `copy x.b`: in this case, although the
50 expression being assigned has type `~int`, there are no moves
55 For each binding in a match or let pattern, we also compute a read
56 or move designation. A move binding means that the value will be
57 moved from the value being matched. As a result, the expression
58 being matched (aka, the 'discriminant') is either moved or read
59 depending on whether the bindings move the value they bind to out of
62 For examples, consider this match expression:
65 Foo { a: a {Read}, b: b {Move} } => {...}
68 Here, the binding `b` is value (not ref) mode, and `b` has type
69 `~int`, and therefore the discriminant expression `x` would be
70 incomplete so it also considered moved.
72 In the following two examples, in contrast, the mode of `b` is either
73 `copy` or `ref` and hence the overall result is a read:
76 Foo { a: a {Read}, b: copy b {Read} } => {...}
80 Foo { a: a {Read}, b: ref b {Read} } => {...}
83 Similar reasoning can be applied to `let` expressions:
85 let Foo { a: a {Read}, b: b {Move} } = x {Move};
86 let Foo { a: a {Read}, b: copy b {Read} } = x {Read};
87 let Foo { a: a {Read}, b: ref b {Read} } = x {Read};
91 The pass results in the struct `MoveMaps` which contains several
94 `moves_map` is a set containing the id of every *outermost expression* or
95 *binding* that causes a move. Note that `moves_map` only contains the *outermost
96 expressions* that are moved. Therefore, if you have a use of `x.b`,
97 as in the example `y` above, the expression `x.b` would be in the
98 `moves_map` but not `x`. The reason for this is that, for most
99 purposes, it's only the outermost expression that is needed. The
100 borrow checker and trans, for example, only care about the outermost
101 expressions that are moved. It is more efficient therefore just to
104 Sometimes though we want to know the variables that are moved (in
105 particular in the borrow checker). For these cases, the set
106 `moved_variables_set` just collects the ids of variables that are
109 Finally, the `capture_map` maps from the node_id of a closure
110 expression to an array of `CaptureVar` structs detailing which
111 variables are captured and how (by ref, by copy, by move).
113 ## Enforcement of Moves
115 The enforcement of moves is done by the borrow checker. Please see
116 the section "Moves and initialization" in `middle/borrowck/doc.rs`.
118 ## Distributive property
120 Copies are "distributive" over parenthesization, but blocks are
121 considered rvalues. What this means is that, for example, neither
122 `a.clone()` nor `(a).clone()` will move `a` (presuming that `a` has a
123 linear type and `clone()` takes its self by reference), but
124 `{a}.clone()` will move `a`, as would `(if cond {a} else {b}).clone()`
130 use middle::pat_util::{pat_bindings};
131 use middle::freevars;
133 use middle::typeck::MethodMap;
135 use util::ppaux::Repr;
136 use util::common::indenter;
137 use util::ppaux::UserString;
138 use util::nodemap::{NodeMap, NodeSet};
140 use std::cell::RefCell;
143 use syntax::ast_util;
145 use syntax::visit::Visitor;
146 use syntax::codemap::Span;
148 #[deriving(Eq, Encodable, Decodable)]
149 pub enum CaptureMode {
150 CapCopy, // Copy the value into the closure.
151 CapMove, // Move the value into the closure.
152 CapRef, // Reference directly from parent stack frame (used by `||`).
155 #[deriving(Encodable, Decodable)]
156 pub struct CaptureVar {
157 def: Def, // Variable being accessed free
158 span: Span, // Location of an access to this variable
159 mode: CaptureMode // How variable is being accessed
162 pub type CaptureMap = @RefCell<NodeMap<Rc<Vec<CaptureVar> >>>;
164 pub type MovesMap = @RefCell<NodeSet>;
167 * Set of variable node-ids that are moved.
169 * Note: The `VariableMovesMap` stores expression ids that
170 * are moves, whereas this set stores the ids of the variables
171 * that are moved at some point */
172 pub type MovedVariablesSet = @RefCell<NodeSet>;
174 /** See the section Output on the module comment for explanation. */
176 pub struct MoveMaps {
178 moved_variables_set: MovedVariablesSet,
179 capture_map: CaptureMap
183 struct VisitContext {
185 method_map: MethodMap,
191 Move, // This value or something owned by it is moved.
192 Read // Read no matter what the type.
195 impl visit::Visitor<()> for VisitContext {
196 fn visit_fn(&mut self, fk: &visit::FnKind, fd: &FnDecl,
197 b: &Block, s: Span, n: NodeId, _: ()) {
198 compute_modes_for_fn(self, fk, fd, b, s, n);
200 fn visit_expr(&mut self, ex: &Expr, _: ()) {
201 compute_modes_for_expr(self, ex);
203 fn visit_local(&mut self, l: &Local, _: ()) {
204 compute_modes_for_local(self, l);
206 // FIXME(#10894) should continue recursing
207 fn visit_ty(&mut self, _t: &Ty, _: ()) {}
210 pub fn compute_moves(tcx: ty::ctxt,
211 method_map: MethodMap,
212 krate: &Crate) -> MoveMaps
214 let mut visit_cx = VisitContext {
216 method_map: method_map,
217 move_maps: MoveMaps {
218 moves_map: @RefCell::new(NodeSet::new()),
219 capture_map: @RefCell::new(NodeMap::new()),
220 moved_variables_set: @RefCell::new(NodeSet::new())
223 let visit_cx = &mut visit_cx;
224 visit::walk_crate(visit_cx, krate, ());
225 return visit_cx.move_maps;
228 pub fn moved_variable_node_id_from_def(def: Def) -> Option<NodeId> {
232 DefLocal(nid, _) => Some(nid),
238 ///////////////////////////////////////////////////////////////////////////
241 fn compute_modes_for_local<'a>(cx: &mut VisitContext,
243 cx.use_pat(local.pat);
244 for &init in local.init.iter() {
245 cx.use_expr(init, Read);
249 fn compute_modes_for_fn(cx: &mut VisitContext,
255 for a in decl.inputs.iter() {
258 visit::walk_fn(cx, fk, decl, body, span, id, ());
261 fn compute_modes_for_expr(cx: &mut VisitContext,
264 cx.consume_expr(expr);
268 pub fn consume_exprs(&mut self, exprs: &[@Expr]) {
269 for expr in exprs.iter() {
270 self.consume_expr(*expr);
274 pub fn consume_expr(&mut self, expr: &Expr) {
276 * Indicates that the value of `expr` will be consumed,
277 * meaning either copied or moved depending on its type.
280 debug!("consume_expr(expr={})",
281 expr.repr(self.tcx));
283 let expr_ty = ty::expr_ty_adjusted(self.tcx, expr);
284 if ty::type_moves_by_default(self.tcx, expr_ty) {
286 let mut moves_map = self.move_maps.moves_map.borrow_mut();
287 moves_map.get().insert(expr.id);
289 self.use_expr(expr, Move);
291 self.use_expr(expr, Read);
295 pub fn consume_block(&mut self, blk: &Block) {
297 * Indicates that the value of `blk` will be consumed,
298 * meaning either copied or moved depending on its type.
301 debug!("consume_block(blk.id={:?})", blk.id);
303 for stmt in blk.stmts.iter() {
304 self.visit_stmt(*stmt, ());
307 for tail_expr in blk.expr.iter() {
308 self.consume_expr(*tail_expr);
312 pub fn use_expr(&mut self,
314 expr_mode: UseMode) {
316 * Indicates that `expr` is used with a given mode. This will
317 * in turn trigger calls to the subcomponents of `expr`.
320 debug!("use_expr(expr={}, mode={:?})",
324 // `expr_mode` refers to the post-adjustment value. If one of
325 // those adjustments is to take a reference, then it's only
326 // reading the underlying expression, not moving it.
328 let adjustments = self.tcx.adjustments.borrow();
329 match adjustments.get().find(&expr.id) {
330 Some(adjustment) => {
332 ty::AutoDerefRef(ty::AutoDerefRef {
343 debug!("comp_mode = {:?}", comp_mode);
349 let def_map = self.tcx.def_map.borrow();
350 let def = def_map.get().get_copy(&expr.id);
351 let r = moved_variable_node_id_from_def(def);
352 for &id in r.iter() {
353 let mut moved_variables_set =
357 moved_variables_set.get().insert(id);
364 ExprUnary(UnDeref, base) => { // *base
365 if !self.use_overloaded_operator(expr, base, [])
367 // Moving out of *base moves out of base.
368 self.use_expr(base, comp_mode);
372 ExprField(base, _, _) => { // base.f
373 // Moving out of base.f moves out of base.
374 self.use_expr(base, comp_mode);
377 ExprIndex(lhs, rhs) => { // lhs[rhs]
378 if !self.use_overloaded_operator(expr, lhs, [rhs])
380 self.use_expr(lhs, comp_mode);
381 self.consume_expr(rhs);
385 ExprCall(callee, ref args) => { // callee(args)
386 // Figure out whether the called function is consumed.
387 let mode = match ty::get(ty::expr_ty(self.tcx, callee)).sty {
388 ty::ty_closure(ref cty) => {
394 ty::ty_bare_fn(..) => Read,
396 self.tcx.sess.span_bug(callee.span,
397 format!("non-function type in moves for expr_call: {:?}", x)),
399 // Note we're not using consume_expr, which uses type_moves_by_default
400 // to determine the mode, for this. The reason is that while stack
401 // closures should be noncopyable, they shouldn't move by default;
402 // calling a closure should only consume it if it's once.
405 let mut moves_map = self.move_maps
408 moves_map.get().insert(callee.id);
411 self.use_expr(callee, mode);
412 self.use_fn_args(args.as_slice());
415 ExprMethodCall(_, _, ref args) => { // callee.m(args)
416 self.use_fn_args(args.as_slice());
419 ExprStruct(_, ref fields, opt_with) => {
420 for field in fields.iter() {
421 self.consume_expr(field.expr);
424 for with_expr in opt_with.iter() {
425 // If there are any fields whose type is move-by-default,
426 // then `with` is consumed, otherwise it is only read
427 let with_ty = ty::expr_ty(self.tcx, *with_expr);
428 let with_fields = match ty::get(with_ty).sty {
429 ty::ty_struct(did, ref substs) => {
430 ty::struct_fields(self.tcx, did, substs)
433 self.tcx.sess.span_bug(
435 format!("bad base expr type in record: {:?}", r))
439 // The `with` expr must be consumed if it contains
440 // any fields which (1) were not explicitly
441 // specified and (2) have a type that
443 let consume_with = with_fields.iter().any(|tf| {
444 !fields.iter().any(|f| f.ident.node.name == tf.ident.name) &&
445 ty::type_moves_by_default(self.tcx, tf.mt.ty)
448 fn has_dtor(tcx: ty::ctxt, ty: ty::t) -> bool {
449 use middle::ty::{get,ty_struct,ty_enum};
451 ty_struct(did, _) | ty_enum(did, _) => ty::has_dtor(tcx, did),
457 if has_dtor(self.tcx, with_ty) {
458 self.tcx.sess.span_err(with_expr.span,
459 format!("cannot move out of type `{}`, \
460 which defines the `Drop` trait",
461 with_ty.user_string(self.tcx)));
463 self.consume_expr(*with_expr);
465 self.use_expr(*with_expr, Read);
470 ExprTup(ref exprs) => {
471 self.consume_exprs(exprs.as_slice());
474 ExprIf(cond_expr, then_blk, opt_else_expr) => {
475 self.consume_expr(cond_expr);
476 self.consume_block(then_blk);
477 for else_expr in opt_else_expr.iter() {
478 self.consume_expr(*else_expr);
482 ExprMatch(discr, ref arms) => {
483 for arm in arms.iter() {
484 self.consume_arm(arm);
487 // The discriminant may, in fact, be partially moved
488 // if there are by-move bindings, but borrowck deals
490 self.use_expr(discr, Read);
494 // Note: base is not considered a *component* here, so
495 // use `expr_mode` not `comp_mode`.
496 self.use_expr(base, expr_mode);
499 ExprVec(ref exprs, _) => {
500 self.consume_exprs(exprs.as_slice());
503 ExprAddrOf(_, base) => { // &base
504 self.use_expr(base, Read);
513 ExprLoop(blk, _) => {
514 self.consume_block(blk);
517 ExprWhile(cond_expr, blk) => {
518 self.consume_expr(cond_expr);
519 self.consume_block(blk);
522 ExprForLoop(..) => fail!("non-desugared expr_for_loop"),
524 ExprUnary(_, lhs) => {
525 if !self.use_overloaded_operator(expr, lhs, [])
527 self.consume_expr(lhs);
531 ExprBinary(_, lhs, rhs) => {
532 if !self.use_overloaded_operator(expr, lhs, [rhs])
534 self.consume_expr(lhs);
535 self.consume_expr(rhs);
540 self.consume_block(blk);
543 ExprRet(ref opt_expr) => {
544 for expr in opt_expr.iter() {
545 self.consume_expr(*expr);
549 ExprAssign(lhs, rhs) => {
550 self.use_expr(lhs, Read);
551 self.consume_expr(rhs);
554 ExprCast(base, _) => {
555 self.consume_expr(base);
558 ExprAssignOp(_, lhs, rhs) => {
559 // FIXME(#4712) --- Overloaded operators?
561 // if !self.use_overloaded_operator(expr, DoDerefArgs, lhs, [rhs])
563 self.consume_expr(lhs);
564 self.consume_expr(rhs);
568 ExprRepeat(base, count, _) => {
569 self.consume_expr(base);
570 self.consume_expr(count);
573 ExprFnBlock(ref decl, body) |
574 ExprProc(ref decl, body) => {
575 for a in decl.inputs.iter() {
578 let cap_vars = self.compute_captures(expr.id);
580 let mut capture_map = self.move_maps
583 capture_map.get().insert(expr.id, cap_vars);
585 self.consume_block(body);
588 ExprVstore(base, _) => {
589 self.use_expr(base, comp_mode);
592 ExprBox(place, base) => {
593 self.use_expr(place, comp_mode);
594 self.use_expr(base, comp_mode);
598 self.tcx.sess.span_bug(
600 "macro expression remains after expansion");
605 pub fn use_overloaded_operator(&mut self,
607 receiver_expr: @Expr,
610 let method_map = self.method_map.borrow();
611 if !method_map.get().contains_key(&expr.id) {
615 self.use_fn_arg(receiver_expr);
617 // for overloaded operatrs, we are always passing in a
618 // reference, so it's always read mode:
619 for arg_expr in arg_exprs.iter() {
620 self.use_expr(*arg_expr, Read);
626 pub fn consume_arm(&mut self, arm: &Arm) {
627 for pat in arm.pats.iter() {
631 for guard in arm.guard.iter() {
632 self.consume_expr(*guard);
635 self.consume_expr(arm.body);
638 pub fn use_pat(&mut self, pat: @Pat) {
641 * Decides whether each binding in a pattern moves the value
642 * into itself or not based on its type and annotation.
645 pat_bindings(self.tcx.def_map, pat, |bm, id, _span, path| {
646 let binding_moves = match bm {
647 BindByRef(_) => false,
649 let pat_ty = ty::node_id_to_type(self.tcx, id);
650 debug!("pattern {:?} {} type is {}",
652 ast_util::path_to_ident(path).repr(self.tcx),
653 pat_ty.repr(self.tcx));
654 ty::type_moves_by_default(self.tcx, pat_ty)
658 debug!("pattern binding {:?}: bm={:?}, binding_moves={}",
659 id, bm, binding_moves);
663 let mut moves_map = self.move_maps.moves_map.borrow_mut();
664 moves_map.get().insert(id);
670 pub fn use_fn_args(&mut self,
671 arg_exprs: &[@Expr]) {
672 //! Uses the argument expressions.
673 for arg_expr in arg_exprs.iter() {
674 self.use_fn_arg(*arg_expr);
678 pub fn use_fn_arg(&mut self, arg_expr: @Expr) {
679 //! Uses the argument.
680 self.consume_expr(arg_expr)
683 pub fn compute_captures(&mut self, fn_expr_id: NodeId) -> Rc<Vec<CaptureVar> > {
684 debug!("compute_capture_vars(fn_expr_id={:?})", fn_expr_id);
685 let _indenter = indenter();
687 let fn_ty = ty::node_id_to_type(self.tcx, fn_expr_id);
688 let sigil = ty::ty_closure_sigil(fn_ty);
689 let freevars = freevars::get_freevars(self.tcx, fn_expr_id);
690 let v = if sigil == BorrowedSigil {
691 // || captures everything by ref
693 .map(|fvar| CaptureVar {def: fvar.def, span: fvar.span, mode: CapRef})
696 // @fn() and ~fn() capture by copy or by move depending on type
699 let fvar_def_id = ast_util::def_id_of_def(fvar.def).node;
700 let fvar_ty = ty::node_id_to_type(self.tcx, fvar_def_id);
701 debug!("fvar_def_id={:?} fvar_ty={}",
702 fvar_def_id, ppaux::ty_to_str(self.tcx, fvar_ty));
703 let mode = if ty::type_moves_by_default(self.tcx, fvar_ty) {
708 CaptureVar {def: fvar.def, span: fvar.span, mode:mode}