1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
14 * The job of the categorization module is to analyze an expression to
15 * determine what kind of memory is used in evaluating it (for example,
16 * where dereferences occur and what kind of pointer is dereferenced;
17 * whether the memory is mutable; etc)
19 * Categorization effectively transforms all of our expressions into
20 * expressions of the following forms (the actual enum has many more
21 * possibilities, naturally, but they are all variants of these base
24 * E = rvalue // some computed rvalue
25 * | x // address of a local variable or argument
26 * | *E // deref of a ptr
27 * | E.comp // access to an interior component
29 * Imagine a routine ToAddr(Expr) that evaluates an expression and returns an
30 * address where the result is to be found. If Expr is an lvalue, then this
31 * is the address of the lvalue. If Expr is an rvalue, this is the address of
32 * some temporary spot in memory where the result is stored.
34 * Now, cat_expr() classifies the expression Expr and the address A=ToAddr(Expr)
37 * - cat: what kind of expression was this? This is a subset of the
38 * full expression forms which only includes those that we care about
39 * for the purpose of the analysis.
40 * - mutbl: mutability of the address A
41 * - ty: the type of data found at the address A
43 * The resulting categorization tree differs somewhat from the expressions
44 * themselves. For example, auto-derefs are explicit. Also, an index a[b] is
45 * decomposed into two operations: a dereference to reach the array data and
46 * then an index to jump forward to the relevant item.
48 * ## By-reference upvars
50 * One part of the translation which may be non-obvious is that we translate
51 * closure upvars into the dereference of a borrowed pointer; this more closely
52 * resembles the runtime translation. So, for example, if we had:
56 * let inc = || x += y;
58 * Then when we categorize `x` (*within* the closure) we would yield a
59 * result of `*x'`, effectively, where `x'` is a `cat_upvar` reference
60 * tied to `x`. The type of `x'` will be a borrowed pointer.
63 #![allow(non_camel_case_types)]
65 pub use self::PointerKind::*;
66 pub use self::InteriorKind::*;
67 pub use self::FieldName::*;
68 pub use self::ElementKind::*;
69 pub use self::MutabilityCategory::*;
70 pub use self::InteriorSafety::*;
71 pub use self::AliasableReason::*;
72 pub use self::Note::*;
73 pub use self::deref_kind::*;
74 pub use self::categorization::*;
78 use middle::ty::{mod, Ty};
80 use util::nodemap::{DefIdMap, NodeMap};
81 use util::ppaux::{ty_to_string, Repr};
83 use syntax::ast::{MutImmutable, MutMutable};
86 use syntax::codemap::Span;
87 use syntax::print::pprust;
88 use syntax::parse::token;
90 use std::cell::RefCell;
93 #[deriving(Clone, PartialEq, Show)]
94 pub enum categorization<'tcx> {
95 cat_rvalue(ty::Region), // temporary val, argument is its scope
97 cat_upvar(Upvar), // upvar referenced by closure env
98 cat_local(ast::NodeId), // local variable
99 cat_deref(cmt<'tcx>, uint, PointerKind), // deref of a ptr
100 cat_interior(cmt<'tcx>, InteriorKind), // something interior: field, tuple, etc
101 cat_downcast(cmt<'tcx>, ast::DefId), // selects a particular enum variant (*1)
103 // (*1) downcast is only required if the enum has more than one variant
106 // Represents any kind of upvar
107 #[deriving(Clone, PartialEq, Show)]
110 // Unboxed closure kinds are used even for old-style closures for simplicity
111 pub kind: ty::UnboxedClosureKind,
112 // Is this from an unboxed closure? Used only for diagnostics.
116 // different kinds of pointers:
117 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
118 pub enum PointerKind {
120 BorrowedPtr(ty::BorrowKind, ty::Region),
121 Implicit(ty::BorrowKind, ty::Region), // Implicit deref of a borrowed ptr.
122 UnsafePtr(ast::Mutability)
125 // We use the term "interior" to mean "something reachable from the
126 // base without a pointer dereference", e.g. a field
127 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
128 pub enum InteriorKind {
129 InteriorField(FieldName),
130 InteriorElement(ElementKind),
133 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
135 NamedField(ast::Name),
136 PositionalField(uint)
139 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
140 pub enum ElementKind {
145 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
146 pub enum MutabilityCategory {
147 McImmutable, // Immutable.
148 McDeclared, // Directly declared as mutable.
149 McInherited, // Inherited from the fact that owner is mutable.
152 // A note about the provenance of a `cmt`. This is used for
153 // special-case handling of upvars such as mutability inference.
154 // Upvar categorization can generate a variable number of nested
155 // derefs. The note allows detecting them without deep pattern
156 // matching on the categorization.
157 #[deriving(Clone, PartialEq, Show)]
159 NoteClosureEnv(ty::UpvarId), // Deref through closure env
160 NoteUpvarRef(ty::UpvarId), // Deref through by-ref upvar
161 NoteNone // Nothing special
164 // `cmt`: "Category, Mutability, and Type".
166 // a complete categorization of a value indicating where it originated
167 // and how it is located, as well as the mutability of the memory in
168 // which the value is stored.
170 // *WARNING* The field `cmt.type` is NOT necessarily the same as the
171 // result of `node_id_to_type(cmt.id)`. This is because the `id` is
172 // always the `id` of the node producing the type; in an expression
173 // like `*x`, the type of this deref node is the deref'd type (`T`),
174 // but in a pattern like `@x`, the `@x` pattern is again a
175 // dereference, but its type is the type *before* the dereference
176 // (`@T`). So use `cmt.ty` to find the type of the value in a consistent
177 // fashion. For more details, see the method `cat_pattern`
178 #[deriving(Clone, PartialEq, Show)]
179 pub struct cmt_<'tcx> {
180 pub id: ast::NodeId, // id of expr/pat producing this value
181 pub span: Span, // span of same expr/pat
182 pub cat: categorization<'tcx>, // categorization of expr
183 pub mutbl: MutabilityCategory, // mutability of expr as lvalue
184 pub ty: Ty<'tcx>, // type of the expr (*see WARNING above*)
185 pub note: Note, // Note about the provenance of this cmt
188 pub type cmt<'tcx> = Rc<cmt_<'tcx>>;
190 // We pun on *T to mean both actual deref of a ptr as well
191 // as accessing of components:
192 pub enum deref_kind {
193 deref_ptr(PointerKind),
194 deref_interior(InteriorKind),
197 // Categorizes a derefable type. Note that we include vectors and strings as
198 // derefable (we model an index as the combination of a deref and then a
199 // pointer adjustment).
200 pub fn opt_deref_kind(t: Ty) -> Option<deref_kind> {
203 ty::ty_closure(box ty::ClosureTy {store: ty::UniqTraitStore, ..}) => {
204 Some(deref_ptr(OwnedPtr))
207 ty::ty_rptr(r, mt) => {
208 let kind = ty::BorrowKind::from_mutbl(mt.mutbl);
209 Some(deref_ptr(BorrowedPtr(kind, r)))
212 ty::ty_closure(box ty::ClosureTy {
213 store: ty::RegionTraitStore(r, _),
216 Some(deref_ptr(BorrowedPtr(ty::ImmBorrow, r)))
219 ty::ty_ptr(ref mt) => {
220 Some(deref_ptr(UnsafePtr(mt.mutbl)))
224 ty::ty_struct(..) => { // newtype
225 Some(deref_interior(InteriorField(PositionalField(0))))
228 ty::ty_vec(_, _) | ty::ty_str => {
229 Some(deref_interior(InteriorElement(element_kind(t))))
236 pub fn deref_kind<'tcx>(tcx: &ty::ctxt<'tcx>, t: Ty<'tcx>) -> deref_kind {
237 debug!("deref_kind {}", ty_to_string(tcx, t));
238 match opt_deref_kind(t) {
242 format!("deref_kind() invoked on non-derefable type {}",
243 ty_to_string(tcx, t)).as_slice());
249 fn id(&self) -> ast::NodeId;
250 fn span(&self) -> Span;
253 impl ast_node for ast::Expr {
254 fn id(&self) -> ast::NodeId { self.id }
255 fn span(&self) -> Span { self.span }
258 impl ast_node for ast::Pat {
259 fn id(&self) -> ast::NodeId { self.id }
260 fn span(&self) -> Span { self.span }
263 pub struct MemCategorizationContext<'t,TYPER:'t> {
267 pub type McResult<T> = Result<T, ()>;
270 * The `Typer` trait provides the interface for the mem-categorization
271 * module to the results of the type check. It can be used to query
272 * the type assigned to an expression node, to inquire after adjustments,
275 * This interface is needed because mem-categorization is used from
276 * two places: `regionck` and `borrowck`. `regionck` executes before
277 * type inference is complete, and hence derives types and so on from
278 * intermediate tables. This also implies that type errors can occur,
279 * and hence `node_ty()` and friends return a `Result` type -- any
280 * error will propagate back up through the mem-categorization
283 * In the borrow checker, in contrast, type checking is complete and we
284 * know that no errors have occurred, so we simply consult the tcx and we
285 * can be sure that only `Ok` results will occur.
287 pub trait Typer<'tcx> {
288 fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx>;
289 fn node_ty(&self, id: ast::NodeId) -> McResult<Ty<'tcx>>;
290 fn node_method_ty(&self, method_call: typeck::MethodCall) -> Option<Ty<'tcx>>;
291 fn adjustments<'a>(&'a self) -> &'a RefCell<NodeMap<ty::AutoAdjustment<'tcx>>>;
292 fn is_method_call(&self, id: ast::NodeId) -> bool;
293 fn temporary_scope(&self, rvalue_id: ast::NodeId) -> Option<region::CodeExtent>;
294 fn upvar_borrow(&self, upvar_id: ty::UpvarId) -> ty::UpvarBorrow;
295 fn capture_mode(&self, closure_expr_id: ast::NodeId)
296 -> ast::CaptureClause;
297 fn unboxed_closures<'a>(&'a self)
298 -> &'a RefCell<DefIdMap<ty::UnboxedClosure<'tcx>>>;
301 impl MutabilityCategory {
302 pub fn from_mutbl(m: ast::Mutability) -> MutabilityCategory {
304 MutImmutable => McImmutable,
305 MutMutable => McDeclared
309 pub fn from_borrow_kind(borrow_kind: ty::BorrowKind) -> MutabilityCategory {
311 ty::ImmBorrow => McImmutable,
312 ty::UniqueImmBorrow => McImmutable,
313 ty::MutBorrow => McDeclared,
317 pub fn from_pointer_kind(base_mutbl: MutabilityCategory,
318 ptr: PointerKind) -> MutabilityCategory {
323 BorrowedPtr(borrow_kind, _) | Implicit(borrow_kind, _) => {
324 MutabilityCategory::from_borrow_kind(borrow_kind)
327 MutabilityCategory::from_mutbl(m)
332 fn from_local(tcx: &ty::ctxt, id: ast::NodeId) -> MutabilityCategory {
333 match tcx.map.get(id) {
334 ast_map::NodeLocal(p) | ast_map::NodeArg(p) => match p.node {
335 ast::PatIdent(bind_mode, _, _) => {
336 if bind_mode == ast::BindByValue(ast::MutMutable) {
342 _ => tcx.sess.span_bug(p.span, "expected identifier pattern")
344 _ => tcx.sess.span_bug(tcx.map.span(id), "expected identifier pattern")
348 pub fn inherit(&self) -> MutabilityCategory {
350 McImmutable => McImmutable,
351 McDeclared => McInherited,
352 McInherited => McInherited,
356 pub fn is_mutable(&self) -> bool {
358 McImmutable => false,
364 pub fn is_immutable(&self) -> bool {
367 McDeclared | McInherited => false
371 pub fn to_user_str(&self) -> &'static str {
373 McDeclared | McInherited => "mutable",
374 McImmutable => "immutable",
383 Err(e) => { return Err(e); }
388 impl<'t,'tcx,TYPER:Typer<'tcx>> MemCategorizationContext<'t,TYPER> {
389 pub fn new(typer: &'t TYPER) -> MemCategorizationContext<'t,TYPER> {
390 MemCategorizationContext { typer: typer }
393 fn tcx(&self) -> &'t ty::ctxt<'tcx> {
397 fn expr_ty(&self, expr: &ast::Expr) -> McResult<Ty<'tcx>> {
398 self.typer.node_ty(expr.id)
401 fn expr_ty_adjusted(&self, expr: &ast::Expr) -> McResult<Ty<'tcx>> {
402 let unadjusted_ty = if_ok!(self.expr_ty(expr));
403 Ok(ty::adjust_ty(self.tcx(), expr.span, expr.id, unadjusted_ty,
404 self.typer.adjustments().borrow().get(&expr.id),
405 |method_call| self.typer.node_method_ty(method_call)))
408 fn node_ty(&self, id: ast::NodeId) -> McResult<Ty<'tcx>> {
409 self.typer.node_ty(id)
412 fn pat_ty(&self, pat: &ast::Pat) -> McResult<Ty<'tcx>> {
413 let tcx = self.typer.tcx();
414 let base_ty = self.typer.node_ty(pat.id);
415 // FIXME (Issue #18207): This code detects whether we are
416 // looking at a `ref x`, and if so, figures out what the type
417 // *being borrowed* is. But ideally we would put in a more
418 // fundamental fix to this conflated use of the node id.
419 let ret_ty = match pat.node {
420 ast::PatIdent(ast::BindByRef(_), _, _) => {
421 // a bind-by-ref means that the base_ty will be the type of the ident itself,
422 // but what we want here is the type of the underlying value being borrowed.
423 // So peel off one-level, turning the &T into T.
425 ty::deref(t, false).unwrap_or_else(|| {
426 panic!("encountered BindByRef with non &-type");
432 debug!("pat_ty(pat={}) base_ty={} ret_ty={}",
433 pat.repr(tcx), base_ty.repr(tcx), ret_ty.repr(tcx));
437 pub fn cat_expr(&self, expr: &ast::Expr) -> McResult<cmt<'tcx>> {
438 match self.typer.adjustments().borrow().get(&expr.id) {
441 self.cat_expr_unadjusted(expr)
444 Some(adjustment) => {
446 ty::AdjustAddEnv(..) => {
447 debug!("cat_expr(AdjustAddEnv): {}",
448 expr.repr(self.tcx()));
449 // Convert a bare fn to a closure by adding NULL env.
450 // Result is an rvalue.
451 let expr_ty = if_ok!(self.expr_ty_adjusted(expr));
452 Ok(self.cat_rvalue_node(expr.id(), expr.span(), expr_ty))
457 autoref: Some(_), ..}) => {
458 debug!("cat_expr(AdjustDerefRef): {}",
459 expr.repr(self.tcx()));
460 // Equivalent to &*expr or something similar.
461 // Result is an rvalue.
462 let expr_ty = if_ok!(self.expr_ty_adjusted(expr));
463 Ok(self.cat_rvalue_node(expr.id(), expr.span(), expr_ty))
468 autoref: None, autoderefs}) => {
469 // Equivalent to *expr or something similar.
470 self.cat_expr_autoderefd(expr, autoderefs)
477 pub fn cat_expr_autoderefd(&self,
480 -> McResult<cmt<'tcx>> {
481 let mut cmt = if_ok!(self.cat_expr_unadjusted(expr));
482 debug!("cat_expr_autoderefd: autoderefs={}, cmt={}",
484 cmt.repr(self.tcx()));
485 for deref in range(1u, autoderefs + 1) {
486 cmt = self.cat_deref(expr, cmt, deref, false);
491 pub fn cat_expr_unadjusted(&self, expr: &ast::Expr) -> McResult<cmt<'tcx>> {
492 debug!("cat_expr: id={} expr={}", expr.id, expr.repr(self.tcx()));
494 let expr_ty = if_ok!(self.expr_ty(expr));
496 ast::ExprUnary(ast::UnDeref, ref e_base) => {
497 let base_cmt = if_ok!(self.cat_expr(&**e_base));
498 Ok(self.cat_deref(expr, base_cmt, 0, false))
501 ast::ExprField(ref base, f_name) => {
502 let base_cmt = if_ok!(self.cat_expr(&**base));
503 debug!("cat_expr(cat_field): id={} expr={} base={}",
505 expr.repr(self.tcx()),
506 base_cmt.repr(self.tcx()));
507 Ok(self.cat_field(expr, base_cmt, f_name.node.name, expr_ty))
510 ast::ExprTupField(ref base, idx) => {
511 let base_cmt = if_ok!(self.cat_expr(&**base));
512 Ok(self.cat_tup_field(expr, base_cmt, idx.node, expr_ty))
515 ast::ExprIndex(ref base, _) => {
516 let method_call = typeck::MethodCall::expr(expr.id());
517 match self.typer.node_method_ty(method_call) {
519 // If this is an index implemented by a method call, then it will
520 // include an implicit deref of the result.
521 let ret_ty = ty::ty_fn_ret(method_ty).unwrap();
522 Ok(self.cat_deref(expr,
523 self.cat_rvalue_node(expr.id(),
528 let base_cmt = if_ok!(self.cat_expr(&**base));
529 Ok(self.cat_index(expr, base_cmt))
534 ast::ExprPath(_) => {
535 let def = (*self.tcx().def_map.borrow())[expr.id];
536 self.cat_def(expr.id, expr.span, expr_ty, def)
539 ast::ExprParen(ref e) => {
543 ast::ExprAddrOf(..) | ast::ExprCall(..) |
544 ast::ExprAssign(..) | ast::ExprAssignOp(..) |
545 ast::ExprClosure(..) | ast::ExprProc(..) |
547 ast::ExprUnary(..) | ast::ExprSlice(..) |
548 ast::ExprMethodCall(..) | ast::ExprCast(..) |
549 ast::ExprVec(..) | ast::ExprTup(..) | ast::ExprIf(..) |
550 ast::ExprBinary(..) | ast::ExprWhile(..) |
551 ast::ExprBlock(..) | ast::ExprLoop(..) | ast::ExprMatch(..) |
552 ast::ExprLit(..) | ast::ExprBreak(..) | ast::ExprMac(..) |
553 ast::ExprAgain(..) | ast::ExprStruct(..) | ast::ExprRepeat(..) |
554 ast::ExprInlineAsm(..) | ast::ExprBox(..) |
555 ast::ExprForLoop(..) => {
556 Ok(self.cat_rvalue_node(expr.id(), expr.span(), expr_ty))
559 ast::ExprIfLet(..) => {
560 self.tcx().sess.span_bug(expr.span, "non-desugared ExprIfLet");
562 ast::ExprWhileLet(..) => {
563 self.tcx().sess.span_bug(expr.span, "non-desugared ExprWhileLet");
568 pub fn cat_def(&self,
573 -> McResult<cmt<'tcx>> {
574 debug!("cat_def: id={} expr={} def={}",
575 id, expr_ty.repr(self.tcx()), def);
578 def::DefStruct(..) | def::DefVariant(..) | def::DefFn(..) |
579 def::DefStaticMethod(..) | def::DefConst(..) => {
580 Ok(self.cat_rvalue_node(id, span, expr_ty))
582 def::DefMod(_) | def::DefForeignMod(_) | def::DefUse(_) |
583 def::DefTrait(_) | def::DefTy(..) | def::DefPrimTy(_) |
584 def::DefTyParam(..) | def::DefTyParamBinder(..) | def::DefRegion(_) |
585 def::DefLabel(_) | def::DefSelfTy(..) | def::DefMethod(..) |
586 def::DefAssociatedTy(..) => {
597 def::DefStatic(_, mutbl) => {
602 mutbl: if mutbl { McDeclared } else { McImmutable},
608 def::DefUpvar(var_id, fn_node_id, _) => {
609 let ty = if_ok!(self.node_ty(fn_node_id));
611 ty::ty_closure(ref closure_ty) => {
612 // Translate old closure type info into unboxed
613 // closure kind/capture mode
614 let (mode, kind) = match (closure_ty.store, closure_ty.onceness) {
616 (ty::RegionTraitStore(..), ast::Many) => {
617 (ast::CaptureByRef, ty::FnMutUnboxedClosureKind)
619 // proc or once closure
621 (ast::CaptureByValue, ty::FnOnceUnboxedClosureKind)
623 // There should be no such old closure type
624 (ty::UniqTraitStore, ast::Many) => {
625 self.tcx().sess.span_bug(span, "Impossible closure type");
628 self.cat_upvar(id, span, var_id, fn_node_id, kind, mode, false)
630 ty::ty_unboxed_closure(closure_id, _, _) => {
631 let unboxed_closures = self.typer.unboxed_closures().borrow();
632 let kind = (*unboxed_closures)[closure_id].kind;
633 let mode = self.typer.capture_mode(fn_node_id);
634 self.cat_upvar(id, span, var_id, fn_node_id, kind, mode, true)
637 self.tcx().sess.span_bug(
639 format!("Upvar of non-closure {} - {}",
641 ty.repr(self.tcx())).as_slice());
646 def::DefLocal(vid) => {
651 mutbl: MutabilityCategory::from_local(self.tcx(), vid),
659 // Categorize an upvar, complete with invisible derefs of closure
660 // environment and upvar reference as appropriate.
665 fn_node_id: ast::NodeId,
666 kind: ty::UnboxedClosureKind,
667 mode: ast::CaptureClause,
669 -> McResult<cmt<'tcx>> {
670 // An upvar can have up to 3 components. The base is a
671 // `cat_upvar`. Next, we add a deref through the implicit
672 // environment pointer with an anonymous free region 'env and
673 // appropriate borrow kind for closure kinds that take self by
674 // reference. Finally, if the upvar was captured
675 // by-reference, we add a deref through that reference. The
676 // region of this reference is an inference variable 'up that
677 // was previously generated and recorded in the upvar borrow
678 // map. The borrow kind bk is inferred by based on how the
681 // This results in the following table for concrete closure
685 // ---------------+----------------------+-------------------------------
686 // Fn | copied -> &'env | upvar -> &'env -> &'up bk
687 // FnMut | copied -> &'env mut | upvar -> &'env mut -> &'up bk
688 // FnOnce | copied | upvar -> &'up bk
689 // old stack | N/A | upvar -> &'env mut -> &'up bk
690 // old proc/once | copied | N/A
691 let var_ty = if_ok!(self.node_ty(var_id));
693 let upvar_id = ty::UpvarId { var_id: var_id,
694 closure_expr_id: fn_node_id };
696 // Mutability of original variable itself
697 let var_mutbl = MutabilityCategory::from_local(self.tcx(), var_id);
699 // Construct information about env pointer dereference, if any
700 let mutbl = match kind {
701 ty::FnOnceUnboxedClosureKind => None, // None, env is by-value
702 ty::FnMutUnboxedClosureKind => match mode { // Depends on capture type
703 ast::CaptureByValue => Some(var_mutbl), // Mutable if the original var is
704 ast::CaptureByRef => Some(McDeclared) // Mutable regardless
706 ty::FnUnboxedClosureKind => Some(McImmutable) // Never mutable
708 let env_info = mutbl.map(|env_mutbl| {
709 // Look up the node ID of the closure body so we can construct
710 // a free region within it
712 let fn_expr = match self.tcx().map.find(fn_node_id) {
713 Some(ast_map::NodeExpr(e)) => e,
718 ast::ExprProc(_, ref body) |
719 ast::ExprClosure(_, _, _, ref body) => body.id,
724 // Region of environment pointer
725 let env_region = ty::ReFree(ty::FreeRegion {
726 scope: region::CodeExtent::from_node_id(fn_body_id),
727 bound_region: ty::BrEnv
730 let env_ptr = BorrowedPtr(if env_mutbl.is_mutable() {
739 // First, switch by capture mode
741 ast::CaptureByValue => {
742 let mut base = cmt_ {
745 cat: cat_upvar(Upvar {
748 is_unboxed: is_unboxed
756 Some((env_mutbl, env_ptr)) => {
757 // We need to add the env deref. This means
758 // that the above is actually immutable and
759 // has a ref type. However, nothing should
760 // actually look at the type, so we can get
761 // away with stuffing a `ty_err` in there
762 // instead of bothering to construct a proper
764 base.mutbl = McImmutable;
765 base.ty = ty::mk_err();
769 cat: cat_deref(Rc::new(base), 0, env_ptr),
772 note: NoteClosureEnv(upvar_id)
775 None => Rc::new(base)
778 ast::CaptureByRef => {
779 // The type here is actually a ref (or ref of a ref),
780 // but we can again get away with not constructing one
781 // properly since it will never be used.
782 let mut base = cmt_ {
785 cat: cat_upvar(Upvar {
788 is_unboxed: is_unboxed
796 Some((env_mutbl, env_ptr)) => {
800 cat: cat_deref(Rc::new(base), 0, env_ptr),
803 note: NoteClosureEnv(upvar_id)
809 // Look up upvar borrow so we can get its region
810 let upvar_borrow = self.typer.upvar_borrow(upvar_id);
811 let ptr = BorrowedPtr(upvar_borrow.kind, upvar_borrow.region);
816 cat: cat_deref(Rc::new(base), 0, ptr),
817 mutbl: MutabilityCategory::from_borrow_kind(upvar_borrow.kind),
819 note: NoteUpvarRef(upvar_id)
825 pub fn cat_rvalue_node(&self,
830 match self.typer.temporary_scope(id) {
833 ty::ty_vec(_, Some(0)) => self.cat_rvalue(id, span, ty::ReStatic, expr_ty),
834 _ => self.cat_rvalue(id, span, ty::ReScope(scope), expr_ty)
838 self.cat_rvalue(id, span, ty::ReStatic, expr_ty)
843 pub fn cat_rvalue(&self,
846 temp_scope: ty::Region,
847 expr_ty: Ty<'tcx>) -> cmt<'tcx> {
851 cat:cat_rvalue(temp_scope),
858 pub fn cat_field<N:ast_node>(&self,
867 mutbl: base_cmt.mutbl.inherit(),
868 cat: cat_interior(base_cmt, InteriorField(NamedField(f_name))),
874 pub fn cat_tup_field<N:ast_node>(&self,
883 mutbl: base_cmt.mutbl.inherit(),
884 cat: cat_interior(base_cmt, InteriorField(PositionalField(f_idx))),
890 fn cat_deref<N:ast_node>(&self,
896 let adjustment = match self.typer.adjustments().borrow().get(&node.id()) {
897 Some(adj) if ty::adjust_is_object(adj) => typeck::AutoObject,
898 _ if deref_cnt != 0 => typeck::AutoDeref(deref_cnt),
899 _ => typeck::NoAdjustment
902 let method_call = typeck::MethodCall {
904 adjustment: adjustment
906 let method_ty = self.typer.node_method_ty(method_call);
908 debug!("cat_deref: method_call={} method_ty={}",
909 method_call, method_ty.map(|ty| ty.repr(self.tcx())));
911 let base_cmt = match method_ty {
913 let ref_ty = ty::ty_fn_ret(method_ty).unwrap();
914 self.cat_rvalue_node(node.id(), node.span(), ref_ty)
918 match ty::deref(base_cmt.ty, true) {
919 Some(mt) => self.cat_deref_common(node, base_cmt, deref_cnt, mt.ty, implicit),
921 self.tcx().sess.span_bug(
923 format!("Explicit deref of non-derefable type: {}",
924 base_cmt.ty.repr(self.tcx())).as_slice());
929 fn cat_deref_common<N:ast_node>(&self,
936 let (m, cat) = match deref_kind(self.tcx(), base_cmt.ty) {
938 let ptr = if implicit {
940 BorrowedPtr(bk, r) => Implicit(bk, r),
941 _ => self.tcx().sess.span_bug(node.span(),
942 "Implicit deref of non-borrowed pointer")
947 // for unique ptrs, we inherit mutability from the
949 (MutabilityCategory::from_pointer_kind(base_cmt.mutbl, ptr),
950 cat_deref(base_cmt, deref_cnt, ptr))
952 deref_interior(interior) => {
953 (base_cmt.mutbl.inherit(), cat_interior(base_cmt, interior))
966 pub fn cat_index<N:ast_node>(&self,
968 mut base_cmt: cmt<'tcx>)
970 //! Creates a cmt for an indexing operation (`[]`).
972 //! One subtle aspect of indexing that may not be
973 //! immediately obvious: for anything other than a fixed-length
974 //! vector, an operation like `x[y]` actually consists of two
975 //! disjoint (from the point of view of borrowck) operations.
976 //! The first is a deref of `x` to create a pointer `p` that points
977 //! at the first element in the array. The second operation is
978 //! an index which adds `y*sizeof(T)` to `p` to obtain the
979 //! pointer to `x[y]`. `cat_index` will produce a resulting
980 //! cmt containing both this deref and the indexing,
981 //! presuming that `base_cmt` is not of fixed-length type.
984 //! - `elt`: the AST node being indexed
985 //! - `base_cmt`: the cmt of `elt`
987 let method_call = typeck::MethodCall::expr(elt.id());
988 let method_ty = self.typer.node_method_ty(method_call);
990 let element_ty = match method_ty {
992 let ref_ty = ty::ty_fn_ret(method_ty).unwrap();
993 base_cmt = self.cat_rvalue_node(elt.id(), elt.span(), ref_ty);
994 ty::ty_fn_args(method_ty)[0]
997 match ty::array_element_ty(base_cmt.ty) {
1000 self.tcx().sess.span_bug(
1002 format!("Explicit index of non-index type `{}`",
1003 base_cmt.ty.repr(self.tcx())).as_slice());
1009 let m = base_cmt.mutbl.inherit();
1010 return interior(elt, base_cmt.clone(), base_cmt.ty, m, element_ty);
1012 fn interior<'tcx, N: ast_node>(elt: &N,
1015 mutbl: MutabilityCategory,
1016 element_ty: Ty<'tcx>) -> cmt<'tcx>
1021 cat:cat_interior(of_cmt, InteriorElement(element_kind(vec_ty))),
1029 // Takes either a vec or a reference to a vec and returns the cmt for the
1031 fn deref_vec<N:ast_node>(&self,
1033 base_cmt: cmt<'tcx>)
1035 match deref_kind(self.tcx(), base_cmt.ty) {
1037 // for unique ptrs, we inherit mutability from the
1038 // owning reference.
1039 let m = MutabilityCategory::from_pointer_kind(base_cmt.mutbl, ptr);
1041 // the deref is explicit in the resulting cmt
1045 cat:cat_deref(base_cmt.clone(), 0, ptr),
1047 ty: match ty::deref(base_cmt.ty, false) {
1049 None => self.tcx().sess.bug("Found non-derefable type")
1055 deref_interior(_) => {
1061 pub fn cat_slice_pattern(&self,
1063 slice_pat: &ast::Pat)
1064 -> McResult<(cmt<'tcx>, ast::Mutability, ty::Region)> {
1066 * Given a pattern P like: `[_, ..Q, _]`, where `vec_cmt` is
1067 * the cmt for `P`, `slice_pat` is the pattern `Q`, returns:
1069 * - the mutability and region of the slice `Q`
1071 * These last two bits of info happen to be things that
1075 let slice_ty = if_ok!(self.node_ty(slice_pat.id));
1076 let (slice_mutbl, slice_r) = vec_slice_info(self.tcx(),
1079 let cmt_slice = self.cat_index(slice_pat, self.deref_vec(slice_pat, vec_cmt));
1080 return Ok((cmt_slice, slice_mutbl, slice_r));
1082 fn vec_slice_info(tcx: &ty::ctxt,
1085 -> (ast::Mutability, ty::Region) {
1087 * In a pattern like [a, b, ..c], normally `c` has slice type,
1088 * but if you have [a, b, ..ref c], then the type of `ref c`
1089 * will be `&&[]`, so to extract the slice details we have
1090 * to recurse through rptrs.
1093 match slice_ty.sty {
1094 ty::ty_rptr(r, ref mt) => match mt.ty.sty {
1095 ty::ty_vec(_, None) => (mt.mutbl, r),
1096 _ => vec_slice_info(tcx, pat, mt.ty),
1100 tcx.sess.span_bug(pat.span,
1101 "type of slice pattern is not a slice");
1107 pub fn cat_imm_interior<N:ast_node>(&self,
1109 base_cmt: cmt<'tcx>,
1110 interior_ty: Ty<'tcx>,
1111 interior: InteriorKind)
1116 mutbl: base_cmt.mutbl.inherit(),
1117 cat: cat_interior(base_cmt, interior),
1123 pub fn cat_downcast<N:ast_node>(&self,
1125 base_cmt: cmt<'tcx>,
1126 downcast_ty: Ty<'tcx>,
1127 variant_did: ast::DefId)
1132 mutbl: base_cmt.mutbl.inherit(),
1133 cat: cat_downcast(base_cmt, variant_did),
1139 pub fn cat_pattern(&self,
1142 op: |&MemCategorizationContext<'t,TYPER>,
1146 // Here, `cmt` is the categorization for the value being
1147 // matched and pat is the pattern it is being matched against.
1149 // In general, the way that this works is that we walk down
1150 // the pattern, constructing a cmt that represents the path
1151 // that will be taken to reach the value being matched.
1153 // When we encounter named bindings, we take the cmt that has
1154 // been built up and pass it off to guarantee_valid() so that
1155 // we can be sure that the binding will remain valid for the
1156 // duration of the arm.
1158 // (*2) There is subtlety concerning the correspondence between
1159 // pattern ids and types as compared to *expression* ids and
1160 // types. This is explained briefly. on the definition of the
1161 // type `cmt`, so go off and read what it says there, then
1162 // come back and I'll dive into a bit more detail here. :) OK,
1165 // In general, the id of the cmt should be the node that
1166 // "produces" the value---patterns aren't executable code
1167 // exactly, but I consider them to "execute" when they match a
1168 // value, and I consider them to produce the value that was
1169 // matched. So if you have something like:
1176 // In this case, the cmt and the relevant ids would be:
1178 // CMT Id Type of Id Type of cmt
1181 // ^~~~~~~^ `x` from discr @@int @@int
1182 // ^~~~~~~~~~^ `@@y` pattern node @@int @int
1183 // ^~~~~~~~~~~~~^ `@y` pattern node @int int
1185 // You can see that the types of the id and the cmt are in
1186 // sync in the first line, because that id is actually the id
1187 // of an expression. But once we get to pattern ids, the types
1188 // step out of sync again. So you'll see below that we always
1189 // get the type of the *subpattern* and use that.
1191 debug!("cat_pattern: id={} pat={} cmt={}",
1192 pat.id, pprust::pat_to_string(pat),
1193 cmt.repr(self.tcx()));
1195 op(self, cmt.clone(), pat);
1197 let def_map = self.tcx().def_map.borrow();
1198 let opt_def = def_map.get(&pat.id);
1200 // Note: This goes up here (rather than within the PatEnum arm
1201 // alone) because struct patterns can refer to struct types or
1202 // to struct variants within enums.
1203 let cmt = match opt_def {
1204 Some(&def::DefVariant(enum_did, variant_did, _))
1205 // univariant enums do not need downcasts
1206 if !ty::enum_is_univariant(self.tcx(), enum_did) => {
1207 self.cat_downcast(pat, cmt.clone(), cmt.ty, variant_did)
1213 ast::PatWild(_) => {
1217 ast::PatEnum(_, None) => {
1220 ast::PatEnum(_, Some(ref subpats)) => {
1222 Some(&def::DefVariant(..)) => {
1224 for (i, subpat) in subpats.iter().enumerate() {
1225 let subpat_ty = if_ok!(self.pat_ty(&**subpat)); // see (*2)
1228 self.cat_imm_interior(
1229 pat, cmt.clone(), subpat_ty,
1230 InteriorField(PositionalField(i)));
1232 if_ok!(self.cat_pattern(subcmt, &**subpat, |x,y,z| op(x,y,z)));
1235 Some(&def::DefStruct(..)) => {
1236 for (i, subpat) in subpats.iter().enumerate() {
1237 let subpat_ty = if_ok!(self.pat_ty(&**subpat)); // see (*2)
1239 self.cat_imm_interior(
1240 pat, cmt.clone(), subpat_ty,
1241 InteriorField(PositionalField(i)));
1242 if_ok!(self.cat_pattern(cmt_field, &**subpat,
1243 |x,y,z| op(x,y,z)));
1246 Some(&def::DefConst(..)) => {
1247 for subpat in subpats.iter() {
1248 if_ok!(self.cat_pattern(cmt.clone(), &**subpat, |x,y,z| op(x,y,z)));
1252 self.tcx().sess.span_bug(
1254 "enum pattern didn't resolve to enum or struct");
1259 ast::PatIdent(_, _, Some(ref subpat)) => {
1260 if_ok!(self.cat_pattern(cmt, &**subpat, op));
1263 ast::PatIdent(_, _, None) => {
1264 // nullary variant or identifier: ignore
1267 ast::PatStruct(_, ref field_pats, _) => {
1268 // {f1: p1, ..., fN: pN}
1269 for fp in field_pats.iter() {
1270 let field_ty = if_ok!(self.pat_ty(&*fp.node.pat)); // see (*2)
1271 let cmt_field = self.cat_field(pat, cmt.clone(), fp.node.ident.name, field_ty);
1272 if_ok!(self.cat_pattern(cmt_field, &*fp.node.pat, |x,y,z| op(x,y,z)));
1276 ast::PatTup(ref subpats) => {
1278 for (i, subpat) in subpats.iter().enumerate() {
1279 let subpat_ty = if_ok!(self.pat_ty(&**subpat)); // see (*2)
1281 self.cat_imm_interior(
1282 pat, cmt.clone(), subpat_ty,
1283 InteriorField(PositionalField(i)));
1284 if_ok!(self.cat_pattern(subcmt, &**subpat, |x,y,z| op(x,y,z)));
1288 ast::PatBox(ref subpat) | ast::PatRegion(ref subpat) => {
1290 let subcmt = self.cat_deref(pat, cmt, 0, false);
1291 if_ok!(self.cat_pattern(subcmt, &**subpat, op));
1294 ast::PatVec(ref before, ref slice, ref after) => {
1295 let elt_cmt = self.cat_index(pat, self.deref_vec(pat, cmt));
1296 for before_pat in before.iter() {
1297 if_ok!(self.cat_pattern(elt_cmt.clone(), &**before_pat,
1298 |x,y,z| op(x,y,z)));
1300 for slice_pat in slice.iter() {
1301 let slice_ty = if_ok!(self.pat_ty(&**slice_pat));
1302 let slice_cmt = self.cat_rvalue_node(pat.id(), pat.span(), slice_ty);
1303 if_ok!(self.cat_pattern(slice_cmt, &**slice_pat, |x,y,z| op(x,y,z)));
1305 for after_pat in after.iter() {
1306 if_ok!(self.cat_pattern(elt_cmt.clone(), &**after_pat, |x,y,z| op(x,y,z)));
1310 ast::PatLit(_) | ast::PatRange(_, _) => {
1315 self.tcx().sess.span_bug(pat.span, "unexpanded macro");
1322 pub fn cmt_to_string(&self, cmt: &cmt_<'tcx>) -> String {
1323 fn upvar_to_string(upvar: &Upvar, is_copy: bool) -> String {
1324 if upvar.is_unboxed {
1325 let kind = match upvar.kind {
1326 ty::FnUnboxedClosureKind => "Fn",
1327 ty::FnMutUnboxedClosureKind => "FnMut",
1328 ty::FnOnceUnboxedClosureKind => "FnOnce"
1330 format!("captured outer variable in an `{}` closure", kind)
1332 (match (upvar.kind, is_copy) {
1333 (ty::FnOnceUnboxedClosureKind, true) => "captured outer variable in a proc",
1334 _ => "captured outer variable"
1340 cat_static_item => {
1341 "static item".to_string()
1344 "non-lvalue".to_string()
1347 match self.tcx().map.find(vid) {
1348 Some(ast_map::NodeArg(_)) => {
1349 "argument".to_string()
1351 _ => "local variable".to_string()
1354 cat_deref(_, _, pk) => {
1355 let upvar = cmt.upvar();
1356 match upvar.as_ref().map(|i| &i.cat) {
1357 Some(&cat_upvar(ref var)) => {
1358 upvar_to_string(var, false)
1360 Some(_) => unreachable!(),
1364 "dereference (dereference is implicit, due to indexing)".to_string()
1366 OwnedPtr => format!("dereference of `{}`", ptr_sigil(pk)),
1367 _ => format!("dereference of `{}`-pointer", ptr_sigil(pk))
1372 cat_interior(_, InteriorField(NamedField(_))) => {
1375 cat_interior(_, InteriorField(PositionalField(_))) => {
1376 "anonymous field".to_string()
1378 cat_interior(_, InteriorElement(VecElement)) => {
1379 "vec content".to_string()
1381 cat_interior(_, InteriorElement(OtherElement)) => {
1382 "indexed content".to_string()
1384 cat_upvar(ref var) => {
1385 upvar_to_string(var, true)
1387 cat_downcast(ref cmt, _) => {
1388 self.cmt_to_string(&**cmt)
1394 pub enum InteriorSafety {
1399 pub enum AliasableReason {
1401 AliasableClosure(ast::NodeId), // Aliasable due to capture Fn closure env
1403 AliasableStatic(InteriorSafety),
1404 AliasableStaticMut(InteriorSafety),
1407 impl<'tcx> cmt_<'tcx> {
1408 pub fn guarantor(&self) -> cmt<'tcx> {
1409 //! Returns `self` after stripping away any owned pointer derefs or
1410 //! interior content. The return value is basically the `cmt` which
1411 //! determines how long the value in `self` remains live.
1417 cat_deref(_, _, UnsafePtr(..)) |
1418 cat_deref(_, _, BorrowedPtr(..)) |
1419 cat_deref(_, _, Implicit(..)) |
1421 Rc::new((*self).clone())
1423 cat_downcast(ref b, _) |
1424 cat_interior(ref b, _) |
1425 cat_deref(ref b, _, OwnedPtr) => {
1431 pub fn freely_aliasable(&self, ctxt: &ty::ctxt<'tcx>)
1432 -> Option<AliasableReason> {
1434 * Returns `Some(_)` if this lvalue represents a freely aliasable
1438 // Maybe non-obvious: copied upvars can only be considered
1439 // non-aliasable in once closures, since any other kind can be
1440 // aliased and eventually recused.
1443 cat_deref(ref b, _, BorrowedPtr(ty::MutBorrow, _)) |
1444 cat_deref(ref b, _, Implicit(ty::MutBorrow, _)) |
1445 cat_deref(ref b, _, BorrowedPtr(ty::UniqueImmBorrow, _)) |
1446 cat_deref(ref b, _, Implicit(ty::UniqueImmBorrow, _)) |
1447 cat_downcast(ref b, _) |
1448 cat_deref(ref b, _, OwnedPtr) |
1449 cat_interior(ref b, _) => {
1450 // Aliasability depends on base cmt
1451 b.freely_aliasable(ctxt)
1457 cat_deref(_, _, UnsafePtr(..)) => { // yes, it's aliasable, but...
1461 cat_static_item(..) => {
1462 let int_safe = if ty::type_interior_is_unsafe(ctxt, self.ty) {
1468 if self.mutbl.is_mutable() {
1469 Some(AliasableStaticMut(int_safe))
1471 Some(AliasableStatic(int_safe))
1475 cat_deref(ref base, _, BorrowedPtr(ty::ImmBorrow, _)) |
1476 cat_deref(ref base, _, Implicit(ty::ImmBorrow, _)) => {
1478 cat_upvar(Upvar{ id, .. }) => Some(AliasableClosure(id.closure_expr_id)),
1479 _ => Some(AliasableBorrowed)
1485 // Digs down through one or two layers of deref and grabs the cmt
1486 // for the upvar if a note indicates there is one.
1487 pub fn upvar(&self) -> Option<cmt<'tcx>> {
1489 NoteClosureEnv(..) | NoteUpvarRef(..) => {
1490 Some(match self.cat {
1491 cat_deref(ref inner, _, _) => {
1493 cat_deref(ref inner, _, _) => inner.clone(),
1494 cat_upvar(..) => inner.clone(),
1506 impl<'tcx> Repr<'tcx> for cmt_<'tcx> {
1507 fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1508 format!("{{{} id:{} m:{} ty:{}}}",
1516 impl<'tcx> Repr<'tcx> for categorization<'tcx> {
1517 fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1523 format!("{}", *self)
1525 cat_deref(ref cmt, derefs, ptr) => {
1526 format!("{}-{}{}->", cmt.cat.repr(tcx), ptr_sigil(ptr), derefs)
1528 cat_interior(ref cmt, interior) => {
1529 format!("{}.{}", cmt.cat.repr(tcx), interior.repr(tcx))
1531 cat_downcast(ref cmt, _) => {
1532 format!("{}->(enum)", cmt.cat.repr(tcx))
1538 pub fn ptr_sigil(ptr: PointerKind) -> &'static str {
1541 BorrowedPtr(ty::ImmBorrow, _) |
1542 Implicit(ty::ImmBorrow, _) => "&",
1543 BorrowedPtr(ty::MutBorrow, _) |
1544 Implicit(ty::MutBorrow, _) => "&mut",
1545 BorrowedPtr(ty::UniqueImmBorrow, _) |
1546 Implicit(ty::UniqueImmBorrow, _) => "&unique",
1551 impl<'tcx> Repr<'tcx> for InteriorKind {
1552 fn repr(&self, _tcx: &ty::ctxt) -> String {
1554 InteriorField(NamedField(fld)) => {
1555 token::get_name(fld).get().to_string()
1557 InteriorField(PositionalField(i)) => format!("#{}", i),
1558 InteriorElement(_) => "[]".to_string(),
1563 fn element_kind(t: Ty) -> ElementKind {
1565 ty::ty_rptr(_, ty::mt{ty, ..}) |
1566 ty::ty_uniq(ty) => match ty.sty {
1567 ty::ty_vec(_, None) => VecElement,
1570 ty::ty_vec(..) => VecElement,