From 802ea5d57e8cd4cd12e1a0e25c446b90be4a6a06 Mon Sep 17 00:00:00 2001 From: Niko Matsakis Date: Wed, 8 Aug 2012 08:15:32 -0700 Subject: refactor categorization out of borrowck into its own module. first step towards #3148 and #3024. --- src/rustc/middle/borrowck.rs | 247 ++---- src/rustc/middle/borrowck/categorization.rs | 505 ------------ src/rustc/middle/borrowck/check_loans.rs | 1 - src/rustc/middle/borrowck/gather_loans.rs | 200 ++--- src/rustc/middle/mem_categorization.rs | 868 +++++++++++++++++++++ src/rustc/middle/typeck/check/regionck.rs | 5 + src/rustc/rustc.rc | 2 +- .../region-return-interior-of-option-in-self.rs | 20 + 8 files changed, 986 insertions(+), 862 deletions(-) delete mode 100644 src/rustc/middle/borrowck/categorization.rs create mode 100644 src/rustc/middle/mem_categorization.rs create mode 100644 src/test/run-pass/region-return-interior-of-option-in-self.rs (limited to 'src') diff --git a/src/rustc/middle/borrowck.rs b/src/rustc/middle/borrowck.rs index 2fbfb4fe9f6..b00a8c31ef0 100644 --- a/src/rustc/middle/borrowck.rs +++ b/src/rustc/middle/borrowck.rs @@ -230,6 +230,7 @@ import util::common::indenter; import ty::to_str; import driver::session::session; import dvec::{dvec, extensions}; +import mem_categorization::*; export check_crate, root_map, mutbl_map; @@ -241,7 +242,6 @@ fn check_crate(tcx: ty::ctxt, let bccx = borrowck_ctxt_(@{tcx: tcx, method_map: method_map, last_use_map: last_use_map, - binding_map: int_hash(), root_map: root_map(), mutbl_map: int_hash(), mut loaned_paths_same: 0, @@ -282,7 +282,6 @@ fn check_crate(tcx: ty::ctxt, type borrowck_ctxt_ = {tcx: ty::ctxt, method_map: typeck::method_map, last_use_map: liveness::last_use_map, - binding_map: binding_map, root_map: root_map, mutbl_map: mutbl_map, @@ -313,10 +312,6 @@ type root_map_key = {id: ast::node_id, derefs: uint}; // this is used in trans for optimization purposes. type mutbl_map = std::map::hashmap; -// maps from each binding's id to the mutability of the location it -// points at. See gather_loan.rs for more detail (search for binding_map) -type binding_map = std::map::hashmap; - // Errors that can occur"] enum bckerr_code { err_mut_uniq, @@ -334,64 +329,6 @@ type bckerr = {cmt: cmt, code: bckerr_code}; // shorthand for something that fails with `bckerr` or succeeds with `T` type bckres = result; -enum categorization { - cat_rvalue, // result of eval'ing some misc expr - cat_special(special_kind), // - cat_local(ast::node_id), // local variable - cat_binding(ast::node_id), // pattern binding - cat_arg(ast::node_id), // formal argument - cat_stack_upvar(cmt), // upvar in stack closure - cat_deref(cmt, uint, ptr_kind), // deref of a ptr - cat_comp(cmt, comp_kind), // adjust to locate an internal component - cat_discr(cmt, ast::node_id), // match discriminant (see preserve()) -} - -// different kinds of pointers: -enum ptr_kind {uniq_ptr, gc_ptr, region_ptr(ty::region), unsafe_ptr} - -// I am coining the term "components" to mean "pieces of a data -// structure accessible without a dereference": -enum comp_kind { - comp_tuple, // elt in a tuple - comp_variant(ast::def_id), // internals to a variant of given enum - comp_field(ast::ident, // name of field - ast::mutability), // declared mutability of field - comp_index(ty::t, // type of vec/str/etc being deref'd - ast::mutability) // mutability of vec content -} - -// We pun on *T to mean both actual deref of a ptr as well -// as accessing of components: -enum deref_kind {deref_ptr(ptr_kind), deref_comp(comp_kind)} - -// different kinds of expressions we might evaluate -enum special_kind { - sk_method, - sk_static_item, - sk_self, - sk_heap_upvar -} - -// a complete categorization of a value indicating where it originated -// and how it is located, as well as the mutability of the memory in -// which the value is stored. -type cmt = @{id: ast::node_id, // id of expr/pat producing this value - span: span, // span of same expr/pat - cat: categorization, // categorization of expr - lp: option<@loan_path>, // loan path for expr, if any - mutbl: ast::mutability, // mutability of expr as lvalue - ty: ty::t}; // type of the expr - -// a loan path is like a category, but it exists only when the data is -// interior to the stack frame. loan paths are used as the key to a -// map indicating what is borrowed at any point in time. -enum loan_path { - lp_local(ast::node_id), - lp_arg(ast::node_id), - lp_deref(@loan_path, ptr_kind), - lp_comp(@loan_path, comp_kind) -} - /// a complete record of a loan that was granted type loan = {lp: @loan_path, cmt: cmt, mutbl: ast::mutability}; @@ -429,38 +366,42 @@ fn root_map() -> root_map { // ___________________________________________________________________________ // Misc -trait ast_node { - fn id() -> ast::node_id; - fn span() -> span; -} +impl borrowck_ctxt { + fn is_subregion_of(r_sub: ty::region, r_sup: ty::region) -> bool { + region::is_subregion_of(self.tcx.region_map, r_sub, r_sup) + } -impl of ast_node for @ast::expr { - fn id() -> ast::node_id { self.id } - fn span() -> span { self.span } -} + fn cat_expr(expr: @ast::expr) -> cmt { + cat_expr(self.tcx, self.method_map, expr) + } -impl of ast_node for @ast::pat { - fn id() -> ast::node_id { self.id } - fn span() -> span { self.span } -} + fn cat_borrow_of_expr(expr: @ast::expr) -> cmt { + cat_borrow_of_expr(self.tcx, self.method_map, expr) + } -trait get_type_for_node { - fn ty(node: N) -> ty::t; -} + fn cat_def(id: ast::node_id, + span: span, + ty: ty::t, + def: ast::def) -> cmt { + cat_def(self.tcx, self.method_map, id, span, ty, def) + } -impl methods of get_type_for_node for ty::ctxt { - fn ty(node: N) -> ty::t { - ty::node_id_to_type(self, node.id()) + fn cat_variant(arg: N, + enum_did: ast::def_id, + cmt: cmt) -> cmt { + cat_variant(self.tcx, self.method_map, arg, enum_did, cmt) } -} -impl borrowck_ctxt { - fn is_subregion_of(r_sub: ty::region, r_sup: ty::region) -> bool { - region::is_subregion_of(self.tcx.region_map, r_sub, r_sup) + fn cat_discr(cmt: cmt, alt_id: ast::node_id) -> cmt { + return @{cat:cat_discr(cmt, alt_id) with *cmt}; + } + + fn cat_pattern(cmt: cmt, pat: @ast::pat, op: fn(cmt, @ast::pat)) { + let mc = &mem_categorization_ctxt {tcx: self.tcx, + method_map: self.method_map}; + mc.cat_pattern(cmt, pat, op); } -} -impl error_methods for borrowck_ctxt { fn report_if_err(bres: bckres<()>) { match bres { ok(()) => (), @@ -494,118 +435,6 @@ impl error_methods for borrowck_ctxt { _ => () } } -} - -impl to_str_methods for borrowck_ctxt { - fn cat_to_repr(cat: categorization) -> ~str { - match cat { - cat_special(sk_method) => ~"method", - cat_special(sk_static_item) => ~"static_item", - cat_special(sk_self) => ~"self", - cat_special(sk_heap_upvar) => ~"heap-upvar", - cat_stack_upvar(_) => ~"stack-upvar", - cat_rvalue => ~"rvalue", - cat_local(node_id) => fmt!{"local(%d)", node_id}, - cat_binding(node_id) => fmt!{"binding(%d)", node_id}, - cat_arg(node_id) => fmt!{"arg(%d)", node_id}, - cat_deref(cmt, derefs, ptr) => { - fmt!{"%s->(%s, %u)", self.cat_to_repr(cmt.cat), - self.ptr_sigil(ptr), derefs} - } - cat_comp(cmt, comp) => { - fmt!{"%s.%s", self.cat_to_repr(cmt.cat), self.comp_to_repr(comp)} - } - cat_discr(cmt, _) => self.cat_to_repr(cmt.cat) - } - } - - fn mut_to_str(mutbl: ast::mutability) -> ~str { - match mutbl { - m_mutbl => ~"mutable", - m_const => ~"const", - m_imm => ~"immutable" - } - } - - fn ptr_sigil(ptr: ptr_kind) -> ~str { - match ptr { - uniq_ptr => ~"~", - gc_ptr => ~"@", - region_ptr(_) => ~"&", - unsafe_ptr => ~"*" - } - } - - fn comp_to_repr(comp: comp_kind) -> ~str { - match comp { - comp_field(fld, _) => *fld, - comp_index(*) => ~"[]", - comp_tuple => ~"()", - comp_variant(_) => ~"" - } - } - - fn lp_to_str(lp: @loan_path) -> ~str { - match *lp { - lp_local(node_id) => { - fmt!{"local(%d)", node_id} - } - lp_arg(node_id) => { - fmt!{"arg(%d)", node_id} - } - lp_deref(lp, ptr) => { - fmt!{"%s->(%s)", self.lp_to_str(lp), - self.ptr_sigil(ptr)} - } - lp_comp(lp, comp) => { - fmt!{"%s.%s", self.lp_to_str(lp), - self.comp_to_repr(comp)} - } - } - } - - fn cmt_to_repr(cmt: cmt) -> ~str { - fmt!{"{%s id:%d m:%s lp:%s ty:%s}", - self.cat_to_repr(cmt.cat), - cmt.id, - self.mut_to_str(cmt.mutbl), - cmt.lp.map_default(~"none", |p| self.lp_to_str(p) ), - ty_to_str(self.tcx, cmt.ty)} - } - - fn cmt_to_str(cmt: cmt) -> ~str { - let mut_str = self.mut_to_str(cmt.mutbl); - match cmt.cat { - cat_special(sk_method) => ~"method", - cat_special(sk_static_item) => ~"static item", - cat_special(sk_self) => ~"self reference", - cat_special(sk_heap_upvar) => { - ~"captured outer variable in a heap closure" - } - cat_rvalue => ~"non-lvalue", - cat_local(_) => mut_str + ~" local variable", - cat_binding(_) => ~"pattern binding", - cat_arg(_) => ~"argument", - cat_deref(_, _, pk) => fmt!{"dereference of %s %s pointer", - mut_str, self.ptr_sigil(pk)}, - cat_stack_upvar(_) => { - ~"captured outer " + mut_str + ~" variable in a stack closure" - } - cat_comp(_, comp_field(*)) => mut_str + ~" field", - cat_comp(_, comp_tuple) => ~"tuple content", - cat_comp(_, comp_variant(_)) => ~"enum content", - cat_comp(_, comp_index(t, _)) => { - match ty::get(t).struct { - ty::ty_evec(*) => mut_str + ~" vec content", - ty::ty_estr(*) => mut_str + ~" str content", - _ => mut_str + ~" indexed content" - } - } - cat_discr(cmt, _) => { - self.cmt_to_str(cmt) - } - } - } fn bckerr_code_to_str(code: bckerr_code) -> ~str { match code { @@ -640,8 +469,22 @@ impl to_str_methods for borrowck_ctxt { } } - fn region_to_str(r: ty::region) -> ~str { - region_to_str(self.tcx, r) + fn cmt_to_str(cmt: cmt) -> ~str { + let mc = &mem_categorization_ctxt {tcx: self.tcx, + method_map: self.method_map}; + mc.cmt_to_str(cmt) + } + + fn cmt_to_repr(cmt: cmt) -> ~str { + let mc = &mem_categorization_ctxt {tcx: self.tcx, + method_map: self.method_map}; + mc.cmt_to_repr(cmt) + } + + fn mut_to_str(mutbl: ast::mutability) -> ~str { + let mc = &mem_categorization_ctxt {tcx: self.tcx, + method_map: self.method_map}; + mc.mut_to_str(mutbl) } } diff --git a/src/rustc/middle/borrowck/categorization.rs b/src/rustc/middle/borrowck/categorization.rs deleted file mode 100644 index 41204f117a5..00000000000 --- a/src/rustc/middle/borrowck/categorization.rs +++ /dev/null @@ -1,505 +0,0 @@ -/*! - * # Categorization - * - * The job of the categorization module is to analyze an expression to - * determine what kind of memory is used in evaluating it (for example, - * where dereferences occur and what kind of pointer is dereferenced; - * whether the memory is mutable; etc) - * - * Categorization effectively transforms all of our expressions into - * expressions of the following forms (the actual enum has many more - * possibilities, naturally, but they are all variants of these base - * forms): - * - * E = rvalue // some computed rvalue - * | x // address of a local variable, arg, or upvar - * | *E // deref of a ptr - * | E.comp // access to an interior component - * - * Imagine a routine ToAddr(Expr) that evaluates an expression and returns an - * address where the result is to be found. If Expr is an lvalue, then this - * is the address of the lvalue. If Expr is an rvalue, this is the address of - * some temporary spot in memory where the result is stored. - * - * Now, cat_expr() classies the expression Expr and the address A=ToAddr(Expr) - * as follows: - * - * - cat: what kind of expression was this? This is a subset of the - * full expression forms which only includes those that we care about - * for the purpose of the analysis. - * - mutbl: mutability of the address A - * - ty: the type of data found at the address A - * - * The resulting categorization tree differs somewhat from the expressions - * themselves. For example, auto-derefs are explicit. Also, an index a[b] is - * decomposed into two operations: a derefence to reach the array data and - * then an index to jump forward to the relevant item. - */ - -export public_methods; -export opt_deref_kind; - -// Categorizes a derefable type. Note that we include vectors and strings as -// derefable (we model an index as the combination of a deref and then a -// pointer adjustment). -fn opt_deref_kind(t: ty::t) -> option { - match ty::get(t).struct { - ty::ty_uniq(*) | - ty::ty_evec(_, ty::vstore_uniq) | - ty::ty_estr(ty::vstore_uniq) => { - some(deref_ptr(uniq_ptr)) - } - - ty::ty_rptr(r, _) | - ty::ty_evec(_, ty::vstore_slice(r)) | - ty::ty_estr(ty::vstore_slice(r)) => { - some(deref_ptr(region_ptr(r))) - } - - ty::ty_box(*) | - ty::ty_evec(_, ty::vstore_box) | - ty::ty_estr(ty::vstore_box) => { - some(deref_ptr(gc_ptr)) - } - - ty::ty_ptr(*) => { - some(deref_ptr(unsafe_ptr)) - } - - ty::ty_enum(did, _) => { - some(deref_comp(comp_variant(did))) - } - - ty::ty_evec(mt, ty::vstore_fixed(_)) => { - some(deref_comp(comp_index(t, mt.mutbl))) - } - - ty::ty_estr(ty::vstore_fixed(_)) => { - some(deref_comp(comp_index(t, m_imm))) - } - - _ => none - } -} - -fn deref_kind(tcx: ty::ctxt, t: ty::t) -> deref_kind { - match opt_deref_kind(t) { - some(k) => k, - none => { - tcx.sess.bug( - fmt!{"deref_cat() invoked on non-derefable type %s", - ty_to_str(tcx, t)}); - } - } -} - -impl public_methods for borrowck_ctxt { - fn cat_borrow_of_expr(expr: @ast::expr) -> cmt { - // a borrowed expression must be either an @, ~, or a @vec, ~vec - let expr_ty = ty::expr_ty(self.tcx, expr); - match ty::get(expr_ty).struct { - ty::ty_evec(*) | ty::ty_estr(*) => { - self.cat_index(expr, expr) - } - - ty::ty_uniq(*) | ty::ty_box(*) | ty::ty_rptr(*) => { - let cmt = self.cat_expr(expr); - self.cat_deref(expr, cmt, 0u, true).get() - } - - /* - ty::ty_fn({proto, _}) { - self.cat_call(expr, expr, proto) - } - */ - - _ => { - self.tcx.sess.span_bug( - expr.span, - fmt!{"Borrowing of non-derefable type `%s`", - ty_to_str(self.tcx, expr_ty)}); - } - } - } - - fn cat_expr(expr: @ast::expr) -> cmt { - debug!{"cat_expr: id=%d expr=%s", - expr.id, pprust::expr_to_str(expr)}; - - let tcx = self.tcx; - let expr_ty = tcx.ty(expr); - match expr.node { - ast::expr_unary(ast::deref, e_base) => { - if self.method_map.contains_key(expr.id) { - return self.cat_rvalue(expr, expr_ty); - } - - let base_cmt = self.cat_expr(e_base); - match self.cat_deref(expr, base_cmt, 0u, true) { - some(cmt) => return cmt, - none => { - tcx.sess.span_bug( - e_base.span, - fmt!{"Explicit deref of non-derefable type `%s`", - ty_to_str(tcx, tcx.ty(e_base))}); - } - } - } - - ast::expr_field(base, f_name, _) => { - if self.method_map.contains_key(expr.id) { - return self.cat_method_ref(expr, expr_ty); - } - - let base_cmt = self.cat_autoderef(base); - self.cat_field(expr, base_cmt, f_name) - } - - ast::expr_index(base, _) => { - if self.method_map.contains_key(expr.id) { - return self.cat_rvalue(expr, expr_ty); - } - - self.cat_index(expr, base) - } - - ast::expr_path(_) => { - let def = self.tcx.def_map.get(expr.id); - self.cat_def(expr.id, expr.span, expr_ty, def) - } - - ast::expr_addr_of(*) | ast::expr_call(*) | - ast::expr_swap(*) | ast::expr_move(*) | ast::expr_assign(*) | - ast::expr_assign_op(*) | ast::expr_fn(*) | ast::expr_fn_block(*) | - ast::expr_assert(*) | ast::expr_ret(*) | - ast::expr_loop_body(*) | ast::expr_do_body(*) | ast::expr_unary(*) | - ast::expr_copy(*) | ast::expr_cast(*) | ast::expr_fail(*) | - ast::expr_vstore(*) | ast::expr_vec(*) | ast::expr_tup(*) | - ast::expr_if(*) | ast::expr_log(*) | - ast::expr_binary(*) | ast::expr_while(*) | - ast::expr_block(*) | ast::expr_loop(*) | ast::expr_match(*) | - ast::expr_lit(*) | ast::expr_break | ast::expr_mac(*) | - ast::expr_again | ast::expr_rec(*) | ast::expr_struct(*) | - ast::expr_unary_move(*) | ast::expr_repeat(*) => { - return self.cat_rvalue(expr, expr_ty); - } - } - } - - fn cat_def(id: ast::node_id, - span: span, - expr_ty: ty::t, - def: ast::def) -> cmt { - match def { - ast::def_fn(*) | ast::def_static_method(*) | ast::def_mod(_) | - ast::def_foreign_mod(_) | ast::def_const(_) | - ast::def_use(_) | ast::def_variant(*) | - ast::def_ty(_) | ast::def_prim_ty(_) | - ast::def_ty_param(*) | ast::def_class(*) | - ast::def_typaram_binder(*) | ast::def_region(_) => { - @{id:id, span:span, - cat:cat_special(sk_static_item), lp:none, - mutbl:m_imm, ty:expr_ty} - } - - ast::def_arg(vid, mode) => { - // Idea: make this could be rewritten to model by-ref - // stuff as `&const` and `&mut`? - - // m: mutability of the argument - // lp: loan path, must be none for aliasable things - let {m,lp} = match ty::resolved_mode(self.tcx, mode) { - ast::by_mutbl_ref => { - {m: m_mutbl, lp: none} - } - ast::by_move | ast::by_copy => { - {m: m_imm, lp: some(@lp_arg(vid))} - } - ast::by_ref => { - {m: m_imm, lp: none} - } - ast::by_val => { - // by-value is this hybrid mode where we have a - // pointer but we do not own it. This is not - // considered loanable because, for example, a by-ref - // and and by-val argument might both actually contain - // the same unique ptr. - {m: m_imm, lp: none} - } - }; - @{id:id, span:span, - cat:cat_arg(vid), lp:lp, - mutbl:m, ty:expr_ty} - } - - ast::def_self(_) => { - @{id:id, span:span, - cat:cat_special(sk_self), lp:none, - mutbl:m_imm, ty:expr_ty} - } - - ast::def_upvar(upvid, inner, fn_node_id) => { - let ty = ty::node_id_to_type(self.tcx, fn_node_id); - let proto = ty::ty_fn_proto(ty); - match proto { - ast::proto_block => { - let upcmt = self.cat_def(id, span, expr_ty, *inner); - @{id:id, span:span, - cat:cat_stack_upvar(upcmt), lp:upcmt.lp, - mutbl:upcmt.mutbl, ty:upcmt.ty} - } - ast::proto_bare | ast::proto_uniq | ast::proto_box => { - // FIXME #2152 allow mutation of moved upvars - @{id:id, span:span, - cat:cat_special(sk_heap_upvar), lp:none, - mutbl:m_imm, ty:expr_ty} - } - } - } - - ast::def_local(vid, mutbl) => { - let m = if mutbl {m_mutbl} else {m_imm}; - @{id:id, span:span, - cat:cat_local(vid), lp:some(@lp_local(vid)), - mutbl:m, ty:expr_ty} - } - - ast::def_binding(vid, ast::bind_by_value) | - ast::def_binding(vid, ast::bind_by_ref(_)) => { - // by-value/by-ref bindings are local variables - @{id:id, span:span, - cat:cat_local(vid), lp:some(@lp_local(vid)), - mutbl:m_imm, ty:expr_ty} - } - - ast::def_binding(pid, ast::bind_by_implicit_ref) => { - // implicit-by-ref bindings are "special" since they are - // implicit pointers. - - // lookup the mutability for this binding that we found in - // gather_loans when we categorized it - let mutbl = self.binding_map.get(pid); - - @{id:id, span:span, - cat:cat_binding(pid), lp:none, - mutbl:mutbl, ty:expr_ty} - } - } - } - - fn cat_variant(arg: N, - enum_did: ast::def_id, - cmt: cmt) -> cmt { - @{id: arg.id(), span: arg.span(), - cat: cat_comp(cmt, comp_variant(enum_did)), - lp: cmt.lp.map(|l| @lp_comp(l, comp_variant(enum_did)) ), - mutbl: cmt.mutbl, // imm iff in an immutable context - ty: self.tcx.ty(arg)} - } - - fn cat_rvalue(expr: @ast::expr, expr_ty: ty::t) -> cmt { - @{id:expr.id, span:expr.span, - cat:cat_rvalue, lp:none, - mutbl:m_imm, ty:expr_ty} - } - - fn cat_discr(cmt: cmt, alt_id: ast::node_id) -> cmt { - return @{cat:cat_discr(cmt, alt_id) with *cmt}; - } - - /// inherited mutability: used in cases where the mutability of a - /// component is inherited from the base it is a part of. For - /// example, a record field is mutable if it is declared mutable - /// or if the container is mutable. - fn inherited_mutability(base_m: ast::mutability, - comp_m: ast::mutability) -> ast::mutability { - match comp_m { - m_imm => {base_m} // imm: as mutable as the container - m_mutbl | m_const => {comp_m} - } - } - - fn cat_field(node: N, base_cmt: cmt, - f_name: ast::ident) -> cmt { - let f_mutbl = match field_mutbl(self.tcx, base_cmt.ty, f_name) { - some(f_mutbl) => f_mutbl, - none => { - self.tcx.sess.span_bug( - node.span(), - fmt!{"Cannot find field `%s` in type `%s`", - *f_name, ty_to_str(self.tcx, base_cmt.ty)}); - } - }; - let m = self.inherited_mutability(base_cmt.mutbl, f_mutbl); - let f_comp = comp_field(f_name, f_mutbl); - let lp = base_cmt.lp.map(|lp| @lp_comp(lp, f_comp) ); - @{id: node.id(), span: node.span(), - cat: cat_comp(base_cmt, f_comp), lp:lp, - mutbl: m, ty: self.tcx.ty(node)} - } - - fn cat_deref(node: N, base_cmt: cmt, derefs: uint, - expl: bool) -> option { - do ty::deref(self.tcx, base_cmt.ty, expl).map |mt| { - match deref_kind(self.tcx, base_cmt.ty) { - deref_ptr(ptr) => { - let lp = do base_cmt.lp.chain |l| { - // Given that the ptr itself is loanable, we can - // loan out deref'd uniq ptrs as the data they are - // the only way to reach the data they point at. - // Other ptr types admit aliases and are therefore - // not loanable. - match ptr { - uniq_ptr => {some(@lp_deref(l, ptr))} - gc_ptr | region_ptr(_) | unsafe_ptr => {none} - } - }; - - // for unique ptrs, we inherit mutability from the - // owning reference. - let m = match ptr { - uniq_ptr => { - self.inherited_mutability(base_cmt.mutbl, mt.mutbl) - } - gc_ptr | region_ptr(_) | unsafe_ptr => { - mt.mutbl - } - }; - - @{id:node.id(), span:node.span(), - cat:cat_deref(base_cmt, derefs, ptr), lp:lp, - mutbl:m, ty:mt.ty} - } - - deref_comp(comp) => { - let lp = base_cmt.lp.map(|l| @lp_comp(l, comp) ); - let m = self.inherited_mutability(base_cmt.mutbl, mt.mutbl); - @{id:node.id(), span:node.span(), - cat:cat_comp(base_cmt, comp), lp:lp, - mutbl:m, ty:mt.ty} - } - } - } - } - - fn cat_index(expr: @ast::expr, base: @ast::expr) -> cmt { - let base_cmt = self.cat_autoderef(base); - - let mt = match ty::index(self.tcx, base_cmt.ty) { - some(mt) => mt, - none => { - self.tcx.sess.span_bug( - expr.span, - fmt!{"Explicit index of non-index type `%s`", - ty_to_str(self.tcx, base_cmt.ty)}); - } - }; - - return match deref_kind(self.tcx, base_cmt.ty) { - deref_ptr(ptr) => { - // (a) the contents are loanable if the base is loanable - // and this is a *unique* vector - let deref_lp = match ptr { - uniq_ptr => {base_cmt.lp.map(|lp| @lp_deref(lp, uniq_ptr))} - _ => {none} - }; - - // (b) for unique ptrs, we inherit mutability from the - // owning reference. - let m = match ptr { - uniq_ptr => { - self.inherited_mutability(base_cmt.mutbl, mt.mutbl) - } - gc_ptr | region_ptr(_) | unsafe_ptr => { - mt.mutbl - } - }; - - // (c) the deref is explicit in the resulting cmt - let deref_cmt = @{id:expr.id, span:expr.span, - cat:cat_deref(base_cmt, 0u, ptr), lp:deref_lp, - mutbl:m, ty:mt.ty}; - - comp(expr, deref_cmt, base_cmt.ty, m, mt.ty) - } - - deref_comp(_) => { - // fixed-length vectors have no deref - comp(expr, base_cmt, base_cmt.ty, mt.mutbl, mt.ty) - } - }; - - fn comp(expr: @ast::expr, of_cmt: cmt, - vect: ty::t, mutbl: ast::mutability, ty: ty::t) -> cmt { - let comp = comp_index(vect, mutbl); - let index_lp = of_cmt.lp.map(|lp| @lp_comp(lp, comp) ); - @{id:expr.id, span:expr.span, - cat:cat_comp(of_cmt, comp), lp:index_lp, - mutbl:mutbl, ty:ty} - } - } - - fn cat_tuple_elt(elt: N, cmt: cmt) -> cmt { - @{id: elt.id(), span: elt.span(), - cat: cat_comp(cmt, comp_tuple), - lp: cmt.lp.map(|l| @lp_comp(l, comp_tuple) ), - mutbl: cmt.mutbl, // imm iff in an immutable context - ty: self.tcx.ty(elt)} - } -} - -impl private_methods for borrowck_ctxt { - fn cat_method_ref(expr: @ast::expr, expr_ty: ty::t) -> cmt { - @{id:expr.id, span:expr.span, - cat:cat_special(sk_method), lp:none, - mutbl:m_imm, ty:expr_ty} - } - - fn cat_autoderef(base: @ast::expr) -> cmt { - // Creates a string of implicit derefences so long as base is - // dereferencable. n.b., it is important that these dereferences are - // associated with the field/index that caused the autoderef (expr). - // This is used later to adjust ref counts and so forth in trans. - - // Given something like base.f where base has type @m1 @m2 T, we want - // to yield the equivalent categories to (**base).f. - let mut cmt = self.cat_expr(base); - let mut ctr = 0u; - loop { - ctr += 1u; - match self.cat_deref(base, cmt, ctr, false) { - none => return cmt, - some(cmt1) => cmt = cmt1 - } - } - } -} - -fn field_mutbl(tcx: ty::ctxt, - base_ty: ty::t, - f_name: ast::ident) -> option { - // Need to refactor so that records/class fields can be treated uniformly. - match ty::get(base_ty).struct { - ty::ty_rec(fields) => { - for fields.each |f| { - if f.ident == f_name { - return some(f.mt.mutbl); - } - } - } - ty::ty_class(did, substs) => { - for ty::lookup_class_fields(tcx, did).each |fld| { - if fld.ident == f_name { - let m = match fld.mutability { - ast::class_mutable => ast::m_mutbl, - ast::class_immutable => ast::m_imm - }; - return some(m); - } - } - } - _ => { } - } - - return none; -} diff --git a/src/rustc/middle/borrowck/check_loans.rs b/src/rustc/middle/borrowck/check_loans.rs index 9b7d0e037c1..d0ec0518458 100644 --- a/src/rustc/middle/borrowck/check_loans.rs +++ b/src/rustc/middle/borrowck/check_loans.rs @@ -8,7 +8,6 @@ // 4. moves to dnot affect things loaned out in any way import dvec::{dvec, extensions}; -import categorization::public_methods; export check_loans; diff --git a/src/rustc/middle/borrowck/gather_loans.rs b/src/rustc/middle/borrowck/gather_loans.rs index 8595ad6b132..ee09584bb9f 100644 --- a/src/rustc/middle/borrowck/gather_loans.rs +++ b/src/rustc/middle/borrowck/gather_loans.rs @@ -6,7 +6,7 @@ // their associated scopes. In phase two, checking loans, we will then make // sure that all of these loans are honored. -import categorization::{public_methods, opt_deref_kind}; +import mem_categorization::{opt_deref_kind}; import loan::public_methods; import preserve::{public_methods, preserve_condition, pc_ok, pc_if_pure}; import ty::ty_region; @@ -406,163 +406,57 @@ impl methods for gather_loan_ctxt { } } - fn gather_pat(cmt: cmt, pat: @ast::pat, + fn gather_pat(discr_cmt: cmt, root_pat: @ast::pat, arm_id: ast::node_id, alt_id: ast::node_id) { - - // Here, `cmt` is the categorization for the value being - // matched and pat is the pattern it is being matched against. - // - // In general, the way that this works is that we walk down - // the pattern, constructing a cmt that represents the path - // that will be taken to reach the value being matched. - // - // When we encounter named bindings, we take the cmt that has - // been built up and pass it off to guarantee_valid() so that - // we can be sure that the binding will remain valid for the - // duration of the arm. - // - // The correspondence between the id in the cmt and which - // pattern is being referred to is somewhat...subtle. In - // general, the id of the cmt is the id of the node that - // produces the value. For patterns, that's actually the - // *subpattern*, generally speaking. - // - // To see what I mean about ids etc, consider: - // - // let x = @@3; - // match x { - // @@y { ... } - // } - // - // Here the cmt for `y` would be something like - // - // local(x)->@->@ - // - // where the id of `local(x)` is the id of the `x` that appears - // in the alt, the id of `local(x)->@` is the `@y` pattern, - // and the id of `local(x)->@->@` is the id of the `y` pattern. - - debug!{"gather_pat: id=%d pat=%s cmt=%s arm_id=%d alt_id=%d", - pat.id, pprust::pat_to_str(pat), - self.bccx.cmt_to_repr(cmt), arm_id, alt_id}; - let _i = indenter(); - - let tcx = self.tcx(); - match pat.node { - ast::pat_wild => { - // _ - } - - ast::pat_enum(_, none) => { - // variant(*) - } - ast::pat_enum(_, some(subpats)) => { - // variant(x, y, z) - let enum_did = match self.bccx.tcx.def_map -.find(pat.id) { - some(ast::def_variant(enum_did, _)) => enum_did, - e => tcx.sess.span_bug(pat.span, - fmt!{"resolved to %?, \ - not variant", e}) - }; - - for subpats.each |subpat| { - let subcmt = self.bccx.cat_variant(subpat, enum_did, cmt); - self.gather_pat(subcmt, subpat, arm_id, alt_id); - } - } - - ast::pat_ident(bm, id, o_pat) if !self.pat_is_variant(pat) => { - match bm { - ast::bind_by_value => { - // copying does not borrow anything, so no check is required - } - ast::bind_by_ref(mutbl) => { - // ref x or ref x @ p --- creates a ptr which must - // remain valid for the scope of the alt - - // find the region of the resulting pointer (note that - // the type of such a pattern will *always* be a - // region pointer) - let scope_r = ty_region(tcx.ty(pat)); - - // if the scope of the region ptr turns out to be - // specific to this arm, wrap the categorization with - // a cat_discr() node. There is a detailed discussion - // of the function of this node in method preserve(): - let arm_scope = ty::re_scope(arm_id); - if self.bccx.is_subregion_of(scope_r, arm_scope) { - let cmt_discr = self.bccx.cat_discr(cmt, alt_id); - self.guarantee_valid(cmt_discr, mutbl, scope_r); - } else { - self.guarantee_valid(cmt, mutbl, scope_r); + do self.bccx.cat_pattern(discr_cmt, root_pat) |cmt, pat| { + match pat.node { + ast::pat_ident(bm, id, o_pat) if !self.pat_is_variant(pat) => { + match bm { + ast::bind_by_value => { + // copying does not borrow anything, so no check + // is required + } + ast::bind_by_ref(mutbl) => { + // ref x or ref x @ p --- creates a ptr which must + // remain valid for the scope of the alt + + // find the region of the resulting pointer (note that + // the type of such a pattern will *always* be a + // region pointer) + let scope_r = ty_region(self.tcx().ty(pat)); + + // if the scope of the region ptr turns out to be + // specific to this arm, wrap the categorization with + // a cat_discr() node. There is a detailed discussion + // of the function of this node in method preserve(): + let arm_scope = ty::re_scope(arm_id); + if self.bccx.is_subregion_of(scope_r, arm_scope) { + let cmt_discr = self.bccx.cat_discr(cmt, alt_id); + self.guarantee_valid(cmt_discr, mutbl, scope_r); + } else { + self.guarantee_valid(cmt, mutbl, scope_r); + } + } + ast::bind_by_implicit_ref => { + // Note: there is a discussion of the function of + // cat_discr in the method preserve(): + let cmt1 = self.bccx.cat_discr(cmt, alt_id); + let arm_scope = ty::re_scope(arm_id); + + // We used to remember the mutability of the location + // that this binding refers to and use it later when + // categorizing the binding. This hack is being + // removed in favor of ref mode bindings. + // + // self.bccx.binding_map.insert(pat.id, cmt1.mutbl); + + self.guarantee_valid(cmt1, m_const, arm_scope); + } } } - ast::bind_by_implicit_ref => { - // Note: there is a discussion of the function of - // cat_discr in the method preserve(): - let cmt1 = self.bccx.cat_discr(cmt, alt_id); - let arm_scope = ty::re_scope(arm_id); - - // Remember the mutability of the location that this - // binding refers to. This will be used later when - // categorizing the binding. This is a bit of a hack that - // would be better fixed by #2329; in that case we could - // allow the user to specify if they want an imm, const, - // or mut binding, or else just reflect the mutability - // through the type of the region pointer. - self.bccx.binding_map.insert(pat.id, cmt1.mutbl); - - self.guarantee_valid(cmt1, m_const, arm_scope); - } - } - for o_pat.each |p| { - self.gather_pat(cmt, p, arm_id, alt_id); - } - } - - ast::pat_ident(*) => { - // nullary variant: ignore. - assert self.pat_is_variant(pat); - } - - ast::pat_rec(field_pats, _) => { - // {f1: p1, ..., fN: pN} - for field_pats.each |fp| { - let cmt_field = self.bccx.cat_field(fp.pat, cmt, fp.ident); - self.gather_pat(cmt_field, fp.pat, arm_id, alt_id); - } - } - - ast::pat_struct(_, field_pats, _) => { - // {f1: p1, ..., fN: pN} - for field_pats.each |fp| { - let cmt_field = self.bccx.cat_field(fp.pat, cmt, fp.ident); - self.gather_pat(cmt_field, fp.pat, arm_id, alt_id); - } - } - ast::pat_tup(subpats) => { - // (p1, ..., pN) - for subpats.each |subpat| { - let subcmt = self.bccx.cat_tuple_elt(subpat, cmt); - self.gather_pat(subcmt, subpat, arm_id, alt_id); + _ => {} } - } - - ast::pat_box(subpat) | ast::pat_uniq(subpat) => { - // @p1, ~p1 - match self.bccx.cat_deref(subpat, cmt, 0u, true) { - some(subcmt) => { - self.gather_pat(subcmt, subpat, arm_id, alt_id); - } - none => { - tcx.sess.span_bug(pat.span, ~"Non derefable type"); - } - } - } - - ast::pat_lit(_) | ast::pat_range(_, _) => { /*always ok*/ } } } diff --git a/src/rustc/middle/mem_categorization.rs b/src/rustc/middle/mem_categorization.rs new file mode 100644 index 00000000000..9d6629d8edc --- /dev/null +++ b/src/rustc/middle/mem_categorization.rs @@ -0,0 +1,868 @@ +/*! + * # Categorization + * + * The job of the categorization module is to analyze an expression to + * determine what kind of memory is used in evaluating it (for example, + * where dereferences occur and what kind of pointer is dereferenced; + * whether the memory is mutable; etc) + * + * Categorization effectively transforms all of our expressions into + * expressions of the following forms (the actual enum has many more + * possibilities, naturally, but they are all variants of these base + * forms): + * + * E = rvalue // some computed rvalue + * | x // address of a local variable, arg, or upvar + * | *E // deref of a ptr + * | E.comp // access to an interior component + * + * Imagine a routine ToAddr(Expr) that evaluates an expression and returns an + * address where the result is to be found. If Expr is an lvalue, then this + * is the address of the lvalue. If Expr is an rvalue, this is the address of + * some temporary spot in memory where the result is stored. + * + * Now, cat_expr() classies the expression Expr and the address A=ToAddr(Expr) + * as follows: + * + * - cat: what kind of expression was this? This is a subset of the + * full expression forms which only includes those that we care about + * for the purpose of the analysis. + * - mutbl: mutability of the address A + * - ty: the type of data found at the address A + * + * The resulting categorization tree differs somewhat from the expressions + * themselves. For example, auto-derefs are explicit. Also, an index a[b] is + * decomposed into two operations: a derefence to reach the array data and + * then an index to jump forward to the relevant item. + */ + +import syntax::ast; +import syntax::ast::{m_imm, m_const, m_mutbl}; +import syntax::codemap::span; +import syntax::print::pprust; +import util::ppaux::{ty_to_str, region_to_str}; +import util::common::indenter; + +enum categorization { + cat_rvalue, // result of eval'ing some misc expr + cat_special(special_kind), // + cat_local(ast::node_id), // local variable + cat_binding(ast::node_id), // pattern binding + cat_arg(ast::node_id), // formal argument + cat_stack_upvar(cmt), // upvar in stack closure + cat_deref(cmt, uint, ptr_kind), // deref of a ptr + cat_comp(cmt, comp_kind), // adjust to locate an internal component + cat_discr(cmt, ast::node_id), // match discriminant (see preserve()) +} + +// different kinds of pointers: +enum ptr_kind {uniq_ptr, gc_ptr, region_ptr(ty::region), unsafe_ptr} + +// I am coining the term "components" to mean "pieces of a data +// structure accessible without a dereference": +enum comp_kind { + comp_tuple, // elt in a tuple + comp_variant(ast::def_id), // internals to a variant of given enum + comp_field(ast::ident, // name of field + ast::mutability), // declared mutability of field + comp_index(ty::t, // type of vec/str/etc being deref'd + ast::mutability) // mutability of vec content +} + +// different kinds of expressions we might evaluate +enum special_kind { + sk_method, + sk_static_item, + sk_self, + sk_heap_upvar +} + +// a complete categorization of a value indicating where it originated +// and how it is located, as well as the mutability of the memory in +// which the value is stored. +type cmt = @{id: ast::node_id, // id of expr/pat producing this value + span: span, // span of same expr/pat + cat: categorization, // categorization of expr + lp: option<@loan_path>, // loan path for expr, if any + mutbl: ast::mutability, // mutability of expr as lvalue + ty: ty::t}; // type of the expr + +// a loan path is like a category, but it exists only when the data is +// interior to the stack frame. loan paths are used as the key to a +// map indicating what is borrowed at any point in time. +enum loan_path { + lp_local(ast::node_id), + lp_arg(ast::node_id), + lp_deref(@loan_path, ptr_kind), + lp_comp(@loan_path, comp_kind) +} + +// We pun on *T to mean both actual deref of a ptr as well +// as accessing of components: +enum deref_kind {deref_ptr(ptr_kind), deref_comp(comp_kind)} + +// Categorizes a derefable type. Note that we include vectors and strings as +// derefable (we model an index as the combination of a deref and then a +// pointer adjustment). +fn opt_deref_kind(t: ty::t) -> option { + match ty::get(t).struct { + ty::ty_uniq(*) | + ty::ty_evec(_, ty::vstore_uniq) | + ty::ty_estr(ty::vstore_uniq) => { + some(deref_ptr(uniq_ptr)) + } + + ty::ty_rptr(r, _) | + ty::ty_evec(_, ty::vstore_slice(r)) | + ty::ty_estr(ty::vstore_slice(r)) => { + some(deref_ptr(region_ptr(r))) + } + + ty::ty_box(*) | + ty::ty_evec(_, ty::vstore_box) | + ty::ty_estr(ty::vstore_box) => { + some(deref_ptr(gc_ptr)) + } + + ty::ty_ptr(*) => { + some(deref_ptr(unsafe_ptr)) + } + + ty::ty_enum(did, _) => { + some(deref_comp(comp_variant(did))) + } + + ty::ty_evec(mt, ty::vstore_fixed(_)) => { + some(deref_comp(comp_index(t, mt.mutbl))) + } + + ty::ty_estr(ty::vstore_fixed(_)) => { + some(deref_comp(comp_index(t, m_imm))) + } + + _ => none + } +} + +fn deref_kind(tcx: ty::ctxt, t: ty::t) -> deref_kind { + match opt_deref_kind(t) { + some(k) => k, + none => { + tcx.sess.bug( + fmt!{"deref_cat() invoked on non-derefable type %s", + ty_to_str(tcx, t)}); + } + } +} + +fn cat_borrow_of_expr( + tcx: ty::ctxt, + method_map: typeck::method_map, + expr: @ast::expr) -> cmt { + + let mcx = &mem_categorization_ctxt { + tcx: tcx, method_map: method_map + }; + return mcx.cat_borrow_of_expr(expr); +} + +fn cat_expr( + tcx: ty::ctxt, + method_map: typeck::method_map, + expr: @ast::expr) -> cmt { + + let mcx = &mem_categorization_ctxt { + tcx: tcx, method_map: method_map + }; + return mcx.cat_expr(expr); +} + +fn cat_def( + tcx: ty::ctxt, + method_map: typeck::method_map, + expr_id: ast::node_id, + expr_span: span, + expr_ty: ty::t, + def: ast::def) -> cmt { + + let mcx = &mem_categorization_ctxt { + tcx: tcx, method_map: method_map + }; + return mcx.cat_def(expr_id, expr_span, expr_ty, def); +} + +fn cat_variant( + tcx: ty::ctxt, + method_map: typeck::method_map, + arg: N, + enum_did: ast::def_id, + cmt: cmt) -> cmt { + + let mcx = &mem_categorization_ctxt { + tcx: tcx, method_map: method_map + }; + return mcx.cat_variant(arg, enum_did, cmt); +} + +trait ast_node { + fn id() -> ast::node_id; + fn span() -> span; +} + +impl of ast_node for @ast::expr { + fn id() -> ast::node_id { self.id } + fn span() -> span { self.span } +} + +impl of ast_node for @ast::pat { + fn id() -> ast::node_id { self.id } + fn span() -> span { self.span } +} + +trait get_type_for_node { + fn ty(node: N) -> ty::t; +} + +impl methods of get_type_for_node for ty::ctxt { + fn ty(node: N) -> ty::t { + ty::node_id_to_type(self, node.id()) + } +} + +struct mem_categorization_ctxt { + tcx: ty::ctxt; + method_map: typeck::method_map; +} + +impl &mem_categorization_ctxt { + fn cat_borrow_of_expr(expr: @ast::expr) -> cmt { + // a borrowed expression must be either an @, ~, or a @vec, ~vec + let expr_ty = ty::expr_ty(self.tcx, expr); + match ty::get(expr_ty).struct { + ty::ty_evec(*) | ty::ty_estr(*) => { + self.cat_index(expr, expr) + } + + ty::ty_uniq(*) | ty::ty_box(*) | ty::ty_rptr(*) => { + let cmt = self.cat_expr(expr); + self.cat_deref(expr, cmt, 0u, true).get() + } + + /* + ty::ty_fn({proto, _}) { + self.cat_call(expr, expr, proto) + } + */ + + _ => { + self.tcx.sess.span_bug( + expr.span, + fmt!{"Borrowing of non-derefable type `%s`", + ty_to_str(self.tcx, expr_ty)}); + } + } + } + + fn cat_expr(expr: @ast::expr) -> cmt { + debug!{"cat_expr: id=%d expr=%s", + expr.id, pprust::expr_to_str(expr)}; + + let tcx = self.tcx; + let expr_ty = tcx.ty(expr); + match expr.node { + ast::expr_unary(ast::deref, e_base) => { + if self.method_map.contains_key(expr.id) { + return self.cat_rvalue(expr, expr_ty); + } + + let base_cmt = self.cat_expr(e_base); + match self.cat_deref(expr, base_cmt, 0u, true) { + some(cmt) => return cmt, + none => { + tcx.sess.span_bug( + e_base.span, + fmt!{"Explicit deref of non-derefable type `%s`", + ty_to_str(tcx, tcx.ty(e_base))}); + } + } + } + + ast::expr_field(base, f_name, _) => { + if self.method_map.contains_key(expr.id) { + return self.cat_method_ref(expr, expr_ty); + } + + let base_cmt = self.cat_autoderef(base); + self.cat_field(expr, base_cmt, f_name) + } + + ast::expr_index(base, _) => { + if self.method_map.contains_key(expr.id) { + return self.cat_rvalue(expr, expr_ty); + } + + self.cat_index(expr, base) + } + + ast::expr_path(_) => { + let def = self.tcx.def_map.get(expr.id); + self.cat_def(expr.id, expr.span, expr_ty, def) + } + + ast::expr_addr_of(*) | ast::expr_call(*) | + ast::expr_swap(*) | ast::expr_move(*) | ast::expr_assign(*) | + ast::expr_assign_op(*) | ast::expr_fn(*) | ast::expr_fn_block(*) | + ast::expr_assert(*) | ast::expr_ret(*) | + ast::expr_loop_body(*) | ast::expr_do_body(*) | ast::expr_unary(*) | + ast::expr_copy(*) | ast::expr_cast(*) | ast::expr_fail(*) | + ast::expr_vstore(*) | ast::expr_vec(*) | ast::expr_tup(*) | + ast::expr_if(*) | ast::expr_log(*) | + ast::expr_binary(*) | ast::expr_while(*) | + ast::expr_block(*) | ast::expr_loop(*) | ast::expr_match(*) | + ast::expr_lit(*) | ast::expr_break | ast::expr_mac(*) | + ast::expr_again | ast::expr_rec(*) | ast::expr_struct(*) | + ast::expr_unary_move(*) | ast::expr_repeat(*) => { + return self.cat_rvalue(expr, expr_ty); + } + } + } + + fn cat_def(id: ast::node_id, + span: span, + expr_ty: ty::t, + def: ast::def) -> cmt { + match def { + ast::def_fn(*) | ast::def_static_method(*) | ast::def_mod(_) | + ast::def_foreign_mod(_) | ast::def_const(_) | + ast::def_use(_) | ast::def_variant(*) | + ast::def_ty(_) | ast::def_prim_ty(_) | + ast::def_ty_param(*) | ast::def_class(*) | + ast::def_typaram_binder(*) | ast::def_region(_) => { + @{id:id, span:span, + cat:cat_special(sk_static_item), lp:none, + mutbl:m_imm, ty:expr_ty} + } + + ast::def_arg(vid, mode) => { + // Idea: make this could be rewritten to model by-ref + // stuff as `&const` and `&mut`? + + // m: mutability of the argument + // lp: loan path, must be none for aliasable things + let {m,lp} = match ty::resolved_mode(self.tcx, mode) { + ast::by_mutbl_ref => { + {m: m_mutbl, lp: none} + } + ast::by_move | ast::by_copy => { + {m: m_imm, lp: some(@lp_arg(vid))} + } + ast::by_ref => { + {m: m_imm, lp: none} + } + ast::by_val => { + // by-value is this hybrid mode where we have a + // pointer but we do not own it. This is not + // considered loanable because, for example, a by-ref + // and and by-val argument might both actually contain + // the same unique ptr. + {m: m_imm, lp: none} + } + }; + @{id:id, span:span, + cat:cat_arg(vid), lp:lp, + mutbl:m, ty:expr_ty} + } + + ast::def_self(_) => { + @{id:id, span:span, + cat:cat_special(sk_self), lp:none, + mutbl:m_imm, ty:expr_ty} + } + + ast::def_upvar(upvid, inner, fn_node_id) => { + let ty = ty::node_id_to_type(self.tcx, fn_node_id); + let proto = ty::ty_fn_proto(ty); + match proto { + ast::proto_block => { + let upcmt = self.cat_def(id, span, expr_ty, *inner); + @{id:id, span:span, + cat:cat_stack_upvar(upcmt), lp:upcmt.lp, + mutbl:upcmt.mutbl, ty:upcmt.ty} + } + ast::proto_bare | ast::proto_uniq | ast::proto_box => { + // FIXME #2152 allow mutation of moved upvars + @{id:id, span:span, + cat:cat_special(sk_heap_upvar), lp:none, + mutbl:m_imm, ty:expr_ty} + } + } + } + + ast::def_local(vid, mutbl) => { + let m = if mutbl {m_mutbl} else {m_imm}; + @{id:id, span:span, + cat:cat_local(vid), lp:some(@lp_local(vid)), + mutbl:m, ty:expr_ty} + } + + ast::def_binding(vid, ast::bind_by_value) | + ast::def_binding(vid, ast::bind_by_ref(_)) => { + // by-value/by-ref bindings are local variables + @{id:id, span:span, + cat:cat_local(vid), lp:some(@lp_local(vid)), + mutbl:m_imm, ty:expr_ty} + } + + ast::def_binding(pid, ast::bind_by_implicit_ref) => { + // implicit-by-ref bindings are "special" since they are + // implicit pointers. + + // Technically, the mutability is not always imm, but we + // (choose to be) unsound for the moment since these + // implicit refs are going away and it reduces external + // dependencies. + + @{id:id, span:span, + cat:cat_binding(pid), lp:none, + mutbl:m_imm, ty:expr_ty} + } + } + } + + fn cat_variant(arg: N, + enum_did: ast::def_id, + cmt: cmt) -> cmt { + @{id: arg.id(), span: arg.span(), + cat: cat_comp(cmt, comp_variant(enum_did)), + lp: cmt.lp.map(|l| @lp_comp(l, comp_variant(enum_did)) ), + mutbl: cmt.mutbl, // imm iff in an immutable context + ty: self.tcx.ty(arg)} + } + + fn cat_rvalue(expr: @ast::expr, expr_ty: ty::t) -> cmt { + @{id:expr.id, span:expr.span, + cat:cat_rvalue, lp:none, + mutbl:m_imm, ty:expr_ty} + } + + /// inherited mutability: used in cases where the mutability of a + /// component is inherited from the base it is a part of. For + /// example, a record field is mutable if it is declared mutable + /// or if the container is mutable. + fn inherited_mutability(base_m: ast::mutability, + comp_m: ast::mutability) -> ast::mutability { + match comp_m { + m_imm => {base_m} // imm: as mutable as the container + m_mutbl | m_const => {comp_m} + } + } + + fn cat_field(node: N, base_cmt: cmt, + f_name: ast::ident) -> cmt { + let f_mutbl = match field_mutbl(self.tcx, base_cmt.ty, f_name) { + some(f_mutbl) => f_mutbl, + none => { + self.tcx.sess.span_bug( + node.span(), + fmt!{"Cannot find field `%s` in type `%s`", + *f_name, ty_to_str(self.tcx, base_cmt.ty)}); + } + }; + let m = self.inherited_mutability(base_cmt.mutbl, f_mutbl); + let f_comp = comp_field(f_name, f_mutbl); + let lp = base_cmt.lp.map(|lp| @lp_comp(lp, f_comp) ); + @{id: node.id(), span: node.span(), + cat: cat_comp(base_cmt, f_comp), lp:lp, + mutbl: m, ty: self.tcx.ty(node)} + } + + fn cat_deref(node: N, base_cmt: cmt, derefs: uint, + expl: bool) -> option { + do ty::deref(self.tcx, base_cmt.ty, expl).map |mt| { + match deref_kind(self.tcx, base_cmt.ty) { + deref_ptr(ptr) => { + let lp = do base_cmt.lp.chain |l| { + // Given that the ptr itself is loanable, we can + // loan out deref'd uniq ptrs as the data they are + // the only way to reach the data they point at. + // Other ptr types admit aliases and are therefore + // not loanable. + match ptr { + uniq_ptr => {some(@lp_deref(l, ptr))} + gc_ptr | region_ptr(_) | unsafe_ptr => {none} + } + }; + + // for unique ptrs, we inherit mutability from the + // owning reference. + let m = match ptr { + uniq_ptr => { + self.inherited_mutability(base_cmt.mutbl, mt.mutbl) + } + gc_ptr | region_ptr(_) | unsafe_ptr => { + mt.mutbl + } + }; + + @{id:node.id(), span:node.span(), + cat:cat_deref(base_cmt, derefs, ptr), lp:lp, + mutbl:m, ty:mt.ty} + } + + deref_comp(comp) => { + let lp = base_cmt.lp.map(|l| @lp_comp(l, comp) ); + let m = self.inherited_mutability(base_cmt.mutbl, mt.mutbl); + @{id:node.id(), span:node.span(), + cat:cat_comp(base_cmt, comp), lp:lp, + mutbl:m, ty:mt.ty} + } + } + } + } + + fn cat_index(expr: @ast::expr, base: @ast::expr) -> cmt { + let base_cmt = self.cat_autoderef(base); + + let mt = match ty::index(self.tcx, base_cmt.ty) { + some(mt) => mt, + none => { + self.tcx.sess.span_bug( + expr.span, + fmt!{"Explicit index of non-index type `%s`", + ty_to_str(self.tcx, base_cmt.ty)}); + } + }; + + return match deref_kind(self.tcx, base_cmt.ty) { + deref_ptr(ptr) => { + // (a) the contents are loanable if the base is loanable + // and this is a *unique* vector + let deref_lp = match ptr { + uniq_ptr => {base_cmt.lp.map(|lp| @lp_deref(lp, uniq_ptr))} + _ => {none} + }; + + // (b) for unique ptrs, we inherit mutability from the + // owning reference. + let m = match ptr { + uniq_ptr => { + self.inherited_mutability(base_cmt.mutbl, mt.mutbl) + } + gc_ptr | region_ptr(_) | unsafe_ptr => { + mt.mutbl + } + }; + + // (c) the deref is explicit in the resulting cmt + let deref_cmt = @{id:expr.id, span:expr.span, + cat:cat_deref(base_cmt, 0u, ptr), lp:deref_lp, + mutbl:m, ty:mt.ty}; + + comp(expr, deref_cmt, base_cmt.ty, m, mt.ty) + } + + deref_comp(_) => { + // fixed-length vectors have no deref + comp(expr, base_cmt, base_cmt.ty, mt.mutbl, mt.ty) + } + }; + + fn comp(expr: @ast::expr, of_cmt: cmt, + vect: ty::t, mutbl: ast::mutability, ty: ty::t) -> cmt { + let comp = comp_index(vect, mutbl); + let index_lp = of_cmt.lp.map(|lp| @lp_comp(lp, comp) ); + @{id:expr.id, span:expr.span, + cat:cat_comp(of_cmt, comp), lp:index_lp, + mutbl:mutbl, ty:ty} + } + } + + fn cat_tuple_elt(elt: N, cmt: cmt) -> cmt { + @{id: elt.id(), span: elt.span(), + cat: cat_comp(cmt, comp_tuple), + lp: cmt.lp.map(|l| @lp_comp(l, comp_tuple) ), + mutbl: cmt.mutbl, // imm iff in an immutable context + ty: self.tcx.ty(elt)} + } + + fn cat_method_ref(expr: @ast::expr, expr_ty: ty::t) -> cmt { + @{id:expr.id, span:expr.span, + cat:cat_special(sk_method), lp:none, + mutbl:m_imm, ty:expr_ty} + } + + fn cat_autoderef(base: @ast::expr) -> cmt { + // Creates a string of implicit derefences so long as base is + // dereferencable. n.b., it is important that these dereferences are + // associated with the field/index that caused the autoderef (expr). + // This is used later to adjust ref counts and so forth in trans. + + // Given something like base.f where base has type @m1 @m2 T, we want + // to yield the equivalent categories to (**base).f. + let mut cmt = self.cat_expr(base); + let mut ctr = 0u; + loop { + ctr += 1u; + match self.cat_deref(base, cmt, ctr, false) { + none => return cmt, + some(cmt1) => cmt = cmt1 + } + } + } + + fn cat_pattern(cmt: cmt, pat: @ast::pat, op: fn(cmt, @ast::pat)) { + + op(cmt, pat); + + // Here, `cmt` is the categorization for the value being + // matched and pat is the pattern it is being matched against. + // + // In general, the way that this works is that we walk down + // the pattern, constructing a cmt that represents the path + // that will be taken to reach the value being matched. + // + // When we encounter named bindings, we take the cmt that has + // been built up and pass it off to guarantee_valid() so that + // we can be sure that the binding will remain valid for the + // duration of the arm. + // + // The correspondence between the id in the cmt and which + // pattern is being referred to is somewhat...subtle. In + // general, the id of the cmt is the id of the node that + // produces the value. For patterns, that's actually the + // *subpattern*, generally speaking. + // + // To see what I mean about ids etc, consider: + // + // let x = @@3; + // match x { + // @@y { ... } + // } + // + // Here the cmt for `y` would be something like + // + // local(x)->@->@ + // + // where the id of `local(x)` is the id of the `x` that appears + // in the alt, the id of `local(x)->@` is the `@y` pattern, + // and the id of `local(x)->@->@` is the id of the `y` pattern. + + debug!{"cat_pattern: id=%d pat=%s cmt=%s", + pat.id, pprust::pat_to_str(pat), + self.cmt_to_repr(cmt)}; + let _i = indenter(); + + let tcx = self.tcx; + match pat.node { + ast::pat_wild => { + // _ + } + + ast::pat_enum(_, none) => { + // variant(*) + } + ast::pat_enum(_, some(subpats)) => { + // variant(x, y, z) + let enum_did = match self.tcx.def_map.find(pat.id) { + some(ast::def_variant(enum_did, _)) => enum_did, + e => tcx.sess.span_bug(pat.span, + fmt!{"resolved to %?, not variant", e}) + }; + + for subpats.each |subpat| { + let subcmt = self.cat_variant(subpat, enum_did, cmt); + self.cat_pattern(subcmt, subpat, op); + } + } + + ast::pat_ident(_, _, some(subpat)) => { + self.cat_pattern(cmt, subpat, op); + } + + ast::pat_ident(_, _, none) => { + // nullary variant or identifier: ignore + } + + ast::pat_rec(field_pats, _) => { + // {f1: p1, ..., fN: pN} + for field_pats.each |fp| { + let cmt_field = self.cat_field(fp.pat, cmt, fp.ident); + self.cat_pattern(cmt_field, fp.pat, op); + } + } + + ast::pat_struct(_, field_pats, _) => { + // {f1: p1, ..., fN: pN} + for field_pats.each |fp| { + let cmt_field = self.cat_field(fp.pat, cmt, fp.ident); + self.cat_pattern(cmt_field, fp.pat, op); + } + } + + ast::pat_tup(subpats) => { + // (p1, ..., pN) + for subpats.each |subpat| { + let subcmt = self.cat_tuple_elt(subpat, cmt); + self.cat_pattern(subcmt, subpat, op); + } + } + + ast::pat_box(subpat) | ast::pat_uniq(subpat) => { + // @p1, ~p1 + match self.cat_deref(subpat, cmt, 0u, true) { + some(subcmt) => { + self.cat_pattern(subcmt, subpat, op); + } + none => { + tcx.sess.span_bug(pat.span, ~"Non derefable type"); + } + } + } + + ast::pat_lit(_) | ast::pat_range(_, _) => { /*always ok*/ } + } + } + + fn cat_to_repr(cat: categorization) -> ~str { + match cat { + cat_special(sk_method) => ~"method", + cat_special(sk_static_item) => ~"static_item", + cat_special(sk_self) => ~"self", + cat_special(sk_heap_upvar) => ~"heap-upvar", + cat_stack_upvar(_) => ~"stack-upvar", + cat_rvalue => ~"rvalue", + cat_local(node_id) => fmt!{"local(%d)", node_id}, + cat_binding(node_id) => fmt!{"binding(%d)", node_id}, + cat_arg(node_id) => fmt!{"arg(%d)", node_id}, + cat_deref(cmt, derefs, ptr) => { + fmt!{"%s->(%s, %u)", self.cat_to_repr(cmt.cat), + self.ptr_sigil(ptr), derefs} + } + cat_comp(cmt, comp) => { + fmt!{"%s.%s", self.cat_to_repr(cmt.cat), self.comp_to_repr(comp)} + } + cat_discr(cmt, _) => self.cat_to_repr(cmt.cat) + } + } + + fn mut_to_str(mutbl: ast::mutability) -> ~str { + match mutbl { + m_mutbl => ~"mutable", + m_const => ~"const", + m_imm => ~"immutable" + } + } + + fn ptr_sigil(ptr: ptr_kind) -> ~str { + match ptr { + uniq_ptr => ~"~", + gc_ptr => ~"@", + region_ptr(_) => ~"&", + unsafe_ptr => ~"*" + } + } + + fn comp_to_repr(comp: comp_kind) -> ~str { + match comp { + comp_field(fld, _) => *fld, + comp_index(*) => ~"[]", + comp_tuple => ~"()", + comp_variant(_) => ~"" + } + } + + fn lp_to_str(lp: @loan_path) -> ~str { + match *lp { + lp_local(node_id) => { + fmt!{"local(%d)", node_id} + } + lp_arg(node_id) => { + fmt!{"arg(%d)", node_id} + } + lp_deref(lp, ptr) => { + fmt!{"%s->(%s)", self.lp_to_str(lp), + self.ptr_sigil(ptr)} + } + lp_comp(lp, comp) => { + fmt!{"%s.%s", self.lp_to_str(lp), + self.comp_to_repr(comp)} + } + } + } + + fn cmt_to_repr(cmt: cmt) -> ~str { + fmt!{"{%s id:%d m:%s lp:%s ty:%s}", + self.cat_to_repr(cmt.cat), + cmt.id, + self.mut_to_str(cmt.mutbl), + cmt.lp.map_default(~"none", |p| self.lp_to_str(p) ), + ty_to_str(self.tcx, cmt.ty)} + } + + fn cmt_to_str(cmt: cmt) -> ~str { + let mut_str = self.mut_to_str(cmt.mutbl); + match cmt.cat { + cat_special(sk_method) => ~"method", + cat_special(sk_static_item) => ~"static item", + cat_special(sk_self) => ~"self reference", + cat_special(sk_heap_upvar) => { + ~"captured outer variable in a heap closure" + } + cat_rvalue => ~"non-lvalue", + cat_local(_) => mut_str + ~" local variable", + cat_binding(_) => ~"pattern binding", + cat_arg(_) => ~"argument", + cat_deref(_, _, pk) => fmt!{"dereference of %s %s pointer", + mut_str, self.ptr_sigil(pk)}, + cat_stack_upvar(_) => { + ~"captured outer " + mut_str + ~" variable in a stack closure" + } + cat_comp(_, comp_field(*)) => mut_str + ~" field", + cat_comp(_, comp_tuple) => ~"tuple content", + cat_comp(_, comp_variant(_)) => ~"enum content", + cat_comp(_, comp_index(t, _)) => { + match ty::get(t).struct { + ty::ty_evec(*) => mut_str + ~" vec content", + ty::ty_estr(*) => mut_str + ~" str content", + _ => mut_str + ~" indexed content" + } + } + cat_discr(cmt, _) => { + self.cmt_to_str(cmt) + } + } + } + + fn region_to_str(r: ty::region) -> ~str { + region_to_str(self.tcx, r) + } +} + +fn field_mutbl(tcx: ty::ctxt, + base_ty: ty::t, + f_name: ast::ident) -> option { + // Need to refactor so that records/class fields can be treated uniformly. + match ty::get(base_ty).struct { + ty::ty_rec(fields) => { + for fields.each |f| { + if f.ident == f_name { + return some(f.mt.mutbl); + } + } + } + ty::ty_class(did, substs) => { + for ty::lookup_class_fields(tcx, did).each |fld| { + if fld.ident == f_name { + let m = match fld.mutability { + ast::class_mutable => ast::m_mutbl, + ast::class_immutable => ast::m_imm + }; + return some(m); + } + } + } + _ => { } + } + + return none; +} diff --git a/src/rustc/middle/typeck/check/regionck.rs b/src/rustc/middle/typeck/check/regionck.rs index e623c3ec0b9..506ed5902e8 100644 --- a/src/rustc/middle/typeck/check/regionck.rs +++ b/src/rustc/middle/typeck/check/regionck.rs @@ -171,7 +171,12 @@ fn visit_expr(e: @ast::expr, &&rcx: @rcx, v: rvt) { } } }; + } + ast::expr_addr_of(_, operand) => { + // FIXME(#3148) -- in some cases, we need to capture a dependency + // between the regions found in operand the resulting region type. + // See #3148 for more details. } _ => () diff --git a/src/rustc/rustc.rc b/src/rustc/rustc.rc index ce921f6d39a..4e12528b968 100644 --- a/src/rustc/rustc.rc +++ b/src/rustc/rustc.rc @@ -77,10 +77,10 @@ mod middle { mod borrowck { mod check_loans; mod gather_loans; - mod categorization; mod loan; mod preserve; } + mod mem_categorization; mod liveness; mod block_use; mod kind; diff --git a/src/test/run-pass/region-return-interior-of-option-in-self.rs b/src/test/run-pass/region-return-interior-of-option-in-self.rs new file mode 100644 index 00000000000..698d49c7319 --- /dev/null +++ b/src/test/run-pass/region-return-interior-of-option-in-self.rs @@ -0,0 +1,20 @@ +// xfail-test (#3148) + +struct cell { + value: T; +} + +struct cells { + vals: ~[option>]; +} + +impl &cells { + fn get(idx: uint) -> &self/T { + match self.vals[idx] { + some(ref v) => &v.value, + none => fail + } + } +} + +fn main() {} -- cgit 1.4.1-3-g733a5