src/librustc/middle/borrowck/mod.rs

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