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
19 use self::UseError::*;
22 use borrowck::InteriorKind::{InteriorElement, InteriorField};
23 use rustc::middle::expr_use_visitor as euv;
24 use rustc::middle::expr_use_visitor::MutateMode;
25 use rustc::middle::mem_categorization as mc;
26 use rustc::middle::mem_categorization::Categorization;
27 use rustc::middle::region;
28 use rustc::ty::{self, TyCtxt};
35 // FIXME (#16118): These functions are intended to allow the borrow checker to
36 // be less precise in its handling of Box while still allowing moves out of a
37 // Box. They should be removed when Unique is removed from LoanPath.
39 fn owned_ptr_base_path<'a, 'tcx>(loan_path: &'a LoanPath<'tcx>) -> &'a LoanPath<'tcx> {
40 //! Returns the base of the leftmost dereference of an Unique in
41 //! `loan_path`. If there is no dereference of an Unique in `loan_path`,
42 //! then it just returns `loan_path` itself.
44 return match helper(loan_path) {
45 Some(new_loan_path) => new_loan_path,
46 None => loan_path.clone()
49 fn helper<'a, 'tcx>(loan_path: &'a LoanPath<'tcx>) -> Option<&'a LoanPath<'tcx>> {
50 match loan_path.kind {
51 LpVar(_) | LpUpvar(_) => None,
52 LpExtend(ref lp_base, _, LpDeref(mc::Unique)) => {
53 match helper(&lp_base) {
55 None => Some(&lp_base)
58 LpDowncast(ref lp_base, _) |
59 LpExtend(ref lp_base, _, _) => helper(&lp_base)
64 fn owned_ptr_base_path_rc<'tcx>(loan_path: &Rc<LoanPath<'tcx>>) -> Rc<LoanPath<'tcx>> {
65 //! The equivalent of `owned_ptr_base_path` for an &Rc<LoanPath> rather than
68 return match helper(loan_path) {
69 Some(new_loan_path) => new_loan_path,
70 None => loan_path.clone()
73 fn helper<'tcx>(loan_path: &Rc<LoanPath<'tcx>>) -> Option<Rc<LoanPath<'tcx>>> {
74 match loan_path.kind {
75 LpVar(_) | LpUpvar(_) => None,
76 LpExtend(ref lp_base, _, LpDeref(mc::Unique)) => {
77 match helper(lp_base) {
79 None => Some(lp_base.clone())
82 LpDowncast(ref lp_base, _) |
83 LpExtend(ref lp_base, _, _) => helper(lp_base)
88 struct CheckLoanCtxt<'a, 'tcx: 'a> {
89 bccx: &'a BorrowckCtxt<'a, 'tcx>,
90 dfcx_loans: &'a LoanDataFlow<'a, 'tcx>,
91 move_data: &'a move_data::FlowedMoveData<'a, 'tcx>,
92 all_loans: &'a [Loan<'tcx>],
93 param_env: &'a ty::ParameterEnvironment<'tcx>,
96 impl<'a, 'tcx> euv::Delegate<'tcx> for CheckLoanCtxt<'a, 'tcx> {
98 consume_id: ast::NodeId,
101 mode: euv::ConsumeMode) {
102 debug!("consume(consume_id={}, cmt={:?}, mode={:?})",
103 consume_id, cmt, mode);
105 self.consume_common(consume_id, consume_span, cmt, mode);
108 fn matched_pat(&mut self,
109 _matched_pat: &hir::Pat,
111 _mode: euv::MatchMode) { }
113 fn consume_pat(&mut self,
114 consume_pat: &hir::Pat,
116 mode: euv::ConsumeMode) {
117 debug!("consume_pat(consume_pat={:?}, cmt={:?}, mode={:?})",
122 self.consume_common(consume_pat.id, consume_pat.span, cmt, mode);
126 borrow_id: ast::NodeId,
129 loan_region: &'tcx ty::Region,
131 loan_cause: euv::LoanCause)
133 debug!("borrow(borrow_id={}, cmt={:?}, loan_region={:?}, \
134 bk={:?}, loan_cause={:?})",
135 borrow_id, cmt, loan_region,
138 match opt_loan_path(&cmt) {
140 let moved_value_use_kind = match loan_cause {
141 euv::ClosureCapture(_) => MovedInCapture,
144 self.check_if_path_is_moved(borrow_id, borrow_span, moved_value_use_kind, &lp);
149 self.check_for_conflicting_loans(borrow_id);
153 assignment_id: ast::NodeId,
154 assignment_span: Span,
155 assignee_cmt: mc::cmt<'tcx>,
156 mode: euv::MutateMode)
158 debug!("mutate(assignment_id={}, assignee_cmt={:?})",
159 assignment_id, assignee_cmt);
161 match opt_loan_path(&assignee_cmt) {
164 MutateMode::Init | MutateMode::JustWrite => {
165 // In a case like `path = 1`, then path does not
166 // have to be *FULLY* initialized, but we still
167 // must be careful lest it contains derefs of
169 self.check_if_assigned_path_is_moved(assignee_cmt.id,
174 MutateMode::WriteAndRead => {
175 // In a case like `path += 1`, then path must be
176 // fully initialized, since we will read it before
178 self.check_if_path_is_moved(assignee_cmt.id,
188 self.check_assignment(assignment_id, assignment_span, assignee_cmt);
191 fn decl_without_init(&mut self, _id: ast::NodeId, _span: Span) { }
194 pub fn check_loans<'a, 'b, 'c, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
195 dfcx_loans: &LoanDataFlow<'b, 'tcx>,
196 move_data: &move_data::FlowedMoveData<'c, 'tcx>,
197 all_loans: &[Loan<'tcx>],
201 debug!("check_loans(body id={})", body.id);
203 let param_env = ty::ParameterEnvironment::for_item(bccx.tcx, fn_id);
204 let infcx = bccx.tcx.borrowck_fake_infer_ctxt(param_env);
205 let mut clcx = CheckLoanCtxt {
207 dfcx_loans: dfcx_loans,
208 move_data: move_data,
209 all_loans: all_loans,
210 param_env: &infcx.parameter_environment
212 euv::ExprUseVisitor::new(&mut clcx, &infcx).walk_fn(decl, body);
216 enum UseError<'tcx> {
218 UseWhileBorrowed(/*loan*/Rc<LoanPath<'tcx>>, /*loan*/Span)
221 fn compatible_borrow_kinds(borrow_kind1: ty::BorrowKind,
222 borrow_kind2: ty::BorrowKind)
224 borrow_kind1 == ty::ImmBorrow && borrow_kind2 == ty::ImmBorrow
227 impl<'a, 'tcx> CheckLoanCtxt<'a, 'tcx> {
228 pub fn tcx(&self) -> TyCtxt<'a, 'tcx, 'tcx> { self.bccx.tcx }
230 pub fn each_issued_loan<F>(&self, node: ast::NodeId, mut op: F) -> bool where
231 F: FnMut(&Loan<'tcx>) -> bool,
233 //! Iterates over each loan that has been issued
234 //! on entrance to `node`, regardless of whether it is
235 //! actually *in scope* at that point. Sometimes loans
236 //! are issued for future scopes and thus they may have been
237 //! *issued* but not yet be in effect.
239 self.dfcx_loans.each_bit_on_entry(node, |loan_index| {
240 let loan = &self.all_loans[loan_index];
245 pub fn each_in_scope_loan<F>(&self, scope: region::CodeExtent, mut op: F) -> bool where
246 F: FnMut(&Loan<'tcx>) -> bool,
248 //! Like `each_issued_loan()`, but only considers loans that are
249 //! currently in scope.
251 let tcx = self.tcx();
252 self.each_issued_loan(scope.node_id(&tcx.region_maps), |loan| {
253 if tcx.region_maps.is_subscope_of(scope, loan.kill_scope) {
261 fn each_in_scope_loan_affecting_path<F>(&self,
262 scope: region::CodeExtent,
263 loan_path: &LoanPath<'tcx>,
266 F: FnMut(&Loan<'tcx>) -> bool,
268 //! Iterates through all of the in-scope loans affecting `loan_path`,
269 //! calling `op`, and ceasing iteration if `false` is returned.
271 // First, we check for a loan restricting the path P being used. This
272 // accounts for borrows of P but also borrows of subpaths, like P.a.b.
273 // Consider the following example:
275 // let x = &mut a.b.c; // Restricts a, a.b, and a.b.c
276 // let y = a; // Conflicts with restriction
278 let loan_path = owned_ptr_base_path(loan_path);
279 let cont = self.each_in_scope_loan(scope, |loan| {
281 for restr_path in &loan.restricted_paths {
282 if **restr_path == *loan_path {
296 // Next, we must check for *loans* (not restrictions) on the path P or
297 // any base path. This rejects examples like the following:
302 // Limiting this search to *loans* and not *restrictions* means that
303 // examples like the following continue to work:
308 let mut loan_path = loan_path;
310 match loan_path.kind {
311 LpVar(_) | LpUpvar(_) => {
314 LpDowncast(ref lp_base, _) |
315 LpExtend(ref lp_base, _, _) => {
316 loan_path = &lp_base;
320 let cont = self.each_in_scope_loan(scope, |loan| {
321 if *loan.loan_path == *loan_path {
336 pub fn loans_generated_by(&self, node: ast::NodeId) -> Vec<usize> {
337 //! Returns a vector of the loans that are generated as
340 let mut result = Vec::new();
341 self.dfcx_loans.each_gen_bit(node, |loan_index| {
342 result.push(loan_index);
348 pub fn check_for_conflicting_loans(&self, node: ast::NodeId) {
349 //! Checks to see whether any of the loans that are issued
350 //! on entrance to `node` conflict with loans that have already been
351 //! issued when we enter `node` (for example, we do not
352 //! permit two `&mut` borrows of the same variable).
354 //! (Note that some loans can be *issued* without necessarily
355 //! taking effect yet.)
357 debug!("check_for_conflicting_loans(node={:?})", node);
359 let new_loan_indices = self.loans_generated_by(node);
360 debug!("new_loan_indices = {:?}", new_loan_indices);
362 for &new_loan_index in &new_loan_indices {
363 self.each_issued_loan(node, |issued_loan| {
364 let new_loan = &self.all_loans[new_loan_index];
365 // Only report an error for the first issued loan that conflicts
366 // to avoid O(n^2) errors.
367 self.report_error_if_loans_conflict(issued_loan, new_loan)
371 for (i, &x) in new_loan_indices.iter().enumerate() {
372 let old_loan = &self.all_loans[x];
373 for &y in &new_loan_indices[(i+1) ..] {
374 let new_loan = &self.all_loans[y];
375 self.report_error_if_loans_conflict(old_loan, new_loan);
380 pub fn report_error_if_loans_conflict(&self,
381 old_loan: &Loan<'tcx>,
382 new_loan: &Loan<'tcx>)
384 //! Checks whether `old_loan` and `new_loan` can safely be issued
387 debug!("report_error_if_loans_conflict(old_loan={:?}, new_loan={:?})",
391 // Should only be called for loans that are in scope at the same time.
392 assert!(self.tcx().region_maps.scopes_intersect(old_loan.kill_scope,
393 new_loan.kill_scope));
395 self.report_error_if_loan_conflicts_with_restriction(
396 old_loan, new_loan, old_loan, new_loan) &&
397 self.report_error_if_loan_conflicts_with_restriction(
398 new_loan, old_loan, old_loan, new_loan)
401 pub fn report_error_if_loan_conflicts_with_restriction(&self,
404 old_loan: &Loan<'tcx>,
405 new_loan: &Loan<'tcx>)
407 //! Checks whether the restrictions introduced by `loan1` would
408 //! prohibit `loan2`. Returns false if an error is reported.
410 debug!("report_error_if_loan_conflicts_with_restriction(\
411 loan1={:?}, loan2={:?})",
415 if compatible_borrow_kinds(loan1.kind, loan2.kind) {
419 let loan2_base_path = owned_ptr_base_path_rc(&loan2.loan_path);
420 for restr_path in &loan1.restricted_paths {
421 if *restr_path != loan2_base_path { continue; }
423 // If new_loan is something like `x.a`, and old_loan is something like `x.b`, we would
424 // normally generate a rather confusing message (in this case, for multiple mutable
427 // error: cannot borrow `x.b` as mutable more than once at a time
428 // note: previous borrow of `x.a` occurs here; the mutable borrow prevents
429 // subsequent moves, borrows, or modification of `x.a` until the borrow ends
431 // What we want to do instead is get the 'common ancestor' of the two borrow paths and
432 // use that for most of the message instead, giving is something like this:
434 // error: cannot borrow `x` as mutable more than once at a time
435 // note: previous borrow of `x` occurs here (through borrowing `x.a`); the mutable
436 // borrow prevents subsequent moves, borrows, or modification of `x` until the
439 let common = new_loan.loan_path.common(&old_loan.loan_path);
440 let (nl, ol, new_loan_msg, old_loan_msg) = {
441 if new_loan.loan_path.has_fork(&old_loan.loan_path) && common.is_some() {
442 let nl = self.bccx.loan_path_to_string(&common.unwrap());
444 let new_loan_msg = format!(" (via `{}`)",
445 self.bccx.loan_path_to_string(
446 &new_loan.loan_path));
447 let old_loan_msg = format!(" (via `{}`)",
448 self.bccx.loan_path_to_string(
449 &old_loan.loan_path));
450 (nl, ol, new_loan_msg, old_loan_msg)
452 (self.bccx.loan_path_to_string(&new_loan.loan_path),
453 self.bccx.loan_path_to_string(&old_loan.loan_path),
459 let ol_pronoun = if new_loan.loan_path == old_loan.loan_path {
465 // We want to assemble all the relevant locations for the error.
467 // 1. Where did the new loan occur.
468 // - if due to closure creation, where was the variable used in closure?
469 // 2. Where did old loan occur.
470 // 3. Where does old loan expire.
472 let previous_end_span =
473 self.tcx().map.span(old_loan.kill_scope.node_id(&self.tcx().region_maps))
476 let mut err = match (new_loan.kind, old_loan.kind) {
477 (ty::MutBorrow, ty::MutBorrow) => {
478 let mut err = struct_span_err!(self.bccx, new_loan.span, E0499,
479 "cannot borrow `{}`{} as mutable \
480 more than once at a time",
484 &format!("first mutable borrow occurs here{}", old_loan_msg));
487 &format!("second mutable borrow occurs here{}", new_loan_msg));
490 &format!("first borrow ends here"));
494 (ty::UniqueImmBorrow, ty::UniqueImmBorrow) => {
495 let mut err = struct_span_err!(self.bccx, new_loan.span, E0524,
496 "two closures require unique access to `{}` \
501 &format!("first closure is constructed here"));
504 &format!("second closure is constructed here"));
507 &format!("borrow from first closure ends here"));
511 (ty::UniqueImmBorrow, _) => {
512 let mut err = struct_span_err!(self.bccx, new_loan.span, E0500,
513 "closure requires unique access to `{}` \
514 but {} is already borrowed{}",
515 nl, ol_pronoun, old_loan_msg);
518 &format!("closure construction occurs here{}", new_loan_msg));
521 &format!("borrow occurs here{}", old_loan_msg));
524 &format!("borrow ends here"));
528 (_, ty::UniqueImmBorrow) => {
529 let mut err = struct_span_err!(self.bccx, new_loan.span, E0501,
530 "cannot borrow `{}`{} as {} because \
531 previous closure requires unique access",
532 nl, new_loan_msg, new_loan.kind.to_user_str());
535 &format!("borrow occurs here{}", new_loan_msg));
538 &format!("closure construction occurs here{}", old_loan_msg));
541 &format!("borrow from closure ends here"));
546 let mut err = struct_span_err!(self.bccx, new_loan.span, E0502,
547 "cannot borrow `{}`{} as {} because \
548 {} is also borrowed as {}{}",
551 new_loan.kind.to_user_str(),
553 old_loan.kind.to_user_str(),
557 &format!("{} borrow occurs here{}",
558 new_loan.kind.to_user_str(),
562 &format!("{} borrow occurs here{}",
563 old_loan.kind.to_user_str(),
567 &format!("{} borrow ends here",
568 old_loan.kind.to_user_str()));
573 match new_loan.cause {
574 euv::ClosureCapture(span) => {
577 &format!("borrow occurs due to use of `{}` in closure", nl));
582 match old_loan.cause {
583 euv::ClosureCapture(span) => {
586 &format!("previous borrow occurs due to use of `{}` in closure",
599 fn consume_common(&self,
603 mode: euv::ConsumeMode) {
604 match opt_loan_path(&cmt) {
606 let moved_value_use_kind = match mode {
608 self.check_for_copy_of_frozen_path(id, span, &lp);
612 match self.move_data.kind_of_move_of_path(id, &lp) {
614 // Sometimes moves don't have a move kind;
615 // this either means that the original move
616 // was from something illegal to move,
617 // or was moved from referent of an unsafe
618 // pointer or something like that.
622 self.check_for_move_of_borrowed_path(id, span,
624 if move_kind == move_data::Captured {
634 self.check_if_path_is_moved(id, span, moved_value_use_kind, &lp);
640 fn check_for_copy_of_frozen_path(&self,
643 copy_path: &LoanPath<'tcx>) {
644 match self.analyze_restrictions_on_use(id, copy_path, ty::ImmBorrow) {
646 UseWhileBorrowed(loan_path, loan_span) => {
647 struct_span_err!(self.bccx, span, E0503,
648 "cannot use `{}` because it was mutably borrowed",
649 &self.bccx.loan_path_to_string(copy_path))
650 .span_label(loan_span,
651 &format!("borrow of `{}` occurs here",
652 &self.bccx.loan_path_to_string(&loan_path))
655 &format!("use of borrowed `{}`",
656 &self.bccx.loan_path_to_string(&loan_path)))
662 fn check_for_move_of_borrowed_path(&self,
665 move_path: &LoanPath<'tcx>,
666 move_kind: move_data::MoveKind) {
667 // We want to detect if there are any loans at all, so we search for
668 // any loans incompatible with MutBorrrow, since all other kinds of
669 // loans are incompatible with that.
670 match self.analyze_restrictions_on_use(id, move_path, ty::MutBorrow) {
672 UseWhileBorrowed(loan_path, loan_span) => {
673 let mut err = match move_kind {
674 move_data::Captured => {
675 let mut err = struct_span_err!(self.bccx, span, E0504,
676 "cannot move `{}` into closure because it is borrowed",
677 &self.bccx.loan_path_to_string(move_path));
680 &format!("borrow of `{}` occurs here",
681 &self.bccx.loan_path_to_string(&loan_path))
685 &format!("move into closure occurs here")
689 move_data::Declared |
690 move_data::MoveExpr |
691 move_data::MovePat => {
692 let mut err = struct_span_err!(self.bccx, span, E0505,
693 "cannot move out of `{}` because it is borrowed",
694 &self.bccx.loan_path_to_string(move_path));
697 &format!("borrow of `{}` occurs here",
698 &self.bccx.loan_path_to_string(&loan_path))
702 &format!("move out of `{}` occurs here",
703 &self.bccx.loan_path_to_string(move_path))
714 pub fn analyze_restrictions_on_use(&self,
715 expr_id: ast::NodeId,
716 use_path: &LoanPath<'tcx>,
717 borrow_kind: ty::BorrowKind)
719 debug!("analyze_restrictions_on_use(expr_id={}, use_path={:?})",
720 self.tcx().map.node_to_string(expr_id),
725 self.each_in_scope_loan_affecting_path(
726 self.tcx().region_maps.node_extent(expr_id), use_path, |loan| {
727 if !compatible_borrow_kinds(loan.kind, borrow_kind) {
728 ret = UseWhileBorrowed(loan.loan_path.clone(), loan.span);
738 /// Reports an error if `expr` (which should be a path)
739 /// is using a moved/uninitialized value
740 fn check_if_path_is_moved(&self,
743 use_kind: MovedValueUseKind,
744 lp: &Rc<LoanPath<'tcx>>) {
745 debug!("check_if_path_is_moved(id={}, use_kind={:?}, lp={:?})",
748 // FIXME (22079): if you find yourself tempted to cut and paste
749 // the body below and then specializing the error reporting,
750 // consider refactoring this instead!
752 let base_lp = owned_ptr_base_path_rc(lp);
753 self.move_data.each_move_of(id, &base_lp, |the_move, moved_lp| {
754 self.bccx.report_use_of_moved_value(
765 /// Reports an error if assigning to `lp` will use a
766 /// moved/uninitialized value. Mainly this is concerned with
767 /// detecting derefs of uninitialized pointers.
773 /// a = 10; // ok, even though a is uninitialized
775 /// struct Point { x: u32, y: u32 }
777 /// p.x = 22; // ok, even though `p` is uninitialized
779 /// let p: Box<Point>;
780 /// (*p).x = 22; // not ok, p is uninitialized, can't deref
782 fn check_if_assigned_path_is_moved(&self,
785 use_kind: MovedValueUseKind,
786 lp: &Rc<LoanPath<'tcx>>)
789 LpVar(_) | LpUpvar(_) => {
790 // assigning to `x` does not require that `x` is initialized
792 LpDowncast(ref lp_base, _) => {
793 // assigning to `(P->Variant).f` is ok if assigning to `P` is ok
794 self.check_if_assigned_path_is_moved(id, span,
797 LpExtend(ref lp_base, _, LpInterior(_, InteriorField(_))) => {
798 match lp_base.to_type().sty {
799 ty::TyStruct(def, _) | ty::TyEnum(def, _) if def.has_dtor() => {
800 // In the case where the owner implements drop, then
801 // the path must be initialized to prevent a case of
802 // partial reinitialization
804 // FIXME (22079): could refactor via hypothetical
805 // generalized check_if_path_is_moved
806 let loan_path = owned_ptr_base_path_rc(lp_base);
807 self.move_data.each_move_of(id, &loan_path, |_, _| {
809 .report_partial_reinitialization_of_uninitialized_structure(
819 // assigning to `P.f` is ok if assigning to `P` is ok
820 self.check_if_assigned_path_is_moved(id, span,
823 LpExtend(ref lp_base, _, LpInterior(_, InteriorElement(..))) |
824 LpExtend(ref lp_base, _, LpDeref(_)) => {
825 // assigning to `P[i]` requires `P` is initialized
826 // assigning to `(*P)` requires `P` is initialized
827 self.check_if_path_is_moved(id, span, use_kind, lp_base);
832 fn check_assignment(&self,
833 assignment_id: ast::NodeId,
834 assignment_span: Span,
835 assignee_cmt: mc::cmt<'tcx>) {
836 debug!("check_assignment(assignee_cmt={:?})", assignee_cmt);
838 // Check that we don't invalidate any outstanding loans
839 if let Some(loan_path) = opt_loan_path(&assignee_cmt) {
840 let scope = self.tcx().region_maps.node_extent(assignment_id);
841 self.each_in_scope_loan_affecting_path(scope, &loan_path, |loan| {
842 self.report_illegal_mutation(assignment_span, &loan_path, loan);
847 // Check for reassignments to (immutable) local variables. This
848 // needs to be done here instead of in check_loans because we
849 // depend on move data.
850 if let Categorization::Local(local_id) = assignee_cmt.cat {
851 let lp = opt_loan_path(&assignee_cmt).unwrap();
852 self.move_data.each_assignment_of(assignment_id, &lp, |assign| {
853 if assignee_cmt.mutbl.is_mutable() {
854 self.tcx().used_mut_nodes.borrow_mut().insert(local_id);
856 self.bccx.report_reassigned_immutable_variable(
867 pub fn report_illegal_mutation(&self,
869 loan_path: &LoanPath<'tcx>,
871 struct_span_err!(self.bccx, span, E0506,
872 "cannot assign to `{}` because it is borrowed",
873 self.bccx.loan_path_to_string(loan_path))
874 .span_label(loan.span,
875 &format!("borrow of `{}` occurs here",
876 self.bccx.loan_path_to_string(loan_path)))
878 &format!("assignment to borrowed `{}` occurs here",
879 self.bccx.loan_path_to_string(loan_path)))