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