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