auto merge of #5827 : nikomatsakis/rust/issue-5656-change-meaning-of-borrowed-self, r=pcwalton

See #5656 for details.

r? @pcwalton

66 files changed, 2463 insertions, 782 deletions

diff --git a/src/libcore/cmp.rs b/src/libcore/cmp.rs
index 2c2b7f40f31..b5a5ed7c9f4 100644
--- a/src/libcore/cmp.rs
+++ b/src/libcore/cmp.rs
@@ -116,6 +116,19 @@ totalord_impl!(i64)
 totalord_impl!(int)
 totalord_impl!(uint)
 
+pub fn cmp2<A:TotalOrd,B:TotalOrd>(
+    a1: &A, b1: &B,
+    a2: &A, b2: &B) -> Ordering
+{
+    //! Compares (a1, b1) against (a2, b2), where the a values are more significant.
+
+    match a1.cmp(a2) {
+        Less => Less,
+        Greater => Greater,
+        Equal => b1.cmp(b2)
+    }
+}
+
 /**
 Return `o1` if it is not `Equal`, otherwise `o2`. Simulates the
 lexical ordering on a type `(int, int)`.
@@ -209,6 +222,14 @@ mod test {
     }
 
     #[test]
+    fn test_cmp2() {
+        assert_eq!(cmp2(1, 2, 3, 4), Less);
+        assert_eq!(cmp2(3, 2, 3, 4), Less);
+        assert_eq!(cmp2(5, 2, 3, 4), Greater);
+        assert_eq!(cmp2(5, 5, 5, 4), Greater);
+    }
+
+    #[test]
     fn test_int_totaleq() {
         assert!(5.equals(&5));
         assert!(!2.equals(&17));
diff --git a/src/libcore/condition.rs b/src/libcore/condition.rs
index ed94f2ef2c4..dc6c80228dd 100644
--- a/src/libcore/condition.rs
+++ b/src/libcore/condition.rs
@@ -28,7 +28,7 @@ pub struct Condition<'self, T, U> {
 }
 
 pub impl<'self, T, U> Condition<'self, T, U> {
-    fn trap(&self, h: &'self fn(T) -> U) -> Trap<'self, T, U> {
+    fn trap(&'self self, h: &'self fn(T) -> U) -> Trap<'self, T, U> {
         unsafe {
             let p : *RustClosure = ::cast::transmute(&h);
             let prev = task::local_data::local_data_get(self.key);
diff --git a/src/libcore/container.rs b/src/libcore/container.rs
index a1836d16fd7..88c78aebfc5 100644
--- a/src/libcore/container.rs
+++ b/src/libcore/container.rs
@@ -25,6 +25,7 @@ pub trait Mutable: Container {
     fn clear(&mut self);
 }
 
+#[cfg(stage0)]
 pub trait Map<K, V>: Mutable {
     /// Return true if the map contains a value for the specified key
     fn contains_key(&self, key: &K) -> bool;
@@ -57,6 +58,41 @@ pub trait Map<K, V>: Mutable {
     fn remove(&mut self, key: &K) -> bool;
 }
 
+#[cfg(stage1)]
+#[cfg(stage2)]
+#[cfg(stage3)]
+pub trait Map<K, V>: Mutable {
+    /// Return true if the map contains a value for the specified key
+    fn contains_key(&self, key: &K) -> bool;
+
+    // Visits all keys and values
+    fn each<'a>(&'a self, f: &fn(&K, &'a V) -> bool);
+
+    /// Visit all keys
+    fn each_key(&self, f: &fn(&K) -> bool);
+
+    /// Visit all values
+    fn each_value<'a>(&'a self, f: &fn(&'a V) -> bool);
+
+    /// Iterate over the map and mutate the contained values
+    fn mutate_values(&mut self, f: &fn(&K, &mut V) -> bool);
+
+    /// Return a reference to the value corresponding to the key
+    fn find<'a>(&'a self, key: &K) -> Option<&'a V>;
+
+    /// Return a mutable reference to the value corresponding to the key
+    fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V>;
+
+    /// Insert a key-value pair into the map. An existing value for a
+    /// key is replaced by the new value. Return true if the key did
+    /// not already exist in the map.
+    fn insert(&mut self, key: K, value: V) -> bool;
+
+    /// Remove a key-value pair from the map. Return true if the key
+    /// was present in the map, otherwise false.
+    fn remove(&mut self, key: &K) -> bool;
+}
+
 pub trait Set<T>: Mutable {
     /// Return true if the set contains a value
     fn contains(&self, value: &T) -> bool;
diff --git a/src/libcore/hashmap.rs b/src/libcore/hashmap.rs
index d4af0ffe7fe..2869c198ca2 100644
--- a/src/libcore/hashmap.rs
+++ b/src/libcore/hashmap.rs
@@ -186,6 +186,7 @@ priv impl<K:Hash + IterBytes + Eq,V> HashMap<K, V> {
         }
     }
 
+    #[cfg(stage0)]
     #[inline(always)]
     fn value_for_bucket(&self, idx: uint) -> &'self V {
         match self.buckets[idx] {
@@ -194,6 +195,18 @@ priv impl<K:Hash + IterBytes + Eq,V> HashMap<K, V> {
         }
     }
 
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    #[inline(always)]
+    fn value_for_bucket<'a>(&'a self, idx: uint) -> &'a V {
+        match self.buckets[idx] {
+            Some(ref bkt) => &bkt.value,
+            None => fail!(~"HashMap::find: internal logic error"),
+        }
+    }
+
+    #[cfg(stage0)]
     #[inline(always)]
     fn mut_value_for_bucket(&mut self, idx: uint) -> &'self mut V {
         match self.buckets[idx] {
@@ -202,6 +215,17 @@ priv impl<K:Hash + IterBytes + Eq,V> HashMap<K, V> {
         }
     }
 
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    #[inline(always)]
+    fn mut_value_for_bucket<'a>(&'a mut self, idx: uint) -> &'a mut V {
+        match self.buckets[idx] {
+            Some(ref mut bkt) => &mut bkt.value,
+            None => unreachable()
+        }
+    }
+
     /// Inserts the key value pair into the buckets.
     /// Assumes that there will be a bucket.
     /// True if there was no previous entry with that key
@@ -307,6 +331,7 @@ impl<K:Hash + IterBytes + Eq,V> Map<K, V> for HashMap<K, V> {
     }
 
     /// Visit all key-value pairs
+    #[cfg(stage0)]
     fn each(&self, blk: &fn(&'self K, &'self V) -> bool) {
         for uint::range(0, self.buckets.len()) |i| {
             for self.buckets[i].each |bucket| {
@@ -317,19 +342,41 @@ impl<K:Hash + IterBytes + Eq,V> Map<K, V> for HashMap<K, V> {
         }
     }
 
+    /// Visit all key-value pairs
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn each<'a>(&'a self, blk: &fn(&'a K, &'a V) -> bool) {
+        for uint::range(0, self.buckets.len()) |i| {
+            for self.buckets[i].each |bucket| {
+                if !blk(&bucket.key, &bucket.value) {
+                    return;
+                }
+            }
+        }
+    }
+
     /// Visit all keys
     fn each_key(&self, blk: &fn(k: &K) -> bool) {
         self.each(|k, _| blk(k))
     }
 
     /// Visit all values
+    #[cfg(stage0)]
     fn each_value(&self, blk: &fn(v: &V) -> bool) {
         self.each(|_, v| blk(v))
     }
 
+    /// Visit all values
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn each_value<'a>(&'a self, blk: &fn(v: &'a V) -> bool) {
+        self.each(|_, v| blk(v))
+    }
+
     /// Iterate over the map and mutate the contained values
-    fn mutate_values(&mut self, blk: &fn(&'self K,
-                          &'self mut V) -> bool) {
+    fn mutate_values(&mut self, blk: &fn(&K, &mut V) -> bool) {
         for uint::range(0, self.buckets.len()) |i| {
             match self.buckets[i] {
               Some(Bucket{key: ref key, value: ref mut value, _}) => {
@@ -341,6 +388,7 @@ impl<K:Hash + IterBytes + Eq,V> Map<K, V> for HashMap<K, V> {
     }
 
     /// Return a reference to the value corresponding to the key
+    #[cfg(stage0)]
     fn find(&self, k: &K) -> Option<&'self V> {
         match self.bucket_for_key(k) {
             FoundEntry(idx) => Some(self.value_for_bucket(idx)),
@@ -348,7 +396,19 @@ impl<K:Hash + IterBytes + Eq,V> Map<K, V> for HashMap<K, V> {
         }
     }
 
+    /// Return a reference to the value corresponding to the key
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn find<'a>(&'a self, k: &K) -> Option<&'a V> {
+        match self.bucket_for_key(k) {
+            FoundEntry(idx) => Some(self.value_for_bucket(idx)),
+            TableFull | FoundHole(_) => None,
+        }
+    }
+
     /// Return a mutable reference to the value corresponding to the key
+    #[cfg(stage0)]
     fn find_mut(&mut self, k: &K) -> Option<&'self mut V> {
         let idx = match self.bucket_for_key(k) {
             FoundEntry(idx) => idx,
@@ -359,6 +419,20 @@ impl<K:Hash + IterBytes + Eq,V> Map<K, V> for HashMap<K, V> {
         }
     }
 
+    /// Return a mutable reference to the value corresponding to the key
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn find_mut<'a>(&'a mut self, k: &K) -> Option<&'a mut V> {
+        let idx = match self.bucket_for_key(k) {
+            FoundEntry(idx) => idx,
+            TableFull | FoundHole(_) => return None
+        };
+        unsafe {  // FIXME(#4903)---requires flow-sensitive borrow checker
+            Some(::cast::transmute_mut_region(self.mut_value_for_bucket(idx)))
+        }
+    }
+
     /// Insert a key-value pair into the map. An existing value for a
     /// key is replaced by the new value. Return true if the key did
     /// not already exist in the map.
@@ -431,6 +505,7 @@ pub impl<K: Hash + IterBytes + Eq, V> HashMap<K, V> {
 
     /// Return the value corresponding to the key in the map, or insert
     /// and return the value if it doesn't exist.
+    #[cfg(stage0)]
     fn find_or_insert(&mut self, k: K, v: V) -> &'self V {
         if self.size >= self.resize_at {
             // n.b.: We could also do this after searching, so
@@ -459,8 +534,42 @@ pub impl<K: Hash + IterBytes + Eq, V> HashMap<K, V> {
         }
     }
 
+    /// Return the value corresponding to the key in the map, or insert
+    /// and return the value if it doesn't exist.
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn find_or_insert<'a>(&'a mut self, k: K, v: V) -> &'a V {
+        if self.size >= self.resize_at {
+            // n.b.: We could also do this after searching, so
+            // that we do not resize if this call to insert is
+            // simply going to update a key in place.  My sense
+            // though is that it's worse to have to search through
+            // buckets to find the right spot twice than to just
+            // resize in this corner case.
+            self.expand();
+        }
+
+        let hash = k.hash_keyed(self.k0, self.k1) as uint;
+        let idx = match self.bucket_for_key_with_hash(hash, &k) {
+            TableFull => fail!(~"Internal logic error"),
+            FoundEntry(idx) => idx,
+            FoundHole(idx) => {
+                self.buckets[idx] = Some(Bucket{hash: hash, key: k,
+                                     value: v});
+                self.size += 1;
+                idx
+            },
+        };
+
+        unsafe { // FIXME(#4903)---requires flow-sensitive borrow checker
+            ::cast::transmute_region(self.value_for_bucket(idx))
+        }
+    }
+
     /// Return the value corresponding to the key in the map, or create,
     /// insert, and return a new value if it doesn't exist.
+    #[cfg(stage0)]
     fn find_or_insert_with(&mut self, k: K, f: &fn(&K) -> V) -> &'self V {
         if self.size >= self.resize_at {
             // n.b.: We could also do this after searching, so
@@ -490,6 +599,40 @@ pub impl<K: Hash + IterBytes + Eq, V> HashMap<K, V> {
         }
     }
 
+    /// Return the value corresponding to the key in the map, or create,
+    /// insert, and return a new value if it doesn't exist.
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn find_or_insert_with<'a>(&'a mut self, k: K, f: &fn(&K) -> V) -> &'a V {
+        if self.size >= self.resize_at {
+            // n.b.: We could also do this after searching, so
+            // that we do not resize if this call to insert is
+            // simply going to update a key in place.  My sense
+            // though is that it's worse to have to search through
+            // buckets to find the right spot twice than to just
+            // resize in this corner case.
+            self.expand();
+        }
+
+        let hash = k.hash_keyed(self.k0, self.k1) as uint;
+        let idx = match self.bucket_for_key_with_hash(hash, &k) {
+            TableFull => fail!(~"Internal logic error"),
+            FoundEntry(idx) => idx,
+            FoundHole(idx) => {
+                let v = f(&k);
+                self.buckets[idx] = Some(Bucket{hash: hash, key: k,
+                                     value: v});
+                self.size += 1;
+                idx
+            },
+        };
+
+        unsafe { // FIXME(#4903)---requires flow-sensitive borrow checker
+            ::cast::transmute_region(self.value_for_bucket(idx))
+        }
+    }
+
     fn consume(&mut self, f: &fn(K, V)) {
         let mut buckets = ~[];
         self.buckets <-> buckets;
@@ -506,6 +649,7 @@ pub impl<K: Hash + IterBytes + Eq, V> HashMap<K, V> {
         }
     }
 
+    #[cfg(stage0)]
     fn get(&self, k: &K) -> &'self V {
         match self.find(k) {
             Some(v) => v,
@@ -513,6 +657,16 @@ pub impl<K: Hash + IterBytes + Eq, V> HashMap<K, V> {
         }
     }
 
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn get<'a>(&'a self, k: &K) -> &'a V {
+        match self.find(k) {
+            Some(v) => v,
+            None => fail!(fmt!("No entry found for key: %?", k)),
+        }
+    }
+
     /// Return true if the map contains a value for the specified key,
     /// using equivalence
     fn contains_key_equiv<Q:Hash + IterBytes + Equiv<K>>(&self, key: &Q)
@@ -525,6 +679,7 @@ pub impl<K: Hash + IterBytes + Eq, V> HashMap<K, V> {
 
     /// Return the value corresponding to the key in the map, using
     /// equivalence
+    #[cfg(stage0)]
     fn find_equiv<Q:Hash + IterBytes + Equiv<K>>(&self, k: &Q)
                                               -> Option<&'self V> {
         match self.bucket_for_key_equiv(k) {
@@ -532,6 +687,20 @@ pub impl<K: Hash + IterBytes + Eq, V> HashMap<K, V> {
             TableFull | FoundHole(_) => None,
         }
     }
+
+    /// Return the value corresponding to the key in the map, using
+    /// equivalence
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn find_equiv<'a, Q:Hash + IterBytes + Equiv<K>>(
+        &'a self, k: &Q) -> Option<&'a V>
+    {
+        match self.bucket_for_key_equiv(k) {
+            FoundEntry(idx) => Some(self.value_for_bucket(idx)),
+            TableFull | FoundHole(_) => None,
+        }
+    }
 }
 
 impl<K:Hash + IterBytes + Eq,V:Eq> Eq for HashMap<K, V> {
diff --git a/src/libcore/option.rs b/src/libcore/option.rs
index de1482e2c39..9b7276879c1 100644
--- a/src/libcore/option.rs
+++ b/src/libcore/option.rs
@@ -101,11 +101,21 @@ impl<T: Copy + Add<T,T>> Add<Option<T>, Option<T>> for Option<T> {
 
 impl<T> BaseIter<T> for Option<T> {
     /// Performs an operation on the contained value by reference
+    #[cfg(stage0)]
     #[inline(always)]
     fn each(&self, f: &fn(x: &'self T) -> bool) {
         match *self { None => (), Some(ref t) => { f(t); } }
     }
 
+    /// Performs an operation on the contained value by reference
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    #[inline(always)]
+    fn each<'a>(&'a self, f: &fn(x: &'a T) -> bool) {
+        match *self { None => (), Some(ref t) => { f(t); } }
+    }
+
     #[inline(always)]
     fn size_hint(&self) -> Option<uint> {
         if self.is_some() { Some(1) } else { Some(0) }
@@ -113,10 +123,19 @@ impl<T> BaseIter<T> for Option<T> {
 }
 
 impl<T> MutableIter<T> for Option<T> {
+    #[cfg(stage0)]
     #[inline(always)]
     fn each_mut(&mut self, f: &fn(&'self mut T) -> bool) {
         match *self { None => (), Some(ref mut t) => { f(t); } }
     }
+
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    #[inline(always)]
+    fn each_mut<'a>(&'a mut self, f: &fn(&'a mut T) -> bool) {
+        match *self { None => (), Some(ref mut t) => { f(t); } }
+    }
 }
 
 impl<A> ExtendedIter<A> for Option<A> {
@@ -182,17 +201,40 @@ pub impl<T> Option<T> {
      * Update an optional value by optionally running its content by reference
      * through a function that returns an option.
      */
+    #[cfg(stage0)]
     #[inline(always)]
     fn chain_ref<U>(&self, f: &fn(x: &'self T) -> Option<U>) -> Option<U> {
         match *self { Some(ref x) => f(x), None => None }
     }
 
+    /**
+     * Update an optional value by optionally running its content by reference
+     * through a function that returns an option.
+     */
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    #[inline(always)]
+    fn chain_ref<'a, U>(&'a self, f: &fn(x: &'a T) -> Option<U>) -> Option<U> {
+        match *self { Some(ref x) => f(x), None => None }
+    }
+
     /// Maps a `some` value from one type to another by reference
+    #[cfg(stage0)]
     #[inline(always)]
     fn map<U>(&self, f: &fn(&'self T) -> U) -> Option<U> {
         match *self { Some(ref x) => Some(f(x)), None => None }
     }
 
+    /// Maps a `some` value from one type to another by reference
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    #[inline(always)]
+    fn map<'a, U>(&self, f: &fn(&'a T) -> U) -> Option<U> {
+        match *self { Some(ref x) => Some(f(x)), None => None }
+    }
+
     /// As `map`, but consumes the option and gives `f` ownership to avoid
     /// copying.
     #[inline(always)]
@@ -201,11 +243,21 @@ pub impl<T> Option<T> {
     }
 
     /// Applies a function to the contained value or returns a default
