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