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