+    #[cfg(stage0)]
     #[inline(always)]
     fn map_default<U>(&self, def: U, f: &fn(&'self T) -> U) -> U {
         match *self { None => def, Some(ref t) => f(t) }
     }
 
+    /// Applies a function to the contained value or returns a default
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    #[inline(always)]
+    fn map_default<'a, U>(&'a self, def: U, f: &fn(&'a T) -> U) -> U {
+        match *self { None => def, Some(ref t) => f(t) }
+    }
+
     /// As `map_default`, but consumes the option and gives `f`
     /// ownership to avoid copying.
     #[inline(always)]
@@ -244,6 +296,7 @@ pub impl<T> Option<T> {
     case explicitly.
      */
     #[inline(always)]
+    #[cfg(stage0)]
     fn get_ref(&self) -> &'self T {
         match *self {
           Some(ref x) => x,
@@ -252,6 +305,31 @@ pub impl<T> Option<T> {
     }
 
     /**
+    Gets an immutable reference to the value inside an option.
+
+    # Failure
+
+    Fails if the value equals `None`
+
+    # Safety note
+
+    In general, because this function may fail, its use is discouraged
+    (calling `get` on `None` is akin to dereferencing a null pointer).
+    Instead, prefer to use pattern matching and handle the `None`
+    case explicitly.
+     */
+    #[inline(always)]
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn get_ref<'a>(&'a self) -> &'a T {
+        match *self {
+          Some(ref x) => x,
+          None => fail!(~"option::get_ref none")
+        }
+    }
+
+    /**
     Gets a mutable reference to the value inside an option.
 
     # Failure
@@ -266,6 +344,7 @@ pub impl<T> Option<T> {
     case explicitly.
      */
     #[inline(always)]
+    #[cfg(stage0)]
     fn get_mut_ref(&mut self) -> &'self mut T {
         match *self {
           Some(ref mut x) => x,
@@ -273,6 +352,31 @@ pub impl<T> Option<T> {
         }
     }
 
+    /**
+    Gets a mutable reference to the value inside an option.
+
+    # Failure
+
+    Fails if the value equals `None`
+
+    # Safety note
+
+    In general, because this function may fail, its use is discouraged
+    (calling `get` on `None` is akin to dereferencing a null pointer).
+    Instead, prefer to use pattern matching and handle the `None`
+    case explicitly.
+     */
+    #[inline(always)]
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn get_mut_ref<'a>(&'a mut self) -> &'a mut T {
+        match *self {
+          Some(ref mut x) => x,
+          None => fail!(~"option::get_mut_ref none")
+        }
+    }
+
     #[inline(always)]
     fn unwrap(self) -> T {
         /*!
diff --git a/src/libcore/result.rs b/src/libcore/result.rs
index 8fd81a20603..58e281c29c6 100644
--- a/src/libcore/result.rs
+++ b/src/libcore/result.rs
@@ -226,9 +226,16 @@ pub fn map_err<T:Copy,E,F:Copy>(res: &Result<T, E>, op: &fn(&E) -> F)
 }
 
 pub impl<T, E> Result<T, E> {
+    #[cfg(stage0)]
     #[inline(always)]
     fn get_ref(&self) -> &'self T { get_ref(self) }
 
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    #[inline(always)]
+    fn get_ref<'a>(&'a self) -> &'a T { get_ref(self) }
+
     #[inline(always)]
     fn is_ok(&self) -> bool { is_ok(self) }
 
diff --git a/src/libcore/rt/rtio.rs b/src/libcore/rt/rtio.rs
index 55e062de85b..6a7c3970c00 100644
--- a/src/libcore/rt/rtio.rs
+++ b/src/libcore/rt/rtio.rs
@@ -22,7 +22,12 @@ pub trait EventLoop {
     fn run(&mut self);
     fn callback(&mut self, ~fn());
     /// The asynchronous I/O services. Not all event loops may provide one
+    #[cfg(stage0)]
     fn io(&mut self) -> Option<&'self mut IoFactoryObject>;
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn io<'a>(&'a mut self) -> Option<&'a mut IoFactoryObject>;
 }
 
 pub trait IoFactory {
diff --git a/src/libcore/rt/sched.rs b/src/libcore/rt/sched.rs
index 46ea5713e2a..25f446fb86d 100644
--- a/src/libcore/rt/sched.rs
+++ b/src/libcore/rt/sched.rs
@@ -272,6 +272,7 @@ pub impl Scheduler {
 
     // XXX: Hack. This should return &'self mut but I don't know how to
     // make the borrowcheck happy
+    #[cfg(stage0)]
     fn task_from_last_cleanup_job(&mut self) -> &mut Task {
         assert!(!self.cleanup_jobs.is_empty());
         let last_job: &'self mut CleanupJob = &mut self.cleanup_jobs[0];
@@ -285,6 +286,25 @@ pub impl Scheduler {
         // borrows
         return unsafe { transmute::<&Task, &mut Task>(last_task) };
     }
+
+    // XXX: Hack. This should return &'self mut but I don't know how to
+    // make the borrowcheck happy
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn task_from_last_cleanup_job<'a>(&'a mut self) -> &mut Task {
+        assert!(!self.cleanup_jobs.is_empty());
+        let last_job: &'a mut CleanupJob = &mut self.cleanup_jobs[0];
+        let last_task: &'a Task = match last_job {
+            &RescheduleTask(~ref task) => task,
+            &RecycleTask(~ref task) => task,
+            &GiveTask(~ref task, _) => task,
+        };
+        // XXX: Pattern matching mutable pointers above doesn't work
+        // because borrowck thinks the three patterns are conflicting
+        // borrows
+        return unsafe { transmute::<&Task, &mut Task>(last_task) };
+    }
 }
 
 static TASK_MIN_STACK_SIZE: uint = 10000000; // XXX: Too much stack
@@ -354,6 +374,7 @@ impl ThreadLocalScheduler {
         }
     }
 
+    #[cfg(stage0)]
     fn get_scheduler(&mut self) -> &'self mut Scheduler {
         unsafe {
             let key = match self { &ThreadLocalScheduler(key) => key };
@@ -370,6 +391,25 @@ impl ThreadLocalScheduler {
         }
     }
 
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn get_scheduler<'a>(&'a mut self) -> &'a mut Scheduler {
+        unsafe {
+            let key = match self { &ThreadLocalScheduler(key) => key };
+            let mut value: *mut c_void = tls::get(key);
+            assert!(value.is_not_null());
+            {
+                let value_ptr = &mut value;
+                let sched: &mut ~Scheduler = {
+                    transmute::<&mut *mut c_void, &mut ~Scheduler>(value_ptr)
+                };
+                let sched: &mut Scheduler = &mut **sched;
+                return sched;
+            }
+        }
+    }
+
     fn take_scheduler(&mut self) -> ~Scheduler {
         unsafe {
             let key = match self { &ThreadLocalScheduler(key) => key };
diff --git a/src/libcore/rt/uvio.rs b/src/libcore/rt/uvio.rs
index 37f29d1a5c0..7162ed27a9d 100644
--- a/src/libcore/rt/uvio.rs
+++ b/src/libcore/rt/uvio.rs
@@ -67,9 +67,17 @@ impl EventLoop for UvEventLoop {
         }
     }
 
+    #[cfg(stage0)]
     fn io(&mut self) -> Option<&'self mut IoFactoryObject> {
         Some(&mut self.uvio)
     }
+
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn io<'a>(&'a mut self) -> Option<&'a mut IoFactoryObject> {
+        Some(&mut self.uvio)
+    }
 }
 
 #[test]
@@ -89,9 +97,17 @@ fn test_callback_run_once() {
 pub struct UvIoFactory(Loop);
 
 pub impl UvIoFactory {
+    #[cfg(stage0)]
     fn uv_loop(&mut self) -> &'self mut Loop {
         match self { &UvIoFactory(ref mut ptr) => ptr }
     }
+
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn uv_loop<'a>(&'a mut self) -> &'a mut Loop {
+        match self { &UvIoFactory(ref mut ptr) => ptr }
+    }
 }
 
 impl IoFactory for UvIoFactory {
diff --git a/src/libcore/str.rs b/src/libcore/str.rs
index 2201836c724..521c8266e05 100644
--- a/src/libcore/str.rs
+++ b/src/libcore/str.rs
@@ -318,7 +318,11 @@ pub fn slice_shift_char<'a>(s: &'a str) -> (char, &'a str) {
 
 /// Prepend a char to a string
 pub fn unshift_char(s: &mut ~str, ch: char) {
-    *s = from_char(ch) + *s;
+    // This could be more efficient.
+    let mut new_str = ~"";
+    new_str.push_char(ch);
+    new_str.push_str(*s);
+    *s = new_str;
 }
 
 /**
diff --git a/src/libcore/task/mod.rs b/src/libcore/task/mod.rs
index 502efcf9dc6..e4ee430cdda 100644
--- a/src/libcore/task/mod.rs
+++ b/src/libcore/task/mod.rs
@@ -39,7 +39,7 @@ use result::Result;
 use comm::{stream, Chan, GenericChan, GenericPort, Port};
 use prelude::*;
 use result;
-use task::rt::{task_id, sched_id, rust_task};
+use task::rt::{task_id, sched_id};
 use util;
 use util::replace;
 use unstable::finally::Finally;
diff --git a/src/libcore/trie.rs b/src/libcore/trie.rs
index f6a92a21385..f4e9ddbdd90 100644
--- a/src/libcore/trie.rs
+++ b/src/libcore/trie.rs
@@ -56,10 +56,20 @@ impl<T> Map<uint, T> for TrieMap<T> {
 
     /// Visit all key-value pairs in order
     #[inline(always)]
+    #[cfg(stage0)]
     fn each(&self, f: &fn(&uint, &'self T) -> bool) {
         self.root.each(f);
     }
 
+    /// Visit all key-value pairs in order
+    #[inline(always)]
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn each<'a>(&'a self, f: &fn(&uint, &'a T) -> bool) {
+        self.root.each(f);
+    }
+
     /// Visit all keys in order
     #[inline(always)]
     fn each_key(&self, f: &fn(&uint) -> bool) {
@@ -68,10 +78,20 @@ impl<T> Map<uint, T> for TrieMap<T> {
 
     /// Visit all values in order
     #[inline(always)]
+    #[cfg(stage0)]
     fn each_value(&self, f: &fn(&T) -> bool) {
         self.each(|_, v| f(v))
     }
 
+    /// Visit all values in order
+    #[inline(always)]
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn each_value<'a>(&'a self, f: &fn(&'a T) -> bool) {
+        self.each(|_, v| f(v))
+    }
+
     /// Iterate over the map and mutate the contained values
     #[inline(always)]
     fn mutate_values(&mut self, f: &fn(&uint, &mut T) -> bool) {
@@ -79,6 +99,7 @@ impl<T> Map<uint, T> for TrieMap<T> {
     }
 
     /// Return a reference to the value corresponding to the key
+    #[cfg(stage0)]
     #[inline(hint)]
     fn find(&self, key: &uint) -> Option<&'self T> {
         let mut node: &'self TrieNode<T> = &self.root;
@@ -99,12 +120,46 @@ impl<T> Map<uint, T> for TrieMap<T> {
         }
     }
 
+    /// Return a reference to the value corresponding to the key
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    #[inline(hint)]
+    fn find<'a>(&'a self, key: &uint) -> Option<&'a T> {
+        let mut node: &'a TrieNode<T> = &self.root;
+        let mut idx = 0;
+        loop {
+            match node.children[chunk(*key, idx)] {
+              Internal(ref x) => node = &**x,
+              External(stored, ref value) => {
+                if stored == *key {
+                    return Some(value)
+                } else {
+                    return None
+                }
+              }
+              Nothing => return None
+            }
+            idx += 1;
+        }
+    }
+
     /// Return a mutable reference to the value corresponding to the key
+    #[cfg(stage0)]
     #[inline(always)]
     fn find_mut(&mut self, key: &uint) -> Option<&'self mut T> {
         find_mut(&mut self.root.children[chunk(*key, 0)], *key, 1)
     }
 
+    /// Return a mutable reference to the value corresponding to the key
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    #[inline(always)]
+    fn find_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut T> {
+        find_mut(&mut self.root.children[chunk(*key, 0)], *key, 1)
+    }
+
     /// Insert a key-value pair into the map. An existing value for a
     /// key is replaced by the new value. Return true if the key did
     /// not already exist in the map.
@@ -138,10 +193,20 @@ pub impl<T> TrieMap<T> {
 
     /// Visit all key-value pairs in reverse order
     #[inline(always)]
+    #[cfg(stage0)]
     fn each_reverse(&self, f: &fn(&uint, &'self T) -> bool) {
         self.root.each_reverse(f);
     }
 
+    /// Visit all key-value pairs in reverse order
+    #[inline(always)]
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn each_reverse<'a>(&'a self, f: &fn(&uint, &'a T) -> bool) {
+        self.root.each_reverse(f);
+    }
+
     /// Visit all keys in reverse order
     #[inline(always)]
     fn each_key_reverse(&self, f: &fn(&uint) -> bool) {
@@ -233,6 +298,7 @@ impl<T> TrieNode<T> {
 }
 
 impl<T> TrieNode<T> {
+    #[cfg(stage0)]
     fn each(&self, f: &fn(&uint, &'self T) -> bool) -> bool {
         for uint::range(0, self.children.len()) |idx| {
             match self.children[idx] {
@@ -244,6 +310,21 @@ impl<T> TrieNode<T> {
         true
     }
 
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn each<'a>(&'a self, f: &fn(&uint, &'a T) -> bool) -> bool {
+        for uint::range(0, self.children.len()) |idx| {
+            match self.children[idx] {
+                Internal(ref x) => if !x.each(f) { return false },
+                External(k, ref v) => if !f(&k, v) { return false },
+                Nothing => ()
+            }
+        }
+        true
+    }
+
+    #[cfg(stage0)]
     fn each_reverse(&self, f: &fn(&uint, &'self T) -> bool) -> bool {
         for uint::range_rev(self.children.len(), 0) |idx| {
             match self.children[idx - 1] {
@@ -255,7 +336,21 @@ impl<T> TrieNode<T> {
         true
     }
 
-    fn mutate_values(&mut self, f: &fn(&uint, &mut T) -> bool) -> bool {
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn each_reverse<'a>(&'a self, f: &fn(&uint, &'a T) -> bool) -> bool {
+        for uint::range_rev(self.children.len(), 0) |idx| {
+            match self.children[idx - 1] {
+                Internal(ref x) => if !x.each_reverse(f) { return false },
+                External(k, ref v) => if !f(&k, v) { return false },
+                Nothing => ()
+            }
+        }
+        true
+    }
+
+    fn mutate_values<'a>(&'a mut self, f: &fn(&uint, &mut T) -> bool) -> bool {
         for vec::each_mut(self.children) |child| {
             match *child {
                 Internal(ref mut x) => if !x.mutate_values(f) {
diff --git a/src/libcore/tuple.rs b/src/libcore/tuple.rs
index 35b8496f6c5..8e908435f35 100644
--- a/src/libcore/tuple.rs
+++ b/src/libcore/tuple.rs
@@ -56,11 +56,13 @@ impl<T:Clone,U:Clone> Clone for (T, U) {
     }
 }
 
+#[cfg(stage0)]
 pub trait ImmutableTuple<T, U> {
     fn first_ref(&self) -> &'self T;
     fn second_ref(&self) -> &'self U;
 }
 
+#[cfg(stage0)]
 impl<T, U> ImmutableTuple<T, U> for (T, U) {
     #[inline(always)]
     fn first_ref(&self) -> &'self T {
@@ -76,6 +78,32 @@ impl<T, U> ImmutableTuple<T, U> for (T, U) {
     }
 }
 
+#[cfg(stage1)]
+#[cfg(stage2)]
+#[cfg(stage3)]
+pub trait ImmutableTuple<T, U> {
+    fn first_ref<'a>(&'a self) -> &'a T;
+    fn second_ref<'a>(&'a self) -> &'a U;
+}
+
+#[cfg(stage1)]
+#[cfg(stage2)]
+#[cfg(stage3)]
+impl<T, U> ImmutableTuple<T, U> for (T, U) {
+    #[inline(always)]
+    fn first_ref<'a>(&'a self) -> &'a T {
+        match *self {
+            (ref t, _) => t,
+        }
+    }
+    #[inline(always)]
+    fn second_ref<'a>(&'a self) -> &'a U {
+        match *self {
+            (_, ref u) => u,
+        }
+    }
+}
+
 pub trait ExtendedTupleOps<A,B> {
     fn zip(&self) -> ~[(A, B)];
     fn map<C>(&self, f: &fn(a: &A, b: &B) -> C) -> ~[C];
@@ -161,7 +189,6 @@ impl<A:Ord> Ord for (A,) {
     fn gt(&self, other: &(A,)) -> bool { other.lt(&(*self))  }
 }
 
-
 #[cfg(notest)]
 impl<A:Eq,B:Eq> Eq for (A, B) {
     #[inline(always)]
diff --git a/src/libcore/vec.rs b/src/libcore/vec.rs
index 5b06591f9ec..7940502d27e 100644
--- a/src/libcore/vec.rs
+++ b/src/libcore/vec.rs
@@ -1763,6 +1763,7 @@ impl<'self,T:Copy> CopyableVector<T> for &'self const [T] {
     }
 }
 
+#[cfg(stage0)]
 pub trait ImmutableVector<T> {
     fn slice(&self, start: uint, end: uint) -> &'self [T];
     fn head(&self) -> &'self T;
@@ -1785,6 +1786,7 @@ pub trait ImmutableVector<T> {
 }
 
 /// Extension methods for vectors
+#[cfg(stage0)]
 impl<'self,T> ImmutableVector<T> for &'self [T] {
     /// Return a slice that points into another slice.
     #[inline]
@@ -1893,6 +1895,142 @@ impl<'self,T> ImmutableVector<T> for &'self [T] {
     }
 }
 
+#[cfg(stage1)]
+#[cfg(stage2)]
+#[cfg(stage3)]
+pub trait ImmutableVector<'self, T> {
+    fn slice(&self, start: uint, end: uint) -> &'self [T];
+    fn head(&self) -> &'self T;
+    fn head_opt(&self) -> Option<&'self T>;
+    fn tail(&self) -> &'self [T];
+    fn tailn(&self, n: uint) -> &'self [T];
+    fn init(&self) -> &'self [T];
+    fn initn(&self, n: uint) -> &'self [T];
+    fn last(&self) -> &'self T;
+    fn last_opt(&self) -> Option<&'self T>;
+    fn each_reverse(&self, blk: &fn(&T) -> bool);
+    fn eachi_reverse(&self, blk: &fn(uint, &T) -> bool);
+    fn foldr<U: Copy>(&self, z: U, p: &fn(t: &T, u: U) -> U) -> U;
+    fn map<U>(&self, f: &fn(t: &T) -> U) -> ~[U];
+    fn mapi<U>(&self, f: &fn(uint, t: &T) -> U) -> ~[U];
+    fn map_r<U>(&self, f: &fn(x: &T) -> U) -> ~[U];
+    fn alli(&self, f: &fn(uint, t: &T) -> bool) -> bool;
+    fn flat_map<U>(&self, f: &fn(t: &T) -> ~[U]) -> ~[U];
+    fn filter_mapped<U:Copy>(&self, f: &fn(t: &T) -> Option<U>) -> ~[U];
+}
+
+/// Extension methods for vectors
+#[cfg(stage1)]
+#[cfg(stage2)]
+#[cfg(stage3)]
+impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
+    /// Return a slice that points into another slice.
+    #[inline]
+    fn slice(&self, start: uint, end: uint) -> &'self [T] {
+        slice(*self, start, end)
+    }
+
+    /// Returns the first element of a vector, failing if the vector is empty.
+    #[inline]
+    fn head(&self) -> &'self T { head(*self) }
+
+    /// Returns the first element of a vector
+    #[inline]
+    fn head_opt(&self) -> Option<&'self T> { head_opt(*self) }
+
+    /// Returns all but the first element of a vector
+    #[inline]
+    fn tail(&self) -> &'self [T] { tail(*self) }
+
+    /// Returns all but the first `n' elements of a vector
+    #[inline]
+    fn tailn(&self, n: uint) -> &'self [T] { tailn(*self, n) }
+
+    /// Returns all but the last elemnt of a vector
+    #[inline]
+    fn init(&self) -> &'self [T] { init(*self) }
+
+    /// Returns all but the last `n' elemnts of a vector
+    #[inline]
+    fn initn(&self, n: uint) -> &'self [T] { initn(*self, n) }
+
+    /// Returns the last element of a `v`, failing if the vector is empty.
+    #[inline]
+    fn last(&self) -> &'self T { last(*self) }
+
+    /// Returns the last element of a `v`, failing if the vector is empty.
+    #[inline]
+    fn last_opt(&self) -> Option<&'self T> { last_opt(*self) }
+
+    /// Iterates over a vector's elements in reverse.
+    #[inline]
+    fn each_reverse(&self, blk: &fn(&T) -> bool) {
+        each_reverse(*self, blk)
+    }
+
+    /// Iterates over a vector's elements and indices in reverse.
+    #[inline]
+    fn eachi_reverse(&self, blk: &fn(uint, &T) -> bool) {
+        eachi_reverse(*self, blk)
+    }
+
+    /// Reduce a vector from right to left
+    #[inline]
+    fn foldr<U:Copy>(&self, z: U, p: &fn(t: &T, u: U) -> U) -> U {
+        foldr(*self, z, p)
+    }
+
+    /// Apply a function to each element of a vector and return the results
+    #[inline]
+    fn map<U>(&self, f: &fn(t: &T) -> U) -> ~[U] { map(*self, f) }
+
+    /**
+     * Apply a function to the index and value of each element in the vector
+     * and return the results
+     */
+    fn mapi<U>(&self, f: &fn(uint, t: &T) -> U) -> ~[U] {
+        mapi(*self, f)
+    }
+
+    #[inline]
+    fn map_r<U>(&self, f: &fn(x: &T) -> U) -> ~[U] {
+        let mut r = ~[];
+        let mut i = 0;
+        while i < self.len() {
+            r.push(f(&self[i]));
+            i += 1;
+        }
+        r
+    }
+
+    /**
+     * Returns true if the function returns true for all elements.
+     *
+     *     If the vector is empty, true is returned.
+     */
+    fn alli(&self, f: &fn(uint, t: &T) -> bool) -> bool {
+        alli(*self, f)
+    }
+    /**
+     * Apply a function to each element of a vector and return a concatenation
+     * of each result vector
+     */
+    #[inline]
+    fn flat_map<U>(&self, f: &fn(t: &T) -> ~[U]) -> ~[U] {
+        flat_map(*self, f)
+    }
+    /**
+     * Apply a function to each element of a vector and return the results
+     *
+     * If function `f` returns `none` then that element is excluded from
+     * the resulting vector.
+     */
+    #[inline]
+    fn filter_mapped<U:Copy>(&self, f: &fn(t: &T) -> Option<U>) -> ~[U] {
+        filter_mapped(*self, f)
+    }
+}
+
 pub trait ImmutableEqVector<T:Eq> {
     fn position(&self, f: &fn(t: &T) -> bool) -> Option<uint>;
     fn position_elem(&self, t: &T) -> Option<uint>;
@@ -2353,6 +2491,7 @@ pub mod bytes {
 // ___________________________________________________________________________
 // ITERATION TRAIT METHODS
 
+#[cfg(stage0)]
 impl<'self,A> iter::BaseIter<A> for &'self [A] {
     #[inline(always)]
     fn each(&self, blk: &fn(v: &'self A) -> bool) { each(*self, blk) }
@@ -2360,7 +2499,18 @@ impl<'self,A> iter::BaseIter<A> for &'self [A] {
     fn size_hint(&self) -> Option<uint> { Some(self.len()) }
 }
 
+#[cfg(stage1)]
+#[cfg(stage2)]
+#[cfg(stage3)]
+impl<'self,A> iter::BaseIter<A> for &'self [A] {
+    #[inline(always)]
+    fn each<'a>(&'a self, blk: &fn(v: &'a A) -> bool) { each(*self, blk) }
+    #[inline(always)]
+    fn size_hint(&self) -> Option<uint> { Some(self.len()) }
+}
+
 // FIXME(#4148): This should be redundant
+#[cfg(stage0)]
 impl<A> iter::BaseIter<A> for ~[A] {
     #[inline(always)]
     fn each(&self, blk: &fn(v: &'self A) -> bool) { each(*self, blk) }
@@ -2369,6 +2519,18 @@ impl<A> iter::BaseIter<A> for ~[A] {
 }
 
 // FIXME(#4148): This should be redundant
+#[cfg(stage1)]
+#[cfg(stage2)]
+#[cfg(stage3)]
+impl<A> iter::BaseIter<A> for ~[A] {
+    #[inline(always)]
+    fn each<'a>(&'a self, blk: &fn(v: &'a A) -> bool) { each(*self, blk) }
+    #[inline(always)]
+    fn size_hint(&self) -> Option<uint> { Some(self.len()) }
+}
+
+// FIXME(#4148): This should be redundant
+#[cfg(stage0)]
 impl<A> iter::BaseIter<A> for @[A] {
     #[inline(always)]
     fn each(&self, blk: &fn(v: &'self A) -> bool) { each(*self, blk) }
@@ -2376,6 +2538,18 @@ impl<A> iter::BaseIter<A> for @[A] {
     fn size_hint(&self) -> Option<uint> { Some(self.len()) }
 }
 
+// FIXME(#4148): This should be redundant
+#[cfg(stage1)]
+#[cfg(stage2)]
+#[cfg(stage3)]
+impl<A> iter::BaseIter<A> for @[A] {
+    #[inline(always)]
+    fn each<'a>(&'a self, blk: &fn(v: &'a A) -> bool) { each(*self, blk) }
+    #[inline(always)]
+    fn size_hint(&self) -> Option<uint> { Some(self.len()) }
+}
+
+#[cfg(stage0)]
 impl<'self,A> iter::MutableIter<A> for &'self mut [A] {
     #[inline(always)]
     fn each_mut(&mut self, blk: &fn(v: &'self mut A) -> bool) {
@@ -2383,7 +2557,18 @@ impl<'self,A> iter::MutableIter<A> for &'self mut [A] {
     }
 }
 
+#[cfg(stage1)]
+#[cfg(stage2)]
+#[cfg(stage3)]
+impl<'self,A> iter::MutableIter<A> for &'self mut [A] {
+    #[inline(always)]
+    fn each_mut<'a>(&'a mut self, blk: &fn(v: &'a mut A) -> bool) {
+        each_mut(*self, blk)
+    }
+}
+
 // FIXME(#4148): This should be redundant
+#[cfg(stage0)]
 impl<A> iter::MutableIter<A> for ~[A] {
     #[inline(always)]
     fn each_mut(&mut self, blk: &fn(v: &'self mut A) -> bool) {
@@ -2391,6 +2576,16 @@ impl<A> iter::MutableIter<A> for ~[A] {
     }
 }
 
+#[cfg(stage1)]
+#[cfg(stage2)]
+#[cfg(stage3)]
+impl<A> iter::MutableIter<A> for ~[A] {
+    #[inline(always)]
+    fn each_mut<'a>(&'a mut self, blk: &fn(v: &'a mut A) -> bool) {
+        each_mut(*self, blk)
+    }
+}
+
 // FIXME(#4148): This should be redundant
 impl<A> iter::MutableIter<A> for @mut [A] {
     #[inline(always)]
diff --git a/src/librustc/metadata/tydecode.rs b/src/librustc/metadata/tydecode.rs
index 8f75f1bd4c2..f52ff056472 100644
--- a/src/librustc/metadata/tydecode.rs
+++ b/src/librustc/metadata/tydecode.rs
@@ -239,7 +239,8 @@ fn parse_region(st: @mut PState) -> ty::Region {
         assert!(next(st) == '|');
         let br = parse_bound_region(st);
         assert!(next(st) == ']');
-        ty::re_free(id, br)
+        ty::re_free(ty::FreeRegion {scope_id: id,
+                                    bound_region: br})
       }
       's' => {
         let id = parse_uint(st) as int;
diff --git a/src/librustc/metadata/tyencode.rs b/src/librustc/metadata/tyencode.rs
index 238f34b8c01..2e1dd8b6dad 100644
--- a/src/librustc/metadata/tyencode.rs
+++ b/src/librustc/metadata/tyencode.rs
@@ -146,12 +146,12 @@ fn enc_region(w: @io::Writer, cx: @ctxt, r: ty::Region) {
         w.write_char('b');
         enc_bound_region(w, cx, br);
       }
-      ty::re_free(id, br) => {
+      ty::re_free(ref fr) => {
         w.write_char('f');
         w.write_char('[');
-        w.write_int(id);
+        w.write_int(fr.scope_id);
         w.write_char('|');
-        enc_bound_region(w, cx, br);
+        enc_bound_region(w, cx, fr.bound_region);
         w.write_char(']');
       }
       ty::re_scope(nid) => {
diff --git a/src/librustc/middle/astencode.rs b/src/librustc/middle/astencode.rs
index f5a31879855..a67be995171 100644
--- a/src/librustc/middle/astencode.rs
+++ b/src/librustc/middle/astencode.rs
@@ -475,9 +475,12 @@ impl tr for ty::Region {
     fn tr(&self, xcx: @ExtendedDecodeContext) -> ty::Region {
         match *self {
             ty::re_bound(br) => ty::re_bound(br.tr(xcx)),
-            ty::re_free(id, br) => ty::re_free(xcx.tr_id(id), br.tr(xcx)),
             ty::re_scope(id) => ty::re_scope(xcx.tr_id(id)),
             ty::re_static | ty::re_infer(*) => *self,
+            ty::re_free(ref fr) => {
+                ty::re_free(ty::FreeRegion {scope_id: xcx.tr_id(fr.scope_id),
+                                            bound_region: fr.bound_region.tr(xcx)})
+            }
         }
     }
 }
diff --git a/src/librustc/middle/borrowck/check_loans.rs b/src/librustc/middle/borrowck/check_loans.rs
index 16035656742..721bb996262 100644
--- a/src/librustc/middle/borrowck/check_loans.rs
+++ b/src/librustc/middle/borrowck/check_loans.rs
@@ -128,9 +128,9 @@ pub impl CheckLoanCtxt {
               Some(e) => return Some(pc_cmt(*e))
             }
 
-            match self.tcx().region_map.find(&scope_id) {
+            match self.tcx().region_maps.opt_encl_scope(scope_id) {
               None => return default_purity,
-              Some(&next_scope_id) => scope_id = next_scope_id
+              Some(next_scope_id) => scope_id = next_scope_id
             }
         }
     }
@@ -146,9 +146,9 @@ pub impl CheckLoanCtxt {
                 }
             }
 
-            match self.tcx().region_map.find(&scope_id) {
+            match self.tcx().region_maps.opt_encl_scope(scope_id) {
               None => return,
-              Some(&next_scope_id) => scope_id = next_scope_id,
+              Some(next_scope_id) => scope_id = next_scope_id,
             }
         }
     }
@@ -270,7 +270,7 @@ pub impl CheckLoanCtxt {
 
         debug!("new_loans has length %?", new_loans.len());
 
-        let par_scope_id = *self.tcx().region_map.get(&scope_id);
+        let par_scope_id = self.tcx().region_maps.encl_scope(scope_id);
         for self.walk_loans(par_scope_id) |old_loan| {
             debug!("old_loan=%?", self.bccx.loan_to_repr(old_loan));
 
diff --git a/src/librustc/middle/borrowck/gather_loans.rs b/src/librustc/middle/borrowck/gather_loans.rs
index 233b1e191dc..4e61b573891 100644
--- a/src/librustc/middle/borrowck/gather_loans.rs
+++ b/src/librustc/middle/borrowck/gather_loans.rs
@@ -242,7 +242,7 @@ fn req_loans_in_expr(ex: @ast::expr,
         // (if used like `a.b(...)`), the call where it's an argument
         // (if used like `x(a.b)`), or the block (if used like `let x
         // = a.b`).
-        let scope_r = ty::re_scope(*self.tcx().region_map.get(&ex.id));
+        let scope_r = self.tcx().region_maps.encl_region(ex.id);
         let rcvr_cmt = self.bccx.cat_expr(rcvr);
         self.guarantee_valid(rcvr_cmt, m_imm, scope_r);
         visit::visit_expr(ex, self, vt);
@@ -524,7 +524,10 @@ pub impl GatherLoanCtxt {
         // immutable structures, this is just the converse I suppose)
 
         let scope_id = match scope_r {
-            ty::re_scope(scope_id) | ty::re_free(scope_id, _) => scope_id,
+            ty::re_scope(scope_id) |
+            ty::re_free(ty::FreeRegion {scope_id, _}) => {
+                scope_id
+            }
             _ => {
                 self.bccx.tcx.sess.span_bug(
                     cmt.span,
diff --git a/src/librustc/middle/borrowck/loan.rs b/src/librustc/middle/borrowck/loan.rs
index 146e0c712a3..a38cd015654 100644
--- a/src/librustc/middle/borrowck/loan.rs
+++ b/src/librustc/middle/borrowck/loan.rs
@@ -130,8 +130,8 @@ pub impl LoanContext {
           }
           cat_local(local_id) | cat_arg(local_id) | cat_self(local_id) => {
               // FIXME(#4903)
-            let local_scope_id = *self.bccx.tcx.region_map.get(&local_id);
-            self.issue_loan(cmt, ty::re_scope(local_scope_id), loan_kind,
+            let local_region = self.bccx.tcx.region_maps.encl_region(local_id);
+            self.issue_loan(cmt, local_region, loan_kind,
                             owns_lent_data)
           }
           cat_stack_upvar(cmt) => {
diff --git a/src/librustc/middle/borrowck/mod.rs b/src/librustc/middle/borrowck/mod.rs
index 5e7903f6610..01fea2a960d 100644
--- a/src/librustc/middle/borrowck/mod.rs
+++ b/src/librustc/middle/borrowck/mod.rs
@@ -227,7 +227,6 @@ Borrowck results in two maps.
 use core::prelude::*;
 
 use middle::mem_categorization::*;
-use middle::region;
 use middle::ty;
 use middle::typeck;
 use middle::moves;
@@ -458,7 +457,7 @@ pub fn root_map() -> root_map {
 
 pub impl BorrowckCtxt {
     fn is_subregion_of(&self, r_sub: ty::Region, r_sup: ty::Region) -> bool {
-        region::is_subregion_of(self.tcx.region_map, r_sub, r_sup)
+        self.tcx.region_maps.is_subregion_of(r_sub, r_sup)
     }
 
     fn cat_expr(&self, expr: @ast::expr) -> cmt {
diff --git a/src/librustc/middle/borrowck/preserve.rs b/src/librustc/middle/borrowck/preserve.rs
index 3056edea233..40a59e2f89f 100644
--- a/src/librustc/middle/borrowck/preserve.rs
+++ b/src/librustc/middle/borrowck/preserve.rs
@@ -108,7 +108,7 @@ pub impl<'self> PreserveCtxt<'self> {
                 // Maybe if we pass in the parent instead here,
                 // we can prevent the "scope not found" error
                 debug!("scope_region thing: %? ", cmt.id);
-                ty::re_scope(*self.tcx().region_map.get(&cmt.id))
+                self.tcx().region_maps.encl_region(cmt.id)
             };
 
             self.compare_scope(cmt, scope_region)
@@ -128,27 +128,27 @@ pub impl<'self> PreserveCtxt<'self> {
                     cmt.span,
                     ~"preserve() called with local and !root_managed_data");
             }
-            let local_scope_id = *self.tcx().region_map.get(&local_id);
-            self.compare_scope(cmt, ty::re_scope(local_scope_id))
+            let local_region = self.tcx().region_maps.encl_region(local_id);
+            self.compare_scope(cmt, local_region)
           }
           cat_binding(local_id) => {
             // Bindings are these kind of weird implicit pointers (cc
             // #2329).  We require (in gather_loans) that they be
             // rooted in an immutable location.
-            let local_scope_id = *self.tcx().region_map.get(&local_id);
-            self.compare_scope(cmt, ty::re_scope(local_scope_id))
+            let local_region = self.tcx().region_maps.encl_region(local_id);
+            self.compare_scope(cmt, local_region)
           }
           cat_arg(local_id) => {
             // This can happen as not all args are lendable (e.g., &&
             // modes).  In that case, the caller guarantees stability
             // for at least the scope of the fn.  This is basically a
             // deref of a region ptr.
-            let local_scope_id = *self.tcx().region_map.get(&local_id);
-            self.compare_scope(cmt, ty::re_scope(local_scope_id))
+            let local_region = self.tcx().region_maps.encl_region(local_id);
+            self.compare_scope(cmt, local_region)
           }
           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))
+            let local_region = self.tcx().region_maps.encl_region(local_id);
+            self.compare_scope(cmt, local_region)
           }
           cat_comp(cmt_base, comp_field(*)) |
           cat_comp(cmt_base, comp_index(*)) |
diff --git a/src/librustc/middle/check_match.rs b/src/librustc/middle/check_match.rs
index fdea403cc2a..6898dcca45d 100644
--- a/src/librustc/middle/check_match.rs
+++ b/src/librustc/middle/check_match.rs
@@ -596,8 +596,11 @@ pub fn specialize(cx: @MatchCheckCtxt,
                                                              class_id);
                             }
                             _ => {
-                                cx.tcx.sess.span_bug(pat_span,
-                                ~"struct pattern didn't resolve to a struct");
+                                cx.tcx.sess.span_bug(
+                                    pat_span,
+                                    fmt!("struct pattern resolved to %s, \
+                                          not a struct",
+                                         ty_to_str(cx.tcx, left_ty)));
                             }
                         }
                         let args = vec::map(class_fields, |class_field| {
diff --git a/src/librustc/middle/kind.rs b/src/librustc/middle/kind.rs
index e82b6ba5e77..e5fc9f2d603 100644
--- a/src/librustc/middle/kind.rs
+++ b/src/librustc/middle/kind.rs
@@ -16,7 +16,7 @@ use middle::liveness;
 use middle::pat_util;
 use middle::ty;
 use middle::typeck;
-use util::ppaux::{Repr, ty_to_str, tys_to_str};
+use util::ppaux::{Repr, ty_to_str};
 
 use syntax::ast::*;
 use syntax::attr::attrs_contains_name;
@@ -478,13 +478,13 @@ pub fn check_durable(tcx: ty::ctxt, ty: ty::t, sp: span) -> bool {
     }
 }
 
-/// This is rather subtle.  When we are casting a value to a
-/// instantiated trait like `a as trait<'r>`, regionck already ensures
-/// that any borrowed pointers that appear in the type of `a` are
-/// bounded by `&r`.  However, it is possible that there are *type
-/// parameters* in the type of `a`, and those *type parameters* may
-/// have borrowed pointers within them.  We have to guarantee that the
-/// regions which appear in those type parameters are not obscured.
+/// This is rather subtle.  When we are casting a value to a instantiated
+/// trait like `a as trait<'r>`, regionck already ensures that any borrowed
+/// pointers that appear in the type of `a` are bounded by `'r` (ed.: modulo
+/// FIXME(#5723)).  However, it is possible that there are *type parameters*
+/// in the type of `a`, and those *type parameters* may have borrowed pointers
+/// within them.  We have to guarantee that the regions which appear in those
+/// type parameters are not obscured.
 ///
 /// Therefore, we ensure that one of three conditions holds:
 ///
@@ -501,6 +501,8 @@ pub fn check_durable(tcx: ty::ctxt, ty: ty::t, sp: span) -> bool {
 ///
 /// (3) The type parameter is owned (and therefore does not contain
 /// borrowed ptrs).
+///
+/// FIXME(#5723)---This code should probably move into regionck.
 pub fn check_cast_for_escaping_regions(
     cx: Context,
     source: @expr,
@@ -509,40 +511,78 @@ pub fn check_cast_for_escaping_regions(
     // Determine what type we are casting to; if it is not an trait, then no
     // worries.
     let target_ty = ty::expr_ty(cx.tcx, target);
-    let target_substs = match ty::get(target_ty).sty {
-      ty::ty_trait(_, ref substs, _) => {(/*bad*/copy *substs)}
-      _ => { return; /* not a cast to a trait */ }
-    };
+    match ty::get(target_ty).sty {
+        ty::ty_trait(*) => {}
+        _ => { return; }
+    }
+
+    // Collect up the regions that appear in the target type.  We want to
+    // ensure that these lifetimes are shorter than all lifetimes that are in
+    // the source type.  See test `src/test/compile-fail/regions-trait-2.rs`
+    let mut target_regions = ~[];
+    ty::walk_regions_and_ty(
+        cx.tcx,
+        target_ty,
+        |r| {
+            if !r.is_bound() {
+                target_regions.push(r);
+            }
+        },
+        |_| true);
 
     // Check, based on the region associated with the trait, whether it can
     // possibly escape the enclosing fn item (note that all type parameters
-    // must have been declared on the enclosing fn item):
-    match target_substs.self_r {
-      Some(ty::re_scope(*)) => { return; /* case (1) */ }
-      None | Some(ty::re_static) | Some(ty::re_free(*)) => {}
-      Some(ty::re_bound(*)) | Some(ty::re_infer(*)) => {
-        cx.tcx.sess.span_bug(
-            source.span,
-            fmt!("bad region found in kind: %?", target_substs.self_r));
-      }
+    // must have been declared on the enclosing fn item).
+    if target_regions.any(|r| is_re_scope(*r)) {
+        return; /* case (1) */
     }
 
     // Assuming the trait instance can escape, then ensure that each parameter
-    // either appears in the trait type or is owned:
+    // either appears in the trait type or is owned.
     let target_params = ty::param_tys_in_type(target_ty);
     let source_ty = ty::expr_ty(cx.tcx, source);
-    do ty::walk_ty(source_ty) |ty| {
-        match ty::get(ty).sty {
-          ty::ty_param(source_param) => {
-            if target_params.contains(&source_param) {
-                /* case (2) */
-            } else {
-                check_durable(cx.tcx, ty, source.span); /* case (3) */
+    ty::walk_regions_and_ty(
+        cx.tcx,
+        source_ty,
+
+        |_r| {
+            // FIXME(#5723) --- turn this check on once &Objects are usable
+            //
+            // if !target_regions.any(|t_r| is_subregion_of(cx, *t_r, r)) {
+            //     cx.tcx.sess.span_err(
+            //         source.span,
+            //         fmt!("source contains borrowed pointer with lifetime \
+            //               not found in the target type `%s`",
+            //              ty_to_str(cx.tcx, target_ty)));
+            //     note_and_explain_region(
+            //         cx.tcx, "source data is only valid for ", r, "");
+            // }
+        },
+
+        |ty| {
+            match ty::get(ty).sty {
+                ty::ty_param(source_param) => {
+                    if target_params.contains(&source_param) {
+                        /* case (2) */
+                    } else {
+                        check_durable(cx.tcx, ty, source.span); /* case (3) */
+                    }
+                }
+                _ => {}
             }
-          }
-          _ => {}
+            true
+        });
+
+    fn is_re_scope(+r: ty::Region) -> bool {
+        match r {
+            ty::re_scope(*) => true,
+            _ => false
         }
     }
+
+    fn is_subregion_of(cx: Context, r_sub: ty::Region, r_sup: ty::Region) -> bool {
+        cx.tcx.region_maps.is_subregion_of(r_sub, r_sup)
+    }
 }
 
 /// Ensures that values placed into a ~Trait are copyable and sendable.
diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index 50c193ab3b0..ecb9fc2cd08 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -11,7 +11,7 @@
 /*!
 
 This file actually contains two passes related to regions.  The first
-pass builds up the `region_map`, which describes the parent links in
+pass builds up the `scope_map`, which describes the parent links in
 the region hierarchy.  The second pass infers which types must be
 region parameterized.
 
@@ -23,7 +23,7 @@ use driver::session::Session;
 use metadata::csearch;
 use middle::resolve;
 use middle::ty::{region_variance, rv_covariant, rv_invariant};
-use middle::ty::{rv_contravariant};
+use middle::ty::{rv_contravariant, FreeRegion};
 use middle::ty;
 
 use core::hashmap::{HashMap, HashSet};
@@ -37,23 +37,31 @@ use syntax::{ast, visit};
 pub type parent = Option<ast::node_id>;
 
 /**
-Encodes the bounding lifetime for a given AST node:
-
-- Expressions are mapped to the expression or block encoding the maximum
-  (static) lifetime of a value produced by that expression.  This is
-  generally the innermost call, statement, match, or block.
-
-- Variables and bindings are mapped to the block in which they are declared.
-
+The region maps encode information about region relationships.
+
+- `scope_map` maps from:
+  - an expression to the expression or block encoding the maximum
+    (static) lifetime of a value produced by that expression.  This is
+    generally the innermost call, statement, match, or block.
+  - a variable or binding id to the block in which that variable is declared.
+- `free_region_map` maps from:
+  - a free region `a` to a list of free regions `bs` such that
+    `a <= b for all b in bs`
+  - the free region map is populated during type check as we check
+    each function. See the function `relate_free_regions` for
+    more information.
 */
-pub type region_map = @mut HashMap<ast::node_id, ast::node_id>;
+pub struct RegionMaps {
+    priv scope_map: HashMap<ast::node_id, ast::node_id>,
+    priv free_region_map: HashMap<FreeRegion, ~[FreeRegion]>,
+}
 
 pub struct ctxt {
     sess: Session,
     def_map: resolve::DefMap,
 
     // Generated maps:
-    region_map: region_map,
+    region_maps: @mut RegionMaps,
 
     // Generally speaking, expressions are parented to their innermost
     // enclosing block. But some kinds of expressions serve as
@@ -98,94 +106,215 @@ pub struct ctxt {
     parent: parent,
 }
 
-/// Returns true if `subscope` is equal to or is lexically nested inside
-/// `superscope` and false otherwise.
-pub fn scope_contains(region_map: region_map, superscope: ast::node_id,
-                      subscope: ast::node_id) -> bool {
-    let mut subscope = subscope;
-    while superscope != subscope {
-        match region_map.find(&subscope) {
-            None => return false,
-            Some(&scope) => subscope = scope
+pub impl RegionMaps {
+    fn relate_free_regions(&mut self,
+                           sub: FreeRegion,
+                           sup: FreeRegion)
+    {
+        match self.free_region_map.find_mut(&sub) {
+            Some(sups) => {
+                if !sups.contains(&sup) {
+                    sups.push(sup);
+                }
+                return;
+            }
+            None => {}
         }
+
+        debug!("relate_free_regions(sub=%?, sup=%?)", sub, sup);
+
+        self.free_region_map.insert(sub, ~[sup]);
     }
-    return true;
-}
 
-/// Determines whether one region is a subregion of another.  This is
-/// intended to run *after inference* and sadly the logic is somewhat
-/// duplicated with the code in infer.rs.
-pub fn is_subregion_of(region_map: region_map,
-                       sub_region: ty::Region,
-                       super_region: ty::Region) -> bool {
-    sub_region == super_region ||
-        match (sub_region, super_region) {
-            (_, ty::re_static) => {
-                true
-            }
+    fn record_parent(&mut self,
+                     sub: ast::node_id,
+                     sup: ast::node_id)
+    {
+        debug!("record_parent(sub=%?, sup=%?)", sub, sup);
 
-            (ty::re_scope(sub_scope), ty::re_scope(super_scope)) |
-            (ty::re_scope(sub_scope), ty::re_free(super_scope, _)) => {
-                scope_contains(region_map, super_scope, sub_scope)
-            }
+        self.scope_map.insert(sub, sup);
+    }
 
-            _ => {
-                false
+    fn opt_encl_scope(&self,
+                      id: ast::node_id) -> Option<ast::node_id>
+    {
+        //! Returns the narrowest scope that encloses `id`, if any.
+
+        self.scope_map.find(&id).map(|&x| *x)
+    }
+
+    fn encl_scope(&self,
+                  id: ast::node_id) -> ast::node_id
+    {
+        //! Returns the narrowest scope that encloses `id`, if any.
+
+        match self.scope_map.find(&id) {
+            Some(&r) => r,
+            None => { fail!(fmt!("No enclosing scope for id %?", id)); }
+        }
+    }
+
+    fn encl_region(&self,
+                   id: ast::node_id) -> ty::Region
+    {
+        //! Returns the narrowest scope region that encloses `id`, if any.
+
+        ty::re_scope(self.encl_scope(id))
+    }
+
+    fn is_sub_scope(&self,
+                    sub_scope: ast::node_id,
+                    superscope: ast::node_id) -> bool
+    {
+        /*!
+         * Returns true if `sub_scope` is equal to or is lexically
+         * nested inside `superscope` and false otherwise.
+         */
+
+        let mut sub_scope = sub_scope;
+        while superscope != sub_scope {
+            match self.scope_map.find(&sub_scope) {
+                None => return false,
+                Some(&scope) => sub_scope = scope
             }
         }
-}
+        return true;
+    }
 
-/// Finds the nearest common ancestor (if any) of two scopes.  That
-/// is, finds the smallest scope which is greater than or equal to
-/// both `scope_a` and `scope_b`.
-pub fn nearest_common_ancestor(region_map: region_map,
-                               scope_a: ast::node_id,
-                               scope_b: ast::node_id)
-                            -> Option<ast::node_id> {
+    fn sub_free_region(&self,
+                       sub: FreeRegion,
+                       sup: FreeRegion) -> bool
+    {
+        /*!
+         * Determines whether two free regions have a subregion relationship
+         * by walking the graph encoded in `free_region_map`.  Note that
+         * it is possible that `sub != sup` and `sub <= sup` and `sup <= sub`
+         * (that is, the user can give two different names to the same lifetime).
+         */
+
+        if sub == sup {
+            return true;
+        }
 
-    fn ancestors_of(region_map: region_map, scope: ast::node_id)
-                    -> ~[ast::node_id] {
-        let mut result = ~[scope];
-        let mut scope = scope;
-        loop {
-            match region_map.find(&scope) {
-                None => return result,
-                Some(&superscope) => {
-                    result.push(superscope);
-                    scope = superscope;
+        // Do a little breadth-first-search here.  The `queue` list
+        // doubles as a way to detect if we've seen a particular FR
+        // before.  Note that we expect this graph to be an *extremely
+        // shallow* tree.
+        let mut queue = ~[sub];
+        let mut i = 0;
+        while i < queue.len() {
+            match self.free_region_map.find(&queue[i]) {
+                Some(parents) => {
+                    for parents.each |parent| {
+                        if *parent == sup {
+                            return true;
+                        }
+
+                        if !queue.contains(parent) {
+                            queue.push(*parent);
+                        }
+                    }
                 }
+                None => {}
             }
+            i += 1;
         }
+        return false;
     }
 
-    if scope_a == scope_b { return Some(scope_a); }
+    fn is_subregion_of(&self,
+                       sub_region: ty::Region,
+                       super_region: ty::Region) -> bool
+    {
+        /*!
+         * Determines whether one region is a subregion of another.  This is
+         * intended to run *after inference* and sadly the logic is somewhat
+         * duplicated with the code in infer.rs.
+         */
+
+        debug!("is_subregion_of(sub_region=%?, super_region=%?)",
+               sub_region, super_region);
+
+        sub_region == super_region || {
+            match (sub_region, super_region) {
+                (_, ty::re_static) => {
+                    true
+                }
 
-    let a_ancestors = ancestors_of(region_map, scope_a);
-    let b_ancestors = ancestors_of(region_map, scope_b);
-    let mut a_index = vec::len(a_ancestors) - 1u;
-    let mut b_index = vec::len(b_ancestors) - 1u;
+                (ty::re_scope(sub_scope), ty::re_scope(super_scope)) => {
+                    self.is_sub_scope(sub_scope, super_scope)
+                }
 
-    // Here, ~[ab]_ancestors is a vector going from narrow to broad.
-    // The end of each vector will be the item where the scope is
-    // defined; if there are any common ancestors, then the tails of
-    // the vector will be the same.  So basically we want to walk
-    // backwards from the tail of each vector and find the first point
-    // where they diverge.  If one vector is a suffix of the other,
-    // then the corresponding scope is a superscope of the other.
+                (ty::re_scope(sub_scope), ty::re_free(ref fr)) => {
+                    self.is_sub_scope(sub_scope, fr.scope_id)
+                }
+
+                (ty::re_free(sub_fr), ty::re_free(super_fr)) => {
+                    self.sub_free_region(sub_fr, super_fr)
+                }
 
-    if a_ancestors[a_index] != b_ancestors[b_index] {
-        return None;
+                _ => {
+                    false
+                }
+            }
+        }
     }
 
-    loop {
-        // Loop invariant: a_ancestors[a_index] == b_ancestors[b_index]
-        // for all indices between a_index and the end of the array
-        if a_index == 0u { return Some(scope_a); }
-        if b_index == 0u { return Some(scope_b); }
-        a_index -= 1u;
-        b_index -= 1u;
+    fn nearest_common_ancestor(&self,
+                               scope_a: ast::node_id,
+                               scope_b: ast::node_id) -> Option<ast::node_id>
+    {
+        /*!
+         * Finds the nearest common ancestor (if any) of two scopes.  That
+         * is, finds the smallest scope which is greater than or equal to
+         * both `scope_a` and `scope_b`.
+         */
+
+        if scope_a == scope_b { return Some(scope_a); }
+
+        let a_ancestors = ancestors_of(self, scope_a);
+        let b_ancestors = ancestors_of(self, scope_b);
+        let mut a_index = vec::len(a_ancestors) - 1u;
+        let mut b_index = vec::len(b_ancestors) - 1u;
+
+        // Here, ~[ab]_ancestors is a vector going from narrow to broad.
+        // The end of each vector will be the item where the scope is
+        // defined; if there are any common ancestors, then the tails of
+        // the vector will be the same.  So basically we want to walk
+        // backwards from the tail of each vector and find the first point
+        // where they diverge.  If one vector is a suffix of the other,
+        // then the corresponding scope is a superscope of the other.
+
         if a_ancestors[a_index] != b_ancestors[b_index] {
-            return Some(a_ancestors[a_index + 1u]);
+            return None;
+        }
+
+        loop {
+            // Loop invariant: a_ancestors[a_index] == b_ancestors[b_index]
+            // for all indices between a_index and the end of the array
+            if a_index == 0u { return Some(scope_a); }
+            if b_index == 0u { return Some(scope_b); }
+            a_index -= 1u;
+            b_index -= 1u;
+            if a_ancestors[a_index] != b_ancestors[b_index] {
+                return Some(a_ancestors[a_index + 1u]);
+            }
+        }
+
+        fn ancestors_of(self: &RegionMaps, scope: ast::node_id)
+            -> ~[ast::node_id]
+        {
+            let mut result = ~[scope];
+            let mut scope = scope;
+            loop {
+                match self.scope_map.find(&scope) {
+                    None => return result,
+                    Some(&superscope) => {
+                        result.push(superscope);
+                        scope = superscope;
+                    }
+                }
+            }
         }
     }
 }
@@ -205,8 +334,7 @@ pub fn parent_id(cx: ctxt, span: span) -> ast::node_id {
 /// Records the current parent (if any) as the parent of `child_id`.
 pub fn record_parent(cx: ctxt, child_id: ast::node_id) {
     for cx.parent.each |parent_id| {
-        debug!("parent of node %d is node %d", child_id, *parent_id);
-        cx.region_map.insert(child_id, *parent_id);
+        cx.region_maps.record_parent(child_id, *parent_id);
     }
 }
 
@@ -328,7 +456,7 @@ pub fn resolve_fn(fk: &visit::fn_kind,
     // Record the ID of `self`.
     match *fk {
         visit::fk_method(_, _, method) => {
-            cx.region_map.insert(method.self_id, body.node.id);
+            cx.region_maps.record_parent(method.self_id, body.node.id);
         }
         _ => {}
     }
@@ -338,7 +466,7 @@ pub fn resolve_fn(fk: &visit::fn_kind,
            body.node.id, cx.parent, fn_cx.parent);
 
     for decl.inputs.each |input| {
-        cx.region_map.insert(input.id, body.node.id);
+        cx.region_maps.record_parent(input.id, body.node.id);
     }
 
     visit::visit_fn(fk, decl, body, sp, id, fn_cx, visitor);
@@ -346,11 +474,15 @@ pub fn resolve_fn(fk: &visit::fn_kind,
 
 pub fn resolve_crate(sess: Session,
                      def_map: resolve::DefMap,
-                     crate: @ast::crate)
-                  -> region_map {
+                     crate: @ast::crate) -> @mut RegionMaps
+{
+    let region_maps = @mut RegionMaps {
+        scope_map: HashMap::new(),
+        free_region_map: HashMap::new()
+    };
     let cx: ctxt = ctxt {sess: sess,
                          def_map: def_map,
-                         region_map: @mut HashMap::new(),
+                         region_maps: region_maps,
                          root_exprs: @mut HashSet::new(),
                          parent: None};
     let visitor = visit::mk_vt(@visit::Visitor {
@@ -365,7 +497,7 @@ pub fn resolve_crate(sess: Session,
         .. *visit::default_visitor()
     });
     visit::visit_crate(*crate, cx, visitor);
-    return cx.region_map;
+    return region_maps;
 }
 
 // ___________________________________________________________________________
@@ -412,10 +544,6 @@ pub struct DetermineRpCtxt {
     // see long discussion on region_is_relevant().
     anon_implies_rp: bool,
 
-    // true when we are not within an &self method.
-    // see long discussion on region_is_relevant().
-    self_implies_rp: bool,
-
     // encodes the context of the current type; invariant if
     // mutable, covariant otherwise
     ambient_variance: region_variance,
@@ -557,7 +685,7 @@ pub impl DetermineRpCtxt {
                 false
             }
             Some(ref l) if l.ident == special_idents::self_ => {
-                self.self_implies_rp
+                true
             }
             Some(_) => {
                 false
@@ -568,23 +696,18 @@ pub impl DetermineRpCtxt {
     fn with(@mut self,
             item_id: ast::node_id,
             anon_implies_rp: bool,
-            self_implies_rp: bool,
             f: &fn()) {
         let old_item_id = self.item_id;
         let old_anon_implies_rp = self.anon_implies_rp;
-        let old_self_implies_rp = self.self_implies_rp;
         self.item_id = item_id;
         self.anon_implies_rp = anon_implies_rp;
-        self.self_implies_rp = self_implies_rp;
-        debug!("with_item_id(%d, %b, %b)",
+        debug!("with_item_id(%d, %b)",
                item_id,
-               anon_implies_rp,
-               self_implies_rp);
+               anon_implies_rp);
         let _i = ::util::common::indenter();
         f();
         self.item_id = old_item_id;
         self.anon_implies_rp = old_anon_implies_rp;
-        self.self_implies_rp = old_self_implies_rp;
     }
 
     fn with_ambient_variance(@mut self, variance: region_variance, f: &fn()) {
@@ -598,7 +721,7 @@ pub impl DetermineRpCtxt {
 pub fn determine_rp_in_item(item: @ast::item,
                             &&cx: @mut DetermineRpCtxt,
                             visitor: visit::vt<@mut DetermineRpCtxt>) {
-    do cx.with(item.id, true, true) {
+    do cx.with(item.id, true) {
         visit::visit_item(item, cx, visitor);
     }
 }
@@ -610,12 +733,7 @@ pub fn determine_rp_in_fn(fk: &visit::fn_kind,
                           _: ast::node_id,
                           &&cx: @mut DetermineRpCtxt,
                           visitor: visit::vt<@mut DetermineRpCtxt>) {
-    let self_implies_rp = match fk {
-        &visit::fk_method(_, _, m) => !m.self_ty.node.is_borrowed(),
-        _ => true
-    };
-
-    do cx.with(cx.item_id, false, self_implies_rp) {
+    do cx.with(cx.item_id, false) {
         do cx.with_ambient_variance(rv_contravariant) {
             for decl.inputs.each |a| {
                 (visitor.visit_ty)(a.ty, cx, visitor);
@@ -631,7 +749,7 @@ pub fn determine_rp_in_fn(fk: &visit::fn_kind,
 pub fn determine_rp_in_ty_method(ty_m: &ast::ty_method,
                                  &&cx: @mut DetermineRpCtxt,
                                  visitor: visit::vt<@mut DetermineRpCtxt>) {
-    do cx.with(cx.item_id, false, !ty_m.self_ty.node.is_borrowed()) {
+    do cx.with(cx.item_id, false) {
         visit::visit_ty_method(ty_m, cx, visitor);
     }
 }
@@ -736,7 +854,7 @@ pub fn determine_rp_in_ty(ty: @ast::Ty,
       ast::ty_bare_fn(@ast::TyBareFn {decl: ref decl, _}) => {
         // fn() binds the & region, so do not consider &T types that
         // appear *inside* a fn() type to affect the enclosing item:
-        do cx.with(cx.item_id, false, true) {
+        do cx.with(cx.item_id, false) {
             // parameters are contravariant
             do cx.with_ambient_variance(rv_contravariant) {
                 for decl.inputs.each |a| {
@@ -797,7 +915,6 @@ pub fn determine_rp_in_crate(sess: Session,
         worklist: ~[],
         item_id: 0,
         anon_implies_rp: false,
-        self_implies_rp: true,
         ambient_variance: rv_covariant
     };
 
diff --git a/src/librustc/middle/subst.rs b/src/librustc/middle/subst.rs
index a754f93f010..35257f9574c 100644
--- a/src/librustc/middle/subst.rs
+++ b/src/librustc/middle/subst.rs
@@ -62,22 +62,7 @@ impl EffectfulSubst for ty::t {
             _ => {
                 ty::fold_regions_and_ty(
                     tcx, *self,
-                    |r| match r {
-                        ty::re_bound(ty::br_self) => {
-                            match substs.self_r {
-                                None => {
-                                    tcx.sess.bug(
-                                        fmt!("ty::subst: \
-                                              Reference to self region when \
-                                              given substs with no self region, \
-                                              ty = %s",
-                                             self.repr(tcx)));
-                                }
-                                Some(self_r) => self_r
-                            }
-                        }
-                        _ => r
-                    },
+                    |r| r.subst(tcx, substs),
                     |t| t.effectfulSubst(tcx, substs),
                     |t| t.effectfulSubst(tcx, substs))
             }
@@ -118,7 +103,7 @@ impl Subst for ty::TraitRef {
 impl Subst for ty::substs {
     fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::substs {
         ty::substs {
-            self_r: self.self_r,
+            self_r: self.self_r.subst(tcx, substs),
             self_ty: self.self_ty.map(|typ| typ.subst(tcx, substs)),
             tps: self.tps.map(|typ| typ.subst(tcx, substs))
         }
@@ -166,6 +151,34 @@ impl Subst for ty::Generics {
     }
 }
 
+impl Subst for ty::Region {
+    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::Region {
+        // Note: This routine only handles the self region, because it
+        // is only concerned with substitutions of regions that appear
+        // in types. Region substitution of the bound regions that
+        // appear in a function signature is done using the
+        // specialized routine
+        // `middle::typeck::check::regionmanip::replace_bound_regions_in_fn_sig()`.
+        // As we transition to the new region syntax this distinction
+        // will most likely disappear.
+        match self {
+            &ty::re_bound(ty::br_self) => {
+                match substs.self_r {
+                    None => {
+                        tcx.sess.bug(
+                            fmt!("ty::Region#subst(): \
+                                  Reference to self region when \
+                                  given substs with no self region: %s",
+                                 substs.repr(tcx)));
+                    }
+                    Some(self_r) => self_r
+                }
+            }
+            _ => *self
+        }
+    }
+}
+
 impl Subst for ty::ty_param_bounds_and_ty {
     fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::ty_param_bounds_and_ty {
         ty::ty_param_bounds_and_ty {
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 335c9824354..a26c1c1e766 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -24,8 +24,7 @@ use middle::subst::Subst;
 use middle::typeck;
 use middle;
 use util::ppaux::{note_and_explain_region, bound_region_to_str};
-use util::ppaux::{region_to_str, vstore_to_str};
-use util::ppaux::{trait_store_to_str, ty_to_str, tys_to_str};
+use util::ppaux::{trait_store_to_str, ty_to_str, vstore_to_str};
 use util::ppaux::Repr;
 use util::common::{indenter};
 
@@ -241,7 +240,7 @@ struct ctxt_ {
     sess: session::Session,
     def_map: resolve::DefMap,
 
-    region_map: middle::region::region_map,
+    region_maps: @mut middle::region::RegionMaps,
     region_paramd_items: middle::region::region_paramd_items,
 
     // Stores the types for various nodes in the AST.  Note that this table
@@ -411,7 +410,7 @@ pub struct param_ty {
 /// Representation of regions:
 #[auto_encode]
 #[auto_decode]
-#[deriving(Eq)]
+#[deriving(Eq, IterBytes)]
 pub enum Region {
     /// Bound regions are found (primarily) in function types.  They indicate
     /// region parameters that have yet to be replaced with actual regions
@@ -427,7 +426,7 @@ pub enum Region {
     /// When checking a function body, the types of all arguments and so forth
     /// that refer to bound region parameters are modified to refer to free
     /// region parameters.
-    re_free(node_id, bound_region),
+    re_free(FreeRegion),
 
     /// A concrete region naming some expression within the current function.
     re_scope(node_id),
@@ -439,9 +438,26 @@ pub enum Region {
     re_infer(InferRegion)
 }
 
+pub impl Region {
+    fn is_bound(&self) -> bool {
+        match self {
+            &re_bound(*) => true,
+            _ => false
+        }
+    }
+}
+
 #[auto_encode]
 #[auto_decode]
-#[deriving(Eq)]
+#[deriving(Eq, IterBytes)]
+pub struct FreeRegion {
+    scope_id: node_id,
+    bound_region: bound_region
+}
+
+#[auto_encode]
+#[auto_decode]
+#[deriving(Eq, IterBytes)]
 pub enum bound_region {
     /// The self region for structs, impls (&T in a type defn or &'self T)
     br_self,
@@ -811,7 +827,7 @@ pub fn mk_ctxt(s: session::Session,
                dm: resolve::DefMap,
                amap: ast_map::map,
                freevars: freevars::freevar_map,
-               region_map: middle::region::region_map,
+               region_maps: @mut middle::region::RegionMaps,
                region_paramd_items: middle::region::region_paramd_items,
                +lang_items: middle::lang_items::LanguageItems,
                crate: @ast::crate)
@@ -838,7 +854,7 @@ pub fn mk_ctxt(s: session::Session,
         cstore: s.cstore,
         sess: s,
         def_map: dm,
-        region_map: region_map,
+        region_maps: region_maps,
         region_paramd_items: region_paramd_items,
         node_types: @mut SmallIntMap::new(),
         node_type_substs: @mut HashMap::new(),
@@ -1177,15 +1193,6 @@ pub fn default_arg_mode_for_ty(tcx: ctxt, ty: ty::t) -> ast::rmode {
     }
 }
 
-// Returns the narrowest lifetime enclosing the evaluation of the expression
-// with id `id`.
-pub fn encl_region(cx: ctxt, id: ast::node_id) -> ty::Region {
-    match cx.region_map.find(&id) {
-      Some(&encl_scope) => ty::re_scope(encl_scope),
-      None => ty::re_static
-    }
-}
-
 pub fn walk_ty(ty: t, f: &fn(t)) {
     maybe_walk_ty(ty, |t| { f(t); true });
 }
@@ -1309,8 +1316,8 @@ pub fn walk_regions_and_ty(
         fold_regions_and_ty(
             cx, ty,
             |r| { walkr(r); r },
-            |t| { walkt(t); walk_regions_and_ty(cx, t, walkr, walkt); t },
-            |t| { walkt(t); walk_regions_and_ty(cx, t, walkr, walkt); t });
+            |t| { walk_regions_and_ty(cx, t, walkr, walkt); t },
+            |t| { walk_regions_and_ty(cx, t, walkr, walkt); t });
     }
 }
 
@@ -2507,43 +2514,52 @@ pub fn index_sty(cx: ctxt, sty: &sty) -> Option<mt> {
     }
 }
 
-impl to_bytes::IterBytes for bound_region {
-    fn iter_bytes(&self, +lsb0: bool, f: to_bytes::Cb) {
-        match *self {
-          ty::br_self => 0u8.iter_bytes(lsb0, f),
-
-          ty::br_anon(ref idx) =>
-          to_bytes::iter_bytes_2(&1u8, idx, lsb0, f),
-
-          ty::br_named(ref ident) =>
-          to_bytes::iter_bytes_2(&2u8, ident, lsb0, f),
+/**
+ * Enforces an arbitrary but consistent total ordering over
+ * free regions.  This is needed for establishing a consistent
+ * LUB in region_inference. */
+impl cmp::TotalOrd for FreeRegion {
+    fn cmp(&self, other: &FreeRegion) -> Ordering {
+        cmp::cmp2(&self.scope_id, &self.bound_region,
+                  &other.scope_id, &other.bound_region)
+    }
+}
 
-          ty::br_cap_avoid(ref id, ref br) =>
-          to_bytes::iter_bytes_3(&3u8, id, br, lsb0, f),
+impl cmp::TotalEq for FreeRegion {
+    fn equals(&self, other: &FreeRegion) -> bool {
+        *self == *other
+    }
+}
 
-          ty::br_fresh(ref x) =>
-          to_bytes::iter_bytes_2(&4u8, x, lsb0, f)
+/**
+ * Enforces an arbitrary but consistent total ordering over
+ * bound regions.  This is needed for establishing a consistent
+ * LUB in region_inference. */
+impl cmp::TotalOrd for bound_region {
+    fn cmp(&self, other: &bound_region) -> Ordering {
+        match (self, other) {
+            (&ty::br_self, &ty::br_self) => cmp::Equal,
+            (&ty::br_self, _) => cmp::Less,
+
+            (&ty::br_anon(ref a1), &ty::br_anon(ref a2)) => a1.cmp(a2),
+            (&ty::br_anon(*), _) => cmp::Less,
+
+            (&ty::br_named(ref a1), &ty::br_named(ref a2)) => a1.repr.cmp(&a2.repr),
+            (&ty::br_named(*), _) => cmp::Less,
+
+            (&ty::br_cap_avoid(ref a1, @ref b1),
+             &ty::br_cap_avoid(ref a2, @ref b2)) => cmp::cmp2(a1, b1, a2, b2),
+            (&ty::br_cap_avoid(*), _) => cmp::Less,
+
+            (&ty::br_fresh(ref a1), &ty::br_fresh(ref a2)) => a1.cmp(a2),
+            (&ty::br_fresh(*), _) => cmp::Less,
         }
     }
 }
 
-impl to_bytes::IterBytes for Region {
-    fn iter_bytes(&self, +lsb0: bool, f: to_bytes::Cb) {
-        match *self {
-          re_bound(ref br) =>
-          to_bytes::iter_bytes_2(&0u8, br, lsb0, f),
-
-          re_free(ref id, ref br) =>
-          to_bytes::iter_bytes_3(&1u8, id, br, lsb0, f),
-
-          re_scope(ref id) =>
-          to_bytes::iter_bytes_2(&2u8, id, lsb0, f),
-
-          re_infer(ref id) =>
-          to_bytes::iter_bytes_2(&3u8, id, lsb0, f),
-
-          re_static => 4u8.iter_bytes(lsb0, f)
-        }
+impl cmp::TotalEq for bound_region {
+    fn equals(&self, other: &bound_region) -> bool {
+        *self == *other
     }
 }
 
@@ -2857,8 +2873,17 @@ pub fn expr_ty_adjusted(cx: ctxt, expr: @ast::expr) -> t {
      */
 
     let unadjusted_ty = expr_ty(cx, expr);
+    adjust_ty(cx, expr.span, unadjusted_ty, cx.adjustments.find(&expr.id))
+}
+
+pub fn adjust_ty(cx: ctxt,
+                 span: span,
+                 unadjusted_ty: ty::t,
+                 adjustment: Option<&@AutoAdjustment>) -> ty::t
+{
+    /*! See `expr_ty_adjusted` */
 
-    return match cx.adjustments.find(&expr.id) {
+    return match adjustment {
         None => unadjusted_ty,
 
         Some(&@AutoAddEnv(r, s)) => {
@@ -2887,7 +2912,7 @@ pub fn expr_ty_adjusted(cx: ctxt, expr: @ast::expr) -> t {
                     Some(mt) => { adjusted_ty = mt.ty; }
                     None => {
                         cx.sess.span_bug(
-                            expr.span,
+                            span,
                             fmt!("The %uth autoderef failed: %s",
                                  i, ty_to_str(cx,
                                               adjusted_ty)));
@@ -2906,18 +2931,18 @@ pub fn expr_ty_adjusted(cx: ctxt, expr: @ast::expr) -> t {
                         }
 
                         AutoBorrowVec => {
-                            borrow_vec(cx, expr, autoref, adjusted_ty)
+                            borrow_vec(cx, span, autoref, adjusted_ty)
                         }
 
                         AutoBorrowVecRef => {
-                            adjusted_ty = borrow_vec(cx, expr, autoref,
+                            adjusted_ty = borrow_vec(cx, span, autoref,
                                                      adjusted_ty);
                             mk_rptr(cx, autoref.region,
                                     mt {ty: adjusted_ty, mutbl: ast::m_imm})
                         }
 
                         AutoBorrowFn => {
-                            borrow_fn(cx, expr, autoref, adjusted_ty)
+                            borrow_fn(cx, span, autoref, adjusted_ty)
                         }
                     }
                 }
@@ -2925,7 +2950,7 @@ pub fn expr_ty_adjusted(cx: ctxt, expr: @ast::expr) -> t {
         }
     };
 
-    fn borrow_vec(cx: ctxt, expr: @ast::expr,
+    fn borrow_vec(cx: ctxt, span: span,
                   autoref: &AutoRef, ty: ty::t) -> ty::t {
         match get(ty).sty {
             ty_evec(mt, _) => {
@@ -2939,14 +2964,14 @@ pub fn expr_ty_adjusted(cx: ctxt, expr: @ast::expr) -> t {
 
             ref s => {
                 cx.sess.span_bug(
-                    expr.span,
+                    span,
                     fmt!("borrow-vec associated with bad sty: %?",
                          s));
             }
         }
     }
 
-    fn borrow_fn(cx: ctxt, expr: @ast::expr,
+    fn borrow_fn(cx: ctxt, span: span,
                  autoref: &AutoRef, ty: ty::t) -> ty::t {
         match get(ty).sty {
             ty_closure(ref fty) => {
@@ -2959,7 +2984,7 @@ pub fn expr_ty_adjusted(cx: ctxt, expr: @ast::expr) -> t {
 
             ref s => {
                 cx.sess.span_bug(
-                    expr.span,
+                    span,
                     fmt!("borrow-fn associated with bad sty: %?",
                          s));
             }
diff --git a/src/librustc/middle/typeck/check/method.rs b/src/librustc/middle/typeck/check/method.rs
index 6a274e7f9eb..6b09133e73a 100644
--- a/src/librustc/middle/typeck/check/method.rs
+++ b/src/librustc/middle/typeck/check/method.rs
@@ -178,15 +178,6 @@ pub struct Candidate {
     origin: method_origin,
 }
 
-/**
- * How the self type should be transformed according to the form of explicit
- * self provided by the method.
- */
-pub enum TransformTypeFlag {
-    TransformTypeNormally,
-    TransformTypeForObject,
-}
-
 pub impl<'self> LookupContext<'self> {
     fn do_lookup(&self, self_ty: ty::t) -> Option<method_map_entry> {
         let mut self_ty = structurally_resolved_type(self.fcx,
@@ -285,13 +276,13 @@ pub impl<'self> LookupContext<'self> {
 
     fn push_inherent_candidates(&self, self_ty: ty::t) {
         /*!
-         *
          * Collect all inherent candidates into
          * `self.inherent_candidates`.  See comment at the start of
          * the file.  To find the inherent candidates, we repeatedly
          * deref the self-ty to find the "base-type".  So, for
          * example, if the receiver is @@C where `C` is a struct type,
-         * we'll want to find the inherent impls for `C`. */
+         * we'll want to find the inherent impls for `C`.
+         */
 
         let mut enum_dids = ~[];
         let mut self_ty = self_ty;
@@ -407,16 +398,9 @@ pub impl<'self> LookupContext<'self> {
             };
             let method = trait_methods[pos];
 
-            let (rcvr_ty, rcvr_substs) =
-                self.create_rcvr_ty_and_substs_for_method(
-                    method.self_ty,
-                    rcvr_ty,
-                    copy bound_trait_ref.substs,
-                    TransformTypeNormally);
-
             let cand = Candidate {
                 rcvr_ty: rcvr_ty,
-                rcvr_substs: rcvr_substs,
+                rcvr_substs: copy bound_trait_ref.substs,
                 method_ty: method,
                 origin: method_param(
                     method_param {
@@ -476,14 +460,8 @@ pub impl<'self> LookupContext<'self> {
             ../*bad*/copy *substs
         };
 
-        let (rcvr_ty, rcvr_substs) =
-            self.create_rcvr_ty_and_substs_for_method(method.self_ty,
-                                                      self_ty,
-                                                      rcvr_substs,
-                                                      TransformTypeForObject);
-
         self.inherent_candidates.push(Candidate {
-            rcvr_ty: rcvr_ty,
+            rcvr_ty: self_ty,
             rcvr_substs: rcvr_substs,
             method_ty: method,
             origin: method_trait(did, index, store)
@@ -538,19 +516,13 @@ pub impl<'self> LookupContext<'self> {
                 // We've found a method -- return it
                 let rcvr_substs = substs {self_ty: Some(self_ty),
                                           ..copy *substs };
-                let (rcvr_ty, rcvr_substs) =
-                    self.create_rcvr_ty_and_substs_for_method(
-                        info.method_ty.self_ty,
-                        self_ty,
-                        rcvr_substs,
-                        TransformTypeNormally);
                 let origin = if did == info.trait_def_id {
                     method_self(info.trait_def_id, info.index)
                 } else {
                     method_super(info.trait_def_id, info.index)
                 };
                 self.inherent_candidates.push(Candidate {
-                    rcvr_ty: rcvr_ty,
+                    rcvr_ty: self_ty,
                     rcvr_substs: rcvr_substs,
                     method_ty: info.method_ty,
                     origin: origin
@@ -598,13 +570,6 @@ pub impl<'self> LookupContext<'self> {
             ty: impl_ty
         } = impl_self_ty(&vcx, location_info, impl_info.did);
 
-        let (impl_ty, impl_substs) =
-            self.create_rcvr_ty_and_substs_for_method(
-                method.self_ty,
-                impl_ty,
-                impl_substs,
-                TransformTypeNormally);
-
         candidates.push(Candidate {
             rcvr_ty: impl_ty,
             rcvr_substs: impl_substs,
@@ -639,69 +604,16 @@ pub impl<'self> LookupContext<'self> {
                 self_ty: None,
                 tps: ~[]
             };
-            let (impl_ty, impl_substs) =
-                self.create_rcvr_ty_and_substs_for_method(
-                    method.self_ty,
-                    self_ty,
-                    dummy_substs,
-                    TransformTypeNormally);
 
             candidates.push(Candidate {
-                rcvr_ty: impl_ty,
-                rcvr_substs: impl_substs,
+                rcvr_ty: self_ty,
+                rcvr_substs: dummy_substs,
                 method_ty: method,
                 origin: method_static(provided_method_info.method_info.did)
             });
         }
     }
 
-    fn create_rcvr_ty_and_substs_for_method(&self,
-                                            self_decl: ast::self_ty_,
-                                            self_ty: ty::t,
-                                            +self_substs: ty::substs,
-                                            transform_type: TransformTypeFlag)
-                                         -> (ty::t, ty::substs) {
-        // If the self type includes a region (like &self), we need to
-        // ensure that the receiver substitutions have a self region.
-        // If the receiver type does not itself contain borrowed
-        // pointers, there may not be one yet.
-        //
-        // FIXME(#3446)--this awkward situation comes about because
-        // the regions in the receiver are substituted before (and
-        // differently from) those in the argument types.  This
-        // shouldn't really have to be.
-        let rcvr_substs = {
-            match self_decl {
-                sty_static | sty_value |
-                sty_box(_) | sty_uniq(_) => {
-                    self_substs
-                }
-                sty_region(*) if self_substs.self_r.is_some() => {
-                    // FIXME(#4846) ignoring expl lifetime here
-                    self_substs
-                }
-                sty_region(*) => {
-                    // FIXME(#4846) ignoring expl lifetime here
-                    substs {
-                        self_r:
-                             Some(self.infcx().next_region_var(
-                                 self.expr.span,
-                                 self.expr.id)),
-                        ..self_substs
-                    }
-                }
-            }
-        };
-
-        let rcvr_ty = transform_self_type_for_method(self.tcx(),
-                                                     rcvr_substs.self_r,
-                                                     self_ty,
-                                                     self_decl,
-                                                     transform_type);
-
-        (rcvr_ty, rcvr_substs)
-    }
-
     // ______________________________________________________________________
     // Candidate selection (see comment at start of file)
 
@@ -1036,20 +948,34 @@ pub impl<'self> LookupContext<'self> {
         self.enforce_trait_instance_limitations(fty, candidate);
         self.enforce_drop_trait_limitations(candidate);
 
-        // before we only checked whether self_ty could be a subtype
-        // of rcvr_ty; now we actually make it so (this may cause
-        // variables to unify etc).  Since we checked beforehand, and
-        // nothing has changed in the meantime, this unification
-        // should never fail.
-        match self.fcx.mk_subty(false, self.self_expr.span,
-                                self_ty, candidate.rcvr_ty) {
-            result::Ok(_) => (),
-            result::Err(_) => {
-                self.bug(fmt!("%s was assignable to %s but now is not?",
-                              self.ty_to_str(self_ty),
-                              self.ty_to_str(candidate.rcvr_ty)));
+        // static methods should never have gotten this far:
+        assert!(candidate.method_ty.self_ty != sty_static);
+
+        let transformed_self_ty = match candidate.origin {
+            method_trait(*) => {
+                match candidate.method_ty.self_ty {
+                    sty_region(*) => {
+                        // FIXME(#5762) again, preserving existing
+                        // behavior here which (for &self) desires
+                        // &@Trait where @Trait is the type of the
+                        // receiver.  Here we fetch the method's
+                        // transformed_self_ty which will be something
+                        // like &'a Self.  We then perform a
+                        // substitution which will replace Self with
+                        // @Trait.
+                        let t = candidate.method_ty.transformed_self_ty.get();
+                        ty::subst(tcx, &candidate.rcvr_substs, t)
+                    }
+                    _ => {
+                        candidate.rcvr_ty
+                    }
+                }
             }
-        }
+            _ => {
+                let t = candidate.method_ty.transformed_self_ty.get();
+                ty::subst(tcx, &candidate.rcvr_substs, t)
+            }
+        };
 
         // Determine the values for the type parameters of the method.
         // If they were not explicitly supplied, just construct fresh
@@ -1100,16 +1026,32 @@ pub impl<'self> LookupContext<'self> {
                     fmt!("Invoking method with non-bare-fn ty: %?", s));
             }
         };
-        let (_, _, fn_sig) =
+        let (_, opt_transformed_self_ty, fn_sig) =
             replace_bound_regions_in_fn_sig(
-                tcx, @Nil, None, &bare_fn_ty.sig,
+                tcx, @Nil, Some(transformed_self_ty), &bare_fn_ty.sig,
                 |_br| self.fcx.infcx().next_region_var(
                     self.expr.span, self.expr.id));
+        let transformed_self_ty = opt_transformed_self_ty.get();
         let fty = ty::mk_bare_fn(tcx, ty::BareFnTy {sig: fn_sig, ..bare_fn_ty});
         debug!("after replacing bound regions, fty=%s", self.ty_to_str(fty));
 
         let self_mode = get_mode_from_self_type(candidate.method_ty.self_ty);
 
+        // before we only checked whether self_ty could be a subtype
+        // of rcvr_ty; now we actually make it so (this may cause
+        // variables to unify etc).  Since we checked beforehand, and
+        // nothing has changed in the meantime, this unification
+        // should never fail.
+        match self.fcx.mk_subty(false, self.self_expr.span,
+                                self_ty, transformed_self_ty) {
+            result::Ok(_) => (),
+            result::Err(_) => {
+                self.bug(fmt!("%s was a subtype of %s but now is not?",
+                              self.ty_to_str(self_ty),
+                              self.ty_to_str(transformed_self_ty)));
+            }
+        }
+
         self.fcx.write_ty(self.callee_id, fty);
         self.fcx.write_substs(self.callee_id, all_substs);
         method_map_entry {
@@ -1180,7 +1122,87 @@ pub impl<'self> LookupContext<'self> {
         debug!("is_relevant(self_ty=%s, candidate=%s)",
                self.ty_to_str(self_ty), self.cand_to_str(candidate));
 
-        self.fcx.can_mk_subty(self_ty, candidate.rcvr_ty).is_ok()
+        // Check for calls to object methods.  We resolve these differently.
+        //
+        // FIXME(#5762)---we don't check that an @self method is only called
+        // on an @Trait object here and so forth
+        match candidate.origin {
+            method_trait(*) => {
+                match candidate.method_ty.self_ty {
+                    sty_static | sty_value => {
+                        return false;
+                    }
+                    sty_region(*) => {
+                        // just echoing current behavior here, which treats
+                        // an &self method on an @Trait object as requiring
+                        // an &@Trait receiver (wacky)
+                    }
+                    sty_box(*) | sty_uniq(*) => {
+                        return self.fcx.can_mk_subty(self_ty,
+                                                     candidate.rcvr_ty).is_ok();
+                    }
+                };
+            }
+            _ => {}
+        }
+
+        return match candidate.method_ty.self_ty {
+            sty_static => {
+                false
+            }
+
+            sty_value => {
+                self.fcx.can_mk_subty(self_ty, candidate.rcvr_ty).is_ok()
+            }
+
+            sty_region(_, m) => {
+                match ty::get(self_ty).sty {
+                    ty::ty_rptr(_, mt) => {
+                        mutability_matches(mt.mutbl, m) &&
+                        self.fcx.can_mk_subty(mt.ty, candidate.rcvr_ty).is_ok()
+                    }
+
+                    _ => false
+                }
+            }
+
+            sty_box(m) => {
+                match ty::get(self_ty).sty {
+                    ty::ty_box(mt) => {
+                        mutability_matches(mt.mutbl, m) &&
+                        self.fcx.can_mk_subty(mt.ty, candidate.rcvr_ty).is_ok()
+                    }
+
+                    _ => false
+                }
+            }
+
+            sty_uniq(m) => {
+                match ty::get(self_ty).sty {
+                    ty::ty_uniq(mt) => {
+                        mutability_matches(mt.mutbl, m) &&
+                        self.fcx.can_mk_subty(mt.ty, candidate.rcvr_ty).is_ok()
+                    }
+
+                    _ => false
+                }
+            }
+        };
+
+        fn mutability_matches(self_mutbl: ast::mutability,
+                              candidate_mutbl: ast::mutability) -> bool {
+            //! True if `self_mutbl <: candidate_mutbl`
+
+            match (self_mutbl, candidate_mutbl) {
+                (_, m_const) => true,
+                (m_mutbl, m_mutbl) => true,
+                (m_imm, m_imm) => true,
+                (m_mutbl, m_imm) => false,
+                (m_imm, m_mutbl) => false,
+                (m_const, m_imm) => false,
+                (m_const, m_mutbl) => false,
+            }
+        }
     }
 
     fn fn_ty_from_origin(&self, origin: &method_origin) -> ty::t {
@@ -1281,45 +1303,6 @@ pub impl<'self> LookupContext<'self> {
     }
 }
 
-pub fn transform_self_type_for_method(tcx: ty::ctxt,
-                                      self_region: Option<ty::Region>,
-                                      impl_ty: ty::t,
-                                      self_type: ast::self_ty_,
-                                      flag: TransformTypeFlag)
-                                   -> ty::t {
-    match self_type {
-      sty_static => {
-        tcx.sess.bug(~"calling transform_self_type_for_method on \
-                       static method");
-      }
-      sty_value => {
-        impl_ty
-      }
-      sty_region(_, mutability) => {
-        // FIXME(#4846) ignoring expl lifetime here
-        mk_rptr(tcx,
-                self_region.expect(~"self region missing for &self param"),
-                ty::mt { ty: impl_ty, mutbl: mutability })
-      }
-      sty_box(mutability) => {
-        match flag {
-            TransformTypeNormally => {
-                mk_box(tcx, ty::mt { ty: impl_ty, mutbl: mutability })
-            }
-            TransformTypeForObject => impl_ty
-        }
-      }
-      sty_uniq(mutability) => {
-        match flag {
-            TransformTypeNormally => {
-                mk_uniq(tcx, ty::mt { ty: impl_ty, mutbl: mutability })
-            }
-            TransformTypeForObject => impl_ty
-        }
-      }
-    }
-}
-
 pub fn get_mode_from_self_type(self_type: ast::self_ty_) -> ast::rmode {
     match self_type { sty_value => by_copy, _ => by_ref }
 }
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index 0eb2e5387c3..2d1c940103a 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -93,16 +93,15 @@ use middle::typeck::check::method::{AutoderefReceiver};
 use middle::typeck::check::method::{AutoderefReceiverFlag};
 use middle::typeck::check::method::{CheckTraitsAndInherentMethods};
 use middle::typeck::check::method::{CheckTraitsOnly, DontAutoderefReceiver};
-use middle::typeck::check::method::{TransformTypeNormally};
 use middle::typeck::check::regionmanip::replace_bound_regions_in_fn_sig;
+use middle::typeck::check::regionmanip::relate_free_regions;
 use middle::typeck::check::vtable::{LocationInfo, VtableContext};
 use middle::typeck::CrateCtxt;
 use middle::typeck::infer::{resolve_type, force_tvar};
 use middle::typeck::infer;
 use middle::typeck::rscope::bound_self_region;
-use middle::typeck::rscope::{RegionError, RegionParameterization};
+use middle::typeck::rscope::{RegionError};
 use middle::typeck::rscope::region_scope;
-use middle::typeck::rscope;
 use middle::typeck::{isr_alist, lookup_def_ccx};
 use middle::typeck::no_params;
 use middle::typeck::{require_same_types, method_map, vtable_map};
@@ -279,7 +278,7 @@ pub fn check_bare_fn(ccx: @mut CrateCtxt,
 }
 
 pub fn check_fn(ccx: @mut CrateCtxt,
-                +self_info: Option<SelfInfo>,
+                opt_self_info: Option<SelfInfo>,
                 purity: ast::purity,
                 fn_sig: &ty::FnSig,
                 decl: &ast::fn_decl,
@@ -306,19 +305,28 @@ pub fn check_fn(ccx: @mut CrateCtxt,
     // First, we have to replace any bound regions in the fn and self
     // types with free ones.  The free region references will be bound
     // the node_id of the body block.
-
-    let (isr, self_info, fn_sig) = {
-        replace_bound_regions_in_fn_sig(tcx, inherited_isr, self_info, fn_sig,
-                                        |br| ty::re_free(body.node.id, br))
+    let (isr, opt_self_info, fn_sig) = {
+        let opt_self_ty = opt_self_info.map(|i| i.self_ty);
+        let (isr, opt_self_ty, fn_sig) =
+            replace_bound_regions_in_fn_sig(
+                tcx, inherited_isr, opt_self_ty, fn_sig,
+                |br| ty::re_free(ty::FreeRegion {scope_id: body.node.id,
+                                                 bound_region: br}));
+        let opt_self_info =
+            opt_self_info.map(
+                |si| SelfInfo {self_ty: opt_self_ty.get(), ..*si});
+        (isr, opt_self_info, fn_sig)
     };
 
+    relate_free_regions(tcx, opt_self_info.map(|s| s.self_ty), &fn_sig);
+
     let arg_tys = fn_sig.inputs.map(|a| a.ty);
     let ret_ty = fn_sig.output;
 
-    debug!("check_fn(arg_tys=%?, ret_ty=%?, self_info.self_ty=%?)",
-           arg_tys.map(|a| ppaux::ty_to_str(tcx, *a)),
+    debug!("check_fn(arg_tys=%?, ret_ty=%?, opt_self_ty=%?)",
+           arg_tys.map(|&a| ppaux::ty_to_str(tcx, a)),
            ppaux::ty_to_str(tcx, ret_ty),
-           self_info.map(|s| ppaux::ty_to_str(tcx, s.self_ty)));
+           opt_self_info.map(|si| ppaux::ty_to_str(tcx, si.self_ty)));
 
     // ______________________________________________________________________
     // Create the function context.  This is either derived from scratch or,
@@ -343,7 +351,7 @@ pub fn check_fn(ccx: @mut CrateCtxt,
         }
     };
 
-    gather_locals(fcx, decl, body, arg_tys, self_info);
+    gather_locals(fcx, decl, body, arg_tys, opt_self_info);
     check_block_with_expected(fcx, body, Some(ret_ty));
 
     // We unify the tail expr's type with the
@@ -361,7 +369,7 @@ pub fn check_fn(ccx: @mut CrateCtxt,
       None => ()
     }
 
-    for self_info.each |self_info| {
+    for opt_self_info.each |self_info| {
         fcx.write_ty(self_info.self_id, self_info.self_ty);
     }
     for vec::each2(decl.inputs, arg_tys) |input, arg| {
@@ -374,7 +382,7 @@ pub fn check_fn(ccx: @mut CrateCtxt,
                      decl: &ast::fn_decl,
                      body: &ast::blk,
                      arg_tys: &[ty::t],
-                     self_info: Option<SelfInfo>) {
+                     opt_self_info: Option<SelfInfo>) {
         let tcx = fcx.ccx.tcx;
 
         let assign: @fn(ast::node_id, Option<ty::t>) = |nid, ty_opt| {
@@ -393,7 +401,7 @@ pub fn check_fn(ccx: @mut CrateCtxt,
         };
 
         // Add the self parameter
-        for self_info.each |self_info| {
+        for opt_self_info.each |self_info| {
             assign(self_info.self_id, Some(self_info.self_ty));
             debug!("self is assigned to %s",
                    fcx.infcx().ty_to_str(
@@ -479,26 +487,22 @@ pub fn check_fn(ccx: @mut CrateCtxt,
 }
 
 pub fn check_method(ccx: @mut CrateCtxt,
-                    method: @ast::method,
-                    self_ty: ty::t)
+                    method: @ast::method)
 {
-    let self_info = if method.self_ty.node == ast::sty_static {None} else {
-        let ty = method::transform_self_type_for_method(
-            ccx.tcx,
-            Some(ty::re_bound(ty::br_self)),
-            self_ty,
-            method.self_ty.node,
-            TransformTypeNormally);
-        Some(SelfInfo {self_ty: ty, self_id: method.self_id,
-                       span: method.self_ty.span})
-    };
+    let method_def_id = local_def(method.id);
+    let method_ty = ty::method(ccx.tcx, method_def_id);
+    let opt_self_info = method_ty.transformed_self_ty.map(|&ty| {
+        SelfInfo {self_ty: ty,
+                  self_id: method.self_id,
+                  span: method.self_ty.span}
+    });
 
     check_bare_fn(
         ccx,
         &method.decl,
         &method.body,
         method.id,
-        self_info
+        opt_self_info
     );
 }
 
@@ -570,15 +574,12 @@ pub fn check_item(ccx: @mut CrateCtxt, it: @ast::item) {
       ast::item_fn(ref decl, _, _, _, ref body) => {
         check_bare_fn(ccx, decl, body, it.id, None);
       }
-      ast::item_impl(ref generics, _, ty, ref ms) => {
+      ast::item_impl(_, _, _, ref ms) => {
         let rp = ccx.tcx.region_paramd_items.find(&it.id).map_consume(|x| *x);
         debug!("item_impl %s with id %d rp %?",
                *ccx.tcx.sess.str_of(it.ident), it.id, rp);
-        let rp = RegionParameterization::from_variance_and_generics(
-            rp, generics);
-        let self_ty = ccx.to_ty(&rscope::type_rscope(rp), ty);
         for ms.each |m| {
-            check_method(ccx, *m, self_ty);
+            check_method(ccx, *m);
         }
       }
       ast::item_trait(_, _, ref trait_methods) => {
@@ -589,8 +590,7 @@ pub fn check_item(ccx: @mut CrateCtxt, it: @ast::item) {
                 // bodies to check.
               }
               provided(m) => {
-                let self_ty = ty::mk_self(ccx.tcx, local_def(it.id));
-                check_method(ccx, m, self_ty);
+                check_method(ccx, m);
               }
             }
         }
@@ -2841,8 +2841,7 @@ pub fn check_decl_local(fcx: @mut FnCtxt, local: @ast::local)  {
         _ => {}
     }
 
-    let region =
-        ty::re_scope(*tcx.region_map.get(&local.node.id));
+    let region = tcx.region_maps.encl_region(local.node.id);
     let pcx = pat_ctxt {
         fcx: fcx,
         map: pat_id_map(tcx.def_map, local.node.pat),
diff --git a/src/librustc/middle/typeck/check/regionck.rs b/src/librustc/middle/typeck/check/regionck.rs
index 833dbff89a0..5594f2a0f65 100644
--- a/src/librustc/middle/typeck/check/regionck.rs
+++ b/src/librustc/middle/typeck/check/regionck.rs
@@ -31,13 +31,15 @@ use core::prelude::*;
 
 use middle::freevars::get_freevars;
 use middle::pat_util::pat_bindings;
-use middle::ty::{encl_region, re_scope};
+use middle::ty::{re_scope};
 use middle::ty;
 use middle::typeck::check::FnCtxt;
 use middle::typeck::check::lookup_def;
+use middle::typeck::check::regionmanip::relate_nested_regions;
 use middle::typeck::infer::resolve_and_force_all_but_regions;
 use middle::typeck::infer::resolve_type;
-use util::ppaux::{note_and_explain_region, ty_to_str};
+use util::ppaux::{note_and_explain_region, ty_to_str,
+                  region_to_str};
 
 use core::result;
 use syntax::ast::{ManagedSigil, OwnedSigil, BorrowedSigil};
@@ -53,12 +55,13 @@ pub struct Rcx {
 
 pub type rvt = visit::vt<@mut Rcx>;
 
-pub fn encl_region_of_def(fcx: @mut FnCtxt, def: ast::def) -> ty::Region {
+fn encl_region_of_def(fcx: @mut FnCtxt, def: ast::def) -> ty::Region {
     let tcx = fcx.tcx();
     match def {
         def_local(node_id, _) | def_arg(node_id, _, _) |
-        def_self(node_id, _) | def_binding(node_id, _) =>
-            return encl_region(tcx, node_id),
+        def_self(node_id, _) | def_binding(node_id, _) => {
+            tcx.region_maps.encl_region(node_id)
+        }
         def_upvar(_, subdef, closure_id, body_id) => {
             match ty::ty_closure_sigil(fcx.node_ty(closure_id)) {
                 BorrowedSigil => encl_region_of_def(fcx, *subdef),
@@ -113,6 +116,24 @@ pub impl Rcx {
     fn resolve_node_type(@mut self, id: ast::node_id) -> ty::t {
         self.resolve_type(self.fcx.node_ty(id))
     }
+
+    /// Try to resolve the type for the given node.
+    fn resolve_expr_type_adjusted(@mut self, expr: @ast::expr) -> ty::t {
+        let ty_unadjusted = self.resolve_node_type(expr.id);
+        if ty::type_is_error(ty_unadjusted) || ty::type_is_bot(ty_unadjusted) {
+            ty_unadjusted
+        } else {
+            let tcx = self.fcx.tcx();
+            let adjustments = self.fcx.inh.adjustments;
+            match adjustments.find(&expr.id) {
+                None => ty_unadjusted,
+                Some(&adjustment) => {
+                    // FIXME(#3850) --- avoid region scoping errors
+                    ty::adjust_ty(tcx, expr.span, ty_unadjusted, Some(&adjustment))
+                }
+            }
+        }
+    }
 }
 
 pub fn regionck_expr(fcx: @mut FnCtxt, e: @ast::expr) {
@@ -129,7 +150,7 @@ pub fn regionck_fn(fcx: @mut FnCtxt, blk: &ast::blk) {
     fcx.infcx().resolve_regions();
 }
 
-pub fn regionck_visitor() -> rvt {
+fn regionck_visitor() -> rvt {
     visit::mk_vt(@visit::Visitor {visit_item: visit_item,
                                   visit_stmt: visit_stmt,
                                   visit_expr: visit_expr,
@@ -138,11 +159,11 @@ pub fn regionck_visitor() -> rvt {
                                   .. *visit::default_visitor()})
 }
 
-pub fn visit_item(_item: @ast::item, &&_rcx: @mut Rcx, _v: rvt) {
+fn visit_item(_item: @ast::item, &&_rcx: @mut Rcx, _v: rvt) {
     // Ignore items
 }
 
-pub fn visit_local(l: @ast::local, &&rcx: @mut Rcx, v: rvt) {
+fn visit_local(l: @ast::local, &&rcx: @mut Rcx, v: rvt) {
     // Check to make sure that the regions in all local variables are
     // within scope.
     //
@@ -173,19 +194,24 @@ pub fn visit_local(l: @ast::local, &&rcx: @mut Rcx, v: rvt) {
     }
 }
 
-pub fn visit_block(b: &ast::blk, &&rcx: @mut Rcx, v: rvt) {
+fn visit_block(b: &ast::blk, &&rcx: @mut Rcx, v: rvt) {
     visit::visit_block(b, rcx, v);
 }
 
-pub fn visit_expr(expr: @ast::expr, &&rcx: @mut Rcx, v: rvt) {
-    debug!("visit_expr(e=%s)", rcx.fcx.expr_to_str(expr));
+fn visit_expr(expr: @ast::expr, &&rcx: @mut Rcx, v: rvt) {
+    debug!("regionck::visit_expr(e=%s)", rcx.fcx.expr_to_str(expr));
 
     for rcx.fcx.inh.adjustments.find(&expr.id).each |&adjustment| {
+        debug!("adjustment=%?", adjustment);
         match *adjustment {
             @ty::AutoDerefRef(
-                ty::AutoDerefRef {
-                    autoderefs: autoderefs, autoref: Some(ref autoref)}) => {
-                guarantor::for_autoref(rcx, expr, autoderefs, autoref);
+                ty::AutoDerefRef {autoderefs: autoderefs, autoref: opt_autoref}) =>
+            {
+                let expr_ty = rcx.resolve_node_type(expr.id);
+                constrain_derefs(rcx, expr, autoderefs, expr_ty);
+                for opt_autoref.each |autoref| {
+                    guarantor::for_autoref(rcx, expr, autoderefs, autoref);
+                }
             }
             _ => {}
         }
@@ -271,6 +297,16 @@ pub fn visit_expr(expr: @ast::expr, &&rcx: @mut Rcx, v: rvt) {
             }
         }
 
+        ast::expr_index(vec_expr, _) => {
+            let vec_type = rcx.resolve_expr_type_adjusted(vec_expr);
+            constrain_index(rcx, expr, vec_type);
+        }
+
+        ast::expr_unary(ast::deref, base) => {
+            let base_ty = rcx.resolve_node_type(base.id);
+            constrain_derefs(rcx, expr, 1, base_ty);
+        }
+
         ast::expr_addr_of(_, base) => {
             guarantor::for_addr_of(rcx, expr, base);
         }
@@ -297,11 +333,11 @@ pub fn visit_expr(expr: @ast::expr, &&rcx: @mut Rcx, v: rvt) {
     visit::visit_expr(expr, rcx, v);
 }
 
-pub fn visit_stmt(s: @ast::stmt, &&rcx: @mut Rcx, v: rvt) {
+fn visit_stmt(s: @ast::stmt, &&rcx: @mut Rcx, v: rvt) {
     visit::visit_stmt(s, rcx, v);
 }
 
-pub fn visit_node(id: ast::node_id, span: span, rcx: @mut Rcx) -> bool {
+fn visit_node(id: ast::node_id, span: span, rcx: @mut Rcx) -> bool {
     /*!
      *
      * checks the type of the node `id` and reports an error if it
@@ -314,13 +350,119 @@ pub fn visit_node(id: ast::node_id, span: span, rcx: @mut Rcx) -> bool {
 
     // find the region where this expr evaluation is taking place
     let tcx = fcx.ccx.tcx;
-    let encl_region = ty::encl_region(tcx, id);
+    let encl_region = match tcx.region_maps.opt_encl_scope(id) {
+        None => ty::re_static,
+        Some(r) => ty::re_scope(r)
+    };
 
     // Otherwise, look at the type and see if it is a region pointer.
     constrain_regions_in_type_of_node(rcx, id, encl_region, span)
 }
 
-pub fn constrain_auto_ref(rcx: @mut Rcx, expr: @ast::expr) {
+fn encl_region_or_static(rcx: @mut Rcx, expr: @ast::expr) -> ty::Region {
+    // FIXME(#3850) --- interactions with modes compel overly large granularity
+    // that is, we would probably prefer to just return re_scope(expr.id)
+    // here but we cannot just yet.
+
+    let tcx = rcx.fcx.tcx();
+    match tcx.region_maps.opt_encl_scope(expr.id) {
+        Some(s) => ty::re_scope(s),
+        None => ty::re_static // occurs in constants
+    }
+}
+
+fn constrain_derefs(rcx: @mut Rcx,
+                    deref_expr: @ast::expr,
+                    derefs: uint,
+                    mut derefd_ty: ty::t)
+{
+    /*!
+     * Invoked on any dereference that occurs, whether explicitly
+     * or through an auto-deref.  Checks that if this is a region
+     * pointer being derefenced, the lifetime of the pointer includes
+     * the deref expr.
+     */
+
+    let tcx = rcx.fcx.tcx();
+    let r_deref_expr = encl_region_or_static(rcx, deref_expr);
+    for uint::range(0, derefs) |i| {
+        debug!("constrain_derefs(deref_expr=%s, derefd_ty=%s, derefs=%?/%?",
+               rcx.fcx.expr_to_str(deref_expr),
+               rcx.fcx.infcx().ty_to_str(derefd_ty),
+               i, derefs);
+
+        match ty::get(derefd_ty).sty {
+            ty::ty_rptr(r_ptr, _) => {
+                match rcx.fcx.mk_subr(true, deref_expr.span, r_deref_expr, r_ptr) {
+                    result::Ok(*) => {}
+                    result::Err(*) => {
+                        tcx.sess.span_err(
+                            deref_expr.span,
+                            fmt!("dereference of reference outside its lifetime"));
+                        note_and_explain_region(
+                            tcx,
+                            "the reference is only valid for ",
+                            r_ptr,
+                            "");
+                    }
+                }
+            }
+
+            _ => {}
+        }
+
+        match ty::deref(tcx, derefd_ty, true) {
+            Some(mt) => derefd_ty = mt.ty,
+            None => {
+                tcx.sess.span_bug(
+                    deref_expr.span,
+                    fmt!("%?'th deref is of a non-deref'able type `%s`",
+                         i, rcx.fcx.infcx().ty_to_str(derefd_ty)));
+            }
+        }
+    }
+}
+
+fn constrain_index(rcx: @mut Rcx,
+                   index_expr: @ast::expr,
+                   indexed_ty: ty::t)
+{
+    /*!
+     * Invoked on any index expression that occurs.  Checks that if
+     * this is a slice being indexed, the lifetime of the pointer
+     * includes the deref expr.
+     */
+
+    let tcx = rcx.fcx.tcx();
+
+    debug!("constrain_index(index_expr=%s, indexed_ty=%s",
+           rcx.fcx.expr_to_str(index_expr),
+           rcx.fcx.infcx().ty_to_str(indexed_ty));
+
+    let r_index_expr = encl_region_or_static(rcx, index_expr);
+    match ty::get(indexed_ty).sty {
+        ty::ty_estr(ty::vstore_slice(r_ptr)) |
+        ty::ty_evec(_, ty::vstore_slice(r_ptr)) => {
+            match rcx.fcx.mk_subr(true, index_expr.span, r_index_expr, r_ptr) {
+                result::Ok(*) => {}
+                result::Err(*) => {
+                    tcx.sess.span_err(
+                        index_expr.span,
+                        fmt!("index of slice outside its lifetime"));
+                    note_and_explain_region(
+                        tcx,
+                        "the slice is only valid for ",
+                        r_ptr,
+                        "");
+                }
+            }
+        }
+
+        _ => {}
+    }
+}
+
+fn constrain_auto_ref(rcx: @mut Rcx, expr: @ast::expr) {
     /*!
      *
      * If `expr` is auto-ref'd (e.g., as part of a borrow), then this
@@ -340,7 +482,7 @@ pub fn constrain_auto_ref(rcx: @mut Rcx, expr: @ast::expr) {
     };
 
     let tcx = rcx.fcx.tcx();
-    let encl_region = ty::encl_region(tcx, expr.id);
+    let encl_region = tcx.region_maps.encl_region(expr.id);
     match rcx.fcx.mk_subr(true, expr.span, encl_region, region) {
         result::Ok(()) => {}
         result::Err(_) => {
@@ -366,7 +508,7 @@ pub fn constrain_auto_ref(rcx: @mut Rcx, expr: @ast::expr) {
     }
 }
 
-pub fn constrain_free_variables(
+fn constrain_free_variables(
     rcx: @mut Rcx,
     region: ty::Region,
     expr: @ast::expr) {
@@ -402,81 +544,103 @@ pub fn constrain_free_variables(
     }
 }
 
-pub fn constrain_regions_in_type_of_node(
+fn constrain_regions_in_type_of_node(
     rcx: @mut Rcx,
     id: ast::node_id,
     encl_region: ty::Region,
-    span: span) -> bool {
+    span: span) -> bool
+{
     let tcx = rcx.fcx.tcx();
 
     // Try to resolve the type.  If we encounter an error, then typeck
     // is going to fail anyway, so just stop here and let typeck
     // report errors later on in the writeback phase.
-    let ty = rcx.resolve_node_type(id);
+    let ty0 = rcx.resolve_node_type(id);
+    let adjustment = rcx.fcx.inh.adjustments.find(&id);
+    let ty = ty::adjust_ty(tcx, span, ty0, adjustment);
     debug!("constrain_regions_in_type_of_node(\
-            ty=%s, id=%d, encl_region=%?)",
-           ty_to_str(tcx, ty), id, encl_region);
+            ty=%s, ty0=%s, id=%d, encl_region=%?, adjustment=%?)",
+           ty_to_str(tcx, ty), ty_to_str(tcx, ty0),
+           id, encl_region, adjustment);
     constrain_regions_in_type(rcx, encl_region, span, ty)
 }
 
-pub fn constrain_regions_in_type(
+fn constrain_regions_in_type(
     rcx: @mut Rcx,
     encl_region: ty::Region,
     span: span,
-    ty: ty::t) -> bool {
+    ty: ty::t) -> bool
+{
     /*!
      *
      * Requires that any regions which appear in `ty` must be
-     * superregions of `encl_region`.  This prevents regions from
-     * being used outside of the block in which they are valid.
-     * Recall that regions represent blocks of code or expressions:
-     * this requirement basically says "any place that uses or may use
-     * a region R must be within the block of code that R corresponds
-     * to." */
+     * superregions of `encl_region`.  Also enforces the constraint
+     * that given a pointer type `&'r T`, T must not contain regions
+     * that outlive 'r, as well as analogous constraints for other
+     * lifetime'd types.
+     *
+     * This check prevents regions from being used outside of the block in
+     * which they are valid.  Recall that regions represent blocks of
+     * code or expressions: this requirement basically says "any place
+     * that uses or may use a region R must be within the block of
+     * code that R corresponds to."
+     */
 
     let e = rcx.errors_reported;
-    ty::walk_regions_and_ty(
-        rcx.fcx.ccx.tcx, ty,
-        |r| constrain_region(rcx, encl_region, span, r),
-        |t| ty::type_has_regions(t));
-    return (e == rcx.errors_reported);
+    let tcx = rcx.fcx.ccx.tcx;
 
-    fn constrain_region(rcx: @mut Rcx,
-                        encl_region: ty::Region,
-                        span: span,
-                        region: ty::Region) {
-        let tcx = rcx.fcx.ccx.tcx;
+    debug!("constrain_regions_in_type(encl_region=%s, ty=%s)",
+           region_to_str(tcx, encl_region),
+           ty_to_str(tcx, ty));
 
-        debug!("constrain_region(encl_region=%?, region=%?)",
-               encl_region, region);
+    do relate_nested_regions(tcx, Some(encl_region), ty) |r_sub, r_sup| {
+        debug!("relate(r_sub=%s, r_sup=%s)",
+               region_to_str(tcx, r_sub),
+               region_to_str(tcx, r_sup));
 
-        match region {
-          ty::re_bound(_) => {
+        if r_sup.is_bound() || r_sub.is_bound() {
             // a bound region is one which appears inside an fn type.
             // (e.g., the `&` in `fn(&T)`).  Such regions need not be
             // constrained by `encl_region` as they are placeholders
             // for regions that are as-yet-unknown.
-            return;
-          }
-          _ => ()
-        }
-
-        match rcx.fcx.mk_subr(true, span, encl_region, region) {
-          result::Err(_) => {
-            tcx.sess.span_err(
-                span,
-                fmt!("reference is not valid outside of its lifetime"));
-            note_and_explain_region(
-                tcx,
-                ~"the reference is only valid for ",
-                region,
-                ~"");
-            rcx.errors_reported += 1u;
-          }
-          result::Ok(()) => {
-          }
+        } else {
+            match rcx.fcx.mk_subr(true, span, r_sub, r_sup) {
+                result::Err(_) => {
+                    if r_sub == encl_region {
+                        tcx.sess.span_err(
+                            span,
+                            fmt!("reference is not valid outside of its lifetime"));
+                        note_and_explain_region(
+                            tcx,
+                            "the reference is only valid for ",
+                            r_sup,
+                            "");
+                    } else {
+                        tcx.sess.span_err(
+                            span,
+                            fmt!("in type `%s`, pointer has a longer lifetime than \
+                                  the data it references",
+                                 rcx.fcx.infcx().ty_to_str(ty)));
+                        note_and_explain_region(
+                            tcx,
+                            "the pointer is valid for ",
+                            r_sub,
+                            "");
+                        note_and_explain_region(
+                            tcx,
+                            "but the referenced data is only valid for ",
+                            r_sup,
+                            "");
+                    }
+                    rcx.errors_reported += 1u;
+                }
+                result::Ok(()) => {
+                }
+            }
         }
     }
+
+    return (e == rcx.errors_reported);
 }
 
 pub mod guarantor {
@@ -577,10 +741,12 @@ pub mod guarantor {
          * region pointers.
          */
 
-        debug!("guarantor::for_autoref(expr=%s)", rcx.fcx.expr_to_str(expr));
+        debug!("guarantor::for_autoref(expr=%s, autoref=%?)",
+               rcx.fcx.expr_to_str(expr), autoref);
         let _i = ::util::common::indenter();
 
         let mut expr_ct = categorize_unadjusted(rcx, expr);
+        debug!("    unadjusted cat=%?", expr_ct.cat);
         expr_ct = apply_autoderefs(
             rcx, expr, autoderefs, expr_ct);
 
@@ -626,7 +792,7 @@ pub mod guarantor {
          * to the lifetime of its guarantor (if any).
          */
 
-        debug!("opt_constrain_region(id=%?, guarantor=%?)", id, guarantor);
+        debug!("link(id=%?, guarantor=%?)", id, guarantor);
 
         let bound = match guarantor {
             None => {
@@ -860,8 +1026,6 @@ pub mod guarantor {
                 match closure_ty.sigil {
                     ast::BorrowedSigil => BorrowedPointer(closure_ty.region),
                     ast::OwnedSigil => OwnedPointer,
-
-                    // NOTE This is...not quite right.  Deduce a test etc.
                     ast::ManagedSigil => OtherPointer,
                 }
             }
@@ -972,7 +1136,6 @@ pub fn infallibly_mk_subr(rcx: @mut Rcx,
                           a: ty::Region,
                           b: ty::Region) {
     /*!
-     *
      * Constrains `a` to be a subregion of `b`.  In many cases, we
      * know that this can never yield an error due to the way that
      * region inferencing works.  Therefore just report a bug if we
diff --git a/src/librustc/middle/typeck/check/regionmanip.rs b/src/librustc/middle/typeck/check/regionmanip.rs
index abbefd1f7e6..1abcefeefac 100644
--- a/src/librustc/middle/typeck/check/regionmanip.rs
+++ b/src/librustc/middle/typeck/check/regionmanip.rs
@@ -13,7 +13,7 @@
 use core::prelude::*;
 
 use middle::ty;
-use middle::typeck::check::SelfInfo;
+
 use middle::typeck::isr_alist;
 use util::common::indenter;
 use util::ppaux::region_to_str;
@@ -26,29 +26,24 @@ use std::list::Cons;
 pub fn replace_bound_regions_in_fn_sig(
     tcx: ty::ctxt,
     isr: isr_alist,
-    self_info: Option<SelfInfo>,
+    opt_self_ty: Option<ty::t>,
     fn_sig: &ty::FnSig,
     mapf: &fn(ty::bound_region) -> ty::Region)
-    -> (isr_alist, Option<SelfInfo>, ty::FnSig)
+    -> (isr_alist, Option<ty::t>, ty::FnSig)
 {
-    // Take self_info apart; the self_ty part is the only one we want
-    // to update here.
-    let self_ty = self_info.map(|s| s.self_ty);
-    let rebuild_self_info = |t| self_info.map(|s| SelfInfo{self_ty: t, ..*s});
-
     let mut all_tys = ty::tys_in_fn_sig(fn_sig);
 
-    for self_info.each |self_info| {
-        all_tys.push(self_info.self_ty);
+    for opt_self_ty.each |&self_ty| {
+        all_tys.push(self_ty);
     }
 
-    for self_ty.each |t| { all_tys.push(*t) }
+    for opt_self_ty.each |&t| { all_tys.push(t) }
 
-    debug!("replace_bound_regions_in_fn_sig(self_info.self_ty=%?, fn_sig=%s, \
+    debug!("replace_bound_regions_in_fn_sig(self_ty=%?, fn_sig=%s, \
             all_tys=%?)",
-           self_ty.map(|t| ppaux::ty_to_str(tcx, *t)),
+           opt_self_ty.map(|&t| ppaux::ty_to_str(tcx, t)),
            ppaux::fn_sig_to_str(tcx, fn_sig),
-           all_tys.map(|t| ppaux::ty_to_str(tcx, *t)));
+           all_tys.map(|&t| ppaux::ty_to_str(tcx, t)));
     let _i = indenter();
 
     let isr = do create_bound_region_mapping(tcx, isr, all_tys) |br| {
@@ -58,20 +53,15 @@ pub fn replace_bound_regions_in_fn_sig(
     let new_fn_sig = ty::fold_sig(fn_sig, |t| {
         replace_bound_regions(tcx, isr, t)
     });
-    let t_self = self_ty.map(|t| replace_bound_regions(tcx, isr, *t));
+    let new_self_ty = opt_self_ty.map(|&t| replace_bound_regions(tcx, isr, t));
 
-    debug!("result of replace_bound_regions_in_fn_sig: self_info.self_ty=%?, \
-                fn_sig=%s",
-           t_self.map(|t| ppaux::ty_to_str(tcx, *t)),
+    debug!("result of replace_bound_regions_in_fn_sig: \
+            new_self_ty=%?, \
+            fn_sig=%s",
+           new_self_ty.map(|&t| ppaux::ty_to_str(tcx, t)),
            ppaux::fn_sig_to_str(tcx, &new_fn_sig));
 
-    // Glue updated self_ty back together with its original def_id.
-    let new_self_info: Option<SelfInfo> = match t_self {
-      None    => None,
-      Some(t) => rebuild_self_info(t)
-    };
-
-    return (isr, new_self_info, new_fn_sig);
+    return (isr, new_self_ty, new_fn_sig);
 
     // Takes `isr`, a (possibly empty) mapping from in-scope region
     // names ("isr"s) to their corresponding regions; `tys`, a list of
@@ -99,7 +89,7 @@ pub fn replace_bound_regions_in_fn_sig(
                       to_r: &fn(ty::bound_region) -> ty::Region,
                       r: ty::Region) -> isr_alist {
             match r {
-              ty::re_free(_, _) | ty::re_static | ty::re_scope(_) |
+              ty::re_free(*) | ty::re_static | ty::re_scope(_) |
               ty::re_infer(_) => {
                 isr
               }
@@ -167,10 +157,125 @@ pub fn replace_bound_regions_in_fn_sig(
               // Free regions like these just stay the same:
               ty::re_static |
               ty::re_scope(_) |
-              ty::re_free(_, _) |
+              ty::re_free(*) |
               ty::re_infer(_) => r
             };
             r1
         }
     }
 }
+
+pub fn relate_nested_regions(
+    tcx: ty::ctxt,
+    opt_region: Option<ty::Region>,
+    ty: ty::t,
+    relate_op: &fn(ty::Region, ty::Region))
+{
+    /*!
+     *
+     * This rather specialized function walks each region `r` that appear
+     * in `ty` and invokes `relate_op(r_encl, r)` for each one.  `r_encl`
+     * here is the region of any enclosing `&'r T` pointer.  If there is
+     * no enclosing pointer, and `opt_region` is Some, then `opt_region.get()`
+     * is used instead.  Otherwise, no callback occurs at all).
+     *
+     * Here are some examples to give you an intution:
+     *
+     * - `relate_nested_regions(Some('r1), &'r2 uint)` invokes
+     *   - `relate_op('r1, 'r2)`
+     * - `relate_nested_regions(Some('r1), &'r2 &'r3 uint)` invokes
+     *   - `relate_op('r1, 'r2)`
+     *   - `relate_op('r2, 'r3)`
+     * - `relate_nested_regions(None, &'r2 &'r3 uint)` invokes
+     *   - `relate_op('r2, 'r3)`
+     * - `relate_nested_regions(None, &'r2 &'r3 &'r4 uint)` invokes
+     *   - `relate_op('r2, 'r3)`
+     *   - `relate_op('r2, 'r4)`
+     *   - `relate_op('r3, 'r4)`
+     *
+     * This function is used in various pieces of code because we enforce the
+     * constraint that a region pointer cannot outlive the things it points at.
+     * Hence, in the second example above, `'r2` must be a subregion of `'r3`.
+     */
+
+    let mut the_stack = ~[];
+    for opt_region.each |&r| { the_stack.push(r); }
+    walk_ty(tcx, &mut the_stack, ty, relate_op);
+
+    fn walk_ty(tcx: ty::ctxt,
+               the_stack: &mut ~[ty::Region],
+               ty: ty::t,
+               relate_op: &fn(ty::Region, ty::Region))
+    {
+        match ty::get(ty).sty {
+            ty::ty_rptr(r, ref mt) |
+            ty::ty_evec(ref mt, ty::vstore_slice(r)) => {
+                relate(*the_stack, r, relate_op);
+                the_stack.push(r);
+                walk_ty(tcx, the_stack, mt.ty, relate_op);
+                the_stack.pop();
+            }
+            _ => {
+                ty::fold_regions_and_ty(
+                    tcx,
+                    ty,
+                    |r| { relate(*the_stack, r, relate_op); r },
+                    |t| { walk_ty(tcx, the_stack, t, relate_op); t },
+                    |t| { walk_ty(tcx, the_stack, t, relate_op); t });
+            }
+        }
+    }
+
+    fn relate(the_stack: &[ty::Region],
+              r_sub: ty::Region,
+              relate_op: &fn(ty::Region, ty::Region))
+    {
+        for the_stack.each |&r| {
+            if !r.is_bound() && !r_sub.is_bound() {
+                relate_op(r, r_sub);
+            }
+        }
+    }
+}
+
+pub fn relate_free_regions(
+    tcx: ty::ctxt,
+    self_ty: Option<ty::t>,
+    fn_sig: &ty::FnSig)
+{
+    /*!
+     * This function populates the region map's `free_region_map`.
+     * It walks over the transformed self type and argument types
+     * for each function just before we check the body of that
+     * function, looking for types where you have a borrowed
+     * pointer to other borrowed data (e.g., `&'a &'b [uint]`.
+     * We do not allow borrowed pointers to outlive the things they
+     * point at, so we can assume that `'a <= 'b`.
+     *
+     * Tests: `src/test/compile-fail/regions-free-region-ordering-*.rs`
+     */
+
+    debug!("relate_free_regions >>");
+
+    let mut all_tys = ~[];
+    for fn_sig.inputs.each |arg| {
+        all_tys.push(arg.ty);
+    }
+    for self_ty.each |&t| {
+        all_tys.push(t);
+    }
+
+    for all_tys.each |&t| {
+        debug!("relate_free_regions(t=%s)", ppaux::ty_to_str(tcx, t));
+        relate_nested_regions(tcx, None, t, |a, b| {
+            match (&a, &b) {
+                (&ty::re_free(free_a), &ty::re_free(free_b)) => {
+                    tcx.region_maps.relate_free_regions(free_a, free_b);
+                }
+                _ => {}
+            }
+        })
+    }
+
+    debug!("<< relate_free_regions");
+}
diff --git a/src/librustc/middle/typeck/check/vtable.rs b/src/librustc/middle/typeck/check/vtable.rs
index 6ea668605fd..8245dc88114 100644
--- a/src/librustc/middle/typeck/check/vtable.rs
+++ b/src/librustc/middle/typeck/check/vtable.rs
@@ -11,7 +11,7 @@
 use core::prelude::*;
 
 use middle::resolve::Impl;
-use middle::ty::{param_ty, substs};
+use middle::ty::{param_ty};
 use middle::ty;
 use middle::typeck::check::{FnCtxt, impl_self_ty};
 use middle::typeck::check::{structurally_resolved_type};
@@ -489,6 +489,8 @@ pub fn early_resolve_expr(ex: @ast::expr,
     match ex.node {
       ast::expr_path(*) => {
         for fcx.opt_node_ty_substs(ex.id) |substs| {
+            debug!("vtable resolution on parameter bounds for expr %s",
+                   ex.repr(fcx.tcx()));
             let def = *cx.tcx.def_map.get(&ex.id);
             let did = ast_util::def_id_of_def(def);
             let item_ty = ty::lookup_item_type(cx.tcx, did);
@@ -518,6 +520,8 @@ pub fn early_resolve_expr(ex: @ast::expr,
       ast::expr_index(*) | ast::expr_method_call(*) => {
         match ty::method_call_type_param_defs(cx.tcx, fcx.inh.method_map, ex.id) {
           Some(type_param_defs) => {
+            debug!("vtable resolution on parameter bounds for method call %s",
+                   ex.repr(fcx.tcx()));
             if has_trait_bounds(*type_param_defs) {
                 let callee_id = match ex.node {
                   ast::expr_field(_, _, _) => ex.id,
@@ -537,6 +541,7 @@ pub fn early_resolve_expr(ex: @ast::expr,
         }
       }
       ast::expr_cast(src, _) => {
+          debug!("vtable resolution on expr %s", ex.repr(fcx.tcx()));
           let target_ty = fcx.expr_ty(ex);
           match ty::get(target_ty).sty {
               ty::ty_trait(target_def_id, ref target_substs, store) => {
diff --git a/src/librustc/middle/typeck/coherence.rs b/src/librustc/middle/typeck/coherence.rs
index 174a20dd7f4..247b8eae2a8 100644
--- a/src/librustc/middle/typeck/coherence.rs
+++ b/src/librustc/middle/typeck/coherence.rs
@@ -24,7 +24,7 @@ use metadata::cstore::{CStore, iter_crate_data};
 use metadata::decoder::{dl_def, dl_field, dl_impl};
 use middle::resolve::{Impl, MethodInfo};
 use middle::ty::{ProvidedMethodSource, ProvidedMethodInfo, bound_copy, get};
-use middle::ty::{lookup_item_type, param_bounds, subst};
+use middle::ty::{lookup_item_type, subst};
 use middle::ty::{substs, t, ty_bool, ty_bot, ty_box, ty_enum, ty_err};
 use middle::ty::{ty_estr, ty_evec, ty_float, ty_infer, ty_int, ty_nil};
 use middle::ty::{ty_opaque_box, ty_param, ty_param_bounds_and_ty, ty_ptr};
diff --git a/src/librustc/middle/typeck/collect.rs b/src/librustc/middle/typeck/collect.rs
index a3296f6c209..59ea8ea039e 100644
--- a/src/librustc/middle/typeck/collect.rs
+++ b/src/librustc/middle/typeck/collect.rs
@@ -55,7 +55,7 @@ use syntax::ast_util::{local_def, split_trait_methods};
 use syntax::ast_util;
 use syntax::codemap::span;
 use syntax::codemap;
-use syntax::print::pprust::path_to_str;
+use syntax::print::pprust::{path_to_str, self_ty_to_str};
 use syntax::visit;
 use syntax::opt_vec::OptVec;
 use syntax::opt_vec;
@@ -453,31 +453,35 @@ pub fn compare_impl_method(tcx: ty::ctxt,
 
     let impl_m = &cm.mty;
 
-    // FIXME(#2687)---this check is too strict.  For example, a trait
-    // method with self type `&self` or `&mut self` should be
-    // implementable by an `&const self` method (the impl assumes less
-    // than the trait provides).
-    if impl_m.self_ty != trait_m.self_ty {
-        if impl_m.self_ty == ast::sty_static {
-            // Needs to be a fatal error because otherwise,
-            // method::transform_self_type_for_method ICEs
-            tcx.sess.span_fatal(cm.span,
-                 fmt!("method `%s` is declared as \
-                       static in its impl, but not in \
-                       its trait", *tcx.sess.str_of(impl_m.ident)));
-        }
-        else if trait_m.self_ty == ast::sty_static {
-            tcx.sess.span_fatal(cm.span,
-                 fmt!("method `%s` is declared as \
-                       static in its trait, but not in \
-                       its impl", *tcx.sess.str_of(impl_m.ident)));
+    // Try to give more informative error messages about self typing
+    // mismatches.  Note that any mismatch will also be detected
+    // below, where we construct a canonical function type that
+    // includes the self parameter as a normal parameter.  It's just
+    // that the error messages you get out of this code are a bit more
+    // inscrutable, particularly for cases where one method has no
+    // self.
+    match (&trait_m.self_ty, &impl_m.self_ty) {
+        (&ast::sty_static, &ast::sty_static) => {}
+        (&ast::sty_static, _) => {
+            tcx.sess.span_err(
+                cm.span,
+                fmt!("method `%s` has a `%s` declaration in the impl, \
+                      but not in the trait",
+                     *tcx.sess.str_of(trait_m.ident),
+                     self_ty_to_str(impl_m.self_ty, tcx.sess.intr())));
+            return;
         }
-        else {
+        (_, &ast::sty_static) => {
             tcx.sess.span_err(
                 cm.span,
-                fmt!("method `%s`'s self type does \
-                      not match the trait method's \
-                      self type", *tcx.sess.str_of(impl_m.ident)));
+                fmt!("method `%s` has a `%s` declaration in the trait, \
+                      but not in the impl",
+                     *tcx.sess.str_of(trait_m.ident),
+                     self_ty_to_str(trait_m.self_ty, tcx.sess.intr())));
+            return;
+        }
+        _ => {
+            // Let the type checker catch other errors below
         }
     }
 
@@ -535,9 +539,55 @@ pub fn compare_impl_method(tcx: ty::ctxt,
     // a free region.  So, for example, if the impl type is
     // "&'self str", then this would replace the self type with a free
     // region `self`.
-    let dummy_self_r = ty::re_free(cm.body_id, ty::br_self);
+    let dummy_self_r = ty::re_free(ty::FreeRegion {scope_id: cm.body_id,
+                                                   bound_region: ty::br_self});
     let self_ty = replace_bound_self(tcx, self_ty, dummy_self_r);
 
+    // We are going to create a synthetic fn type that includes
+    // both the method's self argument and its normal arguments.
+    // So a method like `fn(&self, a: uint)` would be converted
+    // into a function `fn(self: &T, a: uint)`.
+    let mut trait_fn_args = ~[];
+    let mut impl_fn_args = ~[];
+
+    // For both the trait and the impl, create an argument to
+    // represent the self argument (unless this is a static method).
+    // This argument will have the *transformed* self type.
+    for trait_m.transformed_self_ty.each |&t| {
+        trait_fn_args.push(ty::arg {mode: ast::expl(ast::by_copy), ty: t});
+    }
+    for impl_m.transformed_self_ty.each |&t| {
+        impl_fn_args.push(ty::arg {mode: ast::expl(ast::by_copy), ty: t});
+    }
+
+    // Add in the normal arguments.
+    trait_fn_args.push_all(trait_m.fty.sig.inputs);
+    impl_fn_args.push_all(impl_m.fty.sig.inputs);
+
+    // Create a bare fn type for trait/impl that includes self argument
+    let trait_fty =
+        ty::mk_bare_fn(
+            tcx,
+            ty::BareFnTy {purity: trait_m.fty.purity,
+                          abis: trait_m.fty.abis,
+                          sig: ty::FnSig {
+                              bound_lifetime_names:
+                                  copy trait_m.fty.sig.bound_lifetime_names,
+                              inputs: trait_fn_args,
+                              output: trait_m.fty.sig.output
+                          }});
+    let impl_fty =
+        ty::mk_bare_fn(
+            tcx,
+            ty::BareFnTy {purity: impl_m.fty.purity,
+                          abis: impl_m.fty.abis,
+                          sig: ty::FnSig {
+                              bound_lifetime_names:
+                                  copy impl_m.fty.sig.bound_lifetime_names,
+                              inputs: impl_fn_args,
+                              output: impl_m.fty.sig.output
+                          }});
+
     // Perform substitutions so that the trait/impl methods are expressed
     // in terms of the same set of type/region parameters:
     // - replace trait type parameters with those from `trait_substs`,
@@ -546,7 +596,6 @@ pub fn compare_impl_method(tcx: ty::ctxt,
     //   that correspond to the parameters we will find on the impl
     // - replace self region with a fresh, dummy region
     let impl_fty = {
-        let impl_fty = ty::mk_bare_fn(tcx, copy impl_m.fty);
         debug!("impl_fty (pre-subst): %s", ppaux::ty_to_str(tcx, impl_fty));
         replace_bound_self(tcx, impl_fty, dummy_self_r)
     };
@@ -564,7 +613,6 @@ pub fn compare_impl_method(tcx: ty::ctxt,
             self_ty: Some(self_ty),
             tps: vec::append(trait_tps, dummy_tps)
         };
-        let trait_fty = ty::mk_bare_fn(tcx, copy trait_m.fty);
         debug!("trait_fty (pre-subst): %s substs=%s",
                trait_fty.repr(tcx), substs.repr(tcx));
         ty::subst(tcx, &substs, trait_fty)
diff --git a/src/librustc/middle/typeck/infer/region_inference.rs b/src/librustc/middle/typeck/infer/region_inference.rs
index e6354d4ab88..7252566d84c 100644
--- a/src/librustc/middle/typeck/infer/region_inference.rs
+++ b/src/librustc/middle/typeck/infer/region_inference.rs
@@ -538,10 +538,9 @@ more convincing in the future.
 
 use core::prelude::*;
 
-use middle::region::is_subregion_of;
-use middle::region;
 use middle::ty;
-use middle::ty::{Region, RegionVid, re_static, re_infer, re_free, re_bound};
+use middle::ty::{FreeRegion, Region, RegionVid};
+use middle::ty::{re_static, re_infer, re_free, re_bound};
 use middle::ty::{re_scope, ReVar, ReSkolemized, br_fresh};
 use middle::typeck::infer::cres;
 use util::common::indenter;
@@ -554,6 +553,7 @@ use core::to_bytes;
 use core::uint;
 use core::vec;
 use syntax::codemap::span;
+use syntax::ast;
 
 #[deriving(Eq)]
 enum Constraint {
@@ -1025,11 +1025,12 @@ pub impl RegionVarBindings {
 }
 
 priv impl RegionVarBindings {
-    fn is_subregion_of(&mut self, sub: Region, sup: Region) -> bool {
-        is_subregion_of(self.tcx.region_map, sub, sup)
+    fn is_subregion_of(&self, sub: Region, sup: Region) -> bool {
+        let rm = self.tcx.region_maps;
+        rm.is_subregion_of(sub, sup)
     }
 
-    fn lub_concrete_regions(&mut self, +a: Region, +b: Region) -> Region {
+    fn lub_concrete_regions(&self, +a: Region, +b: Region) -> Region {
         match (a, b) {
           (re_static, _) | (_, re_static) => {
             re_static // nothing lives longer than static
@@ -1042,17 +1043,17 @@ priv impl RegionVarBindings {
                       non-concrete regions: %?, %?", a, b));
           }
 
-          (f @ re_free(f_id, _), re_scope(s_id)) |
-          (re_scope(s_id), f @ re_free(f_id, _)) => {
+          (f @ re_free(ref fr), re_scope(s_id)) |
+          (re_scope(s_id), f @ re_free(ref fr)) => {
             // A "free" region can be interpreted as "some region
-            // at least as big as the block f_id".  So, we can
+            // at least as big as the block fr.scope_id".  So, we can
             // reasonably compare free regions and scopes:
-            let rm = self.tcx.region_map;
-            match region::nearest_common_ancestor(rm, f_id, s_id) {
-              // if the free region's scope `f_id` is bigger than
+            let rm = self.tcx.region_maps;
+            match rm.nearest_common_ancestor(fr.scope_id, s_id) {
+              // if the free region's scope `fr.scope_id` is bigger than
               // the scope region `s_id`, then the LUB is the free
               // region itself:
-              Some(r_id) if r_id == f_id => f,
+              Some(r_id) if r_id == fr.scope_id => f,
 
               // otherwise, we don't know what the free region is,
               // so we must conservatively say the LUB is static:
@@ -1064,32 +1065,67 @@ priv impl RegionVarBindings {
             // The region corresponding to an outer block is a
             // subtype of the region corresponding to an inner
             // block.
-            let rm = self.tcx.region_map;
-            match region::nearest_common_ancestor(rm, a_id, b_id) {
+            let rm = self.tcx.region_maps;
+            match rm.nearest_common_ancestor(a_id, b_id) {
               Some(r_id) => re_scope(r_id),
               _ => re_static
             }
           }
 
+          (re_free(ref a_fr), re_free(ref b_fr)) => {
+             self.lub_free_regions(a_fr, b_fr)
+          }
+
           // For these types, we cannot define any additional
           // relationship:
           (re_infer(ReSkolemized(*)), _) |
           (_, re_infer(ReSkolemized(*))) |
-          (re_free(_, _), re_free(_, _)) |
           (re_bound(_), re_bound(_)) |
-          (re_bound(_), re_free(_, _)) |
+          (re_bound(_), re_free(_)) |
           (re_bound(_), re_scope(_)) |
-          (re_free(_, _), re_bound(_)) |
+          (re_free(_), re_bound(_)) |
           (re_scope(_), re_bound(_)) => {
             if a == b {a} else {re_static}
           }
         }
     }
 
-    fn glb_concrete_regions(&mut self,
+    fn lub_free_regions(&self,
+                        a: &FreeRegion,
+                        b: &FreeRegion) -> ty::Region
+    {
+        /*!
+         * Computes a region that encloses both free region arguments.
+         * Guarantee that if the same two regions are given as argument,
+         * in any order, a consistent result is returned.
+         */
+
+        return match a.cmp(b) {
+            Less => helper(self, a, b),
+            Greater => helper(self, b, a),
+            Equal => ty::re_free(*a)
+        };
+
+        fn helper(self: &RegionVarBindings,
+                  a: &FreeRegion,
+                  b: &FreeRegion) -> ty::Region
+        {
+            let rm = self.tcx.region_maps;
+            if rm.sub_free_region(*a, *b) {
+                ty::re_free(*b)
+            } else if rm.sub_free_region(*b, *a) {
+                ty::re_free(*a)
+            } else {
+                ty::re_static
+            }
+        }
+    }
+
+    fn glb_concrete_regions(&self,
                             +a: Region,
                             +b: Region)
                          -> cres<Region> {
+        debug!("glb_concrete_regions(%?, %?)", a, b);
         match (a, b) {
             (re_static, r) | (r, re_static) => {
                 // static lives longer than everything else
@@ -1104,37 +1140,26 @@ priv impl RegionVarBindings {
                           non-concrete regions: %?, %?", a, b));
             }
 
-            (re_free(f_id, _), s @ re_scope(s_id)) |
-            (s @ re_scope(s_id), re_free(f_id, _)) => {
+            (re_free(ref fr), s @ re_scope(s_id)) |
+            (s @ re_scope(s_id), re_free(ref fr)) => {
                 // Free region is something "at least as big as
-                // `f_id`."  If we find that the scope `f_id` is bigger
+                // `fr.scope_id`."  If we find that the scope `fr.scope_id` is bigger
                 // than the scope `s_id`, then we can say that the GLB
                 // is the scope `s_id`.  Otherwise, as we do not know
                 // big the free region is precisely, the GLB is undefined.
-                let rm = self.tcx.region_map;
-                match region::nearest_common_ancestor(rm, f_id, s_id) {
-                    Some(r_id) if r_id == f_id => Ok(s),
+                let rm = self.tcx.region_maps;
+                match rm.nearest_common_ancestor(fr.scope_id, s_id) {
+                    Some(r_id) if r_id == fr.scope_id => Ok(s),
                     _ => Err(ty::terr_regions_no_overlap(b, a))
                 }
             }
 
-            (re_scope(a_id), re_scope(b_id)) |
-            (re_free(a_id, _), re_free(b_id, _)) => {
-                if a == b {
-                    // Same scope or same free identifier, easy case.
-                    Ok(a)
-                } else {
-                    // We want to generate the intersection of two
-                    // scopes or two free regions.  So, if one of
-                    // these scopes is a subscope of the other, return
-                    // it.  Otherwise fail.
-                    let rm = self.tcx.region_map;
-                    match region::nearest_common_ancestor(rm, a_id, b_id) {
-                        Some(r_id) if a_id == r_id => Ok(re_scope(b_id)),
-                        Some(r_id) if b_id == r_id => Ok(re_scope(a_id)),
-                        _ => Err(ty::terr_regions_no_overlap(b, a))
-                    }
-                }
+            (re_scope(a_id), re_scope(b_id)) => {
+                self.intersect_scopes(a, b, a_id, b_id)
+            }
+
+            (re_free(ref a_fr), re_free(ref b_fr)) => {
+                self.glb_free_regions(a_fr, b_fr)
             }
 
             // For these types, we cannot define any additional
@@ -1142,9 +1167,9 @@ priv impl RegionVarBindings {
             (re_infer(ReSkolemized(*)), _) |
             (_, re_infer(ReSkolemized(*))) |
             (re_bound(_), re_bound(_)) |
-            (re_bound(_), re_free(_, _)) |
+            (re_bound(_), re_free(_)) |
             (re_bound(_), re_scope(_)) |
-            (re_free(_, _), re_bound(_)) |
+            (re_free(_), re_bound(_)) |
             (re_scope(_), re_bound(_)) => {
                 if a == b {
                     Ok(a)
@@ -1155,10 +1180,62 @@ priv impl RegionVarBindings {
         }
     }
 
+    fn glb_free_regions(&self,
+                        a: &FreeRegion,
+                        b: &FreeRegion) -> cres<ty::Region>
+    {
+        /*!
+         * Computes a region that is enclosed by both free region arguments,
+         * if any. Guarantees that if the same two regions are given as argument,
+         * in any order, a consistent result is returned.
+         */
+
+        return match a.cmp(b) {
+            Less => helper(self, a, b),
+            Greater => helper(self, b, a),
+            Equal => Ok(ty::re_free(*a))
+        };
+
+        fn helper(self: &RegionVarBindings,
+                  a: &FreeRegion,
+                  b: &FreeRegion) -> cres<ty::Region>
+        {
+            let rm = self.tcx.region_maps;
+            if rm.sub_free_region(*a, *b) {
+                Ok(ty::re_free(*a))
+            } else if rm.sub_free_region(*b, *a) {
+                Ok(ty::re_free(*b))
+            } else {
+                self.intersect_scopes(ty::re_free(*a), ty::re_free(*b),
+                                      a.scope_id, b.scope_id)
+            }
+        }
+    }
+
     fn report_type_error(&mut self, span: span, terr: &ty::type_err) {
         let terr_str = ty::type_err_to_str(self.tcx, terr);
         self.tcx.sess.span_err(span, terr_str);
     }
+
+    fn intersect_scopes(&self,
+                        region_a: ty::Region,
+                        region_b: ty::Region,
+                        scope_a: ast::node_id,
+                        scope_b: ast::node_id) -> cres<Region>
+    {
+        // We want to generate the intersection of two
+        // scopes or two free regions.  So, if one of
+        // these scopes is a subscope of the other, return
+        // it.  Otherwise fail.
+        debug!("intersect_scopes(scope_a=%?, scope_b=%?, region_a=%?, region_b=%?)",
+               scope_a, scope_b, region_a, region_b);
+        let rm = self.tcx.region_maps;
+        match rm.nearest_common_ancestor(scope_a, scope_b) {
+            Some(r_id) if scope_a == r_id => Ok(re_scope(scope_b)),
+            Some(r_id) if scope_b == r_id => Ok(re_scope(scope_a)),
+            _ => Err(ty::terr_regions_no_overlap(region_a, region_b))
+        }
+    }
 }
 
 // ______________________________________________________________________
diff --git a/src/librustc/middle/typeck/infer/test.rs b/src/librustc/middle/typeck/infer/test.rs
index 52a0300c5a0..bf607e2c362 100644
--- a/src/librustc/middle/typeck/infer/test.rs
+++ b/src/librustc/middle/typeck/infer/test.rs
@@ -210,7 +210,9 @@ pub impl Env {
     }
 
     fn t_rptr_free(&self, nid: ast::node_id, id: uint) -> ty::t {
-        ty::mk_imm_rptr(self.tcx, ty::re_free(nid, ty::br_anon(id)),
+        ty::mk_imm_rptr(self.tcx,
+                        ty::re_free(ty::FreeRegion {scope_id: nid,
+                                                    bound_region: ty::br_anon(id)}),
                         self.t_int())
     }
 
diff --git a/src/librustc/middle/typeck/rscope.rs b/src/librustc/middle/typeck/rscope.rs
index eeca90dbecd..3ff36a409a7 100644
--- a/src/librustc/middle/typeck/rscope.rs
+++ b/src/librustc/middle/typeck/rscope.rs
@@ -180,12 +180,11 @@ impl region_scope for MethodRscope {
         })
     }
     fn self_region(&self, _span: span) -> Result<ty::Region, RegionError> {
-        assert!(self.variance.is_some() || self.self_ty.is_borrowed());
+        assert!(self.variance.is_some());
         match self.variance {
             None => {}  // must be borrowed self, so this is OK
             Some(_) => {
-                if !self.self_ty.is_borrowed() &&
-                        !self.region_param_names.has_self() {
+                if !self.region_param_names.has_self() {
                     return Err(RegionError {
                         msg: ~"the `self` lifetime must be declared",
                         replacement: ty::re_bound(ty::br_self)
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index f26eeeca446..9b9e0e81b43 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -41,9 +41,9 @@ pub trait Repr {
 }
 
 pub fn note_and_explain_region(cx: ctxt,
-                               prefix: ~str,
+                               prefix: &str,
                                region: ty::Region,
-                               suffix: ~str) {
+                               suffix: &str) {
     match explain_region_and_span(cx, region) {
       (ref str, Some(span)) => {
         cx.sess.span_note(
@@ -98,23 +98,23 @@ pub fn explain_region_and_span(cx: ctxt, region: ty::Region)
         }
       }
 
-      re_free(id, br) => {
-        let prefix = match br {
+      re_free(ref fr) => {
+        let prefix = match fr.bound_region {
           br_anon(idx) => fmt!("the anonymous lifetime #%u defined on",
                                idx + 1),
           br_fresh(_) => fmt!("an anonymous lifetime defined on"),
           _ => fmt!("the lifetime %s as defined on",
-                    bound_region_to_str(cx, br))
+                    bound_region_to_str(cx, fr.bound_region))
         };
 
-        match cx.items.find(&id) {
+        match cx.items.find(&fr.scope_id) {
           Some(&ast_map::node_block(ref blk)) => {
             let (msg, opt_span) = explain_span(cx, "block", blk.span);
             (fmt!("%s %s", prefix, msg), opt_span)
           }
           Some(_) | None => {
             // this really should not happen
-            (fmt!("%s node %d", prefix, id), None)
+            (fmt!("%s node %d", prefix, fr.scope_id), None)
           }
         }
       }
@@ -215,7 +215,7 @@ pub fn region_to_str_space(cx: ctxt, prefix: &str, region: Region) -> ~str {
     match region {
         re_scope(_) => prefix.to_str(),
         re_bound(br) => bound_region_to_str_space(cx, prefix, br),
-        re_free(_, br) => bound_region_to_str_space(cx, prefix, br),
+        re_free(ref fr) => bound_region_to_str_space(cx, prefix, fr.bound_region),
         re_infer(ReSkolemized(_, br)) => {
             bound_region_to_str_space(cx, prefix, br)
         }
@@ -225,12 +225,16 @@ pub fn region_to_str_space(cx: ctxt, prefix: &str, region: Region) -> ~str {
 }
 
 pub fn mt_to_str(cx: ctxt, m: &mt) -> ~str {
+    mt_to_str_wrapped(cx, "", m, "")
+}
+
+pub fn mt_to_str_wrapped(cx: ctxt, before: &str, m: &mt, after: &str) -> ~str {
     let mstr = match m.mutbl {
       ast::m_mutbl => "mut ",
       ast::m_imm => "",
       ast::m_const => "const "
     };
-    return fmt!("%s%s", mstr, ty_to_str(cx, m.ty));
+    return fmt!("%s%s%s%s", mstr, before, ty_to_str(cx, m.ty), after);
 }
 
 pub fn vstore_to_str(cx: ctxt, vs: ty::vstore) -> ~str {
@@ -250,15 +254,14 @@ pub fn trait_store_to_str(cx: ctxt, s: ty::TraitStore) -> ~str {
     }
 }
 
-pub fn vstore_ty_to_str(cx: ctxt, ty: ~str, vs: ty::vstore) -> ~str {
+pub fn vstore_ty_to_str(cx: ctxt, mt: &mt, vs: ty::vstore) -> ~str {
     match vs {
-      ty::vstore_fixed(_) => {
-        fmt!("[%s, .. %s]", ty, vstore_to_str(cx, vs))
-      }
-      ty::vstore_slice(_) => {
-        fmt!("%s %s", vstore_to_str(cx, vs), ty)
-      }
-      _ => fmt!("%s[%s]", vstore_to_str(cx, vs), ty)
+        ty::vstore_fixed(_) => {
+            fmt!("[%s, .. %s]", mt_to_str(cx, mt), vstore_to_str(cx, vs))
+        }
+        _ => {
+            fmt!("%s%s", vstore_to_str(cx, vs), mt_to_str_wrapped(cx, "[", mt, "]"))
+        }
     }
 }
 
@@ -460,7 +463,7 @@ pub fn ty_to_str(cx: ctxt, typ: t) -> ~str {
         fmt!("%s%s", trait_store_to_str(cx, s), ty)
       }
       ty_evec(ref mt, vs) => {
-        vstore_ty_to_str(cx, fmt!("%s", mt_to_str(cx, mt)), vs)
+        vstore_ty_to_str(cx, mt, vs)
       }
       ty_estr(vs) => fmt!("%s%s", vstore_to_str(cx, vs), ~"str"),
       ty_opaque_box => ~"@?",
@@ -747,6 +750,12 @@ impl Repr for ty::TraitStore {
     }
 }
 
+impl Repr for ty::vstore {
+    fn repr(&self, tcx: ctxt) -> ~str {
+        vstore_to_str(tcx, *self)
+    }
+}
+
 // Local Variables:
 // mode: rust
 // fill-column: 78;
diff --git a/src/libstd/arena.rs b/src/libstd/arena.rs
index 81c28f94d9f..3d2c3ac70b6 100644
--- a/src/libstd/arena.rs
+++ b/src/libstd/arena.rs
@@ -171,7 +171,7 @@ unsafe fn un_bitpack_tydesc_ptr(p: uint) -> (*TypeDesc, bool) {
 
 pub impl Arena {
     // Functions for the POD part of the arena
-    fn alloc_pod_grow(&self, n_bytes: uint, align: uint) -> *u8 {
+    priv fn alloc_pod_grow(&self, n_bytes: uint, align: uint) -> *u8 {
         // Allocate a new chunk.
         let chunk_size = at_vec::capacity(self.pod_head.data);
         let new_min_chunk_size = uint::max(n_bytes, chunk_size);
@@ -183,7 +183,7 @@ pub impl Arena {
     }
 
     #[inline(always)]
-    fn alloc_pod_inner(&self, n_bytes: uint, align: uint) -> *u8 {
+    priv fn alloc_pod_inner(&self, n_bytes: uint, align: uint) -> *u8 {
         let head = &mut self.pod_head;
 
         let start = round_up_to(head.fill, align);
@@ -202,7 +202,22 @@ pub impl Arena {
     }
 
     #[inline(always)]
-    fn alloc_pod<T>(&self, op: &fn() -> T) -> &'self T {
+    #[cfg(stage0)]
+    priv fn alloc_pod<T>(&self, op: &fn() -> T) -> &'self T {
+        unsafe {
+            let tydesc = sys::get_type_desc::<T>();
+            let ptr = self.alloc_pod_inner((*tydesc).size, (*tydesc).align);
+            let ptr: *mut T = reinterpret_cast(&ptr);
+            rusti::move_val_init(&mut (*ptr), op());
+            return reinterpret_cast(&ptr);
+        }
+    }
+
+    #[inline(always)]
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    priv fn alloc_pod<'a, T>(&'a self, op: &fn() -> T) -> &'a T {
         unsafe {
             let tydesc = sys::get_type_desc::<T>();
             let ptr = self.alloc_pod_inner((*tydesc).size, (*tydesc).align);
@@ -213,7 +228,7 @@ pub impl Arena {
     }
 
     // Functions for the non-POD part of the arena
-    fn alloc_nonpod_grow(&self, n_bytes: uint, align: uint) -> (*u8, *u8) {
+    priv fn alloc_nonpod_grow(&self, n_bytes: uint, align: uint) -> (*u8, *u8) {
         // Allocate a new chunk.
         let chunk_size = at_vec::capacity(self.head.data);
         let new_min_chunk_size = uint::max(n_bytes, chunk_size);
@@ -225,7 +240,7 @@ pub impl Arena {
     }
 
     #[inline(always)]
-    fn alloc_nonpod_inner(&self, n_bytes: uint, align: uint) -> (*u8, *u8) {
+    priv fn alloc_nonpod_inner(&self, n_bytes: uint, align: uint) -> (*u8, *u8) {
         let head = &mut self.head;
 
         let tydesc_start = head.fill;
@@ -247,7 +262,32 @@ pub impl Arena {
     }
 
     #[inline(always)]
-    fn alloc_nonpod<T>(&self, op: &fn() -> T) -> &'self T {
+    #[cfg(stage0)]
+    priv fn alloc_nonpod<T>(&self, op: &fn() -> T) -> &'self T {
+        unsafe {
+            let tydesc = sys::get_type_desc::<T>();
+            let (ty_ptr, ptr) =
+                self.alloc_nonpod_inner((*tydesc).size, (*tydesc).align);
+            let ty_ptr: *mut uint = reinterpret_cast(&ty_ptr);
+            let ptr: *mut T = reinterpret_cast(&ptr);
+            // Write in our tydesc along with a bit indicating that it
+            // has *not* been initialized yet.
+            *ty_ptr = reinterpret_cast(&tydesc);
+            // Actually initialize it
+            rusti::move_val_init(&mut(*ptr), op());
+            // Now that we are done, update the tydesc to indicate that
+            // the object is there.
+            *ty_ptr = bitpack_tydesc_ptr(tydesc, true);
+
+            return reinterpret_cast(&ptr);
+        }
+    }
+
+    #[inline(always)]
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    priv fn alloc_nonpod<'a, T>(&'a self, op: &fn() -> T) -> &'a T {
         unsafe {
             let tydesc = sys::get_type_desc::<T>();
             let (ty_ptr, ptr) =
@@ -269,6 +309,7 @@ pub impl Arena {
 
     // The external interface
     #[inline(always)]
+    #[cfg(stage0)]
     fn alloc<T>(&self, op: &fn() -> T) -> &'self T {
         unsafe {
             if !rusti::needs_drop::<T>() {
@@ -278,6 +319,21 @@ pub impl Arena {
             }
         }
     }
+
+    // The external interface
+    #[inline(always)]
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn alloc<'a, T>(&'a self, op: &fn() -> T) -> &'a T {
+        unsafe {
+            if !rusti::needs_drop::<T>() {
+                self.alloc_pod(op)
+            } else {
+                self.alloc_nonpod(op)
+            }
+        }
+    }
 }
 
 #[test]
diff --git a/src/libstd/bitv.rs b/src/libstd/bitv.rs
index f69e2130e71..632a38e8ca2 100644
--- a/src/libstd/bitv.rs
+++ b/src/libstd/bitv.rs
@@ -437,8 +437,7 @@ pub impl Bitv {
             if offset >= bitv.nbits {
                 0
             } else {
-                // NOTE cannot use bitv[offset] until snapshot
-                bitv.index(&offset) as u8 << (7 - bit)
+                bitv[offset] as u8 << (7 - bit)
             }
         }
 
@@ -460,8 +459,7 @@ pub impl Bitv {
      * Transform self into a [bool] by turning each bit into a bool
      */
     fn to_bools(&self) -> ~[bool] {
-        // NOTE cannot use self[i] until snapshot
-        vec::from_fn(self.nbits, |i| self.index(&i))
+        vec::from_fn(self.nbits, |i| self[i])
     }
 
     /**
diff --git a/src/libstd/deque.rs b/src/libstd/deque.rs
index e7ec86963ee..a88d13fda66 100644
--- a/src/libstd/deque.rs
+++ b/src/libstd/deque.rs
@@ -41,6 +41,7 @@ impl<T> Mutable for Deque<T> {
     }
 }
 
+#[cfg(stage0)]
 pub impl<T> Deque<T> {
     /// Create an empty Deque
     fn new() -> Deque<T> {
@@ -51,21 +52,142 @@ pub impl<T> Deque<T> {
     /// Return a reference to the first element in the deque
     ///
     /// Fails if the deque is empty
+    #[cfg(stage0)]
     fn peek_front(&self) -> &'self T { get(self.elts, self.lo) }
 
+    /// Return a reference to the first element in the deque
+    ///
+    /// Fails if the deque is empty
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn peek_front<'a>(&'a self) -> &'a T { get(self.elts, self.lo) }
+
     /// Return a reference to the last element in the deque
     ///
     /// Fails if the deque is empty
+    #[cfg(stage0)]
     fn peek_back(&self) -> &'self T { get(self.elts, self.hi - 1u) }
 
+    /// Return a reference to the last element in the deque
+    ///
+    /// Fails if the deque is empty
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn peek_back<'a>(&'a self) -> &'a T { get(self.elts, self.hi - 1u) }
+
     /// Retrieve an element in the deque by index
     ///
     /// Fails if there is no element with the given index
+    #[cfg(stage0)]
     fn get(&self, i: int) -> &'self T {
         let idx = (self.lo + (i as uint)) % self.elts.len();
         get(self.elts, idx)
     }
 
+    /// Retrieve an element in the deque by index
+    ///
+    /// Fails if there is no element with the given index
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn get<'a>(&'a self, i: int) -> &'a T {
+        let idx = (self.lo + (i as uint)) % self.elts.len();
+        get(self.elts, idx)
+    }
+
+    /// Iterate over the elements in the deque
+    fn each(&self, f: &fn(&T) -> bool) {
+        self.eachi(|_i, e| f(e))
+    }
+
+    /// Iterate over the elements in the deque by index
+    fn eachi(&self, f: &fn(uint, &T) -> bool) {
+        for uint::range(0, self.nelts) |i| {
+            if !f(i, self.get(i as int)) { return; }
+        }
+    }
+
+    /// Remove and return the first element in the deque
+    ///
+    /// Fails if the deque is empty
+    fn pop_front(&mut self) -> T {
+        let mut result = self.elts[self.lo].swap_unwrap();
+        self.lo = (self.lo + 1u) % self.elts.len();
+        self.nelts -= 1u;
+        result
+    }
+
+    /// Remove and return the last element in the deque
+    ///
+    /// Fails if the deque is empty
+    fn pop_back(&mut self) -> T {
+        if self.hi == 0u {
+            self.hi = self.elts.len() - 1u;
+        } else { self.hi -= 1u; }
+        let mut result = self.elts[self.hi].swap_unwrap();
+        self.elts[self.hi] = None;
+        self.nelts -= 1u;
+        result
+    }
+
+    /// Prepend an element to the deque
+    fn add_front(&mut self, t: T) {
+        let oldlo = self.lo;
+        if self.lo == 0u {
+            self.lo = self.elts.len() - 1u;
+        } else { self.lo -= 1u; }
+        if self.lo == self.hi {
+            self.elts = grow(self.nelts, oldlo, self.elts);
+            self.lo = self.elts.len() - 1u;
+            self.hi = self.nelts;
+        }
+        self.elts[self.lo] = Some(t);
+        self.nelts += 1u;
+    }
+
+    /// Append an element to the deque
+    fn add_back(&mut self, t: T) {
+        if self.lo == self.hi && self.nelts != 0u {
+            self.elts = grow(self.nelts, self.lo, self.elts);
+            self.lo = 0u;
+            self.hi = self.nelts;
+        }
+        self.elts[self.hi] = Some(t);
+        self.hi = (self.hi + 1u) % self.elts.len();
+        self.nelts += 1u;
+    }
+}
+
+#[cfg(stage1)]
+#[cfg(stage2)]
+#[cfg(stage3)]
+pub impl<T> Deque<T> {
+    /// Create an empty Deque
+    fn new() -> Deque<T> {
+        Deque{nelts: 0, lo: 0, hi: 0,
+              elts: vec::from_fn(initial_capacity, |_| None)}
+    }
+
+    /// Return a reference to the first element in the deque
+    ///
+    /// Fails if the deque is empty
+    fn peek_front<'a>(&'a self) -> &'a T { get(self.elts, self.lo) }
+
+    /// Return a reference to the last element in the deque
+    ///
+    /// Fails if the deque is empty
+    fn peek_back<'a>(&'a self) -> &'a T { get(self.elts, self.hi - 1u) }
+
+    /// Retrieve an element in the deque by index
+    ///
+    /// Fails if there is no element with the given index
+    fn get<'a>(&'a self, i: int) -> &'a T {
+        let idx = (self.lo + (i as uint)) % self.elts.len();
+        get(self.elts, idx)
+    }
+
     /// Iterate over the elements in the deque
     fn each(&self, f: &fn(&T) -> bool) {
         self.eachi(|_i, e| f(e))
diff --git a/src/libstd/future.rs b/src/libstd/future.rs
index a4887306d2a..feea8fb4fcd 100644
--- a/src/libstd/future.rs
+++ b/src/libstd/future.rs
@@ -55,7 +55,7 @@ pub impl<A:Copy> Future<A> {
 }
 
 pub impl<A> Future<A> {
-
+    #[cfg(stage0)]
     fn get_ref(&self) -> &'self A {
         /*!
         * Executes the future's closure and then returns a borrowed
@@ -80,6 +80,34 @@ pub impl<A> Future<A> {
             }
         }
     }
+
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn get_ref<'a>(&'a self) -> &'a A {
+        /*!
+        * Executes the future's closure and then returns a borrowed
+        * pointer to the result.  The borrowed pointer lasts as long as
+        * the future.
+        */
+        unsafe {
+            match self.state {
+                Forced(ref mut v) => { return cast::transmute(v); }
+                Evaluating => fail!(~"Recursive forcing of future!"),
+                Pending(_) => {}
+            }
+
+            let mut state = Evaluating;
+            self.state <-> state;
+            match state {
+                Forced(_) | Evaluating => fail!(~"Logic error."),
+                Pending(f) => {
+                    self.state = Forced(f());
+                    self.get_ref()
+                }
+            }
+        }
+    }
 }
 
 pub fn from_value<A>(val: A) -> Future<A> {
diff --git a/src/libstd/priority_queue.rs b/src/libstd/priority_queue.rs
index dd56e413595..c8d250f90f6 100644
--- a/src/libstd/priority_queue.rs
+++ b/src/libstd/priority_queue.rs
@@ -50,13 +50,29 @@ impl<T:Ord> Mutable for PriorityQueue<T> {
 
 pub impl <T:Ord> PriorityQueue<T> {
     /// Returns the greatest item in the queue - fails if empty
+    #[cfg(stage0)]
     fn top(&self) -> &'self T { &self.data[0] }
 
+    /// Returns the greatest item in the queue - fails if empty
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn top<'a>(&'a self) -> &'a T { &self.data[0] }
+
     /// Returns the greatest item in the queue - None if empty
+    #[cfg(stage0)]
     fn maybe_top(&self) -> Option<&'self T> {
         if self.is_empty() { None } else { Some(self.top()) }
     }
 
+    /// Returns the greatest item in the queue - None if empty
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn maybe_top<'a>(&'a self) -> Option<&'a T> {
+        if self.is_empty() { None } else { Some(self.top()) }
+    }
+
     /// Returns the number of elements the queue can hold without reallocating
     fn capacity(&self) -> uint { vec::capacity(&self.data) }
 
diff --git a/src/libstd/smallintmap.rs b/src/libstd/smallintmap.rs
index 811cd710a62..d50804ba47b 100644
--- a/src/libstd/smallintmap.rs
+++ b/src/libstd/smallintmap.rs
@@ -51,6 +51,7 @@ impl<V> Map<uint, V> for SmallIntMap<V> {
     }
 
     /// Visit all key-value pairs in order
+    #[cfg(stage0)]
     fn each(&self, it: &fn(&uint, &'self V) -> bool) {
         for uint::range(0, self.v.len()) |i| {
             match self.v[i] {
@@ -60,18 +61,40 @@ impl<V> Map<uint, V> for SmallIntMap<V> {
         }
     }
 
+    /// Visit all key-value pairs in order
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn each<'a>(&'a self, it: &fn(&uint, &'a V) -> bool) {
+        for uint::range(0, self.v.len()) |i| {
+            match self.v[i] {
+              Some(ref elt) => if !it(&i, elt) { break },
+              None => ()
+            }
+        }
+    }
+
     /// Visit all keys in order
     fn each_key(&self, blk: &fn(key: &uint) -> bool) {
         self.each(|k, _| blk(k))
     }
 
     /// Visit all values in order
+    #[cfg(stage0)]
     fn each_value(&self, blk: &fn(value: &V) -> bool) {
         self.each(|_, v| blk(v))
     }
 
+    /// Visit all values in order
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn each_value<'a>(&'a self, blk: &fn(value: &'a V) -> bool) {
+        self.each(|_, v| blk(v))
+    }
+
     /// Iterate over the map and mutate the contained values
-    fn mutate_values(&mut self, it: &fn(&uint, &'self mut V) -> bool) {
+    fn mutate_values(&mut self, it: &fn(&uint, &mut V) -> bool) {
         for uint::range(0, self.v.len()) |i| {
             match self.v[i] {
               Some(ref mut elt) => if !it(&i, elt) { break },
@@ -81,6 +104,7 @@ impl<V> Map<uint, V> for SmallIntMap<V> {
     }
 
     /// Return a reference to the value corresponding to the key
+    #[cfg(stage0)]
     fn find(&self, key: &uint) -> Option<&'self V> {
         if *key < self.v.len() {
             match self.v[*key] {
@@ -92,7 +116,23 @@ impl<V> Map<uint, V> for SmallIntMap<V> {
         }
     }
 
+    /// Return a reference to the value corresponding to the key
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn find<'a>(&'a self, key: &uint) -> Option<&'a V> {
+        if *key < self.v.len() {
+            match self.v[*key] {
+              Some(ref value) => Some(value),
+              None => None
+            }
+        } else {
+            None
+        }
+    }
+
     /// Return a mutable reference to the value corresponding to the key
+    #[cfg(stage0)]
     fn find_mut(&mut self, key: &uint) -> Option<&'self mut V> {
         if *key < self.v.len() {
             match self.v[*key] {
@@ -104,6 +144,21 @@ impl<V> Map<uint, V> for SmallIntMap<V> {
         }
     }
 
+    /// Return a mutable reference to the value corresponding to the key
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn find_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut V> {
+        if *key < self.v.len() {
+            match self.v[*key] {
+              Some(ref mut value) => Some(value),
+              None => None
+            }
+        } else {
+            None
+        }
+    }
+
     /// Insert a key-value pair into the map. An existing value for a
     /// key is replaced by the new value. Return true if the key did
     /// not already exist in the map.
@@ -134,6 +189,7 @@ pub impl<V> SmallIntMap<V> {
     fn new() -> SmallIntMap<V> { SmallIntMap{v: ~[]} }
 
     /// Visit all key-value pairs in reverse order
+    #[cfg(stage0)]
     fn each_reverse(&self, it: &fn(uint, &'self V) -> bool) {
         for uint::range_rev(self.v.len(), 0) |i| {
             match self.v[i - 1] {
@@ -143,9 +199,30 @@ pub impl<V> SmallIntMap<V> {
         }
     }
 
+    /// Visit all key-value pairs in reverse order
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn each_reverse<'a>(&'a self, it: &fn(uint, &'a V) -> bool) {
+        for uint::range_rev(self.v.len(), 0) |i| {
+            match self.v[i - 1] {
+              Some(ref elt) => if !it(i - 1, elt) { break },
+              None => ()
+            }
+        }
+    }
+
+    #[cfg(stage0)]
     fn get(&self, key: &uint) -> &'self V {
         self.find(key).expect("key not present")
     }
+
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn get<'a>(&'a self, key: &uint) -> &'a V {
+        self.find(key).expect("key not present")
+    }
 }
 
 pub impl<V:Copy> SmallIntMap<V> {
diff --git a/src/libstd/treemap.rs b/src/libstd/treemap.rs
index 041ea855cb3..006455c44e4 100644
--- a/src/libstd/treemap.rs
+++ b/src/libstd/treemap.rs
@@ -105,26 +105,45 @@ impl<K: TotalOrd, V> Map<K, V> for TreeMap<K, V> {
     }
 
     /// Visit all key-value pairs in order
+    #[cfg(stage0)]
     fn each(&self, f: &fn(&'self K, &'self V) -> bool) {
         each(&self.root, f)
     }
 
+    /// Visit all key-value pairs in order
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn each<'a>(&'a self, f: &fn(&'a K, &'a V) -> bool) {
+        each(&self.root, f)
+    }
+
     /// Visit all keys in order
     fn each_key(&self, f: &fn(&K) -> bool) {
         self.each(|k, _| f(k))
     }
 
     /// Visit all values in order
+    #[cfg(stage0)]
     fn each_value(&self, f: &fn(&V) -> bool) {
         self.each(|_, v| f(v))
     }
 
+    /// Visit all values in order
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn each_value<'a>(&'a self, f: &fn(&'a V) -> bool) {
+        self.each(|_, v| f(v))
+    }
+
     /// Iterate over the map and mutate the contained values
-    fn mutate_values(&mut self, f: &fn(&'self K, &'self mut V) -> bool) {
+    fn mutate_values(&mut self, f: &fn(&K, &mut V) -> bool) {
         mutate_values(&mut self.root, f);
     }
 
     /// Return a reference to the value corresponding to the key
+    #[cfg(stage0)]
     fn find(&self, key: &K) -> Option<&'self V> {
         let mut current: &'self Option<~TreeNode<K, V>> = &self.root;
         loop {
@@ -141,12 +160,42 @@ impl<K: TotalOrd, V> Map<K, V> for TreeMap<K, V> {
         }
     }
 
+    /// Return a reference to the value corresponding to the key
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn find<'a>(&'a self, key: &K) -> Option<&'a V> {
+        let mut current: &'a Option<~TreeNode<K, V>> = &self.root;
+        loop {
+            match *current {
+              Some(ref r) => {
+                match key.cmp(&r.key) {
+                  Less => current = &r.left,
+                  Greater => current = &r.right,
+                  Equal => return Some(&r.value)
+                }
+              }
+              None => return None
+            }
+        }
+    }
+
     /// Return a mutable reference to the value corresponding to the key
     #[inline(always)]
+    #[cfg(stage0)]
     fn find_mut(&mut self, key: &K) -> Option<&'self mut V> {
         find_mut(&mut self.root, key)
     }
 
+    /// Return a mutable reference to the value corresponding to the key
+    #[inline(always)]
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V> {
+        find_mut(&mut self.root, key)
+    }
+
     /// Insert a key-value pair into the map. An existing value for a
     /// key is replaced by the new value. Return true if the key did
     /// not already exist in the map.
@@ -170,7 +219,16 @@ pub impl<K: TotalOrd, V> TreeMap<K, V> {
     fn new() -> TreeMap<K, V> { TreeMap{root: None, length: 0} }
 
     /// Visit all key-value pairs in reverse order
-    fn each_reverse(&'self self, f: &fn(&'self K, &'self V) -> bool) {
+    #[cfg(stage0)]
+    fn each_reverse(&self, f: &fn(&'self K, &'self V) -> bool) {
+        each_reverse(&self.root, f);
+    }
+
+    /// Visit all key-value pairs in reverse order
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn each_reverse<'a>(&'a self, f: &fn(&'a K, &'a V) -> bool) {
         each_reverse(&self.root, f);
     }
 
@@ -186,9 +244,19 @@ pub impl<K: TotalOrd, V> TreeMap<K, V> {
 
     /// Get a lazy iterator over the key-value pairs in the map.
     /// Requires that it be frozen (immutable).
+    #[cfg(stage0)]
     fn iter(&self) -> TreeMapIterator<'self, K, V> {
         TreeMapIterator{stack: ~[], node: &self.root}
     }
+
+    /// Get a lazy iterator over the key-value pairs in the map.
+    /// Requires that it be frozen (immutable).
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn iter<'a>(&'a self) -> TreeMapIterator<'a, K, V> {
+        TreeMapIterator{stack: ~[], node: &self.root}
+    }
 }
 
 /// Lazy forward iterator over a map
@@ -490,9 +558,20 @@ pub impl <T: TotalOrd> TreeSet<T> {
     /// Get a lazy iterator over the values in the set.
     /// Requires that it be frozen (immutable).
     #[inline(always)]
+    #[cfg(stage0)]
     fn iter(&self) -> TreeSetIterator<'self, T> {
         TreeSetIterator{iter: self.map.iter()}
     }
+
+    /// Get a lazy iterator over the values in the set.
+    /// Requires that it be frozen (immutable).
+    #[inline(always)]
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn iter<'a>(&'a self) -> TreeSetIterator<'a, T> {
+        TreeSetIterator{iter: self.map.iter()}
+    }
 }
 
 /// Lazy forward iterator over a set
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index 4add371a36f..9c20012d42e 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -1002,15 +1002,6 @@ pub enum self_ty_ {
     sty_uniq(mutability)                       // `~self`
 }
 
-impl self_ty_ {
-    fn is_borrowed(&self) -> bool {
-        match *self {
-            sty_region(*) => true,
-            _ => false
-        }
-    }
-}
-
 pub type self_ty = spanned<self_ty_>;
 
 #[auto_encode]
diff --git a/src/libsyntax/ext/base.rs b/src/libsyntax/ext/base.rs
index 92f0c7c7679..886af694920 100644
--- a/src/libsyntax/ext/base.rs
+++ b/src/libsyntax/ext/base.rs
@@ -454,6 +454,7 @@ impl <K: Eq + Hash + IterBytes ,V: Copy> MapChain<K,V>{
 
     // ugh: can't get this to compile with mut because of the
     // lack of flow sensitivity.
+    #[cfg(stage0)]
     fn get_map(&self) -> &'self HashMap<K,@V> {
         match *self {
             BaseMapChain (~ref map) => map,
@@ -461,6 +462,18 @@ impl <K: Eq + Hash + IterBytes ,V: Copy> MapChain<K,V>{
         }
     }
 
+    // ugh: can't get this to compile with mut because of the
+    // lack of flow sensitivity.
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn get_map<'a>(&'a self) -> &'a HashMap<K,@V> {
+        match *self {
+            BaseMapChain (~ref map) => map,
+            ConsMapChain (~ref map,_) => map
+        }
+    }
+
 // traits just don't work anywhere...?
 //pub impl Map<Name,SyntaxExtension> for MapChain {
 
diff --git a/src/libsyntax/opt_vec.rs b/src/libsyntax/opt_vec.rs
index fd54746f3dc..1604c40f917 100644
--- a/src/libsyntax/opt_vec.rs
+++ b/src/libsyntax/opt_vec.rs
@@ -61,6 +61,7 @@ impl<T> OptVec<T> {
         }
     }
 
+    #[cfg(stage0)]
     fn get(&self, i: uint) -> &'self T {
         match *self {
             Empty => fail!(fmt!("Invalid index %u", i)),
@@ -68,6 +69,16 @@ impl<T> OptVec<T> {
         }
     }
 
+    #[cfg(stage1)]
+    #[cfg(stage2)]
+    #[cfg(stage3)]
+    fn get<'a>(&'a self, i: uint) -> &'a T {
+        match *self {
+            Empty => fail!(fmt!("Invalid index %u", i)),
+            Vec(ref v) => &v[i]
+        }
+    }
+
     fn is_empty(&self) -> bool {
         self.len() == 0
     }
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index 4e7e5144a7d..cf29f170f40 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -1632,6 +1632,10 @@ pub fn print_pat(s: @ps, &&pat: @ast::pat, refutable: bool) {
     (s.ann.post)(ann_node);
 }
 
+pub fn self_ty_to_str(self_ty: ast::self_ty_, intr: @ident_interner) -> ~str {
+    to_str(self_ty, |a, b| { print_self_ty(a, b); () }, intr)
+}
+
 // Returns whether it printed anything
 pub fn print_self_ty(s: @ps, self_ty: ast::self_ty_) -> bool {
     match self_ty {
diff --git a/src/test/compile-fail/issue-3311.rs b/src/test/compile-fail/issue-3311.rs
deleted file mode 100644
index 67059e4623e..00000000000
--- a/src/test/compile-fail/issue-3311.rs
+++ /dev/null
@@ -1,31 +0,0 @@
-// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-#[legacy_mode]
-struct Foo<'self> {
-    s: &'self str,
-    u: ~()
-}
-
-pub impl<'self> Foo<'self> {
-    fn get_s(&self) -> &'self str {
-        self.s
-    }
-}
-
-fn bar(s: &str, f: &fn(Option<Foo>)) {
-    f(Some(Foo {s: s, u: ~()}));
-}
-
-fn main() {
-    do bar(~"testing") |opt| {
-        io::println(opt.unwrap().get_s()); //~ ERROR illegal borrow:
-    };
-}
diff --git a/src/test/compile-fail/issue-3563.rs b/src/test/compile-fail/issue-3563.rs
index d56cb0d51d2..38f28bd79df 100644
--- a/src/test/compile-fail/issue-3563.rs
+++ b/src/test/compile-fail/issue-3563.rs
@@ -10,7 +10,7 @@
 
 trait A {
   fn a(&self) {
-      || self.b() //~ ERROR type `&'self Self` does not implement any method in scope named `b`
+      || self.b() //~ ERROR type `&Self` does not implement any method in scope named `b`
   }
 }
 fn main() {}
diff --git a/src/test/compile-fail/issue-3888.rs b/src/test/compile-fail/issue-3888.rs
deleted file mode 100644
index 35f8557c32b..00000000000
--- a/src/test/compile-fail/issue-3888.rs
+++ /dev/null
@@ -1,42 +0,0 @@
-// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-// n.b. This should be a run-pass test, but for now I'm testing
-// that we don't see an "unknown scope" error.
-fn vec_peek<'r, T>(v: &'r [T]) -> Option< (&'r T, &'r [T]) > {
-    if v.len() == 0 {
-        None
-    } else {
-        let vec_len = v.len();
-        let head = &v[0];
-        // note: this *shouldn't* be an illegal borrow! See #3888
-        let tail = v.slice(1, vec_len); //~ ERROR illegal borrow: borrowed value does not live long enough
-        Some( (head, tail) )
-    }
-}
-
-
-fn test_peek_empty_stack() {
-    let v : &[int] = &[];
-    assert!((None == vec_peek(v)));
-}
-
-fn test_peek_empty_unique() {
-    let v : ~[int] = ~[];
-    assert!((None == vec_peek(v)));
-}
-
-fn test_peek_empty_managed() {
-    let v : @[int] = @[];
-    assert!((None == vec_peek(v)));
-}
-
-
-fn main() {}
diff --git a/src/test/compile-fail/issue-3969.rs b/src/test/compile-fail/issue-3969.rs
index 60991d40a54..b60a54a44bb 100644
--- a/src/test/compile-fail/issue-3969.rs
+++ b/src/test/compile-fail/issue-3969.rs
@@ -18,7 +18,7 @@ trait BikeMethods {
 
 impl BikeMethods for Bike {
     fn woops() -> ~str { ~"foo" }
-    //~^ ERROR method `woops` is declared as static in its impl, but not in its trait
+    //~^ ERROR has a `&const self` declaration in the trait, but not in the impl
 }
 
 pub fn main() {
diff --git a/src/test/compile-fail/kindck-owned-trait-contains.rs b/src/test/compile-fail/kindck-owned-trait-contains.rs
index f5153265308..54ee8bcc70e 100644
--- a/src/test/compile-fail/kindck-owned-trait-contains.rs
+++ b/src/test/compile-fail/kindck-owned-trait-contains.rs
@@ -27,5 +27,6 @@ fn main() {
         let x: &'blk int = &3;
         repeater(@x)
     };
-    assert!(3 == *(y.get())); //~ ERROR reference is not valid
+    assert!(3 == *(y.get())); //~ ERROR dereference of reference outside its lifetime
+    //~^ ERROR reference is not valid outside of its lifetime
 }
diff --git a/src/test/compile-fail/regions-escape-via-trait-or-not.rs b/src/test/compile-fail/regions-escape-via-trait-or-not.rs
index fb9d963dc80..f7165784c79 100644
--- a/src/test/compile-fail/regions-escape-via-trait-or-not.rs
+++ b/src/test/compile-fail/regions-escape-via-trait-or-not.rs
@@ -24,9 +24,9 @@ fn with<R:deref>(f: &fn(x: &int) -> R) -> int {
 
 fn return_it() -> int {
     with(|o| o)
-    //~^ ERROR reference is not valid outside of its lifetime
+    //~^ ERROR cannot infer an appropriate lifetime due to conflicting requirements
     //~^^ ERROR reference is not valid outside of its lifetime
-    //~^^^ ERROR cannot infer an appropriate lifetime
+    //~^^^ ERROR reference is not valid outside of its lifetime
 }
 
 fn main() {
diff --git a/src/test/compile-fail/regions-free-region-ordering-callee.rs b/src/test/compile-fail/regions-free-region-ordering-callee.rs
new file mode 100644
index 00000000000..e5399fc7fa3
--- /dev/null
+++ b/src/test/compile-fail/regions-free-region-ordering-callee.rs
@@ -0,0 +1,37 @@
+// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Tests that callees correctly infer an ordering between free regions
+// that appear in their parameter list.  See also
+// regions-free-region-ordering-caller.rs
+
+fn ordering1<'a, 'b>(x: &'a &'b uint) -> &'a uint {
+    // It is safe to assume that 'a <= 'b due to the type of x
+    let y: &'b uint = &**x;
+    return y;
+}
+
+fn ordering2<'a, 'b>(x: &'a &'b uint, y: &'a uint) -> &'b uint {
+    // However, it is not safe to assume that 'b <= 'a
+    &*y //~ ERROR cannot infer an appropriate lifetime
+}
+
+fn ordering3<'a, 'b>(x: &'a uint, y: &'b uint) -> &'a &'b uint {
+    // Do not infer an ordering from the return value.
+    let z: &'b uint = &*x;
+    //~^ ERROR cannot infer an appropriate lifetime due to conflicting requirements
+    fail!();
+}
+
+fn ordering4<'a, 'b>(a: &'a uint, b: &'b uint, x: &fn(&'a &'b uint)) {
+    let z: Option<&'a &'b uint> = None;
+}
+
+fn main() {}
\ No newline at end of file
diff --git a/src/test/compile-fail/regions-free-region-ordering-caller.rs b/src/test/compile-fail/regions-free-region-ordering-caller.rs
new file mode 100644
index 00000000000..d06dcd8aa86
--- /dev/null
+++ b/src/test/compile-fail/regions-free-region-ordering-caller.rs
@@ -0,0 +1,40 @@
+// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test various ways to construct a pointer with a longer lifetime
+// than the thing it points at and ensure that they result in
+// errors. See also regions-free-region-ordering-callee.rs
+
+struct Paramd<'self> { x: &'self uint }
+
+fn call1<'a>(x: &'a uint) {
+    let y: uint = 3;
+    let z: &'a &'blk uint = &(&y);
+    //~^ ERROR pointer has a longer lifetime than the data it references
+}
+
+fn call2<'a, 'b>(a: &'a uint, b: &'b uint) {
+    let z: Option<&'b &'a uint> = None;
+    //~^ ERROR pointer has a longer lifetime than the data it references
+}
+
+fn call3<'a, 'b>(a: &'a uint, b: &'b uint) {
+    let y: Paramd<'a> = Paramd { x: a };
+    let z: Option<&'b Paramd<'a>> = None;
+    //~^ ERROR pointer has a longer lifetime than the data it references
+}
+
+fn call4<'a, 'b>(a: &'a uint, b: &'b uint) {
+    let z: Option<&fn(&'a &'b uint)> = None;
+    //~^ ERROR pointer has a longer lifetime than the data it references
+}
+
+
+fn main() {}
\ No newline at end of file
diff --git a/src/test/compile-fail/regions-infer-paramd-indirect.rs b/src/test/compile-fail/regions-infer-paramd-indirect.rs
index e4ad93bde17..e8d66ab297b 100644
--- a/src/test/compile-fail/regions-infer-paramd-indirect.rs
+++ b/src/test/compile-fail/regions-infer-paramd-indirect.rs
@@ -18,12 +18,12 @@ struct c<'self> {
     f: @b<'self>
 }
 
-trait set_f {
+trait set_f<'self> {
     fn set_f_ok(&self, b: @b<'self>);
     fn set_f_bad(&self, b: @b);
 }
 
-impl<'self> set_f for c<'self> {
+impl<'self> set_f<'self> for c<'self> {
     fn set_f_ok(&self, b: @b<'self>) {
         self.f = b;
     }
diff --git a/src/test/compile-fail/regions-trait-2.rs b/src/test/compile-fail/regions-trait-2.rs
index 5811496cab4..9855a234618 100644
--- a/src/test/compile-fail/regions-trait-2.rs
+++ b/src/test/compile-fail/regions-trait-2.rs
@@ -8,6 +8,11 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+// xfail-test #5723
+
+// Test that you cannot escape a borrowed pointer
+// into a trait.
+
 struct ctxt { v: uint }
 
 trait get_ctxt {
@@ -24,8 +29,9 @@ fn make_gc() -> @get_ctxt  {
     let ctxt = ctxt { v: 22u };
     let hc = has_ctxt { c: &ctxt };
     return @hc as @get_ctxt;
+    //^~ ERROR source contains borrowed pointer
 }
 
 fn main() {
-    make_gc().get_ctxt().v; //~ ERROR illegal borrow
+    make_gc().get_ctxt().v;
 }
diff --git a/src/test/compile-fail/staticness-mismatch.rs b/src/test/compile-fail/staticness-mismatch.rs
index 719da233335..9bcf0777bbd 100644
--- a/src/test/compile-fail/staticness-mismatch.rs
+++ b/src/test/compile-fail/staticness-mismatch.rs
@@ -14,7 +14,7 @@ trait foo {
 }
 
 impl foo for int {
-    fn bar(&self) {} //~ ERROR method `bar` is declared as static in its trait, but not in its impl
+    fn bar(&self) {} //~ ERROR method `bar` has a `&self` declaration in the impl, but not in the trait
 }
 
 fn main() {}
diff --git a/src/test/run-pass/class-impl-very-parameterized-trait.rs b/src/test/run-pass/class-impl-very-parameterized-trait.rs
index cfde61d74b2..e4374e4d225 100644
--- a/src/test/run-pass/class-impl-very-parameterized-trait.rs
+++ b/src/test/run-pass/class-impl-very-parameterized-trait.rs
@@ -59,7 +59,7 @@ impl<T> Mutable for cat<T> {
 }
 
 impl<T> Map<int, T> for cat<T> {
-    fn each(&self, f: &fn(&int, &T) -> bool) {
+    fn each<'a>(&'a self, f: &fn(&int, &'a T) -> bool) {
         let mut n = int::abs(self.meows);
         while n > 0 {
             if !f(&n, &self.name) { break; }
@@ -73,7 +73,7 @@ impl<T> Map<int, T> for cat<T> {
         for self.each |k, _| { if !f(k) { break; } loop;};
     }
 
-    fn each_value(&self, f: &fn(v: &T) -> bool) {
+    fn each_value<'a>(&'a self, f: &fn(v: &'a T) -> bool) {
         for self.each |_, v| { if !f(v) { break; } loop;};
     }
 
@@ -86,7 +86,7 @@ impl<T> Map<int, T> for cat<T> {
         true
     }
 
-    fn find(&self, k: &int) -> Option<&'self T> {
+    fn find<'a>(&'a self, k: &int) -> Option<&'a T> {
         if *k <= self.meows {
             Some(&self.name)
         } else {
@@ -94,7 +94,7 @@ impl<T> Map<int, T> for cat<T> {
         }
     }
 
-    fn find_mut(&mut self, _k: &int) -> Option<&'self mut T> { fail!() }
+    fn find_mut<'a>(&'a mut self, _k: &int) -> Option<&'a mut T> { fail!() }
 
     fn remove(&mut self, k: &int) -> bool {
         if self.find(k).is_some() {
@@ -106,7 +106,7 @@ impl<T> Map<int, T> for cat<T> {
 }
 
 pub impl<T> cat<T> {
-    fn get(&self, k: &int) -> &'self T {
+    fn get<'a>(&'a self, k: &int) -> &'a T {
         match self.find(k) {
           Some(v) => { v }
           None    => { fail!(~"epic fail"); }
diff --git a/src/test/run-pass/explicit-self.rs b/src/test/run-pass/explicit-self.rs
index c5b5016572c..7e46bf22c4d 100644
--- a/src/test/run-pass/explicit-self.rs
+++ b/src/test/run-pass/explicit-self.rs
@@ -58,7 +58,7 @@ pub impl thing {
     fn foo(@self) -> int { *self.x.a }
     fn bar(~self) -> int { *self.x.a }
     fn quux(&self) -> int { *self.x.a }
-    fn baz(&self) -> &'self A { &self.x }
+    fn baz<'a>(&'a self) -> &'a A { &self.x }
     fn spam(self) -> int { *self.x.a }
 }
 
diff --git a/src/test/run-pass/issue-3860.rs b/src/test/run-pass/issue-3860.rs
index 18839fa3c7f..46aa7187c9a 100644
--- a/src/test/run-pass/issue-3860.rs
+++ b/src/test/run-pass/issue-3860.rs
@@ -11,7 +11,7 @@
 struct Foo { x: int }
 
 pub impl Foo {
-    fn stuff(&mut self) -> &'self mut Foo {
+    fn stuff<'a>(&'a mut self) -> &'a mut Foo {
         return self;
     }
 }
diff --git a/src/test/run-pass/regions-parameterization-self-types-issue-5224.rs b/src/test/run-pass/regions-parameterization-self-types-issue-5224.rs
deleted file mode 100644
index 346a0fcfe07..00000000000
--- a/src/test/run-pass/regions-parameterization-self-types-issue-5224.rs
+++ /dev/null
@@ -1,38 +0,0 @@
-// Copyright 2013 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-// Test how region-parameterization inference
-// interacts with explicit self types.
-//
-// Issue #5224.
-
-trait Getter {
-    // This trait does not need to be
-    // region-parameterized, because 'self
-    // is bound in the self type:
-    fn get(&self) -> &'self int;
-}
-
-struct Foo {
-    field: int
-}
-
-impl Getter for Foo {
-    fn get(&self) -> &'self int { &self.field }
-}
-
-fn get_int<G: Getter>(g: &G) -> int {
-    *g.get()
-}
-
-pub fn main() {
-    let foo = Foo { field: 22 };
-    assert!(get_int(&foo) == 22);
-}
diff --git a/src/test/run-pass/regions-self-impls.rs b/src/test/run-pass/regions-self-impls.rs
index 16b6364093e..2f4eefe5243 100644
--- a/src/test/run-pass/regions-self-impls.rs
+++ b/src/test/run-pass/regions-self-impls.rs
@@ -16,7 +16,7 @@ trait get_chowder<'self> {
     fn get_chowder(&self) -> &'self int;
 }
 
-impl<'self> get_chowder for Clam<'self> {
+impl<'self> get_chowder<'self> for Clam<'self> {
     fn get_chowder(&self) -> &'self int { return self.chowder; }
 }
 
diff --git a/src/test/run-pass/regions-trait.rs b/src/test/run-pass/regions-trait.rs
index f4532720579..a2ed9da67f2 100644
--- a/src/test/run-pass/regions-trait.rs
+++ b/src/test/run-pass/regions-trait.rs
@@ -16,7 +16,7 @@ trait get_ctxt<'self> {
 
 struct HasCtxt<'self> { c: &'self Ctxt }
 
-impl<'self> get_ctxt for HasCtxt<'self> {
+impl<'self> get_ctxt<'self> for HasCtxt<'self> {
     fn get_ctxt(&self) -> &'self Ctxt {
         self.c
     }