mod.rs 29.3 KB
Newer Older
1 2 3 4 5 6 7 8 9 10
// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

N
Niko Matsakis 已提交
11
/*! See doc.rs for a thorough explanation of the borrow checker */
B
Brian Anderson 已提交
12

P
Patrick Walton 已提交
13

N
Niko Matsakis 已提交
14
use mc = middle::mem_categorization;
15
use middle::ty;
16
use middle::typeck;
17
use middle::moves;
N
Niko Matsakis 已提交
18 19
use middle::dataflow::DataFlowContext;
use middle::dataflow::DataFlowOperator;
A
Alex Crichton 已提交
20
use util::common::stmt_set;
21
use util::ppaux::{note_and_explain_region, Repr, UserString};
22

23 24 25
use std::hashmap::{HashSet, HashMap};
use std::ops::{BitOr, BitAnd};
use std::result::{Result};
26
use syntax::ast;
N
Niko Matsakis 已提交
27
use syntax::ast_map;
28
use syntax::codemap::Span;
29
use syntax::parse::token;
30 31
use syntax::visit;
use syntax::visit::{Visitor,fn_kind};
32
use syntax::ast::{P,fn_decl,Block,NodeId};
B
Brian Anderson 已提交
33

N
Niko Matsakis 已提交
34 35 36 37 38 39 40 41 42 43 44
macro_rules! if_ok(
    ($inp: expr) => (
        match $inp {
            Ok(v) => { v }
            Err(e) => { return Err(e); }
        }
    )
)

pub mod doc;

45
pub mod check_loans;
N
Niko Matsakis 已提交
46

47
pub mod gather_loans;
N
Niko Matsakis 已提交
48

49 50
pub mod move_data;

N
Niko Matsakis 已提交
51
pub struct LoanDataFlowOperator;
52 53 54 55 56 57 58 59 60

/// XXX(pcwalton): Should just be #[deriving(Clone)], but that doesn't work
/// yet on unit structs.
impl Clone for LoanDataFlowOperator {
    fn clone(&self) -> LoanDataFlowOperator {
        LoanDataFlowOperator
    }
}

N
Niko Matsakis 已提交
61
pub type LoanDataFlow = DataFlowContext<LoanDataFlowOperator>;
B
Brian Anderson 已提交
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 71 72 73
pub fn check_crate(
    tcx: ty::ctxt,
    method_map: typeck::method_map,
    moves_map: moves::MovesMap,
N
Niko Matsakis 已提交
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 80 81
        tcx: tcx,
        method_map: method_map,
        moves_map: moves_map,
N
Niko Matsakis 已提交
82
        moved_variables_set: moved_variables_set,
83 84
        capture_map: capture_map,
        root_map: root_map(),
N
Niko Matsakis 已提交
85
        loan_map: @mut HashMap::new(),
86 87
        write_guard_map: @mut HashSet::new(),
        stmt_map: @mut HashSet::new(),
88 89 90 91 92 93 94 95
        stats: @mut BorrowStats {
            loaned_paths_same: 0,
            loaned_paths_imm: 0,
            stable_paths: 0,
            req_pure_paths: 0,
            guaranteed_paths: 0,
        }
    };
96
    let bccx = &mut bccx;
B
Brian Anderson 已提交
97

98
    visit::walk_crate(bccx, crate, ());
B
Brian Anderson 已提交
99 100

    if tcx.sess.borrowck_stats() {
A
Alex Crichton 已提交
101
        println("--- borrowck stats ---");
102 103 104 105 106 107 108 109 110 111
        println!("paths requiring guarantees: {}",
                 bccx.stats.guaranteed_paths);
        println!("paths requiring loans     : {}",
                 make_stat(bccx, bccx.stats.loaned_paths_same));
        println!("paths requiring imm loans : {}",
                 make_stat(bccx, bccx.stats.loaned_paths_imm));
        println!("stable paths              : {}",
                 make_stat(bccx, bccx.stats.stable_paths));
        println!("paths requiring purity    : {}",
                 make_stat(bccx, bccx.stats.req_pure_paths));
B
Brian Anderson 已提交
112 113
    }

N
Niko Matsakis 已提交
114
    return (bccx.root_map, bccx.write_guard_map);
B
Brian Anderson 已提交
115

116
    fn make_stat(bccx: &mut BorrowckCtxt, stat: uint) -> ~str {
D
Daniel Micay 已提交
117 118 119
        let stat_f = stat as f64;
        let total = bccx.stats.guaranteed_paths as f64;
        format!("{} ({:.0f}%)", stat  , stat_f * 100.0 / total)
B
Brian Anderson 已提交
120 121 122
    }
}

