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