src/librustc_typeck/mem_categorization.rs

   1 //! # Categorization
   2 //!
   3 //! The job of the categorization module is to analyze an expression to
   4 //! determine what kind of memory is used in evaluating it (for example,
   5 //! where dereferences occur and what kind of pointer is dereferenced;
   6 //! whether the memory is mutable, etc.).
   7 //!
   8 //! Categorization effectively transforms all of our expressions into
   9 //! expressions of the following forms (the actual enum has many more
  10 //! possibilities, naturally, but they are all variants of these base
  11 //! forms):
  12 //!
  13 //!     E = rvalue    // some computed rvalue
  14 //!       | x         // address of a local variable or argument
  15 //!       | *E        // deref of a ptr
  16 //!       | E.comp    // access to an interior component
  17 //!
  18 //! Imagine a routine ToAddr(Expr) that evaluates an expression and returns an
  19 //! address where the result is to be found. If Expr is a place, then this
  20 //! is the address of the place. If `Expr` is an rvalue, this is the address of
  21 //! some temporary spot in memory where the result is stored.
  22 //!
  23 //! Now, `cat_expr()` classifies the expression `Expr` and the address `A = ToAddr(Expr)`
  24 //! as follows:
  25 //!
  26 //! - `cat`: what kind of expression was this? This is a subset of the
  27 //!   full expression forms which only includes those that we care about
  28 //!   for the purpose of the analysis.
  29 //! - `mutbl`: mutability of the address `A`.
  30 //! - `ty`: the type of data found at the address `A`.
  31 //!
  32 //! The resulting categorization tree differs somewhat from the expressions
  33 //! themselves. For example, auto-derefs are explicit. Also, an index a[b] is
  34 //! decomposed into two operations: a dereference to reach the array data and
  35 //! then an index to jump forward to the relevant item.
  36 //!
  37 //! ## By-reference upvars
  38 //!
  39 //! One part of the codegen which may be non-obvious is that we translate
  40 //! closure upvars into the dereference of a borrowed pointer; this more closely
  41 //! resembles the runtime codegen. So, for example, if we had:
  42 //!
  43 //!     let mut x = 3;
  44 //!     let y = 5;
  45 //!     let inc = || x += y;
  46 //!
  47 //! Then when we categorize `x` (*within* the closure) we would yield a
  48 //! result of `*x'`, effectively, where `x'` is a `Categorization::Upvar` reference
  49 //! tied to `x`. The type of `x'` will be a borrowed pointer.
  50
  51 use rustc::ty::adjustment;
  52 use rustc::ty::fold::TypeFoldable;
  53 use rustc::ty::{self, Ty, TyCtxt};
  54
  55 use rustc_data_structures::fx::FxIndexMap;
  56 use rustc_hir as hir;
  57 use rustc_hir::def::{DefKind, Res};
  58 use rustc_hir::def_id::DefId;
  59 use rustc_hir::PatKind;
  60 use rustc_infer::infer::InferCtxt;
  61 use rustc_span::Span;
  62
  63 #[derive(Clone, Debug)]
  64 pub enum PlaceBase {
  65     /// A temporary variable
  66     Rvalue,
  67     /// A named `static` item
  68     StaticItem,
  69     /// A named local variable
  70     Local(hir::HirId),
  71     /// An upvar referenced by closure env
  72     Upvar(ty::UpvarId),
  73 }
  74
  75 #[derive(Clone, Debug)]
  76 pub enum Projection<'tcx> {
  77     /// A dereference of a pointer, reference or `Box<T>` of the given type
  78     Deref(Ty<'tcx>),
  79     /// An index or a field
  80     Other,
  81 }
  82
  83 /// A `Place` represents how a value is located in memory.
  84 ///
  85 /// This is an HIR version of `mir::Place`
  86 #[derive(Clone, Debug)]
  87 pub struct Place<'tcx> {
  88     /// `HirId` of the expression or pattern producing this value.
  89     pub hir_id: hir::HirId,
  90     /// The `Span` of the expression or pattern producing this value.
  91     pub span: Span,
  92     /// The type of the `Place`
  93     pub ty: Ty<'tcx>,
  94     /// The "outermost" place that holds this value.
  95     pub base: PlaceBase,
  96     /// How this place is derived from the base place.
  97     pub projections: Vec<Projection<'tcx>>,
  98 }
  99
 100 impl<'tcx> Place<'tcx> {
 101     /// Returns an iterator of the types that have to be dereferenced to access
 102     /// the `Place`.
 103     ///
 104     /// The types are in the reverse order that they are applied. So if
 105     /// `x: &*const u32` and the `Place` is `**x`, then the types returned are
 106     ///`*const u32` then `&*const u32`.
 107     crate fn deref_tys(&self) -> impl Iterator<Item = Ty<'tcx>> + '_ {
 108         self.projections.iter().rev().filter_map(|proj| {
 109             if let Projection::Deref(deref_ty) = *proj { Some(deref_ty) } else { None }
 110         })
 111     }
 112 }
 113
 114 crate trait HirNode {
 115     fn hir_id(&self) -> hir::HirId;
 116     fn span(&self) -> Span;
 117 }
 118
 119 impl HirNode for hir::Expr<'_> {
 120     fn hir_id(&self) -> hir::HirId {
 121         self.hir_id
 122     }
 123     fn span(&self) -> Span {
 124         self.span
 125     }
 126 }
 127
 128 impl HirNode for hir::Pat<'_> {
 129     fn hir_id(&self) -> hir::HirId {
 130         self.hir_id
 131     }
 132     fn span(&self) -> Span {
 133         self.span
 134     }
 135 }
 136
 137 #[derive(Clone)]
 138 crate struct MemCategorizationContext<'a, 'tcx> {
 139     crate tables: &'a ty::TypeckTables<'tcx>,
 140     infcx: &'a InferCtxt<'a, 'tcx>,
 141     param_env: ty::ParamEnv<'tcx>,
 142     body_owner: DefId,
 143     upvars: Option<&'tcx FxIndexMap<hir::HirId, hir::Upvar>>,
 144 }
 145
 146 crate type McResult<T> = Result<T, ()>;
 147
 148 impl<'a, 'tcx> MemCategorizationContext<'a, 'tcx> {
 149     /// Creates a `MemCategorizationContext`.
 150     crate fn new(
 151         infcx: &'a InferCtxt<'a, 'tcx>,
 152         param_env: ty::ParamEnv<'tcx>,
 153         body_owner: DefId,
 154         tables: &'a ty::TypeckTables<'tcx>,
 155     ) -> MemCategorizationContext<'a, 'tcx> {
 156         MemCategorizationContext {
 157             tables,
 158             infcx,
 159             param_env,
 160             body_owner,
 161             upvars: infcx.tcx.upvars(body_owner),
 162         }
 163     }
 164
 165     crate fn tcx(&self) -> TyCtxt<'tcx> {
 166         self.infcx.tcx
 167     }
 168
 169     crate fn type_is_copy_modulo_regions(&self, ty: Ty<'tcx>, span: Span) -> bool {
 170         self.infcx.type_is_copy_modulo_regions(self.param_env, ty, span)
 171     }
 172
 173     fn resolve_vars_if_possible<T>(&self, value: &T) -> T
 174     where
 175         T: TypeFoldable<'tcx>,
 176     {
 177         self.infcx.resolve_vars_if_possible(value)
 178     }
 179
 180     fn is_tainted_by_errors(&self) -> bool {
 181         self.infcx.is_tainted_by_errors()
 182     }
 183
 184     fn resolve_type_vars_or_error(
 185         &self,
 186         id: hir::HirId,
 187         ty: Option<Ty<'tcx>>,
 188     ) -> McResult<Ty<'tcx>> {
 189         match ty {
 190             Some(ty) => {
 191                 let ty = self.resolve_vars_if_possible(&ty);
 192                 if ty.references_error() || ty.is_ty_var() {
 193                     debug!("resolve_type_vars_or_error: error from {:?}", ty);
 194                     Err(())
 195                 } else {
 196                     Ok(ty)
 197                 }
 198             }
 199             // FIXME
 200             None if self.is_tainted_by_errors() => Err(()),
 201             None => {
 202                 bug!(
 203                     "no type for node {}: {} in mem_categorization",
 204                     id,
 205                     self.tcx().hir().node_to_string(id)
 206                 );
 207             }
 208         }
 209     }
 210
 211     crate fn node_ty(&self, hir_id: hir::HirId) -> McResult<Ty<'tcx>> {
 212         self.resolve_type_vars_or_error(hir_id, self.tables.node_type_opt(hir_id))
 213     }
 214
 215     fn expr_ty(&self, expr: &hir::Expr<'_>) -> McResult<Ty<'tcx>> {
 216         self.resolve_type_vars_or_error(expr.hir_id, self.tables.expr_ty_opt(expr))
 217     }
 218
 219     crate fn expr_ty_adjusted(&self, expr: &hir::Expr<'_>) -> McResult<Ty<'tcx>> {
 220         self.resolve_type_vars_or_error(expr.hir_id, self.tables.expr_ty_adjusted_opt(expr))
 221     }
 222
 223     /// Returns the type of value that this pattern matches against.
 224     /// Some non-obvious cases:
 225     ///
 226     /// - a `ref x` binding matches against a value of type `T` and gives
 227     ///   `x` the type `&T`; we return `T`.
 228     /// - a pattern with implicit derefs (thanks to default binding
 229     ///   modes #42640) may look like `Some(x)` but in fact have
 230     ///   implicit deref patterns attached (e.g., it is really
 231     ///   `&Some(x)`). In that case, we return the "outermost" type
 232     ///   (e.g., `&Option<T>).
 233     crate fn pat_ty_adjusted(&self, pat: &hir::Pat<'_>) -> McResult<Ty<'tcx>> {
 234         // Check for implicit `&` types wrapping the pattern; note
 235         // that these are never attached to binding patterns, so
 236         // actually this is somewhat "disjoint" from the code below
 237         // that aims to account for `ref x`.
 238         if let Some(vec) = self.tables.pat_adjustments().get(pat.hir_id) {
 239             if let Some(first_ty) = vec.first() {
 240                 debug!("pat_ty(pat={:?}) found adjusted ty `{:?}`", pat, first_ty);
 241                 return Ok(first_ty);
 242             }
 243         }
 244
 245         self.pat_ty_unadjusted(pat)
 246     }
 247
 248     /// Like `pat_ty`, but ignores implicit `&` patterns.
 249     fn pat_ty_unadjusted(&self, pat: &hir::Pat<'_>) -> McResult<Ty<'tcx>> {
 250         let base_ty = self.node_ty(pat.hir_id)?;
 251         debug!("pat_ty(pat={:?}) base_ty={:?}", pat, base_ty);
 252
 253         // This code detects whether we are looking at a `ref x`,
 254         // and if so, figures out what the type *being borrowed* is.
 255         let ret_ty = match pat.kind {
 256             PatKind::Binding(..) => {
 257                 let bm =
 258                     *self.tables.pat_binding_modes().get(pat.hir_id).expect("missing binding mode");
 259
 260                 if let ty::BindByReference(_) = bm {
 261                     // a bind-by-ref means that the base_ty will be the type of the ident itself,
 262                     // but what we want here is the type of the underlying value being borrowed.
 263                     // So peel off one-level, turning the &T into T.
 264                     match base_ty.builtin_deref(false) {
 265                         Some(t) => t.ty,
 266                         None => {
 267                             debug!("By-ref binding of non-derefable type {:?}", base_ty);
 268                             return Err(());
 269                         }
 270                     }
 271                 } else {
 272                     base_ty
 273                 }
 274             }
 275             _ => base_ty,
 276         };
 277         debug!("pat_ty(pat={:?}) ret_ty={:?}", pat, ret_ty);
 278
 279         Ok(ret_ty)
 280     }
 281
 282     crate fn cat_expr(&self, expr: &hir::Expr<'_>) -> McResult<Place<'tcx>> {
 283         // This recursion helper avoids going through *too many*
 284         // adjustments, since *only* non-overloaded deref recurses.
 285         fn helper<'a, 'tcx>(
 286             mc: &MemCategorizationContext<'a, 'tcx>,
 287             expr: &hir::Expr<'_>,
 288             adjustments: &[adjustment::Adjustment<'tcx>],
 289         ) -> McResult<Place<'tcx>> {
 290             match adjustments.split_last() {
 291                 None => mc.cat_expr_unadjusted(expr),
 292                 Some((adjustment, previous)) => {
 293                     mc.cat_expr_adjusted_with(expr, || helper(mc, expr, previous), adjustment)
 294                 }
 295             }
 296         }
 297
 298         helper(self, expr, self.tables.expr_adjustments(expr))
 299     }
 300
 301     crate fn cat_expr_adjusted(
 302         &self,
 303         expr: &hir::Expr<'_>,
 304         previous: Place<'tcx>,
 305         adjustment: &adjustment::Adjustment<'tcx>,
 306     ) -> McResult<Place<'tcx>> {
 307         self.cat_expr_adjusted_with(expr, || Ok(previous), adjustment)
 308     }
 309
 310     fn cat_expr_adjusted_with<F>(
 311         &self,
 312         expr: &hir::Expr<'_>,
 313         previous: F,
 314         adjustment: &adjustment::Adjustment<'tcx>,
 315     ) -> McResult<Place<'tcx>>
 316     where
 317         F: FnOnce() -> McResult<Place<'tcx>>,
 318     {
 319         debug!("cat_expr_adjusted_with({:?}): {:?}", adjustment, expr);
 320         let target = self.resolve_vars_if_possible(&adjustment.target);
 321         match adjustment.kind {
 322             adjustment::Adjust::Deref(overloaded) => {
 323                 // Equivalent to *expr or something similar.
 324                 let base = if let Some(deref) = overloaded {
 325                     let ref_ty = self
 326                         .tcx()
 327                         .mk_ref(deref.region, ty::TypeAndMut { ty: target, mutbl: deref.mutbl });
 328                     self.cat_rvalue(expr.hir_id, expr.span, ref_ty)
 329                 } else {
 330                     previous()?
 331                 };
 332                 self.cat_deref(expr, base)
 333             }
 334
 335             adjustment::Adjust::NeverToAny
 336             | adjustment::Adjust::Pointer(_)
 337             | adjustment::Adjust::Borrow(_) => {
 338                 // Result is an rvalue.
 339                 Ok(self.cat_rvalue(expr.hir_id, expr.span, target))
 340             }
 341         }
 342     }
 343
 344     crate fn cat_expr_unadjusted(&self, expr: &hir::Expr<'_>) -> McResult<Place<'tcx>> {
 345         debug!("cat_expr: id={} expr={:?}", expr.hir_id, expr);
 346
 347         let expr_ty = self.expr_ty(expr)?;
 348         match expr.kind {
 349             hir::ExprKind::Unary(hir::UnOp::UnDeref, ref e_base) => {
 350                 if self.tables.is_method_call(expr) {
 351                     self.cat_overloaded_place(expr, e_base)
 352                 } else {
 353                     let base = self.cat_expr(&e_base)?;
 354                     self.cat_deref(expr, base)
 355                 }
 356             }
 357
 358             hir::ExprKind::Field(ref base, _) => {
 359                 let base = self.cat_expr(&base)?;
 360                 debug!("cat_expr(cat_field): id={} expr={:?} base={:?}", expr.hir_id, expr, base);
 361                 Ok(self.cat_projection(expr, base, expr_ty))
 362             }
 363
 364             hir::ExprKind::Index(ref base, _) => {
 365                 if self.tables.is_method_call(expr) {
 366                     // If this is an index implemented by a method call, then it
 367                     // will include an implicit deref of the result.
 368                     // The call to index() returns a `&T` value, which
 369                     // is an rvalue. That is what we will be
 370                     // dereferencing.
 371                     self.cat_overloaded_place(expr, base)
 372                 } else {
 373                     let base = self.cat_expr(&base)?;
 374                     Ok(self.cat_projection(expr, base, expr_ty))
 375                 }
 376             }
 377
 378             hir::ExprKind::Path(ref qpath) => {
 379                 let res = self.tables.qpath_res(qpath, expr.hir_id);
 380                 self.cat_res(expr.hir_id, expr.span, expr_ty, res)
 381             }
 382
 383             hir::ExprKind::Type(ref e, _) => self.cat_expr(&e),
 384
 385             hir::ExprKind::AddrOf(..)
 386             | hir::ExprKind::Call(..)
 387             | hir::ExprKind::Assign(..)
 388             | hir::ExprKind::AssignOp(..)
 389             | hir::ExprKind::Closure(..)
 390             | hir::ExprKind::Ret(..)
 391             | hir::ExprKind::Unary(..)
 392             | hir::ExprKind::Yield(..)
 393             | hir::ExprKind::MethodCall(..)
 394             | hir::ExprKind::Cast(..)
 395             | hir::ExprKind::DropTemps(..)
 396             | hir::ExprKind::Array(..)
 397             | hir::ExprKind::Tup(..)
 398             | hir::ExprKind::Binary(..)
 399             | hir::ExprKind::Block(..)
 400             | hir::ExprKind::Loop(..)
 401             | hir::ExprKind::Match(..)
 402             | hir::ExprKind::Lit(..)
 403             | hir::ExprKind::Break(..)
 404             | hir::ExprKind::Continue(..)
 405             | hir::ExprKind::Struct(..)
 406             | hir::ExprKind::Repeat(..)
 407             | hir::ExprKind::InlineAsm(..)
 408             | hir::ExprKind::Box(..)
 409             | hir::ExprKind::Err => Ok(self.cat_rvalue(expr.hir_id, expr.span, expr_ty)),
 410         }
 411     }
 412
 413     crate fn cat_res(
 414         &self,
 415         hir_id: hir::HirId,
 416         span: Span,
 417         expr_ty: Ty<'tcx>,
 418         res: Res,
 419     ) -> McResult<Place<'tcx>> {
 420         debug!("cat_res: id={:?} expr={:?} def={:?}", hir_id, expr_ty, res);
 421
 422         match res {
 423             Res::Def(DefKind::Ctor(..), _)
 424             | Res::Def(DefKind::Const, _)
 425             | Res::Def(DefKind::ConstParam, _)
 426             | Res::Def(DefKind::AssocConst, _)
 427             | Res::Def(DefKind::Fn, _)
 428             | Res::Def(DefKind::Method, _)
 429             | Res::SelfCtor(..) => Ok(self.cat_rvalue(hir_id, span, expr_ty)),
 430
 431             Res::Def(DefKind::Static, _) => Ok(Place {
 432                 hir_id,
 433                 span,
 434                 ty: expr_ty,
 435                 base: PlaceBase::StaticItem,
 436                 projections: Vec::new(),
 437             }),
 438
 439             Res::Local(var_id) => {
 440                 if self.upvars.map_or(false, |upvars| upvars.contains_key(&var_id)) {
 441                     self.cat_upvar(hir_id, span, var_id)
 442                 } else {
 443                     Ok(Place {
 444                         hir_id,
 445                         span,
 446                         ty: expr_ty,
 447                         base: PlaceBase::Local(var_id),
 448                         projections: Vec::new(),
 449                     })
 450                 }
 451             }
 452
 453             def => span_bug!(span, "unexpected definition in memory categorization: {:?}", def),
 454         }
 455     }
 456
 457     /// Categorize an upvar.
 458     ///
 459     /// Note: the actual upvar access contains invisible derefs of closure
 460     /// environment and upvar reference as appropriate. Only regionck cares
 461     /// about these dereferences, so we let it compute them as needed.
 462     fn cat_upvar(
 463         &self,
 464         hir_id: hir::HirId,
 465         span: Span,
 466         var_id: hir::HirId,
 467     ) -> McResult<Place<'tcx>> {
 468         let closure_expr_def_id = self.body_owner;
 469
 470         let upvar_id = ty::UpvarId {
 471             var_path: ty::UpvarPath { hir_id: var_id },
 472             closure_expr_id: closure_expr_def_id.to_local(),
 473         };
 474         let var_ty = self.node_ty(var_id)?;
 475
 476         let ret = Place {
 477             hir_id,
 478             span,
 479             ty: var_ty,
 480             base: PlaceBase::Upvar(upvar_id),
 481             projections: Vec::new(),
 482         };
 483
 484         debug!("cat_upvar ret={:?}", ret);
 485         Ok(ret)
 486     }
 487
 488     crate fn cat_rvalue(&self, hir_id: hir::HirId, span: Span, expr_ty: Ty<'tcx>) -> Place<'tcx> {
 489         debug!("cat_rvalue hir_id={:?}, expr_ty={:?}, span={:?}", hir_id, expr_ty, span);
 490         let ret =
 491             Place { hir_id, span, base: PlaceBase::Rvalue, projections: Vec::new(), ty: expr_ty };
 492         debug!("cat_rvalue ret={:?}", ret);
 493         ret
 494     }
 495
 496     crate fn cat_projection<N: HirNode>(
 497         &self,
 498         node: &N,
 499         base_place: Place<'tcx>,
 500         ty: Ty<'tcx>,
 501     ) -> Place<'tcx> {
 502         let mut projections = base_place.projections;
 503         projections.push(Projection::Other);
 504         let ret = Place {
 505             hir_id: node.hir_id(),
 506             span: node.span(),
 507             ty,
 508             base: base_place.base,
 509             projections,
 510         };
 511         debug!("cat_field ret {:?}", ret);
 512         ret
 513     }
 514
 515     fn cat_overloaded_place(
 516         &self,
 517         expr: &hir::Expr<'_>,
 518         base: &hir::Expr<'_>,
 519     ) -> McResult<Place<'tcx>> {
 520         debug!("cat_overloaded_place(expr={:?}, base={:?})", expr, base);
 521
 522         // Reconstruct the output assuming it's a reference with the
 523         // same region and mutability as the receiver. This holds for
 524         // `Deref(Mut)::Deref(_mut)` and `Index(Mut)::index(_mut)`.
 525         let place_ty = self.expr_ty(expr)?;
 526         let base_ty = self.expr_ty_adjusted(base)?;
 527
 528         let (region, mutbl) = match base_ty.kind {
 529             ty::Ref(region, _, mutbl) => (region, mutbl),
 530             _ => span_bug!(expr.span, "cat_overloaded_place: base is not a reference"),
 531         };
 532         let ref_ty = self.tcx().mk_ref(region, ty::TypeAndMut { ty: place_ty, mutbl });
 533
 534         let base = self.cat_rvalue(expr.hir_id, expr.span, ref_ty);
 535         self.cat_deref(expr, base)
 536     }
 537
 538     fn cat_deref(&self, node: &impl HirNode, base_place: Place<'tcx>) -> McResult<Place<'tcx>> {
 539         debug!("cat_deref: base_place={:?}", base_place);
 540
 541         let base_ty = base_place.ty;
 542         let deref_ty = match base_ty.builtin_deref(true) {
 543             Some(mt) => mt.ty,
 544             None => {
 545                 debug!("explicit deref of non-derefable type: {:?}", base_ty);
 546                 return Err(());
 547             }
 548         };
 549         let mut projections = base_place.projections;
 550         projections.push(Projection::Deref(base_ty));
 551
 552         let ret = Place {
 553             hir_id: node.hir_id(),
 554             span: node.span(),
 555             ty: deref_ty,
 556             base: base_place.base,
 557             projections,
 558         };
 559         debug!("cat_deref ret {:?}", ret);
 560         Ok(ret)
 561     }
 562
 563     crate fn cat_pattern<F>(
 564         &self,
 565         place: Place<'tcx>,
 566         pat: &hir::Pat<'_>,
 567         mut op: F,
 568     ) -> McResult<()>
 569     where
 570         F: FnMut(&Place<'tcx>, &hir::Pat<'_>),
 571     {
 572         self.cat_pattern_(place, pat, &mut op)
 573     }
 574
 575     // FIXME(#19596) This is a workaround, but there should be a better way to do this
 576     fn cat_pattern_<F>(
 577         &self,
 578         mut place: Place<'tcx>,
 579         pat: &hir::Pat<'_>,
 580         op: &mut F,
 581     ) -> McResult<()>
 582     where
 583         F: FnMut(&Place<'tcx>, &hir::Pat<'_>),
 584     {
 585         // Here, `place` is the `Place` being matched and pat is the pattern it
 586         // is being matched against.
 587         //
 588         // In general, the way that this works is that we walk down the pattern,
 589         // constructing a `Place` that represents the path that will be taken
 590         // to reach the value being matched.
 591
 592         debug!("cat_pattern(pat={:?}, place={:?})", pat, place);
 593
 594         // If (pattern) adjustments are active for this pattern, adjust the `Place` correspondingly.
 595         // `Place`s are constructed differently from patterns. For example, in
 596         //
 597         // ```
 598         // match foo {
 599         //     &&Some(x, ) => { ... },
 600         //     _ => { ... },
 601         // }
 602         // ```
 603         //
 604         // the pattern `&&Some(x,)` is represented as `Ref { Ref { TupleStruct }}`. To build the
 605         // corresponding `Place` we start with the `Place` for `foo`, and then, by traversing the
 606         // pattern, try to answer the question: given the address of `foo`, how is `x` reached?
 607         //
 608         // `&&Some(x,)` `place_foo`
 609         //  `&Some(x,)` `deref { place_foo}`
 610         //   `Some(x,)` `deref { deref { place_foo }}`
 611         //        (x,)` `field0 { deref { deref { place_foo }}}` <- resulting place
 612         //
 613         // The above example has no adjustments. If the code were instead the (after adjustments,
 614         // equivalent) version
 615         //
 616         // ```
 617         // match foo {
 618         //     Some(x, ) => { ... },
 619         //     _ => { ... },
 620         // }
 621         // ```
 622         //
 623         // Then we see that to get the same result, we must start with
 624         // `deref { deref { place_foo }}` instead of `place_foo` since the pattern is now `Some(x,)`
 625         // and not `&&Some(x,)`, even though its assigned type is that of `&&Some(x,)`.
 626         for _ in 0..self.tables.pat_adjustments().get(pat.hir_id).map(|v| v.len()).unwrap_or(0) {
 627             debug!("cat_pattern: applying adjustment to place={:?}", place);
 628             place = self.cat_deref(pat, place)?;
 629         }
 630         let place = place; // lose mutability
 631         debug!("cat_pattern: applied adjustment derefs to get place={:?}", place);
 632
 633         // Invoke the callback, but only now, after the `place` has adjusted.
 634         //
 635         // To see that this makes sense, consider `match &Some(3) { Some(x) => { ... }}`. In that
 636         // case, the initial `place` will be that for `&Some(3)` and the pattern is `Some(x)`. We
 637         // don't want to call `op` with these incompatible values. As written, what happens instead
 638         // is that `op` is called with the adjusted place (that for `*&Some(3)`) and the pattern
 639         // `Some(x)` (which matches). Recursing once more, `*&Some(3)` and the pattern `Some(x)`
 640         // result in the place `Downcast<Some>(*&Some(3)).0` associated to `x` and invoke `op` with
 641         // that (where the `ref` on `x` is implied).
 642         op(&place, pat);
 643
 644         match pat.kind {
 645             PatKind::TupleStruct(_, ref subpats, _) | PatKind::Tuple(ref subpats, _) => {
 646                 // S(p1, ..., pN) or (p1, ..., pN)
 647                 for subpat in subpats.iter() {
 648                     let subpat_ty = self.pat_ty_adjusted(&subpat)?;
 649                     let sub_place = self.cat_projection(pat, place.clone(), subpat_ty);
 650                     self.cat_pattern_(sub_place, &subpat, op)?;
 651                 }
 652             }
 653
 654             PatKind::Struct(_, field_pats, _) => {
 655                 // S { f1: p1, ..., fN: pN }
 656                 for fp in field_pats {
 657                     let field_ty = self.pat_ty_adjusted(&fp.pat)?;
 658                     let field_place = self.cat_projection(pat, place.clone(), field_ty);
 659                     self.cat_pattern_(field_place, &fp.pat, op)?;
 660                 }
 661             }
 662
 663             PatKind::Or(pats) => {
 664                 for pat in pats {
 665                     self.cat_pattern_(place.clone(), &pat, op)?;
 666                 }
 667             }
 668
 669             PatKind::Binding(.., Some(ref subpat)) => {
 670                 self.cat_pattern_(place, &subpat, op)?;
 671             }
 672
 673             PatKind::Box(ref subpat) | PatKind::Ref(ref subpat, _) => {
 674                 // box p1, &p1, &mut p1.  we can ignore the mutability of
 675                 // PatKind::Ref since that information is already contained
 676                 // in the type.
 677                 let subplace = self.cat_deref(pat, place)?;
 678                 self.cat_pattern_(subplace, &subpat, op)?;
 679             }
 680
 681             PatKind::Slice(before, ref slice, after) => {
 682                 let element_ty = match place.ty.builtin_index() {
 683                     Some(ty) => ty,
 684                     None => {
 685                         debug!("explicit index of non-indexable type {:?}", place);
 686                         return Err(());
 687                     }
 688                 };
 689                 let elt_place = self.cat_projection(pat, place.clone(), element_ty);
 690                 for before_pat in before {
 691                     self.cat_pattern_(elt_place.clone(), &before_pat, op)?;
 692                 }
 693                 if let Some(ref slice_pat) = *slice {
 694                     let slice_pat_ty = self.pat_ty_adjusted(&slice_pat)?;
 695                     let slice_place = self.cat_projection(pat, place, slice_pat_ty);
 696                     self.cat_pattern_(slice_place, &slice_pat, op)?;
 697                 }
 698                 for after_pat in after {
 699                     self.cat_pattern_(elt_place.clone(), &after_pat, op)?;
 700                 }
 701             }
 702
 703             PatKind::Path(_)
 704             | PatKind::Binding(.., None)
 705             | PatKind::Lit(..)
 706             | PatKind::Range(..)
 707             | PatKind::Wild => {
 708                 // always ok
 709             }
 710         }
 711
 712         Ok(())
 713     }
 714 }