src/librustc/middle/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 use mc = middle::mem_categorization;
  16 use middle::ty;
  17 use middle::typeck;
  18 use middle::moves;
  19 use middle::dataflow::DataFlowContext;
  20 use middle::dataflow::DataFlowOperator;
  21 use util::nodemap::{NodeMap, NodeSet};
  22 use util::ppaux::{note_and_explain_region, Repr, UserString};
  23
  24 use std::cell::{Cell, RefCell};
  25 use std::ops::{BitOr, BitAnd};
  26 use std::rc::Rc;
  27 use std::strbuf::StrBuf;
  28 use syntax::ast;
  29 use syntax::ast_map;
  30 use syntax::ast_util;
  31 use syntax::codemap::Span;
  32 use syntax::parse::token;
  33 use syntax::visit;
  34 use syntax::visit::{Visitor, FnKind};
  35 use syntax::ast::{FnDecl, Block, NodeId};
  36
  37 macro_rules! if_ok(
  38     ($inp: expr) => (
  39         match $inp {
  40             Ok(v) => { v }
  41             Err(e) => { return Err(e); }
  42         }
  43     )
  44 )
  45
  46 pub mod doc;
  47
  48 pub mod check_loans;
  49
  50 pub mod gather_loans;
  51
  52 pub mod move_data;
  53
  54 pub struct LoanDataFlowOperator;
  55
  56 /// FIXME(pcwalton): Should just be #[deriving(Clone)], but that doesn't work
  57 /// yet on unit structs.
  58 impl Clone for LoanDataFlowOperator {
  59     fn clone(&self) -> LoanDataFlowOperator {
  60         LoanDataFlowOperator
  61     }
  62 }
  63
  64 pub type LoanDataFlow<'a> = DataFlowContext<'a, LoanDataFlowOperator>;
  65
  66 impl<'a> Visitor<()> for BorrowckCtxt<'a> {
  67     fn visit_fn(&mut self, fk: &FnKind, fd: &FnDecl,
  68                 b: &Block, s: Span, n: NodeId, _: ()) {
  69         borrowck_fn(self, fk, fd, b, s, n);
  70     }
  71
  72     fn visit_item(&mut self, item: &ast::Item, _: ()) {
  73         borrowck_item(self, item);
  74     }
  75 }
  76
  77 pub fn check_crate(tcx: &ty::ctxt,
  78                    moves_map: &NodeSet,
  79                    capture_map: &moves::CaptureMap,
  80                    krate: &ast::Crate) {
  81     let mut bccx = BorrowckCtxt {
  82         tcx: tcx,
  83         moves_map: moves_map,
  84         capture_map: capture_map,
  85         stats: @BorrowStats {
  86             loaned_paths_same: Cell::new(0),
  87             loaned_paths_imm: Cell::new(0),
  88             stable_paths: Cell::new(0),
  89             guaranteed_paths: Cell::new(0),
  90         }
  91     };
  92
  93     visit::walk_crate(&mut bccx, krate, ());
  94
  95     if tcx.sess.borrowck_stats() {
  96         println!("--- borrowck stats ---");
  97         println!("paths requiring guarantees: {}",
  98                  bccx.stats.guaranteed_paths.get());
  99         println!("paths requiring loans     : {}",
 100                  make_stat(&bccx, bccx.stats.loaned_paths_same.get()));
 101         println!("paths requiring imm loans : {}",
 102                  make_stat(&bccx, bccx.stats.loaned_paths_imm.get()));
 103         println!("stable paths              : {}",
 104                  make_stat(&bccx, bccx.stats.stable_paths.get()));
 105     }
 106
 107     fn make_stat(bccx: &BorrowckCtxt, stat: uint) -> ~str {
 108         let stat_f = stat as f64;
 109         let total = bccx.stats.guaranteed_paths.get() as f64;
 110         format!("{} ({:.0f}%)", stat  , stat_f * 100.0 / total)
 111     }
 112 }
 113
 114 fn borrowck_item(this: &mut BorrowckCtxt, item: &ast::Item) {
 115     // Gather loans for items. Note that we don't need
 116     // to check loans for single expressions. The check
 117     // loan step is intended for things that have a data
 118     // flow dependent conditions.
 119     match item.node {
 120         ast::ItemStatic(_, _, ex) => {
 121             gather_loans::gather_loans_in_static_initializer(this, ex);
 122         }
 123         _ => {
 124             visit::walk_item(this, item, ());
 125         }
 126     }
 127 }
 128
 129 fn borrowck_fn(this: &mut BorrowckCtxt,
 130                fk: &FnKind,
 131                decl: &ast::FnDecl,
 132                body: &ast::Block,
 133                sp: Span,
 134                id: ast::NodeId) {
 135     debug!("borrowck_fn(id={})", id);
 136
 137     // Check the body of fn items.
 138     let (id_range, all_loans, move_data) =
 139         gather_loans::gather_loans_in_fn(this, decl, body);
 140     let mut loan_dfcx =
 141         DataFlowContext::new(this.tcx,
 142                              LoanDataFlowOperator,
 143                              id_range,
 144                              all_loans.len());
 145     for (loan_idx, loan) in all_loans.iter().enumerate() {
 146         loan_dfcx.add_gen(loan.gen_scope, loan_idx);
 147         loan_dfcx.add_kill(loan.kill_scope, loan_idx);
 148     }
 149     loan_dfcx.propagate(body);
 150
 151     let flowed_moves = move_data::FlowedMoveData::new(move_data,
 152                                                       this.tcx,
 153                                                       id_range,
 154                                                       body);
 155
 156     check_loans::check_loans(this, &loan_dfcx, flowed_moves,
 157                              all_loans.as_slice(), body);
 158
 159     visit::walk_fn(this, fk, decl, body, sp, id, ());
 160 }
 161
 162 // ----------------------------------------------------------------------
 163 // Type definitions
 164
 165 pub struct BorrowckCtxt<'a> {
 166     tcx: &'a ty::ctxt,
 167     moves_map: &'a NodeSet,
 168     capture_map: &'a moves::CaptureMap,
 169
 170     // Statistics:
 171     stats: @BorrowStats
 172 }
 173
 174 pub struct BorrowStats {
 175     loaned_paths_same: Cell<uint>,
 176     loaned_paths_imm: Cell<uint>,
 177     stable_paths: Cell<uint>,
 178     guaranteed_paths: Cell<uint>,
 179 }
 180
 181 pub type BckResult<T> = Result<T, BckError>;
 182
 183 #[deriving(Eq)]
 184 pub enum PartialTotal {
 185     Partial,   // Loan affects some portion
 186     Total      // Loan affects entire path
 187 }
 188
 189 ///////////////////////////////////////////////////////////////////////////
 190 // Loans and loan paths
 191
 192 /// Record of a loan that was issued.
 193 pub struct Loan {
 194     index: uint,
 195     loan_path: Rc<LoanPath>,
 196     cmt: mc::cmt,
 197     kind: ty::BorrowKind,
 198     restrictions: Vec<Restriction>,
 199     gen_scope: ast::NodeId,
 200     kill_scope: ast::NodeId,
 201     span: Span,
 202     cause: LoanCause,
 203 }
 204
 205 #[deriving(Eq)]
 206 pub enum LoanCause {
 207     ClosureCapture(Span),
 208     AddrOf,
 209     AutoRef,
 210     RefBinding,
 211     ClosureInvocation,
 212 }
 213
 214 #[deriving(Eq, TotalEq, Hash)]
 215 pub enum LoanPath {
 216     LpVar(ast::NodeId),               // `x` in doc.rs
 217     LpExtend(Rc<LoanPath>, mc::MutabilityCategory, LoanPathElem)
 218 }
 219
 220 #[deriving(Eq, TotalEq, Hash)]
 221 pub enum LoanPathElem {
 222     LpDeref(mc::PointerKind),    // `*LV` in doc.rs
 223     LpInterior(mc::InteriorKind) // `LV.f` in doc.rs
 224 }
 225
 226 impl LoanPath {
 227     pub fn node_id(&self) -> ast::NodeId {
 228         match *self {
 229             LpVar(local_id) => local_id,
 230             LpExtend(ref base, _, _) => base.node_id()
 231         }
 232     }
 233 }
 234
 235 pub fn opt_loan_path(cmt: &mc::cmt) -> Option<Rc<LoanPath>> {
 236     //! Computes the `LoanPath` (if any) for a `cmt`.
 237     //! Note that this logic is somewhat duplicated in
 238     //! the method `compute()` found in `gather_loans::restrictions`,
 239     //! which allows it to share common loan path pieces as it
 240     //! traverses the CMT.
 241
 242     match cmt.cat {
 243         mc::cat_rvalue(..) |
 244         mc::cat_static_item |
 245         mc::cat_copied_upvar(mc::CopiedUpvar { onceness: ast::Many, .. }) => {
 246             None
 247         }
 248
 249         mc::cat_local(id) |
 250         mc::cat_arg(id) |
 251         mc::cat_copied_upvar(mc::CopiedUpvar { upvar_id: id, .. }) |
 252         mc::cat_upvar(ty::UpvarId {var_id: id, ..}, _) => {
 253             Some(Rc::new(LpVar(id)))
 254         }
 255
 256         mc::cat_deref(ref cmt_base, _, pk) => {
 257             opt_loan_path(cmt_base).map(|lp| {
 258                 Rc::new(LpExtend(lp, cmt.mutbl, LpDeref(pk)))
 259             })
 260         }
 261
 262         mc::cat_interior(ref cmt_base, ik) => {
 263             opt_loan_path(cmt_base).map(|lp| {
 264                 Rc::new(LpExtend(lp, cmt.mutbl, LpInterior(ik)))
 265             })
 266         }
 267
 268         mc::cat_downcast(ref cmt_base) |
 269         mc::cat_discr(ref cmt_base, _) => {
 270             opt_loan_path(cmt_base)
 271         }
 272     }
 273 }
 274
 275 ///////////////////////////////////////////////////////////////////////////
 276 // Restrictions
 277 //
 278 // Borrowing an lvalue often results in *restrictions* that limit what
 279 // can be done with this lvalue during the scope of the loan:
 280 //
 281 // - `RESTR_MUTATE`: The lvalue may not be modified or `&mut` borrowed.
 282 // - `RESTR_FREEZE`: `&` borrows of the lvalue are forbidden.
 283 //
 284 // In addition, no value which is restricted may be moved. Therefore,
 285 // restrictions are meaningful even if the RestrictionSet is empty,
 286 // because the restriction against moves is implied.
 287
 288 pub struct Restriction {
 289     loan_path: Rc<LoanPath>,
 290     set: RestrictionSet
 291 }
 292
 293 #[deriving(Eq)]
 294 pub struct RestrictionSet {
 295     bits: u32
 296 }
 297
 298 #[allow(dead_code)] // potentially useful
 299 pub static RESTR_EMPTY: RestrictionSet  = RestrictionSet {bits: 0b0000};
 300 pub static RESTR_MUTATE: RestrictionSet = RestrictionSet {bits: 0b0001};
 301 pub static RESTR_FREEZE: RestrictionSet = RestrictionSet {bits: 0b0010};
 302
 303 impl RestrictionSet {
 304     pub fn intersects(&self, restr: RestrictionSet) -> bool {
 305         (self.bits & restr.bits) != 0
 306     }
 307 }
 308
 309 impl BitOr<RestrictionSet,RestrictionSet> for RestrictionSet {
 310     fn bitor(&self, rhs: &RestrictionSet) -> RestrictionSet {
 311         RestrictionSet {bits: self.bits | rhs.bits}
 312     }
 313 }
 314
 315 impl BitAnd<RestrictionSet,RestrictionSet> for RestrictionSet {
 316     fn bitand(&self, rhs: &RestrictionSet) -> RestrictionSet {
 317         RestrictionSet {bits: self.bits & rhs.bits}
 318     }
 319 }
 320
 321 impl Repr for RestrictionSet {
 322     fn repr(&self, _tcx: &ty::ctxt) -> ~str {
 323         format!("RestrictionSet(0x{:x})", self.bits as uint)
 324     }
 325 }
 326
 327 ///////////////////////////////////////////////////////////////////////////
 328 // Errors
 329
 330 // Errors that can occur
 331 #[deriving(Eq)]
 332 pub enum bckerr_code {
 333     err_mutbl,
 334     err_out_of_scope(ty::Region, ty::Region), // superscope, subscope
 335     err_borrowed_pointer_too_short(
 336         ty::Region, ty::Region, RestrictionSet), // loan, ptr
 337 }
 338
 339 // Combination of an error code and the categorization of the expression
 340 // that caused it
 341 #[deriving(Eq)]
 342 pub struct BckError {
 343     span: Span,
 344     cause: LoanCause,
 345     cmt: mc::cmt,
 346     code: bckerr_code
 347 }
 348
 349 pub enum AliasableViolationKind {
 350     MutabilityViolation,
 351     BorrowViolation(LoanCause)
 352 }
 353
 354 pub enum MovedValueUseKind {
 355     MovedInUse,
 356     MovedInCapture,
 357 }
 358
 359 ///////////////////////////////////////////////////////////////////////////
 360 // Misc
 361
 362 impl<'a> BorrowckCtxt<'a> {
 363     pub fn is_subregion_of(&self, r_sub: ty::Region, r_sup: ty::Region)
 364                            -> bool {
 365         self.tcx.region_maps.is_subregion_of(r_sub, r_sup)
 366     }
 367
 368     pub fn is_subscope_of(&self, r_sub: ast::NodeId, r_sup: ast::NodeId)
 369                           -> bool {
 370         self.tcx.region_maps.is_subscope_of(r_sub, r_sup)
 371     }
 372
 373     pub fn is_move(&self, id: ast::NodeId) -> bool {
 374         self.moves_map.contains(&id)
 375     }
 376
 377     pub fn mc(&self) -> mc::MemCategorizationContext<&'a ty::ctxt> {
 378         mc::MemCategorizationContext {
 379             typer: self.tcx,
 380         }
 381     }
 382
 383     pub fn cat_expr(&self, expr: &ast::Expr) -> mc::cmt {
 384         match self.mc().cat_expr(expr) {
 385             Ok(c) => c,
 386             Err(()) => {
 387                 self.tcx.sess.span_bug(expr.span, "error in mem categorization");
 388             }
 389         }
 390     }
 391
 392     pub fn cat_expr_unadjusted(&self, expr: &ast::Expr) -> mc::cmt {
 393         match self.mc().cat_expr_unadjusted(expr) {
 394             Ok(c) => c,
 395             Err(()) => {
 396                 self.tcx.sess.span_bug(expr.span, "error in mem categorization");
 397             }
 398         }
 399     }
 400
 401     pub fn cat_expr_autoderefd(&self,
 402                                expr: &ast::Expr,
 403                                adj: &ty::AutoAdjustment)
 404                                -> mc::cmt {
 405         let r = match *adj {
 406             ty::AutoAddEnv(..) | ty::AutoObject(..) => {
 407                 // no autoderefs
 408                 self.mc().cat_expr_unadjusted(expr)
 409             }
 410
 411             ty::AutoDerefRef(
 412                 ty::AutoDerefRef {
 413                     autoderefs: autoderefs, ..}) => {
 414                 self.mc().cat_expr_autoderefd(expr, autoderefs)
 415             }
 416         };
 417
 418         match r {
 419             Ok(c) => c,
 420             Err(()) => {
 421                 self.tcx.sess.span_bug(expr.span,
 422                                        "error in mem categorization");
 423             }
 424         }
 425     }
 426
 427     pub fn cat_def(&self,
 428                    id: ast::NodeId,
 429                    span: Span,
 430                    ty: ty::t,
 431                    def: ast::Def)
 432                    -> mc::cmt {
 433         match self.mc().cat_def(id, span, ty, def) {
 434             Ok(c) => c,
 435             Err(()) => {
 436                 self.tcx.sess.span_bug(span, "error in mem categorization");
 437             }
 438         }
 439     }
 440
 441     pub fn cat_captured_var(&self,
 442                             id: ast::NodeId,
 443                             span: Span,
 444                             captured_var: &moves::CaptureVar) -> mc::cmt {
 445         // Create the cmt for the variable being borrowed, from the
 446         // caller's perspective
 447         let var_id = ast_util::def_id_of_def(captured_var.def).node;
 448         let var_ty = ty::node_id_to_type(self.tcx, var_id);
 449         self.cat_def(id, span, var_ty, captured_var.def)
 450     }
 451
 452     pub fn cat_discr(&self, cmt: mc::cmt, match_id: ast::NodeId) -> mc::cmt {
 453         Rc::new(mc::cmt_ {
 454             cat: mc::cat_discr(cmt.clone(), match_id),
 455             mutbl: cmt.mutbl.inherit(),
 456             ..*cmt
 457         })
 458     }
 459
 460     pub fn cat_pattern(&self,
 461                        cmt: mc::cmt,
 462                        pat: &ast::Pat,
 463                        op: |mc::cmt, &ast::Pat|) {
 464         let r = self.mc().cat_pattern(cmt, pat, |_,x,y| op(x,y));
 465         assert!(r.is_ok());
 466     }
 467
 468     pub fn report(&self, err: BckError) {
 469         self.span_err(
 470             err.span,
 471             self.bckerr_to_str(&err));
 472         self.note_and_explain_bckerr(err);
 473     }
 474
 475     pub fn report_use_of_moved_value(&self,
 476                                      use_span: Span,
 477                                      use_kind: MovedValueUseKind,
 478                                      lp: &LoanPath,
 479                                      move: &move_data::Move,
 480                                      moved_lp: &LoanPath) {
 481         let verb = match use_kind {
 482             MovedInUse => "use",
 483             MovedInCapture => "capture",
 484         };
 485
 486         match move.kind {
 487             move_data::Declared => {
 488                 self.tcx.sess.span_err(
 489                     use_span,
 490                     format!("{} of possibly uninitialized variable: `{}`",
 491                          verb,
 492                          self.loan_path_to_str(lp)));
 493             }
 494             _ => {
 495                 let partially = if lp == moved_lp {""} else {"partially "};
 496                 self.tcx.sess.span_err(
 497                     use_span,
 498                     format!("{} of {}moved value: `{}`",
 499                          verb,
 500                          partially,
 501                          self.loan_path_to_str(lp)));
 502             }
 503         }
 504
 505         match move.kind {
 506             move_data::Declared => {}
 507
 508             move_data::MoveExpr => {
 509                 let (expr_ty, expr_span) = match self.tcx.map.find(move.id) {
 510                     Some(ast_map::NodeExpr(expr)) => {
 511                         (ty::expr_ty_adjusted(self.tcx, expr), expr.span)
 512                     }
 513                     r => self.tcx.sess.bug(format!("MoveExpr({:?}) maps to {:?}, not Expr",
 514                                                    move.id, r))
 515                 };
 516                 let suggestion = move_suggestion(self.tcx, expr_ty,
 517                         "moved by default (use `copy` to override)");
 518                 self.tcx.sess.span_note(
 519                     expr_span,
 520                     format!("`{}` moved here because it has type `{}`, which is {}",
 521                          self.loan_path_to_str(moved_lp),
 522                          expr_ty.user_string(self.tcx), suggestion));
 523             }
 524
 525             move_data::MovePat => {
 526                 let pat_ty = ty::node_id_to_type(self.tcx, move.id);
 527                 self.tcx.sess.span_note(self.tcx.map.span(move.id),
 528                     format!("`{}` moved here because it has type `{}`, \
 529                           which is moved by default (use `ref` to override)",
 530                          self.loan_path_to_str(moved_lp),
 531                          pat_ty.user_string(self.tcx)));
 532             }
 533
 534             move_data::Captured => {
 535                 let (expr_ty, expr_span) = match self.tcx.map.find(move.id) {
 536                     Some(ast_map::NodeExpr(expr)) => {
 537                         (ty::expr_ty_adjusted(self.tcx, expr), expr.span)
 538                     }
 539                     r => self.tcx.sess.bug(format!("Captured({:?}) maps to {:?}, not Expr",
 540                                                    move.id, r))
 541                 };
 542                 let suggestion = move_suggestion(self.tcx, expr_ty,
 543                         "moved by default (make a copy and \
 544                          capture that instead to override)");
 545                 self.tcx.sess.span_note(
 546                     expr_span,
 547                     format!("`{}` moved into closure environment here because it \
 548                           has type `{}`, which is {}",
 549                          self.loan_path_to_str(moved_lp),
 550                          expr_ty.user_string(self.tcx), suggestion));
 551             }
 552         }
 553
 554         fn move_suggestion(tcx: &ty::ctxt, ty: ty::t, default_msg: &'static str)
 555                           -> &'static str {
 556             match ty::get(ty).sty {
 557                 ty::ty_closure(~ty::ClosureTy { store: ty::RegionTraitStore(..), .. }) =>
 558                     "a non-copyable stack closure (capture it in a new closure, \
 559                      e.g. `|x| f(x)`, to override)",
 560                 _ if ty::type_moves_by_default(tcx, ty) =>
 561                     "non-copyable (perhaps you meant to use clone()?)",
 562                 _ => default_msg,
 563             }
 564         }
 565     }
 566
 567     pub fn report_reassigned_immutable_variable(&self,
 568                                                 span: Span,
 569                                                 lp: &LoanPath,
 570                                                 assign:
 571                                                 &move_data::Assignment) {
 572         self.tcx.sess.span_err(
 573             span,
 574             format!("re-assignment of immutable variable `{}`",
 575                  self.loan_path_to_str(lp)));
 576         self.tcx.sess.span_note(
 577             assign.span,
 578             format!("prior assignment occurs here"));
 579     }
 580
 581     pub fn span_err(&self, s: Span, m: &str) {
 582         self.tcx.sess.span_err(s, m);
 583     }
 584
 585     pub fn span_note(&self, s: Span, m: &str) {
 586         self.tcx.sess.span_note(s, m);
 587     }
 588
 589     pub fn span_end_note(&self, s: Span, m: &str) {
 590         self.tcx.sess.span_end_note(s, m);
 591     }
 592
 593     pub fn bckerr_to_str(&self, err: &BckError) -> ~str {
 594         match err.code {
 595             err_mutbl => {
 596                 let descr = match opt_loan_path(&err.cmt) {
 597                     None => format!("{} {}",
 598                                     err.cmt.mutbl.to_user_str(),
 599                                     self.cmt_to_str(&*err.cmt)),
 600                     Some(lp) => format!("{} {} `{}`",
 601                                         err.cmt.mutbl.to_user_str(),
 602                                         self.cmt_to_str(&*err.cmt),
 603                                         self.loan_path_to_str(&*lp)),
 604                 };
 605
 606                 match err.cause {
 607                     ClosureCapture(_) => {
 608                         format!("closure cannot assign to {}", descr)
 609                     }
 610                     AddrOf | RefBinding | AutoRef => {
 611                         format!("cannot borrow {} as mutable", descr)
 612                     }
 613                     ClosureInvocation => {
 614                         self.tcx.sess.span_bug(err.span,
 615                             "err_mutbl with a closure invocation");
 616                     }
 617                 }
 618             }
 619             err_out_of_scope(..) => {
 620                 let msg = match opt_loan_path(&err.cmt) {
 621                     None => format!("borrowed value"),
 622                     Some(lp) => format!("`{}`", self.loan_path_to_str(&*lp)),
 623                 };
 624                 format!("{} does not live long enough", msg)
 625             }
 626             err_borrowed_pointer_too_short(..) => {
 627                 let descr = match opt_loan_path(&err.cmt) {
 628                     Some(lp) => format!("`{}`", self.loan_path_to_str(&*lp)),
 629                     None => self.cmt_to_str(&*err.cmt),
 630                 };
 631
 632                 format!("lifetime of {} is too short to guarantee \
 633                         its contents can be safely reborrowed",
 634                         descr)
 635             }
 636         }
 637     }
 638
 639     pub fn report_aliasability_violation(&self,
 640                                          span: Span,
 641                                          kind: AliasableViolationKind,
 642                                          cause: mc::AliasableReason) {
 643         let prefix = match kind {
 644             MutabilityViolation => {
 645                 "cannot assign to data"
 646             }
 647             BorrowViolation(ClosureCapture(_)) => {
 648                 // I don't think we can get aliasability violations
 649                 // with closure captures, so no need to come up with a
 650                 // good error message. The reason this cannot happen
 651                 // is because we only capture local variables in
 652                 // closures, and those are never aliasable.
 653                 self.tcx.sess.span_bug(
 654                     span,
 655                     "aliasability violation with closure");
 656             }
 657             BorrowViolation(AddrOf) |
 658             BorrowViolation(AutoRef) |
 659             BorrowViolation(RefBinding) => {
 660                 "cannot borrow data mutably"
 661             }
 662
 663             BorrowViolation(ClosureInvocation) => {
 664                 "closure invocation"
 665             }
 666         };
 667
 668         match cause {
 669             mc::AliasableOther => {
 670                 self.tcx.sess.span_err(
 671                     span,
 672                     format!("{} in an aliasable location", prefix));
 673             }
 674             mc::AliasableStatic(..) |
 675             mc::AliasableStaticMut(..) => {
 676                 self.tcx.sess.span_err(
 677                     span,
 678                     format!("{} in a static location", prefix));
 679             }
 680             mc::AliasableManaged => {
 681                 self.tcx.sess.span_err(
 682                     span,
 683                     format!("{} in a `@` pointer", prefix));
 684             }
 685             mc::AliasableBorrowed => {
 686                 self.tcx.sess.span_err(
 687                     span,
 688                     format!("{} in a `&` reference", prefix));
 689             }
 690         }
 691     }
 692
 693     pub fn note_and_explain_bckerr(&self, err: BckError) {
 694         let code = err.code;
 695         match code {
 696             err_mutbl(..) => { }
 697
 698             err_out_of_scope(super_scope, sub_scope) => {
 699                 note_and_explain_region(
 700                     self.tcx,
 701                     "reference must be valid for ",
 702                     sub_scope,
 703                     "...");
 704                 note_and_explain_region(
 705                     self.tcx,
 706                     "...but borrowed value is only valid for ",
 707                     super_scope,
 708                     "");
 709             }
 710
 711             err_borrowed_pointer_too_short(loan_scope, ptr_scope, _) => {
 712                 let descr = match opt_loan_path(&err.cmt) {
 713                     Some(lp) => format!("`{}`", self.loan_path_to_str(&*lp)),
 714                     None => self.cmt_to_str(&*err.cmt),
 715                 };
 716                 note_and_explain_region(
 717                     self.tcx,
 718                     format!("{} would have to be valid for ", descr),
 719                     loan_scope,
 720                     "...");
 721                 note_and_explain_region(
 722                     self.tcx,
 723                     format!("...but {} is only valid for ", descr),
 724                     ptr_scope,
 725                     "");
 726             }
 727         }
 728     }
 729
 730     pub fn append_loan_path_to_str(&self,
 731                                    loan_path: &LoanPath,
 732                                    out: &mut StrBuf) {
 733         match *loan_path {
 734             LpVar(id) => {
 735                 out.push_str(ty::local_var_name_str(self.tcx, id).get());
 736             }
 737
 738             LpExtend(ref lp_base, _, LpInterior(mc::InteriorField(fname))) => {
 739                 self.append_autoderefd_loan_path_to_str(&**lp_base, out);
 740                 match fname {
 741                     mc::NamedField(fname) => {
 742                         out.push_char('.');
 743                         out.push_str(token::get_name(fname).get());
 744                     }
 745                     mc::PositionalField(idx) => {
 746                         out.push_char('#'); // invent a notation here
 747                         out.push_str(idx.to_str());
 748                     }
 749                 }
 750             }
 751
 752             LpExtend(ref lp_base, _, LpInterior(mc::InteriorElement(_))) => {
 753                 self.append_autoderefd_loan_path_to_str(&**lp_base, out);
 754                 out.push_str("[..]");
 755             }
 756
 757             LpExtend(ref lp_base, _, LpDeref(_)) => {
 758                 out.push_char('*');
 759                 self.append_loan_path_to_str(&**lp_base, out);
 760             }
 761         }
 762     }
 763
 764     pub fn append_autoderefd_loan_path_to_str(&self,
 765                                               loan_path: &LoanPath,
 766                                               out: &mut StrBuf) {
 767         match *loan_path {
 768             LpExtend(ref lp_base, _, LpDeref(_)) => {
 769                 // For a path like `(*x).f` or `(*x)[3]`, autoderef
 770                 // rules would normally allow users to omit the `*x`.
 771                 // So just serialize such paths to `x.f` or x[3]` respectively.
 772                 self.append_autoderefd_loan_path_to_str(&**lp_base, out)
 773             }
 774
 775             LpVar(..) | LpExtend(_, _, LpInterior(..)) => {
 776                 self.append_loan_path_to_str(loan_path, out)
 777             }
 778         }
 779     }
 780
 781     pub fn loan_path_to_str(&self, loan_path: &LoanPath) -> ~str {
 782         let mut result = StrBuf::new();
 783         self.append_loan_path_to_str(loan_path, &mut result);
 784         result.into_owned()
 785     }
 786
 787     pub fn cmt_to_str(&self, cmt: &mc::cmt_) -> ~str {
 788         self.mc().cmt_to_str(cmt)
 789     }
 790 }
 791
 792 impl DataFlowOperator for LoanDataFlowOperator {
 793     #[inline]
 794     fn initial_value(&self) -> bool {
 795         false // no loans in scope by default
 796     }
 797
 798     #[inline]
 799     fn join(&self, succ: uint, pred: uint) -> uint {
 800         succ | pred // loans from both preds are in scope
 801     }
 802 }
 803
 804 impl Repr for Loan {
 805     fn repr(&self, tcx: &ty::ctxt) -> ~str {
 806         format!("Loan_{:?}({}, {:?}, {:?}-{:?}, {})",
 807              self.index,
 808              self.loan_path.repr(tcx),
 809              self.kind,
 810              self.gen_scope,
 811              self.kill_scope,
 812              self.restrictions.repr(tcx))
 813     }
 814 }
 815
 816 impl Repr for Restriction {
 817     fn repr(&self, tcx: &ty::ctxt) -> ~str {
 818         format!("Restriction({}, {:x})",
 819              self.loan_path.repr(tcx),
 820              self.set.bits as uint)
 821     }
 822 }
 823
 824 impl Repr for LoanPath {
 825     fn repr(&self, tcx: &ty::ctxt) -> ~str {
 826         match self {
 827             &LpVar(id) => {
 828                 format!("$({})", tcx.map.node_to_str(id))
 829             }
 830
 831             &LpExtend(ref lp, _, LpDeref(_)) => {
 832                 format!("{}.*", lp.repr(tcx))
 833             }
 834
 835             &LpExtend(ref lp, _, LpInterior(ref interior)) => {
 836                 format!("{}.{}", lp.repr(tcx), interior.repr(tcx))
 837             }
 838         }
 839     }
 840 }
 841
 842 ///////////////////////////////////////////////////////////////////////////
 843
 844 impl<'a> mc::Typer for &'a ty::ctxt {
 845     fn tcx<'a>(&'a self) -> &'a ty::ctxt {
 846         *self
 847     }
 848
 849     fn node_ty(&self, id: ast::NodeId) -> mc::McResult<ty::t> {
 850         Ok(ty::node_id_to_type(*self, id))
 851     }
 852
 853     fn node_method_ty(&self, method_call: typeck::MethodCall) -> Option<ty::t> {
 854         self.method_map.borrow().find(&method_call).map(|method| method.ty)
 855     }
 856
 857     fn adjustments<'a>(&'a self) -> &'a RefCell<NodeMap<ty::AutoAdjustment>> {
 858         &self.adjustments
 859     }
 860
 861     fn is_method_call(&self, id: ast::NodeId) -> bool {
 862         self.method_map.borrow().contains_key(&typeck::MethodCall::expr(id))
 863     }
 864
 865     fn temporary_scope(&self, id: ast::NodeId) -> Option<ast::NodeId> {
 866         self.region_maps.temporary_scope(id)
 867     }
 868
 869     fn upvar_borrow(&self, id: ty::UpvarId) -> ty::UpvarBorrow {
 870         self.upvar_borrow_map.borrow().get_copy(&id)
 871     }
 872 }