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