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.
52 use rustc
::hir
::PatKind
;
53 use rustc
::hir
::def_id
::DefId
;
54 use rustc
::hir
::def
::{Res, DefKind}
;
55 use rustc
::infer
::InferCtxt
;
56 use rustc
::ty
::adjustment
;
57 use rustc
::ty
::{self, Ty, TyCtxt}
;
58 use rustc
::ty
::fold
::TypeFoldable
;
62 use rustc_data_structures
::fx
::FxIndexMap
;
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
| if let Projection
::Deref(deref_ty
) = *proj
{
117 crate trait HirNode
{
118 fn hir_id(&self) -> hir
::HirId
;
119 fn span(&self) -> Span
;
122 impl HirNode
for hir
::Expr
{
123 fn hir_id(&self) -> hir
::HirId { self.hir_id }
124 fn span(&self) -> Span { self.span }
127 impl HirNode
for hir
::Pat
{
128 fn hir_id(&self) -> hir
::HirId { self.hir_id }
129 fn span(&self) -> Span { self.span }
133 crate struct MemCategorizationContext
<'a
, 'tcx
> {
134 crate tables
: &'a ty
::TypeckTables
<'tcx
>,
135 infcx
: &'a InferCtxt
<'a
, 'tcx
>,
136 param_env
: ty
::ParamEnv
<'tcx
>,
138 upvars
: Option
<&'tcx FxIndexMap
<hir
::HirId
, hir
::Upvar
>>,
141 crate type McResult
<T
> = Result
<T
, ()>;
143 impl<'a
, 'tcx
> MemCategorizationContext
<'a
, 'tcx
> {
144 /// Creates a `MemCategorizationContext`.
146 infcx
: &'a InferCtxt
<'a
, 'tcx
>,
147 param_env
: ty
::ParamEnv
<'tcx
>,
149 tables
: &'a ty
::TypeckTables
<'tcx
>,
150 ) -> MemCategorizationContext
<'a
, 'tcx
> {
151 MemCategorizationContext
{
156 upvars
: infcx
.tcx
.upvars(body_owner
),
160 crate fn tcx(&self) -> TyCtxt
<'tcx
> {
164 crate fn type_is_copy_modulo_regions(
169 self.infcx
.type_is_copy_modulo_regions(self.param_env
, ty
, span
)
172 fn resolve_vars_if_possible
<T
>(&self, value
: &T
) -> T
173 where T
: TypeFoldable
<'tcx
>
175 self.infcx
.resolve_vars_if_possible(value
)
178 fn is_tainted_by_errors(&self) -> bool
{
179 self.infcx
.is_tainted_by_errors()
182 fn resolve_type_vars_or_error(&self,
184 ty
: Option
<Ty
<'tcx
>>)
185 -> McResult
<Ty
<'tcx
>> {
188 let ty
= self.resolve_vars_if_possible(&ty
);
189 if ty
.references_error() || ty
.is_ty_var() {
190 debug
!("resolve_type_vars_or_error: error from {:?}", ty
);
197 None
if self.is_tainted_by_errors() => Err(()),
199 bug
!("no type for node {}: {} in mem_categorization",
200 id
, self.tcx().hir().node_to_string(id
));
205 crate fn node_ty(&self, hir_id
: hir
::HirId
) -> McResult
<Ty
<'tcx
>> {
206 self.resolve_type_vars_or_error(hir_id
, self.tables
.node_type_opt(hir_id
))
209 fn expr_ty(&self, expr
: &hir
::Expr
) -> McResult
<Ty
<'tcx
>> {
210 self.resolve_type_vars_or_error(expr
.hir_id
, self.tables
.expr_ty_opt(expr
))
213 crate fn expr_ty_adjusted(&self, expr
: &hir
::Expr
) -> McResult
<Ty
<'tcx
>> {
214 self.resolve_type_vars_or_error(expr
.hir_id
, self.tables
.expr_ty_adjusted_opt(expr
))
217 /// Returns the type of value that this pattern matches against.
218 /// Some non-obvious cases:
220 /// - a `ref x` binding matches against a value of type `T` and gives
221 /// `x` the type `&T`; we return `T`.
222 /// - a pattern with implicit derefs (thanks to default binding
223 /// modes #42640) may look like `Some(x)` but in fact have
224 /// implicit deref patterns attached (e.g., it is really
225 /// `&Some(x)`). In that case, we return the "outermost" type
226 /// (e.g., `&Option<T>).
227 crate fn pat_ty_adjusted(&self, pat
: &hir
::Pat
) -> McResult
<Ty
<'tcx
>> {
228 // Check for implicit `&` types wrapping the pattern; note
229 // that these are never attached to binding patterns, so
230 // actually this is somewhat "disjoint" from the code below
231 // that aims to account for `ref x`.
232 if let Some(vec
) = self.tables
.pat_adjustments().get(pat
.hir_id
) {
233 if let Some(first_ty
) = vec
.first() {
234 debug
!("pat_ty(pat={:?}) found adjusted ty `{:?}`", pat
, first_ty
);
239 self.pat_ty_unadjusted(pat
)
243 /// Like `pat_ty`, but ignores implicit `&` patterns.
244 fn pat_ty_unadjusted(&self, pat
: &hir
::Pat
) -> McResult
<Ty
<'tcx
>> {
245 let base_ty
= self.node_ty(pat
.hir_id
)?
;
246 debug
!("pat_ty(pat={:?}) base_ty={:?}", pat
, base_ty
);
248 // This code detects whether we are looking at a `ref x`,
249 // and if so, figures out what the type *being borrowed* is.
250 let ret_ty
= match pat
.kind
{
251 PatKind
::Binding(..) => {
252 let bm
= *self.tables
255 .expect("missing binding mode");
257 if let ty
::BindByReference(_
) = bm
{
258 // a bind-by-ref means that the base_ty will be the type of the ident itself,
259 // but what we want here is the type of the underlying value being borrowed.
260 // So peel off one-level, turning the &T into T.
261 match base_ty
.builtin_deref(false) {
264 debug
!("By-ref binding of non-derefable type {:?}", base_ty
);
274 debug
!("pat_ty(pat={:?}) ret_ty={:?}", pat
, ret_ty
);
279 crate fn cat_expr(&self, expr
: &hir
::Expr
) -> McResult
<Place
<'tcx
>> {
280 // This recursion helper avoids going through *too many*
281 // adjustments, since *only* non-overloaded deref recurses.
283 mc
: &MemCategorizationContext
<'a
, 'tcx
>,
285 adjustments
: &[adjustment
::Adjustment
<'tcx
>],
286 ) -> McResult
<Place
<'tcx
>> {
287 match adjustments
.split_last() {
288 None
=> mc
.cat_expr_unadjusted(expr
),
289 Some((adjustment
, previous
)) => {
290 mc
.cat_expr_adjusted_with(expr
, || helper(mc
, expr
, previous
), adjustment
)
295 helper(self, expr
, self.tables
.expr_adjustments(expr
))
298 crate fn cat_expr_adjusted(&self, expr
: &hir
::Expr
,
299 previous
: Place
<'tcx
>,
300 adjustment
: &adjustment
::Adjustment
<'tcx
>)
301 -> McResult
<Place
<'tcx
>> {
302 self.cat_expr_adjusted_with(expr
, || Ok(previous
), adjustment
)
305 fn cat_expr_adjusted_with
<F
>(&self, expr
: &hir
::Expr
,
307 adjustment
: &adjustment
::Adjustment
<'tcx
>)
308 -> McResult
<Place
<'tcx
>>
309 where F
: FnOnce() -> McResult
<Place
<'tcx
>>
311 debug
!("cat_expr_adjusted_with({:?}): {:?}", adjustment
, expr
);
312 let target
= self.resolve_vars_if_possible(&adjustment
.target
);
313 match adjustment
.kind
{
314 adjustment
::Adjust
::Deref(overloaded
) => {
315 // Equivalent to *expr or something similar.
316 let base
= if let Some(deref
) = overloaded
{
317 let ref_ty
= self.tcx().mk_ref(deref
.region
, ty
::TypeAndMut
{
321 self.cat_rvalue(expr
.hir_id
, expr
.span
, ref_ty
)
325 self.cat_deref(expr
, base
)
328 adjustment
::Adjust
::NeverToAny
|
329 adjustment
::Adjust
::Pointer(_
) |
330 adjustment
::Adjust
::Borrow(_
) => {
331 // Result is an rvalue.
332 Ok(self.cat_rvalue(expr
.hir_id
, expr
.span
, target
))
337 crate fn cat_expr_unadjusted(&self, expr
: &hir
::Expr
) -> McResult
<Place
<'tcx
>> {
338 debug
!("cat_expr: id={} expr={:?}", expr
.hir_id
, expr
);
340 let expr_ty
= self.expr_ty(expr
)?
;
342 hir
::ExprKind
::Unary(hir
::UnDeref
, ref e_base
) => {
343 if self.tables
.is_method_call(expr
) {
344 self.cat_overloaded_place(expr
, e_base
)
346 let base
= self.cat_expr(&e_base
)?
;
347 self.cat_deref(expr
, base
)
351 hir
::ExprKind
::Field(ref base
, _
) => {
352 let base
= self.cat_expr(&base
)?
;
353 debug
!("cat_expr(cat_field): id={} expr={:?} base={:?}",
357 Ok(self.cat_projection(expr
, base
, expr_ty
))
360 hir
::ExprKind
::Index(ref base
, _
) => {
361 if self.tables
.is_method_call(expr
) {
362 // If this is an index implemented by a method call, then it
363 // will include an implicit deref of the result.
364 // The call to index() returns a `&T` value, which
365 // is an rvalue. That is what we will be
367 self.cat_overloaded_place(expr
, base
)
369 let base
= self.cat_expr(&base
)?
;
370 Ok(self.cat_projection(expr
, base
, expr_ty
))
374 hir
::ExprKind
::Path(ref qpath
) => {
375 let res
= self.tables
.qpath_res(qpath
, expr
.hir_id
);
376 self.cat_res(expr
.hir_id
, expr
.span
, expr_ty
, res
)
379 hir
::ExprKind
::Type(ref e
, _
) => {
383 hir
::ExprKind
::AddrOf(..) | hir
::ExprKind
::Call(..) |
384 hir
::ExprKind
::Assign(..) | hir
::ExprKind
::AssignOp(..) |
385 hir
::ExprKind
::Closure(..) | hir
::ExprKind
::Ret(..) |
386 hir
::ExprKind
::Unary(..) | hir
::ExprKind
::Yield(..) |
387 hir
::ExprKind
::MethodCall(..) | hir
::ExprKind
::Cast(..) | hir
::ExprKind
::DropTemps(..) |
388 hir
::ExprKind
::Array(..) | hir
::ExprKind
::Tup(..) |
389 hir
::ExprKind
::Binary(..) |
390 hir
::ExprKind
::Block(..) | hir
::ExprKind
::Loop(..) | hir
::ExprKind
::Match(..) |
391 hir
::ExprKind
::Lit(..) | hir
::ExprKind
::Break(..) |
392 hir
::ExprKind
::Continue(..) | hir
::ExprKind
::Struct(..) | hir
::ExprKind
::Repeat(..) |
393 hir
::ExprKind
::InlineAsm(..) | hir
::ExprKind
::Box(..) | hir
::ExprKind
::Err
=> {
394 Ok(self.cat_rvalue(expr
.hir_id
, expr
.span
, expr_ty
))
399 crate fn cat_res(&self,
404 -> McResult
<Place
<'tcx
>> {
405 debug
!("cat_res: id={:?} expr={:?} def={:?}",
406 hir_id
, expr_ty
, res
);
409 Res
::Def(DefKind
::Ctor(..), _
)
410 | Res
::Def(DefKind
::Const
, _
)
411 | Res
::Def(DefKind
::ConstParam
, _
)
412 | Res
::Def(DefKind
::AssocConst
, _
)
413 | Res
::Def(DefKind
::Fn
, _
)
414 | Res
::Def(DefKind
::Method
, _
)
415 | Res
::SelfCtor(..) => {
416 Ok(self.cat_rvalue(hir_id
, span
, expr_ty
))
419 Res
::Def(DefKind
::Static
, _
) => {
424 base
: PlaceBase
::StaticItem
,
425 projections
: Vec
::new(),
429 Res
::Local(var_id
) => {
430 if self.upvars
.map_or(false, |upvars
| upvars
.contains_key(&var_id
)) {
431 self.cat_upvar(hir_id
, span
, var_id
)
437 base
: PlaceBase
::Local(var_id
),
438 projections
: Vec
::new(),
443 def
=> span_bug
!(span
, "unexpected definition in memory categorization: {:?}", def
)
447 /// Categorize an upvar.
449 /// Note: the actual upvar access contains invisible derefs of closure
450 /// environment and upvar reference as appropriate. Only regionck cares
451 /// about these dereferences, so we let it compute them as needed.
457 ) -> McResult
<Place
<'tcx
>> {
458 let closure_expr_def_id
= self.body_owner
;
460 let upvar_id
= ty
::UpvarId
{
461 var_path
: ty
::UpvarPath { hir_id: var_id }
,
462 closure_expr_id
: closure_expr_def_id
.to_local(),
464 let var_ty
= self.node_ty(var_id
)?
;
470 base
: PlaceBase
::Upvar(upvar_id
),
471 projections
: Vec
::new(),
474 debug
!("cat_upvar ret={:?}", ret
);
478 crate fn cat_rvalue(&self, hir_id
: hir
::HirId
, span
: Span
, expr_ty
: Ty
<'tcx
>) -> Place
<'tcx
> {
479 debug
!("cat_rvalue hir_id={:?}, expr_ty={:?}, span={:?}", hir_id
, expr_ty
, span
);
483 base
: PlaceBase
::Rvalue
,
484 projections
: Vec
::new(),
487 debug
!("cat_rvalue ret={:?}", ret
);
491 crate fn cat_projection
<N
: HirNode
>(
494 base_place
: Place
<'tcx
>,
497 let mut projections
= base_place
.projections
;
498 projections
.push(Projection
::Other
);
500 hir_id
: node
.hir_id(),
503 base
: base_place
.base
,
506 debug
!("cat_field ret {:?}", ret
);
510 fn cat_overloaded_place(
514 ) -> McResult
<Place
<'tcx
>> {
515 debug
!("cat_overloaded_place(expr={:?}, base={:?})", expr
, base
);
517 // Reconstruct the output assuming it's a reference with the
518 // same region and mutability as the receiver. This holds for
519 // `Deref(Mut)::Deref(_mut)` and `Index(Mut)::index(_mut)`.
520 let place_ty
= self.expr_ty(expr
)?
;
521 let base_ty
= self.expr_ty_adjusted(base
)?
;
523 let (region
, mutbl
) = match base_ty
.kind
{
524 ty
::Ref(region
, _
, mutbl
) => (region
, mutbl
),
525 _
=> span_bug
!(expr
.span
, "cat_overloaded_place: base is not a reference")
527 let ref_ty
= self.tcx().mk_ref(region
, ty
::TypeAndMut
{
532 let base
= self.cat_rvalue(expr
.hir_id
, expr
.span
, ref_ty
);
533 self.cat_deref(expr
, base
)
539 base_place
: Place
<'tcx
>,
540 ) -> McResult
<Place
<'tcx
>> {
541 debug
!("cat_deref: base_place={:?}", base_place
);
543 let base_ty
= base_place
.ty
;
544 let deref_ty
= match base_ty
.builtin_deref(true) {
547 debug
!("explicit deref of non-derefable type: {:?}", base_ty
);
551 let mut projections
= base_place
.projections
;
552 projections
.push(Projection
::Deref(base_ty
));
555 hir_id
: node
.hir_id(),
558 base
: base_place
.base
,
561 debug
!("cat_deref ret {:?}", ret
);
565 crate fn cat_pattern
<F
>(&self, place
: Place
<'tcx
>, pat
: &hir
::Pat
, mut op
: F
) -> McResult
<()>
566 where F
: FnMut(&Place
<'tcx
>, &hir
::Pat
),
568 self.cat_pattern_(place
, pat
, &mut op
)
571 // FIXME(#19596) This is a workaround, but there should be a better way to do this
572 fn cat_pattern_
<F
>(&self, mut place
: Place
<'tcx
>, pat
: &hir
::Pat
, op
: &mut F
) -> McResult
<()>
573 where F
: FnMut(&Place
<'tcx
>, &hir
::Pat
)
575 // Here, `place` is the `Place` being matched and pat is the pattern it
576 // is being matched against.
578 // In general, the way that this works is that we walk down the pattern,
579 // constructing a `Place` that represents the path that will be taken
580 // to reach the value being matched.
582 debug
!("cat_pattern(pat={:?}, place={:?})", pat
, place
);
584 // If (pattern) adjustments are active for this pattern, adjust the `Place` correspondingly.
585 // `Place`s are constructed differently from patterns. For example, in
589 // &&Some(x, ) => { ... },
594 // the pattern `&&Some(x,)` is represented as `Ref { Ref { TupleStruct }}`. To build the
595 // corresponding `Place` we start with the `Place` for `foo`, and then, by traversing the
596 // pattern, try to answer the question: given the address of `foo`, how is `x` reached?
598 // `&&Some(x,)` `place_foo`
599 // `&Some(x,)` `deref { place_foo}`
600 // `Some(x,)` `deref { deref { place_foo }}`
601 // (x,)` `field0 { deref { deref { place_foo }}}` <- resulting place
603 // The above example has no adjustments. If the code were instead the (after adjustments,
604 // equivalent) version
608 // Some(x, ) => { ... },
613 // Then we see that to get the same result, we must start with
614 // `deref { deref { place_foo }}` instead of `place_foo` since the pattern is now `Some(x,)`
615 // and not `&&Some(x,)`, even though its assigned type is that of `&&Some(x,)`.
616 for _
in 0..self.tables
622 debug
!("cat_pattern: applying adjustment to place={:?}", place
);
623 place
= self.cat_deref(pat
, place
)?
;
625 let place
= place
; // lose mutability
626 debug
!("cat_pattern: applied adjustment derefs to get place={:?}", place
);
628 // Invoke the callback, but only now, after the `place` has adjusted.
630 // To see that this makes sense, consider `match &Some(3) { Some(x) => { ... }}`. In that
631 // case, the initial `place` will be that for `&Some(3)` and the pattern is `Some(x)`. We
632 // don't want to call `op` with these incompatible values. As written, what happens instead
633 // is that `op` is called with the adjusted place (that for `*&Some(3)`) and the pattern
634 // `Some(x)` (which matches). Recursing once more, `*&Some(3)` and the pattern `Some(x)`
635 // result in the place `Downcast<Some>(*&Some(3)).0` associated to `x` and invoke `op` with
636 // that (where the `ref` on `x` is implied).
640 PatKind
::TupleStruct(_
, ref subpats
, _
)
641 | PatKind
::Tuple(ref subpats
, _
) => {
642 // S(p1, ..., pN) or (p1, ..., pN)
643 for subpat
in subpats
.iter() {
644 let subpat_ty
= self.pat_ty_adjusted(&subpat
)?
;
645 let sub_place
= self.cat_projection(pat
, place
.clone(), subpat_ty
);
646 self.cat_pattern_(sub_place
, &subpat
, op
)?
;
650 PatKind
::Struct(_
, ref field_pats
, _
) => {
651 // S { f1: p1, ..., fN: pN }
652 for fp
in field_pats
{
653 let field_ty
= self.pat_ty_adjusted(&fp
.pat
)?
;
654 let field_place
= self.cat_projection(pat
, place
.clone(), field_ty
);
655 self.cat_pattern_(field_place
, &fp
.pat
, op
)?
;
659 PatKind
::Or(ref pats
) => {
661 self.cat_pattern_(place
.clone(), &pat
, op
)?
;
665 PatKind
::Binding(.., Some(ref subpat
)) => {
666 self.cat_pattern_(place
, &subpat
, op
)?
;
669 PatKind
::Box(ref subpat
) | PatKind
::Ref(ref subpat
, _
) => {
670 // box p1, &p1, &mut p1. we can ignore the mutability of
671 // PatKind::Ref since that information is already contained
673 let subplace
= self.cat_deref(pat
, place
)?
;
674 self.cat_pattern_(subplace
, &subpat
, op
)?
;
677 PatKind
::Slice(ref before
, ref slice
, ref after
) => {
678 let element_ty
= match place
.ty
.builtin_index() {
681 debug
!("explicit index of non-indexable type {:?}", place
);
685 let elt_place
= self.cat_projection(pat
, place
.clone(), element_ty
);
686 for before_pat
in before
{
687 self.cat_pattern_(elt_place
.clone(), &before_pat
, op
)?
;
689 if let Some(ref slice_pat
) = *slice
{
690 let slice_pat_ty
= self.pat_ty_adjusted(&slice_pat
)?
;
691 let slice_place
= self.cat_projection(pat
, place
, slice_pat_ty
);
692 self.cat_pattern_(slice_place
, &slice_pat
, op
)?
;
694 for after_pat
in after
{
695 self.cat_pattern_(elt_place
.clone(), &after_pat
, op
)?
;
699 PatKind
::Path(_
) | PatKind
::Binding(.., None
) |
700 PatKind
::Lit(..) | PatKind
::Range(..) | PatKind
::Wild
=> {