librustc: Allow `&mut` to be loaned; allow `self` to be loaned; make `&mut` loanable to `&`. r=nmatsakis

29 files changed, 338 insertions, 166 deletions

diff --git a/src/libcore/vec.rs b/src/libcore/vec.rs
index ee30d7939b7..7d7e16e930c 100644
--- a/src/libcore/vec.rs
+++ b/src/libcore/vec.rs
@@ -14,6 +14,7 @@
 #[forbid(deprecated_pattern)];
 #[warn(non_camel_case_types)];
 
+use cast::transmute;
 use cast;
 use cmp::{Eq, Ord};
 use iter::BaseIter;
@@ -477,14 +478,20 @@ pub fn shift<T>(v: &mut ~[T]) -> T {
         // Memcopy the head element (the one we want) to the location we just
         // popped. For the moment it unsafely exists at both the head and last
         // positions
-        let first_slice = view(*v, 0, 1);
-        let last_slice = mut_view(*v, next_ln, ln);
-        raw::copy_memory(last_slice, first_slice, 1);
+        {
+            let first_slice = view(*v, 0, 1);
+            let last_slice = view(*v, next_ln, ln);
+            raw::copy_memory(::cast::transmute(last_slice), first_slice, 1);
+        }
 
         // Memcopy everything to the left one element
-        let init_slice = mut_view(*v, 0, next_ln);
-        let tail_slice = view(*v, 1, ln);
-        raw::copy_memory(init_slice, tail_slice, next_ln);
+        {
+            let init_slice = view(*v, 0, next_ln);
+            let tail_slice = view(*v, 1, ln);
+            raw::copy_memory(::cast::transmute(init_slice),
+                             tail_slice,
+                             next_ln);
+        }
 
         // Set the new length. Now the vector is back to normal
         raw::set_len(&mut *v, next_ln);
diff --git a/src/librustc/middle/borrowck/check_loans.rs b/src/librustc/middle/borrowck/check_loans.rs
index c7ccf28755c..ff5854322f4 100644
--- a/src/librustc/middle/borrowck/check_loans.rs
+++ b/src/librustc/middle/borrowck/check_loans.rs
@@ -22,9 +22,9 @@ use core::prelude::*;
 use middle::borrowck::{Loan, bckerr, borrowck_ctxt, cmt, inherent_mutability};
 use middle::borrowck::{req_maps, save_and_restore};
 use middle::mem_categorization::{cat_arg, cat_binding, cat_comp, cat_deref};
-use middle::mem_categorization::{cat_local, cat_rvalue, cat_special, gc_ptr};
-use middle::mem_categorization::{loan_path, lp_arg, lp_comp, lp_deref};
-use middle::mem_categorization::{lp_local};
+use middle::mem_categorization::{cat_local, cat_rvalue, cat_self};
+use middle::mem_categorization::{cat_special, gc_ptr, loan_path, lp_arg};
+use middle::mem_categorization::{lp_comp, lp_deref, lp_local};
 use middle::ty::{CopyValue, MoveValue, ReadValue};
 use middle::ty;
 use util::ppaux::ty_to_str;
@@ -444,7 +444,7 @@ impl check_loan_ctxt {
             self.check_for_loan_conflicting_with_assignment(
                 at, ex, cmt, lp_base);
           }
-          lp_comp(*) | lp_local(*) | lp_arg(*) | lp_deref(*) => ()
+          lp_comp(*) | lp_self | lp_local(*) | lp_arg(*) | lp_deref(*) => ()
         }
     }
 
@@ -481,16 +481,13 @@ impl check_loan_ctxt {
 
         match cmt.cat {
           // Rvalues, locals, and arguments can be moved:
-          cat_rvalue | cat_local(_) | cat_arg(_) => {}
+          cat_rvalue | cat_local(_) | cat_arg(_) | cat_self(_) => {}
 
           // We allow moving out of static items because the old code
           // did.  This seems consistent with permitting moves out of
           // rvalues, I guess.
           cat_special(sk_static_item) => {}
 
-          // We allow moving out of explicit self only.
-          cat_special(sk_self) => {}
-
           cat_deref(_, _, unsafe_ptr) => {}
 
           // Nothing else.
diff --git a/src/librustc/middle/borrowck/gather_loans.rs b/src/librustc/middle/borrowck/gather_loans.rs
index aa7f3b71a50..967b1681b1b 100644
--- a/src/librustc/middle/borrowck/gather_loans.rs
+++ b/src/librustc/middle/borrowck/gather_loans.rs
@@ -480,13 +480,44 @@ impl gather_loan_ctxt {
             return;
         }
 
+        // Normally we wouldn't allow `re_free` here. However, in this case
+        // it should be sound. Below is nmatsakis' reasoning:
+        //
+        // Perhaps [this permits] a function kind of like this one here, which
+        // consumes one mut pointer and returns a narrower one:
+        //
+        //     struct Foo { f: int }
+        //     fn foo(p: &v/mut Foo) -> &v/mut int { &mut p.f }
+        //
+        // I think this should work fine but there is more subtlety to it than
+        // I at first imagined. Unfortunately it's a very important use case,
+        // I think, so it really ought to work. The changes you [pcwalton]
+        // made to permit re_free() do permit this case, I think, but I'm not
+        // sure what else they permit. I have to think that over a bit.
+        //
+        // Ordinarily, a loan with scope re_free wouldn't make sense, because
+        // you couldn't enforce it. But in this case, your function signature
+        // informs the caller that you demand exclusive access to p and its
+        // contents for the lifetime v. Since borrowed pointers are
+        // non-copyable, they must have (a) made a borrow which will enforce
+        // those conditions and then (b) given you the resulting pointer.
+        // Therefore, they should be respecting the loan. So it actually seems
+        // that it's ok in this case to have a loan with re_free, so long as
+        // the scope of the loan is no greater than the region pointer on
+        // which it is based. Neat but not something I had previously
+        // considered all the way through. (Note that we already rely on
+        // similar reasoning to permit you to return borrowed pointers into
+        // immutable structures, this is just the converse I suppose)
+
         let scope_id = match scope_r {
-            ty::re_scope(scope_id) => scope_id,
+            ty::re_scope(scope_id) | ty::re_free(scope_id, _) => scope_id,
             _ => {
                 self.bccx.tcx.sess.span_bug(
                     cmt.span,
-                    fmt!("loans required but scope is scope_region is %s",
-                         region_to_str(self.tcx(), scope_r)));
+                    fmt!("loans required but scope is scope_region is %s \
+                          (%?)",
+                         region_to_str(self.tcx(), scope_r),
+                         scope_r));
             }
         };
 
diff --git a/src/librustc/middle/borrowck/loan.rs b/src/librustc/middle/borrowck/loan.rs
index a9bbcbb9cc2..1b274a5241c 100644
--- a/src/librustc/middle/borrowck/loan.rs
+++ b/src/librustc/middle/borrowck/loan.rs
@@ -17,7 +17,7 @@ use core::prelude::*;
 use middle::borrowck::{Loan, bckres, borrowck_ctxt, cmt, err_mutbl};
 use middle::borrowck::{err_out_of_scope};
 use middle::mem_categorization::{cat_arg, cat_binding, cat_discr, cat_comp};
-use middle::mem_categorization::{cat_deref, cat_discr, cat_local};
+use middle::mem_categorization::{cat_deref, cat_discr, cat_local, cat_self};
 use middle::mem_categorization::{cat_special, cat_stack_upvar, comp_field};
 use middle::mem_categorization::{comp_index, comp_variant, gc_ptr};
 use middle::mem_categorization::{region_ptr};
@@ -121,7 +121,7 @@ impl LoanContext {
                 cmt.span,
                 ~"rvalue with a non-none lp");
           }
