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