1 // Copyright 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.
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.
12 * A different sort of visitor for walking fn bodies. Unlike the
13 * normal visitor, which just walks the entire body in one shot, the
14 * `ExprUseVisitor` determines how expressions are being used.
17 use mc = middle::mem_categorization;
22 use middle::typeck::MethodCall;
25 use syntax::codemap::{Span};
26 use util::ppaux::Repr;
28 ///////////////////////////////////////////////////////////////////////////
31 /// This trait defines the callbacks you can expect to receive when
32 /// employing the ExprUseVisitor.
34 // The value found at `cmt` is either copied or moved, depending
37 consume_id: ast::NodeId,
42 // The value found at `cmt` is either copied or moved via the
43 // pattern binding `consume_pat`, depending on mode.
44 fn consume_pat(&mut self,
45 consume_pat: &ast::Pat,
49 // The value found at `borrow` is being borrowed at the point
50 // `borrow_id` for the region `loan_region` with kind `bk`.
52 borrow_id: ast::NodeId,
55 loan_region: ty::Region,
57 loan_cause: LoanCause);
59 // The local variable `id` is declared but not initialized.
60 fn decl_without_init(&mut self,
64 // The path at `cmt` is being assigned to.
66 assignment_id: ast::NodeId,
67 assignment_span: Span,
68 assignee_cmt: mc::cmt,
72 #[deriving(PartialEq)]
82 #[deriving(PartialEq,Show)]
83 pub enum ConsumeMode {
84 Copy, // reference to x where x has a type that copies
85 Move(MoveReason), // reference to x where x has a type that moves
88 #[deriving(PartialEq,Show)]
95 #[deriving(PartialEq,Show)]
99 WriteAndRead, // x += y
102 ///////////////////////////////////////////////////////////////////////////
103 // The ExprUseVisitor type
105 // This is the code that actually walks the tree. Like
106 // mem_categorization, it requires a TYPER, which is a type that
107 // supplies types from the tree. After type checking is complete, you
108 // can just use the tcx as the typer.
110 pub struct ExprUseVisitor<'d,'t,TYPER> {
112 mc: mc::MemCategorizationContext<'t,TYPER>,
113 delegate: &'d mut Delegate,
116 // If the TYPER results in an error, it's because the type check
117 // failed (or will fail, when the error is uncovered and reported
118 // during writeback). In this case, we just ignore this part of the
121 // Note that this macro appears similar to try!(), but, unlike try!(),
122 // it does not propagate the error.
123 macro_rules! return_if_err(
132 impl<'d,'t,TYPER:mc::Typer> ExprUseVisitor<'d,'t,TYPER> {
133 pub fn new(delegate: &'d mut Delegate,
135 -> ExprUseVisitor<'d,'t,TYPER> {
136 ExprUseVisitor { typer: typer,
137 mc: mc::MemCategorizationContext::new(typer),
141 pub fn walk_fn(&mut self,
144 self.walk_arg_patterns(decl, body);
145 self.walk_block(body);
148 fn walk_arg_patterns(&mut self,
151 for arg in decl.inputs.iter() {
152 let arg_ty = ty::node_id_to_type(self.tcx(), arg.pat.id);
154 let arg_cmt = self.mc.cat_rvalue(
157 ty::ReScope(body.id), // Args live only as long as the fn body.
160 self.walk_pat(arg_cmt, arg.pat);
164 fn tcx<'a>(&'a self) -> &'a ty::ctxt {
168 fn delegate_consume(&mut self,
169 consume_id: ast::NodeId,
172 let mode = copy_or_move(self.tcx(), cmt.ty, DirectRefMove);
173 self.delegate.consume(consume_id, consume_span, cmt, mode);
176 fn consume_exprs(&mut self, exprs: &Vec<@ast::Expr>) {
177 for &expr in exprs.iter() {
178 self.consume_expr(expr);
182 fn consume_expr(&mut self, expr: &ast::Expr) {
183 debug!("consume_expr(expr={})", expr.repr(self.tcx()));
185 let cmt = return_if_err!(self.mc.cat_expr(expr));
186 self.delegate_consume(expr.id, expr.span, cmt);
189 ast::ExprParen(subexpr) => {
190 // Argh but is ExprParen horrible. So, if we consume
191 // `(x)`, that generally is also consuming `x`, UNLESS
192 // there are adjustments on the `(x)` expression
193 // (e.g., autoderefs and autorefs).
194 if self.typer.adjustments().borrow().contains_key(&expr.id) {
195 self.walk_expr(expr);
197 self.consume_expr(subexpr);
207 fn mutate_expr(&mut self,
208 assignment_expr: &ast::Expr,
211 let cmt = return_if_err!(self.mc.cat_expr(expr));
212 self.delegate.mutate(assignment_expr.id, assignment_expr.span, cmt, mode);
213 self.walk_expr(expr);
216 fn borrow_expr(&mut self,
221 debug!("borrow_expr(expr={}, r={}, bk={})",
222 expr.repr(self.tcx()), r.repr(self.tcx()), bk.repr(self.tcx()));
224 let cmt = return_if_err!(self.mc.cat_expr(expr));
225 self.delegate.borrow(expr.id, expr.span, cmt, r, bk, cause);
227 // Note: Unlike consume, we can ignore ExprParen. cat_expr
228 // already skips over them, and walk will uncover any
229 // attachments or whatever.
233 fn select_from_expr(&mut self, expr: &ast::Expr) {
237 fn walk_expr(&mut self, expr: &ast::Expr) {
238 debug!("walk_expr(expr={})", expr.repr(self.tcx()));
240 self.walk_adjustment(expr);
243 ast::ExprParen(subexpr) => {
244 self.walk_expr(subexpr)
247 ast::ExprPath(..) => { }
249 ast::ExprUnary(ast::UnDeref, base) => { // *base
250 if !self.walk_overloaded_operator(expr, base, []) {
251 self.select_from_expr(base);
255 ast::ExprField(base, _, _) => { // base.f
256 self.select_from_expr(base);
259 ast::ExprIndex(lhs, rhs) => { // lhs[rhs]
260 if !self.walk_overloaded_operator(expr, lhs, [rhs]) {
261 self.select_from_expr(lhs);
262 self.consume_expr(rhs);
266 ast::ExprCall(callee, ref args) => { // callee(args)
267 self.walk_callee(expr, callee);
268 self.consume_exprs(args);
271 ast::ExprMethodCall(_, _, ref args) => { // callee.m(args)
272 self.consume_exprs(args);
275 ast::ExprStruct(_, ref fields, opt_with) => {
276 self.walk_struct_expr(expr, fields, opt_with);
279 ast::ExprTup(ref exprs) => {
280 self.consume_exprs(exprs);
283 ast::ExprIf(cond_expr, then_blk, opt_else_expr) => {
284 self.consume_expr(cond_expr);
285 self.walk_block(then_blk);
286 for else_expr in opt_else_expr.iter() {
287 self.consume_expr(*else_expr);
291 ast::ExprMatch(discr, ref arms) => {
292 // treatment of the discriminant is handled while
294 self.walk_expr(discr);
295 let discr_cmt = return_if_err!(self.mc.cat_expr(discr));
296 for arm in arms.iter() {
297 self.walk_arm(discr_cmt.clone(), arm);
301 ast::ExprVec(ref exprs) => {
302 self.consume_exprs(exprs);
305 ast::ExprAddrOf(m, base) => { // &base
306 // make sure that the thing we are pointing out stays valid
307 // for the lifetime `scope_r` of the resulting ptr:
308 let expr_ty = ty::expr_ty(self.tcx(), expr);
309 if !ty::type_is_bot(expr_ty) {
310 let r = ty::ty_region(self.tcx(), expr.span, expr_ty);
311 let bk = ty::BorrowKind::from_mutbl(m);
312 self.borrow_expr(base, r, bk, AddrOf);
314 self.walk_expr(base);
318 ast::ExprInlineAsm(ref ia) => {
319 for &(_, input) in ia.inputs.iter() {
320 self.consume_expr(input);
323 for &(_, output) in ia.outputs.iter() {
324 self.mutate_expr(expr, output, JustWrite);
330 ast::ExprLit(..) => {}
332 ast::ExprLoop(blk, _) => {
333 self.walk_block(blk);
336 ast::ExprWhile(cond_expr, blk) => {
337 self.consume_expr(cond_expr);
338 self.walk_block(blk);
341 ast::ExprForLoop(..) => fail!("non-desugared expr_for_loop"),
343 ast::ExprUnary(_, lhs) => {
344 if !self.walk_overloaded_operator(expr, lhs, []) {
345 self.consume_expr(lhs);
349 ast::ExprBinary(_, lhs, rhs) => {
350 if !self.walk_overloaded_operator(expr, lhs, [rhs]) {
351 self.consume_expr(lhs);
352 self.consume_expr(rhs);
356 ast::ExprBlock(blk) => {
357 self.walk_block(blk);
360 ast::ExprRet(ref opt_expr) => {
361 for expr in opt_expr.iter() {
362 self.consume_expr(*expr);
366 ast::ExprAssign(lhs, rhs) => {
367 self.mutate_expr(expr, lhs, JustWrite);
368 self.consume_expr(rhs);
371 ast::ExprCast(base, _) => {
372 self.consume_expr(base);
375 ast::ExprAssignOp(_, lhs, rhs) => {
376 // This will have to change if/when we support
377 // overloaded operators for `+=` and so forth.
378 self.mutate_expr(expr, lhs, WriteAndRead);
379 self.consume_expr(rhs);
382 ast::ExprRepeat(base, count) => {
383 self.consume_expr(base);
384 self.consume_expr(count);
387 ast::ExprFnBlock(..) |
388 ast::ExprProc(..) => {
389 self.walk_captures(expr)
392 ast::ExprVstore(base, _) => {
393 self.consume_expr(base);
396 ast::ExprBox(place, base) => {
397 self.consume_expr(place);
398 self.consume_expr(base);
401 ast::ExprMac(..) => {
402 self.tcx().sess.span_bug(
404 "macro expression remains after expansion");
409 fn walk_callee(&mut self, call: &ast::Expr, callee: &ast::Expr) {
410 let callee_ty = ty::expr_ty_adjusted(self.tcx(), callee);
411 debug!("walk_callee: callee={} callee_ty={}",
412 callee.repr(self.tcx()), callee_ty.repr(self.tcx()));
413 match ty::get(callee_ty).sty {
414 ty::ty_bare_fn(..) => {
415 self.consume_expr(callee);
417 ty::ty_closure(ref f) => {
420 self.borrow_expr(callee,
421 ty::ReScope(call.id),
426 self.consume_expr(callee);
434 .find(&MethodCall::expr(call.id)) {
436 // FIXME(#14774, pcwalton): Implement this.
439 self.tcx().sess.span_bug(
441 format!("unxpected callee type {}",
442 callee_ty.repr(self.tcx())).as_slice());
449 fn walk_stmt(&mut self, stmt: &ast::Stmt) {
451 ast::StmtDecl(decl, _) => {
453 ast::DeclLocal(local) => {
454 self.walk_local(local);
457 ast::DeclItem(_) => {
458 // we don't visit nested items in this visitor,
459 // only the fn body we were given.
464 ast::StmtExpr(expr, _) |
465 ast::StmtSemi(expr, _) => {
466 self.consume_expr(expr);
469 ast::StmtMac(..) => {
470 self.tcx().sess.span_bug(stmt.span, "unexpanded stmt macro");
475 fn walk_local(&mut self, local: @ast::Local) {
478 let delegate = &mut self.delegate;
479 pat_util::pat_bindings(&self.typer.tcx().def_map, local.pat, |_, id, span, _| {
480 delegate.decl_without_init(id, span);
485 // Variable declarations with
486 // initializers are considered
487 // "assigns", which is handled by
489 self.walk_expr(expr);
490 let init_cmt = return_if_err!(self.mc.cat_expr(expr));
491 self.walk_pat(init_cmt, local.pat);
496 fn walk_block(&mut self, blk: &ast::Block) {
498 * Indicates that the value of `blk` will be consumed,
499 * meaning either copied or moved depending on its type.
502 debug!("walk_block(blk.id={:?})", blk.id);
504 for stmt in blk.stmts.iter() {
505 self.walk_stmt(*stmt);
508 for tail_expr in blk.expr.iter() {
509 self.consume_expr(*tail_expr);
513 fn walk_struct_expr(&mut self,
515 fields: &Vec<ast::Field>,
516 opt_with: Option<@ast::Expr>) {
517 // Consume the expressions supplying values for each field.
518 for field in fields.iter() {
519 self.consume_expr(field.expr);
522 let with_expr = match opt_with {
527 let with_cmt = return_if_err!(self.mc.cat_expr(with_expr));
529 // Select just those fields of the `with`
530 // expression that will actually be used
531 let with_fields = match ty::get(with_cmt.ty).sty {
532 ty::ty_struct(did, ref substs) => {
533 ty::struct_fields(self.tcx(), did, substs)
536 self.tcx().sess.span_bug(
538 "with expression doesn't evaluate to a struct");
542 // Consume those fields of the with expression that are needed.
543 for with_field in with_fields.iter() {
544 if !contains_field_named(with_field, fields) {
545 let cmt_field = self.mc.cat_field(with_expr,
549 self.delegate_consume(with_expr.id, with_expr.span, cmt_field);
553 fn contains_field_named(field: &ty::field,
554 fields: &Vec<ast::Field>)
558 |f| f.ident.node.name == field.ident.name)
562 // Invoke the appropriate delegate calls for anything that gets
563 // consumed or borrowed as part of the automatic adjustment
565 fn walk_adjustment(&mut self, expr: &ast::Expr) {
566 let typer = self.typer;
567 match typer.adjustments().borrow().find(&expr.id) {
569 Some(adjustment) => {
572 ty::AutoObject(..) => {
573 // Creating an object or closure consumes the
574 // input and stores it into the resulting rvalue.
575 debug!("walk_adjustment(AutoAddEnv|AutoObject)");
577 return_if_err!(self.mc.cat_expr_unadjusted(expr));
578 self.delegate_consume(expr.id, expr.span, cmt_unadjusted);
580 ty::AutoDerefRef(ty::AutoDerefRef {
581 autoref: ref opt_autoref,
584 self.walk_autoderefs(expr, n);
589 self.walk_autoref(expr, r, n);
598 fn walk_autoderefs(&mut self,
602 * Autoderefs for overloaded Deref calls in fact reference
603 * their receiver. That is, if we have `(*x)` where `x` is of
604 * type `Rc<T>`, then this in fact is equivalent to
605 * `x.deref()`. Since `deref()` is declared with `&self`, this
606 * is an autoref of `x`.
608 debug!("walk_autoderefs expr={} autoderefs={}", expr.repr(self.tcx()), autoderefs);
610 for i in range(0, autoderefs) {
611 let deref_id = typeck::MethodCall::autoderef(expr.id, i as u32);
612 match self.typer.node_method_ty(deref_id) {
615 let cmt = return_if_err!(self.mc.cat_expr_autoderefd(expr, i));
616 let self_ty = *ty::ty_fn_args(method_ty).get(0);
617 let (m, r) = match ty::get(self_ty).sty {
618 ty::ty_rptr(r, ref m) => (m.mutbl, r),
619 _ => self.tcx().sess.span_bug(expr.span,
620 format!("bad overloaded deref type {}",
621 method_ty.repr(self.tcx())).as_slice())
623 let bk = ty::BorrowKind::from_mutbl(m);
624 self.delegate.borrow(expr.id, expr.span, cmt,
631 fn walk_autoref(&mut self,
633 autoref: &ty::AutoRef,
635 debug!("walk_autoref expr={} autoderefs={}", expr.repr(self.tcx()), autoderefs);
637 let cmt_derefd = return_if_err!(
638 self.mc.cat_expr_autoderefd(expr, autoderefs));
640 debug!("walk_autoref: cmt_derefd={}", cmt_derefd.repr(self.tcx()));
643 ty::AutoPtr(r, m) => {
644 self.delegate.borrow(expr.id,
648 ty::BorrowKind::from_mutbl(m),
651 ty::AutoBorrowVec(r, m) | ty::AutoBorrowVecRef(r, m) => {
652 let cmt_index = self.mc.cat_index(expr, cmt_derefd, autoderefs+1);
653 self.delegate.borrow(expr.id,
657 ty::BorrowKind::from_mutbl(m),
660 ty::AutoBorrowObj(r, m) => {
661 let cmt_deref = self.mc.cat_deref_obj(expr, cmt_derefd);
662 self.delegate.borrow(expr.id,
666 ty::BorrowKind::from_mutbl(m),
669 ty::AutoUnsafe(_) => {}
673 fn walk_overloaded_operator(&mut self,
675 receiver: &ast::Expr,
679 if !self.typer.is_method_call(expr.id) {
683 self.walk_expr(receiver);
685 // Arguments (but not receivers) to overloaded operator
686 // methods are implicitly autoref'd which sadly does not use
687 // adjustments, so we must hardcode the borrow here.
689 let r = ty::ReScope(expr.id);
690 let bk = ty::ImmBorrow;
692 for &arg in args.iter() {
693 self.borrow_expr(arg, r, bk, OverloadedOperator);
698 fn walk_arm(&mut self, discr_cmt: mc::cmt, arm: &ast::Arm) {
699 for &pat in arm.pats.iter() {
700 self.walk_pat(discr_cmt.clone(), pat);
703 for guard in arm.guard.iter() {
704 self.consume_expr(*guard);
707 self.consume_expr(arm.body);
710 fn walk_pat(&mut self, cmt_discr: mc::cmt, pat: @ast::Pat) {
711 debug!("walk_pat cmt_discr={} pat={}", cmt_discr.repr(self.tcx()),
712 pat.repr(self.tcx()));
714 let typer = self.typer;
715 let tcx = typer.tcx();
716 let def_map = &self.typer.tcx().def_map;
717 let delegate = &mut self.delegate;
718 return_if_err!(mc.cat_pattern(cmt_discr, pat, |mc, cmt_pat, pat| {
719 if pat_util::pat_is_binding(def_map, pat) {
720 let tcx = typer.tcx();
722 debug!("binding cmt_pat={} pat={}",
726 // pat_ty: the type of the binding being produced.
727 let pat_ty = ty::node_id_to_type(tcx, pat.id);
729 // Each match binding is effectively an assignment to the
730 // binding being produced.
731 let def = def_map.borrow().get_copy(&pat.id);
732 match mc.cat_def(pat.id, pat.span, pat_ty, def) {
734 delegate.mutate(pat.id, pat.span, binding_cmt, Init);
739 // It is also a borrow or copy/move of the value being matched.
741 ast::PatIdent(ast::BindByRef(m), _, _) => {
743 (ty::ty_region(tcx, pat.span, pat_ty),
744 ty::BorrowKind::from_mutbl(m))
746 delegate.borrow(pat.id, pat.span, cmt_pat,
749 ast::PatIdent(ast::BindByValue(_), _, _) => {
750 let mode = copy_or_move(typer.tcx(), cmt_pat.ty, PatBindingMove);
751 delegate.consume_pat(pat, cmt_pat, mode);
754 typer.tcx().sess.span_bug(
756 "binding pattern not an identifier");
761 ast::PatVec(_, Some(slice_pat), _) => {
762 // The `slice_pat` here creates a slice into
763 // the original vector. This is effectively a
764 // borrow of the elements of the vector being
767 let (slice_cmt, slice_mutbl, slice_r) = {
768 match mc.cat_slice_pattern(cmt_pat, slice_pat) {
771 tcx.sess.span_bug(slice_pat.span,
777 // Note: We declare here that the borrow
778 // occurs upon entering the `[...]`
779 // pattern. This implies that something like
780 // `[a, ..b]` where `a` is a move is illegal,
781 // because the borrow is already in effect.
782 // In fact such a move would be safe-ish, but
783 // it effectively *requires* that we use the
784 // nulling out semantics to indicate when a
785 // value has been moved, which we are trying
786 // to move away from. Otherwise, how can we
787 // indicate that the first element in the
788 // vector has been moved? Eventually, we
789 // could perhaps modify this rule to permit
790 // `[..a, b]` where `b` is a move, because in
791 // that case we can adjust the length of the
792 // original vec accordingly, but we'd have to
793 // make trans do the right thing, and it would
794 // only work for `~` vectors. It seems simpler
795 // to just require that people call
796 // `vec.pop()` or `vec.unshift()`.
797 let slice_bk = ty::BorrowKind::from_mutbl(slice_mutbl);
798 delegate.borrow(pat.id, pat.span,
800 slice_bk, RefBinding);
808 fn walk_captures(&mut self, closure_expr: &ast::Expr) {
809 debug!("walk_captures({})", closure_expr.repr(self.tcx()));
811 let tcx = self.typer.tcx();
812 freevars::with_freevars(tcx, closure_expr.id, |freevars| {
813 match freevars::get_capture_mode(self.tcx(), closure_expr.id) {
814 freevars::CaptureByRef => {
815 self.walk_by_ref_captures(closure_expr, freevars);
817 freevars::CaptureByValue => {
818 self.walk_by_value_captures(closure_expr, freevars);
824 fn walk_by_ref_captures(&mut self,
825 closure_expr: &ast::Expr,
826 freevars: &[freevars::freevar_entry]) {
827 for freevar in freevars.iter() {
828 let id_var = freevar.def.def_id().node;
829 let cmt_var = return_if_err!(self.cat_captured_var(closure_expr.id,
833 // Lookup the kind of borrow the callee requires, as
834 // inferred by regionbk
835 let upvar_id = ty::UpvarId { var_id: id_var,
836 closure_expr_id: closure_expr.id };
837 let upvar_borrow = self.tcx().upvar_borrow_map.borrow()
838 .get_copy(&upvar_id);
840 self.delegate.borrow(closure_expr.id,
845 ClosureCapture(freevar.span));
849 fn walk_by_value_captures(&mut self,
850 closure_expr: &ast::Expr,
851 freevars: &[freevars::freevar_entry]) {
852 for freevar in freevars.iter() {
853 let cmt_var = return_if_err!(self.cat_captured_var(closure_expr.id,
856 let mode = copy_or_move(self.tcx(), cmt_var.ty, CaptureMove);
857 self.delegate.consume(closure_expr.id, freevar.span, cmt_var, mode);
861 fn cat_captured_var(&mut self,
862 closure_id: ast::NodeId,
865 -> mc::McResult<mc::cmt> {
866 // Create the cmt for the variable being borrowed, from the
867 // caller's perspective
868 let var_id = upvar_def.def_id().node;
869 let var_ty = ty::node_id_to_type(self.tcx(), var_id);
870 self.mc.cat_def(closure_id, closure_span, var_ty, upvar_def)
874 fn copy_or_move(tcx: &ty::ctxt, ty: ty::t, move_reason: MoveReason) -> ConsumeMode {
875 if ty::type_moves_by_default(tcx, ty) { Move(move_reason) } else { Copy }