-          cat_local(local_id) | cat_arg(local_id) => {
+          cat_local(local_id) | cat_arg(local_id) | cat_self(local_id) => {
             let local_scope_id = self.tcx().region_map.get(local_id);
             self.issue_loan(cmt, ty::re_scope(local_scope_id), req_mutbl)
           }
@@ -162,9 +162,18 @@ impl LoanContext {
             // then the memory is freed.
             self.loan_unstable_deref(cmt, cmt_base, req_mutbl)
           }
+          cat_deref(cmt_base, _, region_ptr(ast::m_mutbl, region)) => {
+            // Mutable data can be loaned out as immutable or const. We must
+            // loan out the base as well as the main memory. For example,
+            // if someone borrows `*b`, we want to borrow `b` as immutable
+            // as well.
+            do self.loan(cmt_base, m_imm).chain |_| {
+                self.issue_loan(cmt, region, m_const)
+            }
+          }
           cat_deref(_, _, unsafe_ptr) |
           cat_deref(_, _, gc_ptr(_)) |
-          cat_deref(_, _, region_ptr(_)) => {
+          cat_deref(_, _, region_ptr(_, _)) => {
             // Aliased data is simply not lendable.
             self.bccx.tcx.sess.span_bug(
                 cmt.span,
diff --git a/src/librustc/middle/borrowck/preserve.rs b/src/librustc/middle/borrowck/preserve.rs
index 2cb188110fe..4f7711c74a6 100644
--- a/src/librustc/middle/borrowck/preserve.rs
+++ b/src/librustc/middle/borrowck/preserve.rs
@@ -20,7 +20,7 @@ use middle::borrowck::{cmt, err_mut_uniq, err_mut_variant};
 use middle::borrowck::{err_out_of_root_scope, err_out_of_scope};
 use middle::borrowck::{err_root_not_permitted};
 use middle::mem_categorization::{cat_arg, cat_binding, cat_comp, cat_deref};
-use middle::mem_categorization::{cat_discr, cat_local, cat_special};
+use middle::mem_categorization::{cat_discr, cat_local, cat_self, cat_special};
 use middle::mem_categorization::{cat_stack_upvar, comp_field, comp_index};
 use middle::mem_categorization::{comp_variant, gc_ptr, region_ptr};
 use middle::ty;
@@ -90,7 +90,6 @@ priv impl &preserve_ctxt {
         let _i = indenter();
 
         match cmt.cat {
-          cat_special(sk_self) |
           cat_special(sk_implicit_self) |
           cat_special(sk_heap_upvar) => {
             self.compare_scope(cmt, ty::re_scope(self.item_ub))
@@ -148,6 +147,10 @@ priv impl &preserve_ctxt {
             let local_scope_id = self.tcx().region_map.get(local_id);
             self.compare_scope(cmt, ty::re_scope(local_scope_id))
           }
+          cat_self(local_id) => {
+            let local_scope_id = self.tcx().region_map.get(local_id);
+            self.compare_scope(cmt, ty::re_scope(local_scope_id))
+          }
           cat_comp(cmt_base, comp_field(*)) |
           cat_comp(cmt_base, comp_index(*)) |
           cat_comp(cmt_base, comp_tuple) |
@@ -171,7 +174,7 @@ priv impl &preserve_ctxt {
             // freed, so require imm.
             self.require_imm(cmt, cmt_base, err_mut_uniq)
           }
-          cat_deref(_, _, region_ptr(region)) => {
+          cat_deref(_, _, region_ptr(_, region)) => {
             // References are always "stable" for lifetime `region` by
             // induction (when the reference of type &MT was created,
             // the memory must have been stable).
diff --git a/src/librustc/middle/mem_categorization.rs b/src/librustc/middle/mem_categorization.rs
index 2669a2ea6cc..909d1f95fde 100644
--- a/src/librustc/middle/mem_categorization.rs
+++ b/src/librustc/middle/mem_categorization.rs
@@ -73,6 +73,7 @@ enum categorization {
     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())
+    cat_self(ast::node_id),         // explicit `self`
 }
 
 // different kinds of pointers:
@@ -80,7 +81,7 @@ enum categorization {
 pub enum ptr_kind {
     uniq_ptr,
     gc_ptr(ast::mutability),
-    region_ptr(ty::Region),
+    region_ptr(ast::mutability, ty::Region),
     unsafe_ptr
 }
 
@@ -103,7 +104,6 @@ pub enum comp_kind {
 enum special_kind {
     sk_method,
     sk_static_item,
-    sk_self,
     sk_implicit_self,   // old by-reference `self`
     sk_heap_upvar
 }
@@ -135,45 +135,15 @@ impl cmt_ : cmp::Eq {
 // 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.
+#[deriving_eq]
 pub enum loan_path {
     lp_local(ast::node_id),
     lp_arg(ast::node_id),
+    lp_self,
     lp_deref(@loan_path, ptr_kind),
     lp_comp(@loan_path, comp_kind)
 }
 
-impl loan_path : cmp::Eq {
-    pure fn eq(&self, other: &loan_path) -> bool {
-        match (*self) {
-            lp_local(e0a) => {
-                match (*other) {
-                    lp_local(e0b) => e0a == e0b,
-                    _ => false
-                }
-            }
-            lp_arg(e0a) => {
-                match (*other) {
-                    lp_arg(e0b) => e0a == e0b,
-                    _ => false
-                }
-            }
-            lp_deref(e0a, e1a) => {
-                match (*other) {
-                    lp_deref(e0b, e1b) => e0a == e0b && e1a == e1b,
-                    _ => false
-                }
-            }
-            lp_comp(e0a, e1a) => {
-                match (*other) {
-                    lp_comp(e0b, e1b) => e0a == e0b && e1a == e1b,
-                    _ => false
-                }
-            }
-        }
-    }
-    pure fn ne(&self, other: &loan_path) -> bool { !(*self).eq(other) }
-}
-
 // 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)}
@@ -193,14 +163,17 @@ fn opt_deref_kind(t: ty::t) -> Option<deref_kind> {
         Some(deref_ptr(uniq_ptr))
       }
 
-      ty::ty_rptr(r, _) |
-      ty::ty_evec(_, ty::vstore_slice(r)) |
+      ty::ty_rptr(r, mt) |
+      ty::ty_evec(mt, ty::vstore_slice(r)) => {
+        Some(deref_ptr(region_ptr(mt.mutbl, r)))
+      }
+
       ty::ty_estr(ty::vstore_slice(r)) => {
-        Some(deref_ptr(region_ptr(r)))
+        Some(deref_ptr(region_ptr(ast::m_imm, r)))
       }
 
       ty::ty_fn(ref f) if (*f).meta.proto == ast::ProtoBorrowed => {
-        Some(deref_ptr(region_ptr((*f).meta.region)))
+        Some(deref_ptr(region_ptr(ast::m_imm, (*f).meta.region)))
       }
 
       ty::ty_box(mt) |
@@ -481,15 +454,18 @@ impl &mem_categorization_ctxt {
               mutbl:m, ty:expr_ty}
           }
 
-          ast::def_self(_, is_implicit) => {
-            let special_kind = if is_implicit {
-                sk_implicit_self
+          ast::def_self(self_id, is_implicit) => {
+            let cat, loan_path;
+            if is_implicit {
+                cat = cat_special(sk_implicit_self);
+                loan_path = None;
             } else {
-                sk_self
+                cat = cat_self(self_id);
+                loan_path = Some(@lp_self);
             };
 
             @{id:id, span:span,
-              cat:cat_special(special_kind), lp:None,
+              cat:cat, lp:loan_path,
               mutbl:m_imm, ty:expr_ty}
           }
 
@@ -626,13 +602,16 @@ impl &mem_categorization_ctxt {
             deref_ptr(ptr) => {
                 let lp = do base_cmt.lp.chain_ref |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.
+                    // loan out deref'd uniq ptrs or mut ptrs as the data
+                    // they are the only way to mutably reach the data they
+                    // point at. Other ptr types admit mutable aliases and
+                    // are therefore not loanable.
                     match ptr {
-                        uniq_ptr => {Some(@lp_deref(*l, ptr))}
-                        gc_ptr(*) | region_ptr(_) | unsafe_ptr => {None}
+                        uniq_ptr => Some(@lp_deref(*l, ptr)),
+                        region_ptr(ast::m_mutbl, _) => {
+                            Some(@lp_deref(*l, ptr))
+                        }
+                        gc_ptr(*) | region_ptr(_, _) | unsafe_ptr => None
                     }
                 };
 
@@ -642,7 +621,7 @@ impl &mem_categorization_ctxt {
                     uniq_ptr => {
                         self.inherited_mutability(base_cmt.mutbl, mt.mutbl)
                     }
-                    gc_ptr(*) | region_ptr(_) | unsafe_ptr => {
+                    gc_ptr(*) | region_ptr(_, _) | unsafe_ptr => {
                         mt.mutbl
                     }
                 };
@@ -688,7 +667,7 @@ impl &mem_categorization_ctxt {
               uniq_ptr => {
                 self.inherited_mutability(base_cmt.mutbl, mt.mutbl)
               }
-              gc_ptr(_) | region_ptr(_) | unsafe_ptr => {
+              gc_ptr(_) | region_ptr(_, _) | unsafe_ptr => {
                 mt.mutbl
               }
             };
@@ -866,13 +845,13 @@ impl &mem_categorization_ctxt {
           cat_special(sk_method) => ~"method",
           cat_special(sk_static_item) => ~"static_item",
           cat_special(sk_implicit_self) => ~"implicit-self",
-          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_self(node_id) => fmt!("self(%d)", node_id),
           cat_deref(cmt, derefs, ptr) => {
             fmt!("%s->(%s, %u)", self.cat_to_repr(cmt.cat),
                  self.ptr_sigil(ptr), derefs)
@@ -896,7 +875,7 @@ impl &mem_categorization_ctxt {
         match ptr {
           uniq_ptr => ~"~",
           gc_ptr(_) => ~"@",
-          region_ptr(_) => ~"&",
+          region_ptr(_, _) => ~"&",
           unsafe_ptr => ~"*"
         }
     }
@@ -919,6 +898,7 @@ impl &mem_categorization_ctxt {
           lp_arg(node_id) => {
             fmt!("arg(%d)", node_id)
           }
+          lp_self => ~"self",
           lp_deref(lp, ptr) => {
             fmt!("%s->(%s)", self.lp_to_str(lp),
                  self.ptr_sigil(ptr))
@@ -945,13 +925,13 @@ impl &mem_categorization_ctxt {
           cat_special(sk_method) => ~"method",
           cat_special(sk_static_item) => ~"static item",
           cat_special(sk_implicit_self) => ~"self reference",
-          cat_special(sk_self) => ~"self value",
           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_self(_) => ~"self value",
           cat_arg(_) => ~"argument",
           cat_deref(_, _, pk) => fmt!("dereference of %s %s pointer",
                                       mut_str, self.ptr_sigil(pk)),
@@ -1045,7 +1025,8 @@ impl categorization {
             cat_special(*) |
             cat_local(*) |
             cat_binding(*) |
-            cat_arg(*) => {
+            cat_arg(*) |
+            cat_self(*) => {
                 false
             }
         }
diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index 592a1318477..dd355f6df70 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -336,6 +336,14 @@ fn resolve_fn(fk: visit::fn_kind, decl: ast::fn_decl, body: ast::blk,
         }
     };
 
+    // Record the ID of `self`.
+    match fk {
+        visit::fk_method(_, _, method) => {
+            cx.region_map.insert(method.self_id, body.node.id);
+        }
+        _ => {}
+    }
+
     debug!("visiting fn with body %d. cx.parent: %? \
             fn_cx.parent: %?",
            body.node.id, cx.parent, fn_cx.parent);
diff --git a/src/libstd/arc.rs b/src/libstd/arc.rs
index 4d1a8af0b1d..536f43d648c 100644
--- a/src/libstd/arc.rs
+++ b/src/libstd/arc.rs
@@ -241,19 +241,24 @@ fn check_poison(is_mutex: bool, failed: bool) {
 
 #[doc(hidden)]
 struct PoisonOnFail {
-    failed: &mut bool,
+    failed: *mut bool,
 }
 
 impl PoisonOnFail : Drop {
     fn finalize(&self) {
-        /* assert !*self.failed; -- might be false in case of cond.wait() */
-        if task::failing() { *self.failed = true; }
+        unsafe {
+            /* assert !*self.failed;
+               -- might be false in case of cond.wait() */
+            if task::failing() {
+                *self.failed = true;
+            }
+        }
     }
 }
 
-fn PoisonOnFail(failed: &r/mut bool) -> PoisonOnFail/&r {
+fn PoisonOnFail(failed: &r/mut bool) -> PoisonOnFail {
     PoisonOnFail {
-        failed: failed
+        failed: ptr::to_mut_unsafe_ptr(failed)
     }
 }
 
@@ -415,7 +420,7 @@ pub fn unwrap_rw_arc<T: Const Owned>(arc: RWARC<T>) -> T {
 // field is never overwritten; only 'failed' and 'data'.
 #[doc(hidden)]
 fn borrow_rwlock<T: Const Owned>(state: &r/mut RWARCInner<T>) -> &r/RWlock {
-    unsafe { cast::transmute_immut(&mut state.lock) }
+    unsafe { cast::transmute(&mut state.lock) }
 }
 
 // FIXME (#3154) ice with struct/&<T> prevents these from being structs.
@@ -442,12 +447,14 @@ impl<T: Const Owned> &RWWriteMode<T> {
         match *self {
             RWWriteMode((ref data, ref token, ref poison)) => {
                 do token.write_cond |cond| {
-                    let cvar = Condvar {
-                        is_mutex: false,
-                        failed: &mut *poison.failed,
-                        cond: cond
-                    };
-                    blk(&mut **data, &cvar)
+                    unsafe {
+                        let cvar = Condvar {
+                            is_mutex: false,
+                            failed: &mut *poison.failed,
+                            cond: cond
+                        };
+                        blk(&mut **data, &cvar)
+                    }
                 }
             }
         }
diff --git a/src/libstd/priority_queue.rs b/src/libstd/priority_queue.rs
index a348026f072..01b62797a8d 100644
--- a/src/libstd/priority_queue.rs
+++ b/src/libstd/priority_queue.rs
@@ -19,6 +19,7 @@ use core::vec;
 #[abi = "rust-intrinsic"]
 extern "C" mod rusti {
     fn move_val_init<T>(dst: &mut T, -src: T);
+    fn init<T>() -> T;
 }
 
 pub struct PriorityQueue <T: Ord>{
@@ -136,8 +137,9 @@ impl <T: Ord> PriorityQueue<T> {
             while pos > start {
                 let parent = (pos - 1) >> 1;
                 if new > self.data[parent] {
-                    rusti::move_val_init(&mut self.data[pos],
-                                         move *addr_of(&self.data[parent]));
+                    let mut x = rusti::init();
+                    x <-> self.data[parent];
+                    rusti::move_val_init(&mut self.data[pos], move x);
                     pos = parent;
                     loop
                 }
@@ -159,8 +161,9 @@ impl <T: Ord> PriorityQueue<T> {
                 if right < end && !(self.data[child] > self.data[right]) {
                     child = right;
                 }
-                rusti::move_val_init(&mut self.data[pos],
-                                     move *addr_of(&self.data[child]));
+                let mut x = rusti::init();
+                x <-> self.data[child];
+                rusti::move_val_init(&mut self.data[pos], move x);
                 pos = child;
                 child = 2 * pos + 1;
             }
diff --git a/src/libstd/treemap.rs b/src/libstd/treemap.rs
index 95397254171..36d919494f1 100644
--- a/src/libstd/treemap.rs
+++ b/src/libstd/treemap.rs
@@ -55,8 +55,10 @@ impl <K: Eq Ord, V: Eq> TreeMap<K, V>: Eq {
                 unsafe { // unsafe as a purity workaround
                     // ICE: x.next() != y.next()
 
-                    let (x1, x2) = x.next().unwrap();
-                    let (y1, y2) = y.next().unwrap();
+                    x = x.next();
+                    y = y.next();
+                    let (x1, x2) = x.get().unwrap();
+                    let (y1, y2) = y.get().unwrap();
 
                     if x1 != y1 || x2 != y2 {
                         return false
@@ -160,35 +162,46 @@ impl <K: Ord, V> TreeMap<K, V> {
     /// Get a lazy iterator over the key-value pairs in the map.
     /// Requires that it be frozen (immutable).
     pure fn iter(&self) -> TreeMapIterator/&self<K, V> {
-        TreeMapIterator{stack: ~[], node: &self.root}
+        TreeMapIterator{stack: ~[], node: &self.root, current: None}
     }
 }
 
 /// Lazy forward iterator over a map
 pub struct TreeMapIterator<K: Ord, V> {
     priv stack: ~[&~TreeNode<K, V>],
-    priv node: &Option<~TreeNode<K, V>>
+    priv node: &Option<~TreeNode<K, V>>,
+    priv current: Option<&~TreeNode<K, V>>
 }
 
 impl <K: Ord, V> TreeMapIterator<K, V> {
-    /// Advance the iterator to the next node (in order) and return a
-    /// tuple with a reference to the key and value. If there are no
-    /// more nodes, return `None`.
-    fn next(&mut self) -> Option<(&self/K, &self/V)> {
-        while !self.stack.is_empty() || self.node.is_some() {
-            match *self.node {
+    // Returns the current node, or None if this iterator is at the end.
+    fn get(&const self) -> Option<(&self/K, &self/V)> {
+        match self.current {
+            Some(res) => Some((&res.key, &res.value)),
+            None => None
+        }
+    }
+
+    /// Advance the iterator to the next node (in order). If this iterator
+    /// is finished, does nothing.
+    fn next(self) -> TreeMapIterator/&self<K, V> {
+        let mut this = self;
+        while !this.stack.is_empty() || this.node.is_some() {
+            match *this.node {
               Some(ref x) => {
-                self.stack.push(x);
-                self.node = &x.left;
+                this.stack.push(x);
+                this.node = &x.left;
               }
               None => {
-                let res = self.stack.pop();
-                self.node = &res.right;
-                return Some((&res.key, &res.value));
+                let res = this.stack.pop();
+                this.node = &res.right;
+                this.current = Some(res);
+                return this;
               }
             }
         }
-        None
+        this.current = None;
+        return this;
     }
 }
 
@@ -256,15 +269,19 @@ impl <T: Ord> TreeSet<T> {
         let mut x = self.iter();
         let mut y = other.iter();
         unsafe { // purity workaround
-            let mut a = x.next();
-            let mut b = y.next();
+            x = x.next();
+            y = y.next();
+            let mut a = x.get();
+            let mut b = y.get();
             while a.is_some() && b.is_some() {
                 let a1 = a.unwrap();
                 let b1 = b.unwrap();
                 if a1 < b1 {
-                    a = x.next();
+                    x = x.next();
+                    a = x.get();
                 } else if b1 < a1 {
-                    b = y.next();
+                    y = y.next();
+                    b = y.get();
                 } else {
                     return false;
                 }
@@ -283,8 +300,10 @@ impl <T: Ord> TreeSet<T> {
         let mut x = self.iter();
         let mut y = other.iter();
         unsafe { // purity workaround
-            let mut a = x.next();
-            let mut b = y.next();
+            x = x.next();
+            y = y.next();
+            let mut a = x.get();
+            let mut b = y.get();
             while b.is_some() {
                 if a.is_none() {
                     return false
@@ -298,9 +317,11 @@ impl <T: Ord> TreeSet<T> {
                 }
 
                 if !(a1 < b1) {
-                    b = y.next();
+                    y = y.next();
+                    b = y.get();
                 }
-                a = x.next();
+                x = x.next();
+                a = x.get();
             }
         }
         true
@@ -312,13 +333,15 @@ impl <T: Ord> TreeSet<T> {
         let mut y = other.iter();
 
         unsafe { // purity workaround
-            let mut a = x.next();
-            let mut b = y.next();
+            x = x.next();
+            y = y.next();
+            let mut a = x.get();
+            let mut b = y.get();
 
             while a.is_some() {
                 if b.is_none() {
                     return do a.while_some() |a1| {
-                        if f(a1) { x.next() } else { None }
+                        if f(a1) { x = x.next(); x.get() } else { None }
                     }
                 }
 
@@ -327,10 +350,12 @@ impl <T: Ord> TreeSet<T> {
 
                 if a1 < b1 {
                     if !f(a1) { return }
-                    a = x.next();
+                    x = x.next();
+                    a = x.get();
                 } else {
-                    if !(b1 < a1) { a = x.next() }
-                    b = y.next();
+                    if !(b1 < a1) { x = x.next(); a = x.get() }
+                    y = y.next();
+                    b = y.get();
                 }
             }
         }
@@ -343,13 +368,15 @@ impl <T: Ord> TreeSet<T> {
         let mut y = other.iter();
 
         unsafe { // purity workaround
-            let mut a = x.next();
-            let mut b = y.next();
+            x = x.next();
+            y = y.next();
+            let mut a = x.get();
+            let mut b = y.get();
 
             while a.is_some() {
                 if b.is_none() {
                     return do a.while_some() |a1| {
-                        if f(a1) { x.next() } else { None }
+                        if f(a1) { x.next(); x.get() } else { None }
                     }
                 }
 
@@ -358,18 +385,21 @@ impl <T: Ord> TreeSet<T> {
 
                 if a1 < b1 {
                     if !f(a1) { return }
-                    a = x.next();
+                    x = x.next();
+                    a = x.get();
                 } else {
                     if b1 < a1 {
                         if !f(b1) { return }
                     } else {
-                        a = x.next();
+                        x = x.next();
+                        a = x.get();
                     }
-                    b = y.next();
+                    y = y.next();
+                    b = y.get();
                 }
             }
             do b.while_some |b1| {
-                if f(b1) { y.next() } else { None }
+                if f(b1) { y = y.next(); y.get() } else { None }
             }
         }
     }
@@ -380,19 +410,23 @@ impl <T: Ord> TreeSet<T> {
         let mut y = other.iter();
 
         unsafe { // purity workaround
-            let mut a = x.next();
-            let mut b = y.next();
+            x = x.next();
+            y = y.next();
+            let mut a = x.get();
+            let mut b = y.get();
 
             while a.is_some() && b.is_some() {
                 let a1 = a.unwrap();
                 let b1 = b.unwrap();
                 if a1 < b1 {
-                    a = x.next();
+                    x = x.next();
+                    a = x.get();
                 } else {
                     if !(b1 < a1) {
                         if !f(a1) { return }
                     }
-                    b = y.next();
+                    y = y.next();
+                    b = y.get();
                 }
             }
         }
@@ -404,13 +438,15 @@ impl <T: Ord> TreeSet<T> {
         let mut y = other.iter();
 
         unsafe { // purity workaround
-            let mut a = x.next();
-            let mut b = y.next();
+            x = x.next();
+            y = y.next();
+            let mut a = x.get();
+            let mut b = y.get();
 
             while a.is_some() {
                 if b.is_none() {
                     return do a.while_some() |a1| {
-                        if f(a1) { x.next() } else { None }
+                        if f(a1) { x = x.next(); x.get() } else { None }
                     }
                 }
 
@@ -419,13 +455,16 @@ impl <T: Ord> TreeSet<T> {
 
                 if b1 < a1 {
                     if !f(b1) { return }
-                    b = y.next();
+                    y = y.next();
+                    b = y.get();
                 } else {
                     if !f(a1) { return }
                     if !(a1 < b1) {
-                        b = y.next()
+                        y = y.next();
+                        b = y.get()
                     }
-                    a = x.next();
+                    x = x.next();
+                    a = x.get();
                 }
             }
         }
@@ -438,11 +477,18 @@ pub struct TreeSetIterator<T: Ord> {
 }
 
 impl <T: Ord> TreeSetIterator<T> {
-    /// Advance the iterator to the next node (in order) and return a
-    /// tuple with a reference to the value. If there are no more nodes,
-    /// return `None`.
-    fn next(&mut self) -> Option<&self/T> {
-        self.iter.next().map_consume(|(x, _)| x)
+    /// Returns the current node, or None if this iterator is at the end.
+    fn get(&const self) -> Option<&self/T> {
+        match self.iter.get() {
+            None => None,
+            Some((k, _)) => Some(k)
+        }
+    }
+
+    /// Advance the iterator to the next node (in order). If this iterator is
+    /// finished, does nothing.
+    fn next(self) -> TreeSetIterator/&self<T> {
+        TreeSetIterator { iter: self.iter.next() }
     }
 }
 
@@ -854,17 +900,23 @@ mod test_treemap {
         //assert iter.next() == Some((&x1, &y1));
         //assert iter.next().eq(&Some((&x1, &y1)));
 
-        assert iter.next().unwrap() == (&x1, &y1);
-        assert iter.next().unwrap() == (&x2, &y2);
-        assert iter.next().unwrap() == (&x3, &y3);
-        assert iter.next().unwrap() == (&x4, &y4);
-        assert iter.next().unwrap() == (&x5, &y5);
+        iter = iter.next();
+        assert iter.get().unwrap() == (&x1, &y1);
+        iter = iter.next();
+        assert iter.get().unwrap() == (&x2, &y2);
+        iter = iter.next();
+        assert iter.get().unwrap() == (&x3, &y3);
+        iter = iter.next();
+        assert iter.get().unwrap() == (&x4, &y4);
+        iter = iter.next();
+        assert iter.get().unwrap() == (&x5, &y5);
 
         // ICE:
         //assert iter.next() == None;
         //assert iter.next().eq(&None);
 
-        assert iter.next().is_none();
+        iter = iter.next();
+        assert iter.get().is_none();
     }
 }
 
diff --git a/src/test/compile-fail/borrowck-autoref-3261.rs b/src/test/compile-fail/borrowck-autoref-3261.rs
index 457cdd23447..0aec458aef4 100644
--- a/src/test/compile-fail/borrowck-autoref-3261.rs
+++ b/src/test/compile-fail/borrowck-autoref-3261.rs
@@ -20,7 +20,7 @@ fn main() {
     do (&mut x).with |opt| {  //~ ERROR illegal borrow
         match opt {
             &Right(ref f) => {
-                x = X(Left((0,0)));
+                x = X(Left((0,0))); //~ ERROR assigning to captured outer mutable variable
                 (*f)()
             },
             _ => fail
diff --git a/src/test/compile-fail/borrowck-call-method-from-mut-aliasable.rs b/src/test/compile-fail/borrowck-call-method-from-mut-aliasable.rs
index 6bbe7adec3b..4e0cc76bf75 100644
--- a/src/test/compile-fail/borrowck-call-method-from-mut-aliasable.rs
+++ b/src/test/compile-fail/borrowck-call-method-from-mut-aliasable.rs
@@ -19,7 +19,7 @@ impl Foo {
 }
 
 fn a(x: &mut Foo) {
-    x.f(); //~ ERROR illegal borrow unless pure
+    x.f();
     x.g();
     x.h();
 }
diff --git a/src/test/compile-fail/borrowck-imm-field-mut-base.rs b/src/test/compile-fail/borrowck-imm-field-mut-base.rs
index 48bd4ef75d6..5c3fe229602 100644
--- a/src/test/compile-fail/borrowck-imm-field-mut-base.rs
+++ b/src/test/compile-fail/borrowck-imm-field-mut-base.rs
@@ -22,8 +22,9 @@ fn main() {
     let q = &mut b.foo; //~ ERROR loan of mutable field as mutable conflicts with prior loan
     //~^ ERROR loan of mutable local variable as mutable conflicts with prior loan
     let r = &mut b; //~ ERROR loan of mutable local variable as mutable conflicts with prior loan
+    //~^ ERROR loan of mutable local variable as mutable conflicts with prior loan
     io::println(fmt!("*p = %u", *p));
     q.x += 1;
     r.foo.x += 1;
     io::println(fmt!("*p = %u", *p));
-}
\ No newline at end of file
+}
diff --git a/src/test/compile-fail/borrowck-imm-ref-to-mut-rec-field-issue-3162-c.rs b/src/test/compile-fail/borrowck-imm-ref-to-mut-rec-field-issue-3162-c.rs
index 618e094da16..88db5f54341 100644
--- a/src/test/compile-fail/borrowck-imm-ref-to-mut-rec-field-issue-3162-c.rs
+++ b/src/test/compile-fail/borrowck-imm-ref-to-mut-rec-field-issue-3162-c.rs
@@ -10,9 +10,9 @@
 
 fn main() {
     let mut _a = 3;
-    let _b = &mut _a;
+    let _b = &mut _a; //~ NOTE loan of mutable local variable granted here
     {
-        let _c = &*_b; //~ ERROR illegal borrow unless pure
-        _a = 4; //~ NOTE impure due to assigning to mutable local variable
+        let _c = &*_b;
+        _a = 4; //~ ERROR assigning to mutable local variable prohibited
     }
 }
diff --git a/src/test/compile-fail/borrowck-uniq-via-ref.rs b/src/test/compile-fail/borrowck-uniq-via-ref.rs
index 046ae7ea6d6..48d39c39e5a 100644
--- a/src/test/compile-fail/borrowck-uniq-via-ref.rs
+++ b/src/test/compile-fail/borrowck-uniq-via-ref.rs
@@ -11,7 +11,7 @@
 fn borrow(_v: &int) {}
 
 fn box_mut(v: &mut ~int) {
-    borrow(*v); //~ ERROR illegal borrow unless pure
+    borrow(*v); // OK: &mut -> &imm
 }
 
 fn box_rec_mut(v: &{mut f: ~int}) {
@@ -19,11 +19,11 @@ fn box_rec_mut(v: &{mut f: ~int}) {
 }
 
 fn box_mut_rec(v: &mut {f: ~int}) {
-    borrow(v.f); //~ ERROR illegal borrow unless pure
+    borrow(v.f); // OK: &mut -> &imm
 }
 
 fn box_mut_recs(v: &mut {f: {g: {h: ~int}}}) {
-    borrow(v.f.g.h); //~ ERROR illegal borrow unless pure
+    borrow(v.f.g.h); // OK: &mut -> &imm
 }
 
 fn box_imm(v: &~int) {
diff --git a/src/test/compile-fail/borrowck-wg-borrow-mut-to-imm-fail-2.rs b/src/test/compile-fail/borrowck-wg-borrow-mut-to-imm-fail-2.rs
new file mode 100644
index 00000000000..e47ad721b0d
--- /dev/null
+++ b/src/test/compile-fail/borrowck-wg-borrow-mut-to-imm-fail-2.rs
@@ -0,0 +1,6 @@
+fn main() {
+    let mut b = ~3;
+    let _x = &mut *b;   //~ NOTE prior loan as mutable granted here
+    let _y = &mut *b;   //~ ERROR loan of dereference of mutable ~ pointer as mutable conflicts with prior loan
+}
+
diff --git a/src/test/compile-fail/borrowck-wg-borrow-mut-to-imm-fail-3.rs b/src/test/compile-fail/borrowck-wg-borrow-mut-to-imm-fail-3.rs
new file mode 100644
index 00000000000..015f368ecb0
--- /dev/null
+++ b/src/test/compile-fail/borrowck-wg-borrow-mut-to-imm-fail-3.rs
@@ -0,0 +1,8 @@
+fn main() {
+    let mut a = ~3;
+    let mut b = &mut a; //~ NOTE loan of mutable local variable granted here
+    let _c = &mut *b;
+    let mut d = /*move*/ a; //~ ERROR moving out of mutable local variable prohibited due to outstanding loan
+    *d += 1;
+}
+
diff --git a/src/test/compile-fail/borrowck-wg-borrow-mut-to-imm-fail.rs b/src/test/compile-fail/borrowck-wg-borrow-mut-to-imm-fail.rs
new file mode 100644
index 00000000000..36d32fddda1
--- /dev/null
+++ b/src/test/compile-fail/borrowck-wg-borrow-mut-to-imm-fail.rs
@@ -0,0 +1,7 @@
+fn main() {
+    let mut b = ~3;
+    let _x = &mut *b;   //~ NOTE loan of mutable local variable granted here
+    let mut y = /*move*/ b; //~ ERROR moving out of mutable local variable prohibited
+    *y += 1;
+}
+
diff --git a/src/test/compile-fail/borrowck-wg-move-base-2.rs b/src/test/compile-fail/borrowck-wg-move-base-2.rs
new file mode 100644
index 00000000000..ba85616e63f
--- /dev/null
+++ b/src/test/compile-fail/borrowck-wg-move-base-2.rs
@@ -0,0 +1,11 @@
+fn foo(x: &mut int) {
+    let mut a = 3;
+    let mut _y = &mut *x;
+    let _z = &mut *_y;
+    _y = &mut a; //~ ERROR assigning to mutable local variable prohibited
+}
+
+fn main() {
+}
+
+
diff --git a/src/test/compile-fail/regions-escape-loop-via-vec.rs b/src/test/compile-fail/regions-escape-loop-via-vec.rs
index 7490448caf0..da5e3c2660e 100644
--- a/src/test/compile-fail/regions-escape-loop-via-vec.rs
+++ b/src/test/compile-fail/regions-escape-loop-via-vec.rs
@@ -15,7 +15,7 @@ fn broken() {
     while x < 10 {
         let mut z = x;
         _y.push(&mut z); //~ ERROR illegal borrow
-        x += 1;
+        x += 1; //~ ERROR assigning to mutable local variable prohibited due to outstanding loan
     }
 }
 
diff --git a/src/test/run-fail/write-guard-fail-2.rs b/src/test/run-fail/borrowck-wg-fail-2.rs
index 126135772ad..126135772ad 100644
--- a/src/test/run-fail/write-guard-fail-2.rs
+++ b/src/test/run-fail/borrowck-wg-fail-2.rs
diff --git a/src/test/run-fail/write-guard-fail-3.rs b/src/test/run-fail/borrowck-wg-fail-3.rs
index ad4c7942121..ad4c7942121 100644
--- a/src/test/run-fail/write-guard-fail-3.rs
+++ b/src/test/run-fail/borrowck-wg-fail-3.rs
diff --git a/src/test/run-fail/write-guard-fail.rs b/src/test/run-fail/borrowck-wg-fail.rs
index d393832c6e8..d393832c6e8 100644
--- a/src/test/run-fail/write-guard-fail.rs
+++ b/src/test/run-fail/borrowck-wg-fail.rs
diff --git a/src/test/compile-fail/borrowck-binding-mutbl.rs b/src/test/run-pass/borrowck-binding-mutbl.rs
index 5840dd001e8..04e00b5972c 100644
--- a/src/test/compile-fail/borrowck-binding-mutbl.rs
+++ b/src/test/run-pass/borrowck-binding-mutbl.rs
@@ -16,8 +16,7 @@ fn main() {
 
     match x {
       {f: ref mut v} => {
-        impure(*v); //~ ERROR illegal borrow unless pure
-        //~^ NOTE impure due to access to impure function
+        impure(*v);
       }
     }
 }
diff --git a/src/test/compile-fail/borrowck-lend-args.rs b/src/test/run-pass/borrowck-lend-args.rs
index a71fca1ec04..745f8f7f357 100644
--- a/src/test/compile-fail/borrowck-lend-args.rs
+++ b/src/test/run-pass/borrowck-lend-args.rs
@@ -15,8 +15,7 @@ fn borrow_from_arg_imm_ref(&&v: ~int) {
 }
 
 fn borrow_from_arg_mut_ref(v: &mut ~int) {
-    borrow(*v); //~ ERROR illegal borrow unless pure
-    //~^ NOTE impure due to access to impure function
+    borrow(*v);
 }
 
 fn borrow_from_arg_move(-v: ~int) {
diff --git a/src/test/run-pass/borrowck-wg-borrow-mut-to-imm-2.rs b/src/test/run-pass/borrowck-wg-borrow-mut-to-imm-2.rs
new file mode 100644
index 00000000000..12dc0c3a310
--- /dev/null
+++ b/src/test/run-pass/borrowck-wg-borrow-mut-to-imm-2.rs
@@ -0,0 +1,13 @@
+struct Cat;
+
+fn bar(_: &Cat) {
+}
+
+fn foo(cat: &mut Cat) {
+    bar(&*cat);
+}
+
+fn main() {
+    let mut mimi = ~Cat;
+    foo(mimi);
+}
diff --git a/src/test/run-pass/borrowck-wg-borrow-mut-to-imm-3.rs b/src/test/run-pass/borrowck-wg-borrow-mut-to-imm-3.rs
new file mode 100644
index 00000000000..66e29f3af3d
--- /dev/null
+++ b/src/test/run-pass/borrowck-wg-borrow-mut-to-imm-3.rs
@@ -0,0 +1,18 @@
+struct Wizard {
+    spells: ~[&static/str]
+}
+
+impl Wizard {
+    fn cast(&mut self) {
+        for self.spells.each |&spell| {
+            io::println(spell);
+        }
+    }
+}
+
+fn main() {
+    let mut harry = Wizard {
+        spells: ~[ "expelliarmus", "expecto patronum", "incendio" ]
+    };
+    harry.cast();
+}
diff --git a/src/test/run-pass/borrowck-wg-borrow-mut-to-imm.rs b/src/test/run-pass/borrowck-wg-borrow-mut-to-imm.rs
new file mode 100644
index 00000000000..36155a9d266
--- /dev/null
+++ b/src/test/run-pass/borrowck-wg-borrow-mut-to-imm.rs
@@ -0,0 +1,12 @@
+fn g(x: &Option<int>) {
+    io::println(x.get().to_str());
+}
+
+fn f(x: &mut Option<int>) {
+    g(&*x);
+}
+
+fn main() {
+    let mut x = ~Some(3);
+    f(x);
+}
diff --git a/src/test/run-pass/write-guard.rs b/src/test/run-pass/borrowck-wg-simple.rs
index bc370b20d15..bc370b20d15 100644
--- a/src/test/run-pass/write-guard.rs
+++ b/src/test/run-pass/borrowck-wg-simple.rs