src/librustc/middle/mem_categorization.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! # Categorization
  12 //!
  13 //! The job of the categorization module is to analyze an expression to
  14 //! determine what kind of memory is used in evaluating it (for example,
  15 //! where dereferences occur and what kind of pointer is dereferenced;
  16 //! whether the memory is mutable; etc)
  17 //!
  18 //! Categorization effectively transforms all of our expressions into
  19 //! expressions of the following forms (the actual enum has many more
  20 //! possibilities, naturally, but they are all variants of these base
  21 //! forms):
  22 //!
  23 //!     E = rvalue    // some computed rvalue
  24 //!       | x         // address of a local variable or argument
  25 //!       | *E        // deref of a ptr
  26 //!       | E.comp    // access to an interior component
  27 //!
  28 //! Imagine a routine ToAddr(Expr) that evaluates an expression and returns an
  29 //! address where the result is to be found.  If Expr is an lvalue, then this
  30 //! is the address of the lvalue.  If Expr is an rvalue, this is the address of
  31 //! some temporary spot in memory where the result is stored.
  32 //!
  33 //! Now, cat_expr() classifies the expression Expr and the address A=ToAddr(Expr)
  34 //! as follows:
  35 //!
  36 //! - cat: what kind of expression was this?  This is a subset of the
  37 //!   full expression forms which only includes those that we care about
  38 //!   for the purpose of the analysis.
  39 //! - mutbl: mutability of the address A
  40 //! - ty: the type of data found at the address A
  41 //!
  42 //! The resulting categorization tree differs somewhat from the expressions
  43 //! themselves.  For example, auto-derefs are explicit.  Also, an index a[b] is
  44 //! decomposed into two operations: a dereference to reach the array data and
  45 //! then an index to jump forward to the relevant item.
  46 //!
  47 //! ## By-reference upvars
  48 //!
  49 //! One part of the translation which may be non-obvious is that we translate
  50 //! closure upvars into the dereference of a borrowed pointer; this more closely
  51 //! resembles the runtime translation. So, for example, if we had:
  52 //!
  53 //!     let mut x = 3;
  54 //!     let y = 5;
  55 //!     let inc = || x += y;
  56 //!
  57 //! Then when we categorize `x` (*within* the closure) we would yield a
  58 //! result of `*x'`, effectively, where `x'` is a `Categorization::Upvar` reference
  59 //! tied to `x`. The type of `x'` will be a borrowed pointer.
  60
  61 #![allow(non_camel_case_types)]
  62
  63 pub use self::PointerKind::*;
  64 pub use self::InteriorKind::*;
  65 pub use self::FieldName::*;
  66 pub use self::ElementKind::*;
  67 pub use self::MutabilityCategory::*;
  68 pub use self::AliasableReason::*;
  69 pub use self::Note::*;
  70 pub use self::deref_kind::*;
  71
  72 use self::Aliasability::*;
  73
  74 use hir::def_id::DefId;
  75 use hir::map as ast_map;
  76 use infer::InferCtxt;
  77 use middle::const_qualif::ConstQualif;
  78 use hir::def::Def;
  79 use ty::adjustment;
  80 use ty::{self, Ty, TyCtxt};
  81
  82 use hir::{MutImmutable, MutMutable, PatKind};
  83 use hir::pat_util::EnumerateAndAdjustIterator;
  84 use hir;
  85 use syntax::ast;
  86 use syntax_pos::Span;
  87
  88 use std::fmt;
  89 use std::rc::Rc;
  90
  91 #[derive(Clone, PartialEq)]
  92 pub enum Categorization<'tcx> {
  93     Rvalue(ty::Region),                    // temporary val, argument is its scope
  94     StaticItem,
  95     Upvar(Upvar),                          // upvar referenced by closure env
  96     Local(ast::NodeId),                    // local variable
  97     Deref(cmt<'tcx>, usize, PointerKind),  // deref of a ptr
  98     Interior(cmt<'tcx>, InteriorKind),     // something interior: field, tuple, etc
  99     Downcast(cmt<'tcx>, DefId),            // selects a particular enum variant (*1)
 100
 101     // (*1) downcast is only required if the enum has more than one variant
 102 }
 103
 104 // Represents any kind of upvar
 105 #[derive(Clone, Copy, PartialEq)]
 106 pub struct Upvar {
 107     pub id: ty::UpvarId,
 108     pub kind: ty::ClosureKind
 109 }
 110
 111 // different kinds of pointers:
 112 #[derive(Clone, Copy, PartialEq, Eq, Hash)]
 113 pub enum PointerKind {
 114     /// `Box<T>`
 115     Unique,
 116
 117     /// `&T`
 118     BorrowedPtr(ty::BorrowKind, ty::Region),
 119
 120     /// `*T`
 121     UnsafePtr(hir::Mutability),
 122
 123     /// Implicit deref of the `&T` that results from an overloaded index `[]`.
 124     Implicit(ty::BorrowKind, ty::Region),
 125 }
 126
 127 // We use the term "interior" to mean "something reachable from the
 128 // base without a pointer dereference", e.g. a field
 129 #[derive(Clone, Copy, PartialEq, Eq, Hash)]
 130 pub enum InteriorKind {
 131     InteriorField(FieldName),
 132     InteriorElement(InteriorOffsetKind, ElementKind),
 133 }
 134
 135 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
 136 pub enum FieldName {
 137     NamedField(ast::Name),
 138     PositionalField(usize)
 139 }
 140
 141 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
 142 pub enum InteriorOffsetKind {
 143     Index,            // e.g. `array_expr[index_expr]`
 144     Pattern,          // e.g. `fn foo([_, a, _, _]: [A; 4]) { ... }`
 145 }
 146
 147 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
 148 pub enum ElementKind {
 149     VecElement,
 150     OtherElement,
 151 }
 152
 153 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
 154 pub enum MutabilityCategory {
 155     McImmutable, // Immutable.
 156     McDeclared,  // Directly declared as mutable.
 157     McInherited, // Inherited from the fact that owner is mutable.
 158 }
 159
 160 // A note about the provenance of a `cmt`.  This is used for
 161 // special-case handling of upvars such as mutability inference.
 162 // Upvar categorization can generate a variable number of nested
 163 // derefs.  The note allows detecting them without deep pattern
 164 // matching on the categorization.
 165 #[derive(Clone, Copy, PartialEq, Debug)]
 166 pub enum Note {
 167     NoteClosureEnv(ty::UpvarId), // Deref through closure env
 168     NoteUpvarRef(ty::UpvarId),   // Deref through by-ref upvar
 169     NoteNone                     // Nothing special
 170 }
 171
 172 // `cmt`: "Category, Mutability, and Type".
 173 //
 174 // a complete categorization of a value indicating where it originated
 175 // and how it is located, as well as the mutability of the memory in
 176 // which the value is stored.
 177 //
 178 // *WARNING* The field `cmt.type` is NOT necessarily the same as the
 179 // result of `node_id_to_type(cmt.id)`. This is because the `id` is
 180 // always the `id` of the node producing the type; in an expression
 181 // like `*x`, the type of this deref node is the deref'd type (`T`),
 182 // but in a pattern like `@x`, the `@x` pattern is again a
 183 // dereference, but its type is the type *before* the dereference
 184 // (`@T`). So use `cmt.ty` to find the type of the value in a consistent
 185 // fashion. For more details, see the method `cat_pattern`
 186 #[derive(Clone, PartialEq)]
 187 pub struct cmt_<'tcx> {
 188     pub id: ast::NodeId,           // id of expr/pat producing this value
 189     pub span: Span,                // span of same expr/pat
 190     pub cat: Categorization<'tcx>, // categorization of expr
 191     pub mutbl: MutabilityCategory, // mutability of expr as lvalue
 192     pub ty: Ty<'tcx>,              // type of the expr (*see WARNING above*)
 193     pub note: Note,                // Note about the provenance of this cmt
 194 }
 195
 196 pub type cmt<'tcx> = Rc<cmt_<'tcx>>;
 197
 198 // We pun on *T to mean both actual deref of a ptr as well
 199 // as accessing of components:
 200 #[derive(Copy, Clone)]
 201 pub enum deref_kind {
 202     deref_ptr(PointerKind),
 203     deref_interior(InteriorKind),
 204 }
 205
 206 type DerefKindContext = Option<InteriorOffsetKind>;
 207
 208 // Categorizes a derefable type.  Note that we include vectors and strings as
 209 // derefable (we model an index as the combination of a deref and then a
 210 // pointer adjustment).
 211 fn deref_kind(t: Ty, context: DerefKindContext) -> McResult<deref_kind> {
 212     match t.sty {
 213         ty::TyBox(_) => {
 214             Ok(deref_ptr(Unique))
 215         }
 216
 217         ty::TyRef(r, mt) => {
 218             let kind = ty::BorrowKind::from_mutbl(mt.mutbl);
 219             Ok(deref_ptr(BorrowedPtr(kind, *r)))
 220         }
 221
 222         ty::TyRawPtr(ref mt) => {
 223             Ok(deref_ptr(UnsafePtr(mt.mutbl)))
 224         }
 225
 226         ty::TyEnum(..) |
 227         ty::TyStruct(..) => { // newtype
 228             Ok(deref_interior(InteriorField(PositionalField(0))))
 229         }
 230
 231         ty::TyArray(_, _) | ty::TySlice(_) => {
 232             // no deref of indexed content without supplying InteriorOffsetKind
 233             if let Some(context) = context {
 234                 Ok(deref_interior(InteriorElement(context, ElementKind::VecElement)))
 235             } else {
 236                 Err(())
 237             }
 238         }
 239
 240         _ => Err(()),
 241     }
 242 }
 243
 244 pub trait ast_node {
 245     fn id(&self) -> ast::NodeId;
 246     fn span(&self) -> Span;
 247 }
 248
 249 impl ast_node for hir::Expr {
 250     fn id(&self) -> ast::NodeId { self.id }
 251     fn span(&self) -> Span { self.span }
 252 }
 253
 254 impl ast_node for hir::Pat {
 255     fn id(&self) -> ast::NodeId { self.id }
 256     fn span(&self) -> Span { self.span }
 257 }
 258
 259 #[derive(Copy, Clone)]
 260 pub struct MemCategorizationContext<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 261     pub infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
 262     options: MemCategorizationOptions,
 263 }
 264
 265 #[derive(Copy, Clone, Default)]
 266 pub struct MemCategorizationOptions {
 267     // If true, then when analyzing a closure upvar, if the closure
 268     // has a missing kind, we treat it like a Fn closure. When false,
 269     // we ICE if the closure has a missing kind. Should be false
 270     // except during closure kind inference. It is used by the
 271     // mem-categorization code to be able to have stricter assertions
 272     // (which are always true except during upvar inference).
 273     pub during_closure_kind_inference: bool,
 274 }
 275
 276 pub type McResult<T> = Result<T, ()>;
 277
 278 impl MutabilityCategory {
 279     pub fn from_mutbl(m: hir::Mutability) -> MutabilityCategory {
 280         let ret = match m {
 281             MutImmutable => McImmutable,
 282             MutMutable => McDeclared
 283         };
 284         debug!("MutabilityCategory::{}({:?}) => {:?}",
 285                "from_mutbl", m, ret);
 286         ret
 287     }
 288
 289     pub fn from_borrow_kind(borrow_kind: ty::BorrowKind) -> MutabilityCategory {
 290         let ret = match borrow_kind {
 291             ty::ImmBorrow => McImmutable,
 292             ty::UniqueImmBorrow => McImmutable,
 293             ty::MutBorrow => McDeclared,
 294         };
 295         debug!("MutabilityCategory::{}({:?}) => {:?}",
 296                "from_borrow_kind", borrow_kind, ret);
 297         ret
 298     }
 299
 300     fn from_pointer_kind(base_mutbl: MutabilityCategory,
 301                          ptr: PointerKind) -> MutabilityCategory {
 302         let ret = match ptr {
 303             Unique => {
 304                 base_mutbl.inherit()
 305             }
 306             BorrowedPtr(borrow_kind, _) | Implicit(borrow_kind, _) => {
 307                 MutabilityCategory::from_borrow_kind(borrow_kind)
 308             }
 309             UnsafePtr(m) => {
 310                 MutabilityCategory::from_mutbl(m)
 311             }
 312         };
 313         debug!("MutabilityCategory::{}({:?}, {:?}) => {:?}",
 314                "from_pointer_kind", base_mutbl, ptr, ret);
 315         ret
 316     }
 317
 318     fn from_local(tcx: TyCtxt, id: ast::NodeId) -> MutabilityCategory {
 319         let ret = match tcx.map.get(id) {
 320             ast_map::NodeLocal(p) => match p.node {
 321                 PatKind::Binding(bind_mode, _, _) => {
 322                     if bind_mode == hir::BindByValue(hir::MutMutable) {
 323                         McDeclared
 324                     } else {
 325                         McImmutable
 326                     }
 327                 }
 328                 _ => span_bug!(p.span, "expected identifier pattern")
 329             },
 330             _ => span_bug!(tcx.map.span(id), "expected identifier pattern")
 331         };
 332         debug!("MutabilityCategory::{}(tcx, id={:?}) => {:?}",
 333                "from_local", id, ret);
 334         ret
 335     }
 336
 337     pub fn inherit(&self) -> MutabilityCategory {
 338         let ret = match *self {
 339             McImmutable => McImmutable,
 340             McDeclared => McInherited,
 341             McInherited => McInherited,
 342         };
 343         debug!("{:?}.inherit() => {:?}", self, ret);
 344         ret
 345     }
 346
 347     pub fn is_mutable(&self) -> bool {
 348         let ret = match *self {
 349             McImmutable => false,
 350             McInherited => true,
 351             McDeclared => true,
 352         };
 353         debug!("{:?}.is_mutable() => {:?}", self, ret);
 354         ret
 355     }
 356
 357     pub fn is_immutable(&self) -> bool {
 358         let ret = match *self {
 359             McImmutable => true,
 360             McDeclared | McInherited => false
 361         };
 362         debug!("{:?}.is_immutable() => {:?}", self, ret);
 363         ret
 364     }
 365
 366     pub fn to_user_str(&self) -> &'static str {
 367         match *self {
 368             McDeclared | McInherited => "mutable",
 369             McImmutable => "immutable",
 370         }
 371     }
 372 }
 373
 374 impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
 375     pub fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>)
 376                -> MemCategorizationContext<'a, 'gcx, 'tcx> {
 377         MemCategorizationContext::with_options(infcx, MemCategorizationOptions::default())
 378     }
 379
 380     pub fn with_options(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
 381                         options: MemCategorizationOptions)
 382                         -> MemCategorizationContext<'a, 'gcx, 'tcx> {
 383         MemCategorizationContext {
 384             infcx: infcx,
 385             options: options,
 386         }
 387     }
 388
 389     fn tcx(&self) -> TyCtxt<'a, 'gcx, 'tcx> {
 390         self.infcx.tcx
 391     }
 392
 393     fn expr_ty(&self, expr: &hir::Expr) -> McResult<Ty<'tcx>> {
 394         match self.infcx.node_ty(expr.id) {
 395             Ok(t) => Ok(t),
 396             Err(()) => {
 397                 debug!("expr_ty({:?}) yielded Err", expr);
 398                 Err(())
 399             }
 400         }
 401     }
 402
 403     fn expr_ty_adjusted(&self, expr: &hir::Expr) -> McResult<Ty<'tcx>> {
 404         let unadjusted_ty = self.expr_ty(expr)?;
 405         Ok(unadjusted_ty.adjust(
 406             self.tcx(), expr.span, expr.id,
 407             self.infcx.adjustments().get(&expr.id),
 408             |method_call| self.infcx.node_method_ty(method_call)))
 409     }
 410
 411     fn node_ty(&self, id: ast::NodeId) -> McResult<Ty<'tcx>> {
 412         self.infcx.node_ty(id)
 413     }
 414
 415     fn pat_ty(&self, pat: &hir::Pat) -> McResult<Ty<'tcx>> {
 416         let base_ty = self.infcx.node_ty(pat.id)?;
 417         // FIXME (Issue #18207): This code detects whether we are
 418         // looking at a `ref x`, and if so, figures out what the type
 419         // *being borrowed* is.  But ideally we would put in a more
 420         // fundamental fix to this conflated use of the node id.
 421         let ret_ty = match pat.node {
 422             PatKind::Binding(hir::BindByRef(_), _, _) => {
 423                 // a bind-by-ref means that the base_ty will be the type of the ident itself,
 424                 // but what we want here is the type of the underlying value being borrowed.
 425                 // So peel off one-level, turning the &T into T.
 426                 match base_ty.builtin_deref(false, ty::NoPreference) {
 427                     Some(t) => t.ty,
 428                     None => { return Err(()); }
 429                 }
 430             }
 431             _ => base_ty,
 432         };
 433         debug!("pat_ty(pat={:?}) base_ty={:?} ret_ty={:?}",
 434                pat, base_ty, ret_ty);
 435         Ok(ret_ty)
 436     }
 437
 438     pub fn cat_expr(&self, expr: &hir::Expr) -> McResult<cmt<'tcx>> {
 439         match self.infcx.adjustments().get(&expr.id) {
 440             None => {
 441                 // No adjustments.
 442                 self.cat_expr_unadjusted(expr)
 443             }
 444
 445             Some(adjustment) => {
 446                 match *adjustment {
 447                     adjustment::AdjustDerefRef(
 448                         adjustment::AutoDerefRef {
 449                             autoref: None, unsize: None, autoderefs, ..}) => {
 450                         // Equivalent to *expr or something similar.
 451                         self.cat_expr_autoderefd(expr, autoderefs)
 452                     }
 453
 454                     adjustment::AdjustNeverToAny(..) |
 455                     adjustment::AdjustReifyFnPointer |
 456                     adjustment::AdjustUnsafeFnPointer |
 457                     adjustment::AdjustMutToConstPointer |
 458                     adjustment::AdjustDerefRef(_) => {
 459                         debug!("cat_expr({:?}): {:?}",
 460                                adjustment,
 461                                expr);
 462                         // Result is an rvalue.
 463                         let expr_ty = self.expr_ty_adjusted(expr)?;
 464                         Ok(self.cat_rvalue_node(expr.id(), expr.span(), expr_ty))
 465                     }
 466                 }
 467             }
 468         }
 469     }
 470
 471     pub fn cat_expr_autoderefd(&self,
 472                                expr: &hir::Expr,
 473                                autoderefs: usize)
 474                                -> McResult<cmt<'tcx>> {
 475         let mut cmt = self.cat_expr_unadjusted(expr)?;
 476         debug!("cat_expr_autoderefd: autoderefs={}, cmt={:?}",
 477                autoderefs,
 478                cmt);
 479         for deref in 1..autoderefs + 1 {
 480             cmt = self.cat_deref(expr, cmt, deref, None)?;
 481         }
 482         return Ok(cmt);
 483     }
 484
 485     pub fn cat_expr_unadjusted(&self, expr: &hir::Expr) -> McResult<cmt<'tcx>> {
 486         debug!("cat_expr: id={} expr={:?}", expr.id, expr);
 487
 488         let expr_ty = self.expr_ty(expr)?;
 489         match expr.node {
 490           hir::ExprUnary(hir::UnDeref, ref e_base) => {
 491             let base_cmt = self.cat_expr(&e_base)?;
 492             self.cat_deref(expr, base_cmt, 0, None)
 493           }
 494
 495           hir::ExprField(ref base, f_name) => {
 496             let base_cmt = self.cat_expr(&base)?;
 497             debug!("cat_expr(cat_field): id={} expr={:?} base={:?}",
 498                    expr.id,
 499                    expr,
 500                    base_cmt);
 501             Ok(self.cat_field(expr, base_cmt, f_name.node, expr_ty))
 502           }
 503
 504           hir::ExprTupField(ref base, idx) => {
 505             let base_cmt = self.cat_expr(&base)?;
 506             Ok(self.cat_tup_field(expr, base_cmt, idx.node, expr_ty))
 507           }
 508
 509           hir::ExprIndex(ref base, _) => {
 510             let method_call = ty::MethodCall::expr(expr.id());
 511             let context = InteriorOffsetKind::Index;
 512             match self.infcx.node_method_ty(method_call) {
 513                 Some(method_ty) => {
 514                     // If this is an index implemented by a method call, then it
 515                     // will include an implicit deref of the result.
 516                     let ret_ty = self.overloaded_method_return_ty(method_ty);
 517
 518                     // The index method always returns an `&T`, so
 519                     // dereference it to find the result type.
 520                     let elem_ty = match ret_ty.sty {
 521                         ty::TyRef(_, mt) => mt.ty,
 522                         _ => {
 523                             debug!("cat_expr_unadjusted: return type of overloaded index is {:?}?",
 524                                    ret_ty);
 525                             return Err(());
 526                         }
 527                     };
 528
 529                     // The call to index() returns a `&T` value, which
 530                     // is an rvalue. That is what we will be
 531                     // dereferencing.
 532                     let base_cmt = self.cat_rvalue_node(expr.id(), expr.span(), ret_ty);
 533                     self.cat_deref_common(expr, base_cmt, 1, elem_ty, Some(context), true)
 534                 }
 535                 None => {
 536                     self.cat_index(expr, self.cat_expr(&base)?, context)
 537                 }
 538             }
 539           }
 540
 541           hir::ExprPath(..) => {
 542             self.cat_def(expr.id, expr.span, expr_ty, self.tcx().expect_def(expr.id))
 543           }
 544
 545           hir::ExprType(ref e, _) => {
 546             self.cat_expr(&e)
 547           }
 548
 549           hir::ExprAddrOf(..) | hir::ExprCall(..) |
 550           hir::ExprAssign(..) | hir::ExprAssignOp(..) |
 551           hir::ExprClosure(..) | hir::ExprRet(..) |
 552           hir::ExprUnary(..) |
 553           hir::ExprMethodCall(..) | hir::ExprCast(..) |
 554           hir::ExprVec(..) | hir::ExprTup(..) | hir::ExprIf(..) |
 555           hir::ExprBinary(..) | hir::ExprWhile(..) |
 556           hir::ExprBlock(..) | hir::ExprLoop(..) | hir::ExprMatch(..) |
 557           hir::ExprLit(..) | hir::ExprBreak(..) |
 558           hir::ExprAgain(..) | hir::ExprStruct(..) | hir::ExprRepeat(..) |
 559           hir::ExprInlineAsm(..) | hir::ExprBox(..) => {
 560             Ok(self.cat_rvalue_node(expr.id(), expr.span(), expr_ty))
 561           }
 562         }
 563     }
 564
 565     pub fn cat_def(&self,
 566                    id: ast::NodeId,
 567                    span: Span,
 568                    expr_ty: Ty<'tcx>,
 569                    def: Def)
 570                    -> McResult<cmt<'tcx>> {
 571         debug!("cat_def: id={} expr={:?} def={:?}",
 572                id, expr_ty, def);
 573
 574         match def {
 575           Def::Struct(..) | Def::Variant(..) | Def::Const(..) |
 576           Def::AssociatedConst(..) | Def::Fn(..) | Def::Method(..) => {
 577                 Ok(self.cat_rvalue_node(id, span, expr_ty))
 578           }
 579
 580           Def::Mod(_) | Def::ForeignMod(_) |
 581           Def::Trait(_) | Def::Enum(..) | Def::TyAlias(..) | Def::PrimTy(_) |
 582           Def::TyParam(..) |
 583           Def::Label(_) | Def::SelfTy(..) |
 584           Def::AssociatedTy(..) => {
 585               span_bug!(span, "Unexpected definition in \
 586                                memory categorization: {:?}", def);
 587           }
 588
 589           Def::Static(_, mutbl) => {
 590               Ok(Rc::new(cmt_ {
 591                   id:id,
 592                   span:span,
 593                   cat:Categorization::StaticItem,
 594                   mutbl: if mutbl { McDeclared } else { McImmutable},
 595                   ty:expr_ty,
 596                   note: NoteNone
 597               }))
 598           }
 599
 600           Def::Upvar(_, var_id, _, fn_node_id) => {
 601               let ty = self.node_ty(fn_node_id)?;
 602               match ty.sty {
 603                   ty::TyClosure(closure_id, _) => {
 604                       match self.infcx.closure_kind(closure_id) {
 605                           Some(kind) => {
 606                               self.cat_upvar(id, span, var_id, fn_node_id, kind)
 607                           }
 608                           None => {
 609                               if !self.options.during_closure_kind_inference {
 610                                   span_bug!(
 611                                       span,
 612                                       "No closure kind for {:?}",
 613                                       closure_id);
 614                               }
 615
 616                               // during closure kind inference, we
 617                               // don't know the closure kind yet, but
 618                               // it's ok because we detect that we are
 619                               // accessing an upvar and handle that
 620                               // case specially anyhow. Use Fn
 621                               // arbitrarily.
 622                               self.cat_upvar(id, span, var_id, fn_node_id, ty::ClosureKind::Fn)
 623                           }
 624                       }
 625                   }
 626                   _ => {
 627                       span_bug!(
 628                           span,
 629                           "Upvar of non-closure {} - {:?}",
 630                           fn_node_id,
 631                           ty);
 632                   }
 633               }
 634           }
 635
 636           Def::Local(_, vid) => {
 637             Ok(Rc::new(cmt_ {
 638                 id: id,
 639                 span: span,
 640                 cat: Categorization::Local(vid),
 641                 mutbl: MutabilityCategory::from_local(self.tcx(), vid),
 642                 ty: expr_ty,
 643                 note: NoteNone
 644             }))
 645           }
 646
 647           Def::Err => bug!("Def::Err in memory categorization")
 648         }
 649     }
 650
 651     // Categorize an upvar, complete with invisible derefs of closure
 652     // environment and upvar reference as appropriate.
 653     fn cat_upvar(&self,
 654                  id: ast::NodeId,
 655                  span: Span,
 656                  var_id: ast::NodeId,
 657                  fn_node_id: ast::NodeId,
 658                  kind: ty::ClosureKind)
 659                  -> McResult<cmt<'tcx>>
 660     {
 661         // An upvar can have up to 3 components. We translate first to a
 662         // `Categorization::Upvar`, which is itself a fiction -- it represents the reference to the
 663         // field from the environment.
 664         //
 665         // `Categorization::Upvar`.  Next, we add a deref through the implicit
 666         // environment pointer with an anonymous free region 'env and
 667         // appropriate borrow kind for closure kinds that take self by
 668         // reference.  Finally, if the upvar was captured
 669         // by-reference, we add a deref through that reference.  The
 670         // region of this reference is an inference variable 'up that
 671         // was previously generated and recorded in the upvar borrow
 672         // map.  The borrow kind bk is inferred by based on how the
 673         // upvar is used.
 674         //
 675         // This results in the following table for concrete closure
 676         // types:
 677         //
 678         //                | move                 | ref
 679         // ---------------+----------------------+-------------------------------
 680         // Fn             | copied -> &'env      | upvar -> &'env -> &'up bk
 681         // FnMut          | copied -> &'env mut  | upvar -> &'env mut -> &'up bk
 682         // FnOnce         | copied               | upvar -> &'up bk
 683
 684         let upvar_id = ty::UpvarId { var_id: var_id,
 685                                      closure_expr_id: fn_node_id };
 686         let var_ty = self.node_ty(var_id)?;
 687
 688         // Mutability of original variable itself
 689         let var_mutbl = MutabilityCategory::from_local(self.tcx(), var_id);
 690
 691         // Construct the upvar. This represents access to the field
 692         // from the environment (perhaps we should eventually desugar
 693         // this field further, but it will do for now).
 694         let cmt_result = cmt_ {
 695             id: id,
 696             span: span,
 697             cat: Categorization::Upvar(Upvar {id: upvar_id, kind: kind}),
 698             mutbl: var_mutbl,
 699             ty: var_ty,
 700             note: NoteNone
 701         };
 702
 703         // If this is a `FnMut` or `Fn` closure, then the above is
 704         // conceptually a `&mut` or `&` reference, so we have to add a
 705         // deref.
 706         let cmt_result = match kind {
 707             ty::ClosureKind::FnOnce => {
 708                 cmt_result
 709             }
 710             ty::ClosureKind::FnMut => {
 711                 self.env_deref(id, span, upvar_id, var_mutbl, ty::MutBorrow, cmt_result)
 712             }
 713             ty::ClosureKind::Fn => {
 714                 self.env_deref(id, span, upvar_id, var_mutbl, ty::ImmBorrow, cmt_result)
 715             }
 716         };
 717
 718         // If this is a by-ref capture, then the upvar we loaded is
 719         // actually a reference, so we have to add an implicit deref
 720         // for that.
 721         let upvar_id = ty::UpvarId { var_id: var_id,
 722                                      closure_expr_id: fn_node_id };
 723         let upvar_capture = self.infcx.upvar_capture(upvar_id).unwrap();
 724         let cmt_result = match upvar_capture {
 725             ty::UpvarCapture::ByValue => {
 726                 cmt_result
 727             }
 728             ty::UpvarCapture::ByRef(upvar_borrow) => {
 729                 let ptr = BorrowedPtr(upvar_borrow.kind, upvar_borrow.region);
 730                 cmt_ {
 731                     id: id,
 732                     span: span,
 733                     cat: Categorization::Deref(Rc::new(cmt_result), 0, ptr),
 734                     mutbl: MutabilityCategory::from_borrow_kind(upvar_borrow.kind),
 735                     ty: var_ty,
 736                     note: NoteUpvarRef(upvar_id)
 737                 }
 738             }
 739         };
 740
 741         let ret = Rc::new(cmt_result);
 742         debug!("cat_upvar ret={:?}", ret);
 743         Ok(ret)
 744     }
 745
 746     fn env_deref(&self,
 747                  id: ast::NodeId,
 748                  span: Span,
 749                  upvar_id: ty::UpvarId,
 750                  upvar_mutbl: MutabilityCategory,
 751                  env_borrow_kind: ty::BorrowKind,
 752                  cmt_result: cmt_<'tcx>)
 753                  -> cmt_<'tcx>
 754     {
 755         // Look up the node ID of the closure body so we can construct
 756         // a free region within it
 757         let fn_body_id = {
 758             let fn_expr = match self.tcx().map.find(upvar_id.closure_expr_id) {
 759                 Some(ast_map::NodeExpr(e)) => e,
 760                 _ => bug!()
 761             };
 762
 763             match fn_expr.node {
 764                 hir::ExprClosure(_, _, ref body, _) => body.id,
 765                 _ => bug!()
 766             }
 767         };
 768
 769         // Region of environment pointer
 770         let env_region = ty::ReFree(ty::FreeRegion {
 771             // The environment of a closure is guaranteed to
 772             // outlive any bindings introduced in the body of the
 773             // closure itself.
 774             scope: self.tcx().region_maps.item_extent(fn_body_id),
 775             bound_region: ty::BrEnv
 776         });
 777
 778         let env_ptr = BorrowedPtr(env_borrow_kind, env_region);
 779
 780         let var_ty = cmt_result.ty;
 781
 782         // We need to add the env deref.  This means
 783         // that the above is actually immutable and
 784         // has a ref type.  However, nothing should
 785         // actually look at the type, so we can get
 786         // away with stuffing a `TyError` in there
 787         // instead of bothering to construct a proper
 788         // one.
 789         let cmt_result = cmt_ {
 790             mutbl: McImmutable,
 791             ty: self.tcx().types.err,
 792             ..cmt_result
 793         };
 794
 795         let mut deref_mutbl = MutabilityCategory::from_borrow_kind(env_borrow_kind);
 796
 797         // Issue #18335. If variable is declared as immutable, override the
 798         // mutability from the environment and substitute an `&T` anyway.
 799         match upvar_mutbl {
 800             McImmutable => { deref_mutbl = McImmutable; }
 801             McDeclared | McInherited => { }
 802         }
 803
 804         let ret = cmt_ {
 805             id: id,
 806             span: span,
 807             cat: Categorization::Deref(Rc::new(cmt_result), 0, env_ptr),
 808             mutbl: deref_mutbl,
 809             ty: var_ty,
 810             note: NoteClosureEnv(upvar_id)
 811         };
 812
 813         debug!("env_deref ret {:?}", ret);
 814
 815         ret
 816     }
 817
 818     /// Returns the lifetime of a temporary created by expr with id `id`.
 819     /// This could be `'static` if `id` is part of a constant expression.
 820     pub fn temporary_scope(&self, id: ast::NodeId) -> ty::Region {
 821         match self.infcx.temporary_scope(id) {
 822             Some(scope) => ty::ReScope(scope),
 823             None => ty::ReStatic
 824         }
 825     }
 826
 827     pub fn cat_rvalue_node(&self,
 828                            id: ast::NodeId,
 829                            span: Span,
 830                            expr_ty: Ty<'tcx>)
 831                            -> cmt<'tcx> {
 832         let qualif = self.tcx().const_qualif_map.borrow().get(&id).cloned()
 833                                .unwrap_or(ConstQualif::NOT_CONST);
 834
 835         // Only promote `[T; 0]` before an RFC for rvalue promotions
 836         // is accepted.
 837         let qualif = match expr_ty.sty {
 838             ty::TyArray(_, 0) => qualif,
 839             _ => ConstQualif::NOT_CONST
 840         };
 841
 842         // Compute maximum lifetime of this rvalue. This is 'static if
 843         // we can promote to a constant, otherwise equal to enclosing temp
 844         // lifetime.
 845         let re = if qualif.intersects(ConstQualif::NON_STATIC_BORROWS) {
 846             self.temporary_scope(id)
 847         } else {
 848             ty::ReStatic
 849         };
 850         let ret = self.cat_rvalue(id, span, re, expr_ty);
 851         debug!("cat_rvalue_node ret {:?}", ret);
 852         ret
 853     }
 854
 855     pub fn cat_rvalue(&self,
 856                       cmt_id: ast::NodeId,
 857                       span: Span,
 858                       temp_scope: ty::Region,
 859                       expr_ty: Ty<'tcx>) -> cmt<'tcx> {
 860         let ret = Rc::new(cmt_ {
 861             id:cmt_id,
 862             span:span,
 863             cat:Categorization::Rvalue(temp_scope),
 864             mutbl:McDeclared,
 865             ty:expr_ty,
 866             note: NoteNone
 867         });
 868         debug!("cat_rvalue ret {:?}", ret);
 869         ret
 870     }
 871
 872     pub fn cat_field<N:ast_node>(&self,
 873                                  node: &N,
 874                                  base_cmt: cmt<'tcx>,
 875                                  f_name: ast::Name,
 876                                  f_ty: Ty<'tcx>)
 877                                  -> cmt<'tcx> {
 878         let ret = Rc::new(cmt_ {
 879             id: node.id(),
 880             span: node.span(),
 881             mutbl: base_cmt.mutbl.inherit(),
 882             cat: Categorization::Interior(base_cmt, InteriorField(NamedField(f_name))),
 883             ty: f_ty,
 884             note: NoteNone
 885         });
 886         debug!("cat_field ret {:?}", ret);
 887         ret
 888     }
 889
 890     pub fn cat_tup_field<N:ast_node>(&self,
 891                                      node: &N,
 892                                      base_cmt: cmt<'tcx>,
 893                                      f_idx: usize,
 894                                      f_ty: Ty<'tcx>)
 895                                      -> cmt<'tcx> {
 896         let ret = Rc::new(cmt_ {
 897             id: node.id(),
 898             span: node.span(),
 899             mutbl: base_cmt.mutbl.inherit(),
 900             cat: Categorization::Interior(base_cmt, InteriorField(PositionalField(f_idx))),
 901             ty: f_ty,
 902             note: NoteNone
 903         });
 904         debug!("cat_tup_field ret {:?}", ret);
 905         ret
 906     }
 907
 908     fn cat_deref<N:ast_node>(&self,
 909                              node: &N,
 910                              base_cmt: cmt<'tcx>,
 911                              deref_cnt: usize,
 912                              deref_context: DerefKindContext)
 913                              -> McResult<cmt<'tcx>> {
 914         let method_call = ty::MethodCall {
 915             expr_id: node.id(),
 916             autoderef: deref_cnt as u32
 917         };
 918         let method_ty = self.infcx.node_method_ty(method_call);
 919
 920         debug!("cat_deref: method_call={:?} method_ty={:?}",
 921                method_call, method_ty.map(|ty| ty));
 922
 923         let base_cmt = match method_ty {
 924             Some(method_ty) => {
 925                 let ref_ty =
 926                     self.tcx().no_late_bound_regions(&method_ty.fn_ret()).unwrap();
 927                 self.cat_rvalue_node(node.id(), node.span(), ref_ty)
 928             }
 929             None => base_cmt
 930         };
 931         let base_cmt_ty = base_cmt.ty;
 932         match base_cmt_ty.builtin_deref(true, ty::NoPreference) {
 933             Some(mt) => {
 934                 let ret = self.cat_deref_common(node, base_cmt, deref_cnt,
 935                                               mt.ty,
 936                                               deref_context,
 937                                                 /* implicit: */ false);
 938                 debug!("cat_deref ret {:?}", ret);
 939                 ret
 940             }
 941             None => {
 942                 debug!("Explicit deref of non-derefable type: {:?}",
 943                        base_cmt_ty);
 944                 return Err(());
 945             }
 946         }
 947     }
 948
 949     fn cat_deref_common<N:ast_node>(&self,
 950                                     node: &N,
 951                                     base_cmt: cmt<'tcx>,
 952                                     deref_cnt: usize,
 953                                     deref_ty: Ty<'tcx>,
 954                                     deref_context: DerefKindContext,
 955                                     implicit: bool)
 956                                     -> McResult<cmt<'tcx>>
 957     {
 958         let (m, cat) = match deref_kind(base_cmt.ty, deref_context)? {
 959             deref_ptr(ptr) => {
 960                 let ptr = if implicit {
 961                     match ptr {
 962                         BorrowedPtr(bk, r) => Implicit(bk, r),
 963                         _ => span_bug!(node.span(),
 964                             "Implicit deref of non-borrowed pointer")
 965                     }
 966                 } else {
 967                     ptr
 968                 };
 969                 // for unique ptrs, we inherit mutability from the
 970                 // owning reference.
 971                 (MutabilityCategory::from_pointer_kind(base_cmt.mutbl, ptr),
 972                  Categorization::Deref(base_cmt, deref_cnt, ptr))
 973             }
 974             deref_interior(interior) => {
 975                 (base_cmt.mutbl.inherit(), Categorization::Interior(base_cmt, interior))
 976             }
 977         };
 978         let ret = Rc::new(cmt_ {
 979             id: node.id(),
 980             span: node.span(),
 981             cat: cat,
 982             mutbl: m,
 983             ty: deref_ty,
 984             note: NoteNone
 985         });
 986         debug!("cat_deref_common ret {:?}", ret);
 987         Ok(ret)
 988     }
 989
 990     pub fn cat_index<N:ast_node>(&self,
 991                                  elt: &N,
 992                                  mut base_cmt: cmt<'tcx>,
 993                                  context: InteriorOffsetKind)
 994                                  -> McResult<cmt<'tcx>> {
 995         //! Creates a cmt for an indexing operation (`[]`).
 996         //!
 997         //! One subtle aspect of indexing that may not be
 998         //! immediately obvious: for anything other than a fixed-length
 999         //! vector, an operation like `x[y]` actually consists of two
1000         //! disjoint (from the point of view of borrowck) operations.
1001         //! The first is a deref of `x` to create a pointer `p` that points
1002         //! at the first element in the array. The second operation is
1003         //! an index which adds `y*sizeof(T)` to `p` to obtain the
1004         //! pointer to `x[y]`. `cat_index` will produce a resulting
1005         //! cmt containing both this deref and the indexing,
1006         //! presuming that `base_cmt` is not of fixed-length type.
1007         //!
1008         //! # Parameters
1009         //! - `elt`: the AST node being indexed
1010         //! - `base_cmt`: the cmt of `elt`
1011
1012         let method_call = ty::MethodCall::expr(elt.id());
1013         let method_ty = self.infcx.node_method_ty(method_call);
1014
1015         let (element_ty, element_kind) = match method_ty {
1016             Some(method_ty) => {
1017                 let ref_ty = self.overloaded_method_return_ty(method_ty);
1018                 base_cmt = self.cat_rvalue_node(elt.id(), elt.span(), ref_ty);
1019
1020                 // FIXME(#20649) -- why are we using the `self_ty` as the element type...?
1021                 let self_ty = method_ty.fn_sig().input(0);
1022                 (self.tcx().no_late_bound_regions(&self_ty).unwrap(),
1023                  ElementKind::OtherElement)
1024             }
1025             None => {
1026                 match base_cmt.ty.builtin_index() {
1027                     Some(ty) => (ty, ElementKind::VecElement),
1028                     None => {
1029                         return Err(());
1030                     }
1031                 }
1032             }
1033         };
1034
1035         let interior_elem = InteriorElement(context, element_kind);
1036         let ret =
1037             self.cat_imm_interior(elt, base_cmt.clone(), element_ty, interior_elem);
1038         debug!("cat_index ret {:?}", ret);
1039         return Ok(ret);
1040     }
1041
1042     pub fn cat_imm_interior<N:ast_node>(&self,
1043                                         node: &N,
1044                                         base_cmt: cmt<'tcx>,
1045                                         interior_ty: Ty<'tcx>,
1046                                         interior: InteriorKind)
1047                                         -> cmt<'tcx> {
1048         let ret = Rc::new(cmt_ {
1049             id: node.id(),
1050             span: node.span(),
1051             mutbl: base_cmt.mutbl.inherit(),
1052             cat: Categorization::Interior(base_cmt, interior),
1053             ty: interior_ty,
1054             note: NoteNone
1055         });
1056         debug!("cat_imm_interior ret={:?}", ret);
1057         ret
1058     }
1059
1060     pub fn cat_downcast<N:ast_node>(&self,
1061                                     node: &N,
1062                                     base_cmt: cmt<'tcx>,
1063                                     downcast_ty: Ty<'tcx>,
1064                                     variant_did: DefId)
1065                                     -> cmt<'tcx> {
1066         let ret = Rc::new(cmt_ {
1067             id: node.id(),
1068             span: node.span(),
1069             mutbl: base_cmt.mutbl.inherit(),
1070             cat: Categorization::Downcast(base_cmt, variant_did),
1071             ty: downcast_ty,
1072             note: NoteNone
1073         });
1074         debug!("cat_downcast ret={:?}", ret);
1075         ret
1076     }
1077
1078     pub fn cat_pattern<F>(&self, cmt: cmt<'tcx>, pat: &hir::Pat, mut op: F) -> McResult<()>
1079         where F: FnMut(&MemCategorizationContext<'a, 'gcx, 'tcx>, cmt<'tcx>, &hir::Pat),
1080     {
1081         self.cat_pattern_(cmt, pat, &mut op)
1082     }
1083
1084     // FIXME(#19596) This is a workaround, but there should be a better way to do this
1085     fn cat_pattern_<F>(&self, cmt: cmt<'tcx>, pat: &hir::Pat, op: &mut F) -> McResult<()>
1086         where F : FnMut(&MemCategorizationContext<'a, 'gcx, 'tcx>, cmt<'tcx>, &hir::Pat)
1087     {
1088         // Here, `cmt` is the categorization for the value being
1089         // matched and pat is the pattern it is being matched against.
1090         //
1091         // In general, the way that this works is that we walk down
1092         // the pattern, constructing a cmt that represents the path
1093         // that will be taken to reach the value being matched.
1094         //
1095         // When we encounter named bindings, we take the cmt that has
1096         // been built up and pass it off to guarantee_valid() so that
1097         // we can be sure that the binding will remain valid for the
1098         // duration of the arm.
1099         //
1100         // (*2) There is subtlety concerning the correspondence between
1101         // pattern ids and types as compared to *expression* ids and
1102         // types. This is explained briefly. on the definition of the
1103         // type `cmt`, so go off and read what it says there, then
1104         // come back and I'll dive into a bit more detail here. :) OK,
1105         // back?
1106         //
1107         // In general, the id of the cmt should be the node that
1108         // "produces" the value---patterns aren't executable code
1109         // exactly, but I consider them to "execute" when they match a
1110         // value, and I consider them to produce the value that was
1111         // matched. So if you have something like:
1112         //
1113         //     let x = @@3;
1114         //     match x {
1115         //       @@y { ... }
1116         //     }
1117         //
1118         // In this case, the cmt and the relevant ids would be:
1119         //
1120         //     CMT             Id                  Type of Id Type of cmt
1121         //
1122         //     local(x)->@->@
1123         //     ^~~~~~~^        `x` from discr      @@int      @@int
1124         //     ^~~~~~~~~~^     `@@y` pattern node  @@int      @int
1125         //     ^~~~~~~~~~~~~^  `@y` pattern node   @int       int
1126         //
1127         // You can see that the types of the id and the cmt are in
1128         // sync in the first line, because that id is actually the id
1129         // of an expression. But once we get to pattern ids, the types
1130         // step out of sync again. So you'll see below that we always
1131         // get the type of the *subpattern* and use that.
1132
1133         debug!("cat_pattern: {:?} cmt={:?}", pat, cmt);
1134
1135         op(self, cmt.clone(), pat);
1136
1137         // Note: This goes up here (rather than within the PatKind::TupleStruct arm
1138         // alone) because PatKind::Struct can also refer to variants.
1139         let cmt = match self.tcx().expect_def_or_none(pat.id) {
1140             Some(Def::Err) => return Err(()),
1141             Some(Def::Variant(enum_did, variant_did))
1142                 // univariant enums do not need downcasts
1143                 if !self.tcx().lookup_adt_def(enum_did).is_univariant() => {
1144                     self.cat_downcast(pat, cmt.clone(), cmt.ty, variant_did)
1145                 }
1146             _ => cmt
1147         };
1148
1149         match pat.node {
1150           PatKind::TupleStruct(_, ref subpats, ddpos) => {
1151             let expected_len = match self.tcx().expect_def(pat.id) {
1152                 Def::Variant(enum_def, def_id) => {
1153                     self.tcx().lookup_adt_def(enum_def).variant_with_id(def_id).fields.len()
1154                 }
1155                 Def::Struct(..) => {
1156                     match self.pat_ty(&pat)?.sty {
1157                         ty::TyStruct(adt_def, _) => {
1158                             adt_def.struct_variant().fields.len()
1159                         }
1160                         ref ty => {
1161                             span_bug!(pat.span, "tuple struct pattern unexpected type {:?}", ty);
1162                         }
1163                     }
1164                 }
1165                 def => {
1166                     span_bug!(pat.span, "tuple struct pattern didn't resolve \
1167                                          to variant or struct {:?}", def);
1168                 }
1169             };
1170
1171             for (i, subpat) in subpats.iter().enumerate_and_adjust(expected_len, ddpos) {
1172                 let subpat_ty = self.pat_ty(&subpat)?; // see (*2)
1173                 let subcmt = self.cat_imm_interior(pat, cmt.clone(), subpat_ty,
1174                                                    InteriorField(PositionalField(i)));
1175                 self.cat_pattern_(subcmt, &subpat, op)?;
1176             }
1177           }
1178
1179           PatKind::Struct(_, ref field_pats, _) => {
1180             // {f1: p1, ..., fN: pN}
1181             for fp in field_pats {
1182                 let field_ty = self.pat_ty(&fp.node.pat)?; // see (*2)
1183                 let cmt_field = self.cat_field(pat, cmt.clone(), fp.node.name, field_ty);
1184                 self.cat_pattern_(cmt_field, &fp.node.pat, op)?;
1185             }
1186           }
1187
1188           PatKind::Binding(_, _, Some(ref subpat)) => {
1189               self.cat_pattern_(cmt, &subpat, op)?;
1190           }
1191
1192           PatKind::Tuple(ref subpats, ddpos) => {
1193             // (p1, ..., pN)
1194             let expected_len = match self.pat_ty(&pat)?.sty {
1195                 ty::TyTuple(ref tys) => tys.len(),
1196                 ref ty => span_bug!(pat.span, "tuple pattern unexpected type {:?}", ty),
1197             };
1198             for (i, subpat) in subpats.iter().enumerate_and_adjust(expected_len, ddpos) {
1199                 let subpat_ty = self.pat_ty(&subpat)?; // see (*2)
1200                 let subcmt = self.cat_imm_interior(pat, cmt.clone(), subpat_ty,
1201                                                    InteriorField(PositionalField(i)));
1202                 self.cat_pattern_(subcmt, &subpat, op)?;
1203             }
1204           }
1205
1206           PatKind::Box(ref subpat) | PatKind::Ref(ref subpat, _) => {
1207             // box p1, &p1, &mut p1.  we can ignore the mutability of
1208             // PatKind::Ref since that information is already contained
1209             // in the type.
1210             let subcmt = self.cat_deref(pat, cmt, 0, None)?;
1211             self.cat_pattern_(subcmt, &subpat, op)?;
1212           }
1213
1214           PatKind::Vec(ref before, ref slice, ref after) => {
1215             let context = InteriorOffsetKind::Pattern;
1216             let elt_cmt = self.cat_index(pat, cmt, context)?;
1217             for before_pat in before {
1218                 self.cat_pattern_(elt_cmt.clone(), &before_pat, op)?;
1219             }
1220             if let Some(ref slice_pat) = *slice {
1221                 self.cat_pattern_(elt_cmt.clone(), &slice_pat, op)?;
1222             }
1223             for after_pat in after {
1224                 self.cat_pattern_(elt_cmt.clone(), &after_pat, op)?;
1225             }
1226           }
1227
1228           PatKind::Path(..) | PatKind::Binding(_, _, None) |
1229           PatKind::Lit(..) | PatKind::Range(..) | PatKind::Wild => {
1230             // always ok
1231           }
1232         }
1233
1234         Ok(())
1235     }
1236
1237     fn overloaded_method_return_ty(&self,
1238                                    method_ty: Ty<'tcx>)
1239                                    -> Ty<'tcx>
1240     {
1241         // When we process an overloaded `*` or `[]` etc, we often
1242         // need to extract the return type of the method. These method
1243         // types are generated by method resolution and always have
1244         // all late-bound regions fully instantiated, so we just want
1245         // to skip past the binder.
1246         self.tcx().no_late_bound_regions(&method_ty.fn_ret())
1247            .unwrap()
1248     }
1249 }
1250
1251 #[derive(Clone, Debug)]
1252 pub enum Aliasability {
1253     FreelyAliasable(AliasableReason),
1254     NonAliasable,
1255     ImmutableUnique(Box<Aliasability>),
1256 }
1257
1258 #[derive(Copy, Clone, Debug)]
1259 pub enum AliasableReason {
1260     AliasableBorrowed,
1261     AliasableClosure(ast::NodeId), // Aliasable due to capture Fn closure env
1262     AliasableOther,
1263     UnaliasableImmutable, // Created as needed upon seeing ImmutableUnique
1264     AliasableStatic,
1265     AliasableStaticMut,
1266 }
1267
1268 impl<'tcx> cmt_<'tcx> {
1269     pub fn guarantor(&self) -> cmt<'tcx> {
1270         //! Returns `self` after stripping away any derefs or
1271         //! interior content. The return value is basically the `cmt` which
1272         //! determines how long the value in `self` remains live.
1273
1274         match self.cat {
1275             Categorization::Rvalue(..) |
1276             Categorization::StaticItem |
1277             Categorization::Local(..) |
1278             Categorization::Deref(_, _, UnsafePtr(..)) |
1279             Categorization::Deref(_, _, BorrowedPtr(..)) |
1280             Categorization::Deref(_, _, Implicit(..)) |
1281             Categorization::Upvar(..) => {
1282                 Rc::new((*self).clone())
1283             }
1284             Categorization::Downcast(ref b, _) |
1285             Categorization::Interior(ref b, _) |
1286             Categorization::Deref(ref b, _, Unique) => {
1287                 b.guarantor()
1288             }
1289         }
1290     }
1291
1292     /// Returns `FreelyAliasable(_)` if this lvalue represents a freely aliasable pointer type.
1293     pub fn freely_aliasable(&self) -> Aliasability {
1294         // Maybe non-obvious: copied upvars can only be considered
1295         // non-aliasable in once closures, since any other kind can be
1296         // aliased and eventually recused.
1297
1298         match self.cat {
1299             Categorization::Deref(ref b, _, BorrowedPtr(ty::MutBorrow, _)) |
1300             Categorization::Deref(ref b, _, Implicit(ty::MutBorrow, _)) |
1301             Categorization::Deref(ref b, _, BorrowedPtr(ty::UniqueImmBorrow, _)) |
1302             Categorization::Deref(ref b, _, Implicit(ty::UniqueImmBorrow, _)) |
1303             Categorization::Downcast(ref b, _) |
1304             Categorization::Interior(ref b, _) => {
1305                 // Aliasability depends on base cmt
1306                 b.freely_aliasable()
1307             }
1308
1309             Categorization::Deref(ref b, _, Unique) => {
1310                 let sub = b.freely_aliasable();
1311                 if b.mutbl.is_mutable() {
1312                     // Aliasability depends on base cmt alone
1313                     sub
1314                 } else {
1315                     // Do not allow mutation through an immutable box.
1316                     ImmutableUnique(Box::new(sub))
1317                 }
1318             }
1319
1320             Categorization::Rvalue(..) |
1321             Categorization::Local(..) |
1322             Categorization::Upvar(..) |
1323             Categorization::Deref(_, _, UnsafePtr(..)) => { // yes, it's aliasable, but...
1324                 NonAliasable
1325             }
1326
1327             Categorization::StaticItem => {
1328                 if self.mutbl.is_mutable() {
1329                     FreelyAliasable(AliasableStaticMut)
1330                 } else {
1331                     FreelyAliasable(AliasableStatic)
1332                 }
1333             }
1334
1335             Categorization::Deref(ref base, _, BorrowedPtr(ty::ImmBorrow, _)) |
1336             Categorization::Deref(ref base, _, Implicit(ty::ImmBorrow, _)) => {
1337                 match base.cat {
1338                     Categorization::Upvar(Upvar{ id, .. }) =>
1339                         FreelyAliasable(AliasableClosure(id.closure_expr_id)),
1340                     _ => FreelyAliasable(AliasableBorrowed)
1341                 }
1342             }
1343         }
1344     }
1345
1346     // Digs down through one or two layers of deref and grabs the cmt
1347     // for the upvar if a note indicates there is one.
1348     pub fn upvar(&self) -> Option<cmt<'tcx>> {
1349         match self.note {
1350             NoteClosureEnv(..) | NoteUpvarRef(..) => {
1351                 Some(match self.cat {
1352                     Categorization::Deref(ref inner, _, _) => {
1353                         match inner.cat {
1354                             Categorization::Deref(ref inner, _, _) => inner.clone(),
1355                             Categorization::Upvar(..) => inner.clone(),
1356                             _ => bug!()
1357                         }
1358                     }
1359                     _ => bug!()
1360                 })
1361             }
1362             NoteNone => None
1363         }
1364     }
1365
1366
1367     pub fn descriptive_string(&self, tcx: TyCtxt) -> String {
1368         match self.cat {
1369             Categorization::StaticItem => {
1370                 "static item".to_string()
1371             }
1372             Categorization::Rvalue(..) => {
1373                 "non-lvalue".to_string()
1374             }
1375             Categorization::Local(vid) => {
1376                 if tcx.map.is_argument(vid) {
1377                     "argument".to_string()
1378                 } else {
1379                     "local variable".to_string()
1380                 }
1381             }
1382             Categorization::Deref(_, _, pk) => {
1383                 let upvar = self.upvar();
1384                 match upvar.as_ref().map(|i| &i.cat) {
1385                     Some(&Categorization::Upvar(ref var)) => {
1386                         var.to_string()
1387                     }
1388                     Some(_) => bug!(),
1389                     None => {
1390                         match pk {
1391                             Implicit(..) => {
1392                                 format!("indexed content")
1393                             }
1394                             Unique => {
1395                                 format!("`Box` content")
1396                             }
1397                             UnsafePtr(..) => {
1398                                 format!("dereference of raw pointer")
1399                             }
1400                             BorrowedPtr(..) => {
1401                                 format!("borrowed content")
1402                             }
1403                         }
1404                     }
1405                 }
1406             }
1407             Categorization::Interior(_, InteriorField(NamedField(_))) => {
1408                 "field".to_string()
1409             }
1410             Categorization::Interior(_, InteriorField(PositionalField(_))) => {
1411                 "anonymous field".to_string()
1412             }
1413             Categorization::Interior(_, InteriorElement(InteriorOffsetKind::Index,
1414                                                         VecElement)) |
1415             Categorization::Interior(_, InteriorElement(InteriorOffsetKind::Index,
1416                                                         OtherElement)) => {
1417                 "indexed content".to_string()
1418             }
1419             Categorization::Interior(_, InteriorElement(InteriorOffsetKind::Pattern,
1420                                                         VecElement)) |
1421             Categorization::Interior(_, InteriorElement(InteriorOffsetKind::Pattern,
1422                                                         OtherElement)) => {
1423                 "pattern-bound indexed content".to_string()
1424             }
1425             Categorization::Upvar(ref var) => {
1426                 var.to_string()
1427             }
1428             Categorization::Downcast(ref cmt, _) => {
1429                 cmt.descriptive_string(tcx)
1430             }
1431         }
1432     }
1433 }
1434
1435 impl<'tcx> fmt::Debug for cmt_<'tcx> {
1436     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1437         write!(f, "{{{:?} id:{} m:{:?} ty:{:?}}}",
1438                self.cat,
1439                self.id,
1440                self.mutbl,
1441                self.ty)
1442     }
1443 }
1444
1445 impl<'tcx> fmt::Debug for Categorization<'tcx> {
1446     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1447         match *self {
1448             Categorization::StaticItem => write!(f, "static"),
1449             Categorization::Rvalue(r) => write!(f, "rvalue({:?})", r),
1450             Categorization::Local(id) => {
1451                let name = ty::tls::with(|tcx| tcx.local_var_name_str(id));
1452                write!(f, "local({})", name)
1453             }
1454             Categorization::Upvar(upvar) => {
1455                 write!(f, "upvar({:?})", upvar)
1456             }
1457             Categorization::Deref(ref cmt, derefs, ptr) => {
1458                 write!(f, "{:?}-{:?}{}->", cmt.cat, ptr, derefs)
1459             }
1460             Categorization::Interior(ref cmt, interior) => {
1461                 write!(f, "{:?}.{:?}", cmt.cat, interior)
1462             }
1463             Categorization::Downcast(ref cmt, _) => {
1464                 write!(f, "{:?}->(enum)", cmt.cat)
1465             }
1466         }
1467     }
1468 }
1469
1470 pub fn ptr_sigil(ptr: PointerKind) -> &'static str {
1471     match ptr {
1472         Unique => "Box",
1473         BorrowedPtr(ty::ImmBorrow, _) |
1474         Implicit(ty::ImmBorrow, _) => "&",
1475         BorrowedPtr(ty::MutBorrow, _) |
1476         Implicit(ty::MutBorrow, _) => "&mut",
1477         BorrowedPtr(ty::UniqueImmBorrow, _) |
1478         Implicit(ty::UniqueImmBorrow, _) => "&unique",
1479         UnsafePtr(_) => "*",
1480     }
1481 }
1482
1483 impl fmt::Debug for PointerKind {
1484     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1485         match *self {
1486             Unique => write!(f, "Box"),
1487             BorrowedPtr(ty::ImmBorrow, ref r) |
1488             Implicit(ty::ImmBorrow, ref r) => {
1489                 write!(f, "&{:?}", r)
1490             }
1491             BorrowedPtr(ty::MutBorrow, ref r) |
1492             Implicit(ty::MutBorrow, ref r) => {
1493                 write!(f, "&{:?} mut", r)
1494             }
1495             BorrowedPtr(ty::UniqueImmBorrow, ref r) |
1496             Implicit(ty::UniqueImmBorrow, ref r) => {
1497                 write!(f, "&{:?} uniq", r)
1498             }
1499             UnsafePtr(_) => write!(f, "*")
1500         }
1501     }
1502 }
1503
1504 impl fmt::Debug for InteriorKind {
1505     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1506         match *self {
1507             InteriorField(NamedField(fld)) => write!(f, "{}", fld),
1508             InteriorField(PositionalField(i)) => write!(f, "#{}", i),
1509             InteriorElement(..) => write!(f, "[]"),
1510         }
1511     }
1512 }
1513
1514 impl fmt::Debug for Upvar {
1515     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1516         write!(f, "{:?}/{:?}", self.id, self.kind)
1517     }
1518 }
1519
1520 impl fmt::Display for Upvar {
1521     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1522         let kind = match self.kind {
1523             ty::ClosureKind::Fn => "Fn",
1524             ty::ClosureKind::FnMut => "FnMut",
1525             ty::ClosureKind::FnOnce => "FnOnce",
1526         };
1527         write!(f, "captured outer variable in an `{}` closure", kind)
1528     }
1529 }