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 middle::borrowck::*;
22 use middle::expr_use_visitor as euv;
23 use middle::mem_categorization as mc;
26 use syntax::codemap::Span;
27 use util::ppaux::Repr;
31 // FIXME (#16118): These functions are intended to allow the borrow checker to
32 // be less precise in its handling of Box while still allowing moves out of a
33 // Box. They should be removed when OwnedPtr is removed from LoanPath.
35 fn owned_ptr_base_path<'a>(loan_path: &'a LoanPath) -> &'a LoanPath {
36 //! Returns the base of the leftmost dereference of an OwnedPtr in
37 //! `loan_path`. If there is no dereference of an OwnedPtr in `loan_path`,
38 //! then it just returns `loan_path` itself.
40 return match owned_ptr_base_path_helper(loan_path) {
41 Some(new_loan_path) => new_loan_path,
42 None => loan_path.clone()
45 fn owned_ptr_base_path_helper<'a>(loan_path: &'a LoanPath) -> Option<&'a LoanPath> {
47 LpVar(_) | LpUpvar(_) => None,
48 LpExtend(ref lp_base, _, LpDeref(mc::OwnedPtr)) => {
49 match owned_ptr_base_path_helper(&**lp_base) {
51 None => Some(&**lp_base)
54 LpExtend(ref lp_base, _, _) => owned_ptr_base_path_helper(&**lp_base)
59 fn owned_ptr_base_path_rc(loan_path: &Rc<LoanPath>) -> Rc<LoanPath> {
60 //! The equivalent of `owned_ptr_base_path` for an &Rc<LoanPath> rather than
63 return match owned_ptr_base_path_helper(loan_path) {
64 Some(new_loan_path) => new_loan_path,
65 None => loan_path.clone()
68 fn owned_ptr_base_path_helper(loan_path: &Rc<LoanPath>) -> Option<Rc<LoanPath>> {
70 LpVar(_) | LpUpvar(_) => None,
71 LpExtend(ref lp_base, _, LpDeref(mc::OwnedPtr)) => {
72 match owned_ptr_base_path_helper(lp_base) {
74 None => Some(lp_base.clone())
77 LpExtend(ref lp_base, _, _) => owned_ptr_base_path_helper(lp_base)
82 struct CheckLoanCtxt<'a, 'tcx: 'a> {
83 bccx: &'a BorrowckCtxt<'a, 'tcx>,
84 dfcx_loans: &'a LoanDataFlow<'a, 'tcx>,
85 move_data: move_data::FlowedMoveData<'a, 'tcx>,
86 all_loans: &'a [Loan],
89 impl<'a, 'tcx> euv::Delegate for CheckLoanCtxt<'a, 'tcx> {
91 consume_id: ast::NodeId,
94 mode: euv::ConsumeMode) {
95 debug!("consume(consume_id={}, cmt={}, mode={})",
96 consume_id, cmt.repr(self.tcx()), mode);
98 self.consume_common(consume_id, consume_span, cmt, mode);
101 fn consume_pat(&mut self,
102 consume_pat: &ast::Pat,
104 mode: euv::ConsumeMode) {
105 debug!("consume_pat(consume_pat={}, cmt={}, mode={})",
106 consume_pat.repr(self.tcx()),
107 cmt.repr(self.tcx()),
110 self.consume_common(consume_pat.id, consume_pat.span, cmt, mode);
114 borrow_id: ast::NodeId,
117 loan_region: ty::Region,
119 loan_cause: euv::LoanCause)
121 debug!("borrow(borrow_id={}, cmt={}, loan_region={}, \
122 bk={}, loan_cause={:?})",
123 borrow_id, cmt.repr(self.tcx()), loan_region,
126 match opt_loan_path(&cmt) {
128 let moved_value_use_kind = match loan_cause {
129 euv::ClosureCapture(_) => MovedInCapture,
132 self.check_if_path_is_moved(borrow_id, borrow_span, moved_value_use_kind, &lp);
137 self.check_for_conflicting_loans(borrow_id);
141 assignment_id: ast::NodeId,
142 assignment_span: Span,
143 assignee_cmt: mc::cmt,
144 mode: euv::MutateMode)
146 debug!("mutate(assignment_id={}, assignee_cmt={})",
147 assignment_id, assignee_cmt.repr(self.tcx()));
149 match opt_loan_path(&assignee_cmt) {
152 euv::Init | euv::JustWrite => {
153 // In a case like `path = 1`, then path does not
154 // have to be *FULLY* initialized, but we still
155 // must be careful lest it contains derefs of
157 self.check_if_assigned_path_is_moved(assignee_cmt.id,
162 euv::WriteAndRead => {
163 // In a case like `path += 1`, then path must be
164 // fully initialized, since we will read it before
166 self.check_if_path_is_moved(assignee_cmt.id,
176 self.check_assignment(assignment_id, assignment_span, assignee_cmt, mode);
179 fn decl_without_init(&mut self, _id: ast::NodeId, _span: Span) { }
182 pub fn check_loans<'a, 'b, 'c, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
183 dfcx_loans: &LoanDataFlow<'b, 'tcx>,
184 move_data: move_data::FlowedMoveData<'c, 'tcx>,
188 debug!("check_loans(body id={:?})", body.id);
190 let mut clcx = CheckLoanCtxt {
192 dfcx_loans: dfcx_loans,
193 move_data: move_data,
194 all_loans: all_loans,
198 let mut euv = euv::ExprUseVisitor::new(&mut clcx, bccx.tcx);
199 euv.walk_fn(decl, body);
203 #[deriving(PartialEq)]
206 UseWhileBorrowed(/*loan*/Rc<LoanPath>, /*loan*/Span)
209 fn compatible_borrow_kinds(borrow_kind1: ty::BorrowKind,
210 borrow_kind2: ty::BorrowKind)
212 borrow_kind1 == ty::ImmBorrow && borrow_kind2 == ty::ImmBorrow
215 impl<'a, 'tcx> CheckLoanCtxt<'a, 'tcx> {
216 pub fn tcx(&self) -> &'a ty::ctxt<'tcx> { self.bccx.tcx }
218 pub fn each_issued_loan(&self, scope_id: ast::NodeId, op: |&Loan| -> bool)
220 //! Iterates over each loan that has been issued
221 //! on entrance to `scope_id`, regardless of whether it is
222 //! actually *in scope* at that point. Sometimes loans
223 //! are issued for future scopes and thus they may have been
224 //! *issued* but not yet be in effect.
226 self.dfcx_loans.each_bit_on_entry(scope_id, |loan_index| {
227 let loan = &self.all_loans[loan_index];
232 pub fn each_in_scope_loan(&self,
233 scope_id: ast::NodeId,
236 //! Like `each_issued_loan()`, but only considers loans that are
237 //! currently in scope.
239 let tcx = self.tcx();
240 self.each_issued_loan(scope_id, |loan| {
241 if tcx.region_maps.is_subscope_of(scope_id, loan.kill_scope) {
249 fn each_in_scope_loan_affecting_path(&self,
250 scope_id: ast::NodeId,
251 loan_path: &LoanPath,
254 //! Iterates through all of the in-scope loans affecting `loan_path`,
255 //! calling `op`, and ceasing iteration if `false` is returned.
257 // First, we check for a loan restricting the path P being used. This
258 // accounts for borrows of P but also borrows of subpaths, like P.a.b.
259 // Consider the following example:
261 // let x = &mut a.b.c; // Restricts a, a.b, and a.b.c
262 // let y = a; // Conflicts with restriction
264 let loan_path = owned_ptr_base_path(loan_path);
265 let cont = self.each_in_scope_loan(scope_id, |loan| {
267 for restr_path in loan.restricted_paths.iter() {
268 if **restr_path == *loan_path {
282 // Next, we must check for *loans* (not restrictions) on the path P or
283 // any base path. This rejects examples like the following:
288 // Limiting this search to *loans* and not *restrictions* means that
289 // examples like the following continue to work:
294 let mut loan_path = loan_path;
297 LpVar(_) | LpUpvar(_) => {
300 LpExtend(ref lp_base, _, _) => {
301 loan_path = &**lp_base;
305 let cont = self.each_in_scope_loan(scope_id, |loan| {
306 if *loan.loan_path == *loan_path {
321 pub fn loans_generated_by(&self, scope_id: ast::NodeId) -> Vec<uint> {
322 //! Returns a vector of the loans that are generated as
323 //! we encounter `scope_id`.
325 let mut result = Vec::new();
326 self.dfcx_loans.each_gen_bit(scope_id, |loan_index| {
327 result.push(loan_index);
333 pub fn check_for_conflicting_loans(&self, scope_id: ast::NodeId) {
334 //! Checks to see whether any of the loans that are issued
335 //! by `scope_id` conflict with loans that have already been
336 //! issued when we enter `scope_id` (for example, we do not
337 //! permit two `&mut` borrows of the same variable).
339 debug!("check_for_conflicting_loans(scope_id={:?})", scope_id);
341 let new_loan_indices = self.loans_generated_by(scope_id);
342 debug!("new_loan_indices = {:?}", new_loan_indices);
344 self.each_issued_loan(scope_id, |issued_loan| {
345 for &new_loan_index in new_loan_indices.iter() {
346 let new_loan = &self.all_loans[new_loan_index];
347 self.report_error_if_loans_conflict(issued_loan, new_loan);
352 for (i, &x) in new_loan_indices.iter().enumerate() {
353 let old_loan = &self.all_loans[x];
354 for &y in new_loan_indices.slice_from(i+1).iter() {
355 let new_loan = &self.all_loans[y];
356 self.report_error_if_loans_conflict(old_loan, new_loan);
361 pub fn report_error_if_loans_conflict(&self,
364 //! Checks whether `old_loan` and `new_loan` can safely be issued
367 debug!("report_error_if_loans_conflict(old_loan={}, new_loan={})",
368 old_loan.repr(self.tcx()),
369 new_loan.repr(self.tcx()));
371 // Should only be called for loans that are in scope at the same time.
372 assert!(self.tcx().region_maps.scopes_intersect(old_loan.kill_scope,
373 new_loan.kill_scope));
375 self.report_error_if_loan_conflicts_with_restriction(
376 old_loan, new_loan, old_loan, new_loan) &&
377 self.report_error_if_loan_conflicts_with_restriction(
378 new_loan, old_loan, old_loan, new_loan);
381 pub fn report_error_if_loan_conflicts_with_restriction(&self,
387 //! Checks whether the restrictions introduced by `loan1` would
388 //! prohibit `loan2`. Returns false if an error is reported.
390 debug!("report_error_if_loan_conflicts_with_restriction(\
391 loan1={}, loan2={})",
392 loan1.repr(self.tcx()),
393 loan2.repr(self.tcx()));
395 if compatible_borrow_kinds(loan1.kind, loan2.kind) {
399 let loan2_base_path = owned_ptr_base_path_rc(&loan2.loan_path);
400 for restr_path in loan1.restricted_paths.iter() {
401 if *restr_path != loan2_base_path { continue; }
403 let old_pronoun = if new_loan.loan_path == old_loan.loan_path {
407 self.bccx.loan_path_to_string(&*old_loan.loan_path))
410 match (new_loan.kind, old_loan.kind) {
411 (ty::MutBorrow, ty::MutBorrow) => {
414 format!("cannot borrow `{}` as mutable \
415 more than once at a time",
416 self.bccx.loan_path_to_string(
417 &*new_loan.loan_path)).as_slice());
420 (ty::UniqueImmBorrow, _) => {
423 format!("closure requires unique access to `{}` \
424 but {} is already borrowed",
425 self.bccx.loan_path_to_string(&*new_loan.loan_path),
426 old_pronoun).as_slice());
429 (_, ty::UniqueImmBorrow) => {
432 format!("cannot borrow `{}` as {} because \
433 previous closure requires unique access",
434 self.bccx.loan_path_to_string(&*new_loan.loan_path),
435 new_loan.kind.to_user_str()).as_slice());
441 format!("cannot borrow `{}` as {} because \
442 {} is also borrowed as {}",
443 self.bccx.loan_path_to_string(&*new_loan.loan_path),
444 new_loan.kind.to_user_str(),
446 old_loan.kind.to_user_str()).as_slice());
450 match new_loan.cause {
451 euv::ClosureCapture(span) => {
454 format!("borrow occurs due to use of `{}` in closure",
455 self.bccx.loan_path_to_string(
456 &*new_loan.loan_path)).as_slice());
461 let rule_summary = match old_loan.kind {
463 format!("the mutable borrow prevents subsequent \
464 moves, borrows, or modification of `{0}` \
465 until the borrow ends",
466 self.bccx.loan_path_to_string(
467 &*old_loan.loan_path))
471 format!("the immutable borrow prevents subsequent \
472 moves or mutable borrows of `{0}` \
473 until the borrow ends",
474 self.bccx.loan_path_to_string(&*old_loan.loan_path))
477 ty::UniqueImmBorrow => {
478 format!("the unique capture prevents subsequent \
479 moves or borrows of `{0}` \
480 until the borrow ends",
481 self.bccx.loan_path_to_string(&*old_loan.loan_path))
485 let borrow_summary = match old_loan.cause {
486 euv::ClosureCapture(_) => {
487 format!("previous borrow of `{}` occurs here due to \
489 self.bccx.loan_path_to_string(&*old_loan.loan_path))
492 euv::OverloadedOperator(..) |
495 euv::ClosureInvocation(..) |
497 euv::RefBinding(..) => {
498 format!("previous borrow of `{}` occurs here",
499 self.bccx.loan_path_to_string(&*old_loan.loan_path))
505 format!("{}; {}", borrow_summary, rule_summary).as_slice());
507 let old_loan_span = self.tcx().map.span(old_loan.kill_scope);
508 self.bccx.span_end_note(old_loan_span,
509 "previous borrow ends here");
517 pub fn is_local_variable_or_arg(&self, cmt: mc::cmt) -> bool {
519 mc::cat_local(_) | mc::cat_arg(_) => true,
524 fn consume_common(&self,
528 mode: euv::ConsumeMode) {
529 match opt_loan_path(&cmt) {
531 let moved_value_use_kind = match mode {
533 self.check_for_copy_of_frozen_path(id, span, &*lp);
537 match self.move_data.kind_of_move_of_path(id, &lp) {
539 // Sometimes moves don't have a move kind;
540 // this either means that the original move
541 // was from something illegal to move,
542 // or was moved from referent of an unsafe
543 // pointer or something like that.
547 self.check_for_move_of_borrowed_path(id, span,
549 if move_kind == move_data::Captured {
559 self.check_if_path_is_moved(id, span, moved_value_use_kind, &lp);
565 fn check_for_copy_of_frozen_path(&self,
568 copy_path: &LoanPath) {
569 match self.analyze_restrictions_on_use(id, copy_path, ty::ImmBorrow) {
571 UseWhileBorrowed(loan_path, loan_span) => {
574 format!("cannot use `{}` because it was mutably borrowed",
575 self.bccx.loan_path_to_string(copy_path).as_slice())
579 format!("borrow of `{}` occurs here",
580 self.bccx.loan_path_to_string(&*loan_path).as_slice())
586 fn check_for_move_of_borrowed_path(&self,
589 move_path: &LoanPath,
590 move_kind: move_data::MoveKind) {
591 // We want to detect if there are any loans at all, so we search for
592 // any loans incompatible with MutBorrrow, since all other kinds of
593 // loans are incompatible with that.
594 match self.analyze_restrictions_on_use(id, move_path, ty::MutBorrow) {
596 UseWhileBorrowed(loan_path, loan_span) => {
597 let err_message = match move_kind {
598 move_data::Captured =>
599 format!("cannot move `{}` into closure because it is borrowed",
600 self.bccx.loan_path_to_string(move_path).as_slice()),
601 move_data::Declared |
602 move_data::MoveExpr |
603 move_data::MovePat =>
604 format!("cannot move out of `{}` because it is borrowed",
605 self.bccx.loan_path_to_string(move_path).as_slice())
608 self.bccx.span_err(span, err_message.as_slice());
611 format!("borrow of `{}` occurs here",
612 self.bccx.loan_path_to_string(&*loan_path).as_slice())
618 pub fn analyze_restrictions_on_use(&self,
619 expr_id: ast::NodeId,
621 borrow_kind: ty::BorrowKind)
623 debug!("analyze_restrictions_on_use(expr_id={:?}, use_path={})",
624 self.tcx().map.node_to_string(expr_id),
625 use_path.repr(self.tcx()));
629 self.each_in_scope_loan_affecting_path(expr_id, use_path, |loan| {
630 if !compatible_borrow_kinds(loan.kind, borrow_kind) {
631 ret = UseWhileBorrowed(loan.loan_path.clone(), loan.span);
641 fn check_if_path_is_moved(&self,
644 use_kind: MovedValueUseKind,
647 * Reports an error if `expr` (which should be a path)
648 * is using a moved/uninitialized value
651 debug!("check_if_path_is_moved(id={:?}, use_kind={:?}, lp={})",
652 id, use_kind, lp.repr(self.bccx.tcx));
653 let base_lp = owned_ptr_base_path_rc(lp);
654 self.move_data.each_move_of(id, &base_lp, |move, moved_lp| {
655 self.bccx.report_use_of_moved_value(
665 fn check_if_assigned_path_is_moved(&self,
668 use_kind: MovedValueUseKind,
672 * Reports an error if assigning to `lp` will use a
673 * moved/uninitialized value. Mainly this is concerned with
674 * detecting derefs of uninitialized pointers.
679 * a = 10; // ok, even though a is uninitialized
681 * struct Point { x: uint, y: uint }
683 * p.x = 22; // ok, even though `p` is uninitialized
686 * (*p).x = 22; // not ok, p is uninitialized, can't deref
690 LpVar(_) | LpUpvar(_) => {
691 // assigning to `x` does not require that `x` is initialized
693 LpExtend(ref lp_base, _, LpInterior(_)) => {
694 // assigning to `P.f` is ok if assigning to `P` is ok
695 self.check_if_assigned_path_is_moved(id, span,
698 LpExtend(ref lp_base, _, LpDeref(_)) => {
699 // assigning to `(*P)` requires that `P` be initialized
700 self.check_if_path_is_moved(id, span,
706 fn check_assignment(&self,
707 assignment_id: ast::NodeId,
708 assignment_span: Span,
709 assignee_cmt: mc::cmt,
710 mode: euv::MutateMode) {
711 debug!("check_assignment(assignee_cmt={})", assignee_cmt.repr(self.tcx()));
713 // Mutable values can be assigned, as long as they obey loans
714 // and aliasing restrictions:
715 if assignee_cmt.mutbl.is_mutable() {
716 if check_for_aliasable_mutable_writes(self, assignment_span, assignee_cmt.clone()) {
717 if mode != euv::Init {
718 check_for_assignment_to_borrowed_path(
719 self, assignment_id, assignment_span, assignee_cmt.clone());
720 mark_variable_as_used_mut(self, assignee_cmt);
726 // Initializations are OK.
727 if mode == euv::Init {
731 // For immutable local variables, assignments are legal
732 // if they cannot already have been assigned
733 if self.is_local_variable_or_arg(assignee_cmt.clone()) {
734 assert!(assignee_cmt.mutbl.is_immutable()); // no "const" locals
735 let lp = opt_loan_path(&assignee_cmt).unwrap();
736 self.move_data.each_assignment_of(assignment_id, &lp, |assign| {
737 self.bccx.report_reassigned_immutable_variable(
746 // Otherwise, just a plain error.
747 match opt_loan_path(&assignee_cmt) {
751 format!("cannot assign to {} {} `{}`",
752 assignee_cmt.mutbl.to_user_str(),
753 self.bccx.cmt_to_string(&*assignee_cmt),
754 self.bccx.loan_path_to_string(&*lp)).as_slice());
759 format!("cannot assign to {} {}",
760 assignee_cmt.mutbl.to_user_str(),
761 self.bccx.cmt_to_string(&*assignee_cmt)).as_slice());
766 fn mark_variable_as_used_mut(this: &CheckLoanCtxt,
768 //! If the mutability of the `cmt` being written is inherited
769 //! from a local variable, liveness will
770 //! not have been able to detect that this variable's mutability
771 //! is important, so we must add the variable to the
772 //! `used_mut_nodes` table here.
775 debug!("mark_variable_as_used_mut(cmt={})", cmt.repr(this.tcx()));
776 match cmt.cat.clone() {
777 mc::cat_copied_upvar(mc::CopiedUpvar { upvar_id: id, .. }) |
778 mc::cat_local(id) | mc::cat_arg(id) => {
779 this.tcx().used_mut_nodes.borrow_mut().insert(id);
783 mc::cat_upvar(..) => {
787 mc::cat_deref(_, _, mc::GcPtr) => {
788 assert_eq!(cmt.mutbl, mc::McImmutable);
793 mc::cat_static_item |
794 mc::cat_deref(_, _, mc::UnsafePtr(..)) |
795 mc::cat_deref(_, _, mc::BorrowedPtr(..)) |
796 mc::cat_deref(_, _, mc::Implicit(..)) => {
797 assert_eq!(cmt.mutbl, mc::McDeclared);
801 mc::cat_discr(b, _) |
802 mc::cat_deref(b, _, mc::OwnedPtr) => {
803 assert_eq!(cmt.mutbl, mc::McInherited);
807 mc::cat_downcast(b) |
808 mc::cat_interior(b, _) => {
809 assert_eq!(cmt.mutbl, mc::McInherited);
816 fn check_for_aliasable_mutable_writes(this: &CheckLoanCtxt,
818 cmt: mc::cmt) -> bool {
819 //! Safety checks related to writes to aliasable, mutable locations
821 let guarantor = cmt.guarantor();
822 debug!("check_for_aliasable_mutable_writes(cmt={}, guarantor={})",
823 cmt.repr(this.tcx()), guarantor.repr(this.tcx()));
824 match guarantor.cat {
825 mc::cat_deref(ref b, _, mc::BorrowedPtr(ty::MutBorrow, _)) => {
826 // Statically prohibit writes to `&mut` when aliasable
828 check_for_aliasability_violation(this, span, b.clone());
834 return true; // no errors reported
837 fn check_for_aliasability_violation(this: &CheckLoanCtxt,
841 match cmt.freely_aliasable(this.tcx()) {
845 Some(mc::AliasableStaticMut(..)) => {
849 this.bccx.report_aliasability_violation(
858 fn check_for_assignment_to_borrowed_path(
859 this: &CheckLoanCtxt,
860 assignment_id: ast::NodeId,
861 assignment_span: Span,
862 assignee_cmt: mc::cmt)
864 //! Check for assignments that violate the terms of an
865 //! outstanding loan.
867 let loan_path = match opt_loan_path(&assignee_cmt) {
869 None => { return; /* no loan path, can't be any loans */ }
872 this.each_in_scope_loan_affecting_path(assignment_id, &*loan_path, |loan| {
873 this.report_illegal_mutation(assignment_span, &*loan_path, loan);
879 pub fn report_illegal_mutation(&self,
881 loan_path: &LoanPath,
885 format!("cannot assign to `{}` because it is borrowed",
886 self.bccx.loan_path_to_string(loan_path)).as_slice());
889 format!("borrow of `{}` occurs here",
890 self.bccx.loan_path_to_string(loan_path)).as_slice());