123
fn borrowck_fn(this: &mut BorrowckCtxt,
124
               fk: &visit::fn_kind,
N
Niko Matsakis 已提交
125
               decl: &ast::fn_decl,
126
               body: ast::P<ast::Block>,
127
               sp: Span,
128
               id: ast::NodeId) {
N
Niko Matsakis 已提交
129
    match fk {
A
Alex Crichton 已提交
130
        &visit::fk_fn_block(..) => {
N
Niko Matsakis 已提交
131 132 133
            // Closures are checked as part of their containing fn item.
        }

A
Alex Crichton 已提交
134 135
        &visit::fk_item_fn(..) |
        &visit::fk_method(..) => {
136
            debug!("borrowck_fn(id={:?})", id);
N
Niko Matsakis 已提交
137 138

            // Check the body of fn items.
139
            let (id_range, all_loans, move_data) =
140
                gather_loans::gather_loans(this, decl, body);
141
            let mut loan_dfcx =
142 143
                DataFlowContext::new(this.tcx,
                                     this.method_map,
N
Niko Matsakis 已提交
144 145 146
                                     LoanDataFlowOperator,
                                     id_range,
                                     all_loans.len());
D
Daniel Micay 已提交
147
            for (loan_idx, loan) in all_loans.iter().enumerate() {
148 149
                loan_dfcx.add_gen(loan.gen_scope, loan_idx);
                loan_dfcx.add_kill(loan.kill_scope, loan_idx);
N
Niko Matsakis 已提交
150
            }
151 152 153 154 155 156 157 158 159 160
            loan_dfcx.propagate(body);

            let flowed_moves = move_data::FlowedMoveData::new(move_data,
                                                              this.tcx,
                                                              this.method_map,
                                                              id_range,
                                                              body);

            check_loans::check_loans(this, &loan_dfcx, flowed_moves,
                                     *all_loans, body);
N
Niko Matsakis 已提交
161 162 163
        }
    }

164
    visit::walk_fn(this, fk, decl, body, sp, id, ());
N
Niko Matsakis 已提交
165 166
}

B
Brian Anderson 已提交
167 168 169
// ----------------------------------------------------------------------
// Type definitions

170 171 172 173
pub struct BorrowckCtxt {
    tcx: ty::ctxt,
    method_map: typeck::method_map,
    moves_map: moves::MovesMap,
N
Niko Matsakis 已提交
174
    moved_variables_set: moves::MovedVariablesSet,
175 176
    capture_map: moves::CaptureMap,
    root_map: root_map,
N
Niko Matsakis 已提交
177
    loan_map: LoanMap,
178 179 180 181
    write_guard_map: write_guard_map,
    stmt_map: stmt_set,

    // Statistics:
182 183 184 185 186 187 188 189 190
    stats: @mut BorrowStats
}

pub struct BorrowStats {
    loaned_paths_same: uint,
    loaned_paths_imm: uint,
    stable_paths: uint,
    req_pure_paths: uint,
    guaranteed_paths: uint
B
Brian Anderson 已提交
191 192
}

193
pub type LoanMap = @mut HashMap<ast::NodeId, @Loan>;
B
Brian Anderson 已提交
194

195 196 197 198 199 200 201 202 203 204 205 206 207
// The keys to the root map combine the `id` of the deref expression
// with the number of types that it is *autodereferenced*. So, for
// example, imagine I have a variable `x: @@@T` and an expression
// `(*x).f`.  This will have 3 derefs, one explicit and then two
// autoderefs. These are the relevant `root_map_key` values that could
// appear:
//
//    {id:*x, derefs:0} --> roots `x` (type: @@@T, due to explicit deref)
//    {id:*x, derefs:1} --> roots `*x` (type: @@T, due to autoderef #1)
//    {id:*x, derefs:2} --> roots `**x` (type: @T, due to autoderef #2)
//
// Note that there is no entry with derefs:3---the type of that expression
// is T, which is not a box.
208 209 210 211 212 213 214 215 216 217
//
// Note that implicit dereferences also occur with indexing of `@[]`,
// `@str`, etc.  The same rules apply. So, for example, given a
// variable `x` of type `@[@[...]]`, if I have an instance of the
// expression `x[0]` which is then auto-slice'd, there would be two
// potential entries in the root map, both with the id of the `x[0]`
// expression. The entry with `derefs==0` refers to the deref of `x`
// used as part of evaluating `x[0]`. The entry with `derefs==1`
// refers to the deref of the `x[0]` that occurs as part of the
// auto-slice.
N
Niko Matsakis 已提交
218
#[deriving(Eq, IterBytes)]
219
pub struct root_map_key {
220
    id: ast::NodeId,
221 222
    derefs: uint
}
B
Brian Anderson 已提交
223

224 225
// A set containing IDs of expressions of gc'd type that need to have a write
// guard.
226
pub type write_guard_map = @mut HashSet<root_map_key>;
227

N
Niko Matsakis 已提交
228
pub type BckResult<T> = Result<T, BckError>;
B
Brian Anderson 已提交
229

230
#[deriving(Eq)]
N
Niko Matsakis 已提交
231 232 233
pub enum PartialTotal {
    Partial,   // Loan affects some portion
    Total      // Loan affects entire path
B
Brian Anderson 已提交
234 235
}

N
Niko Matsakis 已提交
236 237 238
///////////////////////////////////////////////////////////////////////////
// Loans and loan paths

