src/librustc_borrowck/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 The Book chapter on the borrow checker for more details.
  12
  13 #![allow(non_camel_case_types)]
  14
  15 pub use self::LoanPathKind::*;
  16 pub use self::LoanPathElem::*;
  17 pub use self::bckerr_code::*;
  18 pub use self::AliasableViolationKind::*;
  19 pub use self::MovedValueUseKind::*;
  20
  21 use self::InteriorKind::*;
  22
  23 use rustc::middle::cfg;
  24 use rustc::middle::dataflow::DataFlowContext;
  25 use rustc::middle::dataflow::BitwiseOperator;
  26 use rustc::middle::dataflow::DataFlowOperator;
  27 use rustc::middle::expr_use_visitor as euv;
  28 use rustc::middle::mem_categorization as mc;
  29 use rustc::middle::region;
  30 use rustc::middle::ty::{self, Ty};
  31 use rustc::util::ppaux::{note_and_explain_region, Repr, UserString};
  32 use std::rc::Rc;
  33 use std::string::String;
  34 use syntax::ast;
  35 use syntax::ast_map;
  36 use syntax::ast_map::blocks::{FnLikeNode, FnParts};
  37 use syntax::ast_util;
  38 use syntax::codemap::Span;
  39 use syntax::parse::token;
  40 use syntax::visit;
  41 use syntax::visit::{Visitor, FnKind};
  42 use syntax::ast::{FnDecl, Block, NodeId};
  43
  44 pub mod check_loans;
  45
  46 pub mod gather_loans;
  47
  48 pub mod move_data;
  49
  50 #[derive(Clone, Copy)]
  51 pub struct LoanDataFlowOperator;
  52
  53 pub type LoanDataFlow<'a, 'tcx> = DataFlowContext<'a, 'tcx, LoanDataFlowOperator>;
  54
  55 impl<'a, 'tcx, 'v> Visitor<'v> for BorrowckCtxt<'a, 'tcx> {
  56     fn visit_fn(&mut self, fk: FnKind<'v>, fd: &'v FnDecl,
  57                 b: &'v Block, s: Span, id: ast::NodeId) {
  58         borrowck_fn(self, fk, fd, b, s, id);
  59     }
  60
  61     fn visit_item(&mut self, item: &ast::Item) {
  62         borrowck_item(self, item);
  63     }
  64 }
  65
  66 pub fn check_crate(tcx: &ty::ctxt) {
  67     let mut bccx = BorrowckCtxt {
  68         tcx: tcx,
  69         stats: BorrowStats {
  70             loaned_paths_same: 0,
  71             loaned_paths_imm: 0,
  72             stable_paths: 0,
  73             guaranteed_paths: 0
  74         }
  75     };
  76
  77     visit::walk_crate(&mut bccx, tcx.map.krate());
  78
  79     if tcx.sess.borrowck_stats() {
  80         println!("--- borrowck stats ---");
  81         println!("paths requiring guarantees: {}",
  82                  bccx.stats.guaranteed_paths);
  83         println!("paths requiring loans     : {}",
  84                  make_stat(&bccx, bccx.stats.loaned_paths_same));
  85         println!("paths requiring imm loans : {}",
  86                  make_stat(&bccx, bccx.stats.loaned_paths_imm));
  87         println!("stable paths              : {}",
  88                  make_stat(&bccx, bccx.stats.stable_paths));
  89     }
  90
  91     fn make_stat(bccx: &BorrowckCtxt, stat: uint) -> String {
  92         let total = bccx.stats.guaranteed_paths as f64;
  93         let perc = if total == 0.0 { 0.0 } else { stat as f64 * 100.0 / total };
  94         format!("{} ({:.0}%)", stat, perc)
  95     }
  96 }
  97
  98 fn borrowck_item(this: &mut BorrowckCtxt, item: &ast::Item) {
  99     // Gather loans for items. Note that we don't need
 100     // to check loans for single expressions. The check
 101     // loan step is intended for things that have a data
 102     // flow dependent conditions.
 103     match item.node {
 104         ast::ItemStatic(_, _, ref ex) |
 105         ast::ItemConst(_, ref ex) => {
 106             gather_loans::gather_loans_in_static_initializer(this, &**ex);
 107         }
 108         _ => {
 109             visit::walk_item(this, item);
 110         }
 111     }
 112 }
 113
 114 /// Collection of conclusions determined via borrow checker analyses.
 115 pub struct AnalysisData<'a, 'tcx: 'a> {
 116     pub all_loans: Vec<Loan<'tcx>>,
 117     pub loans: DataFlowContext<'a, 'tcx, LoanDataFlowOperator>,
 118     pub move_data: move_data::FlowedMoveData<'a, 'tcx>,
 119 }
 120
 121 fn borrowck_fn(this: &mut BorrowckCtxt,
 122                fk: FnKind,
 123                decl: &ast::FnDecl,
 124                body: &ast::Block,
 125                sp: Span,
 126                id: ast::NodeId) {
 127     debug!("borrowck_fn(id={})", id);
 128     let cfg = cfg::CFG::new(this.tcx, body);
 129     let AnalysisData { all_loans,
 130                        loans: loan_dfcx,
 131                        move_data:flowed_moves } =
 132         build_borrowck_dataflow_data(this, fk, decl, &cfg, body, sp, id);
 133
 134     move_data::fragments::instrument_move_fragments(&flowed_moves.move_data,
 135                                                     this.tcx, sp, id);
 136
 137     check_loans::check_loans(this,
 138                              &loan_dfcx,
 139                              flowed_moves,
 140                              &all_loans[..],
 141                              id,
 142                              decl,
 143                              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, id, 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.node_id(), loan_idx);
 170         loan_dfcx.add_kill(loan.kill_scope.node_id(), 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: BorrowStats {
 210             loaned_paths_same: 0,
 211             loaned_paths_imm: 0,
 212             stable_paths: 0,
 213             guaranteed_paths: 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: BorrowStats
 238 }
 239
 240 struct BorrowStats {
 241     loaned_paths_same: uint,
 242     loaned_paths_imm: uint,
 243     stable_paths: uint,
 244     guaranteed_paths: uint
 245 }
 246
 247 pub type BckResult<'tcx, T> = Result<T, BckError<'tcx>>;
 248
 249 ///////////////////////////////////////////////////////////////////////////
 250 // Loans and loan paths
 251
 252 /// Record of a loan that was issued.
 253 pub struct Loan<'tcx> {
 254     index: uint,
 255     loan_path: Rc<LoanPath<'tcx>>,
 256     kind: ty::BorrowKind,
 257     restricted_paths: Vec<Rc<LoanPath<'tcx>>>,
 258
 259     /// gen_scope indicates where loan is introduced. Typically the
 260     /// loan is introduced at the point of the borrow, but in some
 261     /// cases, notably method arguments, the loan may be introduced
 262     /// only later, once it comes into scope.  See also
 263     /// `GatherLoanCtxt::compute_gen_scope`.
 264     gen_scope: region::CodeExtent,
 265
 266     /// kill_scope indicates when the loan goes out of scope.  This is
 267     /// either when the lifetime expires or when the local variable
 268     /// which roots the loan-path goes out of scope, whichever happens
 269     /// faster. See also `GatherLoanCtxt::compute_kill_scope`.
 270     kill_scope: region::CodeExtent,
 271     span: Span,
 272     cause: euv::LoanCause,
 273 }
 274
 275 impl<'tcx> Loan<'tcx> {
 276     pub fn loan_path(&self) -> Rc<LoanPath<'tcx>> {
 277         self.loan_path.clone()
 278     }
 279 }
 280
 281 #[derive(Eq, Hash, Debug)]
 282 pub struct LoanPath<'tcx> {
 283     kind: LoanPathKind<'tcx>,
 284     ty: ty::Ty<'tcx>,
 285 }
 286
 287 impl<'tcx> PartialEq for LoanPath<'tcx> {
 288     fn eq(&self, that: &LoanPath<'tcx>) -> bool {
 289         let r = self.kind == that.kind;
 290         debug_assert!(self.ty == that.ty || !r,
 291                       "Somehow loan paths are equal though their tys are not.");
 292         r
 293     }
 294 }
 295
 296 #[derive(PartialEq, Eq, Hash, Debug)]
 297 pub enum LoanPathKind<'tcx> {
 298     LpVar(ast::NodeId),                         // `x` in doc.rs
 299     LpUpvar(ty::UpvarId),                       // `x` captured by-value into closure
 300     LpDowncast(Rc<LoanPath<'tcx>>, ast::DefId), // `x` downcast to particular enum variant
 301     LpExtend(Rc<LoanPath<'tcx>>, mc::MutabilityCategory, LoanPathElem)
 302 }
 303
 304 impl<'tcx> LoanPath<'tcx> {
 305     fn new(kind: LoanPathKind<'tcx>, ty: ty::Ty<'tcx>) -> LoanPath<'tcx> {
 306         LoanPath { kind: kind, ty: ty }
 307     }
 308
 309     fn to_type(&self) -> ty::Ty<'tcx> { self.ty }
 310 }
 311
 312 // FIXME (pnkfelix): See discussion here
 313 // https://github.com/pnkfelix/rust/commit/
 314 //     b2b39e8700e37ad32b486b9a8409b50a8a53aa51#commitcomment-7892003
 315 static DOWNCAST_PRINTED_OPERATOR : &'static str = " as ";
 316
 317 // A local, "cleaned" version of `mc::InteriorKind` that drops
 318 // information that is not relevant to loan-path analysis. (In
 319 // particular, the distinction between how precisely a array-element
 320 // is tracked is irrelevant here.)
 321 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
 322 pub enum InteriorKind {
 323     InteriorField(mc::FieldName),
 324     InteriorElement(mc::ElementKind),
 325 }
 326
 327 trait ToInteriorKind { fn cleaned(self) -> InteriorKind; }
 328 impl ToInteriorKind for mc::InteriorKind {
 329     fn cleaned(self) -> InteriorKind {
 330         match self {
 331             mc::InteriorField(name) => InteriorField(name),
 332             mc::InteriorElement(_, elem_kind) => InteriorElement(elem_kind),
 333         }
 334     }
 335 }
 336
 337 #[derive(Copy, PartialEq, Eq, Hash, Debug)]
 338 pub enum LoanPathElem {
 339     LpDeref(mc::PointerKind),    // `*LV` in doc.rs
 340     LpInterior(InteriorKind),    // `LV.f` in doc.rs
 341 }
 342
 343 pub fn closure_to_block(closure_id: ast::NodeId,
 344                         tcx: &ty::ctxt) -> ast::NodeId {
 345     match tcx.map.get(closure_id) {
 346         ast_map::NodeExpr(expr) => match expr.node {
 347             ast::ExprClosure(_, _, ref block) => {
 348                 block.id
 349             }
 350             _ => {
 351                 panic!("encountered non-closure id: {}", closure_id)
 352             }
 353         },
 354         _ => panic!("encountered non-expr id: {}", closure_id)
 355     }
 356 }
 357
 358 impl<'tcx> LoanPath<'tcx> {
 359     pub fn kill_scope(&self, tcx: &ty::ctxt<'tcx>) -> region::CodeExtent {
 360         match self.kind {
 361             LpVar(local_id) => tcx.region_maps.var_scope(local_id),
 362             LpUpvar(upvar_id) => {
 363                 let block_id = closure_to_block(upvar_id.closure_expr_id, tcx);
 364                 region::CodeExtent::from_node_id(block_id)
 365             }
 366             LpDowncast(ref base, _) |
 367             LpExtend(ref base, _, _) => base.kill_scope(tcx),
 368         }
 369     }
 370
 371     fn has_fork(&self, other: &LoanPath<'tcx>) -> bool {
 372         match (&self.kind, &other.kind) {
 373             (&LpExtend(ref base, _, LpInterior(id)), &LpExtend(ref base2, _, LpInterior(id2))) =>
 374                 if id == id2 {
 375                     base.has_fork(&**base2)
 376                 } else {
 377                     true
 378                 },
 379             (&LpExtend(ref base, _, LpDeref(_)), _) => base.has_fork(other),
 380             (_, &LpExtend(ref base, _, LpDeref(_))) => self.has_fork(&**base),
 381             _ => false,
 382         }
 383     }
 384
 385     fn depth(&self) -> uint {
 386         match self.kind {
 387             LpExtend(ref base, _, LpDeref(_)) => base.depth(),
 388             LpExtend(ref base, _, LpInterior(_)) => base.depth() + 1,
 389             _ => 0,
 390         }
 391     }
 392
 393     fn common(&self, other: &LoanPath<'tcx>) -> Option<LoanPath<'tcx>> {
 394         match (&self.kind, &other.kind) {
 395             (&LpExtend(ref base, a, LpInterior(id)),
 396              &LpExtend(ref base2, _, LpInterior(id2))) => {
 397                 if id == id2 {
 398                     base.common(&**base2).map(|x| {
 399                         let xd = x.depth();
 400                         if base.depth() == xd && base2.depth() == xd {
 401                             assert_eq!(base.ty, base2.ty);
 402                             assert_eq!(self.ty, other.ty);
 403                             LoanPath {
 404                                 kind: LpExtend(Rc::new(x), a, LpInterior(id)),
 405                                 ty: self.ty,
 406                             }
 407                         } else {
 408                             x
 409                         }
 410                     })
 411                 } else {
 412                     base.common(&**base2)
 413                 }
 414             }
 415             (&LpExtend(ref base, _, LpDeref(_)), _) => base.common(other),
 416             (_, &LpExtend(ref other, _, LpDeref(_))) => self.common(&**other),
 417             (&LpVar(id), &LpVar(id2)) => {
 418                 if id == id2 {
 419                     assert_eq!(self.ty, other.ty);
 420                     Some(LoanPath { kind: LpVar(id), ty: self.ty })
 421                 } else {
 422                     None
 423                 }
 424             }
 425             (&LpUpvar(id), &LpUpvar(id2)) => {
 426                 if id == id2 {
 427                     assert_eq!(self.ty, other.ty);
 428                     Some(LoanPath { kind: LpUpvar(id), ty: self.ty })
 429                 } else {
 430                     None
 431                 }
 432             }
 433             _ => None,
 434         }
 435     }
 436 }
 437
 438 pub fn opt_loan_path<'tcx>(cmt: &mc::cmt<'tcx>) -> Option<Rc<LoanPath<'tcx>>> {
 439     //! Computes the `LoanPath` (if any) for a `cmt`.
 440     //! Note that this logic is somewhat duplicated in
 441     //! the method `compute()` found in `gather_loans::restrictions`,
 442     //! which allows it to share common loan path pieces as it
 443     //! traverses the CMT.
 444
 445     let new_lp = |v: LoanPathKind<'tcx>| Rc::new(LoanPath::new(v, cmt.ty));
 446
 447     match cmt.cat {
 448         mc::cat_rvalue(..) |
 449         mc::cat_static_item => {
 450             None
 451         }
 452
 453         mc::cat_local(id) => {
 454             Some(new_lp(LpVar(id)))
 455         }
 456
 457         mc::cat_upvar(mc::Upvar { id, .. }) => {
 458             Some(new_lp(LpUpvar(id)))
 459         }
 460
 461         mc::cat_deref(ref cmt_base, _, pk) => {
 462             opt_loan_path(cmt_base).map(|lp| {
 463                 new_lp(LpExtend(lp, cmt.mutbl, LpDeref(pk)))
 464             })
 465         }
 466
 467         mc::cat_interior(ref cmt_base, ik) => {
 468             opt_loan_path(cmt_base).map(|lp| {
 469                 new_lp(LpExtend(lp, cmt.mutbl, LpInterior(ik.cleaned())))
 470             })
 471         }
 472
 473         mc::cat_downcast(ref cmt_base, variant_def_id) =>
 474             opt_loan_path(cmt_base)
 475             .map(|lp| {
 476                 new_lp(LpDowncast(lp, variant_def_id))
 477             }),
 478
 479     }
 480 }
 481
 482 ///////////////////////////////////////////////////////////////////////////
 483 // Errors
 484
 485 // Errors that can occur
 486 #[derive(PartialEq)]
 487 pub enum bckerr_code {
 488     err_mutbl,
 489     err_out_of_scope(ty::Region, ty::Region), // superscope, subscope
 490     err_borrowed_pointer_too_short(ty::Region, ty::Region), // loan, ptr
 491 }
 492
 493 // Combination of an error code and the categorization of the expression
 494 // that caused it
 495 #[derive(PartialEq)]
 496 pub struct BckError<'tcx> {
 497     span: Span,
 498     cause: euv::LoanCause,
 499     cmt: mc::cmt<'tcx>,
 500     code: bckerr_code
 501 }
 502
 503 #[derive(Copy)]
 504 pub enum AliasableViolationKind {
 505     MutabilityViolation,
 506     BorrowViolation(euv::LoanCause)
 507 }
 508
 509 #[derive(Copy, Debug)]
 510 pub enum MovedValueUseKind {
 511     MovedInUse,
 512     MovedInCapture,
 513 }
 514
 515 ///////////////////////////////////////////////////////////////////////////
 516 // Misc
 517
 518 impl<'a, 'tcx> BorrowckCtxt<'a, 'tcx> {
 519     pub fn is_subregion_of(&self, r_sub: ty::Region, r_sup: ty::Region)
 520                            -> bool {
 521         self.tcx.region_maps.is_subregion_of(r_sub, r_sup)
 522     }
 523
 524     pub fn report(&self, err: BckError<'tcx>) {
 525         self.span_err(
 526             err.span,
 527             &self.bckerr_to_string(&err)[]);
 528         self.note_and_explain_bckerr(err);
 529     }
 530
 531     pub fn report_use_of_moved_value<'b>(&self,
 532                                          use_span: Span,
 533                                          use_kind: MovedValueUseKind,
 534                                          lp: &LoanPath<'tcx>,
 535                                          the_move: &move_data::Move,
 536                                          moved_lp: &LoanPath<'tcx>,
 537                                          param_env: &ty::ParameterEnvironment<'b,'tcx>) {
 538         let verb = match use_kind {
 539             MovedInUse => "use",
 540             MovedInCapture => "capture",
 541         };
 542
 543         let (ol, moved_lp_msg) = match the_move.kind {
 544             move_data::Declared => {
 545                 self.tcx.sess.span_err(
 546                     use_span,
 547                     &format!("{} of possibly uninitialized variable: `{}`",
 548                             verb,
 549                             self.loan_path_to_string(lp))[]);
 550                 (self.loan_path_to_string(moved_lp),
 551                  String::new())
 552             }
 553             _ => {
 554                 // If moved_lp is something like `x.a`, and lp is something like `x.b`, we would
 555                 // normally generate a rather confusing message:
 556                 //
 557                 //     error: use of moved value: `x.b`
 558                 //     note: `x.a` moved here...
 559                 //
 560                 // What we want to do instead is get the 'common ancestor' of the two moves and
 561                 // use that for most of the message instead, giving is something like this:
 562                 //
 563                 //     error: use of moved value: `x`
 564                 //     note: `x` moved here (through moving `x.a`)...
 565
 566                 let common = moved_lp.common(lp);
 567                 let has_common = common.is_some();
 568                 let has_fork = moved_lp.has_fork(lp);
 569                 let (nl, ol, moved_lp_msg) =
 570                     if has_fork && has_common {
 571                         let nl = self.loan_path_to_string(&common.unwrap());
 572                         let ol = nl.clone();
 573                         let moved_lp_msg = format!(" (through moving `{}`)",
 574                                                    self.loan_path_to_string(moved_lp));
 575                         (nl, ol, moved_lp_msg)
 576                     } else {
 577                         (self.loan_path_to_string(lp),
 578                          self.loan_path_to_string(moved_lp),
 579                          String::new())
 580                     };
 581
 582                 let partial = moved_lp.depth() > lp.depth();
 583                 let msg = if !has_fork && partial { "partially " }
 584                           else if has_fork && !has_common { "collaterally "}
 585                           else { "" };
 586                 self.tcx.sess.span_err(
 587                     use_span,
 588                     &format!("{} of {}moved value: `{}`",
 589                             verb,
 590                             msg,
 591                             nl)[]);
 592                 (ol, moved_lp_msg)
 593             }
 594         };
 595
 596         match the_move.kind {
 597             move_data::Declared => {}
 598
 599             move_data::MoveExpr => {
 600                 let (expr_ty, expr_span) = match self.tcx
 601                                                      .map
 602                                                      .find(the_move.id) {
 603                     Some(ast_map::NodeExpr(expr)) => {
 604                         (ty::expr_ty_adjusted(self.tcx, &*expr), expr.span)
 605                     }
 606                     r => {
 607                         self.tcx.sess.bug(&format!("MoveExpr({}) maps to \
 608                                                    {:?}, not Expr",
 609                                                   the_move.id,
 610                                                   r)[])
 611                     }
 612                 };
 613                 let (suggestion, _) =
 614                     move_suggestion(param_env, expr_span, expr_ty, ("moved by default", ""));
 615                 self.tcx.sess.span_note(
 616                     expr_span,
 617                     &format!("`{}` moved here{} because it has type `{}`, which is {}",
 618                             ol,
 619                             moved_lp_msg,
 620                             expr_ty.user_string(self.tcx),
 621                             suggestion)[]);
 622             }
 623
 624             move_data::MovePat => {
 625                 let pat_ty = ty::node_id_to_type(self.tcx, the_move.id);
 626                 let span = self.tcx.map.span(the_move.id);
 627                 self.tcx.sess.span_note(span,
 628                     &format!("`{}` moved here{} because it has type `{}`, \
 629                              which is moved by default",
 630                             ol,
 631                             moved_lp_msg,
 632                             pat_ty.user_string(self.tcx))[]);
 633                 self.tcx.sess.span_help(span,
 634                     "use `ref` to override");
 635             }
 636
 637             move_data::Captured => {
 638                 let (expr_ty, expr_span) = match self.tcx
 639                                                      .map
 640                                                      .find(the_move.id) {
 641                     Some(ast_map::NodeExpr(expr)) => {
 642                         (ty::expr_ty_adjusted(self.tcx, &*expr), expr.span)
 643                     }
 644                     r => {
 645                         self.tcx.sess.bug(&format!("Captured({}) maps to \
 646                                                    {:?}, not Expr",
 647                                                   the_move.id,
 648                                                   r)[])
 649                     }
 650                 };
 651                 let (suggestion, help) =
 652                     move_suggestion(param_env,
 653                                     expr_span,
 654                                     expr_ty,
 655                                     ("moved by default",
 656                                      "make a copy and capture that instead to override"));
 657                 self.tcx.sess.span_note(
 658                     expr_span,
 659                     &format!("`{}` moved into closure environment here{} because it \
 660                             has type `{}`, which is {}",
 661                             ol,
 662                             moved_lp_msg,
 663                             expr_ty.user_string(self.tcx),
 664                             suggestion)[]);
 665                 self.tcx.sess.span_help(expr_span, help);
 666             }
 667         }
 668
 669         fn move_suggestion<'a,'tcx>(param_env: &ty::ParameterEnvironment<'a,'tcx>,
 670                                     span: Span,
 671                                     ty: Ty<'tcx>,
 672                                     default_msgs: (&'static str, &'static str))
 673                                     -> (&'static str, &'static str) {
 674             match ty.sty {
 675                 _ => {
 676                     if ty::type_moves_by_default(param_env, span, ty) {
 677                         ("non-copyable",
 678                          "perhaps you meant to use `clone()`?")
 679                     } else {
 680                         default_msgs
 681                     }
 682                 }
 683             }
 684         }
 685     }
 686
 687     pub fn report_partial_reinitialization_of_uninitialized_structure(
 688             &self,
 689             span: Span,
 690             lp: &LoanPath<'tcx>) {
 691         self.tcx
 692             .sess
 693             .span_err(span,
 694                       (format!("partial reinitialization of uninitialized \
 695                                structure `{}`",
 696                                self.loan_path_to_string(lp))).as_slice());
 697     }
 698
 699     pub fn report_reassigned_immutable_variable(&self,
 700                                                 span: Span,
 701                                                 lp: &LoanPath<'tcx>,
 702                                                 assign:
 703                                                 &move_data::Assignment) {
 704         self.tcx.sess.span_err(
 705             span,
 706             &format!("re-assignment of immutable variable `{}`",
 707                     self.loan_path_to_string(lp))[]);
 708         self.tcx.sess.span_note(assign.span, "prior assignment occurs here");
 709     }
 710
 711     pub fn span_err(&self, s: Span, m: &str) {
 712         self.tcx.sess.span_err(s, m);
 713     }
 714
 715     pub fn span_bug(&self, s: Span, m: &str) {
 716         self.tcx.sess.span_bug(s, m);
 717     }
 718
 719     pub fn span_note(&self, s: Span, m: &str) {
 720         self.tcx.sess.span_note(s, m);
 721     }
 722
 723     pub fn span_end_note(&self, s: Span, m: &str) {
 724         self.tcx.sess.span_end_note(s, m);
 725     }
 726
 727     pub fn span_help(&self, s: Span, m: &str) {
 728         self.tcx.sess.span_help(s, m);
 729     }
 730
 731     pub fn bckerr_to_string(&self, err: &BckError<'tcx>) -> String {
 732         match err.code {
 733             err_mutbl => {
 734                 let descr = match err.cmt.note {
 735                     mc::NoteClosureEnv(_) | mc::NoteUpvarRef(_) => {
 736                         self.cmt_to_string(&*err.cmt)
 737                     }
 738                     _ => match opt_loan_path(&err.cmt) {
 739                         None => {
 740                             format!("{} {}",
 741                                     err.cmt.mutbl.to_user_str(),
 742                                     self.cmt_to_string(&*err.cmt))
 743                         }
 744                         Some(lp) => {
 745                             format!("{} {} `{}`",
 746                                     err.cmt.mutbl.to_user_str(),
 747                                     self.cmt_to_string(&*err.cmt),
 748                                     self.loan_path_to_string(&*lp))
 749                         }
 750                     }
 751                 };
 752
 753                 match err.cause {
 754                     euv::ClosureCapture(_) => {
 755                         format!("closure cannot assign to {}", descr)
 756                     }
 757                     euv::OverloadedOperator |
 758                     euv::AddrOf |
 759                     euv::RefBinding |
 760                     euv::AutoRef |
 761                     euv::ForLoop |
 762                     euv::MatchDiscriminant => {
 763                         format!("cannot borrow {} as mutable", descr)
 764                     }
 765                     euv::ClosureInvocation => {
 766                         self.tcx.sess.span_bug(err.span,
 767                             "err_mutbl with a closure invocation");
 768                     }
 769                 }
 770             }
 771             err_out_of_scope(..) => {
 772                 let msg = match opt_loan_path(&err.cmt) {
 773                     None => "borrowed value".to_string(),
 774                     Some(lp) => {
 775                         format!("`{}`", self.loan_path_to_string(&*lp))
 776                     }
 777                 };
 778                 format!("{} does not live long enough", msg)
 779             }
 780             err_borrowed_pointer_too_short(..) => {
 781                 let descr = match opt_loan_path(&err.cmt) {
 782                     Some(lp) => {
 783                         format!("`{}`", self.loan_path_to_string(&*lp))
 784                     }
 785                     None => self.cmt_to_string(&*err.cmt),
 786                 };
 787
 788                 format!("lifetime of {} is too short to guarantee \
 789                                 its contents can be safely reborrowed",
 790                                descr)
 791             }
 792         }
 793     }
 794
 795     pub fn report_aliasability_violation(&self,
 796                                          span: Span,
 797                                          kind: AliasableViolationKind,
 798                                          cause: mc::AliasableReason) {
 799         let mut is_closure = false;
 800         let prefix = match kind {
 801             MutabilityViolation => {
 802                 "cannot assign to data"
 803             }
 804             BorrowViolation(euv::ClosureCapture(_)) |
 805             BorrowViolation(euv::OverloadedOperator) |
 806             BorrowViolation(euv::AddrOf) |
 807             BorrowViolation(euv::AutoRef) |
 808             BorrowViolation(euv::RefBinding) |
 809             BorrowViolation(euv::MatchDiscriminant) => {
 810                 "cannot borrow data mutably"
 811             }
 812
 813             BorrowViolation(euv::ClosureInvocation) => {
 814                 is_closure = true;
 815                 "closure invocation"
 816             }
 817
 818             BorrowViolation(euv::ForLoop) => {
 819                 "`for` loop"
 820             }
 821         };
 822
 823         match cause {
 824             mc::AliasableOther => {
 825                 self.tcx.sess.span_err(
 826                     span,
 827                     &format!("{} in an aliasable location",
 828                              prefix)[]);
 829             }
 830             mc::AliasableClosure(id) => {
 831                 self.tcx.sess.span_err(span,
 832                                        &format!("{} in a captured outer \
 833                                                 variable in an `Fn` closure", prefix));
 834                 if let BorrowViolation(euv::ClosureCapture(_)) = kind {
 835                     // The aliasability violation with closure captures can
 836                     // happen for nested closures, so we know the enclosing
 837                     // closure incorrectly accepts an `Fn` while it needs to
 838                     // be `FnMut`.
 839                     span_help!(self.tcx.sess, self.tcx.map.span(id),
 840                            "consider changing this to accept closures that implement `FnMut`");
 841                 } else {
 842                     span_help!(self.tcx.sess, self.tcx.map.span(id),
 843                            "consider changing this closure to take self by mutable reference");
 844                 }
 845             }
 846             mc::AliasableStatic(..) |
 847             mc::AliasableStaticMut(..) => {
 848                 self.tcx.sess.span_err(
 849                     span,
 850                     &format!("{} in a static location", prefix)[]);
 851             }
 852             mc::AliasableBorrowed => {
 853                 self.tcx.sess.span_err(
 854                     span,
 855                     &format!("{} in a `&` reference", prefix)[]);
 856             }
 857         }
 858
 859         if is_closure {
 860             self.tcx.sess.span_help(
 861                 span,
 862                 "closures behind references must be called via `&mut`");
 863         }
 864     }
 865
 866     pub fn note_and_explain_bckerr(&self, err: BckError<'tcx>) {
 867         let code = err.code;
 868         match code {
 869             err_mutbl(..) => {
 870                 match err.cmt.note {
 871                     mc::NoteClosureEnv(upvar_id) | mc::NoteUpvarRef(upvar_id) => {
 872                         // If this is an `Fn` closure, it simply can't mutate upvars.
 873                         // If it's an `FnMut` closure, the original variable was declared immutable.
 874                         // We need to determine which is the case here.
 875                         let kind = match err.cmt.upvar().unwrap().cat {
 876                             mc::cat_upvar(mc::Upvar { kind, .. }) => kind,
 877                             _ => unreachable!()
 878                         };
 879                         if kind == ty::FnClosureKind {
 880                             self.tcx.sess.span_help(
 881                                 self.tcx.map.span(upvar_id.closure_expr_id),
 882                                 "consider changing this closure to take \
 883                                  self by mutable reference");
 884                         }
 885                     }
 886                     _ => {}
 887                 }
 888             }
 889
 890             err_out_of_scope(super_scope, sub_scope) => {
 891                 note_and_explain_region(
 892                     self.tcx,
 893                     "reference must be valid for ",
 894                     sub_scope,
 895                     "...");
 896                 let suggestion = if is_statement_scope(self.tcx, super_scope) {
 897                     Some("consider using a `let` binding to increase its lifetime")
 898                 } else {
 899                     None
 900                 };
 901                 let span = note_and_explain_region(
 902                     self.tcx,
 903                     "...but borrowed value is only valid for ",
 904                     super_scope,
 905                     "");
 906                 match (span, suggestion) {
 907                     (_, None) => {},
 908                     (Some(span), Some(msg)) => self.tcx.sess.span_help(span, msg),
 909                     (None, Some(msg)) => self.tcx.sess.help(msg),
 910                 }
 911             }
 912
 913             err_borrowed_pointer_too_short(loan_scope, ptr_scope) => {
 914                 let descr = match opt_loan_path(&err.cmt) {
 915                     Some(lp) => {
 916                         format!("`{}`", self.loan_path_to_string(&*lp))
 917                     }
 918                     None => self.cmt_to_string(&*err.cmt),
 919                 };
 920                 note_and_explain_region(
 921                     self.tcx,
 922                     &format!("{} would have to be valid for ",
 923                             descr)[],
 924                     loan_scope,
 925                     "...");
 926                 note_and_explain_region(
 927                     self.tcx,
 928                     &format!("...but {} is only valid for ", descr)[],
 929                     ptr_scope,
 930                     "");
 931             }
 932         }
 933     }
 934
 935     pub fn append_loan_path_to_string(&self,
 936                                       loan_path: &LoanPath<'tcx>,
 937                                       out: &mut String) {
 938         match loan_path.kind {
 939             LpUpvar(ty::UpvarId{ var_id: id, closure_expr_id: _ }) |
 940             LpVar(id) => {
 941                 out.push_str(&ty::local_var_name_str(self.tcx, id));
 942             }
 943
 944             LpDowncast(ref lp_base, variant_def_id) => {
 945                 out.push('(');
 946                 self.append_loan_path_to_string(&**lp_base, out);
 947                 out.push_str(DOWNCAST_PRINTED_OPERATOR);
 948                 out.push_str(&ty::item_path_str(self.tcx, variant_def_id)[]);
 949                 out.push(')');
 950             }
 951
 952
 953             LpExtend(ref lp_base, _, LpInterior(InteriorField(fname))) => {
 954                 self.append_autoderefd_loan_path_to_string(&**lp_base, out);
 955                 match fname {
 956                     mc::NamedField(fname) => {
 957                         out.push('.');
 958                         out.push_str(&token::get_name(fname));
 959                     }
 960                     mc::PositionalField(idx) => {
 961                         out.push('.');
 962                         out.push_str(&idx.to_string()[]);
 963                     }
 964                 }
 965             }
 966
 967             LpExtend(ref lp_base, _, LpInterior(InteriorElement(..))) => {
 968                 self.append_autoderefd_loan_path_to_string(&**lp_base, out);
 969                 out.push_str("[..]");
 970             }
 971
 972             LpExtend(ref lp_base, _, LpDeref(_)) => {
 973                 out.push('*');
 974                 self.append_loan_path_to_string(&**lp_base, out);
 975             }
 976         }
 977     }
 978
 979     pub fn append_autoderefd_loan_path_to_string(&self,
 980                                                  loan_path: &LoanPath<'tcx>,
 981                                                  out: &mut String) {
 982         match loan_path.kind {
 983             LpExtend(ref lp_base, _, LpDeref(_)) => {
 984                 // For a path like `(*x).f` or `(*x)[3]`, autoderef
 985                 // rules would normally allow users to omit the `*x`.
 986                 // So just serialize such paths to `x.f` or x[3]` respectively.
 987                 self.append_autoderefd_loan_path_to_string(&**lp_base, out)
 988             }
 989
 990             LpDowncast(ref lp_base, variant_def_id) => {
 991                 out.push('(');
 992                 self.append_autoderefd_loan_path_to_string(&**lp_base, out);
 993                 out.push(':');
 994                 out.push_str(&ty::item_path_str(self.tcx, variant_def_id)[]);
 995                 out.push(')');
 996             }
 997
 998             LpVar(..) | LpUpvar(..) | LpExtend(_, _, LpInterior(..)) => {
 999                 self.append_loan_path_to_string(loan_path, out)
1000             }
1001         }
1002     }
1003
1004     pub fn loan_path_to_string(&self, loan_path: &LoanPath<'tcx>) -> String {
1005         let mut result = String::new();
1006         self.append_loan_path_to_string(loan_path, &mut result);
1007         result
1008     }
1009
1010     pub fn cmt_to_string(&self, cmt: &mc::cmt_<'tcx>) -> String {
1011         cmt.descriptive_string(self.tcx)
1012     }
1013 }
1014
1015 fn is_statement_scope(tcx: &ty::ctxt, region: ty::Region) -> bool {
1016      match region {
1017          ty::ReScope(scope) => {
1018              match tcx.map.find(scope.node_id()) {
1019                  Some(ast_map::NodeStmt(_)) => true,
1020                  _ => false
1021              }
1022          }
1023          _ => false
1024      }
1025 }
1026
1027 impl BitwiseOperator for LoanDataFlowOperator {
1028     #[inline]
1029     fn join(&self, succ: uint, pred: uint) -> uint {
1030         succ | pred // loans from both preds are in scope
1031     }
1032 }
1033
1034 impl DataFlowOperator for LoanDataFlowOperator {
1035     #[inline]
1036     fn initial_value(&self) -> bool {
1037         false // no loans in scope by default
1038     }
1039 }
1040
1041 impl<'tcx> Repr<'tcx> for InteriorKind {
1042     fn repr(&self, _tcx: &ty::ctxt<'tcx>) -> String {
1043         match *self {
1044             InteriorField(mc::NamedField(fld)) =>
1045                 format!("{}", token::get_name(fld)),
1046             InteriorField(mc::PositionalField(i)) => format!("#{}", i),
1047             InteriorElement(..) => "[]".to_string(),
1048         }
1049     }
1050 }
1051
1052 impl<'tcx> Repr<'tcx> for Loan<'tcx> {
1053     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1054         format!("Loan_{}({}, {:?}, {:?}-{:?}, {})",
1055                  self.index,
1056                  self.loan_path.repr(tcx),
1057                  self.kind,
1058                  self.gen_scope,
1059                  self.kill_scope,
1060                  self.restricted_paths.repr(tcx))
1061     }
1062 }
1063
1064 impl<'tcx> Repr<'tcx> for LoanPath<'tcx> {
1065     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1066         match self.kind {
1067             LpVar(id) => {
1068                 format!("$({})", tcx.map.node_to_string(id))
1069             }
1070
1071             LpUpvar(ty::UpvarId{ var_id, closure_expr_id }) => {
1072                 let s = tcx.map.node_to_string(var_id);
1073                 format!("$({} captured by id={})", s, closure_expr_id)
1074             }
1075
1076             LpDowncast(ref lp, variant_def_id) => {
1077                 let variant_str = if variant_def_id.krate == ast::LOCAL_CRATE {
1078                     ty::item_path_str(tcx, variant_def_id)
1079                 } else {
1080                     variant_def_id.repr(tcx)
1081                 };
1082                 format!("({}{}{})", lp.repr(tcx), DOWNCAST_PRINTED_OPERATOR, variant_str)
1083             }
1084
1085             LpExtend(ref lp, _, LpDeref(_)) => {
1086                 format!("{}.*", lp.repr(tcx))
1087             }
1088
1089             LpExtend(ref lp, _, LpInterior(ref interior)) => {
1090                 format!("{}.{}", lp.repr(tcx), interior.repr(tcx))
1091             }
1092         }
1093     }
1094 }
1095
1096 impl<'tcx> UserString<'tcx> for LoanPath<'tcx> {
1097     fn user_string(&self, tcx: &ty::ctxt<'tcx>) -> String {
1098         match self.kind {
1099             LpVar(id) => {
1100                 format!("$({})", tcx.map.node_to_user_string(id))
1101             }
1102
1103             LpUpvar(ty::UpvarId{ var_id, closure_expr_id: _ }) => {
1104                 let s = tcx.map.node_to_user_string(var_id);
1105                 format!("$({} captured by closure)", s)
1106             }
1107
1108             LpDowncast(ref lp, variant_def_id) => {
1109                 let variant_str = if variant_def_id.krate == ast::LOCAL_CRATE {
1110                     ty::item_path_str(tcx, variant_def_id)
1111                 } else {
1112                     variant_def_id.repr(tcx)
1113                 };
1114                 format!("({}{}{})", lp.user_string(tcx), DOWNCAST_PRINTED_OPERATOR, variant_str)
1115             }
1116
1117             LpExtend(ref lp, _, LpDeref(_)) => {
1118                 format!("{}.*", lp.user_string(tcx))
1119             }
1120
1121             LpExtend(ref lp, _, LpInterior(ref interior)) => {
1122                 format!("{}.{}", lp.user_string(tcx), interior.repr(tcx))
1123             }
1124         }
1125     }
1126 }