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