src/librustc/middle/expr_use_visitor.rs

   1 // Copyright 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 /*!
  12  * A different sort of visitor for walking fn bodies.  Unlike the
  13  * normal visitor, which just walks the entire body in one shot, the
  14  * `ExprUseVisitor` determines how expressions are being used.
  15  */
  16
  17 use middle::mem_categorization as mc;
  18 use middle::def;
  19 use middle::freevars;
  20 use middle::pat_util;
  21 use middle::ty;
  22 use middle::typeck::{MethodCall, MethodObject, MethodOrigin, MethodParam};
  23 use middle::typeck::{MethodStatic, MethodStaticUnboxedClosure};
  24 use middle::typeck;
  25 use util::ppaux::Repr;
  26
  27 use std::gc::Gc;
  28 use syntax::ast;
  29 use syntax::codemap::Span;
  30
  31 ///////////////////////////////////////////////////////////////////////////
  32 // The Delegate trait
  33
  34 /// This trait defines the callbacks you can expect to receive when
  35 /// employing the ExprUseVisitor.
  36 pub trait Delegate {
  37     // The value found at `cmt` is either copied or moved, depending
  38     // on mode.
  39     fn consume(&mut self,
  40                consume_id: ast::NodeId,
  41                consume_span: Span,
  42                cmt: mc::cmt,
  43                mode: ConsumeMode);
  44
  45     // The value found at `cmt` is either copied or moved via the
  46     // pattern binding `consume_pat`, depending on mode.
  47     fn consume_pat(&mut self,
  48                    consume_pat: &ast::Pat,
  49                    cmt: mc::cmt,
  50                    mode: ConsumeMode);
  51
  52     // The value found at `borrow` is being borrowed at the point
  53     // `borrow_id` for the region `loan_region` with kind `bk`.
  54     fn borrow(&mut self,
  55               borrow_id: ast::NodeId,
  56               borrow_span: Span,
  57               cmt: mc::cmt,
  58               loan_region: ty::Region,
  59               bk: ty::BorrowKind,
  60               loan_cause: LoanCause);
  61
  62     // The local variable `id` is declared but not initialized.
  63     fn decl_without_init(&mut self,
  64                          id: ast::NodeId,
  65                          span: Span);
  66
  67     // The path at `cmt` is being assigned to.
  68     fn mutate(&mut self,
  69               assignment_id: ast::NodeId,
  70               assignment_span: Span,
  71               assignee_cmt: mc::cmt,
  72               mode: MutateMode);
  73 }
  74
  75 #[deriving(PartialEq)]
  76 pub enum LoanCause {
  77     ClosureCapture(Span),
  78     AddrOf,
  79     AutoRef,
  80     RefBinding,
  81     OverloadedOperator,
  82     ClosureInvocation,
  83     ForLoop,
  84 }
  85
  86 #[deriving(PartialEq,Show)]
  87 pub enum ConsumeMode {
  88     Copy,                // reference to x where x has a type that copies
  89     Move(MoveReason),    // reference to x where x has a type that moves
  90 }
  91
  92 #[deriving(PartialEq,Show)]
  93 pub enum MoveReason {
  94     DirectRefMove,
  95     PatBindingMove,
  96     CaptureMove,
  97 }
  98
  99 #[deriving(PartialEq,Show)]
 100 pub enum MutateMode {
 101     Init,
 102     JustWrite,    // x = y
 103     WriteAndRead, // x += y
 104 }
 105
 106 enum OverloadedCallType {
 107     FnOverloadedCall,
 108     FnMutOverloadedCall,
 109     FnOnceOverloadedCall,
 110 }
 111
 112 impl OverloadedCallType {
 113     fn from_trait_id(tcx: &ty::ctxt, trait_id: ast::DefId)
 114                      -> OverloadedCallType {
 115         for &(maybe_function_trait, overloaded_call_type) in [
 116             (tcx.lang_items.fn_once_trait(), FnOnceOverloadedCall),
 117             (tcx.lang_items.fn_mut_trait(), FnMutOverloadedCall),
 118             (tcx.lang_items.fn_trait(), FnOverloadedCall)
 119         ].iter() {
 120             match maybe_function_trait {
 121                 Some(function_trait) if function_trait == trait_id => {
 122                     return overloaded_call_type
 123                 }
 124                 _ => continue,
 125             }
 126         }
 127
 128         tcx.sess.bug("overloaded call didn't map to known function trait")
 129     }
 130
 131     fn from_method_id(tcx: &ty::ctxt, method_id: ast::DefId)
 132                       -> OverloadedCallType {
 133         let method_descriptor = match ty::impl_or_trait_item(tcx, method_id) {
 134             ty::MethodTraitItem(ref method_descriptor) => {
 135                 (*method_descriptor).clone()
 136             }
 137         };
 138         let impl_id = match method_descriptor.container {
 139             ty::TraitContainer(_) => {
 140                 tcx.sess.bug("statically resolved overloaded call method \
 141                               belonged to a trait?!")
 142             }
 143             ty::ImplContainer(impl_id) => impl_id,
 144         };
 145         let trait_ref = match ty::impl_trait_ref(tcx, impl_id) {
 146             None => {
 147                 tcx.sess.bug("statically resolved overloaded call impl \
 148                               didn't implement a trait?!")
 149             }
 150             Some(ref trait_ref) => (*trait_ref).clone(),
 151         };
 152         OverloadedCallType::from_trait_id(tcx, trait_ref.def_id)
 153     }
 154
 155     fn from_unboxed_closure(tcx: &ty::ctxt, closure_did: ast::DefId)
 156                             -> OverloadedCallType {
 157         let trait_did =
 158             tcx.unboxed_closures
 159                .borrow()
 160                .find(&closure_did)
 161                .expect("OverloadedCallType::from_unboxed_closure: didn't \
 162                         find closure id")
 163                .kind
 164                .trait_did(tcx);
 165         OverloadedCallType::from_trait_id(tcx, trait_did)
 166     }
 167
 168     fn from_method_origin(tcx: &ty::ctxt, origin: &MethodOrigin)
 169                           -> OverloadedCallType {
 170         match *origin {
 171             MethodStatic(def_id) => {
 172                 OverloadedCallType::from_method_id(tcx, def_id)
 173             }
 174             MethodStaticUnboxedClosure(def_id) => {
 175                 OverloadedCallType::from_unboxed_closure(tcx, def_id)
 176             }
 177             MethodParam(ref method_param) => {
 178                 OverloadedCallType::from_trait_id(tcx, method_param.trait_id)
 179             }
 180             MethodObject(ref method_object) => {
 181                 OverloadedCallType::from_trait_id(tcx, method_object.trait_id)
 182             }
 183         }
 184     }
 185 }
 186
 187 ///////////////////////////////////////////////////////////////////////////
 188 // The ExprUseVisitor type
 189 //
 190 // This is the code that actually walks the tree. Like
 191 // mem_categorization, it requires a TYPER, which is a type that
 192 // supplies types from the tree. After type checking is complete, you
 193 // can just use the tcx as the typer.
 194
 195 pub struct ExprUseVisitor<'d,'t,TYPER:'t> {
 196     typer: &'t TYPER,
 197     mc: mc::MemCategorizationContext<'t,TYPER>,
 198     delegate: &'d mut Delegate+'d,
 199 }
 200
 201 // If the TYPER results in an error, it's because the type check
 202 // failed (or will fail, when the error is uncovered and reported
 203 // during writeback). In this case, we just ignore this part of the
 204 // code.
 205 //
 206 // Note that this macro appears similar to try!(), but, unlike try!(),
 207 // it does not propagate the error.
 208 macro_rules! return_if_err(
 209     ($inp: expr) => (
 210         match $inp {
 211             Ok(v) => v,
 212             Err(()) => return
 213         }
 214     )
 215 )
 216
 217 impl<'d,'t,'tcx,TYPER:mc::Typer<'tcx>> ExprUseVisitor<'d,'t,TYPER> {
 218     pub fn new(delegate: &'d mut Delegate,
 219                typer: &'t TYPER)
 220                -> ExprUseVisitor<'d,'t,TYPER> {
 221         ExprUseVisitor { typer: typer,
 222                          mc: mc::MemCategorizationContext::new(typer),
 223                          delegate: delegate }
 224     }
 225
 226     pub fn walk_fn(&mut self,
 227                    decl: &ast::FnDecl,
 228                    body: &ast::Block) {
 229         self.walk_arg_patterns(decl, body);
 230         self.walk_block(body);
 231     }
 232
 233     fn walk_arg_patterns(&mut self,
 234                          decl: &ast::FnDecl,
 235                          body: &ast::Block) {
 236         for arg in decl.inputs.iter() {
 237             let arg_ty = return_if_err!(self.typer.node_ty(arg.pat.id));
 238
 239             let arg_cmt = self.mc.cat_rvalue(
 240                 arg.id,
 241                 arg.pat.span,
 242                 ty::ReScope(body.id), // Args live only as long as the fn body.
 243                 arg_ty);
 244
 245             self.walk_pat(arg_cmt, arg.pat.clone());
 246         }
 247     }
 248
 249     fn tcx(&self) -> &'t ty::ctxt<'tcx> {
 250         self.typer.tcx()
 251     }
 252
 253     fn delegate_consume(&mut self,
 254                         consume_id: ast::NodeId,
 255                         consume_span: Span,
 256                         cmt: mc::cmt) {
 257         let mode = copy_or_move(self.tcx(), cmt.ty, DirectRefMove);
 258         self.delegate.consume(consume_id, consume_span, cmt, mode);
 259     }
 260
 261     fn consume_exprs(&mut self, exprs: &Vec<Gc<ast::Expr>>) {
 262         for expr in exprs.iter() {
 263             self.consume_expr(&**expr);
 264         }
 265     }
 266
 267     fn consume_expr(&mut self, expr: &ast::Expr) {
 268         debug!("consume_expr(expr={})", expr.repr(self.tcx()));
 269
 270         let cmt = return_if_err!(self.mc.cat_expr(expr));
 271         self.delegate_consume(expr.id, expr.span, cmt);
 272         self.walk_expr(expr);
 273     }
 274
 275     fn mutate_expr(&mut self,
 276                    assignment_expr: &ast::Expr,
 277                    expr: &ast::Expr,
 278                    mode: MutateMode) {
 279         let cmt = return_if_err!(self.mc.cat_expr(expr));
 280         self.delegate.mutate(assignment_expr.id, assignment_expr.span, cmt, mode);
 281         self.walk_expr(expr);
 282     }
 283
 284     fn borrow_expr(&mut self,
 285                    expr: &ast::Expr,
 286                    r: ty::Region,
 287                    bk: ty::BorrowKind,
 288                    cause: LoanCause) {
 289         debug!("borrow_expr(expr={}, r={}, bk={})",
 290                expr.repr(self.tcx()), r.repr(self.tcx()), bk.repr(self.tcx()));
 291
 292         let cmt = return_if_err!(self.mc.cat_expr(expr));
 293         self.delegate.borrow(expr.id, expr.span, cmt, r, bk, cause);
 294
 295         // Note: Unlike consume, we can ignore ExprParen. cat_expr
 296         // already skips over them, and walk will uncover any
 297         // attachments or whatever.
 298         self.walk_expr(expr)
 299     }
 300
 301     fn select_from_expr(&mut self, expr: &ast::Expr) {
 302         self.walk_expr(expr)
 303     }
 304
 305     pub fn walk_expr(&mut self, expr: &ast::Expr) {
 306         debug!("walk_expr(expr={})", expr.repr(self.tcx()));
 307
 308         self.walk_adjustment(expr);
 309
 310         match expr.node {
 311             ast::ExprParen(ref subexpr) => {
 312                 self.walk_expr(&**subexpr)
 313             }
 314
 315             ast::ExprPath(..) => { }
 316
 317             ast::ExprUnary(ast::UnDeref, ref base) => {      // *base
 318                 if !self.walk_overloaded_operator(expr, &**base, []) {
 319                     self.select_from_expr(&**base);
 320                 }
 321             }
 322
 323             ast::ExprField(ref base, _, _) => {         // base.f
 324                 self.select_from_expr(&**base);
 325             }
 326
 327             ast::ExprTupField(ref base, _, _) => {         // base.<n>
 328                 self.select_from_expr(&**base);
 329             }
 330
 331             ast::ExprIndex(ref lhs, ref rhs) => {           // lhs[rhs]
 332                 if !self.walk_overloaded_operator(expr, &**lhs, [rhs.clone()]) {
 333                     self.select_from_expr(&**lhs);
 334                     self.consume_expr(&**rhs);
 335                 }
 336             }
 337
 338             ast::ExprCall(ref callee, ref args) => {    // callee(args)
 339                 self.walk_callee(expr, &**callee);
 340                 self.consume_exprs(args);
 341             }
 342
 343             ast::ExprMethodCall(_, _, ref args) => { // callee.m(args)
 344                 self.consume_exprs(args);
 345             }
 346
 347             ast::ExprStruct(_, ref fields, ref opt_with) => {
 348                 self.walk_struct_expr(expr, fields, opt_with.clone());
 349             }
 350
 351             ast::ExprTup(ref exprs) => {
 352                 self.consume_exprs(exprs);
 353             }
 354
 355             ast::ExprIf(ref cond_expr, ref then_blk, ref opt_else_expr) => {
 356                 self.consume_expr(&**cond_expr);
 357                 self.walk_block(&**then_blk);
 358                 for else_expr in opt_else_expr.iter() {
 359                     self.consume_expr(&**else_expr);
 360                 }
 361             }
 362
 363             ast::ExprMatch(ref discr, ref arms) => {
 364                 // treatment of the discriminant is handled while
 365                 // walking the arms:
 366                 self.walk_expr(&**discr);
 367                 let discr_cmt = return_if_err!(self.mc.cat_expr(&**discr));
 368                 for arm in arms.iter() {
 369                     self.walk_arm(discr_cmt.clone(), arm);
 370                 }
 371             }
 372
 373             ast::ExprVec(ref exprs) => {
 374                 self.consume_exprs(exprs);
 375             }
 376
 377             ast::ExprAddrOf(m, ref base) => {   // &base
 378                 // make sure that the thing we are pointing out stays valid
 379                 // for the lifetime `scope_r` of the resulting ptr:
 380                 let expr_ty = ty::expr_ty(self.tcx(), expr);
 381                 if !ty::type_is_bot(expr_ty) {
 382                     let r = ty::ty_region(self.tcx(), expr.span, expr_ty);
 383                     let bk = ty::BorrowKind::from_mutbl(m);
 384                     self.borrow_expr(&**base, r, bk, AddrOf);
 385                 } else {
 386                     self.walk_expr(&**base);
 387                 }
 388             }
 389
 390             ast::ExprInlineAsm(ref ia) => {
 391                 for &(_, ref input) in ia.inputs.iter() {
 392                     self.consume_expr(&**input);
 393                 }
 394
 395                 for &(_, ref output, is_rw) in ia.outputs.iter() {
 396                     self.mutate_expr(expr, &**output,
 397                                            if is_rw { WriteAndRead } else { JustWrite });
 398                 }
 399             }
 400
 401             ast::ExprBreak(..) |
 402             ast::ExprAgain(..) |
 403             ast::ExprLit(..) => {}
 404
 405             ast::ExprLoop(ref blk, _) => {
 406                 self.walk_block(&**blk);
 407             }
 408
 409             ast::ExprWhile(ref cond_expr, ref blk, _) => {
 410                 self.consume_expr(&**cond_expr);
 411                 self.walk_block(&**blk);
 412             }
 413
 414             ast::ExprForLoop(ref pat, ref head, ref blk, _) => {
 415                 // The pattern lives as long as the block.
 416                 debug!("walk_expr for loop case: blk id={}", blk.id);
 417                 self.consume_expr(&**head);
 418
 419                 // Fetch the type of the value that the iteration yields to
 420                 // produce the pattern's categorized mutable type.
 421                 let pattern_type = return_if_err!(self.typer.node_ty(pat.id));
 422                 let pat_cmt = self.mc.cat_rvalue(pat.id,
 423                                                  pat.span,
 424                                                  ty::ReScope(blk.id),
 425                                                  pattern_type);
 426                 self.walk_pat(pat_cmt, pat.clone());
 427
 428                 self.walk_block(&**blk);
 429             }
 430
 431             ast::ExprUnary(_, ref lhs) => {
 432                 if !self.walk_overloaded_operator(expr, &**lhs, []) {
 433                     self.consume_expr(&**lhs);
 434                 }
 435             }
 436
 437             ast::ExprBinary(_, ref lhs, ref rhs) => {
 438                 if !self.walk_overloaded_operator(expr, &**lhs, [rhs.clone()]) {
 439                     self.consume_expr(&**lhs);
 440                     self.consume_expr(&**rhs);
 441                 }
 442             }
 443
 444             ast::ExprBlock(ref blk) => {
 445                 self.walk_block(&**blk);
 446             }
 447
 448             ast::ExprRet(ref opt_expr) => {
 449                 for expr in opt_expr.iter() {
 450                     self.consume_expr(&**expr);
 451                 }
 452             }
 453
 454             ast::ExprAssign(ref lhs, ref rhs) => {
 455                 self.mutate_expr(expr, &**lhs, JustWrite);
 456                 self.consume_expr(&**rhs);
 457             }
 458
 459             ast::ExprCast(ref base, _) => {
 460                 self.consume_expr(&**base);
 461             }
 462
 463             ast::ExprAssignOp(_, ref lhs, ref rhs) => {
 464                 // This will have to change if/when we support
 465                 // overloaded operators for `+=` and so forth.
 466                 self.mutate_expr(expr, &**lhs, WriteAndRead);
 467                 self.consume_expr(&**rhs);
 468             }
 469
 470             ast::ExprRepeat(ref base, ref count) => {
 471                 self.consume_expr(&**base);
 472                 self.consume_expr(&**count);
 473             }
 474
 475             ast::ExprFnBlock(..) |
 476             ast::ExprUnboxedFn(..) |
 477             ast::ExprProc(..) => {
 478                 self.walk_captures(expr)
 479             }
 480
 481             ast::ExprBox(ref place, ref base) => {
 482                 self.consume_expr(&**place);
 483                 self.consume_expr(&**base);
 484             }
 485
 486             ast::ExprMac(..) => {
 487                 self.tcx().sess.span_bug(
 488                     expr.span,
 489                     "macro expression remains after expansion");
 490             }
 491         }
 492     }
 493
 494     fn walk_callee(&mut self, call: &ast::Expr, callee: &ast::Expr) {
 495         let callee_ty = ty::expr_ty_adjusted(self.tcx(), callee);
 496         debug!("walk_callee: callee={} callee_ty={}",
 497                callee.repr(self.tcx()), callee_ty.repr(self.tcx()));
 498         match ty::get(callee_ty).sty {
 499             ty::ty_bare_fn(..) => {
 500                 self.consume_expr(callee);
 501             }
 502             ty::ty_closure(ref f) => {
 503                 match f.onceness {
 504                     ast::Many => {
 505                         self.borrow_expr(callee,
 506                                          ty::ReScope(call.id),
 507                                          ty::UniqueImmBorrow,
 508                                          ClosureInvocation);
 509                     }
 510                     ast::Once => {
 511                         self.consume_expr(callee);
 512                     }
 513                 }
 514             }
 515             _ => {
 516                 let overloaded_call_type =
 517                     match self.tcx()
 518                               .method_map
 519                               .borrow()
 520                               .find(&MethodCall::expr(call.id)) {
 521                     Some(ref method_callee) => {
 522                         OverloadedCallType::from_method_origin(
 523                             self.tcx(),
 524                             &method_callee.origin)
 525                     }
 526                     None => {
 527                         self.tcx().sess.span_bug(
 528                             callee.span,
 529                             format!("unexpected callee type {}",
 530                                     callee_ty.repr(self.tcx())).as_slice())
 531                     }
 532                 };
 533                 match overloaded_call_type {
 534                     FnMutOverloadedCall => {
 535                         self.borrow_expr(callee,
 536                                          ty::ReScope(call.id),
 537                                          ty::MutBorrow,
 538                                          ClosureInvocation);
 539                     }
 540                     FnOverloadedCall => {
 541                         self.borrow_expr(callee,
 542                                          ty::ReScope(call.id),
 543                                          ty::ImmBorrow,
 544                                          ClosureInvocation);
 545                     }
 546                     FnOnceOverloadedCall => self.consume_expr(callee),
 547                 }
 548             }
 549         }
 550     }
 551
 552     fn walk_stmt(&mut self, stmt: &ast::Stmt) {
 553         match stmt.node {
 554             ast::StmtDecl(ref decl, _) => {
 555                 match decl.node {
 556                     ast::DeclLocal(ref local) => {
 557                         self.walk_local(local.clone());
 558                     }
 559
 560                     ast::DeclItem(_) => {
 561                         // we don't visit nested items in this visitor,
 562                         // only the fn body we were given.
 563                     }
 564                 }
 565             }
 566
 567             ast::StmtExpr(ref expr, _) |
 568             ast::StmtSemi(ref expr, _) => {
 569                 self.consume_expr(&**expr);
 570             }
 571
 572             ast::StmtMac(..) => {
 573                 self.tcx().sess.span_bug(stmt.span, "unexpanded stmt macro");
 574             }
 575         }
 576     }
 577
 578     fn walk_local(&mut self, local: Gc<ast::Local>) {
 579         match local.init {
 580             None => {
 581                 let delegate = &mut self.delegate;
 582                 pat_util::pat_bindings(&self.typer.tcx().def_map, &*local.pat,
 583                                        |_, id, span, _| {
 584                     delegate.decl_without_init(id, span);
 585                 })
 586             }
 587
 588             Some(ref expr) => {
 589                 // Variable declarations with
 590                 // initializers are considered
 591                 // "assigns", which is handled by
 592                 // `walk_pat`:
 593                 self.walk_expr(&**expr);
 594                 let init_cmt = return_if_err!(self.mc.cat_expr(&**expr));
 595                 self.walk_pat(init_cmt, local.pat);
 596             }
 597         }
 598     }
 599
 600     fn walk_block(&mut self, blk: &ast::Block) {
 601         /*!
 602          * Indicates that the value of `blk` will be consumed,
 603          * meaning either copied or moved depending on its type.
 604          */
 605
 606         debug!("walk_block(blk.id={:?})", blk.id);
 607
 608         for stmt in blk.stmts.iter() {
 609             self.walk_stmt(&**stmt);
 610         }
 611
 612         for tail_expr in blk.expr.iter() {
 613             self.consume_expr(&**tail_expr);
 614         }
 615     }
 616
 617     fn walk_struct_expr(&mut self,
 618                         _expr: &ast::Expr,
 619                         fields: &Vec<ast::Field>,
 620                         opt_with: Option<Gc<ast::Expr>>) {
 621         // Consume the expressions supplying values for each field.
 622         for field in fields.iter() {
 623             self.consume_expr(&*field.expr);
 624         }
 625
 626         let with_expr = match opt_with {
 627             Some(ref w) => { w.clone() }
 628             None => { return; }
 629         };
 630
 631         let with_cmt = return_if_err!(self.mc.cat_expr(&*with_expr));
 632
 633         // Select just those fields of the `with`
 634         // expression that will actually be used
 635         let with_fields = match ty::get(with_cmt.ty).sty {
 636             ty::ty_struct(did, ref substs) => {
 637                 ty::struct_fields(self.tcx(), did, substs)
 638             }
 639             _ => {
 640                 self.tcx().sess.span_bug(
 641                     with_expr.span,
 642                     "with expression doesn't evaluate to a struct");
 643             }
 644         };
 645
 646         // Consume those fields of the with expression that are needed.
 647         for with_field in with_fields.iter() {
 648             if !contains_field_named(with_field, fields) {
 649                 let cmt_field = self.mc.cat_field(&*with_expr,
 650                                                   with_cmt.clone(),
 651                                                   with_field.ident,
 652                                                   with_field.mt.ty);
 653                 self.delegate_consume(with_expr.id, with_expr.span, cmt_field);
 654             }
 655         }
 656
 657         fn contains_field_named(field: &ty::field,
 658                                 fields: &Vec<ast::Field>)
 659                                 -> bool
 660         {
 661             fields.iter().any(
 662                 |f| f.ident.node.name == field.ident.name)
 663         }
 664     }
 665
 666     // Invoke the appropriate delegate calls for anything that gets
 667     // consumed or borrowed as part of the automatic adjustment
 668     // process.
 669     fn walk_adjustment(&mut self, expr: &ast::Expr) {
 670         let typer = self.typer;
 671         match typer.adjustments().borrow().find(&expr.id) {
 672             None => { }
 673             Some(adjustment) => {
 674                 match *adjustment {
 675                     ty::AutoAddEnv(..) => {
 676                         // Creating a closure consumes the input and stores it
 677                         // into the resulting rvalue.
 678                         debug!("walk_adjustment(AutoAddEnv)");
 679                         let cmt_unadjusted =
 680                             return_if_err!(self.mc.cat_expr_unadjusted(expr));
 681                         self.delegate_consume(expr.id, expr.span, cmt_unadjusted);
 682                     }
 683                     ty::AutoDerefRef(ty::AutoDerefRef {
 684                         autoref: ref opt_autoref,
 685                         autoderefs: n
 686                     }) => {
 687                         self.walk_autoderefs(expr, n);
 688
 689                         match *opt_autoref {
 690                             None => { }
 691                             Some(ref r) => {
 692                                 self.walk_autoref(expr, r, n);
 693                             }
 694                         }
 695                     }
 696                 }
 697             }
 698         }
 699     }
 700
 701     fn walk_autoderefs(&mut self,
 702                        expr: &ast::Expr,
 703                        autoderefs: uint) {
 704         /*!
 705          * Autoderefs for overloaded Deref calls in fact reference
 706          * their receiver. That is, if we have `(*x)` where `x` is of
 707          * type `Rc<T>`, then this in fact is equivalent to
 708          * `x.deref()`. Since `deref()` is declared with `&self`, this
 709          * is an autoref of `x`.
 710          */
 711         debug!("walk_autoderefs expr={} autoderefs={}", expr.repr(self.tcx()), autoderefs);
 712
 713         for i in range(0, autoderefs) {
 714             let deref_id = typeck::MethodCall::autoderef(expr.id, i);
 715             match self.typer.node_method_ty(deref_id) {
 716                 None => {}
 717                 Some(method_ty) => {
 718                     let cmt = return_if_err!(self.mc.cat_expr_autoderefd(expr, i));
 719                     let self_ty = *ty::ty_fn_args(method_ty).get(0);
 720                     let (m, r) = match ty::get(self_ty).sty {
 721                         ty::ty_rptr(r, ref m) => (m.mutbl, r),
 722                         _ => self.tcx().sess.span_bug(expr.span,
 723                                 format!("bad overloaded deref type {}",
 724                                     method_ty.repr(self.tcx())).as_slice())
 725                     };
 726                     let bk = ty::BorrowKind::from_mutbl(m);
 727                     self.delegate.borrow(expr.id, expr.span, cmt,
 728                                          r, bk, AutoRef);
 729                 }
 730             }
 731         }
 732     }
 733
 734     fn walk_autoref(&mut self,
 735                     expr: &ast::Expr,
 736                     autoref: &ty::AutoRef,
 737                     n: uint) {
 738         debug!("walk_autoref expr={}", expr.repr(self.tcx()));
 739
 740         // Match for unique trait coercions first, since we don't need the
 741         // call to cat_expr_autoderefd.
 742         match *autoref {
 743             ty::AutoUnsizeUniq(ty::UnsizeVtable(..)) |
 744             ty::AutoUnsize(ty::UnsizeVtable(..)) => {
 745                 assert!(n == 1, format!("Expected exactly 1 deref with Uniq \
 746                                          AutoRefs, found: {}", n));
 747                 let cmt_unadjusted =
 748                     return_if_err!(self.mc.cat_expr_unadjusted(expr));
 749                 self.delegate_consume(expr.id, expr.span, cmt_unadjusted);
 750                 return;
 751             }
 752             _ => {}
 753         }
 754
 755         let cmt_derefd = return_if_err!(
 756             self.mc.cat_expr_autoderefd(expr, n));
 757         debug!("walk_adjustment: cmt_derefd={}",
 758                cmt_derefd.repr(self.tcx()));
 759
 760         match *autoref {
 761             ty::AutoPtr(r, m, _) => {
 762                 self.delegate.borrow(expr.id,
 763                                      expr.span,
 764                                      cmt_derefd,
 765                                      r,
 766                                      ty::BorrowKind::from_mutbl(m),
 767                                      AutoRef);
 768             }
 769             ty::AutoUnsizeUniq(_) | ty::AutoUnsize(_) | ty::AutoUnsafe(..) => {}
 770         }
 771     }
 772
 773     fn walk_overloaded_operator(&mut self,
 774                                 expr: &ast::Expr,
 775                                 receiver: &ast::Expr,
 776                                 args: &[Gc<ast::Expr>])
 777                                 -> bool
 778     {
 779         if !self.typer.is_method_call(expr.id) {
 780             return false;
 781         }
 782
 783         self.walk_expr(receiver);
 784
 785         // Arguments (but not receivers) to overloaded operator
 786         // methods are implicitly autoref'd which sadly does not use
 787         // adjustments, so we must hardcode the borrow here.
 788
 789         let r = ty::ReScope(expr.id);
 790         let bk = ty::ImmBorrow;
 791
 792         for arg in args.iter() {
 793             self.borrow_expr(&**arg, r, bk, OverloadedOperator);
 794         }
 795         return true;
 796     }
 797
 798     fn walk_arm(&mut self, discr_cmt: mc::cmt, arm: &ast::Arm) {
 799         for &pat in arm.pats.iter() {
 800             self.walk_pat(discr_cmt.clone(), pat);
 801         }
 802
 803         for guard in arm.guard.iter() {
 804             self.consume_expr(&**guard);
 805         }
 806
 807         self.consume_expr(&*arm.body);
 808     }
 809
 810     fn walk_pat(&mut self, cmt_discr: mc::cmt, pat: Gc<ast::Pat>) {
 811         debug!("walk_pat cmt_discr={} pat={}", cmt_discr.repr(self.tcx()),
 812                pat.repr(self.tcx()));
 813         let mc = &self.mc;
 814         let typer = self.typer;
 815         let tcx = typer.tcx();
 816         let def_map = &self.typer.tcx().def_map;
 817         let delegate = &mut self.delegate;
 818         return_if_err!(mc.cat_pattern(cmt_discr, &*pat, |mc, cmt_pat, pat| {
 819             if pat_util::pat_is_binding(def_map, pat) {
 820                 let tcx = typer.tcx();
 821
 822                 debug!("binding cmt_pat={} pat={}",
 823                        cmt_pat.repr(tcx),
 824                        pat.repr(tcx));
 825
 826                 // pat_ty: the type of the binding being produced.
 827                 let pat_ty = return_if_err!(typer.node_ty(pat.id));
 828
 829                 // Each match binding is effectively an assignment to the
 830                 // binding being produced.
 831                 let def = def_map.borrow().get_copy(&pat.id);
 832                 match mc.cat_def(pat.id, pat.span, pat_ty, def) {
 833                     Ok(binding_cmt) => {
 834                         delegate.mutate(pat.id, pat.span, binding_cmt, Init);
 835                     }
 836                     Err(_) => { }
 837                 }
 838
 839                 // It is also a borrow or copy/move of the value being matched.
 840                 match pat.node {
 841                     ast::PatIdent(ast::BindByRef(m), _, _) => {
 842                         let (r, bk) = {
 843                             (ty::ty_region(tcx, pat.span, pat_ty),
 844                              ty::BorrowKind::from_mutbl(m))
 845                         };
 846                         delegate.borrow(pat.id, pat.span, cmt_pat,
 847                                              r, bk, RefBinding);
 848                     }
 849                     ast::PatIdent(ast::BindByValue(_), _, _) => {
 850                         let mode = copy_or_move(typer.tcx(), cmt_pat.ty, PatBindingMove);
 851                         debug!("walk_pat binding consuming pat");
 852                         delegate.consume_pat(pat, cmt_pat, mode);
 853                     }
 854                     _ => {
 855                         typer.tcx().sess.span_bug(
 856                             pat.span,
 857                             "binding pattern not an identifier");
 858                     }
 859                 }
 860             } else {
 861                 match pat.node {
 862                     ast::PatVec(_, Some(slice_pat), _) => {
 863                         // The `slice_pat` here creates a slice into
 864                         // the original vector.  This is effectively a
 865                         // borrow of the elements of the vector being
 866                         // matched.
 867
 868                         let (slice_cmt, slice_mutbl, slice_r) = {
 869                             match mc.cat_slice_pattern(cmt_pat, &*slice_pat) {
 870                                 Ok(v) => v,
 871                                 Err(()) => {
 872                                     tcx.sess.span_bug(slice_pat.span,
 873                                                       "Err from mc")
 874                                 }
 875                             }
 876                         };
 877
 878                         // Note: We declare here that the borrow
 879                         // occurs upon entering the `[...]`
 880                         // pattern. This implies that something like
 881                         // `[a, ..b]` where `a` is a move is illegal,
 882                         // because the borrow is already in effect.
 883                         // In fact such a move would be safe-ish, but
 884                         // it effectively *requires* that we use the
 885                         // nulling out semantics to indicate when a
 886                         // value has been moved, which we are trying
 887                         // to move away from.  Otherwise, how can we
 888                         // indicate that the first element in the
 889                         // vector has been moved?  Eventually, we
 890                         // could perhaps modify this rule to permit
 891                         // `[..a, b]` where `b` is a move, because in
 892                         // that case we can adjust the length of the
 893                         // original vec accordingly, but we'd have to
 894                         // make trans do the right thing, and it would
 895                         // only work for `~` vectors. It seems simpler
 896                         // to just require that people call
 897                         // `vec.pop()` or `vec.unshift()`.
 898                         let slice_bk = ty::BorrowKind::from_mutbl(slice_mutbl);
 899                         delegate.borrow(pat.id, pat.span,
 900                                         slice_cmt, slice_r,
 901                                         slice_bk, RefBinding);
 902                     }
 903                     _ => { }
 904                 }
 905             }
 906         }));
 907     }
 908
 909     fn walk_captures(&mut self, closure_expr: &ast::Expr) {
 910         debug!("walk_captures({})", closure_expr.repr(self.tcx()));
 911
 912         let tcx = self.typer.tcx();
 913         freevars::with_freevars(tcx, closure_expr.id, |freevars| {
 914             match freevars::get_capture_mode(self.tcx(), closure_expr.id) {
 915                 freevars::CaptureByRef => {
 916                     self.walk_by_ref_captures(closure_expr, freevars);
 917                 }
 918                 freevars::CaptureByValue => {
 919                     self.walk_by_value_captures(closure_expr, freevars);
 920                 }
 921             }
 922         });
 923     }
 924
 925     fn walk_by_ref_captures(&mut self,
 926                             closure_expr: &ast::Expr,
 927                             freevars: &[freevars::freevar_entry]) {
 928         for freevar in freevars.iter() {
 929             let id_var = freevar.def.def_id().node;
 930             let cmt_var = return_if_err!(self.cat_captured_var(closure_expr.id,
 931                                                                closure_expr.span,
 932                                                                freevar.def));
 933
 934             // Lookup the kind of borrow the callee requires, as
 935             // inferred by regionbk
 936             let upvar_id = ty::UpvarId { var_id: id_var,
 937                                          closure_expr_id: closure_expr.id };
 938             let upvar_borrow = self.tcx().upvar_borrow_map.borrow()
 939                                    .get_copy(&upvar_id);
 940
 941             self.delegate.borrow(closure_expr.id,
 942                                  closure_expr.span,
 943                                  cmt_var,
 944                                  upvar_borrow.region,
 945                                  upvar_borrow.kind,
 946                                  ClosureCapture(freevar.span));
 947         }
 948     }
 949
 950     fn walk_by_value_captures(&mut self,
 951                               closure_expr: &ast::Expr,
 952                               freevars: &[freevars::freevar_entry]) {
 953         for freevar in freevars.iter() {
 954             let cmt_var = return_if_err!(self.cat_captured_var(closure_expr.id,
 955                                                                closure_expr.span,
 956                                                                freevar.def));
 957             let mode = copy_or_move(self.tcx(), cmt_var.ty, CaptureMove);
 958             self.delegate.consume(closure_expr.id, freevar.span, cmt_var, mode);
 959         }
 960     }
 961
 962     fn cat_captured_var(&mut self,
 963                         closure_id: ast::NodeId,
 964                         closure_span: Span,
 965                         upvar_def: def::Def)
 966                         -> mc::McResult<mc::cmt> {
 967         // Create the cmt for the variable being borrowed, from the
 968         // caller's perspective
 969         let var_id = upvar_def.def_id().node;
 970         let var_ty = try!(self.typer.node_ty(var_id));
 971         self.mc.cat_def(closure_id, closure_span, var_ty, upvar_def)
 972     }
 973 }
 974
 975 fn copy_or_move(tcx: &ty::ctxt, ty: ty::t, move_reason: MoveReason) -> ConsumeMode {
 976     if ty::type_moves_by_default(tcx, ty) { Move(move_reason) } else { Copy }
 977 }
 978