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};
26 use std::string::String;
29 use syntax::ast_map::blocks::{FnLikeNode, FnParts};
31 use syntax::codemap::Span;
32 use syntax::parse::token;
34 use syntax::visit::{Visitor, FnKind};
35 use syntax::ast::{FnDecl, Block, NodeId};
41 Err(e) => { return Err(e); }
57 pub struct LoanDataFlowOperator;
59 pub type LoanDataFlow<'a, 'tcx> = DataFlowContext<'a, 'tcx, LoanDataFlowOperator>;
61 impl<'a, 'tcx, 'v> Visitor<'v> for BorrowckCtxt<'a, 'tcx> {
62 fn visit_fn(&mut self, fk: FnKind<'v>, fd: &'v FnDecl,
63 b: &'v Block, s: Span, n: NodeId) {
64 borrowck_fn(self, fk, fd, b, s, n);
67 fn visit_item(&mut self, item: &ast::Item) {
68 borrowck_item(self, item);
72 pub fn check_crate(tcx: &ty::ctxt) {
73 let mut bccx = BorrowckCtxt {
83 visit::walk_crate(&mut bccx, tcx.map.krate());
85 if tcx.sess.borrowck_stats() {
86 println!("--- borrowck stats ---");
87 println!("paths requiring guarantees: {}",
88 bccx.stats.guaranteed_paths);
89 println!("paths requiring loans : {}",
90 make_stat(&bccx, bccx.stats.loaned_paths_same));
91 println!("paths requiring imm loans : {}",
92 make_stat(&bccx, bccx.stats.loaned_paths_imm));
93 println!("stable paths : {}",
94 make_stat(&bccx, bccx.stats.stable_paths));
97 fn make_stat(bccx: &BorrowckCtxt, stat: uint) -> String {
98 let total = bccx.stats.guaranteed_paths as f64;
99 let perc = if total == 0.0 { 0.0 } else { stat as f64 * 100.0 / total };
100 format!("{} ({:.0f}%)", stat, perc)
104 fn borrowck_item(this: &mut BorrowckCtxt, item: &ast::Item) {
105 // Gather loans for items. Note that we don't need
106 // to check loans for single expressions. The check
107 // loan step is intended for things that have a data
108 // flow dependent conditions.
110 ast::ItemStatic(_, _, ref ex) => {
111 gather_loans::gather_loans_in_static_initializer(this, &**ex);
114 visit::walk_item(this, item);
119 /// Collection of conclusions determined via borrow checker analyses.
120 pub struct AnalysisData<'a, 'tcx: 'a> {
121 pub all_loans: Vec<Loan>,
122 pub loans: DataFlowContext<'a, 'tcx, LoanDataFlowOperator>,
123 pub move_data: move_data::FlowedMoveData<'a, 'tcx>,
126 fn borrowck_fn(this: &mut BorrowckCtxt,
132 debug!("borrowck_fn(id={})", id);
133 let cfg = cfg::CFG::new(this.tcx, body);
134 let AnalysisData { all_loans,
136 move_data:flowed_moves } =
137 build_borrowck_dataflow_data(this, fk, decl, &cfg, body, sp, id);
139 check_loans::check_loans(this, &loan_dfcx, flowed_moves,
140 all_loans.as_slice(), decl, body);
142 visit::walk_fn(this, fk, decl, body, sp);
145 fn build_borrowck_dataflow_data<'a, 'tcx>(this: &mut BorrowckCtxt<'a, 'tcx>,
151 id: ast::NodeId) -> AnalysisData<'a, 'tcx> {
152 // Check the body of fn items.
153 let id_range = ast_util::compute_id_range_for_fn_body(fk, decl, body, sp, id);
154 let (all_loans, move_data) =
155 gather_loans::gather_loans_in_fn(this, decl, body);
158 DataFlowContext::new(this.tcx,
162 LoanDataFlowOperator,
165 for (loan_idx, loan) in all_loans.iter().enumerate() {
166 loan_dfcx.add_gen(loan.gen_scope, loan_idx);
167 loan_dfcx.add_kill(loan.kill_scope, loan_idx);
169 loan_dfcx.add_kills_from_flow_exits(cfg);
170 loan_dfcx.propagate(cfg, body);
172 let flowed_moves = move_data::FlowedMoveData::new(move_data,
179 AnalysisData { all_loans: all_loans,
181 move_data:flowed_moves }
184 /// This and a `ty::ctxt` is all you need to run the dataflow analyses
185 /// used in the borrow checker.
186 pub struct FnPartsWithCFG<'a> {
187 pub fn_parts: FnParts<'a>,
188 pub cfg: &'a cfg::CFG,
191 impl<'a> FnPartsWithCFG<'a> {
192 pub fn from_fn_like(f: &'a FnLikeNode,
193 g: &'a cfg::CFG) -> FnPartsWithCFG<'a> {
194 FnPartsWithCFG { fn_parts: f.to_fn_parts(), cfg: g }
198 /// Accessor for introspective clients inspecting `AnalysisData` and
199 /// the `BorrowckCtxt` itself , e.g. the flowgraph visualizer.
200 pub fn build_borrowck_dataflow_data_for_fn<'a, 'tcx>(
201 tcx: &'a ty::ctxt<'tcx>,
202 input: FnPartsWithCFG<'a>) -> (BorrowckCtxt<'a, 'tcx>, AnalysisData<'a, 'tcx>) {
204 let mut bccx = BorrowckCtxt {
207 loaned_paths_same: 0,
214 let p = input.fn_parts;
216 let dataflow_data = build_borrowck_dataflow_data(&mut bccx,
224 (bccx, dataflow_data)
227 // ----------------------------------------------------------------------
230 pub struct BorrowckCtxt<'a, 'tcx: 'a> {
231 tcx: &'a ty::ctxt<'tcx>,
238 loaned_paths_same: uint,
239 loaned_paths_imm: uint,
241 guaranteed_paths: uint
244 pub type BckResult<T> = Result<T, BckError>;
246 #[deriving(PartialEq)]
247 pub enum PartialTotal {
248 Partial, // Loan affects some portion
249 Total // Loan affects entire path
252 ///////////////////////////////////////////////////////////////////////////
253 // Loans and loan paths
255 /// Record of a loan that was issued.
258 loan_path: Rc<LoanPath>,
259 kind: ty::BorrowKind,
260 restricted_paths: Vec<Rc<LoanPath>>,
261 gen_scope: ast::NodeId,
262 kill_scope: ast::NodeId,
264 cause: euv::LoanCause,
268 pub fn loan_path(&self) -> Rc<LoanPath> {
269 self.loan_path.clone()
273 #[deriving(PartialEq, Eq, Hash)]
275 LpVar(ast::NodeId), // `x` in doc.rs
276 LpUpvar(ty::UpvarId), // `x` captured by-value into closure
277 LpExtend(Rc<LoanPath>, mc::MutabilityCategory, LoanPathElem)
280 #[deriving(PartialEq, Eq, Hash)]
281 pub enum LoanPathElem {
282 LpDeref(mc::PointerKind), // `*LV` in doc.rs
283 LpInterior(mc::InteriorKind) // `LV.f` in doc.rs
286 pub fn closure_to_block(closure_id: ast::NodeId,
287 tcx: &ty::ctxt) -> ast::NodeId {
288 match tcx.map.get(closure_id) {
289 ast_map::NodeExpr(expr) => match expr.node {
290 ast::ExprProc(_, ref block) |
291 ast::ExprFnBlock(_, _, ref block) |
292 ast::ExprUnboxedFn(_, _, _, ref block) => { block.id }
293 _ => fail!("encountered non-closure id: {}", closure_id)
295 _ => fail!("encountered non-expr id: {}", closure_id)
300 pub fn kill_scope(&self, tcx: &ty::ctxt) -> ast::NodeId {
302 LpVar(local_id) => tcx.region_maps.var_scope(local_id),
304 closure_to_block(upvar_id.closure_expr_id, tcx),
305 LpExtend(ref base, _, _) => base.kill_scope(tcx),
310 pub fn opt_loan_path(cmt: &mc::cmt) -> Option<Rc<LoanPath>> {
311 //! Computes the `LoanPath` (if any) for a `cmt`.
312 //! Note that this logic is somewhat duplicated in
313 //! the method `compute()` found in `gather_loans::restrictions`,
314 //! which allows it to share common loan path pieces as it
315 //! traverses the CMT.
319 mc::cat_static_item |
320 mc::cat_copied_upvar(mc::CopiedUpvar { onceness: ast::Many, .. }) => {
326 Some(Rc::new(LpVar(id)))
329 mc::cat_upvar(ty::UpvarId {var_id: id, closure_expr_id: proc_id}, _) |
330 mc::cat_copied_upvar(mc::CopiedUpvar { upvar_id: id,
332 capturing_proc: proc_id }) => {
333 let upvar_id = ty::UpvarId{ var_id: id, closure_expr_id: proc_id };
334 Some(Rc::new(LpUpvar(upvar_id)))
337 mc::cat_deref(ref cmt_base, _, pk) => {
338 opt_loan_path(cmt_base).map(|lp| {
339 Rc::new(LpExtend(lp, cmt.mutbl, LpDeref(pk)))
343 mc::cat_interior(ref cmt_base, ik) => {
344 opt_loan_path(cmt_base).map(|lp| {
345 Rc::new(LpExtend(lp, cmt.mutbl, LpInterior(ik)))
349 mc::cat_downcast(ref cmt_base) |
350 mc::cat_discr(ref cmt_base, _) => {
351 opt_loan_path(cmt_base)
356 ///////////////////////////////////////////////////////////////////////////
359 // Errors that can occur
360 #[deriving(PartialEq)]
361 pub enum bckerr_code {
363 err_out_of_scope(ty::Region, ty::Region), // superscope, subscope
364 err_borrowed_pointer_too_short(ty::Region, ty::Region), // loan, ptr
367 // Combination of an error code and the categorization of the expression
369 #[deriving(PartialEq)]
370 pub struct BckError {
372 cause: euv::LoanCause,
377 pub enum AliasableViolationKind {
379 BorrowViolation(euv::LoanCause)
382 pub enum MovedValueUseKind {
387 ///////////////////////////////////////////////////////////////////////////
390 impl<'a, 'tcx> BorrowckCtxt<'a, 'tcx> {
391 pub fn is_subregion_of(&self, r_sub: ty::Region, r_sup: ty::Region)
393 self.tcx.region_maps.is_subregion_of(r_sub, r_sup)
396 pub fn is_subscope_of(&self, r_sub: ast::NodeId, r_sup: ast::NodeId)
398 self.tcx.region_maps.is_subscope_of(r_sub, r_sup)
401 pub fn mc(&self) -> mc::MemCategorizationContext<'a, ty::ctxt<'tcx>> {
402 mc::MemCategorizationContext::new(self.tcx)
405 pub fn cat_expr(&self, expr: &ast::Expr) -> mc::cmt {
406 match self.mc().cat_expr(expr) {
409 self.tcx.sess.span_bug(expr.span, "error in mem categorization");
414 pub fn cat_expr_unadjusted(&self, expr: &ast::Expr) -> mc::cmt {
415 match self.mc().cat_expr_unadjusted(expr) {
418 self.tcx.sess.span_bug(expr.span, "error in mem categorization");
423 pub fn cat_expr_autoderefd(&self,
425 adj: &ty::AutoAdjustment)
430 autoderefs: autoderefs, ..}) => {
431 self.mc().cat_expr_autoderefd(expr, autoderefs)
433 ty::AutoAddEnv(..) => {
435 self.mc().cat_expr_unadjusted(expr)
442 self.tcx.sess.span_bug(expr.span,
443 "error in mem categorization");
448 pub fn cat_def(&self,
454 match self.mc().cat_def(id, span, ty, def) {
457 self.tcx.sess.span_bug(span, "error in mem categorization");
462 pub fn cat_captured_var(&self,
463 closure_id: ast::NodeId,
467 // Create the cmt for the variable being borrowed, from the
468 // caller's perspective
469 let var_id = upvar_def.def_id().node;
470 let var_ty = ty::node_id_to_type(self.tcx, var_id);
471 self.cat_def(closure_id, closure_span, var_ty, upvar_def)
474 pub fn cat_discr(&self, cmt: mc::cmt, match_id: ast::NodeId) -> mc::cmt {
476 cat: mc::cat_discr(cmt.clone(), match_id),
477 mutbl: cmt.mutbl.inherit(),
482 pub fn cat_pattern(&self,
485 op: |mc::cmt, &ast::Pat|) {
486 let r = self.mc().cat_pattern(cmt, pat, |_,x,y| op(x,y));
490 pub fn report(&self, err: BckError) {
493 self.bckerr_to_string(&err).as_slice());
494 self.note_and_explain_bckerr(err);
497 pub fn report_use_of_moved_value(&self,
499 use_kind: MovedValueUseKind,
501 move: &move_data::Move,
502 moved_lp: &LoanPath) {
503 let verb = match use_kind {
505 MovedInCapture => "capture",
509 move_data::Declared => {
510 self.tcx.sess.span_err(
512 format!("{} of possibly uninitialized variable: `{}`",
514 self.loan_path_to_string(lp)).as_slice());
517 let partially = if lp == moved_lp {""} else {"partially "};
518 self.tcx.sess.span_err(
520 format!("{} of {}moved value: `{}`",
523 self.loan_path_to_string(lp)).as_slice());
528 move_data::Declared => {}
530 move_data::MoveExpr => {
531 let (expr_ty, expr_span) = match self.tcx.map.find(move.id) {
532 Some(ast_map::NodeExpr(expr)) => {
533 (ty::expr_ty_adjusted(self.tcx, &*expr), expr.span)
536 self.tcx.sess.bug(format!("MoveExpr({:?}) maps to \
542 let suggestion = move_suggestion(self.tcx, expr_ty,
543 "moved by default (use `copy` to override)");
544 self.tcx.sess.span_note(
546 format!("`{}` moved here because it has type `{}`, which is {}",
547 self.loan_path_to_string(moved_lp),
548 expr_ty.user_string(self.tcx),
549 suggestion).as_slice());
552 move_data::MovePat => {
553 let pat_ty = ty::node_id_to_type(self.tcx, move.id);
554 self.tcx.sess.span_note(self.tcx.map.span(move.id),
555 format!("`{}` moved here because it has type `{}`, \
556 which is moved by default (use `ref` to \
558 self.loan_path_to_string(moved_lp),
559 pat_ty.user_string(self.tcx)).as_slice());
562 move_data::Captured => {
563 let (expr_ty, expr_span) = match self.tcx.map.find(move.id) {
564 Some(ast_map::NodeExpr(expr)) => {
565 (ty::expr_ty_adjusted(self.tcx, &*expr), expr.span)
568 self.tcx.sess.bug(format!("Captured({:?}) maps to \
574 let suggestion = move_suggestion(self.tcx, expr_ty,
575 "moved by default (make a copy and \
576 capture that instead to override)");
577 self.tcx.sess.span_note(
579 format!("`{}` moved into closure environment here because it \
580 has type `{}`, which is {}",
581 self.loan_path_to_string(moved_lp),
582 expr_ty.user_string(self.tcx),
583 suggestion).as_slice());
587 fn move_suggestion(tcx: &ty::ctxt, ty: ty::t, default_msg: &'static str)
589 match ty::get(ty).sty {
590 ty::ty_closure(box ty::ClosureTy {
591 store: ty::RegionTraitStore(..),
594 "a non-copyable stack closure (capture it in a new closure, \
595 e.g. `|x| f(x)`, to override)",
596 _ if ty::type_moves_by_default(tcx, ty) =>
597 "non-copyable (perhaps you meant to use clone()?)",
603 pub fn report_reassigned_immutable_variable(&self,
607 &move_data::Assignment) {
608 self.tcx.sess.span_err(
610 format!("re-assignment of immutable variable `{}`",
611 self.loan_path_to_string(lp)).as_slice());
612 self.tcx.sess.span_note(assign.span, "prior assignment occurs here");
615 pub fn span_err(&self, s: Span, m: &str) {
616 self.tcx.sess.span_err(s, m);
619 pub fn span_note(&self, s: Span, m: &str) {
620 self.tcx.sess.span_note(s, m);
623 pub fn span_end_note(&self, s: Span, m: &str) {
624 self.tcx.sess.span_end_note(s, m);
627 pub fn bckerr_to_string(&self, err: &BckError) -> String {
630 let descr = match opt_loan_path(&err.cmt) {
633 err.cmt.mutbl.to_user_str(),
634 self.cmt_to_string(&*err.cmt))
637 format!("{} {} `{}`",
638 err.cmt.mutbl.to_user_str(),
639 self.cmt_to_string(&*err.cmt),
640 self.loan_path_to_string(&*lp))
645 euv::ClosureCapture(_) => {
646 format!("closure cannot assign to {}", descr)
648 euv::OverloadedOperator |
653 format!("cannot borrow {} as mutable", descr)
655 euv::ClosureInvocation => {
656 self.tcx.sess.span_bug(err.span,
657 "err_mutbl with a closure invocation");
661 err_out_of_scope(..) => {
662 let msg = match opt_loan_path(&err.cmt) {
663 None => "borrowed value".to_string(),
665 format!("`{}`", self.loan_path_to_string(&*lp))
668 format!("{} does not live long enough", msg)
670 err_borrowed_pointer_too_short(..) => {
671 let descr = match opt_loan_path(&err.cmt) {
673 format!("`{}`", self.loan_path_to_string(&*lp))
675 None => self.cmt_to_string(&*err.cmt),
678 format!("lifetime of {} is too short to guarantee \
679 its contents can be safely reborrowed",
685 pub fn report_aliasability_violation(&self,
687 kind: AliasableViolationKind,
688 cause: mc::AliasableReason) {
689 let prefix = match kind {
690 MutabilityViolation => {
691 "cannot assign to data"
693 BorrowViolation(euv::ClosureCapture(_)) => {
694 // I don't think we can get aliasability violations
695 // with closure captures, so no need to come up with a
696 // good error message. The reason this cannot happen
697 // is because we only capture local variables in
698 // closures, and those are never aliasable.
699 self.tcx.sess.span_bug(
701 "aliasability violation with closure");
703 BorrowViolation(euv::OverloadedOperator) |
704 BorrowViolation(euv::AddrOf) |
705 BorrowViolation(euv::AutoRef) |
706 BorrowViolation(euv::RefBinding) => {
707 "cannot borrow data mutably"
710 BorrowViolation(euv::ClosureInvocation) => {
714 BorrowViolation(euv::ForLoop) => {
720 mc::AliasableOther => {
721 self.tcx.sess.span_err(
723 format!("{} in an aliasable location",
726 mc::AliasableStatic(..) |
727 mc::AliasableStaticMut(..) => {
728 self.tcx.sess.span_err(
730 format!("{} in a static location", prefix).as_slice());
732 mc::AliasableManaged => {
733 self.tcx.sess.span_err(
735 format!("{} in a `@` pointer", prefix).as_slice());
737 mc::AliasableBorrowed => {
738 self.tcx.sess.span_err(
740 format!("{} in a `&` reference", prefix).as_slice());
745 pub fn note_and_explain_bckerr(&self, err: BckError) {
750 err_out_of_scope(super_scope, sub_scope) => {
751 note_and_explain_region(
753 "reference must be valid for ",
756 let suggestion = if is_statement_scope(self.tcx, super_scope) {
757 "; consider using a `let` binding to increase its lifetime"
761 note_and_explain_region(
763 "...but borrowed value is only valid for ",
768 err_borrowed_pointer_too_short(loan_scope, ptr_scope) => {
769 let descr = match opt_loan_path(&err.cmt) {
771 format!("`{}`", self.loan_path_to_string(&*lp))
773 None => self.cmt_to_string(&*err.cmt),
775 note_and_explain_region(
777 format!("{} would have to be valid for ",
781 note_and_explain_region(
783 format!("...but {} is only valid for ", descr).as_slice(),
790 pub fn append_loan_path_to_string(&self,
791 loan_path: &LoanPath,
794 LpUpvar(ty::UpvarId{ var_id: id, closure_expr_id: _ }) |
796 out.push_str(ty::local_var_name_str(self.tcx, id).get());
799 LpExtend(ref lp_base, _, LpInterior(mc::InteriorField(fname))) => {
800 self.append_autoderefd_loan_path_to_string(&**lp_base, out);
802 mc::NamedField(fname) => {
804 out.push_str(token::get_name(fname).get());
806 mc::PositionalField(idx) => {
808 out.push_str(idx.to_string().as_slice());
813 LpExtend(ref lp_base, _, LpInterior(mc::InteriorElement(_))) => {
814 self.append_autoderefd_loan_path_to_string(&**lp_base, out);
815 out.push_str("[..]");
818 LpExtend(ref lp_base, _, LpDeref(_)) => {
820 self.append_loan_path_to_string(&**lp_base, out);
825 pub fn append_autoderefd_loan_path_to_string(&self,
826 loan_path: &LoanPath,
829 LpExtend(ref lp_base, _, LpDeref(_)) => {
830 // For a path like `(*x).f` or `(*x)[3]`, autoderef
831 // rules would normally allow users to omit the `*x`.
832 // So just serialize such paths to `x.f` or x[3]` respectively.
833 self.append_autoderefd_loan_path_to_string(&**lp_base, out)
836 LpVar(..) | LpUpvar(..) | LpExtend(_, _, LpInterior(..)) => {
837 self.append_loan_path_to_string(loan_path, out)
842 pub fn loan_path_to_string(&self, loan_path: &LoanPath) -> String {
843 let mut result = String::new();
844 self.append_loan_path_to_string(loan_path, &mut result);
848 pub fn cmt_to_string(&self, cmt: &mc::cmt_) -> String {
849 self.mc().cmt_to_string(cmt)
853 fn is_statement_scope(tcx: &ty::ctxt, region: ty::Region) -> bool {
855 ty::ReScope(node_id) => {
856 match tcx.map.find(node_id) {
857 Some(ast_map::NodeStmt(_)) => true,
865 impl BitwiseOperator for LoanDataFlowOperator {
867 fn join(&self, succ: uint, pred: uint) -> uint {
868 succ | pred // loans from both preds are in scope
872 impl DataFlowOperator for LoanDataFlowOperator {
874 fn initial_value(&self) -> bool {
875 false // no loans in scope by default
880 fn repr(&self, tcx: &ty::ctxt) -> String {
881 format!("Loan_{:?}({}, {:?}, {:?}-{:?}, {})",
883 self.loan_path.repr(tcx),
887 self.restricted_paths.repr(tcx))
891 impl Repr for LoanPath {
892 fn repr(&self, tcx: &ty::ctxt) -> String {
895 format!("$({})", tcx.map.node_to_string(id))
898 &LpUpvar(ty::UpvarId{ var_id, closure_expr_id }) => {
899 let s = tcx.map.node_to_string(var_id);
900 format!("$({} captured by id={})", s, closure_expr_id)
903 &LpExtend(ref lp, _, LpDeref(_)) => {
904 format!("{}.*", lp.repr(tcx))
907 &LpExtend(ref lp, _, LpInterior(ref interior)) => {
908 format!("{}.{}", lp.repr(tcx), interior.repr(tcx))