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