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};
32 use rustc_mir::util::borrowck_errors::{BorrowckErrors, Origin};
36 // FIXME (#16118): These functions are intended to allow the borrow checker to
37 // be less precise in its handling of Box while still allowing moves out of a
38 // Box. They should be removed when Unique is removed from LoanPath.
40 fn owned_ptr_base_path<'a, 'tcx>(loan_path: &'a LoanPath<'tcx>) -> &'a LoanPath<'tcx> {
41 //! Returns the base of the leftmost dereference of an Unique in
42 //! `loan_path`. If there is no dereference of an Unique in `loan_path`,
43 //! then it just returns `loan_path` itself.
45 return match helper(loan_path) {
46 Some(new_loan_path) => new_loan_path,
47 None => loan_path.clone()
50 fn helper<'a, 'tcx>(loan_path: &'a LoanPath<'tcx>) -> Option<&'a LoanPath<'tcx>> {
51 match loan_path.kind {
52 LpVar(_) | LpUpvar(_) => None,
53 LpExtend(ref lp_base, _, LpDeref(mc::Unique)) => {
54 match helper(&lp_base) {
56 None => Some(&lp_base)
59 LpDowncast(ref lp_base, _) |
60 LpExtend(ref lp_base, ..) => helper(&lp_base)
65 fn owned_ptr_base_path_rc<'tcx>(loan_path: &Rc<LoanPath<'tcx>>) -> Rc<LoanPath<'tcx>> {
66 //! The equivalent of `owned_ptr_base_path` for an &Rc<LoanPath> rather than
69 return match helper(loan_path) {
70 Some(new_loan_path) => new_loan_path,
71 None => loan_path.clone()
74 fn helper<'tcx>(loan_path: &Rc<LoanPath<'tcx>>) -> Option<Rc<LoanPath<'tcx>>> {
75 match loan_path.kind {
76 LpVar(_) | LpUpvar(_) => None,
77 LpExtend(ref lp_base, _, LpDeref(mc::Unique)) => {
78 match helper(lp_base) {
80 None => Some(lp_base.clone())
83 LpDowncast(ref lp_base, _) |
84 LpExtend(ref lp_base, ..) => helper(lp_base)
89 struct CheckLoanCtxt<'a, 'tcx: 'a> {
90 bccx: &'a BorrowckCtxt<'a, 'tcx>,
91 dfcx_loans: &'a LoanDataFlow<'a, 'tcx>,
92 move_data: &'a move_data::FlowedMoveData<'a, 'tcx>,
93 all_loans: &'a [Loan<'tcx>],
94 param_env: ty::ParamEnv<'tcx>,
97 impl<'a, 'tcx> euv::Delegate<'tcx> for CheckLoanCtxt<'a, 'tcx> {
99 consume_id: ast::NodeId,
102 mode: euv::ConsumeMode) {
103 debug!("consume(consume_id={}, cmt={:?}, mode={:?})",
104 consume_id, cmt, mode);
106 let hir_id = self.tcx().hir.node_to_hir_id(consume_id);
107 self.consume_common(hir_id.local_id, consume_span, cmt, mode);
110 fn matched_pat(&mut self,
111 _matched_pat: &hir::Pat,
113 _mode: euv::MatchMode) { }
115 fn consume_pat(&mut self,
116 consume_pat: &hir::Pat,
118 mode: euv::ConsumeMode) {
119 debug!("consume_pat(consume_pat={:?}, cmt={:?}, mode={:?})",
124 self.consume_common(consume_pat.hir_id.local_id, consume_pat.span, cmt, mode);
128 borrow_id: ast::NodeId,
131 loan_region: ty::Region<'tcx>,
133 loan_cause: euv::LoanCause)
135 debug!("borrow(borrow_id={}, cmt={:?}, loan_region={:?}, \
136 bk={:?}, loan_cause={:?})",
137 borrow_id, cmt, loan_region,
140 let hir_id = self.tcx().hir.node_to_hir_id(borrow_id);
141 if let Some(lp) = opt_loan_path(&cmt) {
142 let moved_value_use_kind = match loan_cause {
143 euv::ClosureCapture(_) => MovedInCapture,
146 self.check_if_path_is_moved(hir_id.local_id, borrow_span, moved_value_use_kind, &lp);
149 self.check_for_conflicting_loans(hir_id.local_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 if let Some(lp) = opt_loan_path(&assignee_cmt) {
163 MutateMode::Init | MutateMode::JustWrite => {
164 // In a case like `path = 1`, then path does not
165 // have to be *FULLY* initialized, but we still
166 // must be careful lest it contains derefs of
168 let hir_id = self.tcx().hir.node_to_hir_id(assignee_cmt.id);
169 self.check_if_assigned_path_is_moved(hir_id.local_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 let hir_id = self.tcx().hir.node_to_hir_id(assignee_cmt.id);
179 self.check_if_path_is_moved(hir_id.local_id,
186 self.check_assignment(self.tcx().hir.node_to_hir_id(assignment_id).local_id,
187 assignment_span, assignee_cmt);
190 fn decl_without_init(&mut self, _id: ast::NodeId, _span: Span) { }
193 pub fn check_loans<'a, 'b, 'c, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
194 dfcx_loans: &LoanDataFlow<'b, 'tcx>,
195 move_data: &move_data::FlowedMoveData<'c, 'tcx>,
196 all_loans: &[Loan<'tcx>],
198 debug!("check_loans(body id={})", body.value.id);
200 let def_id = bccx.tcx.hir.body_owner_def_id(body.id());
201 let param_env = bccx.tcx.param_env(def_id);
202 let mut clcx = CheckLoanCtxt {
209 let rvalue_promotable_map = bccx.tcx.rvalue_promotable_map(def_id);
210 euv::ExprUseVisitor::new(&mut clcx,
213 &bccx.region_scope_tree,
215 Some(rvalue_promotable_map))
220 enum UseError<'tcx> {
222 UseWhileBorrowed(/*loan*/Rc<LoanPath<'tcx>>, /*loan*/Span)
225 fn compatible_borrow_kinds(borrow_kind1: ty::BorrowKind,
226 borrow_kind2: ty::BorrowKind)
228 borrow_kind1 == ty::ImmBorrow && borrow_kind2 == ty::ImmBorrow
231 impl<'a, 'tcx> CheckLoanCtxt<'a, 'tcx> {
232 pub fn tcx(&self) -> TyCtxt<'a, 'tcx, 'tcx> { self.bccx.tcx }
234 pub fn each_issued_loan<F>(&self, node: hir::ItemLocalId, mut op: F) -> bool where
235 F: FnMut(&Loan<'tcx>) -> bool,
237 //! Iterates over each loan that has been issued
238 //! on entrance to `node`, regardless of whether it is
239 //! actually *in scope* at that point. Sometimes loans
240 //! are issued for future scopes and thus they may have been
241 //! *issued* but not yet be in effect.
243 self.dfcx_loans.each_bit_on_entry(node, |loan_index| {
244 let loan = &self.all_loans[loan_index];
249 pub fn each_in_scope_loan<F>(&self, scope: region::Scope, mut op: F) -> bool where
250 F: FnMut(&Loan<'tcx>) -> bool,
252 //! Like `each_issued_loan()`, but only considers loans that are
253 //! currently in scope.
255 self.each_issued_loan(scope.item_local_id(), |loan| {
256 if self.bccx.region_scope_tree.is_subscope_of(scope, loan.kill_scope) {
264 fn each_in_scope_loan_affecting_path<F>(&self,
265 scope: region::Scope,
266 loan_path: &LoanPath<'tcx>,
269 F: FnMut(&Loan<'tcx>) -> bool,
271 //! Iterates through all of the in-scope loans affecting `loan_path`,
272 //! calling `op`, and ceasing iteration if `false` is returned.
274 // First, we check for a loan restricting the path P being used. This
275 // accounts for borrows of P but also borrows of subpaths, like P.a.b.
276 // Consider the following example:
278 // let x = &mut a.b.c; // Restricts a, a.b, and a.b.c
279 // let y = a; // Conflicts with restriction
281 let loan_path = owned_ptr_base_path(loan_path);
282 let cont = self.each_in_scope_loan(scope, |loan| {
284 for restr_path in &loan.restricted_paths {
285 if **restr_path == *loan_path {
299 // Next, we must check for *loans* (not restrictions) on the path P or
300 // any base path. This rejects examples like the following:
305 // Limiting this search to *loans* and not *restrictions* means that
306 // examples like the following continue to work:
311 let mut loan_path = loan_path;
313 match loan_path.kind {
314 LpVar(_) | LpUpvar(_) => {
317 LpDowncast(ref lp_base, _) |
318 LpExtend(ref lp_base, ..) => {
319 loan_path = &lp_base;
323 let cont = self.each_in_scope_loan(scope, |loan| {
324 if *loan.loan_path == *loan_path {
339 pub fn loans_generated_by(&self, node: hir::ItemLocalId) -> Vec<usize> {
340 //! Returns a vector of the loans that are generated as
343 let mut result = Vec::new();
344 self.dfcx_loans.each_gen_bit(node, |loan_index| {
345 result.push(loan_index);
351 pub fn check_for_conflicting_loans(&self, node: hir::ItemLocalId) {
352 //! Checks to see whether any of the loans that are issued
353 //! on entrance to `node` conflict with loans that have already been
354 //! issued when we enter `node` (for example, we do not
355 //! permit two `&mut` borrows of the same variable).
357 //! (Note that some loans can be *issued* without necessarily
358 //! taking effect yet.)
360 debug!("check_for_conflicting_loans(node={:?})", node);
362 let new_loan_indices = self.loans_generated_by(node);
363 debug!("new_loan_indices = {:?}", new_loan_indices);
365 for &new_loan_index in &new_loan_indices {
366 self.each_issued_loan(node, |issued_loan| {
367 let new_loan = &self.all_loans[new_loan_index];
368 // Only report an error for the first issued loan that conflicts
369 // to avoid O(n^2) errors.
370 self.report_error_if_loans_conflict(issued_loan, new_loan)
374 for (i, &x) in new_loan_indices.iter().enumerate() {
375 let old_loan = &self.all_loans[x];
376 for &y in &new_loan_indices[(i+1) ..] {
377 let new_loan = &self.all_loans[y];
378 self.report_error_if_loans_conflict(old_loan, new_loan);
383 pub fn report_error_if_loans_conflict(&self,
384 old_loan: &Loan<'tcx>,
385 new_loan: &Loan<'tcx>)
387 //! Checks whether `old_loan` and `new_loan` can safely be issued
390 debug!("report_error_if_loans_conflict(old_loan={:?}, new_loan={:?})",
394 // Should only be called for loans that are in scope at the same time.
395 assert!(self.bccx.region_scope_tree.scopes_intersect(old_loan.kill_scope,
396 new_loan.kill_scope));
398 self.report_error_if_loan_conflicts_with_restriction(
399 old_loan, new_loan, old_loan, new_loan) &&
400 self.report_error_if_loan_conflicts_with_restriction(
401 new_loan, old_loan, old_loan, new_loan)
404 pub fn report_error_if_loan_conflicts_with_restriction(&self,
407 old_loan: &Loan<'tcx>,
408 new_loan: &Loan<'tcx>)
410 //! Checks whether the restrictions introduced by `loan1` would
411 //! prohibit `loan2`. Returns false if an error is reported.
413 debug!("report_error_if_loan_conflicts_with_restriction(\
414 loan1={:?}, loan2={:?})",
418 if compatible_borrow_kinds(loan1.kind, loan2.kind) {
422 let loan2_base_path = owned_ptr_base_path_rc(&loan2.loan_path);
423 for restr_path in &loan1.restricted_paths {
424 if *restr_path != loan2_base_path { continue; }
426 // If new_loan is something like `x.a`, and old_loan is something like `x.b`, we would
427 // normally generate a rather confusing message (in this case, for multiple mutable
430 // error: cannot borrow `x.b` as mutable more than once at a time
431 // note: previous borrow of `x.a` occurs here; the mutable borrow prevents
432 // subsequent moves, borrows, or modification of `x.a` until the borrow ends
434 // What we want to do instead is get the 'common ancestor' of the two borrow paths and
435 // use that for most of the message instead, giving is something like this:
437 // error: cannot borrow `x` as mutable more than once at a time
438 // note: previous borrow of `x` occurs here (through borrowing `x.a`); the mutable
439 // borrow prevents subsequent moves, borrows, or modification of `x` until the
442 let common = new_loan.loan_path.common(&old_loan.loan_path);
443 let (nl, ol, new_loan_msg, old_loan_msg) = {
444 if new_loan.loan_path.has_fork(&old_loan.loan_path) && common.is_some() {
445 let nl = self.bccx.loan_path_to_string(&common.unwrap());
447 let new_loan_msg = format!(" (via `{}`)",
448 self.bccx.loan_path_to_string(
449 &new_loan.loan_path));
450 let old_loan_msg = format!(" (via `{}`)",
451 self.bccx.loan_path_to_string(
452 &old_loan.loan_path));
453 (nl, ol, new_loan_msg, old_loan_msg)
455 (self.bccx.loan_path_to_string(&new_loan.loan_path),
456 self.bccx.loan_path_to_string(&old_loan.loan_path),
462 let ol_pronoun = if new_loan.loan_path == old_loan.loan_path {
468 // We want to assemble all the relevant locations for the error.
470 // 1. Where did the new loan occur.
471 // - if due to closure creation, where was the variable used in closure?
472 // 2. Where did old loan occur.
473 // 3. Where does old loan expire.
475 let previous_end_span =
476 old_loan.kill_scope.span(self.tcx(), &self.bccx.region_scope_tree).end_point();
478 let mut err = match (new_loan.kind, old_loan.kind) {
479 (ty::MutBorrow, ty::MutBorrow) =>
480 self.bccx.cannot_mutably_borrow_multiply(
481 new_loan.span, &nl, &new_loan_msg, old_loan.span, &old_loan_msg,
482 previous_end_span, Origin::Ast),
483 (ty::UniqueImmBorrow, ty::UniqueImmBorrow) =>
484 self.bccx.cannot_uniquely_borrow_by_two_closures(
485 new_loan.span, &nl, old_loan.span, previous_end_span, Origin::Ast),
486 (ty::UniqueImmBorrow, _) =>
487 self.bccx.cannot_uniquely_borrow_by_one_closure(
488 new_loan.span, &nl, &new_loan_msg,
489 old_loan.span, &ol_pronoun, &old_loan_msg, previous_end_span, Origin::Ast),
490 (_, ty::UniqueImmBorrow) => {
491 let new_loan_str = &new_loan.kind.to_user_str();
492 self.bccx.cannot_reborrow_already_uniquely_borrowed(
493 new_loan.span, &nl, &new_loan_msg, new_loan_str,
494 old_loan.span, &old_loan_msg, previous_end_span, Origin::Ast)
497 self.bccx.cannot_reborrow_already_borrowed(
499 &nl, &new_loan_msg, &new_loan.kind.to_user_str(),
500 old_loan.span, &ol_pronoun, &old_loan.kind.to_user_str(), &old_loan_msg,
501 previous_end_span, Origin::Ast)
504 match new_loan.cause {
505 euv::ClosureCapture(span) => {
508 format!("borrow occurs due to use of `{}` in closure", nl));
513 match old_loan.cause {
514 euv::ClosureCapture(span) => {
517 format!("previous borrow occurs due to use of `{}` in closure",
530 fn consume_common(&self,
531 id: hir::ItemLocalId,
534 mode: euv::ConsumeMode) {
535 if let Some(lp) = opt_loan_path(&cmt) {
536 let moved_value_use_kind = match mode {
538 self.check_for_copy_of_frozen_path(id, span, &lp);
542 match self.move_data.kind_of_move_of_path(id, &lp) {
544 // Sometimes moves don't have a move kind;
545 // this either means that the original move
546 // was from something illegal to move,
547 // or was moved from referent of an unsafe
548 // pointer or something like that.
552 self.check_for_move_of_borrowed_path(id, span,
554 if move_kind == move_data::Captured {
564 self.check_if_path_is_moved(id, span, moved_value_use_kind, &lp);
568 fn check_for_copy_of_frozen_path(&self,
569 id: hir::ItemLocalId,
571 copy_path: &LoanPath<'tcx>) {
572 match self.analyze_restrictions_on_use(id, copy_path, ty::ImmBorrow) {
574 UseWhileBorrowed(loan_path, loan_span) => {
575 let desc = self.bccx.loan_path_to_string(copy_path);
576 self.bccx.cannot_use_when_mutably_borrowed(
578 loan_span, &self.bccx.loan_path_to_string(&loan_path),
585 fn check_for_move_of_borrowed_path(&self,
586 id: hir::ItemLocalId,
588 move_path: &LoanPath<'tcx>,
589 move_kind: move_data::MoveKind) {
590 // We want to detect if there are any loans at all, so we search for
591 // any loans incompatible with MutBorrrow, since all other kinds of
592 // loans are incompatible with that.
593 match self.analyze_restrictions_on_use(id, move_path, ty::MutBorrow) {
595 UseWhileBorrowed(loan_path, loan_span) => {
596 let mut err = match move_kind {
597 move_data::Captured => {
598 let mut err = self.bccx.cannot_move_into_closure(
599 span, &self.bccx.loan_path_to_string(move_path), Origin::Ast);
602 format!("borrow of `{}` occurs here",
603 &self.bccx.loan_path_to_string(&loan_path))
607 "move into closure occurs here"
611 move_data::Declared |
612 move_data::MoveExpr |
613 move_data::MovePat => {
614 let desc = self.bccx.loan_path_to_string(move_path);
615 let mut err = self.bccx.cannot_move_when_borrowed(span, &desc, Origin::Ast);
618 format!("borrow of `{}` occurs here",
619 &self.bccx.loan_path_to_string(&loan_path))
623 format!("move out of `{}` occurs here",
624 &self.bccx.loan_path_to_string(move_path))
635 pub fn analyze_restrictions_on_use(&self,
636 expr_id: hir::ItemLocalId,
637 use_path: &LoanPath<'tcx>,
638 borrow_kind: ty::BorrowKind)
640 debug!("analyze_restrictions_on_use(expr_id={:?}, use_path={:?})",
645 self.each_in_scope_loan_affecting_path(
646 region::Scope::Node(expr_id), use_path, |loan| {
647 if !compatible_borrow_kinds(loan.kind, borrow_kind) {
648 ret = UseWhileBorrowed(loan.loan_path.clone(), loan.span);
658 /// Reports an error if `expr` (which should be a path)
659 /// is using a moved/uninitialized value
660 fn check_if_path_is_moved(&self,
661 id: hir::ItemLocalId,
663 use_kind: MovedValueUseKind,
664 lp: &Rc<LoanPath<'tcx>>) {
665 debug!("check_if_path_is_moved(id={:?}, use_kind={:?}, lp={:?})",
668 // FIXME: if you find yourself tempted to cut and paste
669 // the body below and then specializing the error reporting,
670 // consider refactoring this instead!
672 let base_lp = owned_ptr_base_path_rc(lp);
673 self.move_data.each_move_of(id, &base_lp, |the_move, moved_lp| {
674 self.bccx.report_use_of_moved_value(
685 /// Reports an error if assigning to `lp` will use a
686 /// moved/uninitialized value. Mainly this is concerned with
687 /// detecting derefs of uninitialized pointers.
693 /// a = 10; // ok, even though a is uninitialized
697 /// struct Point { x: u32, y: u32 }
698 /// let mut p: Point;
699 /// p.x = 22; // ok, even though `p` is uninitialized
702 /// ```compile_fail,E0381
703 /// # struct Point { x: u32, y: u32 }
704 /// let mut p: Box<Point>;
705 /// (*p).x = 22; // not ok, p is uninitialized, can't deref
707 fn check_if_assigned_path_is_moved(&self,
708 id: hir::ItemLocalId,
710 use_kind: MovedValueUseKind,
711 lp: &Rc<LoanPath<'tcx>>)
714 LpVar(_) | LpUpvar(_) => {
715 // assigning to `x` does not require that `x` is initialized
717 LpDowncast(ref lp_base, _) => {
718 // assigning to `(P->Variant).f` is ok if assigning to `P` is ok
719 self.check_if_assigned_path_is_moved(id, span,
722 LpExtend(ref lp_base, _, LpInterior(_, InteriorField(_))) => {
723 match lp_base.to_type().sty {
724 ty::TyAdt(def, _) if def.has_dtor(self.tcx()) => {
725 // In the case where the owner implements drop, then
726 // the path must be initialized to prevent a case of
727 // partial reinitialization
729 // FIXME: could refactor via hypothetical
730 // generalized check_if_path_is_moved
731 let loan_path = owned_ptr_base_path_rc(lp_base);
732 self.move_data.each_move_of(id, &loan_path, |_, _| {
734 .report_partial_reinitialization_of_uninitialized_structure(
744 // assigning to `P.f` is ok if assigning to `P` is ok
745 self.check_if_assigned_path_is_moved(id, span,
748 LpExtend(ref lp_base, _, LpInterior(_, InteriorElement)) |
749 LpExtend(ref lp_base, _, LpDeref(_)) => {
750 // assigning to `P[i]` requires `P` is initialized
751 // assigning to `(*P)` requires `P` is initialized
752 self.check_if_path_is_moved(id, span, use_kind, lp_base);
757 fn check_assignment(&self,
758 assignment_id: hir::ItemLocalId,
759 assignment_span: Span,
760 assignee_cmt: mc::cmt<'tcx>) {
761 debug!("check_assignment(assignee_cmt={:?})", assignee_cmt);
763 // Check that we don't invalidate any outstanding loans
764 if let Some(loan_path) = opt_loan_path(&assignee_cmt) {
765 let scope = region::Scope::Node(assignment_id);
766 self.each_in_scope_loan_affecting_path(scope, &loan_path, |loan| {
767 self.report_illegal_mutation(assignment_span, &loan_path, loan);
772 // Check for reassignments to (immutable) local variables. This
773 // needs to be done here instead of in check_loans because we
774 // depend on move data.
775 if let Categorization::Local(local_id) = assignee_cmt.cat {
776 let lp = opt_loan_path(&assignee_cmt).unwrap();
777 self.move_data.each_assignment_of(assignment_id, &lp, |assign| {
778 if assignee_cmt.mutbl.is_mutable() {
779 let hir_id = self.bccx.tcx.hir.node_to_hir_id(local_id);
780 self.bccx.used_mut_nodes.borrow_mut().insert(hir_id);
782 self.bccx.report_reassigned_immutable_variable(
793 pub fn report_illegal_mutation(&self,
795 loan_path: &LoanPath<'tcx>,
797 self.bccx.cannot_assign_to_borrowed(
798 span, loan.span, &self.bccx.loan_path_to_string(loan_path), Origin::Ast)