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