refactor categorization out of borrowck into its own module.

first step towards #3148 and #3024.

6 files changed, 474 insertions, 370 deletions

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<ast::node_id, ()>;
 
-// 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<ast::node_id, ast::mutability>;
-
 // 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<T> = result<T, bckerr>;
 
-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<N: ast_node>(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<N: ast_node>(node: N) -> ty::t {
-        ty::node_id_to_type(self, node.id())
+    fn cat_variant<N: ast_node>(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(_) => ~"<enum>"
-        }
-    }
-
-    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/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/borrowck/categorization.rs b/src/rustc/middle/mem_categorization.rs
index 41204f117a5..9d6629d8edc 100644
--- a/src/rustc/middle/borrowck/categorization.rs
+++ b/src/rustc/middle/mem_categorization.rs
@@ -36,8 +36,70 @@
  * then an index to jump forward to the relevant item.
  */
 
-export public_methods;
-export opt_deref_kind;
+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
@@ -93,7 +155,86 @@ fn deref_kind(tcx: ty::ctxt, t: ty::t) -> deref_kind {
     }
 }
 
-impl public_methods for borrowck_ctxt {
+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<N: ast_node>(
+    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<N: ast_node>(node: N) -> ty::t;
+}
+
+impl methods of get_type_for_node for ty::ctxt {
+    fn ty<N: ast_node>(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);
@@ -276,13 +417,14 @@ impl public_methods for borrowck_ctxt {
             // 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);
+            // 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:mutbl, ty:expr_ty}
+              mutbl:m_imm, ty:expr_ty}
           }
         }
     }
@@ -303,10 +445,6 @@ impl public_methods for borrowck_ctxt {
           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
@@ -446,9 +584,7 @@ impl public_methods for borrowck_ctxt {
           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,
@@ -473,6 +609,233 @@ impl private_methods for borrowck_ctxt {
             }
         }
     }
+
+    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(_) => ~"<enum>"
+        }
+    }
+
+    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,
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;