239 240 241 242 243 244 245 246
#[deriving(Clone, Eq)]
pub enum LoanMutability {
    ImmutableMutability,
    ConstMutability,
    MutableMutability,
}

impl LoanMutability {
247
    pub fn from_ast_mutability(ast_mutability: ast::Mutability)
248 249
                               -> LoanMutability {
        match ast_mutability {
250 251
            ast::MutImmutable => ImmutableMutability,
            ast::MutMutable => MutableMutability,
252 253 254 255 256 257 258 259 260 261 262 263 264 265
        }
    }
}

impl ToStr for LoanMutability {
    fn to_str(&self) -> ~str {
        match *self {
            ImmutableMutability => ~"immutable",
            ConstMutability => ~"read-only",
            MutableMutability => ~"mutable",
        }
    }
}

N
Niko Matsakis 已提交
266 267 268 269 270
/// Record of a loan that was issued.
pub struct Loan {
    index: uint,
    loan_path: @LoanPath,
    cmt: mc::cmt,
271
    mutbl: LoanMutability,
N
Niko Matsakis 已提交
272
    restrictions: ~[Restriction],
273 274
    gen_scope: ast::NodeId,
    kill_scope: ast::NodeId,
275
    span: Span,
276 277
}

278
#[deriving(Eq, IterBytes)]
N
Niko Matsakis 已提交
279
pub enum LoanPath {
280
    LpVar(ast::NodeId),               // `x` in doc.rs
N
Niko Matsakis 已提交
281 282
    LpExtend(@LoanPath, mc::MutabilityCategory, LoanPathElem)
}
B
Brian Anderson 已提交
283

284
#[deriving(Eq, IterBytes)]
N
Niko Matsakis 已提交
285
pub enum LoanPathElem {
N
Niko Matsakis 已提交
286
    LpDeref(mc::PointerKind),    // `*LV` in doc.rs
287
    LpInterior(mc::InteriorKind) // `LV.f` in doc.rs
288 289
}

290
impl LoanPath {
291
    pub fn node_id(&self) -> ast::NodeId {
N
Niko Matsakis 已提交
292 293 294 295 296
        match *self {
            LpVar(local_id) => local_id,
            LpExtend(base, _, _) => base.node_id()
        }
    }
297
}
B
Brian Anderson 已提交
298

N
Niko Matsakis 已提交
299 300 301 302 303 304 305 306
pub fn opt_loan_path(cmt: mc::cmt) -> Option<@LoanPath> {
    //! Computes the `LoanPath` (if any) for a `cmt`.
    //! Note that this logic is somewhat duplicated in
    //! the method `compute()` found in `gather_loans::restrictions`,
    //! which allows it to share common loan path pieces as it
    //! traverses the CMT.

    match cmt.cat {
A
Alex Crichton 已提交
307
        mc::cat_rvalue(..) |
N
Niko Matsakis 已提交
308
        mc::cat_static_item |
N
Niko Matsakis 已提交
309
        mc::cat_copied_upvar(_) => {
N
Niko Matsakis 已提交
310 311 312 313
            None
        }

        mc::cat_local(id) |
314
        mc::cat_arg(id) |
N
Niko Matsakis 已提交
315 316 317 318
        mc::cat_self(id) => {
            Some(@LpVar(id))
        }

N
Niko Matsakis 已提交
319
        mc::cat_deref(cmt_base, _, pk) => {
320
            opt_loan_path(cmt_base).map(|lp| {
N
Niko Matsakis 已提交
321
                @LpExtend(lp, cmt.mutbl, LpDeref(pk))
322
            })
N
Niko Matsakis 已提交
323 324 325
        }

        mc::cat_interior(cmt_base, ik) => {
326
            opt_loan_path(cmt_base).map(|lp| {
327
                @LpExtend(lp, cmt.mutbl, LpInterior(ik))
328
            })
N
Niko Matsakis 已提交
329 330
        }

331
        mc::cat_downcast(cmt_base) |
N
Niko Matsakis 已提交
332 333 334 335 336
        mc::cat_stack_upvar(cmt_base) |
        mc::cat_discr(cmt_base, _) => {
            opt_loan_path(cmt_base)
        }
    }
337
}
B
Brian Anderson 已提交
338

N
Niko Matsakis 已提交
339 340 341 342 343 344
///////////////////////////////////////////////////////////////////////////
// Restrictions
//
// Borrowing an lvalue often results in *restrictions* that limit what
// can be done with this lvalue during the scope of the loan:
//
345 346 347 348
// - `RESTR_MUTATE`: The lvalue may not be modified.
// - `RESTR_CLAIM`: `&mut` borrows of the lvalue are forbidden.
// - `RESTR_FREEZE`: `&` borrows of the lvalue are forbidden.
// - `RESTR_ALIAS`: All borrows of the lvalue are forbidden.
N
Niko Matsakis 已提交
349 350 351 352 353 354 355 356
//
// In addition, no value which is restricted may be moved. Therefore,
// restrictions are meaningful even if the RestrictionSet is empty,
// because the restriction against moves is implied.

