1 // Copyright 2012-2013 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.
11 // ----------------------------------------------------------------------
14 // Phase 2 of check: we walk down the tree and check that:
15 // 1. assignments are always made to mutable locations;
16 // 2. loans made in overlapping scopes do not conflict
17 // 3. assignments do not affect things loaned out as immutable
18 // 4. moves do not affect things loaned out in any way
21 use mc = middle::mem_categorization;
22 use middle::borrowck::*;
28 use syntax::codemap::Span;
29 use syntax::parse::token;
30 use syntax::visit::Visitor;
32 use util::ppaux::Repr;
34 struct CheckLoanCtxt<'a> {
35 bccx: &'a BorrowckCtxt,
36 dfcx_loans: &'a LoanDataFlow,
37 move_data: move_data::FlowedMoveData,
38 all_loans: &'a [Loan],
41 impl<'a> Visitor<()> for CheckLoanCtxt<'a> {
43 fn visit_expr(&mut self, ex: &ast::Expr, _: ()) {
44 check_loans_in_expr(self, ex);
46 fn visit_local(&mut self, l: &ast::Local, _: ()) {
47 check_loans_in_local(self, l);
49 fn visit_block(&mut self, b: &ast::Block, _: ()) {
50 check_loans_in_block(self, b);
52 fn visit_pat(&mut self, p: &ast::Pat, _: ()) {
53 check_loans_in_pat(self, p);
55 fn visit_fn(&mut self, fk: &visit::FnKind, fd: &ast::FnDecl,
56 b: &ast::Block, s: Span, n: ast::NodeId, _: ()) {
57 check_loans_in_fn(self, fk, fd, b, s, n);
60 // FIXME(#10894) should continue recursing
61 fn visit_ty(&mut self, _t: &ast::Ty, _: ()) {}
64 pub fn check_loans(bccx: &BorrowckCtxt,
65 dfcx_loans: &LoanDataFlow,
66 move_data: move_data::FlowedMoveData,
69 debug!("check_loans(body id={:?})", body.id);
71 let mut clcx = CheckLoanCtxt {
73 dfcx_loans: dfcx_loans,
78 clcx.visit_block(body, ());
84 MoveWhileBorrowed(/*loan*/@LoanPath, /*loan*/Span)
87 impl<'a> CheckLoanCtxt<'a> {
88 pub fn tcx(&self) -> ty::ctxt { self.bccx.tcx }
90 pub fn each_issued_loan(&self, scope_id: ast::NodeId, op: |&Loan| -> bool)
92 //! Iterates over each loan that has been issued
93 //! on entrance to `scope_id`, regardless of whether it is
94 //! actually *in scope* at that point. Sometimes loans
95 //! are issued for future scopes and thus they may have been
96 //! *issued* but not yet be in effect.
98 self.dfcx_loans.each_bit_on_entry_frozen(scope_id, |loan_index| {
99 let loan = &self.all_loans[loan_index];
104 pub fn each_in_scope_loan(&self,
105 scope_id: ast::NodeId,
108 //! Like `each_issued_loan()`, but only considers loans that are
109 //! currently in scope.
111 let tcx = self.tcx();
112 self.each_issued_loan(scope_id, |loan| {
113 if tcx.region_maps.is_subscope_of(scope_id, loan.kill_scope) {
121 pub fn each_in_scope_restriction(&self,
122 scope_id: ast::NodeId,
123 loan_path: @LoanPath,
124 op: |&Loan, &Restriction| -> bool)
126 //! Iterates through all the in-scope restrictions for the
127 //! given `loan_path`
129 self.each_in_scope_loan(scope_id, |loan| {
130 debug!("each_in_scope_restriction found loan: {:?}",
131 loan.repr(self.tcx()));
134 for restr in loan.restrictions.iter() {
135 if restr.loan_path == loan_path {
136 if !op(loan, restr) {
146 pub fn loans_generated_by(&self, scope_id: ast::NodeId) -> ~[uint] {
147 //! Returns a vector of the loans that are generated as
148 //! we encounter `scope_id`.
150 let mut result = ~[];
151 self.dfcx_loans.each_gen_bit_frozen(scope_id, |loan_index| {
152 result.push(loan_index);
158 pub fn check_for_conflicting_loans(&self, scope_id: ast::NodeId) {
159 //! Checks to see whether any of the loans that are issued
160 //! by `scope_id` conflict with loans that have already been
161 //! issued when we enter `scope_id` (for example, we do not
162 //! permit two `&mut` borrows of the same variable).
164 debug!("check_for_conflicting_loans(scope_id={:?})", scope_id);
166 let new_loan_indices = self.loans_generated_by(scope_id);
167 debug!("new_loan_indices = {:?}", new_loan_indices);
169 self.each_issued_loan(scope_id, |issued_loan| {
170 for &new_loan_index in new_loan_indices.iter() {
171 let new_loan = &self.all_loans[new_loan_index];
172 self.report_error_if_loans_conflict(issued_loan, new_loan);
177 for (i, &x) in new_loan_indices.iter().enumerate() {
178 let old_loan = &self.all_loans[x];
179 for &y in new_loan_indices.slice_from(i+1).iter() {
180 let new_loan = &self.all_loans[y];
181 self.report_error_if_loans_conflict(old_loan, new_loan);
186 pub fn report_error_if_loans_conflict(&self,
189 //! Checks whether `old_loan` and `new_loan` can safely be issued
192 debug!("report_error_if_loans_conflict(old_loan={}, new_loan={})",
193 old_loan.repr(self.tcx()),
194 new_loan.repr(self.tcx()));
196 // Should only be called for loans that are in scope at the same time.
197 assert!(self.tcx().region_maps.scopes_intersect(old_loan.kill_scope,
198 new_loan.kill_scope));
200 self.report_error_if_loan_conflicts_with_restriction(
201 old_loan, new_loan, old_loan, new_loan) &&
202 self.report_error_if_loan_conflicts_with_restriction(
203 new_loan, old_loan, old_loan, new_loan);
206 pub fn report_error_if_loan_conflicts_with_restriction(&self,
212 //! Checks whether the restrictions introduced by `loan1` would
213 //! prohibit `loan2`. Returns false if an error is reported.
215 debug!("report_error_if_loan_conflicts_with_restriction(\
216 loan1={}, loan2={})",
217 loan1.repr(self.tcx()),
218 loan2.repr(self.tcx()));
220 // Restrictions that would cause the new loan to be illegal:
221 let illegal_if = match loan2.mutbl {
222 MutableMutability => RESTR_FREEZE | RESTR_CLAIM,
223 ImmutableMutability => RESTR_FREEZE,
225 debug!("illegal_if={:?}", illegal_if);
227 for restr in loan1.restrictions.iter() {
228 if !restr.set.intersects(illegal_if) { continue; }
229 if restr.loan_path != loan2.loan_path { continue; }
231 match (new_loan.mutbl, old_loan.mutbl) {
232 (_, MutableMutability) => {
233 let var = self.bccx.loan_path_to_str(new_loan.loan_path);
236 format!("cannot borrow `{}` because it is already \
237 borrowed as mutable", var));
240 format!("previous borrow of `{0}` as mutable occurs \
241 here; the mutable borrow prevents subsequent \
242 moves, borrows, or modification of `{0}` \
243 until the borrow ends", var));
249 format!("cannot borrow `{}` as {} because \
250 it is already borrowed as {}",
251 self.bccx.loan_path_to_str(new_loan.loan_path),
252 self.bccx.mut_to_str(new_loan.mutbl),
253 self.bccx.mut_to_str(old_loan.mutbl)));
255 let var = self.bccx.loan_path_to_str(new_loan.loan_path);
256 let mut note = format!("previous borrow of `{}` occurs \
258 if mutability == ImmutableMutability {
259 note.push_str(format!("; the immutable borrow prevents \
260 subsequent moves or mutable
261 borrows of `{}` until the
264 self.bccx.span_note(old_loan.span, note);
268 let old_loan_span = ast_map::node_span(self.tcx().items,
269 old_loan.kill_scope);
270 self.bccx.span_end_note(old_loan_span,
271 "previous borrow ends here");
278 pub fn is_local_variable(&self, cmt: mc::cmt) -> bool {
280 mc::cat_local(_) => true,
285 pub fn check_if_path_is_moved(&self,
288 use_kind: MovedValueUseKind,
291 * Reports an error if `expr` (which should be a path)
292 * is using a moved/uninitialized value
295 debug!("check_if_path_is_moved(id={:?}, use_kind={:?}, lp={})",
296 id, use_kind, lp.repr(self.bccx.tcx));
297 self.move_data.each_move_of(id, lp, |move, moved_lp| {
298 self.bccx.report_use_of_moved_value(
308 pub fn check_assignment(&self, expr: &ast::Expr) {
309 // We don't use cat_expr() here because we don't want to treat
310 // auto-ref'd parameters in overloaded operators as rvalues.
312 let adjustments = self.bccx.tcx.adjustments.borrow();
313 adjustments.get().find_copy(&expr.id)
315 let cmt = match adj {
316 None => self.bccx.cat_expr_unadjusted(expr),
317 Some(adj) => self.bccx.cat_expr_autoderefd(expr, adj)
320 debug!("check_assignment(cmt={})", cmt.repr(self.tcx()));
322 // Mutable values can be assigned, as long as they obey loans
323 // and aliasing restrictions:
324 if cmt.mutbl.is_mutable() {
325 if check_for_aliasable_mutable_writes(self, expr, cmt) {
326 if check_for_assignment_to_restricted_or_frozen_location(
329 // Safe, but record for lint pass later:
330 mark_variable_as_used_mut(self, cmt);
336 // For immutable local variables, assignments are legal
337 // if they cannot already have been assigned
338 if self.is_local_variable(cmt) {
339 assert!(cmt.mutbl.is_immutable()); // no "const" locals
340 let lp = opt_loan_path(cmt).unwrap();
341 self.move_data.each_assignment_of(expr.id, lp, |assign| {
342 self.bccx.report_reassigned_immutable_variable(
351 // Otherwise, just a plain error.
354 format!("cannot assign to {} {}",
355 cmt.mutbl.to_user_str(),
356 self.bccx.cmt_to_str(cmt)));
359 fn mark_variable_as_used_mut(this: &CheckLoanCtxt,
361 //! If the mutability of the `cmt` being written is inherited
362 //! from a local variable, liveness will
363 //! not have been able to detect that this variable's mutability
364 //! is important, so we must add the variable to the
365 //! `used_mut_nodes` table here.
369 debug!("mark_writes_through_upvars_as_used_mut(cmt={})",
370 cmt.repr(this.tcx()));
372 mc::cat_local(id) | mc::cat_arg(id) => {
373 let mut used_mut_nodes = this.tcx()
376 used_mut_nodes.get().insert(id);
380 mc::cat_stack_upvar(b) => {
384 mc::cat_deref(_, _, mc::gc_ptr) => {
385 assert_eq!(cmt.mutbl, mc::McImmutable);
390 mc::cat_static_item |
391 mc::cat_copied_upvar(..) |
392 mc::cat_deref(_, _, mc::unsafe_ptr(..)) |
393 mc::cat_deref(_, _, mc::region_ptr(..)) => {
394 assert_eq!(cmt.mutbl, mc::McDeclared);
398 mc::cat_discr(b, _) |
399 mc::cat_deref(b, _, mc::uniq_ptr) => {
400 assert_eq!(cmt.mutbl, mc::McInherited);
404 mc::cat_downcast(b) |
405 mc::cat_interior(b, _) => {
406 if cmt.mutbl == mc::McInherited {
409 return; // field declared as mutable or some such
416 fn check_for_aliasable_mutable_writes(this: &CheckLoanCtxt,
418 cmt: mc::cmt) -> bool {
419 //! Safety checks related to writes to aliasable, mutable locations
421 let guarantor = cmt.guarantor();
422 debug!("check_for_aliasable_mutable_writes(cmt={}, guarantor={})",
423 cmt.repr(this.tcx()), guarantor.repr(this.tcx()));
424 match guarantor.cat {
425 mc::cat_deref(b, _, mc::region_ptr(ast::MutMutable, _)) => {
426 // Statically prohibit writes to `&mut` when aliasable
428 check_for_aliasability_violation(this, expr, b);
434 return true; // no errors reported
437 fn check_for_aliasability_violation(this: &CheckLoanCtxt,
441 match cmt.freely_aliasable() {
446 this.bccx.report_aliasability_violation(
455 fn check_for_assignment_to_restricted_or_frozen_location(
456 this: &CheckLoanCtxt,
458 cmt: mc::cmt) -> bool
460 //! Check for assignments that violate the terms of an
461 //! outstanding loan.
463 let loan_path = match opt_loan_path(cmt) {
465 None => { return true; /* no loan path, can't be any loans */ }
468 // Start by searching for an assignment to a *restricted*
469 // location. Here is one example of the kind of error caught
472 // let mut v = ~[1, 2, 3];
476 // In this case, creating `p` triggers a RESTR_MUTATE
477 // restriction on the path `v`.
479 // Here is a second, more subtle example:
481 // let mut v = ~[1, 2, 3];
482 // let p = &const v[0];
485 // v = ~[4, 5, 3]; // Error
487 // In this case, `p` is pointing to `v[0]`, and it is a
488 // `const` pointer in any case. So the first two
489 // assignments are legal (and would be permitted by this
490 // check). However, the final assignment (which is
491 // logically equivalent) is forbidden, because it would
492 // cause the existing `v` array to be freed, thus
493 // invalidating `p`. In the code, this error results
494 // because `gather_loans::restrictions` adds a
495 // `RESTR_MUTATE` restriction whenever the contents of an
496 // owned pointer are borrowed, and hence while `v[*]` is not
497 // restricted from being written, `v` is.
498 let cont = this.each_in_scope_restriction(expr.id,
501 if restr.set.intersects(RESTR_MUTATE) {
502 this.report_illegal_mutation(expr, loan_path, loan);
509 if !cont { return false }
511 // The previous code handled assignments to paths that
512 // have been restricted. This covers paths that have been
513 // directly lent out and their base paths, but does not
514 // cover random extensions of those paths. For example,
515 // the following program is not declared illegal by the
518 // let mut v = ~[1, 2, 3];
520 // v[0] = 4; // declared error by loop below, not code above
522 // The reason that this passes the previous check whereas
523 // an assignment like `v = ~[4]` fails is because the assignment
524 // here is to `v[*]`, and the existing restrictions were issued
525 // for `v`, not `v[*]`.
527 // So in this loop, we walk back up the loan path so long
528 // as the mutability of the path is dependent on a super
529 // path, and check that the super path was not lent out as
530 // mutable or immutable (a const loan is ok).
532 // Mutability of a path can be dependent on the super path
533 // in two ways. First, it might be inherited mutability.
534 // Second, the pointee of an `&mut` pointer can only be
535 // mutated if it is found in an unaliased location, so we
536 // have to check that the owner location is not borrowed.
538 // Note that we are *not* checking for any and all
539 // restrictions. We are only interested in the pointers
540 // that the user created, whereas we add restrictions for
541 // all kinds of paths that are not directly aliased. If we checked
542 // for all restrictions, and not just loans, then the following
543 // valid program would be considered illegal:
545 // let mut v = ~[1, 2, 3];
546 // let p = &const v[0];
549 // Here the restriction that `v` not be mutated would be misapplied
550 // to block the subpath `v[1]`.
551 let full_loan_path = loan_path;
552 let mut loan_path = loan_path;
555 // Peel back one layer if, for `loan_path` to be
556 // mutable, `lp_base` must be mutable. This occurs
557 // with inherited mutability and with `&mut`
559 LpExtend(lp_base, mc::McInherited, _) |
560 LpExtend(lp_base, _, LpDeref(mc::region_ptr(ast::MutMutable, _))) => {
564 // Otherwise stop iterating
565 LpExtend(_, mc::McDeclared, _) |
566 LpExtend(_, mc::McImmutable, _) |
572 // Check for a non-const loan of `loan_path`
573 let cont = this.each_in_scope_loan(expr.id, |loan| {
574 if loan.loan_path == loan_path {
575 this.report_illegal_mutation(expr,
584 if !cont { return false }
589 pub fn report_illegal_mutation(&self,
591 loan_path: &LoanPath,
595 format!("cannot assign to `{}` because it is borrowed",
596 self.bccx.loan_path_to_str(loan_path)));
599 format!("borrow of `{}` occurs here",
600 self.bccx.loan_path_to_str(loan_path)));
603 fn check_move_out_from_expr(&self, expr: &ast::Expr) {
605 ast::ExprFnBlock(..) | ast::ExprProc(..) => {
606 // moves due to capture clauses are checked
607 // in `check_loans_in_fn`, so that we can
608 // give a better error message
611 self.check_move_out_from_id(expr.id, expr.span)
616 fn check_move_out_from_id(&self, id: ast::NodeId, span: Span) {
617 self.move_data.each_path_moved_by(id, |_, move_path| {
618 match self.analyze_move_out_from(id, move_path) {
620 MoveWhileBorrowed(loan_path, loan_span) => {
623 format!("cannot move out of `{}` \
624 because it is borrowed",
625 self.bccx.loan_path_to_str(move_path)));
628 format!("borrow of `{}` occurs here",
629 self.bccx.loan_path_to_str(loan_path)));
636 pub fn analyze_move_out_from(&self,
637 expr_id: ast::NodeId,
638 mut move_path: @LoanPath)
640 debug!("analyze_move_out_from(expr_id={:?}, move_path={})",
641 ast_map::node_id_to_str(self.tcx().items,
643 token::get_ident_interner()),
644 move_path.repr(self.tcx()));
646 // We must check every element of a move path. See
647 // `borrowck-move-subcomponent.rs` for a test case.
649 // check for a conflicting loan:
650 let mut ret = MoveOk;
651 self.each_in_scope_restriction(expr_id, move_path, |loan, _| {
652 // Any restriction prevents moves.
653 ret = MoveWhileBorrowed(loan.loan_path, loan.span);
662 LpVar(_) => return MoveOk,
663 LpExtend(subpath, _, _) => move_path = subpath,
668 pub fn check_call(&self,
670 _callee: Option<@ast::Expr>,
671 _callee_id: ast::NodeId,
673 _args: &[@ast::Expr]) {
674 // NB: This call to check for conflicting loans is not truly
675 // necessary, because the callee_id never issues new loans.
676 // However, I added it for consistency and lest the system
677 // should change in the future.
679 // FIXME(#6268) nested method calls
680 // self.check_for_conflicting_loans(callee_id);
684 fn check_loans_in_fn<'a>(this: &mut CheckLoanCtxt<'a>,
691 visit::FkItemFn(..) | visit::FkMethod(..) => {
692 // Don't process nested items.
696 visit::FkFnBlock(..) => {
697 check_captured_variables(this, id, sp);
701 visit::walk_fn(this, fk, decl, body, sp, id, ());
703 fn check_captured_variables(this: &CheckLoanCtxt,
704 closure_id: ast::NodeId,
706 let capture_map = this.bccx.capture_map.borrow();
707 let cap_vars = capture_map.get().get(&closure_id);
708 for cap_var in cap_vars.borrow().iter() {
709 let var_id = ast_util::def_id_of_def(cap_var.def).node;
710 let var_path = @LpVar(var_id);
711 this.check_if_path_is_moved(closure_id, span,
712 MovedInCapture, var_path);
714 moves::CapRef | moves::CapCopy => {}
716 check_by_move_capture(this, closure_id, cap_var, var_path);
722 fn check_by_move_capture(this: &CheckLoanCtxt,
723 closure_id: ast::NodeId,
724 cap_var: &moves::CaptureVar,
725 move_path: @LoanPath) {
726 let move_err = this.analyze_move_out_from(closure_id, move_path);
729 MoveWhileBorrowed(loan_path, loan_span) => {
732 format!("cannot move `{}` into closure \
733 because it is borrowed",
734 this.bccx.loan_path_to_str(move_path)));
737 format!("borrow of `{}` occurs here",
738 this.bccx.loan_path_to_str(loan_path)));
745 fn check_loans_in_local<'a>(this: &mut CheckLoanCtxt<'a>,
746 local: &ast::Local) {
747 visit::walk_local(this, local, ());
750 fn check_loans_in_expr<'a>(this: &mut CheckLoanCtxt<'a>,
752 visit::walk_expr(this, expr, ());
754 debug!("check_loans_in_expr(expr={})",
755 expr.repr(this.tcx()));
757 this.check_for_conflicting_loans(expr.id);
758 this.check_move_out_from_expr(expr);
760 let method_map = this.bccx.method_map.borrow();
762 ast::ExprPath(..) => {
763 if !this.move_data.is_assignee(expr.id) {
764 let cmt = this.bccx.cat_expr_unadjusted(expr);
765 debug!("path cmt={}", cmt.repr(this.tcx()));
766 let r = opt_loan_path(cmt);
767 for &lp in r.iter() {
768 this.check_if_path_is_moved(expr.id, expr.span, MovedInUse, lp);
772 ast::ExprAssign(dest, _) |
773 ast::ExprAssignOp(_, _, dest, _) => {
774 this.check_assignment(dest);
776 ast::ExprCall(f, ref args, _) => {
777 this.check_call(expr, Some(f), f.id, f.span, *args);
779 ast::ExprMethodCall(callee_id, _, _, ref args, _) => {
780 this.check_call(expr, None, callee_id, expr.span, *args);
782 ast::ExprIndex(callee_id, _, rval) |
783 ast::ExprBinary(callee_id, _, _, rval)
784 if method_map.get().contains_key(&expr.id) => {
785 this.check_call(expr, None, callee_id, expr.span, [rval]);
787 ast::ExprUnary(callee_id, _, _) | ast::ExprIndex(callee_id, _, _)
788 if method_map.get().contains_key(&expr.id) => {
789 this.check_call(expr, None, callee_id, expr.span, []);
791 ast::ExprInlineAsm(ref ia) => {
792 for &(_, out) in ia.outputs.iter() {
793 this.check_assignment(out);
800 fn check_loans_in_pat<'a>(this: &mut CheckLoanCtxt<'a>,
803 this.check_for_conflicting_loans(pat.id);
804 this.check_move_out_from_id(pat.id, pat.span);
805 visit::walk_pat(this, pat, ());
808 fn check_loans_in_block<'a>(this: &mut CheckLoanCtxt<'a>,
811 visit::walk_block(this, blk, ());
812 this.check_for_conflicting_loans(blk.id);