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         mc::cat_arg(id) => {
 326             Some(Rc::new(LpVar(id)))
 327         }
 328
 329         mc::cat_upvar(ty::UpvarId {var_id: id, closure_expr_id: proc_id}, _) |
 330         mc::cat_copied_upvar(mc::CopiedUpvar { upvar_id: id,
 331                                                onceness: _,
 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)))
 335         }
 336
 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)))
 340             })
 341         }
 342
 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)))
 346             })
 347         }
 348
 349         mc::cat_downcast(ref cmt_base) |
 350         mc::cat_discr(ref cmt_base, _) => {
 351             opt_loan_path(cmt_base)
 352         }
 353     }
 354 }
 355
 356 ///////////////////////////////////////////////////////////////////////////
 357 // Errors
 358
 359 // Errors that can occur
 360 #[deriving(PartialEq)]
 361 pub enum bckerr_code {
 362     err_mutbl,
 363     err_out_of_scope(ty::Region, ty::Region), // superscope, subscope
 364     err_borrowed_pointer_too_short(ty::Region, ty::Region), // loan, ptr
 365 }
 366
 367 // Combination of an error code and the categorization of the expression
 368 // that caused it
 369 #[deriving(PartialEq)]
 370 pub struct BckError {
 371     span: Span,
 372     cause: euv::LoanCause,
 373     cmt: mc::cmt,
 374     code: bckerr_code
 375 }
 376
 377 pub enum AliasableViolationKind {
 378     MutabilityViolation,
 379     BorrowViolation(euv::LoanCause)
 380 }
 381
 382 pub enum MovedValueUseKind {
 383     MovedInUse,
 384     MovedInCapture,
 385 }
 386
 387 ///////////////////////////////////////////////////////////////////////////
 388 // Misc
 389
 390 impl<'a, 'tcx> BorrowckCtxt<'a, 'tcx> {
 391     pub fn is_subregion_of(&self, r_sub: ty::Region, r_sup: ty::Region)
 392                            -> bool {
 393         self.tcx.region_maps.is_subregion_of(r_sub, r_sup)
 394     }
 395
 396     pub fn is_subscope_of(&self, r_sub: ast::NodeId, r_sup: ast::NodeId)
 397                           -> bool {
 398         self.tcx.region_maps.is_subscope_of(r_sub, r_sup)
 399     }
 400
 401     pub fn mc(&self) -> mc::MemCategorizationContext<'a, ty::ctxt<'tcx>> {
 402         mc::MemCategorizationContext::new(self.tcx)
 403     }
 404
 405     pub fn cat_expr(&self, expr: &ast::Expr) -> mc::cmt {
 406         match self.mc().cat_expr(expr) {
 407             Ok(c) => c,
 408             Err(()) => {
 409                 self.tcx.sess.span_bug(expr.span, "error in mem categorization");
 410             }
 411         }
 412     }
 413
 414     pub fn cat_expr_unadjusted(&self, expr: &ast::Expr) -> mc::cmt {
 415         match self.mc().cat_expr_unadjusted(expr) {
 416             Ok(c) => c,
 417             Err(()) => {
 418                 self.tcx.sess.span_bug(expr.span, "error in mem categorization");
 419             }
 420         }
 421     }
 422
 423     pub fn cat_expr_autoderefd(&self,
 424                                expr: &ast::Expr,
 425                                adj: &ty::AutoAdjustment)
 426                                -> mc::cmt {
 427         let r = match *adj {
 428             ty::AutoDerefRef(
 429                 ty::AutoDerefRef {
 430                     autoderefs: autoderefs, ..}) => {
 431                 self.mc().cat_expr_autoderefd(expr, autoderefs)
 432             }
 433             ty::AutoAddEnv(..) => {
 434                 // no autoderefs
 435                 self.mc().cat_expr_unadjusted(expr)
 436             }
 437         };
 438
 439         match r {
 440             Ok(c) => c,
 441             Err(()) => {
 442                 self.tcx.sess.span_bug(expr.span,
 443                                        "error in mem categorization");
 444             }
 445         }
 446     }
 447
 448     pub fn cat_def(&self,
 449                    id: ast::NodeId,
 450                    span: Span,
 451                    ty: ty::t,
 452                    def: def::Def)
 453                    -> mc::cmt {
 454         match self.mc().cat_def(id, span, ty, def) {
 455             Ok(c) => c,
 456             Err(()) => {
 457                 self.tcx.sess.span_bug(span, "error in mem categorization");
 458             }
 459         }
 460     }
 461
 462     pub fn cat_captured_var(&self,
 463                             closure_id: ast::NodeId,
 464                             closure_span: Span,
 465                             upvar_def: def::Def)
 466                             -> mc::cmt {
 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)
 472     }
 473
 474     pub fn cat_discr(&self, cmt: mc::cmt, match_id: ast::NodeId) -> mc::cmt {
 475         Rc::new(mc::cmt_ {
 476             cat: mc::cat_discr(cmt.clone(), match_id),
 477             mutbl: cmt.mutbl.inherit(),
 478             ..*cmt
 479         })
 480     }
 481
 482     pub fn cat_pattern(&self,
 483                        cmt: mc::cmt,
 484                        pat: &ast::Pat,
 485                        op: |mc::cmt, &ast::Pat|) {
 486         let r = self.mc().cat_pattern(cmt, pat, |_,x,y| op(x,y));
 487         assert!(r.is_ok());
 488     }
 489
 490     pub fn report(&self, err: BckError) {
 491         self.span_err(
 492             err.span,
 493             self.bckerr_to_string(&err).as_slice());
 494         self.note_and_explain_bckerr(err);
 495     }
 496
 497     pub fn report_use_of_moved_value(&self,
 498                                      use_span: Span,
 499                                      use_kind: MovedValueUseKind,
 500                                      lp: &LoanPath,
 501                                      move: &move_data::Move,
 502                                      moved_lp: &LoanPath) {
 503         let verb = match use_kind {
 504             MovedInUse => "use",
 505             MovedInCapture => "capture",
 506         };
 507
 508         match move.kind {
 509             move_data::Declared => {
 510                 self.tcx.sess.span_err(
 511                     use_span,
 512                     format!("{} of possibly uninitialized variable: `{}`",
 513                             verb,
 514                             self.loan_path_to_string(lp)).as_slice());
 515             }
 516             _ => {
 517                 let partially = if lp == moved_lp {""} else {"partially "};
 518                 self.tcx.sess.span_err(
 519                     use_span,
 520                     format!("{} of {}moved value: `{}`",
 521                             verb,
 522                             partially,
 523                             self.loan_path_to_string(lp)).as_slice());
 524             }
 525         }
 526
 527         match move.kind {
 528             move_data::Declared => {}
 529
 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)
 534                     }
 535                     r => {
 536                         self.tcx.sess.bug(format!("MoveExpr({:?}) maps to \
 537                                                    {:?}, not Expr",
 538                                                   move.id,
 539                                                   r).as_slice())
 540                     }
 541                 };
 542                 let suggestion = move_suggestion(self.tcx, expr_ty,
 543                         "moved by default (use `copy` to override)");
 544                 self.tcx.sess.span_note(
 545                     expr_span,
 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());
 550             }
 551
 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 \
 557                              override)",
 558                             self.loan_path_to_string(moved_lp),
 559                             pat_ty.user_string(self.tcx)).as_slice());
 560             }
 561
 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)
 566                     }
 567                     r => {
 568                         self.tcx.sess.bug(format!("Captured({:?}) maps to \
 569                                                    {:?}, not Expr",
 570                                                   move.id,
 571                                                   r).as_slice())
 572                     }
 573                 };
 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(
 578                     expr_span,
 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());
 584             }
 585         }
 586
 587         fn move_suggestion(tcx: &ty::ctxt, ty: ty::t, default_msg: &'static str)
 588                           -> &'static str {
 589             match ty::get(ty).sty {
 590                 ty::ty_closure(box ty::ClosureTy {
 591                         store: ty::RegionTraitStore(..),
 592                         ..
 593                     }) =>
 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()?)",
 598                 _ => default_msg,
 599             }
 600         }
 601     }
 602
 603     pub fn report_reassigned_immutable_variable(&self,
 604                                                 span: Span,
 605                                                 lp: &LoanPath,
 606                                                 assign:
 607                                                 &move_data::Assignment) {
 608         self.tcx.sess.span_err(
 609             span,
 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");
 613     }
 614
 615     pub fn span_err(&self, s: Span, m: &str) {
 616         self.tcx.sess.span_err(s, m);
 617     }
 618
 619     pub fn span_note(&self, s: Span, m: &str) {
 620         self.tcx.sess.span_note(s, m);
 621     }
 622
 623     pub fn span_end_note(&self, s: Span, m: &str) {
 624         self.tcx.sess.span_end_note(s, m);
 625     }
 626
 627     pub fn bckerr_to_string(&self, err: &BckError) -> String {
 628         match err.code {
 629             err_mutbl => {
 630                 let descr = match opt_loan_path(&err.cmt) {
 631                     None => {
 632                         format!("{} {}",
 633                                 err.cmt.mutbl.to_user_str(),
 634                                 self.cmt_to_string(&*err.cmt))
 635                     }
 636                     Some(lp) => {
 637                         format!("{} {} `{}`",
 638                                 err.cmt.mutbl.to_user_str(),
 639                                 self.cmt_to_string(&*err.cmt),
 640                                 self.loan_path_to_string(&*lp))
 641                     }
 642                 };
 643
 644                 match err.cause {
 645                     euv::ClosureCapture(_) => {
 646                         format!("closure cannot assign to {}", descr)
 647                     }
 648                     euv::OverloadedOperator |
 649                     euv::AddrOf |
 650                     euv::RefBinding |
 651                     euv::AutoRef |
 652                     euv::ForLoop => {
 653                         format!("cannot borrow {} as mutable", descr)
 654                     }
 655                     euv::ClosureInvocation => {
 656                         self.tcx.sess.span_bug(err.span,
 657                             "err_mutbl with a closure invocation");
 658                     }
 659                 }
 660             }
 661             err_out_of_scope(..) => {
 662                 let msg = match opt_loan_path(&err.cmt) {
 663                     None => "borrowed value".to_string(),
 664                     Some(lp) => {
 665                         format!("`{}`", self.loan_path_to_string(&*lp))
 666                     }
 667                 };
 668                 format!("{} does not live long enough", msg)
 669             }
 670             err_borrowed_pointer_too_short(..) => {
 671                 let descr = match opt_loan_path(&err.cmt) {
 672                     Some(lp) => {
 673                         format!("`{}`", self.loan_path_to_string(&*lp))
 674                     }
 675                     None => self.cmt_to_string(&*err.cmt),
 676                 };
 677
 678                 format!("lifetime of {} is too short to guarantee \
 679                                 its contents can be safely reborrowed",
 680                                descr)
 681             }
 682         }
 683     }
 684
 685     pub fn report_aliasability_violation(&self,
 686                                          span: Span,
 687                                          kind: AliasableViolationKind,
 688                                          cause: mc::AliasableReason) {
 689         let prefix = match kind {
 690             MutabilityViolation => {
 691                 "cannot assign to data"
 692             }
 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(
 700                     span,
 701                     "aliasability violation with closure");
 702             }
 703             BorrowViolation(euv::OverloadedOperator) |
 704             BorrowViolation(euv::AddrOf) |
 705             BorrowViolation(euv::AutoRef) |
 706             BorrowViolation(euv::RefBinding) => {
 707                 "cannot borrow data mutably"
 708             }
 709
 710             BorrowViolation(euv::ClosureInvocation) => {
 711                 "closure invocation"
 712             }
 713
 714             BorrowViolation(euv::ForLoop) => {
 715                 "`for` loop"
 716             }
 717         };
 718
 719         match cause {
 720             mc::AliasableOther => {
 721                 self.tcx.sess.span_err(
 722                     span,
 723                     format!("{} in an aliasable location",
 724                              prefix).as_slice());
 725             }
 726             mc::AliasableStatic(..) |
 727             mc::AliasableStaticMut(..) => {
 728                 self.tcx.sess.span_err(
 729                     span,
 730                     format!("{} in a static location", prefix).as_slice());
 731             }
 732             mc::AliasableManaged => {
 733                 self.tcx.sess.span_err(
 734                     span,
 735                     format!("{} in a `@` pointer", prefix).as_slice());
 736             }
 737             mc::AliasableBorrowed => {
 738                 self.tcx.sess.span_err(
 739                     span,
 740                     format!("{} in a `&` reference", prefix).as_slice());
 741             }
 742         }
 743     }
 744
 745     pub fn note_and_explain_bckerr(&self, err: BckError) {
 746         let code = err.code;
 747         match code {
 748             err_mutbl(..) => { }
 749
 750             err_out_of_scope(super_scope, sub_scope) => {
 751                 note_and_explain_region(
 752                     self.tcx,
 753                     "reference must be valid for ",
 754                     sub_scope,
 755                     "...");
 756                 let suggestion = if is_statement_scope(self.tcx, super_scope) {
 757                     "; consider using a `let` binding to increase its lifetime"
 758                 } else {
 759                     ""
 760                 };
 761                 note_and_explain_region(
 762                     self.tcx,
 763                     "...but borrowed value is only valid for ",
 764                     super_scope,
 765                     suggestion);
 766             }
 767
 768             err_borrowed_pointer_too_short(loan_scope, ptr_scope) => {
 769                 let descr = match opt_loan_path(&err.cmt) {
 770                     Some(lp) => {
 771                         format!("`{}`", self.loan_path_to_string(&*lp))
 772                     }
 773                     None => self.cmt_to_string(&*err.cmt),
 774                 };
 775                 note_and_explain_region(
 776                     self.tcx,
 777                     format!("{} would have to be valid for ",
 778                             descr).as_slice(),
 779                     loan_scope,
 780                     "...");
 781                 note_and_explain_region(
 782                     self.tcx,
 783                     format!("...but {} is only valid for ", descr).as_slice(),
 784                     ptr_scope,
 785                     "");
 786             }
 787         }
 788     }
 789
 790     pub fn append_loan_path_to_string(&self,
 791                                    loan_path: &LoanPath,
 792                                    out: &mut String) {
 793         match *loan_path {
 794             LpUpvar(ty::UpvarId{ var_id: id, closure_expr_id: _ }) |
 795             LpVar(id) => {
 796                 out.push_str(ty::local_var_name_str(self.tcx, id).get());
 797             }
 798
 799             LpExtend(ref lp_base, _, LpInterior(mc::InteriorField(fname))) => {
 800                 self.append_autoderefd_loan_path_to_string(&**lp_base, out);
 801                 match fname {
 802                     mc::NamedField(fname) => {
 803                         out.push_char('.');
 804                         out.push_str(token::get_name(fname).get());
 805                     }
 806                     mc::PositionalField(idx) => {
 807                         out.push_char('.');
 808                         out.push_str(idx.to_string().as_slice());
 809                     }
 810                 }
 811             }
 812
 813             LpExtend(ref lp_base, _, LpInterior(mc::InteriorElement(_))) => {
 814                 self.append_autoderefd_loan_path_to_string(&**lp_base, out);
 815                 out.push_str("[..]");
 816             }
 817
 818             LpExtend(ref lp_base, _, LpDeref(_)) => {
 819                 out.push_char('*');
 820                 self.append_loan_path_to_string(&**lp_base, out);
 821             }
 822         }
 823     }
 824
 825     pub fn append_autoderefd_loan_path_to_string(&self,
 826                                               loan_path: &LoanPath,
 827                                               out: &mut String) {
 828         match *loan_path {
 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)
 834             }
 835
 836             LpVar(..) | LpUpvar(..) | LpExtend(_, _, LpInterior(..)) => {
 837                 self.append_loan_path_to_string(loan_path, out)
 838             }
 839         }
 840     }
 841
 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);
 845         result
 846     }
 847
 848     pub fn cmt_to_string(&self, cmt: &mc::cmt_) -> String {
 849         self.mc().cmt_to_string(cmt)
 850     }
 851 }
 852
 853 fn is_statement_scope(tcx: &ty::ctxt, region: ty::Region) -> bool {
 854      match region {
 855          ty::ReScope(node_id) => {
 856              match tcx.map.find(node_id) {
 857                  Some(ast_map::NodeStmt(_)) => true,
 858                  _ => false
 859              }
 860          }
 861          _ => false
 862      }
 863 }
 864
 865 impl BitwiseOperator for LoanDataFlowOperator {
 866     #[inline]
 867     fn join(&self, succ: uint, pred: uint) -> uint {
 868         succ | pred // loans from both preds are in scope
 869     }
 870 }
 871
 872 impl DataFlowOperator for LoanDataFlowOperator {
 873     #[inline]
 874     fn initial_value(&self) -> bool {
 875         false // no loans in scope by default
 876     }
 877 }
 878
 879 impl Repr for Loan {
 880     fn repr(&self, tcx: &ty::ctxt) -> String {
 881         format!("Loan_{:?}({}, {:?}, {:?}-{:?}, {})",
 882                  self.index,
 883                  self.loan_path.repr(tcx),
 884                  self.kind,
 885                  self.gen_scope,
 886                  self.kill_scope,
 887                  self.restricted_paths.repr(tcx))
 888     }
 889 }
 890
 891 impl Repr for LoanPath {
 892     fn repr(&self, tcx: &ty::ctxt) -> String {
 893         match self {
 894             &LpVar(id) => {
 895                 format!("$({})", tcx.map.node_to_string(id))
 896             }
 897
 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)
 901             }
 902
 903             &LpExtend(ref lp, _, LpDeref(_)) => {
 904                 format!("{}.*", lp.repr(tcx))
 905             }
 906
 907             &LpExtend(ref lp, _, LpInterior(ref interior)) => {
 908                 format!("{}.{}", lp.repr(tcx), interior.repr(tcx))
 909             }
 910         }
 911     }
 912 }