pub struct Restriction {
    loan_path: @LoanPath,
    set: RestrictionSet
357 358
}

359
#[deriving(Eq)]
N
Niko Matsakis 已提交
360 361
pub struct RestrictionSet {
    bits: u32
B
Brian Anderson 已提交
362 363
}

364 365 366 367 368
pub static RESTR_EMPTY: RestrictionSet  = RestrictionSet {bits: 0b0000};
pub static RESTR_MUTATE: RestrictionSet = RestrictionSet {bits: 0b0001};
pub static RESTR_CLAIM: RestrictionSet  = RestrictionSet {bits: 0b0010};
pub static RESTR_FREEZE: RestrictionSet = RestrictionSet {bits: 0b0100};
pub static RESTR_ALIAS: RestrictionSet  = RestrictionSet {bits: 0b1000};
N
Niko Matsakis 已提交
369

370 371
impl RestrictionSet {
    pub fn intersects(&self, restr: RestrictionSet) -> bool {
N
Niko Matsakis 已提交
372
        (self.bits & restr.bits) != 0
373 374
    }

375
    pub fn contains_all(&self, restr: RestrictionSet) -> bool {
N
Niko Matsakis 已提交
376
        (self.bits & restr.bits) == restr.bits
377 378 379
    }
}

N
Niko Matsakis 已提交
380 381 382 383 384
impl BitOr<RestrictionSet,RestrictionSet> for RestrictionSet {
    fn bitor(&self, rhs: &RestrictionSet) -> RestrictionSet {
        RestrictionSet {bits: self.bits | rhs.bits}
    }
}
B
Brian Anderson 已提交
385

N
Niko Matsakis 已提交
386 387 388
impl BitAnd<RestrictionSet,RestrictionSet> for RestrictionSet {
    fn bitand(&self, rhs: &RestrictionSet) -> RestrictionSet {
        RestrictionSet {bits: self.bits & rhs.bits}
B
Brian Anderson 已提交
389 390 391
    }
}

N
Niko Matsakis 已提交
392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411
///////////////////////////////////////////////////////////////////////////
// Rooting of managed boxes
//
// When we borrow the interior of a managed box, it is sometimes
// necessary to *root* the box, meaning to stash a copy of the box
// somewhere that the garbage collector will find it. This ensures
// that the box is not collected for the lifetime of the borrow.
//
// As part of this rooting, we sometimes also freeze the box at
// runtime, meaning that we dynamically detect when the box is
// borrowed in incompatible ways.
//
// Both of these actions are driven through the `root_map`, which maps
// from a node to the dynamic rooting action that should be taken when
// that node executes. The node is identified through a
// `root_map_key`, which pairs a node-id and a deref count---the
// problem is that sometimes the box that needs to be rooted is only
// uncovered after a certain number of auto-derefs.

pub struct RootInfo {
412
    scope: ast::NodeId,
N
Niko Matsakis 已提交
413 414 415 416 417
    freeze: Option<DynaFreezeKind> // Some() if we should freeze box at runtime
}

pub type root_map = @mut HashMap<root_map_key, RootInfo>;

418
pub fn root_map() -> root_map {
419
    return @mut HashMap::new();
B
Brian Anderson 已提交
420 421
}

N
Niko Matsakis 已提交
422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441
pub enum DynaFreezeKind {
    DynaImm,
    DynaMut
}

impl ToStr for DynaFreezeKind {
    fn to_str(&self) -> ~str {
        match *self {
            DynaMut => ~"mutable",
            DynaImm => ~"immutable"
        }
    }
}

///////////////////////////////////////////////////////////////////////////
// Errors

// Errors that can occur
#[deriving(Eq)]
pub enum bckerr_code {
442
    err_mutbl(LoanMutability),
N
Niko Matsakis 已提交
443 444
    err_out_of_root_scope(ty::Region, ty::Region), // superscope, subscope
    err_out_of_scope(ty::Region, ty::Region), // superscope, subscope
445
    err_freeze_aliasable_const,
446 447
    err_borrowed_pointer_too_short(
        ty::Region, ty::Region, RestrictionSet), // loan, ptr
N
Niko Matsakis 已提交
448 449 450 451 452 453
}

// Combination of an error code and the categorization of the expression
// that caused it
#[deriving(Eq)]
pub struct BckError {
454
    span: Span,
N
Niko Matsakis 已提交
455 456 457 458 459 460 461 462 463
    cmt: mc::cmt,
    code: bckerr_code
}

pub enum AliasableViolationKind {
    MutabilityViolation,
    BorrowViolation
}

464 465 466 467 468
pub enum MovedValueUseKind {
    MovedInUse,
    MovedInCapture,
}

N
Niko Matsakis 已提交
469
///////////////////////////////////////////////////////////////////////////
B
Brian Anderson 已提交
470 471
// Misc

