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