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)]
16 use middle::dataflow::DataFlowContext;
17 use middle::dataflow::BitwiseOperator;
18 use middle::dataflow::DataFlowOperator;
20 use middle::expr_use_visitor as euv;
21 use middle::mem_categorization as mc;
23 use util::ppaux::{note_and_explain_region, Repr, UserString};
25 use std::cell::{Cell};
27 use std::gc::{Gc, GC};
28 use std::string::String;
31 use syntax::ast_map::blocks::{FnLikeNode, FnParts};
33 use syntax::codemap::Span;
34 use syntax::parse::token;
36 use syntax::visit::{Visitor, FnKind};
37 use syntax::ast::{FnDecl, Block, NodeId};
43 Err(e) => { return Err(e); }
59 pub struct LoanDataFlowOperator;
61 pub type LoanDataFlow<'a, 'tcx> = DataFlowContext<'a, 'tcx, LoanDataFlowOperator>;
63 impl<'a, 'tcx> Visitor<()> for BorrowckCtxt<'a, 'tcx> {
64 fn visit_fn(&mut self, fk: &FnKind, fd: &FnDecl,
65 b: &Block, s: Span, n: NodeId, _: ()) {
66 borrowck_fn(self, fk, fd, b, s, n);
69 fn visit_item(&mut self, item: &ast::Item, _: ()) {
70 borrowck_item(self, item);
74 pub fn check_crate(tcx: &ty::ctxt,
76 let mut bccx = BorrowckCtxt {
78 stats: box(GC) BorrowStats {
79 loaned_paths_same: Cell::new(0),
80 loaned_paths_imm: Cell::new(0),
81 stable_paths: Cell::new(0),
82 guaranteed_paths: Cell::new(0),
86 visit::walk_crate(&mut bccx, krate, ());
88 if tcx.sess.borrowck_stats() {
89 println!("--- borrowck stats ---");
90 println!("paths requiring guarantees: {}",
91 bccx.stats.guaranteed_paths.get());
92 println!("paths requiring loans : {}",
93 make_stat(&bccx, bccx.stats.loaned_paths_same.get()));
94 println!("paths requiring imm loans : {}",
95 make_stat(&bccx, bccx.stats.loaned_paths_imm.get()));
96 println!("stable paths : {}",
97 make_stat(&bccx, bccx.stats.stable_paths.get()));
100 fn make_stat(bccx: &BorrowckCtxt, stat: uint) -> String {
101 let total = bccx.stats.guaranteed_paths.get() as f64;
102 let perc = if total == 0.0 { 0.0 } else { stat as f64 * 100.0 / total };
103 format!("{} ({:.0f}%)", stat, perc)
107 fn borrowck_item(this: &mut BorrowckCtxt, item: &ast::Item) {
108 // Gather loans for items. Note that we don't need
109 // to check loans for single expressions. The check
110 // loan step is intended for things that have a data
111 // flow dependent conditions.
113 ast::ItemStatic(_, _, ex) => {
114 gather_loans::gather_loans_in_static_initializer(this, &*ex);
117 visit::walk_item(this, item, ());
122 /// Collection of conclusions determined via borrow checker analyses.
123 pub struct AnalysisData<'a, 'tcx: 'a> {
124 pub all_loans: Vec<Loan>,
125 pub loans: DataFlowContext<'a, 'tcx, LoanDataFlowOperator>,
126 pub move_data: move_data::FlowedMoveData<'a, 'tcx>,
129 fn borrowck_fn(this: &mut BorrowckCtxt,
135 debug!("borrowck_fn(id={})", id);
136 let cfg = cfg::CFG::new(this.tcx, body);
137 let AnalysisData { all_loans,
139 move_data:flowed_moves } =
140 build_borrowck_dataflow_data(this, fk, decl, &cfg, body, sp, id);
142 check_loans::check_loans(this, &loan_dfcx, flowed_moves,
143 all_loans.as_slice(), decl, body);
145 visit::walk_fn(this, fk, decl, body, sp, ());
148 fn build_borrowck_dataflow_data<'a, 'tcx>(this: &mut BorrowckCtxt<'a, 'tcx>,
154 id: ast::NodeId) -> AnalysisData<'a, 'tcx> {
155 // Check the body of fn items.
156 let id_range = ast_util::compute_id_range_for_fn_body(fk, decl, body, sp, id);
157 let (all_loans, move_data) =
158 gather_loans::gather_loans_in_fn(this, decl, body);
161 DataFlowContext::new(this.tcx,
165 LoanDataFlowOperator,
168 for (loan_idx, loan) in all_loans.iter().enumerate() {
169 loan_dfcx.add_gen(loan.gen_scope, loan_idx);
170 loan_dfcx.add_kill(loan.kill_scope, loan_idx);
172 loan_dfcx.add_kills_from_flow_exits(cfg);
173 loan_dfcx.propagate(cfg, body);
175 let flowed_moves = move_data::FlowedMoveData::new(move_data,
182 AnalysisData { all_loans: all_loans,
184 move_data:flowed_moves }
187 /// This and a `ty::ctxt` is all you need to run the dataflow analyses
188 /// used in the borrow checker.
189 pub struct FnPartsWithCFG<'a> {
190 pub fn_parts: FnParts<'a>,
191 pub cfg: &'a cfg::CFG,
194 impl<'a> FnPartsWithCFG<'a> {
195 pub fn from_fn_like(f: &'a FnLikeNode,
196 g: &'a cfg::CFG) -> FnPartsWithCFG<'a> {
197 FnPartsWithCFG { fn_parts: f.to_fn_parts(), cfg: g }
201 /// Accessor for introspective clients inspecting `AnalysisData` and
202 /// the `BorrowckCtxt` itself , e.g. the flowgraph visualizer.
203 pub fn build_borrowck_dataflow_data_for_fn<'a, 'tcx>(
204 tcx: &'a ty::ctxt<'tcx>,
205 input: FnPartsWithCFG<'a>) -> (BorrowckCtxt<'a, 'tcx>, AnalysisData<'a, 'tcx>) {
207 let mut bccx = BorrowckCtxt {
209 stats: box(GC) BorrowStats {
210 loaned_paths_same: Cell::new(0),
211 loaned_paths_imm: Cell::new(0),
212 stable_paths: Cell::new(0),
213 guaranteed_paths: Cell::new(0),
217 let p = input.fn_parts;
219 let dataflow_data = build_borrowck_dataflow_data(&mut bccx,
227 (bccx, dataflow_data)
230 // ----------------------------------------------------------------------
233 pub struct BorrowckCtxt<'a, 'tcx: 'a> {
234 tcx: &'a ty::ctxt<'tcx>,
237 stats: Gc<BorrowStats>,
240 pub struct BorrowStats {
241 loaned_paths_same: Cell<uint>,
242 loaned_paths_imm: Cell<uint>,
243 stable_paths: Cell<uint>,
244 guaranteed_paths: Cell<uint>,
247 pub type BckResult<T> = Result<T, BckError>;
249 #[deriving(PartialEq)]
250 pub enum PartialTotal {
251 Partial, // Loan affects some portion
252 Total // Loan affects entire path
255 ///////////////////////////////////////////////////////////////////////////
256 // Loans and loan paths
258 /// Record of a loan that was issued.
261 loan_path: Rc<LoanPath>,
262 kind: ty::BorrowKind,
263 restricted_paths: Vec<Rc<LoanPath>>,
264 gen_scope: ast::NodeId,
265 kill_scope: ast::NodeId,
267 cause: euv::LoanCause,
271 pub fn loan_path(&self) -> Rc<LoanPath> {
272 self.loan_path.clone()
276 #[deriving(PartialEq, Eq, Hash)]
278 LpVar(ast::NodeId), // `x` in doc.rs
279 LpUpvar(ty::UpvarId), // `x` captured by-value into closure
280 LpExtend(Rc<LoanPath>, mc::MutabilityCategory, LoanPathElem)
283 #[deriving(PartialEq, Eq, Hash)]
284 pub enum LoanPathElem {
285 LpDeref(mc::PointerKind), // `*LV` in doc.rs
286 LpInterior(mc::InteriorKind) // `LV.f` in doc.rs
289 pub fn closure_to_block(closure_id: ast::NodeId,
290 tcx: &ty::ctxt) -> ast::NodeId {
291 match tcx.map.get(closure_id) {
292 ast_map::NodeExpr(expr) => match expr.node {
293 ast::ExprProc(_, block) |
294 ast::ExprFnBlock(_, _, block) |
295 ast::ExprUnboxedFn(_, _, _, block) => { block.id }
296 _ => fail!("encountered non-closure id: {}", closure_id)
298 _ => fail!("encountered non-expr id: {}", closure_id)
303 pub fn kill_scope(&self, tcx: &ty::ctxt) -> ast::NodeId {
305 LpVar(local_id) => tcx.region_maps.var_scope(local_id),
307 closure_to_block(upvar_id.closure_expr_id, tcx),
308 LpExtend(ref base, _, _) => base.kill_scope(tcx),
313 pub fn opt_loan_path(cmt: &mc::cmt) -> Option<Rc<LoanPath>> {
314 //! Computes the `LoanPath` (if any) for a `cmt`.
315 //! Note that this logic is somewhat duplicated in
316 //! the method `compute()` found in `gather_loans::restrictions`,
317 //! which allows it to share common loan path pieces as it
318 //! traverses the CMT.
322 mc::cat_static_item |
323 mc::cat_copied_upvar(mc::CopiedUpvar { onceness: ast::Many, .. }) => {
329 Some(Rc::new(LpVar(id)))
332 mc::cat_upvar(ty::UpvarId {var_id: id, closure_expr_id: proc_id}, _) |
333 mc::cat_copied_upvar(mc::CopiedUpvar { upvar_id: id,
335 capturing_proc: proc_id }) => {
336 let upvar_id = ty::UpvarId{ var_id: id, closure_expr_id: proc_id };
337 Some(Rc::new(LpUpvar(upvar_id)))
340 mc::cat_deref(ref cmt_base, _, pk) => {
341 opt_loan_path(cmt_base).map(|lp| {
342 Rc::new(LpExtend(lp, cmt.mutbl, LpDeref(pk)))
346 mc::cat_interior(ref cmt_base, ik) => {
347 opt_loan_path(cmt_base).map(|lp| {
348 Rc::new(LpExtend(lp, cmt.mutbl, LpInterior(ik)))
352 mc::cat_downcast(ref cmt_base) |
353 mc::cat_discr(ref cmt_base, _) => {
354 opt_loan_path(cmt_base)
359 ///////////////////////////////////////////////////////////////////////////
362 // Errors that can occur
363 #[deriving(PartialEq)]
364 pub enum bckerr_code {
366 err_out_of_scope(ty::Region, ty::Region), // superscope, subscope
367 err_borrowed_pointer_too_short(ty::Region, ty::Region), // loan, ptr
370 // Combination of an error code and the categorization of the expression
372 #[deriving(PartialEq)]
373 pub struct BckError {
375 cause: euv::LoanCause,
380 pub enum AliasableViolationKind {
382 BorrowViolation(euv::LoanCause)
385 pub enum MovedValueUseKind {
390 ///////////////////////////////////////////////////////////////////////////
393 impl<'a, 'tcx> BorrowckCtxt<'a, 'tcx> {
394 pub fn is_subregion_of(&self, r_sub: ty::Region, r_sup: ty::Region)
396 self.tcx.region_maps.is_subregion_of(r_sub, r_sup)
399 pub fn is_subscope_of(&self, r_sub: ast::NodeId, r_sup: ast::NodeId)
401 self.tcx.region_maps.is_subscope_of(r_sub, r_sup)
404 pub fn mc(&self) -> mc::MemCategorizationContext<'a, ty::ctxt<'tcx>> {
405 mc::MemCategorizationContext::new(self.tcx)
408 pub fn cat_expr(&self, expr: &ast::Expr) -> mc::cmt {
409 match self.mc().cat_expr(expr) {
412 self.tcx.sess.span_bug(expr.span, "error in mem categorization");
417 pub fn cat_expr_unadjusted(&self, expr: &ast::Expr) -> mc::cmt {
418 match self.mc().cat_expr_unadjusted(expr) {
421 self.tcx.sess.span_bug(expr.span, "error in mem categorization");
426 pub fn cat_expr_autoderefd(&self,
428 adj: &ty::AutoAdjustment)
433 autoderefs: autoderefs, ..}) => {
434 self.mc().cat_expr_autoderefd(expr, autoderefs)
436 ty::AutoAddEnv(..) => {
438 self.mc().cat_expr_unadjusted(expr)
445 self.tcx.sess.span_bug(expr.span,
446 "error in mem categorization");
451 pub fn cat_def(&self,
457 match self.mc().cat_def(id, span, ty, def) {
460 self.tcx.sess.span_bug(span, "error in mem categorization");
465 pub fn cat_captured_var(&self,
466 closure_id: ast::NodeId,
470 // Create the cmt for the variable being borrowed, from the
471 // caller's perspective
472 let var_id = upvar_def.def_id().node;
473 let var_ty = ty::node_id_to_type(self.tcx, var_id);
474 self.cat_def(closure_id, closure_span, var_ty, upvar_def)
477 pub fn cat_discr(&self, cmt: mc::cmt, match_id: ast::NodeId) -> mc::cmt {
479 cat: mc::cat_discr(cmt.clone(), match_id),
480 mutbl: cmt.mutbl.inherit(),
485 pub fn cat_pattern(&self,
488 op: |mc::cmt, &ast::Pat|) {
489 let r = self.mc().cat_pattern(cmt, pat, |_,x,y| op(x,y));
493 pub fn report(&self, err: BckError) {
496 self.bckerr_to_string(&err).as_slice());
497 self.note_and_explain_bckerr(err);
500 pub fn report_use_of_moved_value(&self,
502 use_kind: MovedValueUseKind,
504 move: &move_data::Move,
505 moved_lp: &LoanPath) {
506 let verb = match use_kind {
508 MovedInCapture => "capture",
512 move_data::Declared => {
513 self.tcx.sess.span_err(
515 format!("{} of possibly uninitialized variable: `{}`",
517 self.loan_path_to_string(lp)).as_slice());
520 let partially = if lp == moved_lp {""} else {"partially "};
521 self.tcx.sess.span_err(
523 format!("{} of {}moved value: `{}`",
526 self.loan_path_to_string(lp)).as_slice());
531 move_data::Declared => {}
533 move_data::MoveExpr => {
534 let (expr_ty, expr_span) = match self.tcx.map.find(move.id) {
535 Some(ast_map::NodeExpr(expr)) => {
536 (ty::expr_ty_adjusted(self.tcx, &*expr), expr.span)
539 self.tcx.sess.bug(format!("MoveExpr({:?}) maps to \
545 let suggestion = move_suggestion(self.tcx, expr_ty,
546 "moved by default (use `copy` to override)");
547 self.tcx.sess.span_note(
549 format!("`{}` moved here because it has type `{}`, which is {}",
550 self.loan_path_to_string(moved_lp),
551 expr_ty.user_string(self.tcx),
552 suggestion).as_slice());
555 move_data::MovePat => {
556 let pat_ty = ty::node_id_to_type(self.tcx, move.id);
557 self.tcx.sess.span_note(self.tcx.map.span(move.id),
558 format!("`{}` moved here because it has type `{}`, \
559 which is moved by default (use `ref` to \
561 self.loan_path_to_string(moved_lp),
562 pat_ty.user_string(self.tcx)).as_slice());
565 move_data::Captured => {
566 let (expr_ty, expr_span) = match self.tcx.map.find(move.id) {
567 Some(ast_map::NodeExpr(expr)) => {
568 (ty::expr_ty_adjusted(self.tcx, &*expr), expr.span)
571 self.tcx.sess.bug(format!("Captured({:?}) maps to \
577 let suggestion = move_suggestion(self.tcx, expr_ty,
578 "moved by default (make a copy and \
579 capture that instead to override)");
580 self.tcx.sess.span_note(
582 format!("`{}` moved into closure environment here because it \
583 has type `{}`, which is {}",
584 self.loan_path_to_string(moved_lp),
585 expr_ty.user_string(self.tcx),
586 suggestion).as_slice());
590 fn move_suggestion(tcx: &ty::ctxt, ty: ty::t, default_msg: &'static str)
592 match ty::get(ty).sty {
593 ty::ty_closure(box ty::ClosureTy {
594 store: ty::RegionTraitStore(..),
597 "a non-copyable stack closure (capture it in a new closure, \
598 e.g. `|x| f(x)`, to override)",
599 _ if ty::type_moves_by_default(tcx, ty) =>
600 "non-copyable (perhaps you meant to use clone()?)",
606 pub fn report_reassigned_immutable_variable(&self,
610 &move_data::Assignment) {
611 self.tcx.sess.span_err(
613 format!("re-assignment of immutable variable `{}`",
614 self.loan_path_to_string(lp)).as_slice());
615 self.tcx.sess.span_note(assign.span, "prior assignment occurs here");
618 pub fn span_err(&self, s: Span, m: &str) {
619 self.tcx.sess.span_err(s, m);
622 pub fn span_note(&self, s: Span, m: &str) {
623 self.tcx.sess.span_note(s, m);
626 pub fn span_end_note(&self, s: Span, m: &str) {
627 self.tcx.sess.span_end_note(s, m);
630 pub fn bckerr_to_string(&self, err: &BckError) -> String {
633 let descr = match opt_loan_path(&err.cmt) {
636 err.cmt.mutbl.to_user_str(),
637 self.cmt_to_string(&*err.cmt))
640 format!("{} {} `{}`",
641 err.cmt.mutbl.to_user_str(),
642 self.cmt_to_string(&*err.cmt),
643 self.loan_path_to_string(&*lp))
648 euv::ClosureCapture(_) => {
649 format!("closure cannot assign to {}", descr)
651 euv::OverloadedOperator |
656 format!("cannot borrow {} as mutable", descr)
658 euv::ClosureInvocation => {
659 self.tcx.sess.span_bug(err.span,
660 "err_mutbl with a closure invocation");
664 err_out_of_scope(..) => {
665 let msg = match opt_loan_path(&err.cmt) {
666 None => "borrowed value".to_string(),
668 format!("`{}`", self.loan_path_to_string(&*lp))
671 format!("{} does not live long enough", msg)
673 err_borrowed_pointer_too_short(..) => {
674 let descr = match opt_loan_path(&err.cmt) {
676 format!("`{}`", self.loan_path_to_string(&*lp))
678 None => self.cmt_to_string(&*err.cmt),
681 format!("lifetime of {} is too short to guarantee \
682 its contents can be safely reborrowed",
688 pub fn report_aliasability_violation(&self,
690 kind: AliasableViolationKind,
691 cause: mc::AliasableReason) {
692 let prefix = match kind {
693 MutabilityViolation => {
694 "cannot assign to data"
696 BorrowViolation(euv::ClosureCapture(_)) => {
697 // I don't think we can get aliasability violations
698 // with closure captures, so no need to come up with a
699 // good error message. The reason this cannot happen
700 // is because we only capture local variables in
701 // closures, and those are never aliasable.
702 self.tcx.sess.span_bug(
704 "aliasability violation with closure");
706 BorrowViolation(euv::OverloadedOperator) |
707 BorrowViolation(euv::AddrOf) |
708 BorrowViolation(euv::AutoRef) |
709 BorrowViolation(euv::RefBinding) => {
710 "cannot borrow data mutably"
713 BorrowViolation(euv::ClosureInvocation) => {
717 BorrowViolation(euv::ForLoop) => {
723 mc::AliasableOther => {
724 self.tcx.sess.span_err(
726 format!("{} in an aliasable location",
729 mc::AliasableStatic(..) |
730 mc::AliasableStaticMut(..) => {
731 self.tcx.sess.span_err(
733 format!("{} in a static location", prefix).as_slice());
735 mc::AliasableManaged => {
736 self.tcx.sess.span_err(
738 format!("{} in a `@` pointer", prefix).as_slice());
740 mc::AliasableBorrowed => {
741 self.tcx.sess.span_err(
743 format!("{} in a `&` reference", prefix).as_slice());
748 pub fn note_and_explain_bckerr(&self, err: BckError) {
753 err_out_of_scope(super_scope, sub_scope) => {
754 note_and_explain_region(
756 "reference must be valid for ",
759 let suggestion = if is_statement_scope(self.tcx, super_scope) {
760 "; consider using a `let` binding to increase its lifetime"
764 note_and_explain_region(
766 "...but borrowed value is only valid for ",
771 err_borrowed_pointer_too_short(loan_scope, ptr_scope) => {
772 let descr = match opt_loan_path(&err.cmt) {
774 format!("`{}`", self.loan_path_to_string(&*lp))
776 None => self.cmt_to_string(&*err.cmt),
778 note_and_explain_region(
780 format!("{} would have to be valid for ",
784 note_and_explain_region(
786 format!("...but {} is only valid for ", descr).as_slice(),
793 pub fn append_loan_path_to_string(&self,
794 loan_path: &LoanPath,
797 LpUpvar(ty::UpvarId{ var_id: id, closure_expr_id: _ }) |
799 out.push_str(ty::local_var_name_str(self.tcx, id).get());
802 LpExtend(ref lp_base, _, LpInterior(mc::InteriorField(fname))) => {
803 self.append_autoderefd_loan_path_to_string(&**lp_base, out);
805 mc::NamedField(fname) => {
807 out.push_str(token::get_name(fname).get());
809 mc::PositionalField(idx) => {
810 out.push_char('#'); // invent a notation here
811 out.push_str(idx.to_string().as_slice());
816 LpExtend(ref lp_base, _, LpInterior(mc::InteriorElement(_))) => {
817 self.append_autoderefd_loan_path_to_string(&**lp_base, out);
818 out.push_str("[..]");
821 LpExtend(ref lp_base, _, LpDeref(_)) => {
823 self.append_loan_path_to_string(&**lp_base, out);
828 pub fn append_autoderefd_loan_path_to_string(&self,
829 loan_path: &LoanPath,
832 LpExtend(ref lp_base, _, LpDeref(_)) => {
833 // For a path like `(*x).f` or `(*x)[3]`, autoderef
834 // rules would normally allow users to omit the `*x`.
835 // So just serialize such paths to `x.f` or x[3]` respectively.
836 self.append_autoderefd_loan_path_to_string(&**lp_base, out)
839 LpVar(..) | LpUpvar(..) | LpExtend(_, _, LpInterior(..)) => {
840 self.append_loan_path_to_string(loan_path, out)
845 pub fn loan_path_to_string(&self, loan_path: &LoanPath) -> String {
846 let mut result = String::new();
847 self.append_loan_path_to_string(loan_path, &mut result);
851 pub fn cmt_to_string(&self, cmt: &mc::cmt_) -> String {
852 self.mc().cmt_to_string(cmt)
856 fn is_statement_scope(tcx: &ty::ctxt, region: ty::Region) -> bool {
858 ty::ReScope(node_id) => {
859 match tcx.map.find(node_id) {
860 Some(ast_map::NodeStmt(_)) => true,
868 impl BitwiseOperator for LoanDataFlowOperator {
870 fn join(&self, succ: uint, pred: uint) -> uint {
871 succ | pred // loans from both preds are in scope
875 impl DataFlowOperator for LoanDataFlowOperator {
877 fn initial_value(&self) -> bool {
878 false // no loans in scope by default
883 fn repr(&self, tcx: &ty::ctxt) -> String {
884 format!("Loan_{:?}({}, {:?}, {:?}-{:?}, {})",
886 self.loan_path.repr(tcx),
890 self.restricted_paths.repr(tcx))
894 impl Repr for LoanPath {
895 fn repr(&self, tcx: &ty::ctxt) -> String {
898 format!("$({})", tcx.map.node_to_string(id))
901 &LpUpvar(ty::UpvarId{ var_id, closure_expr_id }) => {
902 let s = tcx.map.node_to_string(var_id);
903 format!("$({} captured by id={})", s, closure_expr_id)
906 &LpExtend(ref lp, _, LpDeref(_)) => {
907 format!("{}.*", lp.repr(tcx))
910 &LpExtend(ref lp, _, LpInterior(ref interior)) => {
911 format!("{}.{}", lp.repr(tcx), interior.repr(tcx))