472 473 474
impl BorrowckCtxt {
    pub fn is_subregion_of(&self, r_sub: ty::Region, r_sup: ty::Region)
                           -> bool {
475
        self.tcx.region_maps.is_subregion_of(r_sub, r_sup)
B
Brian Anderson 已提交
476 477
    }

478
    pub fn is_subscope_of(&self, r_sub: ast::NodeId, r_sup: ast::NodeId)
479
                          -> bool {
N
Niko Matsakis 已提交
480 481 482
        self.tcx.region_maps.is_subscope_of(r_sub, r_sup)
    }

483
    pub fn is_move(&self, id: ast::NodeId) -> bool {
484 485 486
        self.moves_map.contains(&id)
    }

487
    pub fn cat_expr(&self, expr: @ast::Expr) -> mc::cmt {
N
Niko Matsakis 已提交
488
        mc::cat_expr(self.tcx, self.method_map, expr)
B
Brian Anderson 已提交
489 490
    }

491
    pub fn cat_expr_unadjusted(&self, expr: @ast::Expr) -> mc::cmt {
N
Niko Matsakis 已提交
492
        mc::cat_expr_unadjusted(self.tcx, self.method_map, expr)
B
Brian Anderson 已提交
493 494
    }

495
    pub fn cat_expr_autoderefd(&self,
496
                               expr: @ast::Expr,
497 498
                               adj: @ty::AutoAdjustment)
                               -> mc::cmt {
499
        match *adj {
A
Alex Crichton 已提交
500
            ty::AutoAddEnv(..) => {
501
                // no autoderefs
N
Niko Matsakis 已提交
502
                mc::cat_expr_unadjusted(self.tcx, self.method_map, expr)
503 504 505 506
            }

            ty::AutoDerefRef(
                ty::AutoDerefRef {
A
Alex Crichton 已提交
507
                    autoderefs: autoderefs, ..}) => {
N
Niko Matsakis 已提交
508 509
                mc::cat_expr_autoderefd(self.tcx, self.method_map, expr,
                                        autoderefs)
510 511
            }
        }
B
Brian Anderson 已提交
512 513
    }

514
    pub fn cat_def(&self,
515
                   id: ast::NodeId,
516
                   span: Span,
517
                   ty: ty::t,
518
                   def: ast::Def)
519
                   -> mc::cmt {
N
Niko Matsakis 已提交
520
        mc::cat_def(self.tcx, self.method_map, id, span, ty, def)
B
Brian Anderson 已提交
521 522
    }

523
    pub fn cat_discr(&self, cmt: mc::cmt, match_id: ast::NodeId) -> mc::cmt {
N
Niko Matsakis 已提交
524 525 526
        @mc::cmt_ {cat:mc::cat_discr(cmt, match_id),
                   mutbl:cmt.mutbl.inherit(),
                   ..*cmt}
B
Brian Anderson 已提交
527 528
    }

529
    pub fn mc_ctxt(&self) -> mc::mem_categorization_ctxt {
N
Niko Matsakis 已提交
530
        mc::mem_categorization_ctxt {tcx: self.tcx,
531
                                     method_map: self.method_map}
532 533
    }

534 535
    pub fn cat_pattern(&self,
                       cmt: mc::cmt,
536
                       pat: @ast::Pat,
537
                       op: |mc::cmt, @ast::Pat|) {
538
        let mc = self.mc_ctxt();
B
Brian Anderson 已提交
539 540 541
        mc.cat_pattern(cmt, pat, op);
    }

542
    pub fn report(&self, err: BckError) {
B
Brian Anderson 已提交
543
        self.span_err(
N
Niko Matsakis 已提交
544 545
            err.span,
            self.bckerr_to_str(err));
B
Brian Anderson 已提交
546 547 548
        self.note_and_explain_bckerr(err);
    }

549
    pub fn report_use_of_moved_value(&self,
550
                                     use_span: Span,
551
                                     use_kind: MovedValueUseKind,
552
                                     lp: &LoanPath,
553 554
                                     move: &move_data::Move,
                                     moved_lp: @LoanPath) {
555 556 557 558 559 560 561 562 563
        let verb = match use_kind {
            MovedInUse => "use",
            MovedInCapture => "capture",
        };

        match move.kind {
            move_data::Declared => {
                self.tcx.sess.span_err(
                    use_span,
A
Alex Crichton 已提交
564
                    format!("{} of possibly uninitialized value: `{}`",
565 566 567 568 569 570 571
                         verb,
                         self.loan_path_to_str(lp)));
            }
            _ => {
                let partially = if lp == moved_lp {""} else {"partially "};
                self.tcx.sess.span_err(
                    use_span,
A
Alex Crichton 已提交
572
                    format!("{} of {}moved value: `{}`",
573 574 575 576 577 578 579 580 581 582 583
                         verb,
                         partially,
                         self.loan_path_to_str(lp)));
            }
        }

        match move.kind {
            move_data::Declared => {}

            move_data::MoveExpr(expr) => {
                let expr_ty = ty::expr_ty_adjusted(self.tcx, expr);
584 585
                let suggestion = move_suggestion(self.tcx, expr_ty,
                        "moved by default (use `copy` to override)");
586 587
                self.tcx.sess.span_note(
                    expr.span,
A
Alex Crichton 已提交
588
                    format!("`{}` moved here because it has type `{}`, which is {}",
589
                         self.loan_path_to_str(moved_lp),
590
                         expr_ty.user_string(self.tcx), suggestion));
591 592 593 594 595 596
            }

            move_data::MovePat(pat) => {
                let pat_ty = ty::node_id_to_type(self.tcx, pat.id);
                self.tcx.sess.span_note(
                    pat.span,
A
Alex Crichton 已提交
597
                    format!("`{}` moved here because it has type `{}`, \
598 599 600 601 602 603
                          which is moved by default (use `ref` to override)",
                         self.loan_path_to_str(moved_lp),
                         pat_ty.user_string(self.tcx)));
            }

            move_data::Captured(expr) => {
604 605 606 607
                let expr_ty = ty::expr_ty_adjusted(self.tcx, expr);
                let suggestion = move_suggestion(self.tcx, expr_ty,
                        "moved by default (make a copy and \
                         capture that instead to override)");
608 609
                self.tcx.sess.span_note(
                    expr.span,
A
Alex Crichton 已提交
610 611
                    format!("`{}` moved into closure environment here because it \
                          has type `{}`, which is {}",
612 613 614 615 616 617 618 619 620 621 622
                         self.loan_path_to_str(moved_lp),
                         expr_ty.user_string(self.tcx), suggestion));
            }
        }

        fn move_suggestion(tcx: ty::ctxt, ty: ty::t, default_msg: &'static str)
                          -> &'static str {
            match ty::get(ty).sty {
                ty::ty_closure(ref cty) if cty.sigil == ast::BorrowedSigil =>
                    "a non-copyable stack closure (capture it in a new closure, \
                     e.g. `|x| f(x)`, to override)",
623
                _ if ty::type_moves_by_default(tcx, ty) =>
624 625
                    "non-copyable (perhaps you meant to use clone()?)",
                _ => default_msg,
626 627 628 629
            }
        }
    }

630
    pub fn report_reassigned_immutable_variable(&self,
631
                                                span: Span,
632
                                                lp: &LoanPath,
633 634
                                                assign:
                                                &move_data::Assignment) {
635 636
        self.tcx.sess.span_err(
            span,
A
Alex Crichton 已提交
637
            format!("re-assignment of immutable variable `{}`",
638 639 640
                 self.loan_path_to_str(lp)));
        self.tcx.sess.span_note(
            assign.span,
A
Alex Crichton 已提交
641
            format!("prior assignment occurs here"));
642 643
    }

644
    pub fn span_err(&self, s: Span, m: &str) {
B
Brian Anderson 已提交
645 646 647
        self.tcx.sess.span_err(s, m);
    }

648
    pub fn span_note(&self, s: Span, m: &str) {
B
Brian Anderson 已提交
649 650 651
        self.tcx.sess.span_note(s, m);
    }

652
    pub fn bckerr_to_str(&self, err: BckError) -> ~str {
B
Brian Anderson 已提交
653
        match err.code {
654
            err_mutbl(lk) => {
A
Alex Crichton 已提交
655
                format!("cannot borrow {} {} as {}",
N
Niko Matsakis 已提交
656 657 658
                     err.cmt.mutbl.to_user_str(),
                     self.cmt_to_str(err.cmt),
                     self.mut_to_str(lk))
B
Brian Anderson 已提交
659
            }
A
Alex Crichton 已提交
660
            err_out_of_root_scope(..) => {
A
Alex Crichton 已提交
661
                format!("cannot root managed value long enough")
B
Brian Anderson 已提交
662
            }
A
Alex Crichton 已提交
663
            err_out_of_scope(..) => {
A
Alex Crichton 已提交
664
                format!("borrowed value does not live long enough")
B
Brian Anderson 已提交
665
            }
N
Niko Matsakis 已提交
666 667 668 669 670
            err_freeze_aliasable_const => {
                // Means that the user borrowed a ~T or enum value
                // residing in &const or @const pointer.  Terrible
                // error message, but then &const and @const are
                // supposed to be going away.
A
Alex Crichton 已提交
671
                format!("unsafe borrow of aliasable, const value")
B
Brian Anderson 已提交
672
            }
N
Niko Matsakis 已提交
673
            err_borrowed_pointer_too_short(..) => {
674 675
                let descr = match opt_loan_path(err.cmt) {
                    Some(lp) => format!("`{}`", self.loan_path_to_str(lp)),
676
                    None => self.cmt_to_str(err.cmt),
677 678
                };

679 680 681
                format!("lifetime of {} is too short to guarantee \
                        its contents can be safely reborrowed",
                        descr)
682
            }
N
Niko Matsakis 已提交
683 684 685
        }
    }

686
    pub fn report_aliasability_violation(&self,
687
                                         span: Span,
688 689
                                         kind: AliasableViolationKind,
                                         cause: mc::AliasableReason) {
N
Niko Matsakis 已提交
690 691 692 693 694 695 696 697 698
        let prefix = match kind {
            MutabilityViolation => "cannot assign to an `&mut`",
            BorrowViolation => "cannot borrow an `&mut`"
        };

        match cause {
            mc::AliasableOther => {
                self.tcx.sess.span_err(
                    span,
A
Alex Crichton 已提交
699
                    format!("{} in an aliasable location", prefix));
B
Brian Anderson 已提交
700
            }
701
            mc::AliasableManaged(ast::MutMutable) => {
N
Niko Matsakis 已提交
702
                // FIXME(#6269) reborrow @mut to &mut
N
Niko Matsakis 已提交
703 704
                self.tcx.sess.span_err(
                    span,
A
Alex Crichton 已提交
705
                    format!("{} in a `@mut` pointer; \
N
Niko Matsakis 已提交
706 707 708 709 710
                          try borrowing as `&mut` first", prefix));
            }
            mc::AliasableManaged(m) => {
                self.tcx.sess.span_err(
                    span,
A
Alex Crichton 已提交
711
                    format!("{} in a `@{}` pointer; \
N
Niko Matsakis 已提交
712 713 714 715 716 717 718
                          try an `@mut` instead",
                         prefix,
                         self.mut_to_keyword(m)));
            }
            mc::AliasableBorrowed(m) => {
                self.tcx.sess.span_err(
                    span,
A
Alex Crichton 已提交
719
                    format!("{} in a `&{}` pointer; \
N
Niko Matsakis 已提交
720 721 722
                          try an `&mut` instead",
                         prefix,
                         self.mut_to_keyword(m)));
B
Brian Anderson 已提交
723 724 725 726
            }
        }
    }

727
    pub fn note_and_explain_bckerr(&self, err: BckError) {
B
Brian Anderson 已提交
728 729
        let code = err.code;
        match code {
A
Alex Crichton 已提交
730
            err_mutbl(..) | err_freeze_aliasable_const(..) => {}
B
Brian Anderson 已提交
731 732 733 734

            err_out_of_root_scope(super_scope, sub_scope) => {
                note_and_explain_region(
                    self.tcx,
735
                    "managed value would have to be rooted for ",
B
Brian Anderson 已提交
736
                    sub_scope,
737
                    "...");
B
Brian Anderson 已提交
738 739
                note_and_explain_region(
                    self.tcx,
740
                    "...but can only be rooted for ",
B
Brian Anderson 已提交
741
                    super_scope,
742
                    "");
B
Brian Anderson 已提交
743 744 745 746 747
            }

            err_out_of_scope(super_scope, sub_scope) => {
                note_and_explain_region(
                    self.tcx,
748
                    "borrowed pointer must be valid for ",
B
Brian Anderson 已提交
749
                    sub_scope,
750
                    "...");
B
Brian Anderson 已提交
751 752
                note_and_explain_region(
                    self.tcx,
753
                    "...but borrowed value is only valid for ",
B
Brian Anderson 已提交
754
                    super_scope,
755
                    "");
756 757
            }

758
            err_borrowed_pointer_too_short(loan_scope, ptr_scope, _) => {
759 760
                let descr = match opt_loan_path(err.cmt) {
                    Some(lp) => format!("`{}`", self.loan_path_to_str(lp)),
761
                    None => self.cmt_to_str(err.cmt),
762 763 764 765 766 767 768 769 770 771 772 773
                };
                note_and_explain_region(
                    self.tcx,
                    format!("{} would have to be valid for ", descr),
                    loan_scope,
                    "...");
                note_and_explain_region(
                    self.tcx,
                    format!("...but {} is only valid for ", descr),
                    ptr_scope,
                    "");
            }
B
Brian Anderson 已提交
774 775 776
        }
    }

777 778 779
    pub fn append_loan_path_to_str_from_interior(&self,
                                                 loan_path: &LoanPath,
                                                 out: &mut ~str) {
N
Niko Matsakis 已提交
780
        match *loan_path {
N
Niko Matsakis 已提交
781
            LpExtend(_, _, LpDeref(_)) => {
782
                out.push_char('(');
N
Niko Matsakis 已提交
783
                self.append_loan_path_to_str(loan_path, out);
784
                out.push_char(')');
N
Niko Matsakis 已提交
785 786 787 788 789 790 791 792
            }
            LpExtend(_, _, LpInterior(_)) |
            LpVar(_) => {
                self.append_loan_path_to_str(loan_path, out);
            }
        }
    }

793 794 795
    pub fn append_loan_path_to_str(&self,
                                   loan_path: &LoanPath,
                                   out: &mut ~str) {
N
Niko Matsakis 已提交
796 797 798
        match *loan_path {
            LpVar(id) => {
                match self.tcx.items.find(&id) {
799
                    Some(&ast_map::node_local(ref ident)) => {
800
                        out.push_str(token::ident_to_str(ident));
N
Niko Matsakis 已提交
801 802 803
                    }
                    r => {
                        self.tcx.sess.bug(
A
Alex Crichton 已提交
804
                            format!("Loan path LpVar({:?}) maps to {:?}, not local",
N
Niko Matsakis 已提交
805 806 807 808
                                 id, r));
                    }
                }
            }
B
Brian Anderson 已提交
809

810
            LpExtend(lp_base, _, LpInterior(mc::InteriorField(fname))) => {
N
Niko Matsakis 已提交
811
                self.append_loan_path_to_str_from_interior(lp_base, out);
812
                match fname {
813
                    mc::NamedField(ref fname) => {
814
                        out.push_char('.');
815
                        out.push_str(token::interner_get(*fname));
816 817
                    }
                    mc::PositionalField(idx) => {
818 819
                        out.push_char('#'); // invent a notation here
                        out.push_str(idx.to_str());
820 821
                    }
                }
N
Niko Matsakis 已提交
822 823
            }

824
            LpExtend(lp_base, _, LpInterior(mc::InteriorElement(_))) => {
N
Niko Matsakis 已提交
825
                self.append_loan_path_to_str_from_interior(lp_base, out);
826
                out.push_str("[]");
N
Niko Matsakis 已提交
827 828
            }

N
Niko Matsakis 已提交
829
            LpExtend(lp_base, _, LpDeref(_)) => {
830
                out.push_char('*');
N
Niko Matsakis 已提交
831 832 833 834 835
                self.append_loan_path_to_str(lp_base, out);
            }
        }
    }

836
    pub fn loan_path_to_str(&self, loan_path: &LoanPath) -> ~str {
N
Niko Matsakis 已提交
837 838 839
        let mut result = ~"";
        self.append_loan_path_to_str(loan_path, &mut result);
        result
B
Brian Anderson 已提交
840 841
    }

842
    pub fn cmt_to_str(&self, cmt: mc::cmt) -> ~str {
N
Niko Matsakis 已提交
843 844 845
        let mc = &mc::mem_categorization_ctxt {tcx: self.tcx,
                                               method_map: self.method_map};
        mc.cmt_to_str(cmt)
B
Brian Anderson 已提交
846 847
    }

848 849
    pub fn mut_to_str(&self, mutbl: LoanMutability) -> ~str {
        mutbl.to_str()
B
Brian Anderson 已提交
850 851
    }

852
    pub fn mut_to_keyword(&self, mutbl: ast::Mutability) -> &'static str {
N
Niko Matsakis 已提交
853
        match mutbl {
854 855
            ast::MutImmutable => "",
            ast::MutMutable => "mut",
856 857
        }
    }
N
Niko Matsakis 已提交
858 859 860
}

impl DataFlowOperator for LoanDataFlowOperator {
861
    #[inline]
N
Niko Matsakis 已提交
862 863 864 865
    fn initial_value(&self) -> bool {
        false // no loans in scope by default
    }

866
    #[inline]
N
Niko Matsakis 已提交
867 868 869 870
    fn join(&self, succ: uint, pred: uint) -> uint {
        succ | pred // loans from both preds are in scope
    }

871
    #[inline]
N
Niko Matsakis 已提交
872 873 874 875
    fn walk_closures(&self) -> bool {
        true
    }
}
876

N
Niko Matsakis 已提交
877 878
impl Repr for Loan {
    fn repr(&self, tcx: ty::ctxt) -> ~str {
A
Alex Crichton 已提交
879
        format!("Loan_{:?}({}, {:?}, {:?}-{:?}, {})",
N
Niko Matsakis 已提交
880 881 882 883 884 885
             self.index,
             self.loan_path.repr(tcx),
             self.mutbl,
             self.gen_scope,
             self.kill_scope,
             self.restrictions.repr(tcx))
B
Brian Anderson 已提交
886 887 888
    }
}

N
Niko Matsakis 已提交
889 890
impl Repr for Restriction {
    fn repr(&self, tcx: ty::ctxt) -> ~str {
A
Alex Crichton 已提交
891
        format!("Restriction({}, {:x})",
N
Niko Matsakis 已提交
892 893 894 895 896 897 898 899 900
             self.loan_path.repr(tcx),
             self.set.bits as uint)
    }
}

impl Repr for LoanPath {
    fn repr(&self, tcx: ty::ctxt) -> ~str {
        match self {
            &LpVar(id) => {
A
Alex Crichton 已提交
901
                format!("$({:?})", id)
N
Niko Matsakis 已提交
902 903
            }

N
Niko Matsakis 已提交
904
            &LpExtend(lp, _, LpDeref(_)) => {
A
Alex Crichton 已提交
905
                format!("{}.*", lp.repr(tcx))
N
Niko Matsakis 已提交
906 907 908
            }

            &LpExtend(lp, _, LpInterior(ref interior)) => {
A
Alex Crichton 已提交
909
                format!("{}.{}", lp.repr(tcx), interior.repr(tcx))
N
Niko Matsakis 已提交
910 911
            }
        }
B
Brian Anderson 已提交
912 913
    }
}