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