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