src/librustc/middle/borrowck/mod.rs

   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.
   4 //
   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.
  10
  11 /*! See doc.rs for a thorough explanation of the borrow checker */
  12
  13 #![allow(non_camel_case_types)]
  14
  15 use middle::cfg;
  16 use middle::dataflow::DataFlowContext;
  17 use middle::dataflow::BitwiseOperator;
  18 use middle::dataflow::DataFlowOperator;
  19 use middle::def;
  20 use middle::expr_use_visitor as euv;
  21 use middle::mem_categorization as mc;
  22 use middle::ty;
  23 use util::ppaux::{note_and_explain_region, Repr, UserString};
  24
  25 use std::rc::Rc;
  26 use std::string::String;
  27 use syntax::ast;
  28 use syntax::ast_map;
  29 use syntax::ast_map::blocks::{FnLikeNode, FnParts};
  30 use syntax::ast_util;
  31 use syntax::codemap::Span;
  32 use syntax::parse::token;
  33 use syntax::visit;
  34 use syntax::visit::{Visitor, FnKind};
  35 use syntax::ast::{FnDecl, Block, NodeId};
  36
  37 macro_rules! if_ok(
  38     ($inp: expr) => (
  39         match $inp {
  40             Ok(v) => { v }
  41             Err(e) => { return Err(e); }
  42         }
  43     )
  44 )
  45
  46 pub mod doc;
  47
  48 pub mod check_loans;
  49
  50 pub mod gather_loans;
  51
  52 pub mod graphviz;
  53
  54 pub mod move_data;
  55
  56 #[deriving(Clone)]
  57 pub struct LoanDataFlowOperator;
  58
  59 pub type LoanDataFlow<'a, 'tcx> = DataFlowContext<'a, 'tcx, LoanDataFlowOperator>;
  60
  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);
  65     }
  66
  67     fn visit_item(&mut self, item: &ast::Item) {
  68         borrowck_item(self, item);
  69     }
  70 }
  71
  72 pub fn check_crate(tcx: &ty::ctxt) {
  73     let mut bccx = BorrowckCtxt {
  74         tcx: tcx,
  75         stats: BorrowStats {
  76             loaned_paths_same: 0,
  77             loaned_paths_imm: 0,
  78             stable_paths: 0,
  79             guaranteed_paths: 0
  80         }
  81     };
  82
  83     visit::walk_crate(&mut bccx, tcx.map.krate());
  84
  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));
  95     }
  96
  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)
 101     }
 102 }
 103
 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.
 109     match item.node {
 110         ast::ItemStatic(_, _, ref ex) => {
 111             gather_loans::gather_loans_in_static_initializer(this, &**ex);
 112         }
 113         _ => {
 114             visit::walk_item(this, item);
 115         }
 116     }
 117 }
 118
 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>,
 124 }
 125
 126 fn borrowck_fn(this: &mut BorrowckCtxt,
 127                fk: FnKind,
 128                decl: &ast::FnDecl,
 129                body: &ast::Block,
 130                sp: Span,
 131                id: ast::NodeId) {
 132     debug!("borrowck_fn(id={})", id);
 133     let cfg = cfg::CFG::new(this.tcx, body);
 134     let AnalysisData { all_loans,
 135                        loans: loan_dfcx,
 136                        move_data:flowed_moves } =
 137         build_borrowck_dataflow_data(this, fk, decl, &cfg, body, sp, id);
 138
 139     check_loans::check_loans(this, &loan_dfcx, flowed_moves,
 140                              all_loans.as_slice(), decl, body);
 141
 142     visit::walk_fn(this, fk, decl, body, sp);
 143 }
 144
 145 fn build_borrowck_dataflow_data<'a, 'tcx>(this: &mut BorrowckCtxt<'a, 'tcx>,
 146                                           fk: FnKind,
 147                                           decl: &ast::FnDecl,
 148                                           cfg: &cfg::CFG,
 149                                           body: &ast::Block,
 150                                           sp: Span,
 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);
 156
 157     let mut loan_dfcx =
 158         DataFlowContext::new(this.tcx,
 159                              "borrowck",
 160                              Some(decl),
 161                              cfg,
 162                              LoanDataFlowOperator,
 163                              id_range,
 164                              all_loans.len());
 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);
 168     }
 169     loan_dfcx.add_kills_from_flow_exits(cfg);
 170     loan_dfcx.propagate(cfg, body);
 171
 172     let flowed_moves = move_data::FlowedMoveData::new(move_data,
 173                                                       this.tcx,
 174                                                       cfg,
 175                                                       id_range,
 176                                                       decl,
 177                                                       body);
 178
 179     AnalysisData { all_loans: all_loans,
 180                    loans: loan_dfcx,
 181                    move_data:flowed_moves }
 182 }
 183
 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,
 189 }
 190
 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 }
 195     }
 196 }
 197
 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>) {
 203
 204     let mut bccx = BorrowckCtxt {
 205         tcx: tcx,
 206         stats: BorrowStats {
 207             loaned_paths_same: 0,
 208             loaned_paths_imm: 0,
 209             stable_paths: 0,
 210             guaranteed_paths: 0
 211         }
 212     };
 213
 214     let p = input.fn_parts;
 215
 216     let dataflow_data = build_borrowck_dataflow_data(&mut bccx,
 217                                                      p.kind,
 218                                                      &*p.decl,
 219                                                      input.cfg,
 220                                                      &*p.body,
 221                                                      p.span,
 222                                                      p.id);
 223
 224     (bccx, dataflow_data)
 225 }
 226
 227 // ----------------------------------------------------------------------
 228 // Type definitions
 229
 230 pub struct BorrowckCtxt<'a, 'tcx: 'a> {
 231     tcx: &'a ty::ctxt<'tcx>,
 232
 233     // Statistics:
 234     stats: BorrowStats
 235 }
 236
 237 struct BorrowStats {
 238     loaned_paths_same: uint,
 239     loaned_paths_imm: uint,
 240     stable_paths: uint,
 241     guaranteed_paths: uint
 242 }
 243
 244 pub type BckResult<T> = Result<T, BckError>;
 245
 246 #[deriving(PartialEq)]
 247 pub enum PartialTotal {
 248     Partial,   // Loan affects some portion
 249     Total      // Loan affects entire path
 250 }
 251
 252 ///////////////////////////////////////////////////////////////////////////
 253 // Loans and loan paths
 254
 255 /// Record of a loan that was issued.
 256 pub struct Loan {
 257     index: uint,
 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,
 263     span: Span,
 264     cause: euv::LoanCause,
 265 }
 266
 267 impl Loan {
 268     pub fn loan_path(&self) -> Rc<LoanPath> {
 269         self.loan_path.clone()
 270     }
 271 }
 272
 273 #[deriving(PartialEq, Eq, Hash)]
 274 pub enum LoanPath {
 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)
 278 }
 279
 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
 284 }
 285
 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)
 294         },
 295         _ => fail!("encountered non-expr id: {}", closure_id)
 296     }
 297 }
 298
 299 impl LoanPath {
 300     pub fn kill_scope(&self, tcx: &ty::ctxt) -> ast::NodeId {
 301         match *self {
 302             LpVar(local_id) => tcx.region_maps.var_scope(local_id),
 303             LpUpvar(upvar_id) =>
 304                 closure_to_block(upvar_id.closure_expr_id, tcx),
 305             LpExtend(ref base, _, _) => base.kill_scope(tcx),
 306         }
 307     }
 308 }
 309
 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.
 316
 317     match cmt.cat {
 318         mc::cat_rvalue(..) |
 319         mc::cat_static_item |
 320         mc::cat_copied_upvar(mc::CopiedUpvar { onceness: ast::Many, .. }) => {
 321             None
 322         }
 323
 324         mc::cat_local(id) => {
 325             Some(Rc::new(LpVar(id)))
 326         }
 327
 328         mc::cat_upvar(ty::UpvarId {var_id: id, closure_expr_id: proc_id}, _) |
 329         mc::cat_copied_upvar(mc::CopiedUpvar { upvar_id: id,
 330                                                onceness: _,
 331                                                capturing_proc: proc_id }) => {
 332             let upvar_id = ty::UpvarId{ var_id: id, closure_expr_id: proc_id };
 333             Some(Rc::new(LpUpvar(upvar_id)))
 334         }
 335
 336         mc::cat_deref(ref cmt_base, _, pk) => {
 337             opt_loan_path(cmt_base).map(|lp| {
 338                 Rc::new(LpExtend(lp, cmt.mutbl, LpDeref(pk)))
 339             })
 340         }
 341
 342         mc::cat_interior(ref cmt_base, ik) => {
 343             opt_loan_path(cmt_base).map(|lp| {
 344                 Rc::new(LpExtend(lp, cmt.mutbl, LpInterior(ik)))
 345             })
 346         }
 347
 348         mc::cat_downcast(ref cmt_base) |
 349         mc::cat_discr(ref cmt_base, _) => {
 350             opt_loan_path(cmt_base)
 351         }
 352     }
 353 }
 354
 355 ///////////////////////////////////////////////////////////////////////////
 356 // Errors
 357
 358 // Errors that can occur
 359 #[deriving(PartialEq)]
 360 pub enum bckerr_code {
 361     err_mutbl,
 362     err_out_of_scope(ty::Region, ty::Region), // superscope, subscope
 363     err_borrowed_pointer_too_short(ty::Region, ty::Region), // loan, ptr
 364 }
 365
 366 // Combination of an error code and the categorization of the expression
 367 // that caused it
 368 #[deriving(PartialEq)]
 369 pub struct BckError {
 370     span: Span,
 371     cause: euv::LoanCause,
 372     cmt: mc::cmt,
 373     code: bckerr_code
 374 }
 375
 376 pub enum AliasableViolationKind {
 377     MutabilityViolation,
 378     BorrowViolation(euv::LoanCause)
 379 }
 380
 381 pub enum MovedValueUseKind {
 382     MovedInUse,
 383     MovedInCapture,
 384 }
 385
 386 ///////////////////////////////////////////////////////////////////////////
 387 // Misc
 388
 389 impl<'a, 'tcx> BorrowckCtxt<'a, 'tcx> {
 390     pub fn is_subregion_of(&self, r_sub: ty::Region, r_sup: ty::Region)
 391                            -> bool {
 392         self.tcx.region_maps.is_subregion_of(r_sub, r_sup)
 393     }
 394
 395     pub fn is_subscope_of(&self, r_sub: ast::NodeId, r_sup: ast::NodeId)
 396                           -> bool {
 397         self.tcx.region_maps.is_subscope_of(r_sub, r_sup)
 398     }
 399
 400     pub fn mc(&self) -> mc::MemCategorizationContext<'a, ty::ctxt<'tcx>> {
 401         mc::MemCategorizationContext::new(self.tcx)
 402     }
 403
 404     pub fn cat_expr(&self, expr: &ast::Expr) -> mc::cmt {
 405         match self.mc().cat_expr(expr) {
 406             Ok(c) => c,
 407             Err(()) => {
 408                 self.tcx.sess.span_bug(expr.span, "error in mem categorization");
 409             }
 410         }
 411     }
 412
 413     pub fn cat_expr_unadjusted(&self, expr: &ast::Expr) -> mc::cmt {
 414         match self.mc().cat_expr_unadjusted(expr) {
 415             Ok(c) => c,
 416             Err(()) => {
 417                 self.tcx.sess.span_bug(expr.span, "error in mem categorization");
 418             }
 419         }
 420     }
 421
 422     pub fn cat_expr_autoderefd(&self,
 423                                expr: &ast::Expr,
 424                                adj: &ty::AutoAdjustment)
 425                                -> mc::cmt {
 426         let r = match *adj {
 427             ty::AutoDerefRef(
 428                 ty::AutoDerefRef {
 429                     autoderefs: autoderefs, ..}) => {
 430                 self.mc().cat_expr_autoderefd(expr, autoderefs)
 431             }
 432             ty::AutoAddEnv(..) => {
 433                 // no autoderefs
 434                 self.mc().cat_expr_unadjusted(expr)
 435             }
 436         };
 437
 438         match r {
 439             Ok(c) => c,
 440             Err(()) => {
 441                 self.tcx.sess.span_bug(expr.span,
 442                                        "error in mem categorization");
 443             }
 444         }
 445     }
 446
 447     pub fn cat_def(&self,
 448                    id: ast::NodeId,
 449                    span: Span,
 450                    ty: ty::t,
 451                    def: def::Def)
 452                    -> mc::cmt {
 453         match self.mc().cat_def(id, span, ty, def) {
 454             Ok(c) => c,
 455             Err(()) => {
 456                 self.tcx.sess.span_bug(span, "error in mem categorization");
 457             }
 458         }
 459     }
 460
 461     pub fn cat_captured_var(&self,
 462                             closure_id: ast::NodeId,
 463                             closure_span: Span,
 464                             upvar_def: def::Def)
 465                             -> mc::cmt {
 466         // Create the cmt for the variable being borrowed, from the
 467         // caller's perspective
 468         let var_id = upvar_def.def_id().node;
 469         let var_ty = ty::node_id_to_type(self.tcx, var_id);
 470         self.cat_def(closure_id, closure_span, var_ty, upvar_def)
 471     }
 472
 473     pub fn cat_discr(&self, cmt: mc::cmt, match_id: ast::NodeId) -> mc::cmt {
 474         Rc::new(mc::cmt_ {
 475             cat: mc::cat_discr(cmt.clone(), match_id),
 476             mutbl: cmt.mutbl.inherit(),
 477             ..*cmt
 478         })
 479     }
 480
 481     pub fn cat_pattern(&self,
 482                        cmt: mc::cmt,
 483                        pat: &ast::Pat,
 484                        op: |mc::cmt, &ast::Pat|) {
 485         let r = self.mc().cat_pattern(cmt, pat, |_,x,y| op(x,y));
 486         assert!(r.is_ok());
 487     }
 488
 489     pub fn report(&self, err: BckError) {
 490         self.span_err(
 491             err.span,
 492             self.bckerr_to_string(&err).as_slice());
 493         self.note_and_explain_bckerr(err);
 494     }
 495
 496     pub fn report_use_of_moved_value(&self,
 497                                      use_span: Span,
 498                                      use_kind: MovedValueUseKind,
 499                                      lp: &LoanPath,
 500                                      move: &move_data::Move,
 501                                      moved_lp: &LoanPath) {
 502         let verb = match use_kind {
 503             MovedInUse => "use",
 504             MovedInCapture => "capture",
 505         };
 506
 507         match move.kind {
 508             move_data::Declared => {
 509                 self.tcx.sess.span_err(
 510                     use_span,
 511                     format!("{} of possibly uninitialized variable: `{}`",
 512                             verb,
 513                             self.loan_path_to_string(lp)).as_slice());
 514             }
 515             _ => {
 516                 let partially = if lp == moved_lp {""} else {"partially "};
 517                 self.tcx.sess.span_err(
 518                     use_span,
 519                     format!("{} of {}moved value: `{}`",
 520                             verb,
 521                             partially,
 522                             self.loan_path_to_string(lp)).as_slice());
 523             }
 524         }
 525
 526         match move.kind {
 527             move_data::Declared => {}
 528
 529             move_data::MoveExpr => {
 530                 let (expr_ty, expr_span) = match self.tcx.map.find(move.id) {
 531                     Some(ast_map::NodeExpr(expr)) => {
 532                         (ty::expr_ty_adjusted(self.tcx, &*expr), expr.span)
 533                     }
 534                     r => {
 535                         self.tcx.sess.bug(format!("MoveExpr({:?}) maps to \
 536                                                    {:?}, not Expr",
 537                                                   move.id,
 538                                                   r).as_slice())
 539                     }
 540                 };
 541                 let suggestion = move_suggestion(self.tcx, expr_ty,
 542                         "moved by default (use `copy` to override)");
 543                 self.tcx.sess.span_note(
 544                     expr_span,
 545                     format!("`{}` moved here because it has type `{}`, which is {}",
 546                             self.loan_path_to_string(moved_lp),
 547                             expr_ty.user_string(self.tcx),
 548                             suggestion).as_slice());
 549             }
 550
 551             move_data::MovePat => {
 552                 let pat_ty = ty::node_id_to_type(self.tcx, move.id);
 553                 self.tcx.sess.span_note(self.tcx.map.span(move.id),
 554                     format!("`{}` moved here because it has type `{}`, \
 555                              which is moved by default (use `ref` to \
 556                              override)",
 557                             self.loan_path_to_string(moved_lp),
 558                             pat_ty.user_string(self.tcx)).as_slice());
 559             }
 560
 561             move_data::Captured => {
 562                 let (expr_ty, expr_span) = match self.tcx.map.find(move.id) {
 563                     Some(ast_map::NodeExpr(expr)) => {
 564                         (ty::expr_ty_adjusted(self.tcx, &*expr), expr.span)
 565                     }
 566                     r => {
 567                         self.tcx.sess.bug(format!("Captured({:?}) maps to \
 568                                                    {:?}, not Expr",
 569                                                   move.id,
 570                                                   r).as_slice())
 571                     }
 572                 };
 573                 let suggestion = move_suggestion(self.tcx, expr_ty,
 574                         "moved by default (make a copy and \
 575                          capture that instead to override)");
 576                 self.tcx.sess.span_note(
 577                     expr_span,
 578                     format!("`{}` moved into closure environment here because it \
 579                             has type `{}`, which is {}",
 580                             self.loan_path_to_string(moved_lp),
 581                             expr_ty.user_string(self.tcx),
 582                             suggestion).as_slice());
 583             }
 584         }
 585
 586         fn move_suggestion(tcx: &ty::ctxt, ty: ty::t, default_msg: &'static str)
 587                           -> &'static str {
 588             match ty::get(ty).sty {
 589                 ty::ty_closure(box ty::ClosureTy {
 590                         store: ty::RegionTraitStore(..),
 591                         ..
 592                     }) =>
 593                     "a non-copyable stack closure (capture it in a new closure, \
 594                      e.g. `|x| f(x)`, to override)",
 595                 _ if ty::type_moves_by_default(tcx, ty) =>
 596                     "non-copyable (perhaps you meant to use clone()?)",
 597                 _ => default_msg,
 598             }
 599         }
 600     }
 601
 602     pub fn report_reassigned_immutable_variable(&self,
 603                                                 span: Span,
 604                                                 lp: &LoanPath,
 605                                                 assign:
 606                                                 &move_data::Assignment) {
 607         self.tcx.sess.span_err(
 608             span,
 609             format!("re-assignment of immutable variable `{}`",
 610                     self.loan_path_to_string(lp)).as_slice());
 611         self.tcx.sess.span_note(assign.span, "prior assignment occurs here");
 612     }
 613
 614     pub fn span_err(&self, s: Span, m: &str) {
 615         self.tcx.sess.span_err(s, m);
 616     }
 617
 618     pub fn span_note(&self, s: Span, m: &str) {
 619         self.tcx.sess.span_note(s, m);
 620     }
 621
 622     pub fn span_end_note(&self, s: Span, m: &str) {
 623         self.tcx.sess.span_end_note(s, m);
 624     }
 625
 626     pub fn bckerr_to_string(&self, err: &BckError) -> String {
 627         match err.code {
 628             err_mutbl => {
 629                 let descr = match opt_loan_path(&err.cmt) {
 630                     None => {
 631                         format!("{} {}",
 632                                 err.cmt.mutbl.to_user_str(),
 633                                 self.cmt_to_string(&*err.cmt))
 634                     }
 635                     Some(lp) => {
 636                         format!("{} {} `{}`",
 637                                 err.cmt.mutbl.to_user_str(),
 638                                 self.cmt_to_string(&*err.cmt),
 639                                 self.loan_path_to_string(&*lp))
 640                     }
 641                 };
 642
 643                 match err.cause {
 644                     euv::ClosureCapture(_) => {
 645                         format!("closure cannot assign to {}", descr)
 646                     }
 647                     euv::OverloadedOperator |
 648                     euv::AddrOf |
 649                     euv::RefBinding |
 650                     euv::AutoRef |
 651                     euv::ForLoop => {
 652                         format!("cannot borrow {} as mutable", descr)
 653                     }
 654                     euv::ClosureInvocation => {
 655                         self.tcx.sess.span_bug(err.span,
 656                             "err_mutbl with a closure invocation");
 657                     }
 658                 }
 659             }
 660             err_out_of_scope(..) => {
 661                 let msg = match opt_loan_path(&err.cmt) {
 662                     None => "borrowed value".to_string(),
 663                     Some(lp) => {
 664                         format!("`{}`", self.loan_path_to_string(&*lp))
 665                     }
 666                 };
 667                 format!("{} does not live long enough", msg)
 668             }
 669             err_borrowed_pointer_too_short(..) => {
 670                 let descr = match opt_loan_path(&err.cmt) {
 671                     Some(lp) => {
 672                         format!("`{}`", self.loan_path_to_string(&*lp))
 673                     }
 674                     None => self.cmt_to_string(&*err.cmt),
 675                 };
 676
 677                 format!("lifetime of {} is too short to guarantee \
 678                                 its contents can be safely reborrowed",
 679                                descr)
 680             }
 681         }
 682     }
 683
 684     pub fn report_aliasability_violation(&self,
 685                                          span: Span,
 686                                          kind: AliasableViolationKind,
 687                                          cause: mc::AliasableReason) {
 688         let prefix = match kind {
 689             MutabilityViolation => {
 690                 "cannot assign to data"
 691             }
 692             BorrowViolation(euv::ClosureCapture(_)) => {
 693                 // I don't think we can get aliasability violations
 694                 // with closure captures, so no need to come up with a
 695                 // good error message. The reason this cannot happen
 696                 // is because we only capture local variables in
 697                 // closures, and those are never aliasable.
 698                 self.tcx.sess.span_bug(
 699                     span,
 700                     "aliasability violation with closure");
 701             }
 702             BorrowViolation(euv::OverloadedOperator) |
 703             BorrowViolation(euv::AddrOf) |
 704             BorrowViolation(euv::AutoRef) |
 705             BorrowViolation(euv::RefBinding) => {
 706                 "cannot borrow data mutably"
 707             }
 708
 709             BorrowViolation(euv::ClosureInvocation) => {
 710                 "closure invocation"
 711             }
 712
 713             BorrowViolation(euv::ForLoop) => {
 714                 "`for` loop"
 715             }
 716         };
 717
 718         match cause {
 719             mc::AliasableOther => {
 720                 self.tcx.sess.span_err(
 721                     span,
 722                     format!("{} in an aliasable location",
 723                              prefix).as_slice());
 724             }
 725             mc::AliasableStatic(..) |
 726             mc::AliasableStaticMut(..) => {
 727                 self.tcx.sess.span_err(
 728                     span,
 729                     format!("{} in a static location", prefix).as_slice());
 730             }
 731             mc::AliasableManaged => {
 732                 self.tcx.sess.span_err(
 733                     span,
 734                     format!("{} in a `@` pointer", prefix).as_slice());
 735             }
 736             mc::AliasableBorrowed => {
 737                 self.tcx.sess.span_err(
 738                     span,
 739                     format!("{} in a `&` reference", prefix).as_slice());
 740             }
 741         }
 742     }
 743
 744     pub fn note_and_explain_bckerr(&self, err: BckError) {
 745         let code = err.code;
 746         match code {
 747             err_mutbl(..) => { }
 748
 749             err_out_of_scope(super_scope, sub_scope) => {
 750                 note_and_explain_region(
 751                     self.tcx,
 752                     "reference must be valid for ",
 753                     sub_scope,
 754                     "...");
 755                 let suggestion = if is_statement_scope(self.tcx, super_scope) {
 756                     "; consider using a `let` binding to increase its lifetime"
 757                 } else {
 758                     ""
 759                 };
 760                 note_and_explain_region(
 761                     self.tcx,
 762                     "...but borrowed value is only valid for ",
 763                     super_scope,
 764                     suggestion);
 765             }
 766
 767             err_borrowed_pointer_too_short(loan_scope, ptr_scope) => {
 768                 let descr = match opt_loan_path(&err.cmt) {
 769                     Some(lp) => {
 770                         format!("`{}`", self.loan_path_to_string(&*lp))
 771                     }
 772                     None => self.cmt_to_string(&*err.cmt),
 773                 };
 774                 note_and_explain_region(
 775                     self.tcx,
 776                     format!("{} would have to be valid for ",
 777                             descr).as_slice(),
 778                     loan_scope,
 779                     "...");
 780                 note_and_explain_region(
 781                     self.tcx,
 782                     format!("...but {} is only valid for ", descr).as_slice(),
 783                     ptr_scope,
 784                     "");
 785             }
 786         }
 787     }
 788
 789     pub fn append_loan_path_to_string(&self,
 790                                    loan_path: &LoanPath,
 791                                    out: &mut String) {
 792         match *loan_path {
 793             LpUpvar(ty::UpvarId{ var_id: id, closure_expr_id: _ }) |
 794             LpVar(id) => {
 795                 out.push_str(ty::local_var_name_str(self.tcx, id).get());
 796             }
 797
 798             LpExtend(ref lp_base, _, LpInterior(mc::InteriorField(fname))) => {
 799                 self.append_autoderefd_loan_path_to_string(&**lp_base, out);
 800                 match fname {
 801                     mc::NamedField(fname) => {
 802                         out.push_char('.');
 803                         out.push_str(token::get_name(fname).get());
 804                     }
 805                     mc::PositionalField(idx) => {
 806                         out.push_char('.');
 807                         out.push_str(idx.to_string().as_slice());
 808                     }
 809                 }
 810             }
 811
 812             LpExtend(ref lp_base, _, LpInterior(mc::InteriorElement(_))) => {
 813                 self.append_autoderefd_loan_path_to_string(&**lp_base, out);
 814                 out.push_str("[..]");
 815             }
 816
 817             LpExtend(ref lp_base, _, LpDeref(_)) => {
 818                 out.push_char('*');
 819                 self.append_loan_path_to_string(&**lp_base, out);
 820             }
 821         }
 822     }
 823
 824     pub fn append_autoderefd_loan_path_to_string(&self,
 825                                               loan_path: &LoanPath,
 826                                               out: &mut String) {
 827         match *loan_path {
 828             LpExtend(ref lp_base, _, LpDeref(_)) => {
 829                 // For a path like `(*x).f` or `(*x)[3]`, autoderef
 830                 // rules would normally allow users to omit the `*x`.
 831                 // So just serialize such paths to `x.f` or x[3]` respectively.
 832                 self.append_autoderefd_loan_path_to_string(&**lp_base, out)
 833             }
 834
 835             LpVar(..) | LpUpvar(..) | LpExtend(_, _, LpInterior(..)) => {
 836                 self.append_loan_path_to_string(loan_path, out)
 837             }
 838         }
 839     }
 840
 841     pub fn loan_path_to_string(&self, loan_path: &LoanPath) -> String {
 842         let mut result = String::new();
 843         self.append_loan_path_to_string(loan_path, &mut result);
 844         result
 845     }
 846
 847     pub fn cmt_to_string(&self, cmt: &mc::cmt_) -> String {
 848         self.mc().cmt_to_string(cmt)
 849     }
 850 }
 851
 852 fn is_statement_scope(tcx: &ty::ctxt, region: ty::Region) -> bool {
 853      match region {
 854          ty::ReScope(node_id) => {
 855              match tcx.map.find(node_id) {
 856                  Some(ast_map::NodeStmt(_)) => true,
 857                  _ => false
 858              }
 859          }
 860          _ => false
 861      }
 862 }
 863
 864 impl BitwiseOperator for LoanDataFlowOperator {
 865     #[inline]
 866     fn join(&self, succ: uint, pred: uint) -> uint {
 867         succ | pred // loans from both preds are in scope
 868     }
 869 }
 870
 871 impl DataFlowOperator for LoanDataFlowOperator {
 872     #[inline]
 873     fn initial_value(&self) -> bool {
 874         false // no loans in scope by default
 875     }
 876 }
 877
 878 impl Repr for Loan {
 879     fn repr(&self, tcx: &ty::ctxt) -> String {
 880         format!("Loan_{:?}({}, {:?}, {:?}-{:?}, {})",
 881                  self.index,
 882                  self.loan_path.repr(tcx),
 883                  self.kind,
 884                  self.gen_scope,
 885                  self.kill_scope,
 886                  self.restricted_paths.repr(tcx))
 887     }
 888 }
 889
 890 impl Repr for LoanPath {
 891     fn repr(&self, tcx: &ty::ctxt) -> String {
 892         match self {
 893             &LpVar(id) => {
 894                 format!("$({})", tcx.map.node_to_string(id))
 895             }
 896
 897             &LpUpvar(ty::UpvarId{ var_id, closure_expr_id }) => {
 898                 let s = tcx.map.node_to_string(var_id);
 899                 format!("$({} captured by id={})", s, closure_expr_id)
 900             }
 901
 902             &LpExtend(ref lp, _, LpDeref(_)) => {
 903                 format!("{}.*", lp.repr(tcx))
 904             }
 905
 906             &LpExtend(ref lp, _, LpInterior(ref interior)) => {
 907                 format!("{}.{}", lp.repr(tcx), interior.repr(tcx))
 908             }
 909         }
 910     }
 911 }