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, Show)]
 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, Show)]
 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, Show)]
 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, Show)]
 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_note(&self, s: Span, m: &str) {
 685         self.tcx.sess.span_note(s, m);
 686     }
 687
 688     pub fn span_end_note(&self, s: Span, m: &str) {
 689         self.tcx.sess.span_end_note(s, m);
 690     }
 691
 692     pub fn span_help(&self, s: Span, m: &str) {
 693         self.tcx.sess.span_help(s, m);
 694     }
 695
 696     pub fn bckerr_to_string(&self, err: &BckError<'tcx>) -> String {
 697         match err.code {
 698             err_mutbl => {
 699                 let descr = match err.cmt.note {
 700                     mc::NoteClosureEnv(_) | mc::NoteUpvarRef(_) => {
 701                         self.cmt_to_string(&*err.cmt)
 702                     }
 703                     _ => match opt_loan_path(&err.cmt) {
 704                         None => {
 705                             format!("{} {}",
 706                                     err.cmt.mutbl.to_user_str(),
 707                                     self.cmt_to_string(&*err.cmt))
 708                         }
 709                         Some(lp) => {
 710                             format!("{} {} `{}`",
 711                                     err.cmt.mutbl.to_user_str(),
 712                                     self.cmt_to_string(&*err.cmt),
 713                                     self.loan_path_to_string(&*lp))
 714                         }
 715                     }
 716                 };
 717
 718                 match err.cause {
 719                     euv::ClosureCapture(_) => {
 720                         format!("closure cannot assign to {}", descr)
 721                     }
 722                     euv::OverloadedOperator |
 723                     euv::AddrOf |
 724                     euv::RefBinding |
 725                     euv::AutoRef |
 726                     euv::ForLoop |
 727                     euv::MatchDiscriminant => {
 728                         format!("cannot borrow {} as mutable", descr)
 729                     }
 730                     euv::ClosureInvocation => {
 731                         self.tcx.sess.span_bug(err.span,
 732                             "err_mutbl with a closure invocation");
 733                     }
 734                 }
 735             }
 736             err_out_of_scope(..) => {
 737                 let msg = match opt_loan_path(&err.cmt) {
 738                     None => "borrowed value".to_string(),
 739                     Some(lp) => {
 740                         format!("`{}`", self.loan_path_to_string(&*lp))
 741                     }
 742                 };
 743                 format!("{} does not live long enough", msg)
 744             }
 745             err_borrowed_pointer_too_short(..) => {
 746                 let descr = match opt_loan_path(&err.cmt) {
 747                     Some(lp) => {
 748                         format!("`{}`", self.loan_path_to_string(&*lp))
 749                     }
 750                     None => self.cmt_to_string(&*err.cmt),
 751                 };
 752
 753                 format!("lifetime of {} is too short to guarantee \
 754                                 its contents can be safely reborrowed",
 755                                descr)
 756             }
 757         }
 758     }
 759
 760     pub fn report_aliasability_violation(&self,
 761                                          span: Span,
 762                                          kind: AliasableViolationKind,
 763                                          cause: mc::AliasableReason) {
 764         let mut is_closure = false;
 765         let prefix = match kind {
 766             MutabilityViolation => {
 767                 "cannot assign to data"
 768             }
 769             BorrowViolation(euv::ClosureCapture(_)) => {
 770                 // I don't think we can get aliasability violations
 771                 // with closure captures, so no need to come up with a
 772                 // good error message. The reason this cannot happen
 773                 // is because we only capture local variables in
 774                 // closures, and those are never aliasable.
 775                 self.tcx.sess.span_bug(
 776                     span,
 777                     "aliasability violation with closure");
 778             }
 779             BorrowViolation(euv::OverloadedOperator) |
 780             BorrowViolation(euv::AddrOf) |
 781             BorrowViolation(euv::AutoRef) |
 782             BorrowViolation(euv::RefBinding) |
 783             BorrowViolation(euv::MatchDiscriminant) => {
 784                 "cannot borrow data mutably"
 785             }
 786
 787             BorrowViolation(euv::ClosureInvocation) => {
 788                 is_closure = true;
 789                 "closure invocation"
 790             }
 791
 792             BorrowViolation(euv::ForLoop) => {
 793                 "`for` loop"
 794             }
 795         };
 796
 797         match cause {
 798             mc::AliasableOther => {
 799                 self.tcx.sess.span_err(
 800                     span,
 801                     format!("{} in an aliasable location",
 802                              prefix)[]);
 803             }
 804             mc::AliasableClosure(id) => {
 805                 self.tcx.sess.span_err(span,
 806                                        format!("{} in a captured outer \
 807                                                variable in an `Fn` closure", prefix)[]);
 808                 span_help!(self.tcx.sess, self.tcx.map.span(id),
 809                            "consider changing this closure to take self by mutable reference");
 810             }
 811             mc::AliasableStatic(..) |
 812             mc::AliasableStaticMut(..) => {
 813                 self.tcx.sess.span_err(
 814                     span,
 815                     format!("{} in a static location", prefix)[]);
 816             }
 817             mc::AliasableBorrowed => {
 818                 self.tcx.sess.span_err(
 819                     span,
 820                     format!("{} in a `&` reference", prefix)[]);
 821             }
 822         }
 823
 824         if is_closure {
 825             self.tcx.sess.span_help(
 826                 span,
 827                 "closures behind references must be called via `&mut`");
 828         }
 829     }
 830
 831     pub fn note_and_explain_bckerr(&self, err: BckError<'tcx>) {
 832         let code = err.code;
 833         match code {
 834             err_mutbl(..) => {
 835                 match err.cmt.note {
 836                     mc::NoteClosureEnv(upvar_id) | mc::NoteUpvarRef(upvar_id) => {
 837                         // If this is an `Fn` closure, it simply can't mutate upvars.
 838                         // If it's an `FnMut` closure, the original variable was declared immutable.
 839                         // We need to determine which is the case here.
 840                         let kind = match err.cmt.upvar().unwrap().cat {
 841                             mc::cat_upvar(mc::Upvar { kind, .. }) => kind,
 842                             _ => unreachable!()
 843                         };
 844                         if kind == ty::FnUnboxedClosureKind {
 845                             self.tcx.sess.span_help(
 846                                 self.tcx.map.span(upvar_id.closure_expr_id),
 847                                 "consider changing this closure to take \
 848                                  self by mutable reference");
 849                         }
 850                     }
 851                     _ => {}
 852                 }
 853             }
 854
 855             err_out_of_scope(super_scope, sub_scope) => {
 856                 note_and_explain_region(
 857                     self.tcx,
 858                     "reference must be valid for ",
 859                     sub_scope,
 860                     "...");
 861                 let suggestion = if is_statement_scope(self.tcx, super_scope) {
 862                     Some("consider using a `let` binding to increase its lifetime")
 863                 } else {
 864                     None
 865                 };
 866                 let span = note_and_explain_region(
 867                     self.tcx,
 868                     "...but borrowed value is only valid for ",
 869                     super_scope,
 870                     "");
 871                 match (span, suggestion) {
 872                     (_, None) => {},
 873                     (Some(span), Some(msg)) => self.tcx.sess.span_help(span, msg),
 874                     (None, Some(msg)) => self.tcx.sess.help(msg),
 875                 }
 876             }
 877
 878             err_borrowed_pointer_too_short(loan_scope, ptr_scope) => {
 879                 let descr = match opt_loan_path(&err.cmt) {
 880                     Some(lp) => {
 881                         format!("`{}`", self.loan_path_to_string(&*lp))
 882                     }
 883                     None => self.cmt_to_string(&*err.cmt),
 884                 };
 885                 note_and_explain_region(
 886                     self.tcx,
 887                     format!("{} would have to be valid for ",
 888                             descr)[],
 889                     loan_scope,
 890                     "...");
 891                 note_and_explain_region(
 892                     self.tcx,
 893                     format!("...but {} is only valid for ", descr)[],
 894                     ptr_scope,
 895                     "");
 896             }
 897         }
 898     }
 899
 900     pub fn append_loan_path_to_string(&self,
 901                                       loan_path: &LoanPath<'tcx>,
 902                                       out: &mut String) {
 903         match loan_path.kind {
 904             LpUpvar(ty::UpvarId{ var_id: id, closure_expr_id: _ }) |
 905             LpVar(id) => {
 906                 out.push_str(ty::local_var_name_str(self.tcx, id).get());
 907             }
 908
 909             LpDowncast(ref lp_base, variant_def_id) => {
 910                 out.push('(');
 911                 self.append_loan_path_to_string(&**lp_base, out);
 912                 out.push_str(DOWNCAST_PRINTED_OPERATOR);
 913                 out.push_str(ty::item_path_str(self.tcx, variant_def_id)[]);
 914                 out.push(')');
 915             }
 916
 917
 918             LpExtend(ref lp_base, _, LpInterior(mc::InteriorField(fname))) => {
 919                 self.append_autoderefd_loan_path_to_string(&**lp_base, out);
 920                 match fname {
 921                     mc::NamedField(fname) => {
 922                         out.push('.');
 923                         out.push_str(token::get_name(fname).get());
 924                     }
 925                     mc::PositionalField(idx) => {
 926                         out.push('.');
 927                         out.push_str(idx.to_string()[]);
 928                     }
 929                 }
 930             }
 931
 932             LpExtend(ref lp_base, _, LpInterior(mc::InteriorElement(_))) => {
 933                 self.append_autoderefd_loan_path_to_string(&**lp_base, out);
 934                 out.push_str("[..]");
 935             }
 936
 937             LpExtend(ref lp_base, _, LpDeref(_)) => {
 938                 out.push('*');
 939                 self.append_loan_path_to_string(&**lp_base, out);
 940             }
 941         }
 942     }
 943
 944     pub fn append_autoderefd_loan_path_to_string(&self,
 945                                                  loan_path: &LoanPath<'tcx>,
 946                                                  out: &mut String) {
 947         match loan_path.kind {
 948             LpExtend(ref lp_base, _, LpDeref(_)) => {
 949                 // For a path like `(*x).f` or `(*x)[3]`, autoderef
 950                 // rules would normally allow users to omit the `*x`.
 951                 // So just serialize such paths to `x.f` or x[3]` respectively.
 952                 self.append_autoderefd_loan_path_to_string(&**lp_base, out)
 953             }
 954
 955             LpDowncast(ref lp_base, variant_def_id) => {
 956                 out.push('(');
 957                 self.append_autoderefd_loan_path_to_string(&**lp_base, out);
 958                 out.push(':');
 959                 out.push_str(ty::item_path_str(self.tcx, variant_def_id)[]);
 960                 out.push(')');
 961             }
 962
 963             LpVar(..) | LpUpvar(..) | LpExtend(_, _, LpInterior(..)) => {
 964                 self.append_loan_path_to_string(loan_path, out)
 965             }
 966         }
 967     }
 968
 969     pub fn loan_path_to_string(&self, loan_path: &LoanPath<'tcx>) -> String {
 970         let mut result = String::new();
 971         self.append_loan_path_to_string(loan_path, &mut result);
 972         result
 973     }
 974
 975     pub fn cmt_to_string(&self, cmt: &mc::cmt_<'tcx>) -> String {
 976         cmt.descriptive_string(self.tcx)
 977     }
 978 }
 979
 980 fn is_statement_scope(tcx: &ty::ctxt, region: ty::Region) -> bool {
 981      match region {
 982          ty::ReScope(scope) => {
 983              match tcx.map.find(scope.node_id()) {
 984                  Some(ast_map::NodeStmt(_)) => true,
 985                  _ => false
 986              }
 987          }
 988          _ => false
 989      }
 990 }
 991
 992 impl BitwiseOperator for LoanDataFlowOperator {
 993     #[inline]
 994     fn join(&self, succ: uint, pred: uint) -> uint {
 995         succ | pred // loans from both preds are in scope
 996     }
 997 }
 998
 999 impl DataFlowOperator for LoanDataFlowOperator {
1000     #[inline]
1001     fn initial_value(&self) -> bool {
1002         false // no loans in scope by default
1003     }
1004 }
1005
1006 impl<'tcx> Repr<'tcx> for Loan<'tcx> {
1007     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1008         format!("Loan_{}({}, {}, {}-{}, {})",
1009                  self.index,
1010                  self.loan_path.repr(tcx),
1011                  self.kind,
1012                  self.gen_scope,
1013                  self.kill_scope,
1014                  self.restricted_paths.repr(tcx))
1015     }
1016 }
1017
1018 impl<'tcx> Repr<'tcx> for LoanPath<'tcx> {
1019     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1020         match self.kind {
1021             LpVar(id) => {
1022                 format!("$({})", tcx.map.node_to_string(id))
1023             }
1024
1025             LpUpvar(ty::UpvarId{ var_id, closure_expr_id }) => {
1026                 let s = tcx.map.node_to_string(var_id);
1027                 format!("$({} captured by id={})", s, closure_expr_id)
1028             }
1029
1030             LpDowncast(ref lp, variant_def_id) => {
1031                 let variant_str = if variant_def_id.krate == ast::LOCAL_CRATE {
1032                     ty::item_path_str(tcx, variant_def_id)
1033                 } else {
1034                     variant_def_id.repr(tcx)
1035                 };
1036                 format!("({}{}{})", lp.repr(tcx), DOWNCAST_PRINTED_OPERATOR, variant_str)
1037             }
1038
1039             LpExtend(ref lp, _, LpDeref(_)) => {
1040                 format!("{}.*", lp.repr(tcx))
1041             }
1042
1043             LpExtend(ref lp, _, LpInterior(ref interior)) => {
1044                 format!("{}.{}", lp.repr(tcx), interior.repr(tcx))
1045             }
1046         }
1047     }
1048 }
1049
1050 impl<'tcx> UserString<'tcx> for LoanPath<'tcx> {
1051     fn user_string(&self, tcx: &ty::ctxt<'tcx>) -> String {
1052         match self.kind {
1053             LpVar(id) => {
1054                 format!("$({})", tcx.map.node_to_user_string(id))
1055             }
1056
1057             LpUpvar(ty::UpvarId{ var_id, closure_expr_id: _ }) => {
1058                 let s = tcx.map.node_to_user_string(var_id);
1059                 format!("$({} captured by closure)", s)
1060             }
1061
1062             LpDowncast(ref lp, variant_def_id) => {
1063                 let variant_str = if variant_def_id.krate == ast::LOCAL_CRATE {
1064                     ty::item_path_str(tcx, variant_def_id)
1065                 } else {
1066                     variant_def_id.repr(tcx)
1067                 };
1068                 format!("({}{}{})", lp.user_string(tcx), DOWNCAST_PRINTED_OPERATOR, variant_str)
1069             }
1070
1071             LpExtend(ref lp, _, LpDeref(_)) => {
1072                 format!("{}.*", lp.user_string(tcx))
1073             }
1074
1075             LpExtend(ref lp, _, LpInterior(ref interior)) => {
1076                 format!("{}.{}", lp.user_string(tcx), interior.repr(tcx))
1077             }
1078         }
1079     }
1080 }