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