libstd: Implement `StrBuf`, a new string buffer type like `Vec`, and

port all code over to use it.

66 files changed, 987 insertions, 928 deletions

diff --git a/src/compiletest/runtest.rs b/src/compiletest/runtest.rs
index b290bd2838a..9c5a71efac6 100644
--- a/src/compiletest/runtest.rs
+++ b/src/compiletest/runtest.rs
@@ -31,6 +31,7 @@ use std::io::timer;
 use std::io;
 use std::os;
 use std::str;
+use std::strbuf::StrBuf;
 use std::task;
 use std::slice;
 use test::MetricMap;
@@ -328,10 +329,10 @@ fn run_debuginfo_test(config: &config, props: &TestProps, testfile: &Path) {
             }
 
             let args = split_maybe_args(&config.target_rustcflags);
-            let mut tool_path:~str = ~"";
+            let mut tool_path = StrBuf::new();
             for arg in args.iter() {
                 if arg.contains("android-cross-path=") {
-                    tool_path = arg.replace("android-cross-path=","");
+                    tool_path = StrBuf::from_str(arg.replace("android-cross-path=", ""));
                     break;
                 }
             }
@@ -348,7 +349,7 @@ fn run_debuginfo_test(config: &config, props: &TestProps, testfile: &Path) {
             let gdb_path = tool_path.append("/bin/arm-linux-androideabi-gdb");
             let procsrv::Result{ out, err, status }=
                 procsrv::run("",
-                             gdb_path,
+                             gdb_path.as_slice(),
                              debugger_opts.as_slice(),
                              vec!((~"",~"")),
                              None)
diff --git a/src/doc/tutorial.md b/src/doc/tutorial.md
index d0463ca17d3..a0a012ef69b 100644
--- a/src/doc/tutorial.md
+++ b/src/doc/tutorial.md
@@ -1579,6 +1579,8 @@ allocated memory on the heap. A unique vector owns the elements it contains, so
 the elements are mutable if the vector is mutable.
 
 ~~~
+use std::strbuf::StrBuf;
+
 // A dynamically sized vector (unique vector)
 let mut numbers = ~[1, 2, 3];
 numbers.push(4);
@@ -1589,7 +1591,7 @@ let more_numbers: ~[int] = numbers;
 
 // The original `numbers` value can no longer be used, due to move semantics.
 
-let mut string = ~"fo";
+let mut string = StrBuf::from_str("fo");
 string.push_char('o');
 ~~~
 
diff --git a/src/libcollections/bitv.rs b/src/libcollections/bitv.rs
index 510e8908427..49865cf5272 100644
--- a/src/libcollections/bitv.rs
+++ b/src/libcollections/bitv.rs
@@ -15,8 +15,9 @@ use std::cmp;
 use std::iter::RandomAccessIterator;
 use std::iter::{Rev, Enumerate, Repeat, Map, Zip};
 use std::ops;
-use std::uint;
 use std::slice;
+use std::strbuf::StrBuf;
+use std::uint;
 
 #[deriving(Clone)]
 struct SmallBitv {
@@ -499,7 +500,7 @@ impl Bitv {
      * character is either '0' or '1'.
      */
      pub fn to_str(&self) -> ~str {
-        let mut rs = ~"";
+        let mut rs = StrBuf::new();
         for i in self.iter() {
             if i {
                 rs.push_char('1');
@@ -507,7 +508,7 @@ impl Bitv {
                 rs.push_char('0');
             }
         };
-        rs
+        rs.into_owned()
      }
 
 
diff --git a/src/libcollections/hashmap.rs b/src/libcollections/hashmap.rs
index 8090b2cea8c..bd0e2ebec6f 100644
--- a/src/libcollections/hashmap.rs
+++ b/src/libcollections/hashmap.rs
@@ -795,6 +795,97 @@ impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     fn search(&self, k: &K) -> Option<table::FullIndex> {
         self.search_hashed(&self.make_hash(k), k)
     }
+
+    fn pop_internal(&mut self, starting_index: table::FullIndex) -> Option<V> {
+        let starting_probe = starting_index.raw_index();
+
+        let ending_probe = {
+            let mut probe = self.probe_next(starting_probe);
+            for _ in range(0u, self.table.size()) {
+                match self.table.peek(probe) {
+                    table::Empty(_) => {}, // empty bucket. this is the end of our shifting.
+                    table::Full(idx) => {
+                        // Bucket that isn't us, which has a non-zero probe distance.
+                        // This isn't the ending index, so keep searching.
+                        if self.bucket_distance(&idx) != 0 {
+                            probe = self.probe_next(probe);
+                            continue;
+                        }
+
+                        // if we do have a bucket_distance of zero, we're at the end
+                        // of what we need to shift.
+                    }
+                }
+                break;
+            }
+
+            probe
+        };
+
+        let (_, _, retval) = self.table.take(starting_index);
+
+        let mut      probe = starting_probe;
+        let mut next_probe = self.probe_next(probe);
+
+        // backwards-shift all the elements after our newly-deleted one.
+        while next_probe != ending_probe {
+            match self.table.peek(next_probe) {
+                table::Empty(_) => {
+                    // nothing to shift in. just empty it out.
+                    match self.table.peek(probe) {
+                        table::Empty(_) => {},
+                        table::Full(idx) => { self.table.take(idx); }
+                    }
+                },
+                table::Full(next_idx) => {
+                    // something to shift. move it over!
+                    let next_hash = next_idx.hash();
+                    let (_, next_key, next_val) = self.table.take(next_idx);
+                    match self.table.peek(probe) {
+                        table::Empty(idx) => {
+                            self.table.put(idx, next_hash, next_key, next_val);
+                        },
+                        table::Full(idx) => {
+                            let (emptyidx, _, _) = self.table.take(idx);
+                            self.table.put(emptyidx, next_hash, next_key, next_val);
+                        }
+                    }
+                }
+            }
+
+            probe = next_probe;
+            next_probe = self.probe_next(next_probe);
+        }
+
+        // Done the backwards shift, but there's still an element left!
+        // Empty it out.
+        match self.table.peek(probe) {
+            table::Empty(_) => {},
+            table::Full(idx) => { self.table.take(idx); }
+        }
+
+        // Now we're done all our shifting. Return the value we grabbed
+        // earlier.
+        return Some(retval);
+    }
+
+    /// Like `pop`, but can operate on any type that is equivalent to a key.
+    #[experimental]
+    pub fn pop_equiv<Q:Hash<S> + Equiv<K>>(&mut self, k: &Q) -> Option<V> {
+        if self.table.size() == 0 {
+            return None
+        }
+
+        let potential_new_size = self.table.size() - 1;
+        self.make_some_room(potential_new_size);
+
+        let starting_index = match self.search_equiv(k) {
+            Some(idx) => idx,
+            None      => return None,
+        };
+
+        self.pop_internal(starting_index)
+    }
 }
 
 impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> Container for HashMap<K, V, H> {
@@ -894,77 +985,9 @@ impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> MutableMap<K, V> for HashMap<K, V
             None      => return None,
         };
 
-        let starting_probe = starting_index.raw_index();
-
-        let ending_probe = {
-            let mut probe = self.probe_next(starting_probe);
-            for _ in range(0u, self.table.size()) {
-                match self.table.peek(probe) {
-                    table::Empty(_) => {}, // empty bucket. this is the end of our shifting.
-                    table::Full(idx) => {
-                        // Bucket that isn't us, which has a non-zero probe distance.
-                        // This isn't the ending index, so keep searching.
-                        if self.bucket_distance(&idx) != 0 {
-                            probe = self.probe_next(probe);
-                            continue;
-                        }
-
-                        // if we do have a bucket_distance of zero, we're at the end
-                        // of what we need to shift.
-                    }
-                }
-                break;
-            }
-
-            probe
-        };
-
-        let (_, _, retval) = self.table.take(starting_index);
-
-        let mut      probe = starting_probe;
-        let mut next_probe = self.probe_next(probe);
-
-        // backwards-shift all the elements after our newly-deleted one.
-        while next_probe != ending_probe {
-            match self.table.peek(next_probe) {
-                table::Empty(_) => {
-                    // nothing to shift in. just empty it out.
-                    match self.table.peek(probe) {
-                        table::Empty(_) => {},
-                        table::Full(idx) => { self.table.take(idx); }
-                    }
-                },
-                table::Full(next_idx) => {
-                    // something to shift. move it over!
-                    let next_hash = next_idx.hash();
-                    let (_, next_key, next_val) = self.table.take(next_idx);
-                    match self.table.peek(probe) {
-                        table::Empty(idx) => {
-                            self.table.put(idx, next_hash, next_key, next_val);
-                        },
-                        table::Full(idx) => {
-                            let (emptyidx, _, _) = self.table.take(idx);
-                            self.table.put(emptyidx, next_hash, next_key, next_val);
-                        }
-                    }
-                }
-            }
-
-            probe = next_probe;
-            next_probe = self.probe_next(next_probe);
-        }
-
-        // Done the backwards shift, but there's still an element left!
-        // Empty it out.
-        match self.table.peek(probe) {
-            table::Empty(_) => {},
-            table::Full(idx) => { self.table.take(idx); }
-        }
-
-        // Now we're done all our shifting. Return the value we grabbed
-        // earlier.
-        return Some(retval);
+        self.pop_internal(starting_index)
     }
+
 }
 
 impl<K: Hash + TotalEq, V> HashMap<K, V, sip::SipHasher> {
@@ -1571,10 +1594,20 @@ pub type SetAlgebraItems<'a, T, H> =
 #[cfg(test)]
 mod test_map {
     use super::HashMap;
+    use std::cmp::Equiv;
     use std::iter::{Iterator,range_inclusive,range_step_inclusive};
     use std::local_data;
     use std::vec;
 
+    struct KindaIntLike(int);
+
+    impl Equiv<int> for KindaIntLike {
+        fn equiv(&self, other: &int) -> bool {
+            let KindaIntLike(this) = *self;
+            this == *other
+        }
+    }
+
     #[test]
     fn test_create_capacity_zero() {
         let mut m = HashMap::with_capacity(0);
@@ -1815,6 +1848,14 @@ mod test_map {
     }
 
     #[test]
+    fn test_pop_equiv() {
+        let mut m = HashMap::new();
+        m.insert(1, 2);
+        assert_eq!(m.pop_equiv(&KindaIntLike(1), Some(2)));
+        assert_eq!(m.pop_equiv(&KindaIntLike(1), None));
+    }
+
+    #[test]
     fn test_swap() {
         let mut m = HashMap::new();
         assert_eq!(m.swap(1, 2), None);
diff --git a/src/libgetopts/lib.rs b/src/libgetopts/lib.rs
index 9d4f2e2f8f0..c8c013b99f2 100644
--- a/src/libgetopts/lib.rs
+++ b/src/libgetopts/lib.rs
@@ -92,6 +92,7 @@
 use std::cmp::Eq;
 use std::result::{Err, Ok};
 use std::result;
+use std::strbuf::StrBuf;
 
 /// Name of an option. Either a string or a single char.
 #[deriving(Clone, Eq)]
@@ -664,7 +665,7 @@ pub fn usage(brief: &str, opts: &[OptGroup]) -> ~str {
                      hasarg: hasarg,
                      ..} = (*optref).clone();
 
-        let mut row = " ".repeat(4);
+        let mut row = StrBuf::from_owned_str(" ".repeat(4));
 
         // short option
         match short_name.len() {
@@ -700,7 +701,7 @@ pub fn usage(brief: &str, opts: &[OptGroup]) -> ~str {
 
         // FIXME: #5516 should be graphemes not codepoints
         // here we just need to indent the start of the description
-        let rowlen = row.char_len();
+        let rowlen = row.as_slice().char_len();
         if rowlen < 24 {
             for _ in range(0, 24 - rowlen) {
                 row.push_char(' ');
@@ -710,7 +711,7 @@ pub fn usage(brief: &str, opts: &[OptGroup]) -> ~str {
         }
 
         // Normalize desc to contain words separated by one space character
-        let mut desc_normalized_whitespace = ~"";
+        let mut desc_normalized_whitespace = StrBuf::new();
         for word in desc.words() {
             desc_normalized_whitespace.push_str(word);
             desc_normalized_whitespace.push_char(' ');
@@ -718,7 +719,9 @@ pub fn usage(brief: &str, opts: &[OptGroup]) -> ~str {
 
         // FIXME: #5516 should be graphemes not codepoints
         let mut desc_rows = Vec::new();
-        each_split_within(desc_normalized_whitespace, 54, |substr| {
+        each_split_within(desc_normalized_whitespace.as_slice(),
+                          54,
+                          |substr| {
             desc_rows.push(substr.to_owned());
             true
         });
@@ -727,14 +730,14 @@ pub fn usage(brief: &str, opts: &[OptGroup]) -> ~str {
         // wrapped description
         row.push_str(desc_rows.connect(desc_sep));
 
-        row
+        row.into_owned()
     });
 
     format!("{}\n\nOptions:\n{}\n", brief, rows.collect::<Vec<~str> >().connect("\n"))
 }
 
 fn format_option(opt: &OptGroup) -> ~str {
-    let mut line = ~"";
+    let mut line = StrBuf::new();
 
     if opt.occur != Req {
         line.push_char('[');
@@ -767,15 +770,14 @@ fn format_option(opt: &OptGroup) -> ~str {
         line.push_str("..");
     }
 
-    line
+    line.into_owned()
 }
 
 /// Derive a short one-line usage summary from a set of long options.
 pub fn short_usage(program_name: &str, opts: &[OptGroup]) -> ~str {
-    let mut line = ~"Usage: " + program_name + " ";
+    let mut line = StrBuf::from_str("Usage: " + program_name + " ");
     line.push_str(opts.iter().map(format_option).collect::<Vec<~str>>().connect(" "));
-
-    line
+    line.into_owned()
 }
 
 
diff --git a/src/libglob/lib.rs b/src/libglob/lib.rs
index d19924da5be..e7661b26b76 100644
--- a/src/libglob/lib.rs
+++ b/src/libglob/lib.rs
@@ -35,6 +35,7 @@ use std::cell::Cell;
 use std::{cmp, os, path};
 use std::io::fs;
 use std::path::is_sep;
+use std::strbuf::StrBuf;
 
 /**
  * An iterator that yields Paths from the filesystem that match a particular
@@ -308,7 +309,7 @@ impl Pattern {
      * match the input string and nothing else.
      */
     pub fn escape(s: &str) -> ~str {
-        let mut escaped = ~"";
+        let mut escaped = StrBuf::new();
         for c in s.chars() {
             match c {
                 // note that ! does not need escaping because it is only special inside brackets
@@ -322,7 +323,7 @@ impl Pattern {
                 }
             }
         }
-        escaped
+        escaped.into_owned()
     }
 
     /**
diff --git a/src/libnative/io/process.rs b/src/libnative/io/process.rs
index fcf59cb0548..8ef46239e61 100644
--- a/src/libnative/io/process.rs
+++ b/src/libnative/io/process.rs
@@ -20,6 +20,7 @@ use super::IoResult;
 use super::file;
 
 #[cfg(windows)] use std::cast;
+#[cfg(windows)] use std::strbuf::StrBuf;
 #[cfg(not(windows))] use super::retry;
 
 /**
@@ -395,15 +396,15 @@ fn zeroed_process_information() -> libc::types::os::arch::extra::PROCESS_INFORMA
 
 #[cfg(windows)]
 fn make_command_line(prog: &str, args: &[~str]) -> ~str {
-    let mut cmd = ~"";
+    let mut cmd = StrBuf::new();
     append_arg(&mut cmd, prog);
     for arg in args.iter() {
         cmd.push_char(' ');
         append_arg(&mut cmd, *arg);
     }
-    return cmd;
+    return cmd.to_owned_str();
 
-    fn append_arg(cmd: &mut ~str, arg: &str) {
+    fn append_arg(cmd: &mut StrBuf, arg: &str) {
         let quote = arg.chars().any(|c| c == ' ' || c == '\t');
         if quote {
             cmd.push_char('"');
@@ -416,7 +417,7 @@ fn make_command_line(prog: &str, args: &[~str]) -> ~str {
         }
     }
 
-    fn append_char_at(cmd: &mut ~str, arg: &str, i: uint) {
+    fn append_char_at(cmd: &mut StrBuf, arg: &str, i: uint) {
         match arg[i] as char {
             '"' => {
                 // Escape quotes.
diff --git a/src/libnum/bigint.rs b/src/libnum/bigint.rs
index f6f0db4b6a9..399fc89bb19 100644
--- a/src/libnum/bigint.rs
+++ b/src/libnum/bigint.rs
@@ -25,7 +25,7 @@ use std::num::CheckedDiv;
 use std::num::{Bitwise, ToPrimitive, FromPrimitive};
 use std::num::{Zero, One, ToStrRadix, FromStrRadix};
 use rand::Rng;
-use std::str;
+use std::strbuf::StrBuf;
 use std::uint;
 use std::{i64, u64};
 
@@ -666,13 +666,13 @@ impl ToStrRadix for BigUint {
 
         fn fill_concat(v: &[BigDigit], radix: uint, l: uint) -> ~str {
             if v.is_empty() { return ~"0" }
-            let mut s = str::with_capacity(v.len() * l);
+            let mut s = StrBuf::with_capacity(v.len() * l);
             for n in v.rev_iter() {
                 let ss = (*n as uint).to_str_radix(radix);
                 s.push_str("0".repeat(l - ss.len()));
                 s.push_str(ss);
             }
-            s.trim_left_chars(&'0').to_owned()
+            s.as_slice().trim_left_chars(&'0').to_owned()
         }
     }
 }
diff --git a/src/librand/lib.rs b/src/librand/lib.rs
index c9e4c81901e..e297dd43617 100644
--- a/src/librand/lib.rs
+++ b/src/librand/lib.rs
@@ -80,7 +80,7 @@ use std::cast;
 use std::io::IoResult;
 use std::kinds::marker;
 use std::local_data;
-use std::str;
+use std::strbuf::StrBuf;
 
 pub use isaac::{IsaacRng, Isaac64Rng};
 pub use os::OSRng;
@@ -258,11 +258,11 @@ pub trait Rng {
         static GEN_ASCII_STR_CHARSET: &'static [u8] = bytes!("ABCDEFGHIJKLMNOPQRSTUVWXYZ\
                                                              abcdefghijklmnopqrstuvwxyz\
                                                              0123456789");
-        let mut s = str::with_capacity(len);
+        let mut s = StrBuf::with_capacity(len);
         for _ in range(0, len) {
             s.push_char(self.choose(GEN_ASCII_STR_CHARSET) as char)
         }
-        s
+        s.into_owned()
     }
 
     /// Choose an item randomly, failing if `values` is empty.
diff --git a/src/librustc/back/link.rs b/src/librustc/back/link.rs
index 0946e375e4f..4e407d52329 100644
--- a/src/librustc/back/link.rs
+++ b/src/librustc/back/link.rs
@@ -28,11 +28,12 @@ use util::sha2::{Digest, Sha256};
 
 use std::c_str::{ToCStr, CString};
 use std::char;
+use std::io::{fs, TempDir, Process};
+use std::io;
 use std::os::consts::{macos, freebsd, linux, android, win32};
 use std::ptr;
 use std::str;
-use std::io;
-use std::io::{fs, TempDir, Process};
+use std::strbuf::StrBuf;
 use flate;
 use serialize::hex::ToHex;
 use syntax::abi;
@@ -546,8 +547,11 @@ fn truncated_hash_result(symbol_hasher: &mut Sha256) -> ~str {
 
 
 // This calculates STH for a symbol, as defined above
-fn symbol_hash(tcx: &ty::ctxt, symbol_hasher: &mut Sha256,
-               t: ty::t, link_meta: &LinkMeta) -> ~str {
+fn symbol_hash(tcx: &ty::ctxt,
+               symbol_hasher: &mut Sha256,
+               t: ty::t,
+               link_meta: &LinkMeta)
+               -> ~str {
     // NB: do *not* use abbrevs here as we want the symbol names
     // to be independent of one another in the crate.
 
@@ -557,10 +561,10 @@ fn symbol_hash(tcx: &ty::ctxt, symbol_hasher: &mut Sha256,
     symbol_hasher.input_str(link_meta.crate_hash.as_str());
     symbol_hasher.input_str("-");
     symbol_hasher.input_str(encoder::encoded_ty(tcx, t));
-    let mut hash = truncated_hash_result(symbol_hasher);
     // Prefix with 'h' so that it never blends into adjacent digits
-    hash.unshift_char('h');
-    hash
+    let mut hash = StrBuf::from_str("h");
+    hash.push_str(truncated_hash_result(symbol_hasher));
+    hash.into_owned()
 }
 
 fn get_symbol_hash(ccx: &CrateContext, t: ty::t) -> ~str {
@@ -580,7 +584,7 @@ fn get_symbol_hash(ccx: &CrateContext, t: ty::t) -> ~str {
 // gas doesn't!
 // gas accepts the following characters in symbols: a-z, A-Z, 0-9, ., _, $
 pub fn sanitize(s: &str) -> ~str {
-    let mut result = ~"";
+    let mut result = StrBuf::new();
     for c in s.chars() {
         match c {
             // Escape these with $ sequences
@@ -605,15 +609,16 @@ pub fn sanitize(s: &str) -> ~str {
             | '_' | '.' | '$' => result.push_char(c),
 
             _ => {
-                let mut tstr = ~"";
+                let mut tstr = StrBuf::new();
                 char::escape_unicode(c, |c| tstr.push_char(c));
                 result.push_char('$');
-                result.push_str(tstr.slice_from(1));
+                result.push_str(tstr.as_slice().slice_from(1));
             }
         }
     }
 
     // Underscore-qualify anything that didn't start as an ident.
+    let result = result.into_owned();
     if result.len() > 0u &&
         result[0] != '_' as u8 &&
         ! char::is_XID_start(result[0] as char) {
@@ -640,9 +645,9 @@ pub fn mangle<PI: Iterator<PathElem>>(mut path: PI,
     // To be able to work on all platforms and get *some* reasonable output, we
     // use C++ name-mangling.
 
-    let mut n = ~"_ZN"; // _Z == Begin name-sequence, N == nested
+    let mut n = StrBuf::from_str("_ZN"); // _Z == Begin name-sequence, N == nested
 
-    fn push(n: &mut ~str, s: &str) {
+    fn push(n: &mut StrBuf, s: &str) {
         let sani = sanitize(s);
         n.push_str(format!("{}{}", sani.len(), sani));
     }
@@ -662,7 +667,7 @@ pub fn mangle<PI: Iterator<PathElem>>(mut path: PI,
     }
 
     n.push_char('E'); // End name-sequence.
-    n
+    n.into_owned()
 }
 
 pub fn exported_name(path: PathElems, hash: &str, vers: &str) -> ~str {
@@ -679,7 +684,7 @@ pub fn exported_name(path: PathElems, hash: &str, vers: &str) -> ~str {
 
 pub fn mangle_exported_name(ccx: &CrateContext, path: PathElems,
                             t: ty::t, id: ast::NodeId) -> ~str {
-    let mut hash = get_symbol_hash(ccx, t);
+    let mut hash = StrBuf::from_owned_str(get_symbol_hash(ccx, t));
 
     // Paths can be completely identical for different nodes,
     // e.g. `fn foo() { { fn a() {} } { fn a() {} } }`, so we
@@ -699,7 +704,9 @@ pub fn mangle_exported_name(ccx: &CrateContext, path: PathElems,
     hash.push_char(EXTRA_CHARS[extra2] as char);
     hash.push_char(EXTRA_CHARS[extra3] as char);
 
-    exported_name(path, hash, ccx.link_meta.crateid.version_or_default())
+    exported_name(path,
+                  hash.as_slice(),
+                  ccx.link_meta.crateid.version_or_default())
 }
 
 pub fn mangle_internal_name_by_type_and_seq(ccx: &CrateContext,
diff --git a/src/librustc/metadata/tydecode.rs b/src/librustc/metadata/tydecode.rs
index 599a1dad33d..f0fcabdabb7 100644
--- a/src/librustc/metadata/tydecode.rs
+++ b/src/librustc/metadata/tydecode.rs
@@ -19,6 +19,7 @@
 use middle::ty;
 
 use std::str;
+use std::strbuf::StrBuf;
 use std::uint;
 use syntax::abi;
 use syntax::ast;
@@ -276,14 +277,14 @@ fn parse_opt<T>(st: &mut PState, f: |&mut PState| -> T) -> Option<T> {
 }
 
 fn parse_str(st: &mut PState, term: char) -> ~str {
-    let mut result = ~"";
+    let mut result = StrBuf::new();
     while peek(st) != term {
         unsafe {
-            str::raw::push_byte(&mut result, next_byte(st));
+            result.push_bytes([next_byte(st)])
         }
     }
     next(st);
-    return result;
+    return result.into_owned();
 }
 
 fn parse_trait_ref(st: &mut PState, conv: conv_did) -> ty::TraitRef {
diff --git a/src/librustc/middle/astencode.rs b/src/librustc/middle/astencode.rs
index 3529f2c57c0..e5b87d716e0 100644
--- a/src/librustc/middle/astencode.rs
+++ b/src/librustc/middle/astencode.rs
@@ -40,6 +40,7 @@ use std::cell::RefCell;
 use std::io::Seek;
 use std::io::MemWriter;
 use std::rc::Rc;
+use std::strbuf::StrBuf;
 
 use serialize::ebml::reader;
 use serialize::ebml;
@@ -1192,11 +1193,11 @@ impl<'a> ebml_decoder_decoder_helpers for reader::Decoder<'a> {
         }).unwrap();
 
         fn type_string(doc: ebml::Doc) -> ~str {
-            let mut str = ~"";
+            let mut str = StrBuf::new();
             for i in range(doc.start, doc.end) {
                 str.push_char(doc.data[i] as char);
             }
-            str
+            str.into_owned()
         }
     }
 
diff --git a/src/librustc/middle/borrowck/mod.rs b/src/librustc/middle/borrowck/mod.rs
index cf558c6afe3..83c45dc830f 100644
--- a/src/librustc/middle/borrowck/mod.rs
+++ b/src/librustc/middle/borrowck/mod.rs
@@ -24,7 +24,8 @@ use util::ppaux::{note_and_explain_region, Repr, UserString};
 use std::cell::{Cell, RefCell};
 use collections::HashMap;
 use std::ops::{BitOr, BitAnd};
-use std::result::{Result};
+use std::result::Result;
+use std::strbuf::StrBuf;
 use syntax::ast;
 use syntax::ast_map;
 use syntax::ast_util;
@@ -802,7 +803,7 @@ impl<'a> BorrowckCtxt<'a> {
 
     pub fn append_loan_path_to_str(&self,
                                    loan_path: &LoanPath,
-                                   out: &mut ~str) {
+                                   out: &mut StrBuf) {
         match *loan_path {
             LpVar(id) => {
                 out.push_str(ty::local_var_name_str(self.tcx, id).get());
@@ -836,7 +837,7 @@ impl<'a> BorrowckCtxt<'a> {
 
     pub fn append_autoderefd_loan_path_to_str(&self,
                                               loan_path: &LoanPath,
-                                              out: &mut ~str) {
+                                              out: &mut StrBuf) {
         match *loan_path {
             LpExtend(lp_base, _, LpDeref(_)) => {
                 // For a path like `(*x).f` or `(*x)[3]`, autoderef
@@ -852,9 +853,9 @@ impl<'a> BorrowckCtxt<'a> {
     }
 
     pub fn loan_path_to_str(&self, loan_path: &LoanPath) -> ~str {
-        let mut result = ~"";
+        let mut result = StrBuf::new();
         self.append_loan_path_to_str(loan_path, &mut result);
-        result
+        result.into_owned()
     }
 
     pub fn cmt_to_str(&self, cmt: mc::cmt) -> ~str {
diff --git a/src/librustc/middle/dataflow.rs b/src/librustc/middle/dataflow.rs
index 2ef1adba771..13e16ec9d82 100644
--- a/src/librustc/middle/dataflow.rs
+++ b/src/librustc/middle/dataflow.rs
@@ -18,8 +18,9 @@
 
 
 use std::io;
-use std::uint;
 use std::slice;
+use std::strbuf::StrBuf;
+use std::uint;
 use syntax::ast;
 use syntax::ast_util;
 use syntax::ast_util::IdRange;
@@ -832,7 +833,7 @@ fn mut_bits_to_str(words: &mut [uint]) -> ~str {
 }
 
 fn bits_to_str(words: &[uint]) -> ~str {
-    let mut result = ~"";
+    let mut result = StrBuf::new();
     let mut sep = '[';
 
     // Note: this is a little endian printout of bytes.
@@ -847,7 +848,7 @@ fn bits_to_str(words: &[uint]) -> ~str {
         }
     }
     result.push_char(']');
-    return result;
+    return result.into_owned();
 }
 
 fn copy_bits(in_vec: &[uint], out_vec: &mut [uint]) -> bool {
diff --git a/src/librustc/middle/resolve.rs b/src/librustc/middle/resolve.rs
index 143b02f96d2..25720b7d7ca 100644
--- a/src/librustc/middle/resolve.rs
+++ b/src/librustc/middle/resolve.rs
@@ -31,10 +31,11 @@ use syntax::owned_slice::OwnedSlice;
 use syntax::visit;
 use syntax::visit::Visitor;
 
+use collections::{HashMap, HashSet};
 use std::cell::{Cell, RefCell};
-use std::uint;
 use std::mem::replace;
-use collections::{HashMap, HashSet};
+use std::strbuf::StrBuf;
+use std::uint;
 
 // Definition mapping
 pub type DefMap = @RefCell<NodeMap<Def>>;
@@ -2096,7 +2097,7 @@ impl<'a> Resolver<'a> {
 
     fn idents_to_str(&mut self, idents: &[Ident]) -> ~str {
         let mut first = true;
-        let mut result = ~"";
+        let mut result = StrBuf::new();
         for ident in idents.iter() {
             if first {
                 first = false
@@ -2105,7 +2106,7 @@ impl<'a> Resolver<'a> {
             }
             result.push_str(token::get_ident(*ident).get());
         };
-        return result;
+        result.into_owned()
     }
 
     fn path_idents_to_str(&mut self, path: &Path) -> ~str {
diff --git a/src/librustc/middle/trans/asm.rs b/src/librustc/middle/trans/asm.rs
index 5c32b3fba44..43b74c387ae 100644
--- a/src/librustc/middle/trans/asm.rs
+++ b/src/librustc/middle/trans/asm.rs
@@ -23,6 +23,7 @@ use middle::trans::type_of;
 use middle::trans::type_::Type;
 
 use std::c_str::ToCStr;
+use std::strbuf::StrBuf;
 use syntax::ast;
 
 // Take an inline assembly expression and splat it out via LLVM
@@ -62,14 +63,17 @@ pub fn trans_inline_asm<'a>(bcx: &'a Block<'a>, ia: &ast::InlineAsm)
     // no failure occurred preparing operands, no need to cleanup
     fcx.pop_custom_cleanup_scope(temp_scope);
 
-    let mut constraints = constraints.iter()
-                                     .map(|s| s.get().to_str())
-                                     .collect::<Vec<~str>>()
-                                     .connect(",");
+    let mut constraints =
+        StrBuf::from_str(constraints.iter()
+                                    .map(|s| s.get().to_str())
+                                    .collect::<Vec<~str>>()
+                                    .connect(","));
 
-    let mut clobbers = getClobbers();
+    let mut clobbers = StrBuf::from_str(getClobbers());
     if !ia.clobbers.get().is_empty() && !clobbers.is_empty() {
-        clobbers = format!("{},{}", ia.clobbers.get(), clobbers);
+        clobbers = StrBuf::from_owned_str(format!("{},{}",
+                                                  ia.clobbers.get(),
+                                                  clobbers));
     } else {
         clobbers.push_str(ia.clobbers.get());
     }
@@ -77,12 +81,12 @@ pub fn trans_inline_asm<'a>(bcx: &'a Block<'a>, ia: &ast::InlineAsm)
     // Add the clobbers to our constraints list
     if clobbers.len() != 0 && constraints.len() != 0 {
         constraints.push_char(',');
-        constraints.push_str(clobbers);
+        constraints.push_str(clobbers.as_slice());
     } else {
-        constraints.push_str(clobbers);
+        constraints.push_str(clobbers.as_slice());
     }
 
-    debug!("Asm Constraints: {:?}", constraints);
+    debug!("Asm Constraints: {:?}", constraints.as_slice());
 
     let num_outputs = outputs.len();
 
@@ -101,7 +105,7 @@ pub fn trans_inline_asm<'a>(bcx: &'a Block<'a>, ia: &ast::InlineAsm)
     };
 
     let r = ia.asm.get().with_c_str(|a| {
-        constraints.with_c_str(|c| {
+        constraints.as_slice().with_c_str(|c| {
             InlineAsmCall(bcx,
                           a,
                           c,
diff --git a/src/librustc/middle/trans/builder.rs b/src/librustc/middle/trans/builder.rs
index b7a18a275ca..7d99ac3e7f3 100644
--- a/src/librustc/middle/trans/builder.rs
+++ b/src/librustc/middle/trans/builder.rs
@@ -20,8 +20,8 @@ use middle::trans::common::*;
 use middle::trans::machine::llalign_of_pref;
 use middle::trans::type_::Type;
 use collections::HashMap;
-use std::vec::Vec;
 use libc::{c_uint, c_ulonglong, c_char};
+use std::strbuf::StrBuf;
 use syntax::codemap::Span;
 
 pub struct Builder<'a> {
@@ -69,7 +69,7 @@ impl<'a> Builder<'a> {
                 // Pass 2: concat strings for each elt, skipping
                 // forwards over any cycles by advancing to rightmost
                 // occurrence of each element in path.
-                let mut s = ~".";
+                let mut s = StrBuf::from_str(".");
                 i = 0u;
                 while i < len {
                     i = *mm.get(&v[i]);
@@ -81,7 +81,8 @@ impl<'a> Builder<'a> {
                 s.push_char('/');
                 s.push_str(category);
 
-                let n = match h.find(&s) {
+                let s = s.into_owned();
+                let n = match h.find_equiv(&s) {
                     Some(&n) => n,
                     _ => 0u
                 };
diff --git a/src/librustc/middle/trans/debuginfo.rs b/src/librustc/middle/trans/debuginfo.rs
index 8a7f30ee2c4..6719bba2492 100644
--- a/src/librustc/middle/trans/debuginfo.rs
+++ b/src/librustc/middle/trans/debuginfo.rs
@@ -147,8 +147,9 @@ use collections::HashMap;
 use collections::HashSet;
 use libc::{c_uint, c_ulonglong, c_longlong};
 use std::ptr;
-use std::sync::atomics;
 use std::slice;
+use std::strbuf::StrBuf;
+use std::sync::atomics;
 use syntax::codemap::{Span, Pos};
 use syntax::{abi, ast, codemap, ast_util, ast_map};
 use syntax::owned_slice::OwnedSlice;
@@ -678,7 +679,7 @@ pub fn create_function_debug_context(cx: &CrateContext,
     };
 
     // get_template_parameters() will append a `<...>` clause to the function name if necessary.
-    let mut function_name = token::get_ident(ident).get().to_str();
+    let mut function_name = StrBuf::from_str(token::get_ident(ident).get());
     let template_parameters = get_template_parameters(cx,
                                                       generics,
                                                       param_substs,
@@ -690,11 +691,12 @@ pub fn create_function_debug_context(cx: &CrateContext,
     // ast_map, or construct a path using the enclosing function).
     let (linkage_name, containing_scope) = if has_path {
         let namespace_node = namespace_for_item(cx, ast_util::local_def(fn_ast_id));
-        let linkage_name = namespace_node.mangled_name_of_contained_item(function_name);
+        let linkage_name = namespace_node.mangled_name_of_contained_item(
+            function_name.as_slice());
         let containing_scope = namespace_node.scope;
         (linkage_name, containing_scope)
     } else {
-        (function_name.clone(), file_metadata)
+        (function_name.as_slice().to_owned(), file_metadata)
     };
 
     // Clang sets this parameter to the opening brace of the function's block, so let's do this too.
@@ -702,7 +704,7 @@ pub fn create_function_debug_context(cx: &CrateContext,
 
     let is_local_to_unit = is_node_local_to_unit(cx, fn_ast_id);
 
-    let fn_metadata = function_name.with_c_str(|function_name| {
+    let fn_metadata = function_name.as_slice().with_c_str(|function_name| {
                           linkage_name.with_c_str(|linkage_name| {
             unsafe {
                 llvm::LLVMDIBuilderCreateFunction(
@@ -803,8 +805,8 @@ pub fn create_function_debug_context(cx: &CrateContext,
                                generics: &ast::Generics,
                                param_substs: Option<@param_substs>,
                                file_metadata: DIFile,
-                               name_to_append_suffix_to: &mut ~str)
-                            -> DIArray {
+                               name_to_append_suffix_to: &mut StrBuf)
+                               -> DIArray {
         let self_type = match param_substs {
             Some(param_substs) => param_substs.self_ty,
             _ => None
@@ -2779,7 +2781,7 @@ struct NamespaceTreeNode {
 
 impl NamespaceTreeNode {
     fn mangled_name_of_contained_item(&self, item_name: &str) -> ~str {
-        fn fill_nested(node: &NamespaceTreeNode, output: &mut ~str) {
+        fn fill_nested(node: &NamespaceTreeNode, output: &mut StrBuf) {
             match node.parent {
                 Some(parent) => fill_nested(parent, output),
                 None => {}
@@ -2789,12 +2791,12 @@ impl NamespaceTreeNode {
             output.push_str(string.get());
         }
 
-        let mut name = ~"_ZN";
+        let mut name = StrBuf::from_str("_ZN");
         fill_nested(self, &mut name);
         name.push_str(format!("{}", item_name.len()));
         name.push_str(item_name);
         name.push_char('E');
-        name
+        name.into_owned()
     }
 }
 
diff --git a/src/librustc/middle/typeck/infer/error_reporting.rs b/src/librustc/middle/typeck/infer/error_reporting.rs
index db66c93086a..4fd68e622bc 100644
--- a/src/librustc/middle/typeck/infer/error_reporting.rs
+++ b/src/librustc/middle/typeck/infer/error_reporting.rs
@@ -76,6 +76,7 @@ use middle::typeck::infer::region_inference::ProcessedErrors;
 use middle::typeck::infer::region_inference::SameRegions;
 use std::cell::{Cell, RefCell};
 use std::char::from_u32;
+use std::strbuf::StrBuf;
 use syntax::ast;
 use syntax::ast_map;
 use syntax::ast_util;
@@ -1361,13 +1362,13 @@ impl LifeGiver {
 
         // 0 .. 25 generates a .. z, 26 .. 51 generates aa .. zz, and so on
         fn num_to_str(counter: uint) -> ~str {
-            let mut s = ~"";
+            let mut s = StrBuf::new();
             let (n, r) = (counter/26 + 1, counter % 26);
             let letter: char = from_u32((r+97) as u32).unwrap();
             for _ in range(0, n) {
                 s.push_char(letter);
             }
-            return s;
+            s.into_owned()
         }
     }
 
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 155ceadf0d8..fec86b0bbe8 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -23,6 +23,7 @@ use middle::ty::{ty_uniq, ty_trait, ty_int, ty_uint, ty_infer};
 use middle::ty;
 use middle::typeck;
 
+use std::strbuf::StrBuf;
 use syntax::abi;
 use syntax::ast_map;
 use syntax::codemap::{Span, Pos};
@@ -258,9 +259,9 @@ pub fn ty_to_str(cx: &ctxt, typ: t) -> ~str {
                       sig: &ty::FnSig)
                       -> ~str {
         let mut s = if abi == abi::Rust {
-            ~""
+            StrBuf::new()
         } else {
-            format!("extern {} ", abi.to_str())
+            StrBuf::from_owned_str(format!("extern {} ", abi.to_str()))
         };
 
         match purity {
@@ -283,17 +284,18 @@ pub fn ty_to_str(cx: &ctxt, typ: t) -> ~str {
 
         push_sig_to_str(cx, &mut s, '(', ')', sig);
 
-        return s;
+        s.into_owned()
     }
+
     fn closure_to_str(cx: &ctxt, cty: &ty::ClosureTy) -> ~str {
         let is_proc =
             (cty.sigil, cty.onceness) == (ast::OwnedSigil, ast::Once);
         let is_borrowed_closure = cty.sigil == ast::BorrowedSigil;
 
         let mut s = if is_proc || is_borrowed_closure {
-            ~""
+            StrBuf::new()
         } else {
-            cty.sigil.to_str()
+            StrBuf::from_owned_str(cty.sigil.to_str())
         };
 
         match (cty.sigil, cty.region) {
@@ -349,10 +351,11 @@ pub fn ty_to_str(cx: &ctxt, typ: t) -> ~str {
             }
         }
 
-        return s;
+        s.into_owned()
     }
+
     fn push_sig_to_str(cx: &ctxt,
-                       s: &mut ~str,
+                       s: &mut StrBuf,
                        bra: char,
                        ket: char,
                        sig: &ty::FnSig) {
diff --git a/src/librustdoc/clean.rs b/src/librustdoc/clean.rs
index e92aec8e25c..6a189acab3a 100644
--- a/src/librustdoc/clean.rs
+++ b/src/librustdoc/clean.rs
@@ -24,12 +24,13 @@ use rustc::metadata::cstore;
 use rustc::metadata::csearch;
 use rustc::metadata::decoder;
 
+use std::local_data;
+use std::strbuf::StrBuf;
 use std;
 
 use core;
 use doctree;
 use visit_ast;
-use std::local_data;
 
 pub trait Clean<T> {
     fn clean(&self) -> T;
@@ -917,7 +918,7 @@ impl Clean<PathSegment> for ast::PathSegment {
 fn path_to_str(p: &ast::Path) -> ~str {
     use syntax::parse::token;
 
-    let mut s = ~"";
+    let mut s = StrBuf::new();
     let mut first = true;
     for i in p.segments.iter().map(|x| token::get_ident(x.identifier)) {
         if !first || p.global {
@@ -927,7 +928,7 @@ fn path_to_str(p: &ast::Path) -> ~str {
         }
         s.push_str(i.get());
     }
-    s
+    s.into_owned()
 }
 
 impl Clean<~str> for ast::Ident {
diff --git a/src/librustdoc/html/format.rs b/src/librustdoc/html/format.rs
index 10c155262c3..a762ccd97c2 100644
--- a/src/librustdoc/html/format.rs
+++ b/src/librustdoc/html/format.rs
@@ -16,8 +16,9 @@
 //! them in the future to instead emit any format desired.
 
 use std::fmt;
-use std::local_data;
 use std::io;
+use std::local_data;
+use std::strbuf::StrBuf;
 
 use syntax::ast;
 use syntax::ast_util;
@@ -185,7 +186,7 @@ fn path(w: &mut io::Writer, path: &clean::Path, print_all: bool,
     -> fmt::Result
 {
     // The generics will get written to both the title and link
-    let mut generics = ~"";
+    let mut generics = StrBuf::new();
     let last = path.segments.last().unwrap();
     if last.lifetimes.len() > 0 || last.types.len() > 0 {
         let mut counter = 0;
@@ -219,7 +220,7 @@ fn path(w: &mut io::Writer, path: &clean::Path, print_all: bool,
                 let amt = path.segments.len() - 1;
                 match rel_root {
                     Some(root) => {
-                        let mut root = root;
+                        let mut root = StrBuf::from_str(root);
                         for seg in path.segments.slice_to(amt).iter() {
                             if "super" == seg.name || "self" == seg.name {
                                 try!(write!(w, "{}::", seg.name));
@@ -228,7 +229,7 @@ fn path(w: &mut io::Writer, path: &clean::Path, print_all: bool,
                                 root.push_str("/");
                                 try!(write!(w, "<a class='mod'
                                                     href='{}index.html'>{}</a>::",
-                                              root,
+                                              root.as_slice(),
                                               seg.name));
                             }
                         }
@@ -244,7 +245,7 @@ fn path(w: &mut io::Writer, path: &clean::Path, print_all: bool,
             match info(&**cache) {
                 // This is a documented path, link to it!
                 Some((ref fqp, shortty)) if abs_root.is_some() => {
-                    let mut url = abs_root.unwrap();
+                    let mut url = StrBuf::from_str(abs_root.unwrap());
                     let to_link = fqp.slice_to(fqp.len() - 1);
                     for component in to_link.iter() {
                         url.push_str(*component);
@@ -271,7 +272,7 @@ fn path(w: &mut io::Writer, path: &clean::Path, print_all: bool,
                     try!(write!(w, "{}", last.name));
                 }
             }
-            try!(write!(w, "{}", generics));
+            try!(write!(w, "{}", generics.as_slice()));
             Ok(())
         })
     })
@@ -430,7 +431,7 @@ impl fmt::Show for clean::FnDecl {
 impl<'a> fmt::Show for Method<'a> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         let Method(selfty, d) = *self;
-        let mut args = ~"";
+        let mut args = StrBuf::new();
         match *selfty {
             clean::SelfStatic => {},
             clean::SelfValue => args.push_str("self"),
@@ -455,7 +456,8 @@ impl<'a> fmt::Show for Method<'a> {
             }
             args.push_str(format!("{}", input.type_));
         }
-        write!(f.buf, "({args}){arrow, select, yes{ -&gt; {ret}} other{}}",
+        write!(f.buf,
+               "({args}){arrow, select, yes{ -&gt; {ret}} other{}}",
                args = args,
                arrow = match d.output { clean::Unit => "no", _ => "yes" },
                ret = d.output)
diff --git a/src/librustdoc/html/render.rs b/src/librustdoc/html/render.rs
index 3ed4ece514a..0fde87af900 100644
--- a/src/librustdoc/html/render.rs
+++ b/src/librustdoc/html/render.rs
@@ -33,13 +33,14 @@
 //! These tasks are not parallelized (they haven't been a bottleneck yet), and
 //! both occur before the crate is rendered.
 
+use collections::{HashMap, HashSet};
 use std::fmt;
-use std::local_data;
-use std::io;
 use std::io::{fs, File, BufferedWriter, MemWriter, BufferedReader};
-use std::str;
+use std::io;
+use std::local_data;
 use std::slice;
-use collections::{HashMap, HashSet};
+use std::str;
+use std::strbuf::StrBuf;
 
 use sync::Arc;
 use serialize::json::ToJson;
@@ -71,7 +72,7 @@ pub struct Context {
     pub current: Vec<~str> ,
     /// String representation of how to get back to the root path of the 'doc/'
     /// folder in terms of a relative URL.
-    pub root_path: ~str,
+    pub root_path: StrBuf,
     /// The current destination folder of where HTML artifacts should be placed.
     /// This changes as the context descends into the module hierarchy.
     pub dst: Path,
@@ -209,7 +210,7 @@ pub fn run(mut krate: clean::Crate, dst: Path) -> io::IoResult<()> {
     let mut cx = Context {
         dst: dst,
         current: Vec::new(),
-        root_path: ~"",
+        root_path: StrBuf::new(),
         sidebar: HashMap::new(),
         layout: layout::Layout {
             logo: ~"",
@@ -498,7 +499,7 @@ impl<'a> SourceCollector<'a> {
 
         // Create the intermediate directories
         let mut cur = self.dst.clone();
-        let mut root_path = ~"../../";
+        let mut root_path = StrBuf::from_str("../../");
         clean_srcpath(p.dirname(), |component| {
             cur.push(component);
             mkdir(&cur).unwrap();
@@ -512,7 +513,7 @@ impl<'a> SourceCollector<'a> {
         let page = layout::Page {
             title: title,
             ty: "source",
-            root_path: root_path,
+            root_path: root_path.as_slice(),
         };
         try!(layout::render(&mut w as &mut Writer, &self.cx.layout,
                               &page, &(""), &Source(contents)));
@@ -813,16 +814,18 @@ impl Context {
             // does make formatting *a lot* nicer.
             local_data::set(current_location_key, cx.current.clone());
 
-            let mut title = cx.current.connect("::");
+            let mut title = StrBuf::from_str(cx.current.connect("::"));
             if pushname {
-                if title.len() > 0 { title.push_str("::"); }
+                if title.len() > 0 {
+                    title.push_str("::");
+                }
                 title.push_str(*it.name.get_ref());
             }
             title.push_str(" - Rust");
             let page = layout::Page {
                 ty: shortty(it),
-                root_path: cx.root_path,
-                title: title,
+                root_path: cx.root_path.as_slice(),
+                title: title.as_slice(),
             };
 
             markdown::reset_headers();
@@ -955,7 +958,7 @@ impl<'a> fmt::Show for Item<'a> {
         let cur = self.cx.current.as_slice();
         let amt = if self.ismodule() { cur.len() - 1 } else { cur.len() };
         for (i, component) in cur.iter().enumerate().take(amt) {
-            let mut trail = ~"";
+            let mut trail = StrBuf::new();
             for _ in range(0, cur.len() - i - 1) {
                 trail.push_str("../");
             }
@@ -989,10 +992,10 @@ fn item_path(item: &clean::Item) -> ~str {
 }
 
 fn full_path(cx: &Context, item: &clean::Item) -> ~str {
-    let mut s = cx.current.connect("::");
+    let mut s = StrBuf::from_str(cx.current.connect("::"));
     s.push_str("::");
     s.push_str(item.name.get_ref().as_slice());
-    return s;
+    return s.into_owned();
 }
 
 fn blank<'a>(s: Option<&'a str>) -> &'a str {
@@ -1190,7 +1193,7 @@ fn item_function(w: &mut Writer, it: &clean::Item,
 
 fn item_trait(w: &mut Writer, it: &clean::Item,
               t: &clean::Trait) -> fmt::Result {
-    let mut parents = ~"";
+    let mut parents = StrBuf::new();
     if t.parents.len() > 0 {
         parents.push_str(": ");
         for (i, p) in t.parents.iter().enumerate() {
@@ -1664,7 +1667,9 @@ impl<'a> fmt::Show for Sidebar<'a> {
                 try!(write!(fmt.buf, "&\\#8203;::"));
             }
             try!(write!(fmt.buf, "<a href='{}index.html'>{}</a>",
-                          cx.root_path.slice_to((cx.current.len() - i - 1) * 3),
+                          cx.root_path
+                            .as_slice()
+                            .slice_to((cx.current.len() - i - 1) * 3),
                           *name));
         }
         try!(write!(fmt.buf, "</p>"));
diff --git a/src/librustdoc/html/toc.rs b/src/librustdoc/html/toc.rs
index afb7f559a80..128cabe16de 100644
--- a/src/librustdoc/html/toc.rs
+++ b/src/librustdoc/html/toc.rs
@@ -11,6 +11,7 @@
 //! Table-of-contents creation.
 
 use std::fmt;
+use std::strbuf::StrBuf;
 
 /// A (recursive) table of contents
 #[deriving(Eq)]
@@ -136,11 +137,11 @@ impl TocBuilder {
         {
             let (toc_level, toc) = match self.chain.last() {
                 None => {
-                    sec_number = ~"";
+                    sec_number = StrBuf::new();
                     (0, &self.top_level)
                 }
                 Some(entry) => {
-                    sec_number = entry.sec_number.clone();
+                    sec_number = StrBuf::from_str(entry.sec_number.clone());
                     sec_number.push_str(".");
                     (entry.level, &entry.children)
                 }
@@ -156,12 +157,12 @@ impl TocBuilder {
         }
 
         self.chain.push(TocEntry {
-                level: level,
-                name: name,
-                sec_number: sec_number,
-                id: id,
-                children: Toc { entries: Vec::new() }
-            });
+            level: level,
+            name: name,
+            sec_number: sec_number.into_owned(),
+            id: id,
+            children: Toc { entries: Vec::new() }
+        });
 
         // get the thing we just pushed, so we can borrow the string
         // out of it with the right lifetime
diff --git a/src/librustdoc/markdown.rs b/src/librustdoc/markdown.rs
index be912798442..983478a4de2 100644
--- a/src/librustdoc/markdown.rs
+++ b/src/librustdoc/markdown.rs
@@ -8,9 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::{str, io};
-
 use collections::HashSet;
+use std::{str, io};
+use std::strbuf::StrBuf;
 
 use getopts;
 use testing;
@@ -62,12 +62,12 @@ fn extract_leading_metadata<'a>(s: &'a str) -> (Vec<&'a str>, &'a str) {
 }
 
 fn load_external_files(names: &[~str]) -> Option<~str> {
-    let mut out = ~"";
+    let mut out = StrBuf::new();
     for name in names.iter() {
         out.push_str(load_or_return!(name.as_slice(), None, None));
         out.push_char('\n');
     }
-    Some(out)
+    Some(out.into_owned())
 }
 
 /// Render `input` (e.g. "foo.md") into an HTML file in `output`
@@ -77,7 +77,7 @@ pub fn render(input: &str, mut output: Path, matches: &getopts::Matches) -> int
     output.push(input_p.filestem().unwrap());
     output.set_extension("html");
 
-    let mut css = ~"";
+    let mut css = StrBuf::new();
     for name in matches.opt_strs("markdown-css").iter() {
         let s = format!("<link rel=\"stylesheet\" type=\"text/css\" href=\"{}\">\n", name);
         css.push_str(s)
diff --git a/src/librustdoc/passes.rs b/src/librustdoc/passes.rs
index 429b4590261..3f45b1a7e69 100644
--- a/src/librustdoc/passes.rs
+++ b/src/librustdoc/passes.rs
@@ -8,12 +8,13 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::cmp;
 use collections::HashSet;
+use rustc::util::nodemap::NodeSet;
+use std::cmp;
 use std::local_data;
+use std::strbuf::StrBuf;
 use std::uint;
 use syntax::ast;
-use rustc::util::nodemap::NodeSet;
 
 use clean;
 use clean::Item;
@@ -235,7 +236,7 @@ pub fn collapse_docs(krate: clean::Crate) -> plugins::PluginResult {
     struct Collapser;
     impl fold::DocFolder for Collapser {
         fn fold_item(&mut self, i: Item) -> Option<Item> {
-            let mut docstr = ~"";
+            let mut docstr = StrBuf::new();
             let mut i = i;
             for attr in i.attrs.iter() {
                 match *attr {
@@ -250,8 +251,8 @@ pub fn collapse_docs(krate: clean::Crate) -> plugins::PluginResult {
                 &clean::NameValue(ref x, _) if "doc" == *x => false,
                 _ => true
             }).map(|x| x.clone()).collect();
-            if "" != docstr {
-                a.push(clean::NameValue(~"doc", docstr));
+            if docstr.len() > 0 {
+                a.push(clean::NameValue(~"doc", docstr.into_owned()));
             }
             i.attrs = a;
             self.fold_item_recur(i)
diff --git a/src/librustdoc/plugins.rs b/src/librustdoc/plugins.rs
index f3a82fead5a..234796c5c3f 100644
--- a/src/librustdoc/plugins.rs
+++ b/src/librustdoc/plugins.rs
@@ -10,8 +10,9 @@
 
 use clean;
 
-use serialize::json;
 use dl = std::unstable::dynamic_lib;
+use serialize::json;
+use std::strbuf::StrBuf;
 
 pub type PluginJson = Option<(~str, json::Json)>;
 pub type PluginResult = (clean::Crate, PluginJson);
@@ -70,21 +71,23 @@ impl PluginManager {
 }
 
 #[cfg(target_os="win32")]
-fn libname(mut n: ~str) -> ~str {
+fn libname(n: ~str) -> ~str {
+    let mut n = StrBuf::from_owned_str(n);
     n.push_str(".dll");
-    n
+    n.into_owned()
 }
 
 #[cfg(target_os="macos")]
-fn libname(mut n: ~str) -> ~str {
+fn libname(n: ~str) -> ~str {
+    let mut n = StrBuf::from_owned_str(n);
     n.push_str(".dylib");
-    n
+    n.into_owned()
 }
 
 #[cfg(not(target_os="win32"), not(target_os="macos"))]
 fn libname(n: ~str) -> ~str {
-    let mut i = ~"lib";
+    let mut i = StrBuf::from_str("lib");
     i.push_str(n);
     i.push_str(".so");
-    i
+    i.into_owned()
 }
diff --git a/src/librustdoc/test.rs b/src/librustdoc/test.rs
index 06b57780abe..ad49f41f64a 100644
--- a/src/librustdoc/test.rs
+++ b/src/librustdoc/test.rs
@@ -15,6 +15,7 @@ use std::io::{Process, TempDir};
 use std::local_data;
 use std::os;
 use std::str;
+use std::strbuf::StrBuf;
 
 use collections::HashSet;
 use testing;
@@ -167,10 +168,10 @@ fn runtest(test: &str, cratename: &str, libs: HashSet<Path>, should_fail: bool,
 }
 
 fn maketest(s: &str, cratename: &str, loose_feature_gating: bool) -> ~str {
-    let mut prog = ~r"
-#![deny(warnings)]
-#![allow(unused_variable, dead_assignment, unused_mut, attribute_usage, dead_code)]
-";
+    let mut prog = StrBuf::from_str(r"
+#![deny(warnings)];
+#![allow(unused_variable, dead_assignment, unused_mut, attribute_usage, dead_code)];
+");
 
     if loose_feature_gating {
         // FIXME #12773: avoid inserting these when the tutorial & manual
@@ -191,7 +192,7 @@ fn maketest(s: &str, cratename: &str, loose_feature_gating: bool) -> ~str {
         prog.push_str("\n}");
     }
 
-    return prog;
+    return prog.into_owned();
 }
 
 pub struct Collector {
diff --git a/src/libsemver/lib.rs b/src/libsemver/lib.rs
index 2663d627e51..23d437b0594 100644
--- a/src/libsemver/lib.rs
+++ b/src/libsemver/lib.rs
@@ -42,6 +42,7 @@ use std::cmp;
 use std::fmt;
 use std::fmt::Show;
 use std::option::{Option, Some, None};
+use std::strbuf::StrBuf;
 
 /// An identifier in the pre-release or build metadata. If the identifier can
 /// be parsed as a decimal value, it will be represented with `Numeric`.
@@ -158,7 +159,7 @@ impl cmp::Ord for Version {
 
 fn take_nonempty_prefix<T:Iterator<char>>(rdr: &mut T, pred: |char| -> bool)
                         -> (~str, Option<char>) {
-    let mut buf = ~"";
+    let mut buf = StrBuf::new();
     let mut ch = rdr.next();
     loop {
         match ch {
@@ -170,7 +171,7 @@ fn take_nonempty_prefix<T:Iterator<char>>(rdr: &mut T, pred: |char| -> bool)
             }
         }
     }
-    (buf, ch)
+    (buf.into_owned(), ch)
 }
 
 fn take_num<T: Iterator<char>>(rdr: &mut T) -> Option<(uint, Option<char>)> {
diff --git a/src/libserialize/json.rs b/src/libserialize/json.rs
index aff4b07f755..6c980f2f834 100644
--- a/src/libserialize/json.rs
+++ b/src/libserialize/json.rs
@@ -231,14 +231,15 @@ fn main() {
 
 */
 
+use collections::HashMap;
 use std::char;
 use std::f64;
-use collections::HashMap;
-use std::io;
+use std::fmt;
 use std::io::MemWriter;
+use std::io;
 use std::num;
 use std::str;
-use std::fmt;
+use std::strbuf::StrBuf;
 
 use Encodable;
 use collections::TreeMap;
@@ -271,7 +272,7 @@ pub type EncodeResult = io::IoResult<()>;
 pub type DecodeResult<T> = Result<T, Error>;
 
 fn escape_str(s: &str) -> ~str {
-    let mut escaped = ~"\"";
+    let mut escaped = StrBuf::from_str("\"");
     for c in s.chars() {
         match c {
           '"' => escaped.push_str("\\\""),
@@ -284,16 +285,16 @@ fn escape_str(s: &str) -> ~str {
           _ => escaped.push_char(c),
         }
     };
-
     escaped.push_char('"');
-
-    escaped
+    escaped.into_owned()
 }
 
 fn spaces(n: uint) -> ~str {
-    let mut ss = ~"";
-    for _ in range(0, n) { ss.push_str(" "); }
-    return ss;
+    let mut ss = StrBuf::new();
+    for _ in range(0, n) {
+        ss.push_str(" ");
+    }
+    return ss.into_owned();
 }
 
 /// A structure for implementing serialization to JSON.
@@ -1130,7 +1131,7 @@ impl<T : Iterator<char>> Parser<T> {
 
     fn parse_str(&mut self) -> DecodeResult<~str> {
         let mut escape = false;
-        let mut res = ~"";
+        let mut res = StrBuf::new();
 
         loop {
             self.bump();
@@ -1184,7 +1185,10 @@ impl<T : Iterator<char>> Parser<T> {
                 escape = true;
             } else {
                 match self.ch {
-                    Some('"') => { self.bump(); return Ok(res); },
+                    Some('"') => {
+                        self.bump();
+                        return Ok(res.into_owned());
+                    },
                     Some(c) => res.push_char(c),
                     None => unreachable!()
                 }
diff --git a/src/libstd/char.rs b/src/libstd/char.rs
index 46447e4a416..702dbcca8be 100644
--- a/src/libstd/char.rs
+++ b/src/libstd/char.rs
@@ -30,7 +30,8 @@ use iter::{Iterator, range_step};
 use str::StrSlice;
 use unicode::{derived_property, property, general_category, decompose, conversions};
 
-#[cfg(test)] use str::OwnedStr;
+#[cfg(test)] use str::Str;
+#[cfg(test)] use strbuf::StrBuf;
 
 #[cfg(not(test))] use cmp::{Eq, Ord};
 #[cfg(not(test))] use default::Default;
@@ -747,9 +748,9 @@ fn test_is_digit() {
 #[test]
 fn test_escape_default() {
     fn string(c: char) -> ~str {
-        let mut result = ~"";
+        let mut result = StrBuf::new();
         escape_default(c, |c| { result.push_char(c); });
-        return result;
+        return result.into_owned();
     }
     assert_eq!(string('\n'), ~"\\n");
     assert_eq!(string('\r'), ~"\\r");
@@ -769,9 +770,9 @@ fn test_escape_default() {
 #[test]
 fn test_escape_unicode() {
     fn string(c: char) -> ~str {
-        let mut result = ~"";
+        let mut result = StrBuf::new();
         escape_unicode(c, |c| { result.push_char(c); });
-        return result;
+        return result.into_owned();
     }
     assert_eq!(string('\x00'), ~"\\x00");
     assert_eq!(string('\n'), ~"\\x0a");
diff --git a/src/libstd/hash/sip.rs b/src/libstd/hash/sip.rs
index 6217ff0f58c..69b35df50e4 100644
--- a/src/libstd/hash/sip.rs
+++ b/src/libstd/hash/sip.rs
@@ -292,6 +292,7 @@ mod tests {
     use num::ToStrRadix;
     use option::{Some, None};
     use str::{Str, OwnedStr};
+    use strbuf::StrBuf;
     use slice::{Vector, ImmutableVector, OwnedVector};
     use self::test::BenchHarness;
 
@@ -387,11 +388,11 @@ mod tests {
         let mut state_full = SipState::new_with_keys(k0, k1);
 
         fn to_hex_str(r: &[u8, ..8]) -> ~str {
-            let mut s = ~"";
+            let mut s = StrBuf::new();
             for b in r.iter() {
                 s.push_str((*b as uint).to_str_radix(16u));
             }
-            s
+            s.into_owned()
         }
 
         fn result_bytes(h: u64) -> ~[u8] {
@@ -408,11 +409,11 @@ mod tests {
 
         fn result_str(h: u64) -> ~str {
             let r = result_bytes(h);
-            let mut s = ~"";
+            let mut s = StrBuf::new();
             for b in r.iter() {
                 s.push_str((*b as uint).to_str_radix(16u));
             }
-            s
+            s.into_owned()
         }
 
         while t < 64 {
diff --git a/src/libstd/lib.rs b/src/libstd/lib.rs
index 985f8a8eb0a..9325a0ad112 100644
--- a/src/libstd/lib.rs
+++ b/src/libstd/lib.rs
@@ -128,6 +128,7 @@ pub mod tuple;
 pub mod slice;
 pub mod vec;
 pub mod str;
+pub mod strbuf;
 
 pub mod ascii;
 
diff --git a/src/libstd/path/windows.rs b/src/libstd/path/windows.rs
index ca9b351210d..57dae68b842 100644
--- a/src/libstd/path/windows.rs
+++ b/src/libstd/path/windows.rs
@@ -20,9 +20,10 @@ use from_str::FromStr;
 use io::Writer;
 use iter::{AdditiveIterator, DoubleEndedIterator, Extendable, Rev, Iterator, Map};
 use option::{Option, Some, None};
-use str;
-use str::{CharSplits, OwnedStr, Str, StrVector, StrSlice};
 use slice::{Vector, OwnedVector, ImmutableVector};
+use str::{CharSplits, OwnedStr, Str, StrVector, StrSlice};
+use str;
+use strbuf::StrBuf;
 use super::{contains_nul, BytesContainer, GenericPath, GenericPathUnsafe};
 
 /// Iterator that yields successive components of a Path as &str
@@ -175,7 +176,7 @@ impl GenericPathUnsafe for Path {
         let filename = filename.container_as_str().unwrap();
         match self.sepidx_or_prefix_len() {
             None if ".." == self.repr => {
-                let mut s = str::with_capacity(3 + filename.len());
+                let mut s = StrBuf::with_capacity(3 + filename.len());
                 s.push_str("..");
                 s.push_char(SEP);
                 s.push_str(filename);
@@ -185,20 +186,20 @@ impl GenericPathUnsafe for Path {
                 self.update_normalized(filename);
             }
             Some((_,idxa,end)) if self.repr.slice(idxa,end) == ".." => {
-                let mut s = str::with_capacity(end + 1 + filename.len());
+                let mut s = StrBuf::with_capacity(end + 1 + filename.len());
                 s.push_str(self.repr.slice_to(end));
                 s.push_char(SEP);
                 s.push_str(filename);
                 self.update_normalized(s);
             }
             Some((idxb,idxa,_)) if self.prefix == Some(DiskPrefix) && idxa == self.prefix_len() => {
-                let mut s = str::with_capacity(idxb + filename.len());
+                let mut s = StrBuf::with_capacity(idxb + filename.len());
                 s.push_str(self.repr.slice_to(idxb));
                 s.push_str(filename);
                 self.update_normalized(s);
             }
             Some((idxb,_,_)) => {
-                let mut s = str::with_capacity(idxb + 1 + filename.len());
+                let mut s = StrBuf::with_capacity(idxb + 1 + filename.len());
                 s.push_str(self.repr.slice_to(idxb));
                 s.push_char(SEP);
                 s.push_str(filename);
@@ -252,7 +253,7 @@ impl GenericPathUnsafe for Path {
             let path_ = if is_verbatim(me) { Path::normalize__(path, None) }
                         else { None };
             let pathlen = path_.as_ref().map_or(path.len(), |p| p.len());
-            let mut s = str::with_capacity(me.repr.len() + 1 + pathlen);
+            let mut s = StrBuf::with_capacity(me.repr.len() + 1 + pathlen);
             s.push_str(me.repr);
             let plen = me.prefix_len();
             // if me is "C:" we don't want to add a path separator
@@ -699,9 +700,9 @@ impl Path {
             match prefix {
                 Some(VerbatimUNCPrefix(x, 0)) if s.len() == 8 + x => {
                     // the server component has no trailing '\'
-                    let mut s = s.into_owned();
+                    let mut s = StrBuf::from_owned_str(s.into_owned());
                     s.push_char(SEP);
-                    Some(s)
+                    Some(s.into_owned())
                 }
                 _ => None
             }
@@ -764,7 +765,7 @@ impl Path {
                         let n = prefix_.len() +
                                 if is_abs { comps.len() } else { comps.len() - 1} +
                                 comps.iter().map(|v| v.len()).sum();
-                        let mut s = str::with_capacity(n);
+                        let mut s = StrBuf::with_capacity(n);
                         match prefix {
                             Some(DiskPrefix) => {
                                 s.push_char(prefix_[0].to_ascii().to_upper().to_char());
@@ -795,7 +796,7 @@ impl Path {
                             s.push_char(SEP);
                             s.push_str(comp);
                         }
-                        Some(s)
+                        Some(s.into_owned())
                     }
                 }
             }
diff --git a/src/libstd/prelude.rs b/src/libstd/prelude.rs
index 0a4b32f5a89..b7bcbefa468 100644
--- a/src/libstd/prelude.rs
+++ b/src/libstd/prelude.rs
@@ -59,6 +59,7 @@ pub use slice::{ImmutableEqVector, ImmutableTotalOrdVector, ImmutableCloneableVe
 pub use slice::{OwnedVector, OwnedCloneableVector, OwnedEqVector};
 pub use slice::{MutableVector, MutableTotalOrdVector};
 pub use slice::{Vector, VectorVector, CloneableVector, ImmutableVector};
+pub use strbuf::StrBuf;
 pub use vec::Vec;
 
 // Reexported runtime types
diff --git a/src/libstd/str.rs b/src/libstd/str.rs
index e24011ca021..525988c698f 100644
--- a/src/libstd/str.rs
+++ b/src/libstd/str.rs
@@ -60,13 +60,6 @@ to that string. With these guarantees, strings can easily transition between
 being mutable/immutable with the same benefits of having mutable strings in
 other languages.
 
-```rust
-let mut buf = ~"testing";
-buf.push_char(' ');
-buf.push_str("123");
-assert_eq!(buf, ~"testing 123");
- ```
-
 # Representation
 
 Rust's string type, `str`, is a sequence of unicode codepoints encoded as a
@@ -97,7 +90,6 @@ use libc;
 use num::Saturating;
 use option::{None, Option, Some};
 use ptr;
-use ptr::RawPtr;
 use from_str::FromStr;
 use slice;
 use slice::{OwnedVector, OwnedCloneableVector, ImmutableVector, MutableVector};
@@ -105,6 +97,7 @@ use slice::{Vector};
 use vec::Vec;
 use default::Default;
 use raw::Repr;
+use strbuf::StrBuf;
 
 /*
 Section: Creating a string
@@ -149,9 +142,9 @@ pub fn from_byte(b: u8) -> ~str {
 
 /// Convert a char to a string
 pub fn from_char(ch: char) -> ~str {
-    let mut buf = ~"";
+    let mut buf = StrBuf::new();
     buf.push_char(ch);
-    buf
+    buf.into_owned()
 }
 
 /// Convert a vector of chars to a string
@@ -159,11 +152,6 @@ pub fn from_chars(chs: &[char]) -> ~str {
     chs.iter().map(|c| *c).collect()
 }
 
-#[doc(hidden)]
-pub fn push_str(lhs: &mut ~str, rhs: &str) {
-    lhs.push_str(rhs)
-}
-
 /// Methods for vectors of strings
 pub trait StrVector {
     /// Concatenate a vector of strings.
@@ -180,12 +168,13 @@ impl<'a, S: Str> StrVector for &'a [S] {
         // `len` calculation may overflow but push_str but will check boundaries
         let len = self.iter().map(|s| s.as_slice().len()).sum();
 
-        let mut result = with_capacity(len);
+        let mut result = StrBuf::with_capacity(len);
 
         for s in self.iter() {
             result.push_str(s.as_slice())
         }
-        result
+
+        result.into_owned()
     }
 
     fn connect(&self, sep: &str) -> ~str {
@@ -198,7 +187,7 @@ impl<'a, S: Str> StrVector for &'a [S] {
         // `len` calculation may overflow but push_str but will check boundaries
         let len = sep.len() * (self.len() - 1)
             + self.iter().map(|s| s.as_slice().len()).sum();
-        let mut result = with_capacity(len);
+        let mut result = StrBuf::with_capacity(len);
         let mut first = true;
 
         for s in self.iter() {
@@ -209,7 +198,7 @@ impl<'a, S: Str> StrVector for &'a [S] {
             }
             result.push_str(s.as_slice());
         }
-        result
+        result.into_owned()
     }
 }
 
@@ -675,7 +664,7 @@ impl<'a> Iterator<char> for Normalizations<'a> {
 ///
 /// The original string with all occurances of `from` replaced with `to`
 pub fn replace(s: &str, from: &str, to: &str) -> ~str {
-    let mut result = ~"";
+    let mut result = StrBuf::new();
     let mut last_end = 0;
     for (start, end) in s.match_indices(from) {
         result.push_str(unsafe{raw::slice_bytes(s, last_end, start)});
@@ -683,7 +672,7 @@ pub fn replace(s: &str, from: &str, to: &str) -> ~str {
         last_end = end;
     }
     result.push_str(unsafe{raw::slice_bytes(s, last_end, s.len())});
-    result
+    result.into_owned()
 }
 
 /*
@@ -992,14 +981,14 @@ pub fn truncate_utf16_at_nul<'a>(v: &'a [u16]) -> &'a [u16] {
 /// assert_eq!(str::from_utf16(v), None);
 /// ```
 pub fn from_utf16(v: &[u16]) -> Option<~str> {
-    let mut s = with_capacity(v.len() / 2);
+    let mut s = StrBuf::with_capacity(v.len() / 2);
     for c in utf16_items(v) {
         match c {
             ScalarValue(c) => s.push_char(c),
             LoneSurrogate(_) => return None
         }
     }
-    Some(s)
+    Some(s.into_owned())
 }
 
 /// Decode a UTF-16 encoded vector `v` into a string, replacing
@@ -1021,15 +1010,6 @@ pub fn from_utf16_lossy(v: &[u16]) -> ~str {
     utf16_items(v).map(|c| c.to_char_lossy()).collect()
 }
 
-/// Allocates a new string with the specified capacity. The string returned is
-/// the empty string, but has capacity for much more.
-#[inline]
-pub fn with_capacity(capacity: uint) -> ~str {
-    unsafe {
-        cast::transmute(slice::with_capacity::<~[u8]>(capacity))
-    }
-}
-
 // https://tools.ietf.org/html/rfc3629
 static UTF8_CHAR_WIDTH: [u8, ..256] = [
 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
@@ -1109,10 +1089,13 @@ pub fn from_utf8_lossy<'a>(v: &'a [u8]) -> MaybeOwned<'a> {
             unsafe_get(xs, i)
         }
     }
-    let mut res = with_capacity(total);
+
+    let mut res = StrBuf::with_capacity(total);
 
     if i > 0 {
-        unsafe { raw::push_bytes(&mut res, v.slice_to(i)) };
+        unsafe {
+            res.push_bytes(v.slice_to(i))
+        };
     }
 
     // subseqidx is the index of the first byte of the subsequence we're looking at.
@@ -1128,10 +1111,10 @@ pub fn from_utf8_lossy<'a>(v: &'a [u8]) -> MaybeOwned<'a> {
         macro_rules! error(() => ({
             unsafe {
                 if subseqidx != i_ {
-                    raw::push_bytes(&mut res, v.slice(subseqidx, i_));
+                    res.push_bytes(v.slice(subseqidx, i_));
                 }
                 subseqidx = i;
-                raw::push_bytes(&mut res, REPLACEMENT);
+                res.push_bytes(REPLACEMENT);
             }
         }))
 
@@ -1196,9 +1179,11 @@ pub fn from_utf8_lossy<'a>(v: &'a [u8]) -> MaybeOwned<'a> {
         }
     }
     if subseqidx < total {
-        unsafe { raw::push_bytes(&mut res, v.slice(subseqidx, total)) };
+        unsafe {
+            res.push_bytes(v.slice(subseqidx, total))
+        };
     }
-    Owned(res)
+    Owned(res.into_owned())
 }
 
 /*
@@ -1354,7 +1339,6 @@ pub mod raw {
     use libc;
     use ptr;
     use ptr::RawPtr;
-    use option::{Option, Some, None};
     use str::{is_utf8, OwnedStr, StrSlice};
     use slice;
     use slice::{MutableVector, ImmutableVector, OwnedVector};
@@ -1448,48 +1432,6 @@ pub mod raw {
             })
     }
 
-    /// Appends a byte to a string.
-    /// The caller must preserve the valid UTF-8 property.
-    #[inline]
-    pub unsafe fn push_byte(s: &mut ~str, b: u8) {
-        as_owned_vec(s).push(b)
-    }
-
-    /// Appends a vector of bytes to a string.
-    /// The caller must preserve the valid UTF-8 property.
-    #[inline]
-    pub unsafe fn push_bytes(s: &mut ~str, bytes: &[u8]) {
-        slice::bytes::push_bytes(as_owned_vec(s), bytes);
-    }
-
-    /// Removes the last byte from a string and returns it.
-    /// Returns None when an empty string is passed.
-    /// The caller must preserve the valid UTF-8 property.
-    pub unsafe fn pop_byte(s: &mut ~str) -> Option<u8> {
-        let len = s.len();
-        if len == 0u {
-            return None;
-        } else {
-            let b = s[len - 1u];
-            s.set_len(len - 1);
-            return Some(b);
-        }
-    }
-
-    /// Removes the first byte from a string and returns it.
-    /// Returns None when an empty string is passed.
-    /// The caller must preserve the valid UTF-8 property.
-    pub unsafe fn shift_byte(s: &mut ~str) -> Option<u8> {
-        let len = s.len();
-        if len == 0u {
-            return None;
-        } else {
-            let b = s[0];
-            *s = s.slice(1, len).to_owned();
-            return Some(b);
-        }
-    }
-
     /// Access the str in its vector representation.
     /// The caller must preserve the valid UTF-8 property when modifying.
     #[inline]
@@ -1525,14 +1467,15 @@ pub mod traits {
     use iter::Iterator;
     use ops::Add;
     use option::{Some, None};
-    use str::{Str, StrSlice, OwnedStr, eq_slice};
+    use str::{Str, StrSlice, eq_slice};
+    use strbuf::StrBuf;
 
     impl<'a> Add<&'a str,~str> for &'a str {
         #[inline]
         fn add(&self, rhs: & &'a str) -> ~str {
-            let mut ret = self.to_owned();
+            let mut ret = StrBuf::from_owned_str(self.to_owned());
             ret.push_str(*rhs);
-            ret
+            ret.into_owned()
         }
     }
 
@@ -1605,8 +1548,20 @@ pub trait Str {
     /// Work with `self` as a slice.
     fn as_slice<'a>(&'a self) -> &'a str;
 
-    /// Convert `self` into a ~str, not making a copy if possible
+    /// Convert `self` into a ~str, not making a copy if possible.
     fn into_owned(self) -> ~str;
+
+    /// Convert `self` into a `StrBuf`.
+    #[inline]
+    fn to_strbuf(&self) -> StrBuf {
+        StrBuf::from_str(self.as_slice())
+    }
+
+    /// Convert `self` into a `StrBuf`, not making a copy if possible.
+    #[inline]
+    fn into_strbuf(self) -> StrBuf {
+        StrBuf::from_owned_str(self.into_owned())
+    }
 }
 
 impl<'a> Str for &'a str {
@@ -2519,19 +2474,19 @@ impl<'a> StrSlice<'a> for &'a str {
     }
 
     fn escape_default(&self) -> ~str {
-        let mut out = with_capacity(self.len());
+        let mut out = StrBuf::with_capacity(self.len());
         for c in self.chars() {
             c.escape_default(|c| out.push_char(c));
         }
-        out
+        out.into_owned()
     }
 
     fn escape_unicode(&self) -> ~str {
-        let mut out = with_capacity(self.len());
+        let mut out = StrBuf::with_capacity(self.len());
         for c in self.chars() {
             c.escape_unicode(|c| out.push_char(c));
         }
-        out
+        out.into_owned()
     }
 
     #[inline]
@@ -2574,7 +2529,7 @@ impl<'a> StrSlice<'a> for &'a str {
     }
 
     fn replace(&self, from: &str, to: &str) -> ~str {
-        let mut result = ~"";
+        let mut result = StrBuf::new();
         let mut last_end = 0;
         for (start, end) in self.match_indices(from) {
             result.push_str(unsafe{raw::slice_bytes(*self, last_end, start)});
@@ -2582,7 +2537,7 @@ impl<'a> StrSlice<'a> for &'a str {
             last_end = end;
         }
         result.push_str(unsafe{raw::slice_bytes(*self, last_end, self.len())});
-        result
+        result.into_owned()
     }
 
     #[inline]
@@ -2727,11 +2682,11 @@ impl<'a> StrSlice<'a> for &'a str {
     }
 
     fn repeat(&self, nn: uint) -> ~str {
-        let mut ret = with_capacity(nn * self.len());
+        let mut ret = StrBuf::with_capacity(nn * self.len());
         for _ in range(0, nn) {
             ret.push_str(*self);
         }
-        ret
+        ret.into_owned()
     }
 
     #[inline]
@@ -2796,75 +2751,6 @@ impl<'a> StrSlice<'a> for &'a str {
 
 /// Methods for owned strings
 pub trait OwnedStr {
-    /// Appends a string slice to the back of a string, without overallocating.
-    fn push_str_no_overallocate(&mut self, rhs: &str);
-
-    /// Appends a string slice to the back of a string
-    fn push_str(&mut self, rhs: &str);
-
-    /// Appends a character to the back of a string
-    fn push_char(&mut self, c: char);
-
-    /// Remove the final character from a string and return it. Return None
-    /// when the string is empty.
-    fn pop_char(&mut self) -> Option<char>;
-
-    /// Remove the first character from a string and return it. Return None
-    /// when the string is empty.
-    fn shift_char(&mut self) -> Option<char>;
-
-    /// Prepend a char to a string
-    fn unshift_char(&mut self, ch: char);
-
-    /// Insert a new sub-string at the given position in a string, in O(n + m) time
-    /// (with n and m the lengths of the string and the substring.)
-    /// This fails if `position` is not at a character boundary.
-    fn insert(&mut self, position: uint, substring: &str);
-
-    /// Insert a char at the given position in a string, in O(n + m) time
-    /// (with n and m the lengths of the string and the substring.)
-    /// This fails if `position` is not at a character boundary.
-    fn insert_char(&mut self, position: uint, ch: char);
-
-    /// Concatenate two strings together.
-    fn append(self, rhs: &str) -> ~str;
-
-    /// Reserves capacity for exactly `n` bytes in the given string.
-    ///
-    /// Assuming single-byte characters, the resulting string will be large
-    /// enough to hold a string of length `n`.
-    ///
-    /// If the capacity for `s` is already equal to or greater than the requested
-    /// capacity, then no action is taken.
-    ///
-    /// # Arguments
-    ///
-    /// * s - A string
-    /// * n - The number of bytes to reserve space for
-    fn reserve_exact(&mut self, n: uint);
-
-    /// Reserves capacity for at least `n` bytes in the given string.
-    ///
-    /// Assuming single-byte characters, the resulting string will be large
-    /// enough to hold a string of length `n`.
-    ///
-    /// This function will over-allocate in order to amortize the allocation costs
-    /// in scenarios where the caller may need to repeatedly reserve additional
-    /// space.
-    ///
-    /// If the capacity for `s` is already equal to or greater than the requested
-    /// capacity, then no action is taken.
-    ///
-    /// # Arguments
-    ///
-    /// * s - A string
-    /// * n - The number of bytes to reserve space for
-    fn reserve(&mut self, n: uint);
-
-    /// Returns the number of single-byte characters the string can hold without
-    /// reallocating
-    fn capacity(&self) -> uint;
-
     /// Shorten a string to the specified length (which must be <= the current length)
     fn truncate(&mut self, len: uint);
 
@@ -2879,120 +2765,13 @@ pub trait OwnedStr {
     /// modifying its buffers, so it is up to the caller to ensure that
     /// the string is actually the specified size.
     unsafe fn set_len(&mut self, new_len: uint);
+
+    /// Pushes the given string onto this string, returning the concatenation of the two strings.
+    fn append(self, rhs: &str) -> ~str;
 }
 
 impl OwnedStr for ~str {
     #[inline]
-    fn push_str_no_overallocate(&mut self, rhs: &str) {
-        let new_cap = self.len() + rhs.len();
-        self.reserve_exact(new_cap);
-        self.push_str(rhs);
-    }
-
-    #[inline]
-    fn push_str(&mut self, rhs: &str) {
-        unsafe {
-            raw::push_bytes(self, rhs.as_bytes());
-        }
-    }
-
-    #[inline]
-    fn push_char(&mut self, c: char) {
-        let cur_len = self.len();
-        // may use up to 4 bytes.
-        unsafe {
-            let v = raw::as_owned_vec(self);
-            v.reserve_additional(4);
-
-            // Attempt to not use an intermediate buffer by just pushing bytes
-            // directly onto this string.
-            let write_ptr = v.as_mut_ptr().offset(cur_len as int);
-            let used = slice::raw::mut_buf_as_slice(write_ptr, 4, |slc| c.encode_utf8(slc));
-
-            v.set_len(cur_len + used);
-        }
-    }
-
-    #[inline]
-    fn pop_char(&mut self) -> Option<char> {
-        let end = self.len();
-        if end == 0u {
-            return None;
-        } else {
-            let CharRange {ch, next} = self.char_range_at_reverse(end);
-            unsafe { self.set_len(next); }
-            return Some(ch);
-        }
-    }
-
-    #[inline]
-    fn shift_char(&mut self) -> Option<char> {
-        if self.is_empty() {
-            return None;
-        } else {
-            let CharRange {ch, next} = self.char_range_at(0u);
-            *self = self.slice(next, self.len()).to_owned();
-            return Some(ch);
-        }
-    }
-
-    #[inline]
-    fn unshift_char(&mut self, ch: char) {
-        // This could be more efficient.
-        let mut new_str = ~"";
-        new_str.push_char(ch);
-        new_str.push_str(*self);
-        *self = new_str;
-    }
-
-    #[inline]
-    fn insert(&mut self, position: uint, substring: &str) {
-        // This could be more efficient.
-        let mut new_str = self.slice_to(position).to_owned();
-        new_str.push_str(substring);
-        new_str.push_str(self.slice_from(position));
-        *self = new_str;
-    }
-
-    #[inline]
-    fn insert_char(&mut self, position: uint, ch: char) {
-        // This could be more efficient.
-        let mut new_str = self.slice_to(position).to_owned();
-        new_str.push_char(ch);
-        new_str.push_str(self.slice_from(position));
-        *self = new_str;
-    }
-
-    #[inline]
-    fn append(self, rhs: &str) -> ~str {
-        let mut new_str = self;
-        new_str.push_str_no_overallocate(rhs);
-        new_str
-    }
-
-    #[inline]
-    fn reserve_exact(&mut self, n: uint) {
-        unsafe {
-            raw::as_owned_vec(self).reserve_exact(n)
-        }
-    }
-
-    #[inline]
-    fn reserve(&mut self, n: uint) {
-        unsafe {
-            raw::as_owned_vec(self).reserve(n)
-        }
-    }
-
-    #[inline]
-    fn capacity(&self) -> uint {
-        unsafe {
-            let buf: &~[u8] = cast::transmute(self);
-            buf.capacity()
-        }
-    }
-
-    #[inline]
     fn truncate(&mut self, len: uint) {
         assert!(len <= self.len());
         assert!(self.is_char_boundary(len));
@@ -3008,6 +2787,13 @@ impl OwnedStr for ~str {
     unsafe fn set_len(&mut self, new_len: uint) {
         raw::as_owned_vec(self).set_len(new_len)
     }
+
+    #[inline]
+    fn append(self, rhs: &str) -> ~str {
+        let mut new_str = StrBuf::from_owned_str(self);
+        new_str.push_str(rhs);
+        new_str.into_owned()
+    }
 }
 
 impl Clone for ~str {
@@ -3021,21 +2807,9 @@ impl FromIterator<char> for ~str {
     #[inline]
     fn from_iter<T: Iterator<char>>(iterator: T) -> ~str {
         let (lower, _) = iterator.size_hint();
-        let mut buf = with_capacity(lower);
+        let mut buf = StrBuf::with_capacity(lower);
         buf.extend(iterator);
-        buf
-    }
-}
-
-impl Extendable<char> for ~str {
-    #[inline]
-    fn extend<T: Iterator<char>>(&mut self, mut iterator: T) {
-        let (lower, _) = iterator.size_hint();
-        let reserve = lower + self.len();
-        self.reserve(reserve);
-        for ch in iterator {
-            self.push_char(ch)
-        }
+        buf.into_owned()
     }
 }
 
@@ -3054,6 +2828,7 @@ mod tests {
     use default::Default;
     use prelude::*;
     use str::*;
+    use strbuf::StrBuf;
 
     #[test]
     fn test_eq() {
@@ -3118,92 +2893,6 @@ mod tests {
     }
 
     #[test]
-    fn test_push_str() {
-        let mut s = ~"";
-        s.push_str("");
-        assert_eq!(s.slice_from(0), "");
-        s.push_str("abc");
-        assert_eq!(s.slice_from(0), "abc");
-        s.push_str("ประเทศไทย中华Việt Nam");
-        assert_eq!(s.slice_from(0), "abcประเทศไทย中华Việt Nam");
-    }
-
-    #[test]
-    fn test_append() {
-        let mut s = ~"";
-        s = s.append("");
-        assert_eq!(s.slice_from(0), "");
-        s = s.append("abc");
-        assert_eq!(s.slice_from(0), "abc");
-        s = s.append("ประเทศไทย中华Việt Nam");
-        assert_eq!(s.slice_from(0), "abcประเทศไทย中华Việt Nam");
-    }
-
-    #[test]
-    fn test_pop_char() {
-        let mut data = ~"ประเทศไทย中华";
-        let cc = data.pop_char();
-        assert_eq!(~"ประเทศไทย中", data);
-        assert_eq!(Some('华'), cc);
-    }
-
-    #[test]
-    fn test_pop_char_2() {
-        let mut data2 = ~"华";
-        let cc2 = data2.pop_char();
-        assert_eq!(~"", data2);
-        assert_eq!(Some('华'), cc2);
-    }
-
-    #[test]
-    fn test_pop_char_empty() {
-        let mut data = ~"";
-        let cc3 = data.pop_char();
-        assert_eq!(~"", data);
-        assert_eq!(None, cc3);
-    }
-
-    #[test]
-    fn test_push_char() {
-        let mut data = ~"ประเทศไทย中";
-        data.push_char('华');
-        data.push_char('b'); // 1 byte
-        data.push_char('¢'); // 2 byte
-        data.push_char('€'); // 3 byte
-        data.push_char('𤭢'); // 4 byte
-        assert_eq!(~"ประเทศไทย中华b¢€𤭢", data);
-    }
-
-    #[test]
-    fn test_shift_char() {
-        let mut data = ~"ประเทศไทย中";
-        let cc = data.shift_char();
-        assert_eq!(~"ระเทศไทย中", data);
-        assert_eq!(Some('ป'), cc);
-    }
-
-    #[test]
-    fn test_unshift_char() {
-        let mut data = ~"ประเทศไทย中";
-        data.unshift_char('华');
-        assert_eq!(~"华ประเทศไทย中", data);
-    }
-
-    #[test]
-    fn test_insert_char() {
-        let mut data = ~"ประเทศไทย中";
-        data.insert_char(15, '华');
-        assert_eq!(~"ประเท华ศไทย中", data);
-    }
-
-    #[test]
-    fn test_insert() {
-        let mut data = ~"ประเทศไทย中";
-        data.insert(15, "华中");
-        assert_eq!(~"ประเท华中ศไทย中", data);
-    }
-
-    #[test]
     fn test_collect() {
         let empty = ~"";
         let s: ~str = empty.chars().collect();
@@ -3214,28 +2903,6 @@ mod tests {
     }
 
     #[test]
-    fn test_extend() {
-        let data = ~"ประเทศไทย中";
-        let mut cpy = data.clone();
-        let other = "abc";
-        let it = other.chars();
-        cpy.extend(it);
-        assert_eq!(cpy, data + other);
-    }
-
-    #[test]
-    fn test_clear() {
-        let mut empty = ~"";
-        empty.clear();
-        assert_eq!("", empty.as_slice());
-        let mut data = ~"ประเทศไทย中";
-        data.clear();
-        assert_eq!("", data.as_slice());
-        data.push_char('华');
-        assert_eq!("华", data.as_slice());
-    }
-
-    #[test]
     fn test_into_bytes() {
         let data = ~"asdf";
         let buf = data.into_bytes();
@@ -3346,15 +3013,21 @@ mod tests {
         assert_eq!("", unsafe {raw::slice_bytes("abc", 1, 1)});
         fn a_million_letter_a() -> ~str {
             let mut i = 0;
-            let mut rs = ~"";
-            while i < 100000 { rs.push_str("aaaaaaaaaa"); i += 1; }
-            rs
+            let mut rs = StrBuf::new();
+            while i < 100000 {
+                rs.push_str("aaaaaaaaaa");
+                i += 1;
+            }
+            rs.into_owned()
         }
         fn half_a_million_letter_a() -> ~str {
             let mut i = 0;
-            let mut rs = ~"";
-            while i < 100000 { rs.push_str("aaaaa"); i += 1; }
-            rs
+            let mut rs = StrBuf::new();
+            while i < 100000 {
+                rs.push_str("aaaaa");
+                i += 1;
+            }
+            rs.into_owned()
         }
         let letters = a_million_letter_a();
         assert!(half_a_million_letter_a() ==
@@ -3455,18 +3128,21 @@ mod tests {
 
         fn a_million_letter_X() -> ~str {
             let mut i = 0;
-            let mut rs = ~"";
+            let mut rs = StrBuf::new();
             while i < 100000 {
-                push_str(&mut rs, "华华华华华华华华华华");
+                rs.push_str("华华华华华华华华华华");
                 i += 1;
             }
-            rs
+            rs.into_owned()
         }
         fn half_a_million_letter_X() -> ~str {
             let mut i = 0;
-            let mut rs = ~"";
-            while i < 100000 { push_str(&mut rs, "华华华华华"); i += 1; }
-            rs
+            let mut rs = StrBuf::new();
+            while i < 100000 {
+                rs.push_str("华华华华华");
+                i += 1;
+            }
+            rs.into_owned()
         }
         let letters = a_million_letter_X();
         assert!(half_a_million_letter_X() ==
@@ -3609,29 +3285,6 @@ mod tests {
     }
 
     #[test]
-    fn test_push_byte() {
-        let mut s = ~"ABC";
-        unsafe{raw::push_byte(&mut s, 'D' as u8)};
-        assert_eq!(s, ~"ABCD");
-    }
-
-    #[test]
-    fn test_shift_byte() {
-        let mut s = ~"ABC";
-        let b = unsafe{raw::shift_byte(&mut s)};
-        assert_eq!(s, ~"BC");
-        assert_eq!(b, Some(65u8));
-    }
-
-    #[test]
-    fn test_pop_byte() {
-        let mut s = ~"ABC";
-        let b = unsafe{raw::pop_byte(&mut s)};
-        assert_eq!(s, ~"AB");
-        assert_eq!(b, Some(67u8));
-    }
-
-    #[test]
     fn test_is_utf8() {
         // deny overlong encodings
         assert!(!is_utf8([0xc0, 0x80]));
@@ -4324,38 +3977,6 @@ mod tests {
     }
 
     #[test]
-    fn test_str_truncate() {
-        let mut s = ~"12345";
-        s.truncate(5);
-        assert_eq!(s.as_slice(), "12345");
-        s.truncate(3);
-        assert_eq!(s.as_slice(), "123");
-        s.truncate(0);
-        assert_eq!(s.as_slice(), "");
-
-        let mut s = ~"12345";
-        let p = s.as_ptr();
-        s.truncate(3);
-        s.push_str("6");
-        let p_ = s.as_ptr();
-        assert_eq!(p_, p);
-    }
-
-    #[test]
-    #[should_fail]
-    fn test_str_truncate_invalid_len() {
-        let mut s = ~"12345";
-        s.truncate(6);
-    }
-
-    #[test]
-    #[should_fail]
-    fn test_str_truncate_split_codepoint() {
-        let mut s = ~"\u00FC"; // ü
-        s.truncate(1);
-    }
-
-    #[test]
     fn test_str_from_utf8() {
         let xs = bytes!("hello");
         assert_eq!(from_utf8(xs), Some("hello"));
@@ -4658,22 +4279,6 @@ mod bench {
     }
 
     #[bench]
-    fn bench_with_capacity(bh: &mut BenchHarness) {
-        bh.iter(|| {
-            with_capacity(100)
-        });
-    }
-
-    #[bench]
-    fn bench_push_str(bh: &mut BenchHarness) {
-        let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
-        bh.iter(|| {
-            let mut r = ~"";
-            r.push_str(s);
-        });
-    }
-
-    #[bench]
     fn bench_connect(bh: &mut BenchHarness) {
         let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
         let sep = "→";
diff --git a/src/libstd/strbuf.rs b/src/libstd/strbuf.rs
new file mode 100644
index 00000000000..e9e50f0a07a
--- /dev/null
+++ b/src/libstd/strbuf.rs
@@ -0,0 +1,355 @@
+// Copyright 2014 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.
+
+//! An owned, growable string that enforces that its contents are valid UTF-8.
+
+use c_vec::CVec;
+use cast;
+use char::Char;
+use container::Container;
+use fmt;
+use io::Writer;
+use iter::{Extendable, FromIterator, Iterator, range};
+use option::{None, Option, Some};
+use ptr::RawPtr;
+use slice::{OwnedVector, Vector};
+use str::{OwnedStr, Str, StrSlice};
+use vec::Vec;
+
+#[deriving(Clone, Eq, Ord, TotalEq, TotalOrd)]
+pub struct StrBuf {
+    vec: Vec<u8>,
+}
+
+impl StrBuf {
+    /// Creates a new string buffer initalized with the empty string.
+    #[inline]
+    pub fn new() -> StrBuf {
+        StrBuf {
+            vec: Vec::new(),
+        }
+    }
+
+    /// Creates a new string buffer with the given capacity.
+    #[inline]
+    pub fn with_capacity(capacity: uint) -> StrBuf {
+        StrBuf {
+            vec: Vec::with_capacity(capacity),
+        }
+    }
+
+    /// Creates a new string buffer from length, capacity, and a pointer.
+    #[inline]
+    pub unsafe fn from_raw_parts(length: uint, capacity: uint, ptr: *mut u8) -> StrBuf {
+        StrBuf {
+            vec: Vec::from_raw_parts(length, capacity, ptr),
+        }
+    }
+
+    /// Creates a new string buffer from the given string.
+    #[inline]
+    pub fn from_str(string: &str) -> StrBuf {
+        StrBuf {
+            vec: Vec::from_slice(string.as_bytes())
+        }
+    }
+
+    /// Creates a new string buffer from the given owned string, taking care not to copy it.
+    #[inline]
+    pub fn from_owned_str(string: ~str) -> StrBuf {
+        StrBuf {
+            vec: string.into_bytes().move_iter().collect(),
+        }
+    }
+
+    /// Pushes the given string onto this buffer; then, returns `self` so that it can be used
+    /// again.
+    #[inline]
+    pub fn append(mut self, second: &str) -> StrBuf {
+        self.push_str(second);
+        self
+    }
+
+    /// Creates a string buffer by repeating a character `length` times.
+    #[inline]
+    pub fn from_char(length: uint, ch: char) -> StrBuf {
+        if length == 0 {
+            return StrBuf::new()
+        }
+
+        let mut buf = StrBuf::new();
+        buf.push_char(ch);
+        let size = buf.len() * length;
+        buf.reserve(size);
+        for _ in range(1, length) {
+            buf.push_char(ch)
+        }
+        buf
+    }
+
+    /// Pushes the given string onto this string buffer.
+    #[inline]
+    pub fn push_str(&mut self, string: &str) {
+        self.vec.push_all(string.as_bytes())
+    }
+
+    #[inline]
+    pub fn grow(&mut self, count: uint, ch: char) {
+        for _ in range(0, count) {
+            self.push_char(ch)
+        }
+    }
+
+    /// Returns the number of bytes that this string buffer can hold without reallocating.
+    #[inline]
+    pub fn byte_capacity(&self) -> uint {
+        self.vec.capacity()
+    }
+
+    /// Reserves capacity for at least `extra` additional bytes in this string buffer.
+    #[inline]
+    pub fn reserve_additional(&mut self, extra: uint) {
+        self.vec.reserve_additional(extra)
+    }
+
+    /// Reserves capacity for at least `capacity` bytes in this string buffer.
+    #[inline]
+    pub fn reserve(&mut self, capacity: uint) {
+        self.vec.reserve(capacity)
+    }
+
+    /// Reserves capacity for exactly `capacity` bytes in this string buffer.
+    #[inline]
+    pub fn reserve_exact(&mut self, capacity: uint) {
+        self.vec.reserve_exact(capacity)
+    }
+
+    /// Shrinks the capacity of this string buffer to match its length.
+    #[inline]
+    pub fn shrink_to_fit(&mut self) {
+        self.vec.shrink_to_fit()
+    }
+
+    /// Adds the given character to the end of the string.
+    #[inline]
+    pub fn push_char(&mut self, ch: char) {
+        let cur_len = self.len();
+        unsafe {
+            // This may use up to 4 bytes.
+            self.vec.reserve_additional(4);
+
+            // Attempt to not use an intermediate buffer by just pushing bytes
+            // directly onto this string.
+            let mut c_vector = CVec::new(self.vec.as_mut_ptr().offset(cur_len as int), 4);
+            let used = ch.encode_utf8(c_vector.as_mut_slice());
+            self.vec.set_len(cur_len + used);
+        }
+    }
+
+    /// Pushes the given bytes onto this string buffer. This is unsafe because it does not check
+    /// to ensure that the resulting string will be valid UTF-8.
+    #[inline]
+    pub unsafe fn push_bytes(&mut self, bytes: &[u8]) {
+        self.vec.push_all(bytes)
+    }
+
+    /// Works with the underlying buffer as a byte slice.
+    #[inline]
+    pub fn as_bytes<'a>(&'a self) -> &'a [u8] {
+        self.vec.as_slice()
+    }
+
+    /// Shorten a string to the specified length (which must be <= the current length)
+    #[inline]
+    pub fn truncate(&mut self, len: uint) {
+        assert!(self.as_slice().is_char_boundary(len));
+        self.vec.truncate(len)
+    }
+
+    /// Appends a byte to this string buffer. The caller must preserve the valid UTF-8 property.
+    #[inline]
+    pub unsafe fn push_byte(&mut self, byte: u8) {
+        self.push_bytes([byte])
+    }
+
+    /// Removes the last byte from the string buffer and returns it. Returns `None` if this string
+    /// buffer is empty.
+    ///
+    /// The caller must preserve the valid UTF-8 property.
+    #[inline]
+    pub unsafe fn pop_byte(&mut self) -> Option<u8> {
+        let len = self.len();
+        if len == 0 {
+            return None
+        }
+
+        let byte = self.as_slice()[len - 1];
+        self.vec.set_len(len - 1);
+        Some(byte)
+    }
+
+    /// Removes the first byte from the string buffer and returns it. Returns `None` if this string
+    /// buffer is empty.
+    ///
+    /// The caller must preserve the valid UTF-8 property.
+    pub unsafe fn shift_byte(&mut self) -> Option<u8> {
+        let len = self.len();
+        if len == 0 {
+            return None
+        }
+
+        let byte = self.as_slice()[0];
+        *self = self.as_slice().slice(1, len).into_strbuf();
+        Some(byte)
+    }
+}
+
+impl Container for StrBuf {
+    #[inline]
+    fn len(&self) -> uint {
+        self.vec.len()
+    }
+}
+
+impl FromIterator<char> for StrBuf {
+    fn from_iter<I:Iterator<char>>(iterator: I) -> StrBuf {
+        let mut buf = StrBuf::new();
+        buf.extend(iterator);
+        buf
+    }
+}
+
+impl Extendable<char> for StrBuf {
+    fn extend<I:Iterator<char>>(&mut self, mut iterator: I) {
+        for ch in iterator {
+            self.push_char(ch)
+        }
+    }
+}
+
+impl Str for StrBuf {
+    #[inline]
+    fn as_slice<'a>(&'a self) -> &'a str {
+        unsafe {
+            cast::transmute(self.vec.as_slice())
+        }
+    }
+
+    #[inline]
+    fn into_owned(self) -> ~str {
+        let StrBuf {
+            vec: vec
+        } = self;
+        unsafe {
+            cast::transmute::<~[u8],~str>(vec.move_iter().collect())
+        }
+    }
+}
+
+impl fmt::Show for StrBuf {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        self.as_slice().fmt(f)
+    }
+}
+
+impl<H:Writer> ::hash::Hash<H> for StrBuf {
+    #[inline]
+    fn hash(&self, hasher: &mut H) {
+        self.as_slice().hash(hasher)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    extern crate test;
+    use self::test::BenchHarness;
+    use str::{Str, StrSlice};
+    use super::StrBuf;
+
+    #[bench]
+    fn bench_with_capacity(bh: &mut BenchHarness) {
+        bh.iter(|| {
+            StrBuf::with_capacity(100)
+        });
+    }
+
+    #[bench]
+    fn bench_push_str(bh: &mut BenchHarness) {
+        let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
+        bh.iter(|| {
+            let mut r = StrBuf::new();
+            r.push_str(s);
+        });
+    }
+
+    #[test]
+    fn test_push_bytes() {
+        let mut s = StrBuf::from_str("ABC");
+        unsafe {
+            s.push_bytes([ 'D' as u8 ]);
+        }
+        assert_eq!(s.as_slice(), "ABCD");
+    }
+
+    #[test]
+    fn test_push_str() {
+        let mut s = StrBuf::new();
+        s.push_str("");
+        assert_eq!(s.as_slice().slice_from(0), "");
+        s.push_str("abc");
+        assert_eq!(s.as_slice().slice_from(0), "abc");
+        s.push_str("ประเทศไทย中华Việt Nam");
+        assert_eq!(s.as_slice().slice_from(0), "abcประเทศไทย中华Việt Nam");
+    }
+
+    #[test]
+    fn test_push_char() {
+        let mut data = StrBuf::from_str("ประเทศไทย中");
+        data.push_char('华');
+        data.push_char('b'); // 1 byte
+        data.push_char('¢'); // 2 byte
+        data.push_char('€'); // 3 byte
+        data.push_char('𤭢'); // 4 byte
+        assert_eq!(data.as_slice(), "ประเทศไทย中华b¢€𤭢");
+    }
+
+    #[test]
+    fn test_str_truncate() {
+        let mut s = StrBuf::from_str("12345");
+        s.truncate(5);
+        assert_eq!(s.as_slice(), "12345");
+        s.truncate(3);
+        assert_eq!(s.as_slice(), "123");
+        s.truncate(0);
+        assert_eq!(s.as_slice(), "");
+
+        let mut s = StrBuf::from_str("12345");
+        let p = s.as_slice().as_ptr();
+        s.truncate(3);
+        s.push_str("6");
+        let p_ = s.as_slice().as_ptr();
+        assert_eq!(p_, p);
+    }
+
+    #[test]
+    #[should_fail]
+    fn test_str_truncate_invalid_len() {
+        let mut s = StrBuf::from_str("12345");
+        s.truncate(6);
+    }
+
+    #[test]
+    #[should_fail]
+    fn test_str_truncate_split_codepoint() {
+        let mut s = StrBuf::from_str("\u00FC"); // ü
+        s.truncate(1);
+    }
+}
+
diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs
index 3c5cdfcf94e..da0e0d73fed 100644
--- a/src/libstd/vec.rs
+++ b/src/libstd/vec.rs
@@ -7,6 +7,7 @@
 // <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.
+
 //! An owned, growable vector.
 
 use cast::{forget, transmute};
@@ -28,7 +29,7 @@ use ptr;
 use rt::global_heap::{malloc_raw, realloc_raw};
 use raw::Slice;
 use slice::{ImmutableEqVector, ImmutableVector, Items, MutItems, MutableVector};
-use slice::{MutableTotalOrdVector, Vector};
+use slice::{MutableTotalOrdVector, OwnedVector, Vector};
 
 /// An owned, growable vector.
 ///
diff --git a/src/libsyntax/ast_map.rs b/src/libsyntax/ast_map.rs
index cf584ff62ac..4c7803f022a 100644
--- a/src/libsyntax/ast_map.rs
+++ b/src/libsyntax/ast_map.rs
@@ -19,9 +19,10 @@ use print::pprust;
 use util::small_vector::SmallVector;
 
 use std::cell::RefCell;
+use std::fmt;
 use std::iter;
 use std::slice;
-use std::fmt;
+use std::strbuf::StrBuf;
 
 #[deriving(Clone, Eq)]
 pub enum PathElem {
@@ -81,14 +82,14 @@ pub type PathElems<'a, 'b> = iter::Chain<Values<'a, PathElem>, LinkedPath<'b>>;
 pub fn path_to_str<PI: Iterator<PathElem>>(mut path: PI) -> ~str {
     let itr = token::get_ident_interner();
 
-    path.fold(~"", |mut s, e| {
+    path.fold(StrBuf::new(), |mut s, e| {
         let e = itr.get(e.name());
         if !s.is_empty() {
             s.push_str("::");
         }
         s.push_str(e.as_slice());
         s
-    })
+    }).into_owned()
 }
 
 #[deriving(Clone)]
diff --git a/src/libsyntax/ast_util.rs b/src/libsyntax/ast_util.rs
index ec9c02ac82a..cf82b9642de 100644
--- a/src/libsyntax/ast_util.rs
+++ b/src/libsyntax/ast_util.rs
@@ -21,6 +21,7 @@ use visit;
 
 use std::cell::Cell;
 use std::cmp;
+use std::strbuf::StrBuf;
 use std::u32;
 
 pub fn path_name_i(idents: &[Ident]) -> ~str {
@@ -235,7 +236,7 @@ pub fn unguarded_pat(a: &Arm) -> Option<Vec<@Pat> > {
 /// listed as `__extensions__::method_name::hash`, with no indication
 /// of the type).
 pub fn impl_pretty_name(trait_ref: &Option<TraitRef>, ty: &Ty) -> Ident {
-    let mut pretty = pprust::ty_to_str(ty);
+    let mut pretty = StrBuf::from_owned_str(pprust::ty_to_str(ty));
     match *trait_ref {
         Some(ref trait_ref) => {
             pretty.push_char('.');
@@ -243,7 +244,7 @@ pub fn impl_pretty_name(trait_ref: &Option<TraitRef>, ty: &Ty) -> Ident {
         }
         None => {}
     }
-    token::gensym_ident(pretty)
+    token::gensym_ident(pretty.as_slice())
 }
 
 pub fn public_methods(ms: Vec<@Method> ) -> Vec<@Method> {
diff --git a/src/libsyntax/codemap.rs b/src/libsyntax/codemap.rs
index 7cadce54765..b174dffdfec 100644
--- a/src/libsyntax/codemap.rs
+++ b/src/libsyntax/codemap.rs
@@ -21,9 +21,10 @@ source code snippets, etc.
 
 */
 
+use serialize::{Encodable, Decodable, Encoder, Decoder};
 use std::cell::RefCell;
 use std::rc::Rc;
-use serialize::{Encodable, Decodable, Encoder, Decoder};
+use std::strbuf::StrBuf;
 
 pub trait Pos {
     fn from_uint(n: uint) -> Self;
@@ -305,22 +306,22 @@ impl CodeMap {
         // FIXME #12884: no efficient/safe way to remove from the start of a string
         // and reuse the allocation.
         let mut src = if src.starts_with("\ufeff") {
-            src.as_slice().slice_from(3).into_owned()
+            StrBuf::from_str(src.as_slice().slice_from(3))
         } else {
-            src
+            StrBuf::from_owned_str(src)
         };
 
         // Append '\n' in case it's not already there.
         // This is a workaround to prevent CodeMap.lookup_filemap_idx from accidentally
         // overflowing into the next filemap in case the last byte of span is also the last
         // byte of filemap, which leads to incorrect results from CodeMap.span_to_*.
-        if src.len() > 0 && !src.ends_with("\n") {
+        if src.len() > 0 && !src.as_slice().ends_with("\n") {
             src.push_char('\n');
         }
 
         let filemap = Rc::new(FileMap {
             name: filename,
-            src: src,
+            src: src.into_owned(),
             start_pos: Pos::from_uint(start_pos),
             lines: RefCell::new(Vec::new()),
             multibyte_chars: RefCell::new(Vec::new()),
diff --git a/src/libsyntax/diagnostic.rs b/src/libsyntax/diagnostic.rs
index b11c99d1a70..e63f2960421 100644
--- a/src/libsyntax/diagnostic.rs
+++ b/src/libsyntax/diagnostic.rs
@@ -17,6 +17,7 @@ use std::cell::{RefCell, Cell};
 use std::fmt;
 use std::io;
 use std::iter::range;
+use std::strbuf::StrBuf;
 use term;
 
 // maximum number of lines we will print for each error; arbitrary.
@@ -368,11 +369,13 @@ fn highlight_lines(err: &mut EmitterWriter,
 
         // indent past |name:## | and the 0-offset column location
         let left = fm.name.len() + digits + lo.col.to_uint() + 3u;
-        let mut s = ~"";
+        let mut s = StrBuf::new();
         // Skip is the number of characters we need to skip because they are
         // part of the 'filename:line ' part of the previous line.
         let skip = fm.name.len() + digits + 3u;
-        for _ in range(0, skip) { s.push_char(' '); }
+        for _ in range(0, skip) {
+            s.push_char(' ');
+        }
         let orig = fm.get_line(*lines.lines.get(0) as int);
         for pos in range(0u, left-skip) {
             let cur_char = orig[pos] as char;
@@ -386,14 +389,16 @@ fn highlight_lines(err: &mut EmitterWriter,
             };
         }
         try!(write!(&mut err.dst, "{}", s));
-        let mut s = ~"^";
+        let mut s = StrBuf::from_str("^");
         let hi = cm.lookup_char_pos(sp.hi);
         if hi.col != lo.col {
             // the ^ already takes up one space
             let num_squigglies = hi.col.to_uint()-lo.col.to_uint()-1u;
-            for _ in range(0, num_squigglies) { s.push_char('~'); }
+            for _ in range(0, num_squigglies) {
+                s.push_char('~');
+            }
         }
-        try!(print_maybe_styled(err, s + "\n",
+        try!(print_maybe_styled(err, s.into_owned() + "\n",
                                 term::attr::ForegroundColor(lvl.color())));
     }
     Ok(())
@@ -409,7 +414,8 @@ fn custom_highlight_lines(w: &mut EmitterWriter,
                           cm: &codemap::CodeMap,
                           sp: Span,
                           lvl: Level,
-                          lines: codemap::FileLines) -> io::IoResult<()> {
+                          lines: codemap::FileLines)
+                          -> io::IoResult<()> {
     let fm = &*lines.file;
 
     let lines = lines.lines.as_slice();
@@ -430,15 +436,21 @@ fn custom_highlight_lines(w: &mut EmitterWriter,
     let hi = cm.lookup_char_pos(sp.hi);
     // Span seems to use half-opened interval, so subtract 1
     let skip = last_line_start.len() + hi.col.to_uint() - 1;
-    let mut s = ~"";
-    for _ in range(0, skip) { s.push_char(' '); }
+    let mut s = StrBuf::new();
+    for _ in range(0, skip) {
+        s.push_char(' ');
+    }
     s.push_char('^');
-    print_maybe_styled(w, s + "\n", term::attr::ForegroundColor(lvl.color()))
+    s.push_char('\n');
+    print_maybe_styled(w,
+                       s.into_owned(),
+                       term::attr::ForegroundColor(lvl.color()))
 }
 
 fn print_macro_backtrace(w: &mut EmitterWriter,
                          cm: &codemap::CodeMap,
-                         sp: Span) -> io::IoResult<()> {
+                         sp: Span)
+                         -> io::IoResult<()> {
     for ei in sp.expn_info.iter() {
         let ss = ei.callee.span.as_ref().map_or(~"", |span| cm.span_to_str(*span));
         let (pre, post) = match ei.callee.format {
diff --git a/src/libsyntax/ext/concat.rs b/src/libsyntax/ext/concat.rs
index e638291ecfa..1db65e3b9e4 100644
--- a/src/libsyntax/ext/concat.rs
+++ b/src/libsyntax/ext/concat.rs
@@ -8,14 +8,15 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::char;
-
 use ast;
 use codemap;
 use ext::base;
 use ext::build::AstBuilder;
 use parse::token;
 
+use std::char;
+use std::strbuf::StrBuf;
+
 pub fn expand_syntax_ext(cx: &mut base::ExtCtxt,
                          sp: codemap::Span,
                          tts: &[ast::TokenTree]) -> base::MacResult {
@@ -23,7 +24,7 @@ pub fn expand_syntax_ext(cx: &mut base::ExtCtxt,
         Some(e) => e,
         None => return base::MacResult::dummy_expr(sp)
     };
-    let mut accumulator = ~"";
+    let mut accumulator = StrBuf::new();
     for e in es.move_iter() {
         match e.node {
             ast::ExprLit(lit) => {
@@ -56,5 +57,7 @@ pub fn expand_syntax_ext(cx: &mut base::ExtCtxt,
             }
         }
     }
-    base::MRExpr(cx.expr_str(sp, token::intern_and_get_ident(accumulator)))
+    base::MRExpr(cx.expr_str(
+            sp,
+            token::intern_and_get_ident(accumulator.into_owned())))
 }
diff --git a/src/libsyntax/ext/concat_idents.rs b/src/libsyntax/ext/concat_idents.rs
index 8441fa719ea..a5faa693982 100644
--- a/src/libsyntax/ext/concat_idents.rs
+++ b/src/libsyntax/ext/concat_idents.rs
@@ -16,9 +16,11 @@ use owned_slice::OwnedSlice;
 use parse::token;
 use parse::token::{str_to_ident};
 
+use std::strbuf::StrBuf;
+
 pub fn expand_syntax_ext(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
     -> base::MacResult {
-    let mut res_str = ~"";
+    let mut res_str = StrBuf::new();
     for (i, e) in tts.iter().enumerate() {
         if i & 1 == 1 {
             match *e {
@@ -40,7 +42,7 @@ pub fn expand_syntax_ext(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
             }
         }
     }
-    let res = str_to_ident(res_str);
+    let res = str_to_ident(res_str.into_owned());
 
     let e = @ast::Expr {
         id: ast::DUMMY_NODE_ID,
diff --git a/src/libsyntax/ext/deriving/show.rs b/src/libsyntax/ext/deriving/show.rs
index 1c80fb9ced2..067958e4bde 100644
--- a/src/libsyntax/ext/deriving/show.rs
+++ b/src/libsyntax/ext/deriving/show.rs
@@ -15,10 +15,10 @@ use ext::format;
 use ext::base::ExtCtxt;
 use ext::build::AstBuilder;
 use ext::deriving::generic::*;
-
 use parse::token;
 
 use collections::HashMap;
+use std::strbuf::StrBuf;
 
 pub fn expand_deriving_show(cx: &mut ExtCtxt,
                             span: Span,
@@ -68,7 +68,7 @@ fn show_substructure(cx: &mut ExtCtxt, span: Span,
         }
     };
 
-    let mut format_string = token::get_ident(name).get().to_owned();
+    let mut format_string = StrBuf::from_str(token::get_ident(name).get());
     // the internal fields we're actually formatting
     let mut exprs = Vec::new();
 
@@ -129,7 +129,7 @@ fn show_substructure(cx: &mut ExtCtxt, span: Span,
     let write_call = cx.expr_call_global(span, std_write, vec!(buf, cx.expr_ident(span, args)));
     let format_closure = cx.lambda_expr(span, vec!(args), write_call);
 
-    let s = token::intern_and_get_ident(format_string);
+    let s = token::intern_and_get_ident(format_string.as_slice());
     let format_string = cx.expr_str(span, s);
 
     // phew, not our responsibility any more!
diff --git a/src/libsyntax/parse/comments.rs b/src/libsyntax/parse/comments.rs
index bb812f7f6b4..1a246eb7f2c 100644
--- a/src/libsyntax/parse/comments.rs
+++ b/src/libsyntax/parse/comments.rs
@@ -19,6 +19,7 @@ use parse::token;
 
 use std::io;
 use std::str;
+use std::strbuf::StrBuf;
 use std::uint;
 
 #[deriving(Clone, Eq)]
@@ -134,13 +135,13 @@ pub fn strip_doc_comment_decoration(comment: &str) -> ~str {
 }
 
 fn read_to_eol(rdr: &mut StringReader) -> ~str {
-    let mut val = ~"";
+    let mut val = StrBuf::new();
     while !rdr.curr_is('\n') && !is_eof(rdr) {
         val.push_char(rdr.curr.unwrap());
         bump(rdr);
     }
     if rdr.curr_is('\n') { bump(rdr); }
-    return val;
+    return val.into_owned();
 }
 
 fn read_one_line_comment(rdr: &mut StringReader) -> ~str {
@@ -255,7 +256,7 @@ fn read_block_comment(rdr: &mut StringReader,
     bump(rdr);
     bump(rdr);
 
-    let mut curr_line = ~"/*";
+    let mut curr_line = StrBuf::from_str("/*");
 
     // doc-comments are not really comments, they are attributes
     if (rdr.curr_is('*') && !nextch_is(rdr, '*')) || rdr.curr_is('!') {
@@ -268,9 +269,11 @@ fn read_block_comment(rdr: &mut StringReader,
             bump(rdr);
             bump(rdr);
         }
-        if !is_block_non_doc_comment(curr_line) { return; }
-        assert!(!curr_line.contains_char('\n'));
-        lines.push(curr_line);
+        if !is_block_non_doc_comment(curr_line.as_slice()) {
+            return
+        }
+        assert!(!curr_line.as_slice().contains_char('\n'));
+        lines.push(curr_line.into_owned());
     } else {
         let mut level: int = 1;
         while level > 0 {
@@ -279,9 +282,10 @@ fn read_block_comment(rdr: &mut StringReader,
                 rdr.fatal(~"unterminated block comment");
             }
             if rdr.curr_is('\n') {
-                trim_whitespace_prefix_and_push_line(&mut lines, curr_line,
+                trim_whitespace_prefix_and_push_line(&mut lines,
+                                                     curr_line.into_owned(),
                                                      col);
-                curr_line = ~"";
+                curr_line = StrBuf::new();
                 bump(rdr);
             } else {
                 curr_line.push_char(rdr.curr.unwrap());
@@ -301,7 +305,9 @@ fn read_block_comment(rdr: &mut StringReader,
             }
         }
         if curr_line.len() != 0 {
-            trim_whitespace_prefix_and_push_line(&mut lines, curr_line, col);
+            trim_whitespace_prefix_and_push_line(&mut lines,
+                                                 curr_line.into_owned(),
+                                                 col);
         }
     }
 
diff --git a/src/libsyntax/parse/lexer.rs b/src/libsyntax/parse/lexer.rs
index 23d7cc0af97..c1c91cb6a4f 100644
--- a/src/libsyntax/parse/lexer.rs
+++ b/src/libsyntax/parse/lexer.rs
@@ -21,6 +21,7 @@ use std::mem::replace;
 use std::num::from_str_radix;
 use std::rc::Rc;
 use std::str;
+use std::strbuf::StrBuf;
 
 pub use ext::tt::transcribe::{TtReader, new_tt_reader};
 
@@ -152,10 +153,10 @@ fn fatal_span_char(rdr: &mut StringReader,
                    m: ~str,
                    c: char)
                 -> ! {
-    let mut m = m;
+    let mut m = StrBuf::from_owned_str(m);
     m.push_str(": ");
     char::escape_default(c, |c| m.push_char(c));
-    fatal_span(rdr, from_pos, to_pos, m);
+    fatal_span(rdr, from_pos, to_pos, m.into_owned());
 }
 
 // report a lexical error spanning [`from_pos`, `to_pos`), appending the
@@ -165,12 +166,12 @@ fn fatal_span_verbose(rdr: &mut StringReader,
                       to_pos: BytePos,
                       m: ~str)
                    -> ! {
-    let mut m = m;
+    let mut m = StrBuf::from_owned_str(m);
     m.push_str(": ");
     let from = byte_offset(rdr, from_pos).to_uint();
     let to = byte_offset(rdr, to_pos).to_uint();
     m.push_str(rdr.filemap.src.slice(from, to));
-    fatal_span(rdr, from_pos, to_pos, m);
+    fatal_span(rdr, from_pos, to_pos, m.into_owned());
 }
 
 // EFFECT: advance peek_tok and peek_span to refer to the next token.
@@ -440,7 +441,7 @@ fn consume_block_comment(rdr: &mut StringReader) -> Option<TokenAndSpan> {
 fn scan_exponent(rdr: &mut StringReader, start_bpos: BytePos) -> Option<~str> {
     // \x00 hits the `return None` case immediately, so this is fine.
     let mut c = rdr.curr.unwrap_or('\x00');
-    let mut rslt = ~"";
+    let mut rslt = StrBuf::new();
     if c == 'e' || c == 'E' {
         rslt.push_char(c);
         bump(rdr);
@@ -451,7 +452,8 @@ fn scan_exponent(rdr: &mut StringReader, start_bpos: BytePos) -> Option<~str> {
         }
         let exponent = scan_digits(rdr, 10u);
         if exponent.len() > 0u {
-            return Some(rslt + exponent);
+            rslt.push_str(exponent);
+            return Some(rslt.into_owned());
         } else {
             fatal_span(rdr, start_bpos, rdr.last_pos,
                        ~"scan_exponent: bad fp literal");
@@ -460,7 +462,7 @@ fn scan_exponent(rdr: &mut StringReader, start_bpos: BytePos) -> Option<~str> {
 }
 
 fn scan_digits(rdr: &mut StringReader, radix: uint) -> ~str {
-    let mut rslt = ~"";
+    let mut rslt = StrBuf::new();
     loop {
         let c = rdr.curr;
         if c == Some('_') { bump(rdr); continue; }
@@ -469,7 +471,7 @@ fn scan_digits(rdr: &mut StringReader, radix: uint) -> ~str {
             rslt.push_char(c.unwrap());
             bump(rdr);
           }
-          _ => return rslt
+          _ => return rslt.into_owned()
         }
     };
 }
@@ -506,7 +508,7 @@ fn scan_number(c: char, rdr: &mut StringReader) -> token::Token {
         bump(rdr);
         base = 2u;
     }
-    num_str = scan_digits(rdr, base);
+    num_str = StrBuf::from_owned_str(scan_digits(rdr, base));
     c = rdr.curr.unwrap_or('\x00');
     nextch(rdr);
     if c == 'u' || c == 'i' {
@@ -544,7 +546,8 @@ fn scan_number(c: char, rdr: &mut StringReader) -> token::Token {
             fatal_span(rdr, start_bpos, rdr.last_pos,
                        ~"no valid digits found for number");
         }
-        let parsed = match from_str_radix::<u64>(num_str, base as uint) {
+        let parsed = match from_str_radix::<u64>(num_str.as_slice(),
+                                                 base as uint) {
             Some(p) => p,
             None => fatal_span(rdr, start_bpos, rdr.last_pos,
                                ~"int literal is too large")
@@ -579,12 +582,14 @@ fn scan_number(c: char, rdr: &mut StringReader) -> token::Token {
             bump(rdr);
             bump(rdr);
             check_float_base(rdr, start_bpos, rdr.last_pos, base);
-            return token::LIT_FLOAT(str_to_ident(num_str), ast::TyF32);
+            return token::LIT_FLOAT(str_to_ident(num_str.into_owned()),
+                                    ast::TyF32);
         } else if c == '6' && n == '4' {
             bump(rdr);
             bump(rdr);
             check_float_base(rdr, start_bpos, rdr.last_pos, base);
-            return token::LIT_FLOAT(str_to_ident(num_str), ast::TyF64);
+            return token::LIT_FLOAT(str_to_ident(num_str.into_owned()),
+                                    ast::TyF64);
             /* FIXME (#2252): if this is out of range for either a
             32-bit or 64-bit float, it won't be noticed till the
             back-end.  */
@@ -595,19 +600,22 @@ fn scan_number(c: char, rdr: &mut StringReader) -> token::Token {
     }
     if is_float {
         check_float_base(rdr, start_bpos, rdr.last_pos, base);
-        return token::LIT_FLOAT_UNSUFFIXED(str_to_ident(num_str));
+        return token::LIT_FLOAT_UNSUFFIXED(str_to_ident(
+                num_str.into_owned()));
     } else {
         if num_str.len() == 0u {
             fatal_span(rdr, start_bpos, rdr.last_pos,
                        ~"no valid digits found for number");
         }
-        let parsed = match from_str_radix::<u64>(num_str, base as uint) {
+        let parsed = match from_str_radix::<u64>(num_str.as_slice(),
+                                                 base as uint) {
             Some(p) => p,
             None => fatal_span(rdr, start_bpos, rdr.last_pos,
                                ~"int literal is too large")
         };
 
-        debug!("lexing {} as an unsuffixed integer literal", num_str);
+        debug!("lexing {} as an unsuffixed integer literal",
+               num_str.as_slice());
         return token::LIT_INT_UNSUFFIXED(parsed as i64);
     }
 }
@@ -863,7 +871,7 @@ fn next_token_inner(rdr: &mut StringReader) -> token::Token {
         return token::LIT_CHAR(c2 as u32);
       }
       '"' => {
-        let mut accum_str = ~"";
+        let mut accum_str = StrBuf::new();
         let start_bpos = rdr.last_pos;
         bump(rdr);
         while !rdr.curr_is('"') {
@@ -912,7 +920,7 @@ fn next_token_inner(rdr: &mut StringReader) -> token::Token {
             }
         }
         bump(rdr);
-        return token::LIT_STR(str_to_ident(accum_str));
+        return token::LIT_STR(str_to_ident(accum_str.as_slice()));
       }
       'r' => {
         let start_bpos = rdr.last_pos;
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index c8ea0b6aac2..704b6a50dc3 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -79,6 +79,7 @@ use owned_slice::OwnedSlice;
 use collections::HashSet;
 use std::mem::replace;
 use std::rc::Rc;
+use std::strbuf::StrBuf;
 
 #[allow(non_camel_case_types)]
 #[deriving(Eq)]
@@ -4136,14 +4137,14 @@ impl<'a> Parser<'a> {
         let mut included_mod_stack = self.sess.included_mod_stack.borrow_mut();
         match included_mod_stack.iter().position(|p| *p == path) {
             Some(i) => {
-                let mut err = ~"circular modules: ";
+                let mut err = StrBuf::from_str("circular modules: ");
                 let len = included_mod_stack.len();
                 for p in included_mod_stack.slice(i, len).iter() {
                     err.push_str(p.display().as_maybe_owned().as_slice());
                     err.push_str(" -> ");
                 }
                 err.push_str(path.display().as_maybe_owned().as_slice());
-                self.span_fatal(id_sp, err);
+                self.span_fatal(id_sp, err.into_owned());
             }
             None => ()
         }
@@ -4711,14 +4712,14 @@ impl<'a> Parser<'a> {
 
         // FAILURE TO PARSE ITEM
         if visibility != Inherited {
-            let mut s = ~"unmatched visibility `";
+            let mut s = StrBuf::from_str("unmatched visibility `");
             if visibility == Public {
                 s.push_str("pub")
             } else {
                 s.push_str("priv")
             }
             s.push_char('`');
-            self.span_fatal(self.last_span, s);
+            self.span_fatal(self.last_span, s.as_slice());
         }
         return IoviNone(attrs);
     }
diff --git a/src/libsyntax/parse/token.rs b/src/libsyntax/parse/token.rs
index ff1509fe23a..baade21d942 100644
--- a/src/libsyntax/parse/token.rs
+++ b/src/libsyntax/parse/token.rs
@@ -23,6 +23,7 @@ use std::fmt;
 use std::local_data;
 use std::path::BytesContainer;
 use std::rc::Rc;
+use std::strbuf::StrBuf;
 
 #[allow(non_camel_case_types)]
 #[deriving(Clone, Encodable, Decodable, Eq, TotalEq, Hash, Show)]
@@ -193,12 +194,12 @@ pub fn to_str(t: &Token) -> ~str {
 
       /* Literals */
       LIT_CHAR(c) => {
-          let mut res = ~"'";
+          let mut res = StrBuf::from_str("'");
           char::from_u32(c).unwrap().escape_default(|c| {
               res.push_char(c);
           });
           res.push_char('\'');
-          res
+          res.into_owned()
       }
       LIT_INT(i, t) => {
           i.to_str() + ast_util::int_ty_to_str(t)
@@ -208,18 +209,19 @@ pub fn to_str(t: &Token) -> ~str {
       }
       LIT_INT_UNSUFFIXED(i) => { i.to_str() }
       LIT_FLOAT(s, t) => {
-        let mut body = get_ident(s).get().to_str();
-        if body.ends_with(".") {
+        let mut body = StrBuf::from_str(get_ident(s).get());
+        if body.as_slice().ends_with(".") {
             body.push_char('0');  // `10.f` is not a float literal
         }
-        body + ast_util::float_ty_to_str(t)
+        body.push_str(ast_util::float_ty_to_str(t));
+        body.into_owned()
       }
       LIT_FLOAT_UNSUFFIXED(s) => {
-        let mut body = get_ident(s).get().to_str();
-        if body.ends_with(".") {
+        let mut body = StrBuf::from_str(get_ident(s).get());
+        if body.as_slice().ends_with(".") {
             body.push_char('0');  // `10.f` is not a float literal
         }
-        body
+        body.into_owned()
       }
       LIT_STR(s) => {
           format!("\"{}\"", get_ident(s).get().escape_default())
diff --git a/src/libsyntax/print/pp.rs b/src/libsyntax/print/pp.rs
index 7b64d0293cc..6cd72cb58f1 100644
--- a/src/libsyntax/print/pp.rs
+++ b/src/libsyntax/print/pp.rs
@@ -62,6 +62,7 @@
  */
 
 use std::io;
+use std::strbuf::StrBuf;
 
 #[deriving(Clone, Eq)]
 pub enum Breaks {
@@ -118,13 +119,17 @@ pub fn tok_str(t: Token) -> ~str {
     }
 }
 
-pub fn buf_str(toks: Vec<Token> , szs: Vec<int> , left: uint, right: uint,
-               lim: uint) -> ~str {
+pub fn buf_str(toks: Vec<Token>,
+               szs: Vec<int>,
+               left: uint,
+               right: uint,
+               lim: uint)
+               -> ~str {
     let n = toks.len();
     assert_eq!(n, szs.len());
     let mut i = left;
     let mut l = lim;
-    let mut s = ~"[";
+    let mut s = StrBuf::from_str("[");
     while i != right && l != 0u {
         l -= 1u;
         if i != left {
@@ -135,7 +140,7 @@ pub fn buf_str(toks: Vec<Token> , szs: Vec<int> , left: uint, right: uint,
         i %= n;
     }
     s.push_char(']');
-    return s;
+    return s.into_owned();
 }
 
 pub enum PrintStackBreak {
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index 44e95aa9573..0d8cd02fc7a 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -27,10 +27,11 @@ use print::pp;
 
 use std::cast;
 use std::char;
-use std::str;
-use std::io;
 use std::io::{IoResult, MemWriter};
+use std::io;
 use std::rc::Rc;
+use std::str;
+use std::strbuf::StrBuf;
 
 pub enum AnnNode<'a> {
     NodeBlock(&'a ast::Block),
@@ -2156,10 +2157,10 @@ impl<'a> State<'a> {
         match lit.node {
             ast::LitStr(ref st, style) => self.print_string(st.get(), style),
             ast::LitChar(ch) => {
-                let mut res = ~"'";
+                let mut res = StrBuf::from_str("'");
                 char::from_u32(ch).unwrap().escape_default(|c| res.push_char(c));
                 res.push_char('\'');
-                word(&mut self.s, res)
+                word(&mut self.s, res.into_owned())
             }
             ast::LitInt(i, t) => {
                 word(&mut self.s, format!("{}{}", i, ast_util::int_ty_to_str(t)))
diff --git a/src/libtest/lib.rs b/src/libtest/lib.rs
index 5c74715fd29..8c6f7576ec4 100644
--- a/src/libtest/lib.rs
+++ b/src/libtest/lib.rs
@@ -59,6 +59,7 @@ use std::io::{File, ChanReader, ChanWriter};
 use std::io;
 use std::os;
 use std::str;
+use std::strbuf::StrBuf;
 use std::task;
 
 // to be used by rustc to compile tests in libtest
@@ -99,13 +100,19 @@ enum NamePadding { PadNone, PadOnLeft, PadOnRight }
 impl TestDesc {
     fn padded_name(&self, column_count: uint, align: NamePadding) -> ~str {
         use std::num::Saturating;
-        let name = self.name.to_str();
+        let mut name = StrBuf::from_str(self.name.to_str());
         let fill = column_count.saturating_sub(name.len());
-        let pad = " ".repeat(fill);
+        let mut pad = StrBuf::from_owned_str(" ".repeat(fill));
         match align {
-            PadNone => name,
-            PadOnLeft => pad.append(name),
-            PadOnRight => name.append(pad),
+            PadNone => name.into_owned(),
+            PadOnLeft => {
+                pad.push_str(name.as_slice());
+                pad.into_owned()
+            }
+            PadOnRight => {
+                name.push_str(pad.as_slice());
+                name.into_owned()
+            }
         }
     }
 }
@@ -543,7 +550,7 @@ impl<T: Writer> ConsoleTestState<T> {
     pub fn write_failures(&mut self) -> io::IoResult<()> {
         try!(self.write_plain("\nfailures:\n"));
         let mut failures = Vec::new();
-        let mut fail_out  = ~"";
+        let mut fail_out = StrBuf::new();
         for &(ref f, ref stdout) in self.failures.iter() {
             failures.push(f.name.to_str());
             if stdout.len() > 0 {
@@ -556,7 +563,7 @@ impl<T: Writer> ConsoleTestState<T> {
         }
         if fail_out.len() > 0 {
             try!(self.write_plain("\n"));
-            try!(self.write_plain(fail_out));
+            try!(self.write_plain(fail_out.as_slice()));
         }
 
         try!(self.write_plain("\nfailures:\n"));
diff --git a/src/libtime/lib.rs b/src/libtime/lib.rs
index 23ffb7813ba..d50ecc2a2ab 100644
--- a/src/libtime/lib.rs
+++ b/src/libtime/lib.rs
@@ -24,6 +24,7 @@ extern crate libc;
 
 use std::io::BufReader;
 use std::num;
+use std::strbuf::StrBuf;
 use std::str;
 
 static NSEC_PER_SEC: i32 = 1_000_000_000_i32;
@@ -236,7 +237,10 @@ pub struct Tm {
 pub fn empty_tm() -> Tm {
     // 64 is the max size of the timezone buffer allocated on windows
     // in rust_localtime. In glibc the max timezone size is supposedly 3.
-    let zone = str::with_capacity(64);
+    let mut zone = StrBuf::new();
+    for _ in range(0, 64) {
+        zone.push_char(' ')
+    }
     Tm {
         tm_sec: 0_i32,
         tm_min: 0_i32,
@@ -248,7 +252,7 @@ pub fn empty_tm() -> Tm {
         tm_yday: 0_i32,
         tm_isdst: 0_i32,
         tm_gmtoff: 0_i32,
-        tm_zone: zone,
+        tm_zone: zone.into_owned(),
         tm_nsec: 0_i32,
     }
 }
diff --git a/src/liburl/lib.rs b/src/liburl/lib.rs
index cd8e36b3c93..1ea67f2bee1 100644
--- a/src/liburl/lib.rs
+++ b/src/liburl/lib.rs
@@ -21,15 +21,15 @@
 
 extern crate collections;
 
+use collections::HashMap;
 use std::cmp::Eq;
 use std::fmt;
+use std::from_str::FromStr;
 use std::hash::Hash;
 use std::io::BufReader;
-use std::from_str::FromStr;
+use std::strbuf::StrBuf;
 use std::uint;
 
-use collections::HashMap;
-
 /// A Uniform Resource Locator (URL).  A URL is a form of URI (Uniform Resource
 /// Identifier) that includes network location information, such as hostname or
 /// port number.
@@ -133,7 +133,7 @@ impl UserInfo {
 
 fn encode_inner(s: &str, full_url: bool) -> ~str {
     let mut rdr = BufReader::new(s.as_bytes());
-    let mut out = ~"";
+    let mut out = StrBuf::new();
 
     loop {
         let mut buf = [0];
@@ -171,7 +171,7 @@ fn encode_inner(s: &str, full_url: bool) -> ~str {
         }
     }
 
-    out
+    out.into_owned()
 }
 
 /**
@@ -206,7 +206,7 @@ pub fn encode_component(s: &str) -> ~str {
 
 fn decode_inner(s: &str, full_url: bool) -> ~str {
     let mut rdr = BufReader::new(s.as_bytes());
-    let mut out = ~"";
+    let mut out = StrBuf::new();
 
     loop {
         let mut buf = [0];
@@ -247,7 +247,7 @@ fn decode_inner(s: &str, full_url: bool) -> ~str {
         }
     }
 
-    out
+    out.into_owned()
 }
 
 /**
@@ -277,7 +277,7 @@ pub fn decode_component(s: &str) -> ~str {
 
 fn encode_plus(s: &str) -> ~str {
     let mut rdr = BufReader::new(s.as_bytes());
-    let mut out = ~"";
+    let mut out = StrBuf::new();
 
     loop {
         let mut buf = [0];
@@ -294,14 +294,14 @@ fn encode_plus(s: &str) -> ~str {
         }
     }
 
-    out
+    out.into_owned()
 }
 
 /**
  * Encode a hashmap to the 'application/x-www-form-urlencoded' media type.
  */
 pub fn encode_form_urlencoded(m: &HashMap<~str, Vec<~str>>) -> ~str {
-    let mut out = ~"";
+    let mut out = StrBuf::new();
     let mut first = true;
 
     for (key, values) in m.iter() {
@@ -319,18 +319,19 @@ pub fn encode_form_urlencoded(m: &HashMap<~str, Vec<~str>>) -> ~str {
         }
     }
 
-    out
+    out.into_owned()
 }
 
 /**
  * Decode a string encoded with the 'application/x-www-form-urlencoded' media
  * type into a hashmap.
  */
+#[allow(experimental)]
 pub fn decode_form_urlencoded(s: &[u8]) -> HashMap<~str, Vec<~str>> {
     let mut rdr = BufReader::new(s);
-    let mut m = HashMap::new();
-    let mut key = ~"";
-    let mut value = ~"";
+    let mut m: HashMap<~str,Vec<~str>> = HashMap::new();
+    let mut key = StrBuf::new();
+    let mut value = StrBuf::new();
     let mut parsing_key = true;
 
     loop {
@@ -341,19 +342,19 @@ pub fn decode_form_urlencoded(s: &[u8]) -> HashMap<~str, Vec<~str>> {
         };
         match ch {
             '&' | ';' => {
-                if key != ~"" && value != ~"" {
-                    let mut values = match m.pop(&key) {
+                if key.len() > 0 && value.len() > 0 {
+                    let mut values = match m.pop_equiv(&key.as_slice()) {
                         Some(values) => values,
                         None => vec!(),
                     };
 
-                    values.push(value);
-                    m.insert(key, values);
+                    values.push(value.into_owned());
+                    m.insert(key.into_owned(), values);
                 }
 
                 parsing_key = true;
-                key = ~"";
-                value = ~"";
+                key = StrBuf::new();
+                value = StrBuf::new();
             }
             '=' => parsing_key = false,
             ch => {
@@ -379,14 +380,14 @@ pub fn decode_form_urlencoded(s: &[u8]) -> HashMap<~str, Vec<~str>> {
         }
     }
 
-    if key != ~"" && value != ~"" {
-        let mut values = match m.pop(&key) {
+    if key.len() > 0 && value.len() > 0 {
+        let mut values = match m.pop_equiv(&key.as_slice()) {
             Some(values) => values,
             None => vec!(),
         };
 
-        values.push(value);
-        m.insert(key, values);
+        values.push(value.into_owned());
+        m.insert(key.into_owned(), values);
     }
 
     m
diff --git a/src/test/bench/shootout-chameneos-redux.rs b/src/test/bench/shootout-chameneos-redux.rs
index 407bea5b4f4..18900abace6 100644
--- a/src/test/bench/shootout-chameneos-redux.rs
+++ b/src/test/bench/shootout-chameneos-redux.rs
@@ -12,6 +12,7 @@
 
 use std::option;
 use std::os;
+use std::strbuf::StrBuf;
 use std::task;
 
 fn print_complements() {
@@ -40,12 +41,12 @@ fn show_color(cc: color) -> ~str {
 }
 
 fn show_color_list(set: Vec<color>) -> ~str {
-    let mut out = ~"";
+    let mut out = StrBuf::new();
     for col in set.iter() {
         out.push_char(' ');
         out.push_str(show_color(*col));
     }
-    return out;
+    return out.to_owned_str();
 }
 
 fn show_digit(nn: uint) -> ~str {
diff --git a/src/test/bench/shootout-k-nucleotide-pipes.rs b/src/test/bench/shootout-k-nucleotide-pipes.rs
index 4c367b85394..ca88f107336 100644
--- a/src/test/bench/shootout-k-nucleotide-pipes.rs
+++ b/src/test/bench/shootout-k-nucleotide-pipes.rs
@@ -23,6 +23,7 @@ use std::option;
 use std::os;
 use std::io;
 use std::str;
+use std::strbuf::StrBuf;
 use std::task;
 use std::vec;
 
@@ -63,8 +64,7 @@ fn sort_and_fmt(mm: &HashMap<Vec<u8> , uint>, total: uint) -> ~str {
 
    let pairs_sorted = sortKV(pairs);
 
-   let mut buffer = ~"";
-
+   let mut buffer = StrBuf::new();
    for &(ref k, v) in pairs_sorted.iter() {
        unsafe {
            buffer.push_str(format!("{} {:0.3f}\n",
@@ -75,7 +75,7 @@ fn sort_and_fmt(mm: &HashMap<Vec<u8> , uint>, total: uint) -> ~str {
        }
    }
 
-   return buffer;
+   return buffer.to_owned_str();
 }
 
 // given a map, search for the frequency of a pattern
diff --git a/src/test/bench/shootout-k-nucleotide.rs b/src/test/bench/shootout-k-nucleotide.rs
index 7ceaaa7ad22..c9794d54829 100644
--- a/src/test/bench/shootout-k-nucleotide.rs
+++ b/src/test/bench/shootout-k-nucleotide.rs
@@ -13,6 +13,7 @@
 
 use std::ascii::OwnedStrAsciiExt;
 use std::str;
+use std::strbuf::StrBuf;
 use std::slice;
 
 static TABLE: [u8, ..4] = [ 'A' as u8, 'C' as u8, 'G' as u8, 'T' as u8 ];
@@ -249,13 +250,13 @@ fn print_occurrences(frequencies: &mut Table, occurrence: &'static str) {
 }
 
 fn get_sequence<R: Buffer>(r: &mut R, key: &str) -> ~[u8] {
-    let mut res = ~"";
+    let mut res = StrBuf::new();
     for l in r.lines().map(|l| l.ok().unwrap())
         .skip_while(|l| key != l.slice_to(key.len())).skip(1)
     {
         res.push_str(l.trim());
     }
-    res.into_ascii_upper().into_bytes()
+    res.to_owned_str().into_ascii_upper().into_bytes()
 }
 
 fn main() {
diff --git a/src/test/run-fail/glob-use-std.rs b/src/test/run-fail/glob-use-std.rs
index a67ab3d2efc..458a95b91cf 100644
--- a/src/test/run-fail/glob-use-std.rs
+++ b/src/test/run-fail/glob-use-std.rs
@@ -16,7 +16,7 @@
 use std::*;
 
 fn main() {
-    str::with_capacity(10); // avoid an unused import message
+    str::from_byte('a' as u8); // avoid an unused import message
 
     fail!("fail works")
 }
diff --git a/src/test/run-pass/istr.rs b/src/test/run-pass/istr.rs
index b8d56f761b8..67cb87145db 100644
--- a/src/test/run-pass/istr.rs
+++ b/src/test/run-pass/istr.rs
@@ -8,6 +8,8 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use std::strbuf::StrBuf;
+
 fn test_stack_assign() {
     let s: ~str = ~"a";
     println!("{}", s.clone());
@@ -43,21 +45,21 @@ fn test_heap_add() {
 }
 
 fn test_append() {
-    let mut s = ~"";
+    let mut s = StrBuf::new();
     s.push_str("a");
-    assert_eq!(s, ~"a");
+    assert_eq!(s.as_slice(), "a");
 
-    let mut s = ~"a";
+    let mut s = StrBuf::from_str("a");
     s.push_str("b");
     println!("{}", s.clone());
-    assert_eq!(s, ~"ab");
+    assert_eq!(s.as_slice(), "ab");
 
-    let mut s = ~"c";
+    let mut s = StrBuf::from_str("c");
     s.push_str("offee");
-    assert!(s == ~"coffee");
+    assert!(s.as_slice() == "coffee");
 
     s.push_str("&tea");
-    assert!(s == ~"coffee&tea");
+    assert!(s.as_slice() == "coffee&tea");
 }
 
 pub fn main() {
diff --git a/src/test/run-pass/move-out-of-field.rs b/src/test/run-pass/move-out-of-field.rs
index 2041c69cecc..42b61695d60 100644
--- a/src/test/run-pass/move-out-of-field.rs
+++ b/src/test/run-pass/move-out-of-field.rs
@@ -8,8 +8,10 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use std::strbuf::StrBuf;
+
 struct StringBuffer {
-    s: ~str
+    s: StrBuf,
 }
 
 impl StringBuffer {
@@ -18,14 +20,16 @@ impl StringBuffer {
     }
 }
 
-fn to_str(sb: StringBuffer) -> ~str {
+fn to_str(sb: StringBuffer) -> StrBuf {
     sb.s
 }
 
 pub fn main() {
-    let mut sb = StringBuffer {s: ~""};
+    let mut sb = StringBuffer {
+        s: StrBuf::new(),
+    };
     sb.append("Hello, ");
     sb.append("World!");
     let str = to_str(sb);
-    assert_eq!(str, ~"Hello, World!");
+    assert_eq!(str.as_slice(), "Hello, World!");
 }
diff --git a/src/test/run-pass/overloaded-autoderef.rs b/src/test/run-pass/overloaded-autoderef.rs
index 6b347b3833e..6c66938af51 100644
--- a/src/test/run-pass/overloaded-autoderef.rs
+++ b/src/test/run-pass/overloaded-autoderef.rs
@@ -10,6 +10,7 @@
 
 use std::cell::RefCell;
 use std::rc::Rc;
+use std::strbuf::StrBuf;
 
 #[deriving(Eq, Show)]
 struct Point {
@@ -33,7 +34,7 @@ pub fn main() {
     assert!(s.equiv(&("foo")));
     assert_eq!(s.as_slice(), "foo");
 
-    let mut_s = Rc::new(RefCell::new(~"foo"));
+    let mut_s = Rc::new(RefCell::new(StrBuf::from_str("foo")));
     mut_s.borrow_mut().push_str("bar");
     // HACK assert_eq! would fail here because it stores the LHS and RHS in two locals.
     assert!(mut_s.borrow().as_slice() == "foobar");
diff --git a/src/test/run-pass/overloaded-deref.rs b/src/test/run-pass/overloaded-deref.rs
index aa9a66daed7..27edb2f0088 100644
--- a/src/test/run-pass/overloaded-deref.rs
+++ b/src/test/run-pass/overloaded-deref.rs
@@ -10,6 +10,7 @@
 
 use std::cell::RefCell;
 use std::rc::Rc;
+use std::strbuf::StrBuf;
 
 #[deriving(Eq, Show)]
 struct Point {
@@ -31,7 +32,7 @@ pub fn main() {
     assert_eq!(*s, ~"foo");
     assert_eq!((*s).as_slice(), "foo");
 
-    let mut_s = Rc::new(RefCell::new(~"foo"));
+    let mut_s = Rc::new(RefCell::new(StrBuf::from_str("foo")));
     (*(*mut_s).borrow_mut()).push_str("bar");
     // assert_eq! would fail here because it stores the LHS and RHS in two locals.
     assert!((*(*mut_s).borrow()).as_slice() == "foobar");
diff --git a/src/test/run-pass/str-append.rs b/src/test/run-pass/str-append.rs
deleted file mode 100644
index ad6e668524c..00000000000
--- a/src/test/run-pass/str-append.rs
+++ /dev/null
@@ -1,30 +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.
-
-fn test1() {
-    let mut s: ~str = ~"hello";
-    s.push_str("world");
-    println!("{}", s.clone());
-    assert_eq!(s[9], 'd' as u8);
-}
-
-fn test2() {
-    // This tests for issue #163
-
-    let ff: ~str = ~"abc";
-    let a: ~str = ff + "ABC" + ff;
-    let b: ~str = ~"ABC" + ff + "ABC";
-    println!("{}", a.clone());
-    println!("{}", b.clone());
-    assert_eq!(a, ~"abcABCabc");
-    assert_eq!(b, ~"ABCabcABC");
-}
-
-pub fn main() { test1(); test2(); }
diff --git a/src/test/run-pass/str-growth.rs b/src/test/run-pass/str-growth.rs
deleted file mode 100644
index 0cdf1841331..00000000000
--- a/src/test/run-pass/str-growth.rs
+++ /dev/null
@@ -1,24 +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.
-
-
-
-pub fn main() {
-    let mut s = ~"a";
-    s.push_char('b');
-    assert_eq!(s[0], 'a' as u8);
-    assert_eq!(s[1], 'b' as u8);
-    s.push_char('c');
-    s.push_char('d');
-    assert_eq!(s[0], 'a' as u8);
-    assert_eq!(s[1], 'b' as u8);
-    assert_eq!(s[2], 'c' as u8);
-    assert_eq!(s[3], 'd' as u8);
-}
diff --git a/src/test/run-pass/utf8_chars.rs b/src/test/run-pass/utf8_chars.rs
index cac2619f35c..a418cd0ae02 100644
--- a/src/test/run-pass/utf8_chars.rs
+++ b/src/test/run-pass/utf8_chars.rs
@@ -38,14 +38,4 @@ pub fn main() {
     assert!((!str::is_utf8([0xf0_u8, 0x10_u8])));
     assert!((!str::is_utf8([0xf0_u8, 0xff_u8, 0x10_u8])));
     assert!((!str::is_utf8([0xf0_u8, 0xff_u8, 0xff_u8, 0x10_u8])));
-
-    let mut stack = ~"a×c€";
-    assert_eq!(stack.pop_char(), Some('€'));
-    assert_eq!(stack.pop_char(), Some('c'));
-    stack.push_char('u');
-    assert!(stack == ~"a×u");
-    assert_eq!(stack.shift_char(), Some('a'));
-    assert_eq!(stack.shift_char(), Some('×'));
-    stack.unshift_char('ß');
-    assert!(stack == ~"ßu");
 }
diff --git a/src/test/run-pass/while-prelude-drop.rs b/src/test/run-pass/while-prelude-drop.rs
index 503e37fcd76..358d296de49 100644
--- a/src/test/run-pass/while-prelude-drop.rs
+++ b/src/test/run-pass/while-prelude-drop.rs
@@ -8,13 +8,14 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use std::strbuf::StrBuf;
 
 #[deriving(Eq)]
-enum t { a, b(~str), }
+enum t { a, b(StrBuf), }
 
 fn make(i: int) -> t {
     if i > 10 { return a; }
-    let mut s = ~"hello";
+    let mut s = StrBuf::from_str("hello");
     // Ensure s is non-const.
 
     s.push_str("there");