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