auto merge of #5630 : erickt/rust/serial, r=erickt

@nikomatsakis and I were talking about how the serializers were a bit too complicated. None of the users of With the `emit_option` and `read_option` functions, the serializers are now moving more high level. This patch series continues that trend. I've removed support for emitting specific string and vec types, and added support for emitting mapping types.

14 files changed, 837 insertions, 759 deletions

diff --git a/src/libcore/hashmap.rs b/src/libcore/hashmap.rs
index 3df48ac70a2..9387ec4f432 100644
--- a/src/libcore/hashmap.rs
+++ b/src/libcore/hashmap.rs
@@ -393,10 +393,16 @@ pub mod linear {
         }
     }
 
-    pub impl<K:Hash + IterBytes + Eq,V> LinearMap<K, V> {
+    pub impl<K: Hash + IterBytes + Eq, V> LinearMap<K, V> {
         /// Create an empty LinearMap
         fn new() -> LinearMap<K, V> {
-            linear_map_with_capacity(INITIAL_CAPACITY)
+            LinearMap::with_capacity(INITIAL_CAPACITY)
+        }
+
+        /// Create an empty LinearMap with space for at least `n` elements in
+        /// the hash table.
+        fn with_capacity(capacity: uint) -> LinearMap<K, V> {
+            linear_map_with_capacity(capacity)
         }
 
         /// Reserve space for at least `n` elements in the hash table.
@@ -652,7 +658,15 @@ pub mod linear {
 
     pub impl <T:Hash + IterBytes + Eq> LinearSet<T> {
         /// Create an empty LinearSet
-        fn new() -> LinearSet<T> { LinearSet{map: LinearMap::new()} }
+        fn new() -> LinearSet<T> {
+            LinearSet::with_capacity(INITIAL_CAPACITY)
+        }
+
+        /// Create an empty LinearSet with space for at least `n` elements in
+        /// the hash table.
+        fn with_capacity(capacity: uint) -> LinearSet<T> {
+            LinearSet { map: LinearMap::with_capacity(capacity) }
+        }
 
         /// Reserve space for at least `n` elements in the hash table.
         fn reserve_at_least(&mut self, n: uint) {
diff --git a/src/libcore/vec.rs b/src/libcore/vec.rs
index 566bceaa86f..0ac86ac280d 100644
--- a/src/libcore/vec.rs
+++ b/src/libcore/vec.rs
@@ -560,6 +560,28 @@ pub fn consume<T>(mut v: ~[T], f: &fn(uint, v: T)) {
     }
 }
 
+pub fn consume_reverse<T>(mut v: ~[T], f: &fn(uint, v: T)) {
+    unsafe {
+        do as_mut_buf(v) |p, ln| {
+            let mut i = ln;
+            while i > 0 {
+                i -= 1;
+
+                // NB: This unsafe operation counts on init writing 0s to the
+                // holes we create in the vector. That ensures that, if the
+                // iterator fails then we won't try to clean up the consumed
+                // elements during unwinding
+                let mut x = intrinsics::init();
+                let p = ptr::mut_offset(p, i);
+                x <-> *p;
+                f(i, x);
+            }
+        }
+
+        raw::set_len(&mut v, 0);
+    }
+}
+
 /// Remove the last element from a vector and return it
 pub fn pop<T>(v: &mut ~[T]) -> T {
     let ln = v.len();
@@ -1985,6 +2007,7 @@ pub trait OwnedVector<T> {
     fn truncate(&mut self, newlen: uint);
     fn retain(&mut self, f: &fn(t: &T) -> bool);
     fn consume(self, f: &fn(uint, v: T));
+    fn consume_reverse(self, f: &fn(uint, v: T));
     fn filter(self, f: &fn(t: &T) -> bool) -> ~[T];
     fn partition(self, f: &fn(&T) -> bool) -> (~[T], ~[T]);
     fn grow_fn(&mut self, n: uint, op: iter::InitOp<T>);
@@ -2047,6 +2070,11 @@ impl<T> OwnedVector<T> for ~[T] {
     }
 
     #[inline]
+    fn consume_reverse(self, f: &fn(uint, v: T)) {
+        consume_reverse(self, f)
+    }
+
+    #[inline]
     fn filter(self, f: &fn(&T) -> bool) -> ~[T] {
         filter(self, f)
     }
diff --git a/src/librustc/middle/astencode.rs b/src/librustc/middle/astencode.rs
index 8dcfaf2eb35..b6b6730620e 100644
--- a/src/librustc/middle/astencode.rs
+++ b/src/librustc/middle/astencode.rs
@@ -558,7 +558,7 @@ trait read_method_map_entry_helper {
 fn encode_method_map_entry(ecx: @e::EncodeContext,
                               ebml_w: writer::Encoder,
                               mme: method_map_entry) {
-    do ebml_w.emit_rec {
+    do ebml_w.emit_struct("method_map_entry", 3) {
         do ebml_w.emit_field(~"self_arg", 0u) {
             ebml_w.emit_arg(ecx, mme.self_arg);
         }
@@ -574,7 +574,7 @@ fn encode_method_map_entry(ecx: @e::EncodeContext,
 impl read_method_map_entry_helper for reader::Decoder {
     fn read_method_map_entry(&self, xcx: @ExtendedDecodeContext)
         -> method_map_entry {
-        do self.read_rec {
+        do self.read_struct("method_map_entry", 3) {
             method_map_entry {
                 self_arg: self.read_field(~"self_arg", 0u, || {
                     self.read_arg(xcx)
@@ -778,7 +778,7 @@ impl ebml_writer_helpers for writer::Encoder {
 
     fn emit_tpbt(&self, ecx: @e::EncodeContext,
                  tpbt: ty::ty_param_bounds_and_ty) {
-        do self.emit_rec {
+        do self.emit_struct("ty_param_bounds_and_ty", 3) {
             do self.emit_field(~"bounds", 0) {
                 do self.emit_from_vec(*tpbt.bounds) |bs| {
                     self.emit_bounds(ecx, *bs);
@@ -1045,7 +1045,7 @@ impl ebml_decoder_decoder_helpers for reader::Decoder {
     fn read_ty_param_bounds_and_ty(&self, xcx: @ExtendedDecodeContext)
         -> ty::ty_param_bounds_and_ty
     {
-        do self.read_rec {
+        do self.read_struct("ty_param_bounds_and_ty", 3) {
             ty::ty_param_bounds_and_ty {
                 bounds: self.read_field(~"bounds", 0u, || {
                     @self.read_to_vec(|| self.read_bounds(xcx) )
@@ -1212,7 +1212,6 @@ fn mk_ctxt() -> @fake_ext_ctxt {
 #[cfg(test)]
 fn roundtrip(in_item: Option<@ast::item>) {
     use core::io;
-    use std::prettyprint;
 
     let in_item = in_item.get();
     let bytes = do io::with_bytes_writer |wr| {
@@ -1222,17 +1221,7 @@ fn roundtrip(in_item: Option<@ast::item>) {
     let ebml_doc = reader::Doc(@bytes);
     let out_item = decode_item_ast(ebml_doc);
 
-    let exp_str = do io::with_str_writer |w| {
-        in_item.encode(&prettyprint::Serializer(w))
-    };
-    let out_str = do io::with_str_writer |w| {
-        out_item.encode(&prettyprint::Serializer(w))
-    };
-
-    debug!("expected string: %s", exp_str);
-    debug!("actual string  : %s", out_str);
-
-    assert!(exp_str == out_str);
+    assert_eq!(in_item, out_item);
 }
 
 #[test]
diff --git a/src/libstd/deque.rs b/src/libstd/deque.rs
index e029b882472..e7ec86963ee 100644
--- a/src/libstd/deque.rs
+++ b/src/libstd/deque.rs
@@ -66,6 +66,18 @@ pub impl<T> Deque<T> {
         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
@@ -223,6 +235,7 @@ mod tests {
         assert!(*deq.get(3) == d);
     }
 
+    #[test]
     fn test_parameterized<T:Copy + Eq + Durable>(a: T, b: T, c: T, d: T) {
         let mut deq = Deque::new();
         assert!(deq.len() == 0);
@@ -300,4 +313,23 @@ mod tests {
         let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) };
         test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
     }
+
+    #[test]
+    fn test_eachi() {
+        let mut deq = Deque::new();
+        deq.add_back(1);
+        deq.add_back(2);
+        deq.add_back(3);
+
+        for deq.eachi |i, e| {
+            assert_eq!(*e, i + 1);
+        }
+
+        deq.pop_front();
+
+        for deq.eachi |i, e| {
+            assert_eq!(*e, i + 2);
+        }
+
+    }
 }
diff --git a/src/libstd/ebml.rs b/src/libstd/ebml.rs
index bc9fc3553fe..b117c8d9882 100644
--- a/src/libstd/ebml.rs
+++ b/src/libstd/ebml.rs
@@ -311,23 +311,10 @@ pub mod reader {
         fn read_f64(&self) -> f64 { fail!(~"read_f64()"); }
         fn read_f32(&self) -> f32 { fail!(~"read_f32()"); }
         fn read_float(&self) -> float { fail!(~"read_float()"); }
-
         fn read_char(&self) -> char { fail!(~"read_char()"); }
-
-        fn read_owned_str(&self) -> ~str { doc_as_str(self.next_doc(EsStr)) }
-        fn read_managed_str(&self) -> @str { fail!(~"read_managed_str()"); }
+        fn read_str(&self) -> ~str { doc_as_str(self.next_doc(EsStr)) }
 
         // Compound types:
-        fn read_owned<T>(&self, f: &fn() -> T) -> T {
-            debug!("read_owned()");
-            f()
-        }
-
-        fn read_managed<T>(&self, f: &fn() -> T) -> T {
-            debug!("read_managed()");
-            f()
-        }
-
         fn read_enum<T>(&self, name: &str, f: &fn() -> T) -> T {
             debug!("read_enum(%s)", name);
             self._check_label(name);
@@ -348,8 +335,8 @@ pub mod reader {
             f()
         }
 
-        fn read_owned_vec<T>(&self, f: &fn(uint) -> T) -> T {
-            debug!("read_owned_vec()");
+        fn read_seq<T>(&self, f: &fn(uint) -> T) -> T {
+            debug!("read_seq()");
             do self.push_doc(self.next_doc(EsVec)) {
                 let len = self._next_uint(EsVecLen);
                 debug!("  len=%u", len);
@@ -357,25 +344,11 @@ pub mod reader {
             }
         }
 
-        fn read_managed_vec<T>(&self, f: &fn(uint) -> T) -> T {
-            debug!("read_managed_vec()");
-            do self.push_doc(self.next_doc(EsVec)) {
-                let len = self._next_uint(EsVecLen);
-                debug!("  len=%u", len);
-                f(len)
-            }
-        }
-
-        fn read_vec_elt<T>(&self, idx: uint, f: &fn() -> T) -> T {
-            debug!("read_vec_elt(idx=%u)", idx);
+        fn read_seq_elt<T>(&self, idx: uint, f: &fn() -> T) -> T {
+            debug!("read_seq_elt(idx=%u)", idx);
             self.push_doc(self.next_doc(EsVecElt), f)
         }
 
-        fn read_rec<T>(&self, f: &fn() -> T) -> T {
-            debug!("read_rec()");
-            f()
-        }
-
         fn read_struct<T>(&self, name: &str, _len: uint, f: &fn() -> T) -> T {
             debug!("read_struct(name=%s)", name);
             f()
@@ -387,16 +360,6 @@ pub mod reader {
             f()
         }
 
-        fn read_tup<T>(&self, len: uint, f: &fn() -> T) -> T {
-            debug!("read_tup(len=%u)", len);
-            f()
-        }
-
-        fn read_tup_elt<T>(&self, idx: uint, f: &fn() -> T) -> T {
-            debug!("read_tup_elt(idx=%u)", idx);
-            f()
-        }
-
         fn read_option<T>(&self, f: &fn(bool) -> T) -> T {
             debug!("read_option()");
             do self.read_enum("Option") || {
@@ -409,6 +372,21 @@ pub mod reader {
                 }
             }
         }
+
+        fn read_map<T>(&self, _f: &fn(uint) -> T) -> T {
+            debug!("read_map()");
+            fail!(~"read_map is unimplemented");
+        }
+
+        fn read_map_elt_key<T>(&self, idx: uint, _f: &fn() -> T) -> T {
+            debug!("read_map_elt_key(idx=%u)", idx);
+            fail!(~"read_map_elt_val is unimplemented");
+        }
+
+        fn read_map_elt_val<T>(&self, idx: uint, _f: &fn() -> T) -> T {
+            debug!("read_map_elt_val(idx=%u)", idx);
+            fail!(~"read_map_elt_val is unimplemented");
+        }
     }
 }
 
@@ -620,22 +598,10 @@ pub mod writer {
             fail!(~"Unimplemented: serializing a char");
         }
 
-        fn emit_borrowed_str(&self, v: &str) {
+        fn emit_str(&self, v: &str) {
             self.wr_tagged_str(EsStr as uint, v)
         }
 
-        fn emit_owned_str(&self, v: &str) {
-            self.emit_borrowed_str(v)
-        }
-
-        fn emit_managed_str(&self, v: &str) {
-            self.emit_borrowed_str(v)
-        }
-
-        fn emit_borrowed(&self, f: &fn()) { f() }
-        fn emit_owned(&self, f: &fn()) { f() }
-        fn emit_managed(&self, f: &fn()) { f() }
-
         fn emit_enum(&self, name: &str, f: &fn()) {
             self._emit_label(name);
             self.wr_tag(EsEnum as uint, f)
@@ -647,35 +613,23 @@ pub mod writer {
         }
         fn emit_enum_variant_arg(&self, _idx: uint, f: &fn()) { f() }
 
-        fn emit_borrowed_vec(&self, len: uint, f: &fn()) {
+        fn emit_seq(&self, len: uint, f: &fn()) {
             do self.wr_tag(EsVec as uint) {
                 self._emit_tagged_uint(EsVecLen, len);
                 f()
             }
         }
 
-        fn emit_owned_vec(&self, len: uint, f: &fn()) {
-            self.emit_borrowed_vec(len, f)
-        }
-
-        fn emit_managed_vec(&self, len: uint, f: &fn()) {
-            self.emit_borrowed_vec(len, f)
-        }
-
-        fn emit_vec_elt(&self, _idx: uint, f: &fn()) {
+        fn emit_seq_elt(&self, _idx: uint, f: &fn()) {
             self.wr_tag(EsVecElt as uint, f)
         }
 
-        fn emit_rec(&self, f: &fn()) { f() }
         fn emit_struct(&self, _name: &str, _len: uint, f: &fn()) { f() }
         fn emit_field(&self, name: &str, _idx: uint, f: &fn()) {
             self._emit_label(name);
             f()
         }
 
-        fn emit_tup(&self, _len: uint, f: &fn()) { f() }
-        fn emit_tup_elt(&self, _idx: uint, f: &fn()) { f() }
-
         fn emit_option(&self, f: &fn()) {
             self.emit_enum("Option", f);
         }
@@ -685,6 +639,18 @@ pub mod writer {
         fn emit_option_some(&self, f: &fn()) {
             self.emit_enum_variant("Some", 1, 1, f)
         }
+
+        fn emit_map(&self, _len: uint, _f: &fn()) {
+            fail!(~"emit_map is unimplemented");
+        }
+
+        fn emit_map_elt_key(&self, _idx: uint, _f: &fn()) {
+            fail!(~"emit_map_elt_key is unimplemented");
+        }
+
+        fn emit_map_elt_val(&self, _idx: uint, _f: &fn()) {
+            fail!(~"emit_map_elt_val is unimplemented");
+        }
     }
 }
 
diff --git a/src/libstd/flatpipes.rs b/src/libstd/flatpipes.rs
index 74e7ad9dc3f..56c67156d3d 100644
--- a/src/libstd/flatpipes.rs
+++ b/src/libstd/flatpipes.rs
@@ -466,8 +466,8 @@ pub mod flatteners {
         fn from_writer(w: @Writer) -> Self;
     }
 
-    impl<'self> FromReader for json::Decoder<'self> {
-        fn from_reader(r: @Reader) -> json::Decoder<'self> {
+    impl FromReader for json::Decoder {
+        fn from_reader(r: @Reader) -> json::Decoder {
             match json::from_reader(r) {
                 Ok(json) => {
                     json::Decoder(json)
diff --git a/src/libstd/json.rs b/src/libstd/json.rs
index 190d2d3fe0b..e090d6bc036 100644
--- a/src/libstd/json.rs
+++ b/src/libstd/json.rs
@@ -105,20 +105,10 @@ impl serialize::Encoder for Encoder {
         self.wr.write_str(float::to_str_digits(v, 6u));
     }
 
-    fn emit_char(&self, v: char) { self.emit_borrowed_str(str::from_char(v)) }
-
-    fn emit_borrowed_str(&self, v: &str) { self.wr.write_str(escape_str(v)) }
-    fn emit_owned_str(&self, v: &str) { self.emit_borrowed_str(v) }
-    fn emit_managed_str(&self, v: &str) { self.emit_borrowed_str(v) }
-
-    fn emit_borrowed(&self, f: &fn()) { f() }
-    fn emit_owned(&self, f: &fn()) { f() }
-    fn emit_managed(&self, f: &fn()) { f() }
-
-    fn emit_enum(&self, _name: &str, f: &fn()) {
-        f()
-    }
+    fn emit_char(&self, v: char) { self.emit_str(str::from_char(v)) }
+    fn emit_str(&self, v: &str) { self.wr.write_str(escape_str(v)) }
 
+    fn emit_enum(&self, _name: &str, f: &fn()) { f() }
     fn emit_enum_variant(&self, name: &str, _id: uint, cnt: uint, f: &fn()) {
         // enums are encoded as strings or vectors:
         // Bunny => "Bunny"
@@ -140,28 +130,17 @@ impl serialize::Encoder for Encoder {
         f();
     }
 
-    fn emit_borrowed_vec(&self, _len: uint, f: &fn()) {
+    fn emit_seq(&self, _len: uint, f: &fn()) {
         self.wr.write_char('[');
         f();
         self.wr.write_char(']');
     }
 
-    fn emit_owned_vec(&self, len: uint, f: &fn()) {
-        self.emit_borrowed_vec(len, f)
-    }
-    fn emit_managed_vec(&self, len: uint, f: &fn()) {
-        self.emit_borrowed_vec(len, f)
-    }
-    fn emit_vec_elt(&self, idx: uint, f: &fn()) {
+    fn emit_seq_elt(&self, idx: uint, f: &fn()) {
         if idx != 0 { self.wr.write_char(','); }
         f()
     }
 
-    fn emit_rec(&self, f: &fn()) {
-        self.wr.write_char('{');
-        f();
-        self.wr.write_char('}');
-    }
     fn emit_struct(&self, _name: &str, _len: uint, f: &fn()) {
         self.wr.write_char('{');
         f();
@@ -174,16 +153,25 @@ impl serialize::Encoder for Encoder {
         f();
     }
 
-    fn emit_tup(&self, len: uint, f: &fn()) {
-        self.emit_borrowed_vec(len, f);
-    }
-    fn emit_tup_elt(&self, idx: uint, f: &fn()) {
-        self.emit_vec_elt(idx, f)
-    }
-
     fn emit_option(&self, f: &fn()) { f(); }
     fn emit_option_none(&self) { self.emit_nil(); }
     fn emit_option_some(&self, f: &fn()) { f(); }
+
+    fn emit_map(&self, _len: uint, f: &fn()) {
+        self.wr.write_char('{');
+        f();
+        self.wr.write_char('}');
+    }
+
+    fn emit_map_elt_key(&self, idx: uint, f: &fn()) {
+        if idx != 0 { self.wr.write_char(','); }
+        f()
+    }
+
+    fn emit_map_elt_val(&self, _idx: uint, f: &fn()) {
+        self.wr.write_char(':');
+        f()
+    }
 }
 
 pub struct PrettyEncoder {
@@ -224,15 +212,8 @@ impl serialize::Encoder for PrettyEncoder {
         self.wr.write_str(float::to_str_digits(v, 6u));
     }
 
-    fn emit_char(&self, v: char) { self.emit_borrowed_str(str::from_char(v)) }
-
-    fn emit_borrowed_str(&self, v: &str) { self.wr.write_str(escape_str(v)); }
-    fn emit_owned_str(&self, v: &str) { self.emit_borrowed_str(v) }
-    fn emit_managed_str(&self, v: &str) { self.emit_borrowed_str(v) }
-
-    fn emit_borrowed(&self, f: &fn()) { f() }
-    fn emit_owned(&self, f: &fn()) { f() }
-    fn emit_managed(&self, f: &fn()) { f() }
+    fn emit_char(&self, v: char) { self.emit_str(str::from_char(v)) }
+    fn emit_str(&self, v: &str) { self.wr.write_str(escape_str(v)); }
 
     fn emit_enum(&self, _name: &str, f: &fn()) { f() }
     fn emit_enum_variant(&self, name: &str, _id: uint, cnt: uint, f: &fn()) {
@@ -260,7 +241,7 @@ impl serialize::Encoder for PrettyEncoder {
         f()
     }
 
-    fn emit_borrowed_vec(&self, len: uint, f: &fn()) {
+    fn emit_seq(&self, len: uint, f: &fn()) {
         if len == 0 {
             self.wr.write_str("[]");
         } else {
@@ -273,13 +254,7 @@ impl serialize::Encoder for PrettyEncoder {
             self.wr.write_char(']');
         }
     }
-    fn emit_owned_vec(&self, len: uint, f: &fn()) {
-        self.emit_borrowed_vec(len, f)
-    }
-    fn emit_managed_vec(&self, len: uint, f: &fn()) {
-        self.emit_borrowed_vec(len, f)
-    }
-    fn emit_vec_elt(&self, idx: uint, f: &fn()) {
+    fn emit_seq_elt(&self, idx: uint, f: &fn()) {
         if idx == 0 {
             self.wr.write_char('\n');
         } else {
@@ -289,20 +264,17 @@ impl serialize::Encoder for PrettyEncoder {
         f()
     }
 
-    fn emit_rec(&self, f: &fn()) {
-        self.wr.write_char('{');
-        self.indent += 2;
-        f();
-        self.wr.write_char('\n');
-        self.indent -= 2;
-        self.wr.write_str(spaces(self.indent));
-        self.wr.write_char('}');
-    }
     fn emit_struct(&self, _name: &str, len: uint, f: &fn()) {
         if len == 0 {
             self.wr.write_str("{}");
         } else {
-            self.emit_rec(f)
+            self.wr.write_char('{');
+            self.indent += 2;
+            f();
+            self.wr.write_char('\n');
+            self.indent -= 2;
+            self.wr.write_str(spaces(self.indent));
+            self.wr.write_char('}');
         }
     }
     fn emit_field(&self, name: &str, idx: uint, f: &fn()) {
@@ -316,37 +288,49 @@ impl serialize::Encoder for PrettyEncoder {
         self.wr.write_str(": ");
         f();
     }
-    fn emit_tup(&self, sz: uint, f: &fn()) {
-        self.emit_borrowed_vec(sz, f);
-    }
-    fn emit_tup_elt(&self, idx: uint, f: &fn()) {
-        self.emit_vec_elt(idx, f)
-    }
 
     fn emit_option(&self, f: &fn()) { f(); }
     fn emit_option_none(&self) { self.emit_nil(); }
     fn emit_option_some(&self, f: &fn()) { f(); }
+
+    fn emit_map(&self, len: uint, f: &fn()) {
+        if len == 0 {
+            self.wr.write_str("{}");
+        } else {
+            self.wr.write_char('{');
+            self.indent += 2;
+            f();
+            self.wr.write_char('\n');
+            self.indent -= 2;
+            self.wr.write_str(spaces(self.indent));
+            self.wr.write_char('}');
+        }
+    }
+    fn emit_map_elt_key(&self, idx: uint, f: &fn()) {
+        if idx == 0 {
+            self.wr.write_char('\n');
+        } else {
+            self.wr.write_str(",\n");
+        }
+        self.wr.write_str(spaces(self.indent));
+        f();
+    }
+
+    fn emit_map_elt_val(&self, _idx: uint, f: &fn()) {
+        self.wr.write_str(": ");
+        f();
+    }
 }
 
-impl<S:serialize::Encoder> serialize::Encodable<S> for Json {
-    fn encode(&self, s: &S) {
+impl<E: serialize::Encoder> serialize::Encodable<E> for Json {
+    fn encode(&self, e: &E) {
         match *self {
-            Number(v) => v.encode(s),
-            String(ref v) => v.encode(s),
-            Boolean(v) => v.encode(s),
-            List(ref v) => v.encode(s),
-            Object(ref v) => {
-                do s.emit_rec || {
-                    let mut idx = 0;
-                    for v.each |&(key, value)| {
-                        do s.emit_field(*key, idx) {
-                            value.encode(s);
-                        }
-                        idx += 1;
-                    }
-                }
-            },
-            Null => s.emit_nil(),
+            Number(v) => v.encode(e),
+            String(ref v) => v.encode(e),
+            Boolean(v) => v.encode(e),
+            List(ref v) => v.encode(e),
+            Object(ref v) => v.encode(e),
+            Null => e.emit_nil(),
         }
     }
 }
@@ -752,37 +736,20 @@ pub fn from_str(s: &str) -> Result<Json, Error> {
     }
 }
 
-pub struct Decoder<'self> {
-    priv json: Json,
-    priv mut stack: ~[&'self Json],
+pub struct Decoder {
+    priv mut stack: ~[Json],
 }
 
 pub fn Decoder(json: Json) -> Decoder {
-    Decoder { json: json, stack: ~[] }
-}
-
-priv impl<'self> Decoder<'self> {
-    fn peek(&self) -> &'self Json {
-        if vec::uniq_len(&const self.stack) == 0 {
-            self.stack.push(&self.json);
-        }
-        self.stack[vec::uniq_len(&const self.stack) - 1]
-    }
-
-    fn pop(&self) -> &'self Json {
-        if vec::uniq_len(&const self.stack) == 0 {
-            self.stack.push(&self.json);
-        }
-        self.stack.pop()
-    }
+    Decoder { stack: ~[json] }
 }
 
-impl<'self> serialize::Decoder for Decoder<'self> {
+impl serialize::Decoder for Decoder {
     fn read_nil(&self) -> () {
         debug!("read_nil");
-        match *self.pop() {
+        match self.stack.pop() {
             Null => (),
-            _ => fail!(~"not a null")
+            value => fail!(fmt!("not a null: %?", value))
         }
     }
 
@@ -800,9 +767,9 @@ impl<'self> serialize::Decoder for Decoder<'self> {
 
     fn read_bool(&self) -> bool {
         debug!("read_bool");
-        match *self.pop() {
+        match self.stack.pop() {
             Boolean(b) => b,
-            _ => fail!(~"not a boolean")
+            value => fail!(fmt!("not a boolean: %?", value))
         }
     }
 
@@ -810,45 +777,27 @@ impl<'self> serialize::Decoder for Decoder<'self> {
     fn read_f32(&self) -> f32 { self.read_float() as f32 }
     fn read_float(&self) -> float {
         debug!("read_float");
-        match *self.pop() {
+        match self.stack.pop() {
             Number(f) => f,
-            _ => fail!(~"not a number")
+            value => fail!(fmt!("not a number: %?", value))
         }
     }
 
     fn read_char(&self) -> char {
         let mut v = ~[];
-        for str::each_char(self.read_owned_str()) |c| { v.push(c) }
+        for str::each_char(self.read_str()) |c| { v.push(c) }
         if v.len() != 1 { fail!(~"string must have one character") }
         v[0]
     }
 
-    fn read_owned_str(&self) -> ~str {
-        debug!("read_owned_str");
-        match *self.pop() {
-            String(ref s) => copy *s,
-            ref json => fail!(fmt!("not a string: %?", *json))
+    fn read_str(&self) -> ~str {
+        debug!("read_str");
+        match self.stack.pop() {
+            String(s) => s,
+            json => fail!(fmt!("not a string: %?", json))
         }
     }
 
-    fn read_managed_str(&self) -> @str {
-        debug!("read_managed_str");
-        match *self.pop() {
-            String(ref s) => s.to_managed(),
-            ref json => fail!(fmt!("not a string: %?", *json))
-        }
-    }
-
-    fn read_owned<T>(&self, f: &fn() -> T) -> T {
-        debug!("read_owned()");
-        f()
-    }
-
-    fn read_managed<T>(&self, f: &fn() -> T) -> T {
-        debug!("read_managed()");
-        f()
-    }
-
     fn read_enum<T>(&self, name: &str, f: &fn() -> T) -> T {
         debug!("read_enum(%s)", name);
         f()
@@ -856,12 +805,20 @@ impl<'self> serialize::Decoder for Decoder<'self> {
 
     fn read_enum_variant<T>(&self, names: &[&str], f: &fn(uint) -> T) -> T {
         debug!("read_enum_variant(names=%?)", names);
-        let name = match *self.peek() {
-            String(ref s) => s,
-            List([String(ref s), .. _]) => s,
+        let name = match self.stack.pop() {
+            String(s) => s,
+            List(list) => {
+                do vec::consume_reverse(list) |_i, v| {
+                    self.stack.push(v);
+                }
+                match self.stack.pop() {
+                    String(s) => s,
+                    value => fail!(fmt!("invalid variant name: %?", value)),
+                }
+            }
             ref json => fail!(fmt!("invalid variant: %?", *json)),
         };
-        let idx = match vec::position(names, |n| str::eq_slice(*n, *name)) {
+        let idx = match vec::position(names, |n| str::eq_slice(*n, name)) {
             Some(idx) => idx,
             None => fail!(fmt!("Unknown variant name: %?", name)),
         };
@@ -870,108 +827,87 @@ impl<'self> serialize::Decoder for Decoder<'self> {
 
     fn read_enum_variant_arg<T>(&self, idx: uint, f: &fn() -> T) -> T {
         debug!("read_enum_variant_arg(idx=%u)", idx);
-        match *self.peek() {
-            List(ref list) => {
-                self.stack.push(&list[idx + 1]);
-                f()
-            }
-            ref json => fail!(fmt!("not a list: %?", json)),
-        }
-    }
-
-    fn read_owned_vec<T>(&self, f: &fn(uint) -> T) -> T {
-        debug!("read_owned_vec()");
-        let len = match *self.peek() {
-            List(ref list) => list.len(),
-            _ => fail!(~"not a list"),
-        };
-        let res = f(len);
-        self.pop();
-        res
-    }
-
-    fn read_managed_vec<T>(&self, f: &fn(uint) -> T) -> T {
-        debug!("read_owned_vec()");
-        let len = match *self.peek() {
-            List(ref list) => list.len(),
-            _ => fail!(~"not a list"),
-        };
-        let res = f(len);
-        self.pop();
-        res
+        f()
     }
 
-    fn read_vec_elt<T>(&self, idx: uint, f: &fn() -> T) -> T {
-        debug!("read_vec_elt(idx=%u)", idx);
-        match *self.peek() {
-            List(ref list) => {
-                self.stack.push(&list[idx]);
-                f()
+    fn read_seq<T>(&self, f: &fn(uint) -> T) -> T {
+        debug!("read_seq()");
+        let len = match self.stack.pop() {
+            List(list) => {
+                let len = list.len();
+                do vec::consume_reverse(list) |_i, v| {
+                    self.stack.push(v);
+                }
+                len
             }
             _ => fail!(~"not a list"),
-        }
+        };
+        f(len)
     }
 
-    fn read_rec<T>(&self, f: &fn() -> T) -> T {
-        debug!("read_rec()");
-        let value = f();
-        self.pop();
-        value
+    fn read_seq_elt<T>(&self, idx: uint, f: &fn() -> T) -> T {
+        debug!("read_seq_elt(idx=%u)", idx);
+        f()
     }
 
-    fn read_struct<T>(&self, _name: &str, _len: uint, f: &fn() -> T) -> T {
-        debug!("read_struct()");
+    fn read_struct<T>(&self, name: &str, len: uint, f: &fn() -> T) -> T {
+        debug!("read_struct(name=%s, len=%u)", name, len);
         let value = f();
-        self.pop();
+        self.stack.pop();
         value
     }
 
     fn read_field<T>(&self, name: &str, idx: uint, f: &fn() -> T) -> T {
-        debug!("read_rec_field(%s, idx=%u)", name, idx);
-        let top = self.peek();
-        match *top {
-            Object(ref obj) => {
-                match obj.find(&name.to_owned()) {
+        debug!("read_field(%s, idx=%u)", name, idx);
+        match self.stack.pop() {
+            Object(obj) => {
+                let mut obj = obj;
+                let value = match obj.pop(&name.to_owned()) {
                     None => fail!(fmt!("no such field: %s", name)),
                     Some(json) => {
                         self.stack.push(json);
                         f()
                     }
-                }
+                };
+                self.stack.push(Object(obj));
+                value
             }
-            Number(_) => fail!(~"num"),
-            String(_) => fail!(~"str"),
-            Boolean(_) => fail!(~"bool"),
-            List(_) => fail!(fmt!("list: %?", top)),
-            Null => fail!(~"null"),
-
-            //_ => fail!(fmt!("not an object: %?", *top))
+            value => fail!(fmt!("not an object: %?", value))
         }
     }
 
-    fn read_tup<T>(&self, len: uint, f: &fn() -> T) -> T {
-        debug!("read_tup(len=%u)", len);
-        let value = f();
-        self.pop();
-        value
+    fn read_option<T>(&self, f: &fn(bool) -> T) -> T {
+        match self.stack.pop() {
+            Null => f(false),
+            value => { self.stack.push(value); f(true) }
+        }
     }
 
-    fn read_tup_elt<T>(&self, idx: uint, f: &fn() -> T) -> T {
-        debug!("read_tup_elt(idx=%u)", idx);
-        match *self.peek() {
-            List(ref list) => {
-                self.stack.push(&list[idx]);
-                f()
+    fn read_map<T>(&self, f: &fn(uint) -> T) -> T {
+        debug!("read_map()");
+        let len = match self.stack.pop() {
+            Object(obj) => {
+                let mut obj = obj;
+                let len = obj.len();
+                do obj.consume |key, value| {
+                    self.stack.push(value);
+                    self.stack.push(String(key));
+                }
+                len
             }
-            _ => fail!(~"not a list")
-        }
+            json => fail!(fmt!("not an object: %?", json)),
+        };
+        f(len)
     }
 
-    fn read_option<T>(&self, f: &fn(bool) -> T) -> T {
-        match *self.peek() {
-            Null => { self.pop(); f(false) }
-            _ => f(true),
-        }
+    fn read_map_elt_key<T>(&self, idx: uint, f: &fn() -> T) -> T {
+        debug!("read_map_elt_key(idx=%u)", idx);
+        f()
+    }
+
+    fn read_map_elt_val<T>(&self, idx: uint, f: &fn() -> T) -> T {
+        debug!("read_map_elt_val(idx=%u)", idx);
+        f()
     }
 }
 
@@ -1229,6 +1165,30 @@ mod tests {
 
     use std::serialize::Decodable;
 
+    #[auto_encode]
+    #[auto_decode]
+    #[deriving(Eq)]
+    enum Animal {
+        Dog,
+        Frog(~str, int)
+    }
+
+    #[auto_encode]
+    #[auto_decode]
+    #[deriving(Eq)]
+    struct Inner {
+        a: (),
+        b: uint,
+        c: ~[~str],
+    }
+
+    #[auto_encode]
+    #[auto_decode]
+    #[deriving(Eq)]
+    struct Outer {
+        inner: ~[Inner],
+    }
+
     fn mk_object(items: &[(~str, Json)]) -> Json {
         let mut d = ~LinearMap::new();
 
@@ -1244,42 +1204,49 @@ mod tests {
     #[test]
     fn test_write_null() {
         assert_eq!(to_str(&Null), ~"null");
+        assert_eq!(to_pretty_str(&Null), ~"null");
     }
 
+
     #[test]
     fn test_write_number() {
         assert_eq!(to_str(&Number(3f)), ~"3");
+        assert_eq!(to_pretty_str(&Number(3f)), ~"3");
+
         assert_eq!(to_str(&Number(3.1f)), ~"3.1");
+        assert_eq!(to_pretty_str(&Number(3.1f)), ~"3.1");
+
         assert_eq!(to_str(&Number(-1.5f)), ~"-1.5");
+        assert_eq!(to_pretty_str(&Number(-1.5f)), ~"-1.5");
+
         assert_eq!(to_str(&Number(0.5f)), ~"0.5");
+        assert_eq!(to_pretty_str(&Number(0.5f)), ~"0.5");
     }
 
     #[test]
     fn test_write_str() {
         assert_eq!(to_str(&String(~"")), ~"\"\"");
+        assert_eq!(to_pretty_str(&String(~"")), ~"\"\"");
+
         assert_eq!(to_str(&String(~"foo")), ~"\"foo\"");
+        assert_eq!(to_pretty_str(&String(~"foo")), ~"\"foo\"");
     }
 
     #[test]
     fn test_write_bool() {
         assert_eq!(to_str(&Boolean(true)), ~"true");
+        assert_eq!(to_pretty_str(&Boolean(true)), ~"true");
+
         assert_eq!(to_str(&Boolean(false)), ~"false");
+        assert_eq!(to_pretty_str(&Boolean(false)), ~"false");
     }
 
     #[test]
     fn test_write_list() {
         assert_eq!(to_str(&List(~[])), ~"[]");
-        assert_eq!(to_str(&List(~[Boolean(true)])), ~"[true]");
-        assert_eq!(to_str(&List(~[
-            Boolean(false),
-            Null,
-            List(~[String(~"foo\nbar"), Number(3.5f)])
-        ])), ~"[false,null,[\"foo\\nbar\",3.5]]");
-    }
-
-    #[test]
-    fn test_write_list_pretty() {
         assert_eq!(to_pretty_str(&List(~[])), ~"[]");
+
+        assert_eq!(to_str(&List(~[Boolean(true)])), ~"[true]");
         assert_eq!(
             to_pretty_str(&List(~[Boolean(true)])),
             ~"\
@@ -1287,6 +1254,12 @@ mod tests {
                 true\n\
             ]"
         );
+
+        assert_eq!(to_str(&List(~[
+            Boolean(false),
+            Null,
+            List(~[String(~"foo\nbar"), Number(3.5f)])
+        ])), ~"[false,null,[\"foo\\nbar\",3.5]]");
         assert_eq!(
             to_pretty_str(&List(~[
                 Boolean(false),
@@ -1308,11 +1281,21 @@ mod tests {
     #[test]
     fn test_write_object() {
         assert_eq!(to_str(&mk_object(~[])), ~"{}");
+        assert_eq!(to_pretty_str(&mk_object(~[])), ~"{}");
+
         assert_eq!(
             to_str(&mk_object(~[(~"a", Boolean(true))])),
             ~"{\"a\":true}"
         );
         assert_eq!(
+            to_pretty_str(&mk_object(~[(~"a", Boolean(true))])),
+            ~"\
+            {\n  \
+                \"a\": true\n\
+            }"
+        );
+
+        assert_eq!(
             to_str(&mk_object(~[
                 (~"b", List(~[
                     mk_object(~[(~"c", String(~"\x0c\r"))]),
@@ -1326,29 +1309,6 @@ mod tests {
                 ]\
             }"
         );
-        let a = mk_object(~[
-            (~"a", Boolean(true)),
-            (~"b", List(~[
-                mk_object(~[(~"c", String(~"\x0c\r"))]),
-                mk_object(~[(~"d", String(~""))])
-            ]))
-        ]);
-        // We can't compare the strings directly because the object fields be
-        // printed in a different order.
-        let b = from_str(to_str(&a)).unwrap();
-        assert_eq!(a, b);
-    }
-
-    #[test]
-    fn test_write_object_pretty() {
-        assert_eq!(to_pretty_str(&mk_object(~[])), ~"{\n}");
-        assert_eq!(
-            to_pretty_str(&mk_object(~[(~"a", Boolean(true))])),
-            ~"\
-            {\n  \
-                \"a\": true\n\
-            }"
-        );
         assert_eq!(
             to_pretty_str(&mk_object(~[
                 (~"b", List(~[
@@ -1368,6 +1328,7 @@ mod tests {
                 ]\n\
             }"
         );
+
         let a = mk_object(~[
             (~"a", Boolean(true)),
             (~"b", List(~[
@@ -1375,63 +1336,44 @@ mod tests {
                 mk_object(~[(~"d", String(~""))])
             ]))
         ]);
+
         // We can't compare the strings directly because the object fields be
         // printed in a different order.
-        let b = from_str(to_str(&a)).unwrap();
-        assert_eq!(a, b);
-    }
-
-    #[auto_encode]
-    #[auto_decode]
-    #[deriving(Eq)]
-    enum Animal {
-        Dog,
-        Frog(~str, int)
+        assert_eq!(copy a, from_str(to_str(&a)).unwrap());
+        assert_eq!(copy a, from_str(to_pretty_str(&a)).unwrap());
     }
 
     #[test]
-    fn test_write_enum_no_args() {
+    fn test_write_enum() {
         let animal = Dog;
+        assert_eq!(
+            do io::with_str_writer |wr| {
+                let encoder = Encoder(wr);
+                animal.encode(&encoder);
+            },
+            ~"\"Dog\""
+        );
+        assert_eq!(
+            do io::with_str_writer |wr| {
+                let encoder = PrettyEncoder(wr);
+                animal.encode(&encoder);
+            },
+            ~"\"Dog\""
+        );
 
-        let s = do io::with_str_writer |wr| {
-            let encoder = Encoder(wr);
-            animal.encode(&encoder);
-        };
-        assert_eq!(s, ~"\"Dog\"");
-    }
-
-    #[test]
-    fn test_write_enum_no_args_pretty() {
-        let animal = Dog;
-
-        let s = do io::with_str_writer |wr| {
-            let encoder = PrettyEncoder(wr);
-            animal.encode(&encoder);
-        };
-        assert_eq!(s, ~"\"Dog\"");
-    }
-
-    #[test]
-    fn test_write_enum_multiple_args() {
-        let animal = Frog(~"Henry", 349);
-
-        let s = do io::with_str_writer |wr| {
-            let encoder = Encoder(wr);
-            animal.encode(&encoder);
-        };
-        assert_eq!(s, ~"[\"Frog\",\"Henry\",349]");
-    }
-
-    #[test]
-    fn test_write_enum_multiple_args_pretty() {
         let animal = Frog(~"Henry", 349);
-
-        let s = do io::with_str_writer |wr| {
-            let encoder = PrettyEncoder(wr);
-            animal.encode(&encoder);
-        };
         assert_eq!(
-            s,
+            do io::with_str_writer |wr| {
+                let encoder = Encoder(wr);
+                animal.encode(&encoder);
+            },
+            ~"[\"Frog\",\"Henry\",349]"
+        );
+        assert_eq!(
+            do io::with_str_writer |wr| {
+                let encoder = PrettyEncoder(wr);
+                animal.encode(&encoder);
+            },
             ~"\
             [\n  \
                 \"Frog\",\n  \
@@ -1449,10 +1391,7 @@ mod tests {
             value.encode(&encoder);
         };
         assert_eq!(s, ~"\"jodhpurs\"");
-    }
 
-    #[test]
-    fn test_write_some_pretty() {
         let value = Some(~"jodhpurs");
         let s = do io::with_str_writer |wr| {
             let encoder = PrettyEncoder(wr);
@@ -1469,11 +1408,7 @@ mod tests {
             value.encode(&encoder);
         };
         assert_eq!(s, ~"null");
-    }
 
-    #[test]
-    fn test_write_none_pretty() {
-        let value: Option<~str> = None;
         let s = do io::with_str_writer |wr| {
             let encoder = Encoder(wr);
             value.encode(&encoder);
@@ -1523,6 +1458,18 @@ mod tests {
     }
 
     #[test]
+    fn test_decode_identifiers() {
+        let v: () = Decodable::decode(&Decoder(from_str(~"null").unwrap()));
+        assert_eq!(v, ());
+
+        let v: bool = Decodable::decode(&Decoder(from_str(~"true").unwrap()));
+        assert_eq!(v, true);
+
+        let v: bool = Decodable::decode(&Decoder(from_str(~"false").unwrap()));
+        assert_eq!(v, false);
+    }
+
+    #[test]
     fn test_read_number() {
         assert_eq!(from_str(~"+"),
             Err(Error {line: 1u, col: 1u, msg: @~"invalid syntax"}));
@@ -1551,6 +1498,30 @@ mod tests {
     }
 
     #[test]
+    fn test_decode_numbers() {
+        let v: float = Decodable::decode(&Decoder(from_str(~"3").unwrap()));
+        assert_eq!(v, 3f);
+
+        let v: float = Decodable::decode(&Decoder(from_str(~"3.1").unwrap()));
+        assert_eq!(v, 3.1f);
+
+        let v: float = Decodable::decode(&Decoder(from_str(~"-1.2").unwrap()));
+        assert_eq!(v, -1.2f);
+
+        let v: float = Decodable::decode(&Decoder(from_str(~"0.4").unwrap()));
+        assert_eq!(v, 0.4f);
+
+        let v: float = Decodable::decode(&Decoder(from_str(~"0.4e5").unwrap()));
+        assert_eq!(v, 0.4e5f);
+
+        let v: float = Decodable::decode(&Decoder(from_str(~"0.4e15").unwrap()));
+        assert_eq!(v, 0.4e15f);
+
+        let v: float = Decodable::decode(&Decoder(from_str(~"0.4e-01").unwrap()));
+        assert_eq!(v, 0.4e-01f);
+    }
+
+    #[test]
     fn test_read_str() {
         assert_eq!(from_str(~"\""),
             Err(Error {line: 1u, col: 2u, msg: @~"EOF while parsing string"
@@ -1567,12 +1538,38 @@ mod tests {
         assert_eq!(from_str(~"\"\\r\""), Ok(String(~"\r")));
         assert_eq!(from_str(~"\"\\t\""), Ok(String(~"\t")));
         assert_eq!(from_str(~" \"foo\" "), Ok(String(~"foo")));
+        assert_eq!(from_str(~"\"\\u12ab\""), Ok(String(~"\u12ab")));
+        assert_eq!(from_str(~"\"\\uAB12\""), Ok(String(~"\uAB12")));
     }
 
     #[test]
-    fn test_unicode_hex_escapes_in_str() {
-        assert_eq!(from_str(~"\"\\u12ab\""), Ok(String(~"\u12ab")));
-        assert_eq!(from_str(~"\"\\uAB12\""), Ok(String(~"\uAB12")));
+    fn test_decode_str() {
+        let v: ~str = Decodable::decode(&Decoder(from_str(~"\"\"").unwrap()));
+        assert_eq!(v, ~"");
+
+        let v: ~str = Decodable::decode(&Decoder(from_str(~"\"foo\"").unwrap()));
+        assert_eq!(v, ~"foo");
+
+        let v: ~str = Decodable::decode(&Decoder(from_str(~"\"\\\"\"").unwrap()));
+        assert_eq!(v, ~"\"");
+
+        let v: ~str = Decodable::decode(&Decoder(from_str(~"\"\\b\"").unwrap()));
+        assert_eq!(v, ~"\x08");
+
+        let v: ~str = Decodable::decode(&Decoder(from_str(~"\"\\n\"").unwrap()));
+        assert_eq!(v, ~"\n");
+
+        let v: ~str = Decodable::decode(&Decoder(from_str(~"\"\\r\"").unwrap()));
+        assert_eq!(v, ~"\r");
+
+        let v: ~str = Decodable::decode(&Decoder(from_str(~"\"\\t\"").unwrap()));
+        assert_eq!(v, ~"\t");
+
+        let v: ~str = Decodable::decode(&Decoder(from_str(~"\"\\u12ab\"").unwrap()));
+        assert_eq!(v, ~"\u12ab");
+
+        let v: ~str = Decodable::decode(&Decoder(from_str(~"\"\\uAB12\"").unwrap()));
+        assert_eq!(v, ~"\uAB12");
     }
 
     #[test]
@@ -1602,6 +1599,28 @@ mod tests {
     }
 
     #[test]
+    fn test_decode_list() {
+        let v: ~[()] = Decodable::decode(&Decoder(from_str(~"[]").unwrap()));
+        assert_eq!(v, ~[]);
+
+        let v: ~[()] = Decodable::decode(&Decoder(from_str(~"[null]").unwrap()));
+        assert_eq!(v, ~[()]);
+
+
+        let v: ~[bool] = Decodable::decode(&Decoder(from_str(~"[true]").unwrap()));
+        assert_eq!(v, ~[true]);
+
+        let v: ~[bool] = Decodable::decode(&Decoder(from_str(~"[true]").unwrap()));
+        assert_eq!(v, ~[true]);
+
+        let v: ~[int] = Decodable::decode(&Decoder(from_str(~"[3, 1]").unwrap()));
+        assert_eq!(v, ~[3, 1]);
+
+        let v: ~[~[uint]] = Decodable::decode(&Decoder(from_str(~"[[3], [1, 2]]").unwrap()));
+        assert_eq!(v, ~[~[3], ~[1, 2]]);
+    }
+
+    #[test]
     fn test_read_object() {
         assert_eq!(from_str(~"{"),
             Err(Error {
@@ -1693,34 +1712,56 @@ mod tests {
     }
 
     #[test]
-    fn test_read_none() {
+    fn test_decode_struct() {
+        let s = ~"{
+            \"inner\": [
+                { \"a\": null, \"b\": 2, \"c\": [\"abc\", \"xyz\"] }
+            ]
+        }";
+        let v: Outer = Decodable::decode(&Decoder(from_str(s).unwrap()));
+        assert_eq!(
+            v,
+            Outer {
+                inner: ~[
+                    Inner { a: (), b: 2, c: ~[~"abc", ~"xyz"] }
+                ]
+            }
+        );
+    }
+
+    #[test]
+    fn test_decode_option() {
         let decoder = Decoder(from_str(~"null").unwrap());
         let value: Option<~str> = Decodable::decode(&decoder);
         assert_eq!(value, None);
-    }
 
-    #[test]
-    fn test_read_some() {
         let decoder = Decoder(from_str(~"\"jodhpurs\"").unwrap());
         let value: Option<~str> = Decodable::decode(&decoder);
         assert_eq!(value, Some(~"jodhpurs"));
     }
 
     #[test]
-    fn test_read_enum_no_args() {
+    fn test_decode_enum() {
         let decoder = Decoder(from_str(~"\"Dog\"").unwrap());
         let value: Animal = Decodable::decode(&decoder);
         assert_eq!(value, Dog);
-    }
 
-    #[test]
-    fn test_read_enum_multiple_args() {
         let decoder = Decoder(from_str(~"[\"Frog\",\"Henry\",349]").unwrap());
         let value: Animal = Decodable::decode(&decoder);
         assert_eq!(value, Frog(~"Henry", 349));
     }
 
     #[test]
+    fn test_decode_map() {
+        let s = ~"{\"a\": \"Dog\", \"b\": [\"Frog\", \"Henry\", 349]}";
+        let decoder = Decoder(from_str(s).unwrap());
+        let mut map: LinearMap<~str, Animal> = Decodable::decode(&decoder);
+
+        assert_eq!(map.pop(&~"a"), Some(Dog));
+        assert_eq!(map.pop(&~"b"), Some(Frog(~"Henry", 349)));
+    }
+
+    #[test]
     fn test_multiline_errors() {
         assert_eq!(from_str(~"{\n  \"foo\":\n \"bar\""),
             Err(Error {
diff --git a/src/libstd/prettyprint.rs b/src/libstd/prettyprint.rs
deleted file mode 100644
index ed4f3e957c0..00000000000
--- a/src/libstd/prettyprint.rs
+++ /dev/null
@@ -1,199 +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.
-
-use serialize;
-
-use core::io::WriterUtil;
-use core::io;
-
-pub struct Serializer {
-    wr: @io::Writer,
-}
-
-pub fn Serializer(wr: @io::Writer) -> Serializer {
-    Serializer { wr: wr }
-}
-
-impl serialize::Encoder for Serializer {
-    fn emit_nil(&self) {
-        self.wr.write_str(~"()")
-    }
-
-    fn emit_uint(&self, v: uint) {
-        self.wr.write_str(fmt!("%?u", v));
-    }
-
-    fn emit_u64(&self, v: u64) {
-        self.wr.write_str(fmt!("%?_u64", v));
-    }
-
-    fn emit_u32(&self, v: u32) {
-        self.wr.write_str(fmt!("%?_u32", v));
-    }
-
-    fn emit_u16(&self, v: u16) {
-        self.wr.write_str(fmt!("%?_u16", v));
-    }
-
-    fn emit_u8(&self, v: u8) {
-        self.wr.write_str(fmt!("%?_u8", v));
-    }
-
-    fn emit_int(&self, v: int) {
-        self.wr.write_str(fmt!("%?", v));
-    }
-
-    fn emit_i64(&self, v: i64) {
-        self.wr.write_str(fmt!("%?_i64", v));
-    }
-
-    fn emit_i32(&self, v: i32) {
-        self.wr.write_str(fmt!("%?_i32", v));
-    }
-
-    fn emit_i16(&self, v: i16) {
-        self.wr.write_str(fmt!("%?_i16", v));
-    }
-
-    fn emit_i8(&self, v: i8) {
-        self.wr.write_str(fmt!("%?_i8", v));
-    }
-
-    fn emit_bool(&self, v: bool) {
-        self.wr.write_str(fmt!("%b", v));
-    }
-
-    fn emit_float(&self, v: float) {
-        self.wr.write_str(fmt!("%?_f", v));
-    }
-
-    fn emit_f64(&self, v: f64) {
-        self.wr.write_str(fmt!("%?_f64", v));
-    }
-
-    fn emit_f32(&self, v: f32) {
-        self.wr.write_str(fmt!("%?_f32", v));
-    }
-
-    fn emit_char(&self, v: char) {
-        self.wr.write_str(fmt!("%?", v));
-    }
-
-    fn emit_borrowed_str(&self, v: &str) {
-        self.wr.write_str(fmt!("&%?", v));
-    }
-
-    fn emit_owned_str(&self, v: &str) {
-        self.wr.write_str(fmt!("~%?", v));
-    }
-
-    fn emit_managed_str(&self, v: &str) {
-        self.wr.write_str(fmt!("@%?", v));
-    }
-
-    fn emit_borrowed(&self, f: &fn()) {
-        self.wr.write_str(~"&");
-        f();
-    }
-
-    fn emit_owned(&self, f: &fn()) {
-        self.wr.write_str(~"~");
-        f();
-    }
-
-    fn emit_managed(&self, f: &fn()) {
-        self.wr.write_str(~"@");
-        f();
-    }
-
-    fn emit_enum(&self, _name: &str, f: &fn()) {
-        f();
-    }
-
-    fn emit_enum_variant(&self, v_name: &str, _v_id: uint, sz: uint,
-                         f: &fn()) {
-        self.wr.write_str(v_name);
-        if sz > 0u { self.wr.write_str(~"("); }
-        f();
-        if sz > 0u { self.wr.write_str(~")"); }
-    }
-
-    fn emit_enum_variant_arg(&self, idx: uint, f: &fn()) {
-        if idx > 0u { self.wr.write_str(~", "); }
-        f();
-    }
-
-    fn emit_borrowed_vec(&self, _len: uint, f: &fn()) {
-        self.wr.write_str(~"&[");
-        f();
-        self.wr.write_str(~"]");
-    }
-
-    fn emit_owned_vec(&self, _len: uint, f: &fn()) {
-        self.wr.write_str(~"~[");
-        f();
-        self.wr.write_str(~"]");
-    }
-
-    fn emit_managed_vec(&self, _len: uint, f: &fn()) {
-        self.wr.write_str(~"@[");
-        f();
-        self.wr.write_str(~"]");
-    }
-
-    fn emit_vec_elt(&self, idx: uint, f: &fn()) {
-        if idx > 0u { self.wr.write_str(~", "); }
-        f();
-    }
-
-    fn emit_rec(&self, f: &fn()) {
-        self.wr.write_str(~"{");
-        f();
-        self.wr.write_str(~"}");
-    }
-
-    fn emit_struct(&self, name: &str, _len: uint, f: &fn()) {
-        self.wr.write_str(fmt!("%s {", name));
-        f();
-        self.wr.write_str(~"}");
-    }
-
-    fn emit_field(&self, name: &str, idx: uint, f: &fn()) {
-        if idx > 0u { self.wr.write_str(~", "); }
-        self.wr.write_str(name);
-        self.wr.write_str(~": ");
-        f();
-    }
-
-    fn emit_tup(&self, _len: uint, f: &fn()) {
-        self.wr.write_str(~"(");
-        f();
-        self.wr.write_str(~")");
-    }
-
-    fn emit_tup_elt(&self, idx: uint, f: &fn()) {
-        if idx > 0u { self.wr.write_str(~", "); }
-        f();
-    }
-
-    fn emit_option(&self, f: &fn()) {
-        f();
-    }
-
-    fn emit_option_none(&self) {
-        self.wr.write_str("None");
-    }
-
-    fn emit_option_some(&self, f: &fn()) {
-        self.wr.write_str("Some(");
-        f();
-        self.wr.write_char(')');
-    }
-}
diff --git a/src/libstd/serialize.rs b/src/libstd/serialize.rs
index 8e7ab318e17..72c81d6d6b4 100644
--- a/src/libstd/serialize.rs
+++ b/src/libstd/serialize.rs
@@ -16,9 +16,12 @@ Core encoding and decoding interfaces.
 
 #[forbid(non_camel_case_types)];
 
-use core::at_vec;
 use core::prelude::*;
-use core::vec;
+use core::dlist::DList;
+use core::hashmap::linear::{LinearMap, LinearSet};
+use core::trie::{TrieMap, TrieSet};
+use deque::Deque;
+use treemap::{TreeMap, TreeSet};
 
 pub trait Encoder {
     // Primitive types:
@@ -38,35 +41,28 @@ pub trait Encoder {
     fn emit_f64(&self, v: f64);
     fn emit_f32(&self, v: f32);
     fn emit_char(&self, v: char);
-    fn emit_borrowed_str(&self, v: &str);
-    fn emit_owned_str(&self, v: &str);
-    fn emit_managed_str(&self, v: &str);
+    fn emit_str(&self, v: &str);
 
     // Compound types:
-    fn emit_borrowed(&self, f: &fn());
-    fn emit_owned(&self, f: &fn());
-    fn emit_managed(&self, f: &fn());
 
     fn emit_enum(&self, name: &str, f: &fn());
     fn emit_enum_variant(&self, v_name: &str, v_id: uint, sz: uint, f: &fn());
     fn emit_enum_variant_arg(&self, idx: uint, f: &fn());
 
-    fn emit_borrowed_vec(&self, len: uint, f: &fn());
-    fn emit_owned_vec(&self, len: uint, f: &fn());
-    fn emit_managed_vec(&self, len: uint, f: &fn());
-    fn emit_vec_elt(&self, idx: uint, f: &fn());
+    fn emit_seq(&self, len: uint, f: &fn());
+    fn emit_seq_elt(&self, idx: uint, f: &fn());
 
-    fn emit_rec(&self, f: &fn());
     fn emit_struct(&self, name: &str, _len: uint, f: &fn());
     fn emit_field(&self, f_name: &str, f_idx: uint, f: &fn());
 
-    fn emit_tup(&self, len: uint, f: &fn());
-    fn emit_tup_elt(&self, idx: uint, f: &fn());
-
     // Specialized types:
     fn emit_option(&self, f: &fn());
     fn emit_option_none(&self);
     fn emit_option_some(&self, f: &fn());
+
+    fn emit_map(&self, len: uint, f: &fn());
+    fn emit_map_elt_key(&self, idx: uint, f: &fn());
+    fn emit_map_elt_val(&self, idx: uint, f: &fn());
 }
 
 pub trait Decoder {
@@ -87,32 +83,25 @@ pub trait Decoder {
     fn read_f32(&self) -> f32;
     fn read_float(&self) -> float;
     fn read_char(&self) -> char;
-    fn read_owned_str(&self) -> ~str;
-    fn read_managed_str(&self) -> @str;
+    fn read_str(&self) -> ~str;
 
     // Compound types:
     fn read_enum<T>(&self, name: &str, f: &fn() -> T) -> T;
-
     fn read_enum_variant<T>(&self, names: &[&str], f: &fn(uint) -> T) -> T;
-
     fn read_enum_variant_arg<T>(&self, idx: uint, f: &fn() -> T) -> T;
 
-    fn read_owned<T>(&self, f: &fn() -> T) -> T;
-    fn read_managed<T>(&self, f: &fn() -> T) -> T;
+    fn read_seq<T>(&self, f: &fn(uint) -> T) -> T;
+    fn read_seq_elt<T>(&self, idx: uint, f: &fn() -> T) -> T;
 
-    fn read_owned_vec<T>(&self, f: &fn(uint) -> T) -> T;
-    fn read_managed_vec<T>(&self, f: &fn(uint) -> T) -> T;
-    fn read_vec_elt<T>(&self, idx: uint, f: &fn() -> T) -> T;
-
-    fn read_rec<T>(&self, f: &fn() -> T) -> T;
     fn read_struct<T>(&self, name: &str, _len: uint, f: &fn() -> T) -> T;
     fn read_field<T>(&self, name: &str, idx: uint, f: &fn() -> T) -> T;
 
-    fn read_tup<T>(&self, sz: uint, f: &fn() -> T) -> T;
-    fn read_tup_elt<T>(&self, idx: uint, f: &fn() -> T) -> T;
-
     // Specialized types:
     fn read_option<T>(&self, f: &fn(bool) -> T) -> T;
+
+    fn read_map<T>(&self, f: &fn(uint) -> T) -> T;
+    fn read_map_elt_key<T>(&self, idx: uint, f: &fn() -> T) -> T;
+    fn read_map_elt_val<T>(&self, idx: uint, f: &fn() -> T) -> T;
 }
 
 pub trait Encodable<S:Encoder> {
@@ -224,27 +213,25 @@ impl<D:Decoder> Decodable<D> for i64 {
 }
 
 impl<'self, S:Encoder> Encodable<S> for &'self str {
-    fn encode(&self, s: &S) { s.emit_borrowed_str(*self) }
+    fn encode(&self, s: &S) { s.emit_str(*self) }
 }
 
 impl<S:Encoder> Encodable<S> for ~str {
-    fn encode(&self, s: &S) { s.emit_owned_str(*self) }
+    fn encode(&self, s: &S) { s.emit_str(*self) }
 }
 
 impl<D:Decoder> Decodable<D> for ~str {
     fn decode(d: &D) -> ~str {
-        d.read_owned_str()
+        d.read_str()
     }
 }
 
 impl<S:Encoder> Encodable<S> for @str {
-    fn encode(&self, s: &S) { s.emit_managed_str(*self) }
+    fn encode(&self, s: &S) { s.emit_str(*self) }
 }
 
 impl<D:Decoder> Decodable<D> for @str {
-    fn decode(d: &D) -> @str {
-        d.read_managed_str()
-    }
+    fn decode(d: &D) -> @str { d.read_str().to_managed() }
 }
 
 impl<S:Encoder> Encodable<S> for float {
@@ -298,39 +285,39 @@ impl<D:Decoder> Decodable<D> for () {
 
 impl<'self, S:Encoder,T:Encodable<S>> Encodable<S> for &'self T {
     fn encode(&self, s: &S) {
-        s.emit_borrowed(|| (**self).encode(s))
+        (**self).encode(s)
     }
 }
 
 impl<S:Encoder,T:Encodable<S>> Encodable<S> for ~T {
     fn encode(&self, s: &S) {
-        s.emit_owned(|| (**self).encode(s))
+        (**self).encode(s)
     }
 }
 
 impl<D:Decoder,T:Decodable<D>> Decodable<D> for ~T {
     fn decode(d: &D) -> ~T {
-        d.read_owned(|| ~Decodable::decode(d))
+        ~Decodable::decode(d)
     }
 }
 
 impl<S:Encoder,T:Encodable<S>> Encodable<S> for @T {
     fn encode(&self, s: &S) {
-        s.emit_managed(|| (**self).encode(s))
+        (**self).encode(s)
     }
 }
 
 impl<D:Decoder,T:Decodable<D>> Decodable<D> for @T {
     fn decode(d: &D) -> @T {
-        d.read_managed(|| @Decodable::decode(d))
+        @Decodable::decode(d)
     }
 }
 
 impl<'self, S:Encoder,T:Encodable<S>> Encodable<S> for &'self [T] {
     fn encode(&self, s: &S) {
-        do s.emit_borrowed_vec(self.len()) {
+        do s.emit_seq(self.len()) {
             for self.eachi |i, e| {
-                s.emit_vec_elt(i, || e.encode(s))
+                s.emit_seq_elt(i, || e.encode(s))
             }
         }
     }
@@ -338,9 +325,9 @@ impl<'self, S:Encoder,T:Encodable<S>> Encodable<S> for &'self [T] {
 
 impl<S:Encoder,T:Encodable<S>> Encodable<S> for ~[T] {
     fn encode(&self, s: &S) {
-        do s.emit_owned_vec(self.len()) {
+        do s.emit_seq(self.len()) {
             for self.eachi |i, e| {
-                s.emit_vec_elt(i, || e.encode(s))
+                s.emit_seq_elt(i, || e.encode(s))
             }
         }
     }
@@ -348,9 +335,9 @@ impl<S:Encoder,T:Encodable<S>> Encodable<S> for ~[T] {
 
 impl<D:Decoder,T:Decodable<D>> Decodable<D> for ~[T] {
     fn decode(d: &D) -> ~[T] {
-        do d.read_owned_vec |len| {
+        do d.read_seq |len| {
             do vec::from_fn(len) |i| {
-                d.read_vec_elt(i, || Decodable::decode(d))
+                d.read_seq_elt(i, || Decodable::decode(d))
             }
         }
     }
@@ -358,9 +345,9 @@ impl<D:Decoder,T:Decodable<D>> Decodable<D> for ~[T] {
 
 impl<S:Encoder,T:Encodable<S>> Encodable<S> for @[T] {
     fn encode(&self, s: &S) {
-        do s.emit_managed_vec(self.len()) {
+        do s.emit_seq(self.len()) {
             for self.eachi |i, e| {
-                s.emit_vec_elt(i, || e.encode(s))
+                s.emit_seq_elt(i, || e.encode(s))
             }
         }
     }
@@ -368,9 +355,9 @@ impl<S:Encoder,T:Encodable<S>> Encodable<S> for @[T] {
 
 impl<D:Decoder,T:Decodable<D>> Decodable<D> for @[T] {
     fn decode(d: &D) -> @[T] {
-        do d.read_managed_vec |len| {
+        do d.read_seq |len| {
             do at_vec::from_fn(len) |i| {
-                d.read_vec_elt(i, || Decodable::decode(d))
+                d.read_seq_elt(i, || Decodable::decode(d))
             }
         }
     }
@@ -403,9 +390,9 @@ impl<S:Encoder,T0:Encodable<S>,T1:Encodable<S>> Encodable<S> for (T0, T1) {
     fn encode(&self, s: &S) {
         match *self {
             (ref t0, ref t1) => {
-                do s.emit_tup(2) {
-                    s.emit_tup_elt(0, || t0.encode(s));
-                    s.emit_tup_elt(1, || t1.encode(s));
+                do s.emit_seq(2) {
+                    s.emit_seq_elt(0, || t0.encode(s));
+                    s.emit_seq_elt(1, || t1.encode(s));
                 }
             }
         }
@@ -414,10 +401,11 @@ impl<S:Encoder,T0:Encodable<S>,T1:Encodable<S>> Encodable<S> for (T0, T1) {
 
 impl<D:Decoder,T0:Decodable<D>,T1:Decodable<D>> Decodable<D> for (T0, T1) {
     fn decode(d: &D) -> (T0, T1) {
-        do d.read_tup(2) {
+        do d.read_seq |len| {
+            assert!(len == 2);
             (
-                d.read_tup_elt(0, || Decodable::decode(d)),
-                d.read_tup_elt(1, || Decodable::decode(d))
+                d.read_seq_elt(0, || Decodable::decode(d)),
+                d.read_seq_elt(1, || Decodable::decode(d))
             )
         }
     }
@@ -432,10 +420,10 @@ impl<
     fn encode(&self, s: &S) {
         match *self {
             (ref t0, ref t1, ref t2) => {
-                do s.emit_tup(3) {
-                    s.emit_tup_elt(0, || t0.encode(s));
-                    s.emit_tup_elt(1, || t1.encode(s));
-                    s.emit_tup_elt(2, || t2.encode(s));
+                do s.emit_seq(3) {
+                    s.emit_seq_elt(0, || t0.encode(s));
+                    s.emit_seq_elt(1, || t1.encode(s));
+                    s.emit_seq_elt(2, || t2.encode(s));
                 }
             }
         }
@@ -449,11 +437,12 @@ impl<
     T2: Decodable<D>
 > Decodable<D> for (T0, T1, T2) {
     fn decode(d: &D) -> (T0, T1, T2) {
-        do d.read_tup(3) {
+        do d.read_seq |len| {
+            assert!(len == 3);
             (
-                d.read_tup_elt(0, || Decodable::decode(d)),
-                d.read_tup_elt(1, || Decodable::decode(d)),
-                d.read_tup_elt(2, || Decodable::decode(d))
+                d.read_seq_elt(0, || Decodable::decode(d)),
+                d.read_seq_elt(1, || Decodable::decode(d)),
+                d.read_seq_elt(2, || Decodable::decode(d))
             )
         }
     }
@@ -469,11 +458,11 @@ impl<
     fn encode(&self, s: &S) {
         match *self {
             (ref t0, ref t1, ref t2, ref t3) => {
-                do s.emit_tup(4) {
-                    s.emit_tup_elt(0, || t0.encode(s));
-                    s.emit_tup_elt(1, || t1.encode(s));
-                    s.emit_tup_elt(2, || t2.encode(s));
-                    s.emit_tup_elt(3, || t3.encode(s));
+                do s.emit_seq(4) {
+                    s.emit_seq_elt(0, || t0.encode(s));
+                    s.emit_seq_elt(1, || t1.encode(s));
+                    s.emit_seq_elt(2, || t2.encode(s));
+                    s.emit_seq_elt(3, || t3.encode(s));
                 }
             }
         }
@@ -488,12 +477,13 @@ impl<
     T3: Decodable<D>
 > Decodable<D> for (T0, T1, T2, T3) {
     fn decode(d: &D) -> (T0, T1, T2, T3) {
-        do d.read_tup(4) {
+        do d.read_seq |len| {
+            assert!(len == 4);
             (
-                d.read_tup_elt(0, || Decodable::decode(d)),
-                d.read_tup_elt(1, || Decodable::decode(d)),
-                d.read_tup_elt(2, || Decodable::decode(d)),
-                d.read_tup_elt(3, || Decodable::decode(d))
+                d.read_seq_elt(0, || Decodable::decode(d)),
+                d.read_seq_elt(1, || Decodable::decode(d)),
+                d.read_seq_elt(2, || Decodable::decode(d)),
+                d.read_seq_elt(3, || Decodable::decode(d))
             )
         }
     }
@@ -510,12 +500,12 @@ impl<
     fn encode(&self, s: &S) {
         match *self {
             (ref t0, ref t1, ref t2, ref t3, ref t4) => {
-                do s.emit_tup(5) {
-                    s.emit_tup_elt(0, || t0.encode(s));
-                    s.emit_tup_elt(1, || t1.encode(s));
-                    s.emit_tup_elt(2, || t2.encode(s));
-                    s.emit_tup_elt(3, || t3.encode(s));
-                    s.emit_tup_elt(4, || t4.encode(s));
+                do s.emit_seq(5) {
+                    s.emit_seq_elt(0, || t0.encode(s));
+                    s.emit_seq_elt(1, || t1.encode(s));
+                    s.emit_seq_elt(2, || t2.encode(s));
+                    s.emit_seq_elt(3, || t3.encode(s));
+                    s.emit_seq_elt(4, || t4.encode(s));
                 }
             }
         }
@@ -532,18 +522,258 @@ impl<
 > Decodable<D> for (T0, T1, T2, T3, T4) {
     fn decode(d: &D)
       -> (T0, T1, T2, T3, T4) {
-        do d.read_tup(5) {
+        do d.read_seq |len| {
+            assert!(len == 5);
             (
-                d.read_tup_elt(0, || Decodable::decode(d)),
-                d.read_tup_elt(1, || Decodable::decode(d)),
-                d.read_tup_elt(2, || Decodable::decode(d)),
-                d.read_tup_elt(3, || Decodable::decode(d)),
-                d.read_tup_elt(4, || Decodable::decode(d))
+                d.read_seq_elt(0, || Decodable::decode(d)),
+                d.read_seq_elt(1, || Decodable::decode(d)),
+                d.read_seq_elt(2, || Decodable::decode(d)),
+                d.read_seq_elt(3, || Decodable::decode(d)),
+                d.read_seq_elt(4, || Decodable::decode(d))
             )
         }
     }
 }
 
+impl<
+    S: Encoder,
+    T: Encodable<S> + Copy
+> Encodable<S> for @mut DList<T> {
+    fn encode(&self, s: &S) {
+        do s.emit_seq(self.size) {
+            let mut i = 0;
+            for self.each |e| {
+                s.emit_seq_elt(i, || e.encode(s));
+                i += 1;
+            }
+        }
+    }
+}
+
+impl<D:Decoder,T:Decodable<D>> Decodable<D> for @mut DList<T> {
+    fn decode(d: &D) -> @mut DList<T> {
+        let list = DList();
+        do d.read_seq |len| {
+            for uint::range(0, len) |i| {
+                list.push(d.read_seq_elt(i, || Decodable::decode(d)));
+            }
+        }
+        list
+    }
+}
+
+impl<
+    S: Encoder,
+    T: Encodable<S>
+> Encodable<S> for Deque<T> {
+    fn encode(&self, s: &S) {
+        do s.emit_seq(self.len()) {
+            for self.eachi |i, e| {
+                s.emit_seq_elt(i, || e.encode(s));
+            }
+        }
+    }
+}
+
+impl<D:Decoder,T:Decodable<D>> Decodable<D> for Deque<T> {
+    fn decode(d: &D) -> Deque<T> {
+        let mut deque = Deque::new();
+        do d.read_seq |len| {
+            for uint::range(0, len) |i| {
+                deque.add_back(d.read_seq_elt(i, || Decodable::decode(d)));
+            }
+        }
+        deque
+    }
+}
+
+impl<
+    E: Encoder,
+    K: Encodable<E> + Hash + IterBytes + Eq,
+    V: Encodable<E>
+> Encodable<E> for LinearMap<K, V> {
+    fn encode(&self, e: &E) {
+        do e.emit_map(self.len()) {
+            let mut i = 0;
+            for self.each |&(key, val)| {
+                e.emit_map_elt_key(i, || key.encode(e));
+                e.emit_map_elt_val(i, || val.encode(e));
+                i += 1;
+            }
+        }
+    }
+}
+
+impl<
+    D: Decoder,
+    K: Decodable<D> + Hash + IterBytes + Eq,
+    V: Decodable<D>
+> Decodable<D> for LinearMap<K, V> {
+    fn decode(d: &D) -> LinearMap<K, V> {
+        do d.read_map |len| {
+            let mut map = LinearMap::with_capacity(len);
+            for uint::range(0, len) |i| {
+                let key = d.read_map_elt_key(i, || Decodable::decode(d));
+                let val = d.read_map_elt_val(i, || Decodable::decode(d));
+                map.insert(key, val);
+            }
+            map
+        }
+    }
+}
+
+impl<
+    S: Encoder,
+    T: Encodable<S> + Hash + IterBytes + Eq
+> Encodable<S> for LinearSet<T> {
+    fn encode(&self, s: &S) {
+        do s.emit_seq(self.len()) {
+            let mut i = 0;
+            for self.each |e| {
+                s.emit_seq_elt(i, || e.encode(s));
+                i += 1;
+            }
+        }
+    }
+}
+
+impl<
+    D: Decoder,
+    T: Decodable<D> + Hash + IterBytes + Eq
+> Decodable<D> for LinearSet<T> {
+    fn decode(d: &D) -> LinearSet<T> {
+        do d.read_seq |len| {
+            let mut set = LinearSet::with_capacity(len);
+            for uint::range(0, len) |i| {
+                set.insert(d.read_seq_elt(i, || Decodable::decode(d)));
+            }
+            set
+        }
+    }
+}
+
+impl<
+    E: Encoder,
+    V: Encodable<E>
+> Encodable<E> for TrieMap<V> {
+    fn encode(&self, e: &E) {
+        do e.emit_map(self.len()) {
+            let mut i = 0;
+            for self.each |&(key, val)| {
+                e.emit_map_elt_key(i, || key.encode(e));
+                e.emit_map_elt_val(i, || val.encode(e));
+                i += 1;
+            }
+        }
+    }
+}
+
+impl<
+    D: Decoder,
+    V: Decodable<D>
+> Decodable<D> for TrieMap<V> {
+    fn decode(d: &D) -> TrieMap<V> {
+        do d.read_map |len| {
+            let mut map = TrieMap::new();
+            for uint::range(0, len) |i| {
+                let key = d.read_map_elt_key(i, || Decodable::decode(d));
+                let val = d.read_map_elt_val(i, || Decodable::decode(d));
+                map.insert(key, val);
+            }
+            map
+        }
+    }
+}
+
+impl<S: Encoder> Encodable<S> for TrieSet {
+    fn encode(&self, s: &S) {
+        do s.emit_seq(self.len()) {
+            let mut i = 0;
+            for self.each |e| {
+                s.emit_seq_elt(i, || e.encode(s));
+                i += 1;
+            }
+        }
+    }
+}
+
+impl<D: Decoder> Decodable<D> for TrieSet {
+    fn decode(d: &D) -> TrieSet {
+        do d.read_seq |len| {
+            let mut set = TrieSet::new();
+            for uint::range(0, len) |i| {
+                set.insert(d.read_seq_elt(i, || Decodable::decode(d)));
+            }
+            set
+        }
+    }
+}
+
+impl<
+    E: Encoder,
+    K: Encodable<E> + Eq + TotalOrd,
+    V: Encodable<E> + Eq
+> Encodable<E> for TreeMap<K, V> {
+    fn encode(&self, e: &E) {
+        do e.emit_map(self.len()) {
+            let mut i = 0;
+            for self.each |&(key, val)| {
+                e.emit_map_elt_key(i, || key.encode(e));
+                e.emit_map_elt_val(i, || val.encode(e));
+                i += 1;
+            }
+        }
+    }
+}
+
+impl<
+    D: Decoder,
+    K: Decodable<D> + Eq + TotalOrd,
+    V: Decodable<D> + Eq
+> Decodable<D> for TreeMap<K, V> {
+    fn decode(d: &D) -> TreeMap<K, V> {
+        do d.read_map |len| {
+            let mut map = TreeMap::new();
+            for uint::range(0, len) |i| {
+                let key = d.read_map_elt_key(i, || Decodable::decode(d));
+                let val = d.read_map_elt_val(i, || Decodable::decode(d));
+                map.insert(key, val);
+            }
+            map
+        }
+    }
+}
+
+impl<
+    S: Encoder,
+    T: Encodable<S> + Eq + TotalOrd
+> Encodable<S> for TreeSet<T> {
+    fn encode(&self, s: &S) {
+        do s.emit_seq(self.len()) {
+            let mut i = 0;
+            for self.each |e| {
+                s.emit_seq_elt(i, || e.encode(s));
+                i += 1;
+            }
+        }
+    }
+}
+
+impl<
+    D: Decoder,
+    T: Decodable<D> + Eq + TotalOrd
+> Decodable<D> for TreeSet<T> {
+    fn decode(d: &D) -> TreeSet<T> {
+        do d.read_seq |len| {
+            let mut set = TreeSet::new();
+            for uint::range(0, len) |i| {
+                set.insert(d.read_seq_elt(i, || Decodable::decode(d)));
+            }
+            set
+        }
+    }
+}
+
 // ___________________________________________________________________________
 // Helper routines
 //
@@ -555,9 +785,9 @@ pub trait EncoderHelpers {
 
 impl<S:Encoder> EncoderHelpers for S {
     fn emit_from_vec<T>(&self, v: &[T], f: &fn(v: &T)) {
-        do self.emit_owned_vec(v.len()) {
+        do self.emit_seq(v.len()) {
             for v.eachi |i, e| {
-                do self.emit_vec_elt(i) {
+                do self.emit_seq_elt(i) {
                     f(e)
                 }
             }
@@ -571,9 +801,9 @@ pub trait DecoderHelpers {
 
 impl<D:Decoder> DecoderHelpers for D {
     fn read_to_vec<T>(&self, f: &fn() -> T) -> ~[T] {
-        do self.read_owned_vec |len| {
+        do self.read_seq |len| {
             do vec::from_fn(len) |i| {
-                self.read_vec_elt(i, || f())
+                self.read_seq_elt(i, || f())
             }
         }
     }
diff --git a/src/libstd/std.rc b/src/libstd/std.rc
index a0ab714de05..b28e2f0ab6d 100644
--- a/src/libstd/std.rc
+++ b/src/libstd/std.rc
@@ -88,7 +88,6 @@ pub mod md4;
 pub mod tempfile;
 pub mod term;
 pub mod time;
-pub mod prettyprint;
 pub mod arena;
 pub mod par;
 pub mod cmp;
diff --git a/src/libstd/workcache.rs b/src/libstd/workcache.rs
index f477a8c9f91..90f10ea5054 100644
--- a/src/libstd/workcache.rs
+++ b/src/libstd/workcache.rs
@@ -137,7 +137,11 @@ pub impl WorkKey {
     }
 }
 
-type WorkMap = LinearMap<WorkKey, ~str>;
+struct WorkMap(LinearMap<WorkKey, ~str>);
+
+impl WorkMap {
+    fn new() -> WorkMap { WorkMap(LinearMap::new()) }
+}
 
 impl<S:Encoder> Encodable<S> for WorkMap {
     fn encode(&self, s: &S) {
@@ -153,7 +157,7 @@ impl<S:Encoder> Encodable<S> for WorkMap {
 impl<D:Decoder> Decodable<D> for WorkMap {
     fn decode(d: &D) -> WorkMap {
         let v : ~[(WorkKey,~str)] = Decodable::decode(d);
-        let mut w = LinearMap::new();
+        let mut w = WorkMap::new();
         for v.each |&(k, v)| {
             w.insert(copy k, copy v);
         }
@@ -235,7 +239,7 @@ fn json_encode<T:Encodable<json::Encoder>>(t: &T) -> ~str {
 }
 
 // FIXME(#5121)
-fn json_decode<T:Decodable<json::Decoder<'static>>>(s: &str) -> T {
+fn json_decode<T:Decodable<json::Decoder>>(s: &str) -> T {
     do io::with_str_reader(s) |rdr| {
         let j = result::unwrap(json::from_reader(rdr));
         Decodable::decode(&json::Decoder(j))
@@ -260,18 +264,25 @@ pub impl Context {
     fn new(db: @Mut<Database>,
                   lg: @Mut<Logger>,
                   cfg: @json::Object) -> Context {
-        Context{db: db, logger: lg, cfg: cfg, freshness: LinearMap::new()}
+        Context {
+            db: db,
+            logger: lg,
+            cfg: cfg,
+            freshness: LinearMap::new()
+        }
     }
 
     fn prep<T:Owned +
               Encodable<json::Encoder> +
-              Decodable<json::Decoder<'static>>>( // FIXME(#5121)
+              Decodable<json::Decoder>>( // FIXME(#5121)
                   @self,
                   fn_name:&str,
                   blk: &fn(@Mut<Prep>)->Work<T>) -> Work<T> {
-        let p = @Mut(Prep {ctxt: self,
-                           fn_name: fn_name.to_owned(),
-                           declared_inputs: LinearMap::new()});
+        let p = @Mut(Prep {
+            ctxt: self,
+            fn_name: fn_name.to_owned(),
+            declared_inputs: WorkMap::new()
+        });
         blk(p)
     }
 }
@@ -283,7 +294,7 @@ trait TPrep {
     fn all_fresh(&self, cat:&str, map:&WorkMap) -> bool;
     fn exec<T:Owned +
               Encodable<json::Encoder> +
-              Decodable<json::Decoder<'static>>>( // FIXME(#5121)
+              Decodable<json::Decoder>>( // FIXME(#5121)
         &self, blk: ~fn(&Exec) -> T) -> Work<T>;
 }
 
@@ -324,7 +335,7 @@ impl TPrep for @Mut<Prep> {
 
     fn exec<T:Owned +
               Encodable<json::Encoder> +
-              Decodable<json::Decoder<'static>>>( // FIXME(#5121)
+              Decodable<json::Decoder>>( // FIXME(#5121)
             &self, blk: ~fn(&Exec) -> T) -> Work<T> {
         let mut bo = Some(blk);
 
@@ -349,8 +360,10 @@ impl TPrep for @Mut<Prep> {
                     let blk = blk.unwrap();
                     let chan = Cell(chan);
                     do task::spawn || {
-                        let exe = Exec{discovered_inputs: LinearMap::new(),
-                                       discovered_outputs: LinearMap::new()};
+                        let exe = Exec {
+                            discovered_inputs: WorkMap::new(),
+                            discovered_outputs: WorkMap::new(),
+                        };
                         let chan = chan.take();
                         let v = blk(&exe);
                         send_one(chan, (exe, v));
@@ -365,7 +378,7 @@ impl TPrep for @Mut<Prep> {
 
 pub impl<T:Owned +
          Encodable<json::Encoder> +
-         Decodable<json::Decoder<'static>>> Work<T> { // FIXME(#5121)
+         Decodable<json::Decoder>> Work<T> { // FIXME(#5121)
     fn new(p: @Mut<Prep>, e: Either<T,PortOne<(Exec,T)>>) -> Work<T> {
         Work { prep: p, res: Some(e) }
     }
@@ -374,7 +387,7 @@ pub impl<T:Owned +
 // FIXME (#3724): movable self. This should be in impl Work.
 fn unwrap<T:Owned +
             Encodable<json::Encoder> +
-            Decodable<json::Decoder<'static>>>( // FIXME(#5121)
+            Decodable<json::Decoder>>( // FIXME(#5121)
         w: Work<T>) -> T {
     let mut ww = w;
     let mut s = None;
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index db04c46ea59..16399674b55 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -71,7 +71,7 @@ impl<S:Encoder> Encodable<S> for ident {
             Some(intr) => intr
         };
 
-        s.emit_owned_str(*(*intr).get(*self));
+        s.emit_str(*(*intr).get(*self));
     }
 }
 
@@ -84,7 +84,7 @@ impl<D:Decoder> Decodable<D> for ident {
             Some(intr) => intr
         };
 
-        (*intr).intern(@d.read_owned_str())
+        (*intr).intern(@d.read_str())
     }
 }
 
diff --git a/src/libsyntax/ext/auto_encode.rs b/src/libsyntax/ext/auto_encode.rs
index d7e0e9aa550..d25792355a7 100644
--- a/src/libsyntax/ext/auto_encode.rs
+++ b/src/libsyntax/ext/auto_encode.rs
@@ -1240,14 +1240,7 @@ mod test {
         fn emit_float(&self, +_v: float) { self.add_unknown_to_log(); }
 
         fn emit_char(&self, +_v: char) { self.add_unknown_to_log(); }
-
-        fn emit_borrowed_str(&self, +_v: &str) { self.add_unknown_to_log(); }
-        fn emit_owned_str(&self, +_v: &str) { self.add_unknown_to_log(); }
-        fn emit_managed_str(&self, +_v: &str) { self.add_unknown_to_log(); }
-
-        fn emit_borrowed(&self, f: &fn()) { self.add_unknown_to_log(); f() }
-        fn emit_owned(&self, f: &fn()) { self.add_unknown_to_log(); f() }
-        fn emit_managed(&self, f: &fn()) { self.add_unknown_to_log(); f() }
+        fn emit_str(&self, +_v: &str) { self.add_unknown_to_log(); }
 
         fn emit_enum(&self, name: &str, f: &fn()) {
             self.add_to_log(CallToEmitEnum(name.to_str())); f(); }
@@ -1262,23 +1255,13 @@ mod test {
             self.add_to_log(CallToEmitEnumVariantArg (idx)); f();
         }
 
-        fn emit_borrowed_vec(&self, +_len: uint, f: &fn()) {
-            self.add_unknown_to_log(); f();
-        }
-
-        fn emit_owned_vec(&self, +_len: uint, f: &fn()) {
+        fn emit_seq(&self, +_len: uint, f: &fn()) {
             self.add_unknown_to_log(); f();
         }
-        fn emit_managed_vec(&self, +_len: uint, f: &fn()) {
-            self.add_unknown_to_log(); f();
-        }
-        fn emit_vec_elt(&self, +_idx: uint, f: &fn()) {
+        fn emit_seq_elt(&self, +_idx: uint, f: &fn()) {
             self.add_unknown_to_log(); f();
         }
 
-        fn emit_rec(&self, f: &fn()) {
-            self.add_unknown_to_log(); f();
-        }
         fn emit_struct(&self, name: &str, +len: uint, f: &fn()) {
             self.add_to_log(CallToEmitStruct (name.to_str(),len)); f();
         }
@@ -1286,13 +1269,6 @@ mod test {
             self.add_to_log(CallToEmitField (name.to_str(),idx)); f();
         }
 
-        fn emit_tup(&self, +_len: uint, f: &fn()) {
-            self.add_unknown_to_log(); f();
-        }
-        fn emit_tup_elt(&self, +_idx: uint, f: &fn()) {
-            self.add_unknown_to_log(); f();
-        }
-
         fn emit_option(&self, f: &fn()) {
             self.add_to_log(CallToEmitOption);
             f();
@@ -1304,6 +1280,16 @@ mod test {
             self.add_to_log(CallToEmitOptionSome);
             f();
         }
+
+        fn emit_map(&self, _len: uint, f: &fn()) {
+            self.add_unknown_to_log(); f();
+        }
+        fn emit_map_elt_key(&self, _idx: uint, f: &fn()) {
+            self.add_unknown_to_log(); f();
+        }
+        fn emit_map_elt_val(&self, _idx: uint, f: &fn()) {
+            self.add_unknown_to_log(); f();
+        }
     }
 
 
diff --git a/src/test/run-pass/auto-encode.rs b/src/test/run-pass/auto-encode.rs
index c4d4f305a62..e0720876900 100644
--- a/src/test/run-pass/auto-encode.rs
+++ b/src/test/run-pass/auto-encode.rs
@@ -22,21 +22,9 @@ use EBWriter = std::ebml::writer;
 use core::cmp::Eq;
 use core::io::Writer;
 use std::ebml;
-use std::prettyprint;
 use std::serialize::{Encodable, Decodable};
 use std::time;
 
-fn test_prettyprint<A:Encodable<prettyprint::Serializer>>(
-    a: &A,
-    expected: &~str
-) {
-    let s = do io::with_str_writer |w| {
-        a.encode(&prettyprint::Serializer(w))
-    };
-    debug!("s == %?", s);
-    assert!(s == *expected);
-}
-
 fn test_ebml<A:
     Eq +
     Encodable<EBWriter::Encoder> +
@@ -149,36 +137,27 @@ enum CLike { A, B, C }
 
 pub fn main() {
     let a = &Plus(@Minus(@Val(3u), @Val(10u)), @Plus(@Val(22u), @Val(5u)));
-    test_prettyprint(a, &~"Plus(@Minus(@Val(3u), @Val(10u)), \
-                           @Plus(@Val(22u), @Val(5u)))");
     test_ebml(a);
 
     let a = &Spanned {lo: 0u, hi: 5u, node: 22u};
-    test_prettyprint(a, &~"Spanned {lo: 0u, hi: 5u, node: 22u}");
     test_ebml(a);
 
     let a = &Point {x: 3u, y: 5u};
-    test_prettyprint(a, &~"Point {x: 3u, y: 5u}");
     test_ebml(a);
 
     let a = &@[1u, 2u, 3u];
-    test_prettyprint(a, &~"@[1u, 2u, 3u]");
     test_ebml(a);
 
     let a = &Top(22u);
-    test_prettyprint(a, &~"Top(22u)");
     test_ebml(a);
 
     let a = &Bottom(222u);
-    test_prettyprint(a, &~"Bottom(222u)");
     test_ebml(a);
 
     let a = &A;
-    test_prettyprint(a, &~"A");
     test_ebml(a);
 
     let a = &B;
-    test_prettyprint(a, &~"B");
     test_ebml(a);
 
     let a = &time::now();