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.).
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
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
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.
23 //! Now, `cat_expr()` classifies the expression `Expr` and the address `A = ToAddr(Expr)`
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`.
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.
37 //! ## By-reference upvars
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:
45 //! let inc = || x += y;
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.
51 use rustc::ty::adjustment;
52 use rustc::ty::fold::TypeFoldable;
53 use rustc::ty::{self, Ty, TyCtxt};
55 use rustc_data_structures::fx::FxIndexMap;
57 use rustc_hir::def::{DefKind, Res};
58 use rustc_hir::def_id::DefId;
59 use rustc_hir::PatKind;
60 use rustc_infer::infer::InferCtxt;
62 use rustc_trait_selection::infer::InferCtxtExt;
64 #[derive(Clone, Debug)]
66 /// A temporary variable
68 /// A named `static` item
70 /// A named local variable
72 /// An upvar referenced by closure env
76 #[derive(Clone, Debug)]
77 pub enum Projection<'tcx> {
78 /// A dereference of a pointer, reference or `Box<T>` of the given type
80 /// An index or a field
84 /// A `Place` represents how a value is located in memory.
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.
93 /// The type of the `Place`
95 /// The "outermost" place that holds this value.
97 /// How this place is derived from the base place.
98 pub projections: Vec<Projection<'tcx>>,
101 impl<'tcx> Place<'tcx> {
102 /// Returns an iterator of the types that have to be dereferenced to access
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 }
115 crate trait HirNode {
116 fn hir_id(&self) -> hir::HirId;
117 fn span(&self) -> Span;
120 impl HirNode for hir::Expr<'_> {
121 fn hir_id(&self) -> hir::HirId {
124 fn span(&self) -> Span {
129 impl HirNode for hir::Pat<'_> {
130 fn hir_id(&self) -> hir::HirId {
133 fn span(&self) -> Span {
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>,
144 upvars: Option<&'tcx FxIndexMap<hir::HirId, hir::Upvar>>,
147 crate type McResult<T> = Result<T, ()>;
149 impl<'a, 'tcx> MemCategorizationContext<'a, 'tcx> {
150 /// Creates a `MemCategorizationContext`.
152 infcx: &'a InferCtxt<'a, 'tcx>,
153 param_env: ty::ParamEnv<'tcx>,
155 tables: &'a ty::TypeckTables<'tcx>,
156 ) -> MemCategorizationContext<'a, 'tcx> {
157 MemCategorizationContext {
162 upvars: infcx.tcx.upvars(body_owner),
166 crate fn tcx(&self) -> TyCtxt<'tcx> {
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)
174 fn resolve_vars_if_possible<T>(&self, value: &T) -> T
176 T: TypeFoldable<'tcx>,
178 self.infcx.resolve_vars_if_possible(value)
181 fn is_tainted_by_errors(&self) -> bool {
182 self.infcx.is_tainted_by_errors()
185 fn resolve_type_vars_or_error(
188 ty: Option<Ty<'tcx>>,
189 ) -> McResult<Ty<'tcx>> {
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);
201 None if self.is_tainted_by_errors() => Err(()),
204 "no type for node {}: {} in mem_categorization",
206 self.tcx().hir().node_to_string(id)
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))
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))
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))
224 /// Returns the type of value that this pattern matches against.
225 /// Some non-obvious cases:
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);
246 self.pat_ty_unadjusted(pat)
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);
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(..) => {
259 *self.tables.pat_binding_modes().get(pat.hir_id).expect("missing binding mode");
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) {
268 debug!("By-ref binding of non-derefable type {:?}", base_ty);
278 debug!("pat_ty(pat={:?}) ret_ty={:?}", pat, ret_ty);
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.
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)
299 helper(self, expr, self.tables.expr_adjustments(expr))
302 crate fn cat_expr_adjusted(
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)
311 fn cat_expr_adjusted_with<F>(
313 expr: &hir::Expr<'_>,
315 adjustment: &adjustment::Adjustment<'tcx>,
316 ) -> McResult<Place<'tcx>>
318 F: FnOnce() -> McResult<Place<'tcx>>,
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 {
328 .mk_ref(deref.region, ty::TypeAndMut { ty: target, mutbl: deref.mutbl });
329 self.cat_rvalue(expr.hir_id, expr.span, ref_ty)
333 self.cat_deref(expr, base)
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))
345 crate fn cat_expr_unadjusted(&self, expr: &hir::Expr<'_>) -> McResult<Place<'tcx>> {
346 debug!("cat_expr: id={} expr={:?}", expr.hir_id, expr);
348 let expr_ty = self.expr_ty(expr)?;
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)
354 let base = self.cat_expr(&e_base)?;
355 self.cat_deref(expr, base)
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))
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
372 self.cat_overloaded_place(expr, base)
374 let base = self.cat_expr(&base)?;
375 Ok(self.cat_projection(expr, base, expr_ty))
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)
384 hir::ExprKind::Type(ref e, _) => self.cat_expr(&e),
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::Box(..)
410 | hir::ExprKind::Err => Ok(self.cat_rvalue(expr.hir_id, expr.span, expr_ty)),
420 ) -> McResult<Place<'tcx>> {
421 debug!("cat_res: id={:?} expr={:?} def={:?}", hir_id, expr_ty, res);
424 Res::Def(DefKind::Ctor(..), _)
425 | Res::Def(DefKind::Const, _)
426 | Res::Def(DefKind::ConstParam, _)
427 | Res::Def(DefKind::AssocConst, _)
428 | Res::Def(DefKind::Fn, _)
429 | Res::Def(DefKind::AssocFn, _)
430 | Res::SelfCtor(..) => Ok(self.cat_rvalue(hir_id, span, expr_ty)),
432 Res::Def(DefKind::Static, _) => Ok(Place {
436 base: PlaceBase::StaticItem,
437 projections: Vec::new(),
440 Res::Local(var_id) => {
441 if self.upvars.map_or(false, |upvars| upvars.contains_key(&var_id)) {
442 self.cat_upvar(hir_id, span, var_id)
448 base: PlaceBase::Local(var_id),
449 projections: Vec::new(),
454 def => span_bug!(span, "unexpected definition in memory categorization: {:?}", def),
458 /// Categorize an upvar.
460 /// Note: the actual upvar access contains invisible derefs of closure
461 /// environment and upvar reference as appropriate. Only regionck cares
462 /// about these dereferences, so we let it compute them as needed.
468 ) -> McResult<Place<'tcx>> {
469 let closure_expr_def_id = self.body_owner;
471 let upvar_id = ty::UpvarId {
472 var_path: ty::UpvarPath { hir_id: var_id },
473 closure_expr_id: closure_expr_def_id.expect_local(),
475 let var_ty = self.node_ty(var_id)?;
481 base: PlaceBase::Upvar(upvar_id),
482 projections: Vec::new(),
485 debug!("cat_upvar ret={:?}", ret);
489 crate fn cat_rvalue(&self, hir_id: hir::HirId, span: Span, expr_ty: Ty<'tcx>) -> Place<'tcx> {
490 debug!("cat_rvalue hir_id={:?}, expr_ty={:?}, span={:?}", hir_id, expr_ty, span);
492 Place { hir_id, span, base: PlaceBase::Rvalue, projections: Vec::new(), ty: expr_ty };
493 debug!("cat_rvalue ret={:?}", ret);
497 crate fn cat_projection<N: HirNode>(
500 base_place: Place<'tcx>,
503 let mut projections = base_place.projections;
504 projections.push(Projection::Other);
506 hir_id: node.hir_id(),
509 base: base_place.base,
512 debug!("cat_field ret {:?}", ret);
516 fn cat_overloaded_place(
518 expr: &hir::Expr<'_>,
519 base: &hir::Expr<'_>,
520 ) -> McResult<Place<'tcx>> {
521 debug!("cat_overloaded_place(expr={:?}, base={:?})", expr, base);
523 // Reconstruct the output assuming it's a reference with the
524 // same region and mutability as the receiver. This holds for
525 // `Deref(Mut)::Deref(_mut)` and `Index(Mut)::index(_mut)`.
526 let place_ty = self.expr_ty(expr)?;
527 let base_ty = self.expr_ty_adjusted(base)?;
529 let (region, mutbl) = match base_ty.kind {
530 ty::Ref(region, _, mutbl) => (region, mutbl),
531 _ => span_bug!(expr.span, "cat_overloaded_place: base is not a reference"),
533 let ref_ty = self.tcx().mk_ref(region, ty::TypeAndMut { ty: place_ty, mutbl });
535 let base = self.cat_rvalue(expr.hir_id, expr.span, ref_ty);
536 self.cat_deref(expr, base)
539 fn cat_deref(&self, node: &impl HirNode, base_place: Place<'tcx>) -> McResult<Place<'tcx>> {
540 debug!("cat_deref: base_place={:?}", base_place);
542 let base_ty = base_place.ty;
543 let deref_ty = match base_ty.builtin_deref(true) {
546 debug!("explicit deref of non-derefable type: {:?}", base_ty);
550 let mut projections = base_place.projections;
551 projections.push(Projection::Deref(base_ty));
554 hir_id: node.hir_id(),
557 base: base_place.base,
560 debug!("cat_deref ret {:?}", ret);
564 crate fn cat_pattern<F>(
571 F: FnMut(&Place<'tcx>, &hir::Pat<'_>),
573 self.cat_pattern_(place, pat, &mut op)
576 // FIXME(#19596) This is a workaround, but there should be a better way to do this
579 mut place: Place<'tcx>,
584 F: FnMut(&Place<'tcx>, &hir::Pat<'_>),
586 // Here, `place` is the `Place` being matched and pat is the pattern it
587 // is being matched against.
589 // In general, the way that this works is that we walk down the pattern,
590 // constructing a `Place` that represents the path that will be taken
591 // to reach the value being matched.
593 debug!("cat_pattern(pat={:?}, place={:?})", pat, place);
595 // If (pattern) adjustments are active for this pattern, adjust the `Place` correspondingly.
596 // `Place`s are constructed differently from patterns. For example, in
600 // &&Some(x, ) => { ... },
605 // the pattern `&&Some(x,)` is represented as `Ref { Ref { TupleStruct }}`. To build the
606 // corresponding `Place` we start with the `Place` for `foo`, and then, by traversing the
607 // pattern, try to answer the question: given the address of `foo`, how is `x` reached?
609 // `&&Some(x,)` `place_foo`
610 // `&Some(x,)` `deref { place_foo}`
611 // `Some(x,)` `deref { deref { place_foo }}`
612 // (x,)` `field0 { deref { deref { place_foo }}}` <- resulting place
614 // The above example has no adjustments. If the code were instead the (after adjustments,
615 // equivalent) version
619 // Some(x, ) => { ... },
624 // Then we see that to get the same result, we must start with
625 // `deref { deref { place_foo }}` instead of `place_foo` since the pattern is now `Some(x,)`
626 // and not `&&Some(x,)`, even though its assigned type is that of `&&Some(x,)`.
627 for _ in 0..self.tables.pat_adjustments().get(pat.hir_id).map(|v| v.len()).unwrap_or(0) {
628 debug!("cat_pattern: applying adjustment to place={:?}", place);
629 place = self.cat_deref(pat, place)?;
631 let place = place; // lose mutability
632 debug!("cat_pattern: applied adjustment derefs to get place={:?}", place);
634 // Invoke the callback, but only now, after the `place` has adjusted.
636 // To see that this makes sense, consider `match &Some(3) { Some(x) => { ... }}`. In that
637 // case, the initial `place` will be that for `&Some(3)` and the pattern is `Some(x)`. We
638 // don't want to call `op` with these incompatible values. As written, what happens instead
639 // is that `op` is called with the adjusted place (that for `*&Some(3)`) and the pattern
640 // `Some(x)` (which matches). Recursing once more, `*&Some(3)` and the pattern `Some(x)`
641 // result in the place `Downcast<Some>(*&Some(3)).0` associated to `x` and invoke `op` with
642 // that (where the `ref` on `x` is implied).
646 PatKind::TupleStruct(_, ref subpats, _) | PatKind::Tuple(ref subpats, _) => {
647 // S(p1, ..., pN) or (p1, ..., pN)
648 for subpat in subpats.iter() {
649 let subpat_ty = self.pat_ty_adjusted(&subpat)?;
650 let sub_place = self.cat_projection(pat, place.clone(), subpat_ty);
651 self.cat_pattern_(sub_place, &subpat, op)?;
655 PatKind::Struct(_, field_pats, _) => {
656 // S { f1: p1, ..., fN: pN }
657 for fp in field_pats {
658 let field_ty = self.pat_ty_adjusted(&fp.pat)?;
659 let field_place = self.cat_projection(pat, place.clone(), field_ty);
660 self.cat_pattern_(field_place, &fp.pat, op)?;
664 PatKind::Or(pats) => {
666 self.cat_pattern_(place.clone(), &pat, op)?;
670 PatKind::Binding(.., Some(ref subpat)) => {
671 self.cat_pattern_(place, &subpat, op)?;
674 PatKind::Box(ref subpat) | PatKind::Ref(ref subpat, _) => {
675 // box p1, &p1, &mut p1. we can ignore the mutability of
676 // PatKind::Ref since that information is already contained
678 let subplace = self.cat_deref(pat, place)?;
679 self.cat_pattern_(subplace, &subpat, op)?;
682 PatKind::Slice(before, ref slice, after) => {
683 let element_ty = match place.ty.builtin_index() {
686 debug!("explicit index of non-indexable type {:?}", place);
690 let elt_place = self.cat_projection(pat, place.clone(), element_ty);
691 for before_pat in before {
692 self.cat_pattern_(elt_place.clone(), &before_pat, op)?;
694 if let Some(ref slice_pat) = *slice {
695 let slice_pat_ty = self.pat_ty_adjusted(&slice_pat)?;
696 let slice_place = self.cat_projection(pat, place, slice_pat_ty);
697 self.cat_pattern_(slice_place, &slice_pat, op)?;
699 for after_pat in after {
700 self.cat_pattern_(elt_place.clone(), &after_pat, op)?;
705 | PatKind::Binding(.., None)