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