1 // Copyright 2012-2014 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 /*! See doc.rs for a thorough explanation of the borrow checker */
13 #![allow(non_camel_case_types)]
15 use middle::dataflow::DataFlowContext;
16 use middle::dataflow::DataFlowOperator;
17 use euv = middle::expr_use_visitor;
18 use mc = middle::mem_categorization;
20 use util::ppaux::{note_and_explain_region, Repr, UserString};
22 use std::cell::{Cell};
23 use std::ops::{BitOr, BitAnd};
25 use std::string::String;
29 use syntax::codemap::Span;
30 use syntax::parse::token;
32 use syntax::visit::{Visitor, FnKind};
33 use syntax::ast::{FnDecl, Block, NodeId};
39 Err(e) => { return Err(e); }
53 pub struct LoanDataFlowOperator;
55 pub type LoanDataFlow<'a> = DataFlowContext<'a, LoanDataFlowOperator>;
57 impl<'a> Visitor<()> for BorrowckCtxt<'a> {
58 fn visit_fn(&mut self, fk: &FnKind, fd: &FnDecl,
59 b: &Block, s: Span, n: NodeId, _: ()) {
60 borrowck_fn(self, fk, fd, b, s, n);
63 fn visit_item(&mut self, item: &ast::Item, _: ()) {
64 borrowck_item(self, item);
68 pub fn check_crate(tcx: &ty::ctxt,
70 let mut bccx = BorrowckCtxt {
73 loaned_paths_same: Cell::new(0),
74 loaned_paths_imm: Cell::new(0),
75 stable_paths: Cell::new(0),
76 guaranteed_paths: Cell::new(0),
80 visit::walk_crate(&mut bccx, krate, ());
82 if tcx.sess.borrowck_stats() {
83 println!("--- borrowck stats ---");
84 println!("paths requiring guarantees: {}",
85 bccx.stats.guaranteed_paths.get());
86 println!("paths requiring loans : {}",
87 make_stat(&bccx, bccx.stats.loaned_paths_same.get()));
88 println!("paths requiring imm loans : {}",
89 make_stat(&bccx, bccx.stats.loaned_paths_imm.get()));
90 println!("stable paths : {}",
91 make_stat(&bccx, bccx.stats.stable_paths.get()));
94 fn make_stat(bccx: &BorrowckCtxt, stat: uint) -> String {
95 let stat_f = stat as f64;
96 let total = bccx.stats.guaranteed_paths.get() as f64;
97 format_strbuf!("{} ({:.0f}%)", stat , stat_f * 100.0 / total)
101 fn borrowck_item(this: &mut BorrowckCtxt, item: &ast::Item) {
102 // Gather loans for items. Note that we don't need
103 // to check loans for single expressions. The check
104 // loan step is intended for things that have a data
105 // flow dependent conditions.
107 ast::ItemStatic(_, _, ex) => {
108 gather_loans::gather_loans_in_static_initializer(this, ex);
111 visit::walk_item(this, item, ());
116 fn borrowck_fn(this: &mut BorrowckCtxt,
122 debug!("borrowck_fn(id={})", id);
124 // Check the body of fn items.
125 let id_range = ast_util::compute_id_range_for_fn_body(fk, decl, body, sp, id);
126 let (all_loans, move_data) =
127 gather_loans::gather_loans_in_fn(this, decl, body);
129 DataFlowContext::new(this.tcx,
130 LoanDataFlowOperator,
133 for (loan_idx, loan) in all_loans.iter().enumerate() {
134 loan_dfcx.add_gen(loan.gen_scope, loan_idx);
135 loan_dfcx.add_kill(loan.kill_scope, loan_idx);
137 loan_dfcx.propagate(body);
139 let flowed_moves = move_data::FlowedMoveData::new(move_data,
144 check_loans::check_loans(this, &loan_dfcx, flowed_moves,
145 all_loans.as_slice(), body);
147 visit::walk_fn(this, fk, decl, body, sp, ());
150 // ----------------------------------------------------------------------
153 pub struct BorrowckCtxt<'a> {
160 pub struct BorrowStats {
161 loaned_paths_same: Cell<uint>,
162 loaned_paths_imm: Cell<uint>,
163 stable_paths: Cell<uint>,
164 guaranteed_paths: Cell<uint>,
167 pub type BckResult<T> = Result<T, BckError>;
170 pub enum PartialTotal {
171 Partial, // Loan affects some portion
172 Total // Loan affects entire path
175 ///////////////////////////////////////////////////////////////////////////
176 // Loans and loan paths
178 /// Record of a loan that was issued.
181 loan_path: Rc<LoanPath>,
183 kind: ty::BorrowKind,
184 restrictions: Vec<Restriction>,
185 gen_scope: ast::NodeId,
186 kill_scope: ast::NodeId,
188 cause: euv::LoanCause,
191 #[deriving(Eq, TotalEq, Hash)]
193 LpVar(ast::NodeId), // `x` in doc.rs
194 LpExtend(Rc<LoanPath>, mc::MutabilityCategory, LoanPathElem)
197 #[deriving(Eq, TotalEq, Hash)]
198 pub enum LoanPathElem {
199 LpDeref(mc::PointerKind), // `*LV` in doc.rs
200 LpInterior(mc::InteriorKind) // `LV.f` in doc.rs
204 pub fn node_id(&self) -> ast::NodeId {
206 LpVar(local_id) => local_id,
207 LpExtend(ref base, _, _) => base.node_id()
212 pub fn opt_loan_path(cmt: &mc::cmt) -> Option<Rc<LoanPath>> {
213 //! Computes the `LoanPath` (if any) for a `cmt`.
214 //! Note that this logic is somewhat duplicated in
215 //! the method `compute()` found in `gather_loans::restrictions`,
216 //! which allows it to share common loan path pieces as it
217 //! traverses the CMT.
221 mc::cat_static_item |
222 mc::cat_copied_upvar(mc::CopiedUpvar { onceness: ast::Many, .. }) => {
228 mc::cat_copied_upvar(mc::CopiedUpvar { upvar_id: id, .. }) |
229 mc::cat_upvar(ty::UpvarId {var_id: id, ..}, _) => {
230 Some(Rc::new(LpVar(id)))
233 mc::cat_deref(ref cmt_base, _, pk) => {
234 opt_loan_path(cmt_base).map(|lp| {
235 Rc::new(LpExtend(lp, cmt.mutbl, LpDeref(pk)))
239 mc::cat_interior(ref cmt_base, ik) => {
240 opt_loan_path(cmt_base).map(|lp| {
241 Rc::new(LpExtend(lp, cmt.mutbl, LpInterior(ik)))
245 mc::cat_downcast(ref cmt_base) |
246 mc::cat_discr(ref cmt_base, _) => {
247 opt_loan_path(cmt_base)
252 ///////////////////////////////////////////////////////////////////////////
255 // Borrowing an lvalue often results in *restrictions* that limit what
256 // can be done with this lvalue during the scope of the loan:
258 // - `RESTR_MUTATE`: The lvalue may not be modified or `&mut` borrowed.
259 // - `RESTR_FREEZE`: `&` borrows of the lvalue are forbidden.
261 // In addition, no value which is restricted may be moved. Therefore,
262 // restrictions are meaningful even if the RestrictionSet is empty,
263 // because the restriction against moves is implied.
265 pub struct Restriction {
266 loan_path: Rc<LoanPath>,
271 pub struct RestrictionSet {
275 #[allow(dead_code)] // potentially useful
276 pub static RESTR_EMPTY: RestrictionSet = RestrictionSet {bits: 0b0000};
277 pub static RESTR_MUTATE: RestrictionSet = RestrictionSet {bits: 0b0001};
278 pub static RESTR_FREEZE: RestrictionSet = RestrictionSet {bits: 0b0010};
280 impl RestrictionSet {
281 pub fn intersects(&self, restr: RestrictionSet) -> bool {
282 (self.bits & restr.bits) != 0
286 impl BitOr<RestrictionSet,RestrictionSet> for RestrictionSet {
287 fn bitor(&self, rhs: &RestrictionSet) -> RestrictionSet {
288 RestrictionSet {bits: self.bits | rhs.bits}
292 impl BitAnd<RestrictionSet,RestrictionSet> for RestrictionSet {
293 fn bitand(&self, rhs: &RestrictionSet) -> RestrictionSet {
294 RestrictionSet {bits: self.bits & rhs.bits}
298 impl Repr for RestrictionSet {
299 fn repr(&self, _tcx: &ty::ctxt) -> String {
300 format_strbuf!("RestrictionSet(0x{:x})", self.bits as uint)
304 ///////////////////////////////////////////////////////////////////////////
307 // Errors that can occur
309 pub enum bckerr_code {
311 err_out_of_scope(ty::Region, ty::Region), // superscope, subscope
312 err_borrowed_pointer_too_short(
313 ty::Region, ty::Region, RestrictionSet), // loan, ptr
316 // Combination of an error code and the categorization of the expression
319 pub struct BckError {
321 cause: euv::LoanCause,
326 pub enum AliasableViolationKind {
328 BorrowViolation(euv::LoanCause)
331 pub enum MovedValueUseKind {
336 ///////////////////////////////////////////////////////////////////////////
339 impl<'a> BorrowckCtxt<'a> {
340 pub fn is_subregion_of(&self, r_sub: ty::Region, r_sup: ty::Region)
342 self.tcx.region_maps.is_subregion_of(r_sub, r_sup)
345 pub fn is_subscope_of(&self, r_sub: ast::NodeId, r_sup: ast::NodeId)
347 self.tcx.region_maps.is_subscope_of(r_sub, r_sup)
350 pub fn mc(&self) -> mc::MemCategorizationContext<'a,ty::ctxt> {
351 mc::MemCategorizationContext::new(self.tcx)
354 pub fn cat_expr(&self, expr: &ast::Expr) -> mc::cmt {
355 match self.mc().cat_expr(expr) {
358 self.tcx.sess.span_bug(expr.span, "error in mem categorization");
363 pub fn cat_expr_unadjusted(&self, expr: &ast::Expr) -> mc::cmt {
364 match self.mc().cat_expr_unadjusted(expr) {
367 self.tcx.sess.span_bug(expr.span, "error in mem categorization");
372 pub fn cat_expr_autoderefd(&self,
374 adj: &ty::AutoAdjustment)
377 ty::AutoAddEnv(..) | ty::AutoObject(..) => {
379 self.mc().cat_expr_unadjusted(expr)
384 autoderefs: autoderefs, ..}) => {
385 self.mc().cat_expr_autoderefd(expr, autoderefs)
392 self.tcx.sess.span_bug(expr.span,
393 "error in mem categorization");
398 pub fn cat_def(&self,
404 match self.mc().cat_def(id, span, ty, def) {
407 self.tcx.sess.span_bug(span, "error in mem categorization");
412 pub fn cat_captured_var(&self,
413 closure_id: ast::NodeId,
417 // Create the cmt for the variable being borrowed, from the
418 // caller's perspective
419 let var_id = ast_util::def_id_of_def(upvar_def).node;
420 let var_ty = ty::node_id_to_type(self.tcx, var_id);
421 self.cat_def(closure_id, closure_span, var_ty, upvar_def)
424 pub fn cat_discr(&self, cmt: mc::cmt, match_id: ast::NodeId) -> mc::cmt {
426 cat: mc::cat_discr(cmt.clone(), match_id),
427 mutbl: cmt.mutbl.inherit(),
432 pub fn cat_pattern(&self,
435 op: |mc::cmt, &ast::Pat|) {
436 let r = self.mc().cat_pattern(cmt, pat, |_,x,y| op(x,y));
440 pub fn report(&self, err: BckError) {
443 self.bckerr_to_str(&err).as_slice());
444 self.note_and_explain_bckerr(err);
447 pub fn report_use_of_moved_value(&self,
449 use_kind: MovedValueUseKind,
451 move: &move_data::Move,
452 moved_lp: &LoanPath) {
453 let verb = match use_kind {
455 MovedInCapture => "capture",
459 move_data::Declared => {
460 self.tcx.sess.span_err(
462 format!("{} of possibly uninitialized variable: `{}`",
464 self.loan_path_to_str(lp)).as_slice());
467 let partially = if lp == moved_lp {""} else {"partially "};
468 self.tcx.sess.span_err(
470 format!("{} of {}moved value: `{}`",
473 self.loan_path_to_str(lp)).as_slice());
478 move_data::Declared => {}
480 move_data::MoveExpr => {
481 let (expr_ty, expr_span) = match self.tcx.map.find(move.id) {
482 Some(ast_map::NodeExpr(expr)) => {
483 (ty::expr_ty_adjusted(self.tcx, expr), expr.span)
486 self.tcx.sess.bug(format!("MoveExpr({:?}) maps to \
492 let suggestion = move_suggestion(self.tcx, expr_ty,
493 "moved by default (use `copy` to override)");
494 self.tcx.sess.span_note(
496 format!("`{}` moved here because it has type `{}`, which is {}",
497 self.loan_path_to_str(moved_lp),
498 expr_ty.user_string(self.tcx),
499 suggestion).as_slice());
502 move_data::MovePat => {
503 let pat_ty = ty::node_id_to_type(self.tcx, move.id);
504 self.tcx.sess.span_note(self.tcx.map.span(move.id),
505 format!("`{}` moved here because it has type `{}`, \
506 which is moved by default (use `ref` to \
508 self.loan_path_to_str(moved_lp),
509 pat_ty.user_string(self.tcx)).as_slice());
512 move_data::Captured => {
513 let (expr_ty, expr_span) = match self.tcx.map.find(move.id) {
514 Some(ast_map::NodeExpr(expr)) => {
515 (ty::expr_ty_adjusted(self.tcx, expr), expr.span)
518 self.tcx.sess.bug(format!("Captured({:?}) maps to \
524 let suggestion = move_suggestion(self.tcx, expr_ty,
525 "moved by default (make a copy and \
526 capture that instead to override)");
527 self.tcx.sess.span_note(
529 format!("`{}` moved into closure environment here because it \
530 has type `{}`, which is {}",
531 self.loan_path_to_str(moved_lp),
532 expr_ty.user_string(self.tcx),
533 suggestion).as_slice());
537 fn move_suggestion(tcx: &ty::ctxt, ty: ty::t, default_msg: &'static str)
539 match ty::get(ty).sty {
540 ty::ty_closure(box ty::ClosureTy {
541 store: ty::RegionTraitStore(..),
544 "a non-copyable stack closure (capture it in a new closure, \
545 e.g. `|x| f(x)`, to override)",
546 _ if ty::type_moves_by_default(tcx, ty) =>
547 "non-copyable (perhaps you meant to use clone()?)",
553 pub fn report_reassigned_immutable_variable(&self,
557 &move_data::Assignment) {
558 self.tcx.sess.span_err(
560 format!("re-assignment of immutable variable `{}`",
561 self.loan_path_to_str(lp)).as_slice());
562 self.tcx.sess.span_note(assign.span, "prior assignment occurs here");
565 pub fn span_err(&self, s: Span, m: &str) {
566 self.tcx.sess.span_err(s, m);
569 pub fn span_note(&self, s: Span, m: &str) {
570 self.tcx.sess.span_note(s, m);
573 pub fn span_end_note(&self, s: Span, m: &str) {
574 self.tcx.sess.span_end_note(s, m);
577 pub fn bckerr_to_str(&self, err: &BckError) -> String {
580 let descr = match opt_loan_path(&err.cmt) {
582 format_strbuf!("{} {}",
583 err.cmt.mutbl.to_user_str(),
584 self.cmt_to_str(&*err.cmt))
587 format_strbuf!("{} {} `{}`",
588 err.cmt.mutbl.to_user_str(),
589 self.cmt_to_str(&*err.cmt),
590 self.loan_path_to_str(&*lp))
595 euv::ClosureCapture(_) => {
596 format_strbuf!("closure cannot assign to {}", descr)
598 euv::OverloadedOperator |
602 format_strbuf!("cannot borrow {} as mutable", descr)
604 euv::ClosureInvocation => {
605 self.tcx.sess.span_bug(err.span,
606 "err_mutbl with a closure invocation");
610 err_out_of_scope(..) => {
611 let msg = match opt_loan_path(&err.cmt) {
612 None => "borrowed value".to_string(),
614 format_strbuf!("`{}`", self.loan_path_to_str(&*lp))
617 format_strbuf!("{} does not live long enough", msg)
619 err_borrowed_pointer_too_short(..) => {
620 let descr = match opt_loan_path(&err.cmt) {
622 format_strbuf!("`{}`", self.loan_path_to_str(&*lp))
624 None => self.cmt_to_str(&*err.cmt),
627 format_strbuf!("lifetime of {} is too short to guarantee \
628 its contents can be safely reborrowed",
634 pub fn report_aliasability_violation(&self,
636 kind: AliasableViolationKind,
637 cause: mc::AliasableReason) {
638 let prefix = match kind {
639 MutabilityViolation => {
640 "cannot assign to data"
642 BorrowViolation(euv::ClosureCapture(_)) => {
643 // I don't think we can get aliasability violations
644 // with closure captures, so no need to come up with a
645 // good error message. The reason this cannot happen
646 // is because we only capture local variables in
647 // closures, and those are never aliasable.
648 self.tcx.sess.span_bug(
650 "aliasability violation with closure");
652 BorrowViolation(euv::OverloadedOperator) |
653 BorrowViolation(euv::AddrOf) |
654 BorrowViolation(euv::AutoRef) |
655 BorrowViolation(euv::RefBinding) => {
656 "cannot borrow data mutably"
659 BorrowViolation(euv::ClosureInvocation) => {
665 mc::AliasableOther => {
666 self.tcx.sess.span_err(
668 format!("{} in an aliasable location",
671 mc::AliasableStatic(..) |
672 mc::AliasableStaticMut(..) => {
673 self.tcx.sess.span_err(
675 format!("{} in a static location", prefix).as_slice());
677 mc::AliasableManaged => {
678 self.tcx.sess.span_err(
680 format!("{} in a `@` pointer", prefix).as_slice());
682 mc::AliasableBorrowed => {
683 self.tcx.sess.span_err(
685 format!("{} in a `&` reference", prefix).as_slice());
690 pub fn note_and_explain_bckerr(&self, err: BckError) {
695 err_out_of_scope(super_scope, sub_scope) => {
696 note_and_explain_region(
698 "reference must be valid for ",
701 let suggestion = if is_statement_scope(self.tcx, super_scope) {
702 "; consider using a `let` binding to increase its lifetime"
706 note_and_explain_region(
708 "...but borrowed value is only valid for ",
713 err_borrowed_pointer_too_short(loan_scope, ptr_scope, _) => {
714 let descr = match opt_loan_path(&err.cmt) {
716 format_strbuf!("`{}`", self.loan_path_to_str(&*lp))
718 None => self.cmt_to_str(&*err.cmt),
720 note_and_explain_region(
722 format!("{} would have to be valid for ",
726 note_and_explain_region(
728 format!("...but {} is only valid for ", descr).as_slice(),
735 pub fn append_loan_path_to_str(&self,
736 loan_path: &LoanPath,
740 out.push_str(ty::local_var_name_str(self.tcx, id).get());
743 LpExtend(ref lp_base, _, LpInterior(mc::InteriorField(fname))) => {
744 self.append_autoderefd_loan_path_to_str(&**lp_base, out);
746 mc::NamedField(fname) => {
748 out.push_str(token::get_name(fname).get());
750 mc::PositionalField(idx) => {
751 out.push_char('#'); // invent a notation here
752 out.push_str(idx.to_str().as_slice());
757 LpExtend(ref lp_base, _, LpInterior(mc::InteriorElement(_))) => {
758 self.append_autoderefd_loan_path_to_str(&**lp_base, out);
759 out.push_str("[..]");
762 LpExtend(ref lp_base, _, LpDeref(_)) => {
764 self.append_loan_path_to_str(&**lp_base, out);
769 pub fn append_autoderefd_loan_path_to_str(&self,
770 loan_path: &LoanPath,
773 LpExtend(ref lp_base, _, LpDeref(_)) => {
774 // For a path like `(*x).f` or `(*x)[3]`, autoderef
775 // rules would normally allow users to omit the `*x`.
776 // So just serialize such paths to `x.f` or x[3]` respectively.
777 self.append_autoderefd_loan_path_to_str(&**lp_base, out)
780 LpVar(..) | LpExtend(_, _, LpInterior(..)) => {
781 self.append_loan_path_to_str(loan_path, out)
786 pub fn loan_path_to_str(&self, loan_path: &LoanPath) -> String {
787 let mut result = String::new();
788 self.append_loan_path_to_str(loan_path, &mut result);
792 pub fn cmt_to_str(&self, cmt: &mc::cmt_) -> String {
793 self.mc().cmt_to_str(cmt)
797 fn is_statement_scope(tcx: &ty::ctxt, region: ty::Region) -> bool {
799 ty::ReScope(node_id) => {
800 match tcx.map.find(node_id) {
801 Some(ast_map::NodeStmt(_)) => true,
809 impl DataFlowOperator for LoanDataFlowOperator {
811 fn initial_value(&self) -> bool {
812 false // no loans in scope by default
816 fn join(&self, succ: uint, pred: uint) -> uint {
817 succ | pred // loans from both preds are in scope
822 fn repr(&self, tcx: &ty::ctxt) -> String {
823 (format!("Loan_{:?}({}, {:?}, {:?}-{:?}, {})",
825 self.loan_path.repr(tcx),
829 self.restrictions.repr(tcx))).to_string()
833 impl Repr for Restriction {
834 fn repr(&self, tcx: &ty::ctxt) -> String {
835 (format!("Restriction({}, {:x})",
836 self.loan_path.repr(tcx),
837 self.set.bits as uint)).to_string()
841 impl Repr for LoanPath {
842 fn repr(&self, tcx: &ty::ctxt) -> String {
845 (format!("$({})", tcx.map.node_to_str(id))).to_string()
848 &LpExtend(ref lp, _, LpDeref(_)) => {
849 (format!("{}.*", lp.repr(tcx))).to_string()
852 &LpExtend(ref lp, _, LpInterior(ref interior)) => {
855 interior.repr(tcx))).to_string()