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::*;
25 use middle::typeck::MethodCall;
29 use syntax::codemap::Span;
30 use syntax::visit::Visitor;
32 use util::ppaux::Repr;
34 struct CheckLoanCtxt<'a> {
35 bccx: &'a BorrowckCtxt<'a>,
36 dfcx_loans: &'a LoanDataFlow<'a>,
37 move_data: move_data::FlowedMoveData<'a>,
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 // Don't process nested items or closures here,
58 // the outer loop will take care of it.
62 // FIXME(#10894) should continue recursing
63 fn visit_ty(&mut self, _t: &ast::Ty, _: ()) {}
66 pub fn check_loans(bccx: &BorrowckCtxt,
67 dfcx_loans: &LoanDataFlow,
68 move_data: move_data::FlowedMoveData,
71 debug!("check_loans(body id={:?})", body.id);
73 let mut clcx = CheckLoanCtxt {
75 dfcx_loans: dfcx_loans,
80 clcx.visit_block(body, ());
86 MoveWhileBorrowed(/*loan*/@LoanPath, /*loan*/Span)
89 impl<'a> CheckLoanCtxt<'a> {
90 pub fn tcx(&self) -> &'a ty::ctxt { self.bccx.tcx }
92 pub fn each_issued_loan(&self, scope_id: ast::NodeId, op: |&Loan| -> bool)
94 //! Iterates over each loan that has been issued
95 //! on entrance to `scope_id`, regardless of whether it is
96 //! actually *in scope* at that point. Sometimes loans
97 //! are issued for future scopes and thus they may have been
98 //! *issued* but not yet be in effect.
100 self.dfcx_loans.each_bit_on_entry_frozen(scope_id, |loan_index| {
101 let loan = &self.all_loans[loan_index];
106 pub fn each_in_scope_loan(&self,
107 scope_id: ast::NodeId,
110 //! Like `each_issued_loan()`, but only considers loans that are
111 //! currently in scope.
113 let tcx = self.tcx();
114 self.each_issued_loan(scope_id, |loan| {
115 if tcx.region_maps.is_subscope_of(scope_id, loan.kill_scope) {
123 pub fn each_in_scope_restriction(&self,
124 scope_id: ast::NodeId,
125 loan_path: @LoanPath,
126 op: |&Loan, &Restriction| -> bool)
128 //! Iterates through all the in-scope restrictions for the
129 //! given `loan_path`
131 self.each_in_scope_loan(scope_id, |loan| {
132 debug!("each_in_scope_restriction found loan: {:?}",
133 loan.repr(self.tcx()));
136 for restr in loan.restrictions.iter() {
137 if restr.loan_path == loan_path {
138 if !op(loan, restr) {
148 pub fn loans_generated_by(&self, scope_id: ast::NodeId) -> Vec<uint> {
149 //! Returns a vector of the loans that are generated as
150 //! we encounter `scope_id`.
152 let mut result = Vec::new();
153 self.dfcx_loans.each_gen_bit_frozen(scope_id, |loan_index| {
154 result.push(loan_index);
160 pub fn check_for_conflicting_loans(&self, scope_id: ast::NodeId) {
161 //! Checks to see whether any of the loans that are issued
162 //! by `scope_id` conflict with loans that have already been
163 //! issued when we enter `scope_id` (for example, we do not
164 //! permit two `&mut` borrows of the same variable).
166 debug!("check_for_conflicting_loans(scope_id={:?})", scope_id);
168 let new_loan_indices = self.loans_generated_by(scope_id);
169 debug!("new_loan_indices = {:?}", new_loan_indices);
171 self.each_issued_loan(scope_id, |issued_loan| {
172 for &new_loan_index in new_loan_indices.iter() {
173 let new_loan = &self.all_loans[new_loan_index];
174 self.report_error_if_loans_conflict(issued_loan, new_loan);
179 for (i, &x) in new_loan_indices.iter().enumerate() {
180 let old_loan = &self.all_loans[x];
181 for &y in new_loan_indices.slice_from(i+1).iter() {
182 let new_loan = &self.all_loans[y];
183 self.report_error_if_loans_conflict(old_loan, new_loan);
188 pub fn report_error_if_loans_conflict(&self,
191 //! Checks whether `old_loan` and `new_loan` can safely be issued
194 debug!("report_error_if_loans_conflict(old_loan={}, new_loan={})",
195 old_loan.repr(self.tcx()),
196 new_loan.repr(self.tcx()));
198 // Should only be called for loans that are in scope at the same time.
199 assert!(self.tcx().region_maps.scopes_intersect(old_loan.kill_scope,
200 new_loan.kill_scope));
202 self.report_error_if_loan_conflicts_with_restriction(
203 old_loan, new_loan, old_loan, new_loan) &&
204 self.report_error_if_loan_conflicts_with_restriction(
205 new_loan, old_loan, old_loan, new_loan);
208 pub fn report_error_if_loan_conflicts_with_restriction(&self,
214 //! Checks whether the restrictions introduced by `loan1` would
215 //! prohibit `loan2`. Returns false if an error is reported.
217 debug!("report_error_if_loan_conflicts_with_restriction(\
218 loan1={}, loan2={})",
219 loan1.repr(self.tcx()),
220 loan2.repr(self.tcx()));
222 // Restrictions that would cause the new loan to be illegal:
223 let illegal_if = match loan2.kind {
224 // Look for restrictions against mutation. These are
225 // generated by all other borrows.
226 ty::MutBorrow => RESTR_MUTATE,
228 // Look for restrictions against freezing (immutable borrows).
229 // These are generated by `&mut` borrows.
230 ty::ImmBorrow => RESTR_FREEZE,
232 // No matter how the data is borrowed (as `&`, as `&mut`,
233 // or as `&unique imm`) it will always generate a
234 // restriction against mutating the data. So look for those.
235 ty::UniqueImmBorrow => RESTR_MUTATE,
237 debug!("illegal_if={:?}", illegal_if);
239 for restr in loan1.restrictions.iter() {
240 if !restr.set.intersects(illegal_if) { continue; }
241 if restr.loan_path != loan2.loan_path { continue; }
243 let old_pronoun = if new_loan.loan_path == old_loan.loan_path {
247 self.bccx.loan_path_to_str(old_loan.loan_path))
250 match (new_loan.kind, old_loan.kind) {
251 (ty::MutBorrow, ty::MutBorrow) => {
254 format!("cannot borrow `{}` as mutable \
255 more than once at a time",
256 self.bccx.loan_path_to_str(new_loan.loan_path)));
259 (ty::UniqueImmBorrow, _) => {
262 format!("closure requires unique access to `{}` \
263 but {} is already borrowed",
264 self.bccx.loan_path_to_str(new_loan.loan_path),
268 (_, ty::UniqueImmBorrow) => {
271 format!("cannot borrow `{}` as {} because \
272 previous closure requires unique access",
273 self.bccx.loan_path_to_str(new_loan.loan_path),
274 new_loan.kind.to_user_str()));
280 format!("cannot borrow `{}` as {} because \
281 {} is also borrowed as {}",
282 self.bccx.loan_path_to_str(new_loan.loan_path),
283 new_loan.kind.to_user_str(),
285 old_loan.kind.to_user_str()));
289 match new_loan.cause {
290 ClosureCapture(span) => {
293 format!("borrow occurs due to use of `{}` in closure",
294 self.bccx.loan_path_to_str(new_loan.loan_path)));
299 let rule_summary = match old_loan.kind {
301 format!("the mutable borrow prevents subsequent \
302 moves, borrows, or modification of `{0}` \
303 until the borrow ends",
304 self.bccx.loan_path_to_str(old_loan.loan_path))
308 format!("the immutable borrow prevents subsequent \
309 moves or mutable borrows of `{0}` \
310 until the borrow ends",
311 self.bccx.loan_path_to_str(old_loan.loan_path))
314 ty::UniqueImmBorrow => {
315 format!("the unique capture prevents subsequent \
316 moves or borrows of `{0}` \
317 until the borrow ends",
318 self.bccx.loan_path_to_str(old_loan.loan_path))
322 let borrow_summary = match old_loan.cause {
323 ClosureCapture(_) => {
324 format!("previous borrow of `{}` occurs here due to \
326 self.bccx.loan_path_to_str(old_loan.loan_path))
329 AddrOf | AutoRef | RefBinding => {
330 format!("previous borrow of `{}` occurs here",
331 self.bccx.loan_path_to_str(old_loan.loan_path))
337 format!("{}; {}", borrow_summary, rule_summary));
339 let old_loan_span = self.tcx().map.span(old_loan.kill_scope);
340 self.bccx.span_end_note(old_loan_span,
341 "previous borrow ends here");
349 pub fn is_local_variable(&self, cmt: mc::cmt) -> bool {
351 mc::cat_local(_) => true,
356 pub fn check_if_path_is_moved(&self,
359 use_kind: MovedValueUseKind,
362 * Reports an error if `expr` (which should be a path)
363 * is using a moved/uninitialized value
366 debug!("check_if_path_is_moved(id={:?}, use_kind={:?}, lp={})",
367 id, use_kind, lp.repr(self.bccx.tcx));
368 self.move_data.each_move_of(id, lp, |move, moved_lp| {
369 self.bccx.report_use_of_moved_value(
379 pub fn check_assignment(&self, expr: &ast::Expr) {
380 // We don't use cat_expr() here because we don't want to treat
381 // auto-ref'd parameters in overloaded operators as rvalues.
383 let adjustments = self.bccx.tcx.adjustments.borrow();
384 adjustments.get().find_copy(&expr.id)
386 let cmt = match adj {
387 None => self.bccx.cat_expr_unadjusted(expr),
388 Some(adj) => self.bccx.cat_expr_autoderefd(expr, adj)
391 debug!("check_assignment(cmt={})", cmt.repr(self.tcx()));
393 // Mutable values can be assigned, as long as they obey loans
394 // and aliasing restrictions:
395 if cmt.mutbl.is_mutable() {
396 if check_for_aliasable_mutable_writes(self, expr, cmt) {
397 if check_for_assignment_to_restricted_or_frozen_location(
400 // Safe, but record for lint pass later:
401 mark_variable_as_used_mut(self, cmt);
407 // For immutable local variables, assignments are legal
408 // if they cannot already have been assigned
409 if self.is_local_variable(cmt) {
410 assert!(cmt.mutbl.is_immutable()); // no "const" locals
411 let lp = opt_loan_path(cmt).unwrap();
412 self.move_data.each_assignment_of(expr.id, lp, |assign| {
413 self.bccx.report_reassigned_immutable_variable(
422 // Otherwise, just a plain error.
423 match opt_loan_path(cmt) {
427 format!("cannot assign to {} {} `{}`",
428 cmt.mutbl.to_user_str(),
429 self.bccx.cmt_to_str(cmt),
430 self.bccx.loan_path_to_str(lp)));
435 format!("cannot assign to {} {}",
436 cmt.mutbl.to_user_str(),
437 self.bccx.cmt_to_str(cmt)));
442 fn mark_variable_as_used_mut(this: &CheckLoanCtxt,
444 //! If the mutability of the `cmt` being written is inherited
445 //! from a local variable, liveness will
446 //! not have been able to detect that this variable's mutability
447 //! is important, so we must add the variable to the
448 //! `used_mut_nodes` table here.
452 debug!("mark_writes_through_upvars_as_used_mut(cmt={})",
453 cmt.repr(this.tcx()));
455 mc::cat_local(id) | mc::cat_arg(id) => {
456 let mut used_mut_nodes = this.tcx()
459 used_mut_nodes.get().insert(id);
463 mc::cat_upvar(..) => {
467 mc::cat_deref(_, _, mc::GcPtr) => {
468 assert_eq!(cmt.mutbl, mc::McImmutable);
473 mc::cat_static_item |
474 mc::cat_copied_upvar(..) |
475 mc::cat_deref(_, _, mc::UnsafePtr(..)) |
476 mc::cat_deref(_, _, mc::BorrowedPtr(..)) => {
477 assert_eq!(cmt.mutbl, mc::McDeclared);
481 mc::cat_discr(b, _) |
482 mc::cat_deref(b, _, mc::OwnedPtr) => {
483 assert_eq!(cmt.mutbl, mc::McInherited);
487 mc::cat_downcast(b) |
488 mc::cat_interior(b, _) => {
489 assert_eq!(cmt.mutbl, mc::McInherited);
496 fn check_for_aliasable_mutable_writes(this: &CheckLoanCtxt,
498 cmt: mc::cmt) -> bool {
499 //! Safety checks related to writes to aliasable, mutable locations
501 let guarantor = cmt.guarantor();
502 debug!("check_for_aliasable_mutable_writes(cmt={}, guarantor={})",
503 cmt.repr(this.tcx()), guarantor.repr(this.tcx()));
504 match guarantor.cat {
505 mc::cat_deref(b, _, mc::BorrowedPtr(ty::MutBorrow, _)) => {
506 // Statically prohibit writes to `&mut` when aliasable
508 check_for_aliasability_violation(this, expr, b);
514 return true; // no errors reported
517 fn check_for_aliasability_violation(this: &CheckLoanCtxt,
521 match cmt.freely_aliasable(this.tcx()) {
525 Some(mc::AliasableStaticMut(..)) => {
529 this.bccx.report_aliasability_violation(
538 fn check_for_assignment_to_restricted_or_frozen_location(
539 this: &CheckLoanCtxt,
541 cmt: mc::cmt) -> bool
543 //! Check for assignments that violate the terms of an
544 //! outstanding loan.
546 let loan_path = match opt_loan_path(cmt) {
548 None => { return true; /* no loan path, can't be any loans */ }
551 // Start by searching for an assignment to a *restricted*
552 // location. Here is one example of the kind of error caught
555 // let mut v = ~[1, 2, 3];
559 // In this case, creating `p` triggers a RESTR_MUTATE
560 // restriction on the path `v`.
562 // Here is a second, more subtle example:
564 // let mut v = ~[1, 2, 3];
565 // let p = &const v[0];
568 // v = ~[4, 5, 3]; // Error
570 // In this case, `p` is pointing to `v[0]`, and it is a
571 // `const` pointer in any case. So the first two
572 // assignments are legal (and would be permitted by this
573 // check). However, the final assignment (which is
574 // logically equivalent) is forbidden, because it would
575 // cause the existing `v` array to be freed, thus
576 // invalidating `p`. In the code, this error results
577 // because `gather_loans::restrictions` adds a
578 // `RESTR_MUTATE` restriction whenever the contents of an
579 // owned pointer are borrowed, and hence while `v[*]` is not
580 // restricted from being written, `v` is.
581 let cont = this.each_in_scope_restriction(expr.id,
584 if restr.set.intersects(RESTR_MUTATE) {
585 this.report_illegal_mutation(expr, loan_path, loan);
592 if !cont { return false }
594 // The previous code handled assignments to paths that
595 // have been restricted. This covers paths that have been
596 // directly lent out and their base paths, but does not
597 // cover random extensions of those paths. For example,
598 // the following program is not declared illegal by the
601 // let mut v = ~[1, 2, 3];
603 // v[0] = 4; // declared error by loop below, not code above
605 // The reason that this passes the previous check whereas
606 // an assignment like `v = ~[4]` fails is because the assignment
607 // here is to `v[*]`, and the existing restrictions were issued
608 // for `v`, not `v[*]`.
610 // So in this loop, we walk back up the loan path so long
611 // as the mutability of the path is dependent on a super
612 // path, and check that the super path was not lent out as
613 // mutable or immutable (a const loan is ok).
615 // Mutability of a path can be dependent on the super path
616 // in two ways. First, it might be inherited mutability.
617 // Second, the pointee of an `&mut` pointer can only be
618 // mutated if it is found in an unaliased location, so we
619 // have to check that the owner location is not borrowed.
621 // Note that we are *not* checking for any and all
622 // restrictions. We are only interested in the pointers
623 // that the user created, whereas we add restrictions for
624 // all kinds of paths that are not directly aliased. If we checked
625 // for all restrictions, and not just loans, then the following
626 // valid program would be considered illegal:
628 // let mut v = ~[1, 2, 3];
629 // let p = &const v[0];
632 // Here the restriction that `v` not be mutated would be misapplied
633 // to block the subpath `v[1]`.
634 let full_loan_path = loan_path;
635 let mut loan_path = loan_path;
638 // Peel back one layer if, for `loan_path` to be
639 // mutable, `lp_base` must be mutable. This occurs
640 // with inherited mutability and with `&mut`
642 LpExtend(lp_base, mc::McInherited, _) |
643 LpExtend(lp_base, _, LpDeref(mc::BorrowedPtr(ty::MutBorrow, _))) => {
647 // Otherwise stop iterating
648 LpExtend(_, mc::McDeclared, _) |
649 LpExtend(_, mc::McImmutable, _) |
655 // Check for a non-const loan of `loan_path`
656 let cont = this.each_in_scope_loan(expr.id, |loan| {
657 if loan.loan_path == loan_path {
658 this.report_illegal_mutation(expr, full_loan_path, loan);
665 if !cont { return false }
670 pub fn report_illegal_mutation(&self,
672 loan_path: &LoanPath,
676 format!("cannot assign to `{}` because it is borrowed",
677 self.bccx.loan_path_to_str(loan_path)));
680 format!("borrow of `{}` occurs here",
681 self.bccx.loan_path_to_str(loan_path)));
684 fn check_move_out_from_expr(&self, expr: &ast::Expr) {
686 ast::ExprFnBlock(..) | ast::ExprProc(..) => {
687 // Moves due to captures are checked in
688 // check_captured_variables() because it allows
689 // us to give a more precise error message with
690 // a more precise span.
693 self.check_move_out_from_id(expr.id, expr.span)
698 fn check_move_out_from_id(&self, id: ast::NodeId, span: Span) {
699 self.move_data.each_path_moved_by(id, |_, move_path| {
700 match self.analyze_move_out_from(id, move_path) {
702 MoveWhileBorrowed(loan_path, loan_span) => {
705 format!("cannot move out of `{}` \
706 because it is borrowed",
707 self.bccx.loan_path_to_str(move_path)));
710 format!("borrow of `{}` occurs here",
711 self.bccx.loan_path_to_str(loan_path)));
718 fn check_captured_variables(&self,
719 closure_id: ast::NodeId,
721 for cap_var in self.bccx.capture_map.get(&closure_id).deref().iter() {
722 let var_id = ast_util::def_id_of_def(cap_var.def).node;
723 let var_path = @LpVar(var_id);
724 self.check_if_path_is_moved(closure_id, span,
725 MovedInCapture, var_path);
727 moves::CapRef | moves::CapCopy => {}
729 check_by_move_capture(self, closure_id, cap_var, var_path);
735 fn check_by_move_capture(this: &CheckLoanCtxt,
736 closure_id: ast::NodeId,
737 cap_var: &moves::CaptureVar,
738 move_path: @LoanPath) {
739 let move_err = this.analyze_move_out_from(closure_id, move_path);
742 MoveWhileBorrowed(loan_path, loan_span) => {
745 format!("cannot move `{}` into closure \
746 because it is borrowed",
747 this.bccx.loan_path_to_str(move_path)));
750 format!("borrow of `{}` occurs here",
751 this.bccx.loan_path_to_str(loan_path)));
757 pub fn analyze_move_out_from(&self,
758 expr_id: ast::NodeId,
759 mut move_path: @LoanPath)
761 debug!("analyze_move_out_from(expr_id={:?}, move_path={})",
762 self.tcx().map.node_to_str(expr_id),
763 move_path.repr(self.tcx()));
765 // We must check every element of a move path. See
766 // `borrowck-move-subcomponent.rs` for a test case.
768 // check for a conflicting loan:
769 let mut ret = MoveOk;
770 self.each_in_scope_restriction(expr_id, move_path, |loan, _| {
771 // Any restriction prevents moves.
772 ret = MoveWhileBorrowed(loan.loan_path, loan.span);
781 LpVar(_) => return MoveOk,
782 LpExtend(subpath, _, _) => move_path = subpath,
787 pub fn check_call(&self,
789 _callee: Option<@ast::Expr>,
791 _args: &[@ast::Expr]) {
792 // NB: This call to check for conflicting loans is not truly
793 // necessary, because the callee_id never issues new loans.
794 // However, I added it for consistency and lest the system
795 // should change in the future.
797 // FIXME(#6268) nested method calls
798 // self.check_for_conflicting_loans(callee_id);
802 fn check_loans_in_local<'a>(this: &mut CheckLoanCtxt<'a>,
803 local: &ast::Local) {
804 visit::walk_local(this, local, ());
807 fn check_loans_in_expr<'a>(this: &mut CheckLoanCtxt<'a>,
809 visit::walk_expr(this, expr, ());
811 debug!("check_loans_in_expr(expr={})",
812 expr.repr(this.tcx()));
814 this.check_for_conflicting_loans(expr.id);
815 this.check_move_out_from_expr(expr);
817 let method_map = this.bccx.method_map.borrow();
819 ast::ExprPath(..) => {
820 if !this.move_data.is_assignee(expr.id) {
821 let cmt = this.bccx.cat_expr_unadjusted(expr);
822 debug!("path cmt={}", cmt.repr(this.tcx()));
823 let r = opt_loan_path(cmt);
824 for &lp in r.iter() {
825 this.check_if_path_is_moved(expr.id, expr.span, MovedInUse, lp);
829 ast::ExprFnBlock(..) | ast::ExprProc(..) => {
830 this.check_captured_variables(expr.id, expr.span)
832 ast::ExprAssign(dest, _) |
833 ast::ExprAssignOp(_, dest, _) => {
834 this.check_assignment(dest);
836 ast::ExprCall(f, ref args) => {
837 this.check_call(expr, Some(f), f.span, args.as_slice());
839 ast::ExprMethodCall(_, _, ref args) => {
840 this.check_call(expr, None, expr.span, args.as_slice());
842 ast::ExprIndex(_, rval) | ast::ExprBinary(_, _, rval)
843 if method_map.get().contains_key(&MethodCall::expr(expr.id)) => {
844 this.check_call(expr, None, expr.span, [rval]);
846 ast::ExprUnary(_, _) | ast::ExprIndex(_, _)
847 if method_map.get().contains_key(&MethodCall::expr(expr.id)) => {
848 this.check_call(expr, None, expr.span, []);
850 ast::ExprInlineAsm(ref ia) => {
851 for &(_, out) in ia.outputs.iter() {
852 this.check_assignment(out);
859 fn check_loans_in_pat<'a>(this: &mut CheckLoanCtxt<'a>,
862 this.check_for_conflicting_loans(pat.id);
863 this.check_move_out_from_id(pat.id, pat.span);
864 visit::walk_pat(this, pat, ());
867 fn check_loans_in_block<'a>(this: &mut CheckLoanCtxt<'a>,
870 visit::walk_block(this, blk, ());
871 this.check_for_conflicting_loans(blk.id);