src/libcollections/string.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10 //
  11 // ignore-lexer-test FIXME #15679
  12
  13 //! An owned, growable string that enforces that its contents are valid UTF-8.
  14
  15 use core::prelude::*;
  16
  17 use core::default::Default;
  18 use core::fmt;
  19 use core::mem;
  20 use core::ptr;
  21 use core::ops;
  22 // FIXME: ICE's abound if you import the `Slice` type while importing `Slice` trait
  23 use core::raw::Slice as RawSlice;
  24
  25 use hash;
  26 use slice::CloneSliceAllocPrelude;
  27 use str;
  28 use str::{CharRange, StrAllocating, MaybeOwned, Owned};
  29 use str::Slice as MaybeOwnedSlice; // So many `Slice`s...
  30 use vec::{DerefVec, Vec, as_vec};
  31
  32 /// A growable string stored as a UTF-8 encoded buffer.
  33 #[deriving(Clone, PartialEq, PartialOrd, Eq, Ord)]
  34 #[stable]
  35 pub struct String {
  36     vec: Vec<u8>,
  37 }
  38
  39 impl String {
  40     /// Creates a new string buffer initialized with the empty string.
  41     ///
  42     /// # Example
  43     ///
  44     /// ```
  45     /// let mut s = String::new();
  46     /// ```
  47     #[inline]
  48     #[stable]
  49     pub fn new() -> String {
  50         String {
  51             vec: Vec::new(),
  52         }
  53     }
  54
  55     /// Creates a new string buffer with the given capacity.
  56     /// The string will be able to hold exactly `capacity` bytes without
  57     /// reallocating. If `capacity` is 0, the string will not allocate.
  58     ///
  59     /// # Example
  60     ///
  61     /// ```
  62     /// let mut s = String::with_capacity(10);
  63     /// ```
  64     #[inline]
  65     #[stable]
  66     pub fn with_capacity(capacity: uint) -> String {
  67         String {
  68             vec: Vec::with_capacity(capacity),
  69         }
  70     }
  71
  72     /// Creates a new string buffer from the given string.
  73     ///
  74     /// # Example
  75     ///
  76     /// ```
  77     /// let s = String::from_str("hello");
  78     /// assert_eq!(s.as_slice(), "hello");
  79     /// ```
  80     #[inline]
  81     #[experimental = "needs investigation to see if to_string() can match perf"]
  82     pub fn from_str(string: &str) -> String {
  83         String { vec: string.as_bytes().to_vec() }
  84     }
  85
  86     /// Returns the vector as a string buffer, if possible, taking care not to
  87     /// copy it.
  88     ///
  89     /// Returns `Err` with the original vector if the vector contains invalid
  90     /// UTF-8.
  91     ///
  92     /// # Example
  93     ///
  94     /// ```rust
  95     /// let hello_vec = vec![104, 101, 108, 108, 111];
  96     /// let s = String::from_utf8(hello_vec);
  97     /// assert_eq!(s, Ok("hello".to_string()));
  98     ///
  99     /// let invalid_vec = vec![240, 144, 128];
 100     /// let s = String::from_utf8(invalid_vec);
 101     /// assert_eq!(s, Err(vec![240, 144, 128]));
 102     /// ```
 103     #[inline]
 104     #[unstable = "error type may change"]
 105     pub fn from_utf8(vec: Vec<u8>) -> Result<String, Vec<u8>> {
 106         if str::is_utf8(vec.as_slice()) {
 107             Ok(String { vec: vec })
 108         } else {
 109             Err(vec)
 110         }
 111     }
 112
 113     /// Converts a vector of bytes to a new UTF-8 string.
 114     /// Any invalid UTF-8 sequences are replaced with U+FFFD REPLACEMENT CHARACTER.
 115     ///
 116     /// # Example
 117     ///
 118     /// ```rust
 119     /// let input = b"Hello \xF0\x90\x80World";
 120     /// let output = String::from_utf8_lossy(input);
 121     /// assert_eq!(output.as_slice(), "Hello \uFFFDWorld");
 122     /// ```
 123     #[unstable = "return type may change"]
 124     pub fn from_utf8_lossy<'a>(v: &'a [u8]) -> MaybeOwned<'a> {
 125         if str::is_utf8(v) {
 126             return MaybeOwnedSlice(unsafe { mem::transmute(v) })
 127         }
 128
 129         static TAG_CONT_U8: u8 = 128u8;
 130         static REPLACEMENT: &'static [u8] = b"\xEF\xBF\xBD"; // U+FFFD in UTF-8
 131         let mut i = 0;
 132         let total = v.len();
 133         fn unsafe_get(xs: &[u8], i: uint) -> u8 {
 134             unsafe { *xs.unsafe_get(i) }
 135         }
 136         fn safe_get(xs: &[u8], i: uint, total: uint) -> u8 {
 137             if i >= total {
 138                 0
 139             } else {
 140                 unsafe_get(xs, i)
 141             }
 142         }
 143
 144         let mut res = String::with_capacity(total);
 145
 146         if i > 0 {
 147             unsafe {
 148                 res.as_mut_vec().push_all(v[..i])
 149             };
 150         }
 151
 152         // subseqidx is the index of the first byte of the subsequence we're looking at.
 153         // It's used to copy a bunch of contiguous good codepoints at once instead of copying
 154         // them one by one.
 155         let mut subseqidx = 0;
 156
 157         while i < total {
 158             let i_ = i;
 159             let byte = unsafe_get(v, i);
 160             i += 1;
 161
 162             macro_rules! error(() => ({
 163                 unsafe {
 164                     if subseqidx != i_ {
 165                         res.as_mut_vec().push_all(v[subseqidx..i_]);
 166                     }
 167                     subseqidx = i;
 168                     res.as_mut_vec().push_all(REPLACEMENT);
 169                 }
 170             }))
 171
 172             if byte < 128u8 {
 173                 // subseqidx handles this
 174             } else {
 175                 let w = str::utf8_char_width(byte);
 176
 177                 match w {
 178                     2 => {
 179                         if safe_get(v, i, total) & 192u8 != TAG_CONT_U8 {
 180                             error!();
 181                             continue;
 182                         }
 183                         i += 1;
 184                     }
 185                     3 => {
 186                         match (byte, safe_get(v, i, total)) {
 187                             (0xE0         , 0xA0 ... 0xBF) => (),
 188                             (0xE1 ... 0xEC, 0x80 ... 0xBF) => (),
 189                             (0xED         , 0x80 ... 0x9F) => (),
 190                             (0xEE ... 0xEF, 0x80 ... 0xBF) => (),
 191                             _ => {
 192                                 error!();
 193                                 continue;
 194                             }
 195                         }
 196                         i += 1;
 197                         if safe_get(v, i, total) & 192u8 != TAG_CONT_U8 {
 198                             error!();
 199                             continue;
 200                         }
 201                         i += 1;
 202                     }
 203                     4 => {
 204                         match (byte, safe_get(v, i, total)) {
 205                             (0xF0         , 0x90 ... 0xBF) => (),
 206                             (0xF1 ... 0xF3, 0x80 ... 0xBF) => (),
 207                             (0xF4         , 0x80 ... 0x8F) => (),
 208                             _ => {
 209                                 error!();
 210                                 continue;
 211                             }
 212                         }
 213                         i += 1;
 214                         if safe_get(v, i, total) & 192u8 != TAG_CONT_U8 {
 215                             error!();
 216                             continue;
 217                         }
 218                         i += 1;
 219                         if safe_get(v, i, total) & 192u8 != TAG_CONT_U8 {
 220                             error!();
 221                             continue;
 222                         }
 223                         i += 1;
 224                     }
 225                     _ => {
 226                         error!();
 227                         continue;
 228                     }
 229                 }
 230             }
 231         }
 232         if subseqidx < total {
 233             unsafe {
 234                 res.as_mut_vec().push_all(v[subseqidx..total])
 235             };
 236         }
 237         Owned(res.into_string())
 238     }
 239
 240     /// Decode a UTF-16 encoded vector `v` into a `String`, returning `None`
 241     /// if `v` contains any invalid data.
 242     ///
 243     /// # Example
 244     ///
 245     /// ```rust
 246     /// // 𝄞music
 247     /// let mut v = [0xD834, 0xDD1E, 0x006d, 0x0075,
 248     ///              0x0073, 0x0069, 0x0063];
 249     /// assert_eq!(String::from_utf16(v), Some("𝄞music".to_string()));
 250     ///
 251     /// // 𝄞mu<invalid>ic
 252     /// v[4] = 0xD800;
 253     /// assert_eq!(String::from_utf16(v), None);
 254     /// ```
 255     #[unstable = "error value in return may change"]
 256     pub fn from_utf16(v: &[u16]) -> Option<String> {
 257         let mut s = String::with_capacity(v.len());
 258         for c in str::utf16_items(v) {
 259             match c {
 260                 str::ScalarValue(c) => s.push(c),
 261                 str::LoneSurrogate(_) => return None
 262             }
 263         }
 264         Some(s)
 265     }
 266
 267     /// Decode a UTF-16 encoded vector `v` into a string, replacing
 268     /// invalid data with the replacement character (U+FFFD).
 269     ///
 270     /// # Example
 271     /// ```rust
 272     /// // 𝄞mus<invalid>ic<invalid>
 273     /// let v = [0xD834, 0xDD1E, 0x006d, 0x0075,
 274     ///          0x0073, 0xDD1E, 0x0069, 0x0063,
 275     ///          0xD834];
 276     ///
 277     /// assert_eq!(String::from_utf16_lossy(v),
 278     ///            "𝄞mus\uFFFDic\uFFFD".to_string());
 279     /// ```
 280     #[stable]
 281     pub fn from_utf16_lossy(v: &[u16]) -> String {
 282         str::utf16_items(v).map(|c| c.to_char_lossy()).collect()
 283     }
 284
 285     /// Convert a vector of `char`s to a `String`.
 286     ///
 287     /// # Example
 288     ///
 289     /// ```rust
 290     /// let chars = ['h', 'e', 'l', 'l', 'o'];
 291     /// let s = String::from_chars(chars);
 292     /// assert_eq!(s.as_slice(), "hello");
 293     /// ```
 294     #[inline]
 295     #[unstable = "may be removed in favor of .collect()"]
 296     pub fn from_chars(chs: &[char]) -> String {
 297         chs.iter().map(|c| *c).collect()
 298     }
 299
 300     /// Return the underlying byte buffer, encoded as UTF-8.
 301     ///
 302     /// # Example
 303     ///
 304     /// ```
 305     /// let s = String::from_str("hello");
 306     /// let bytes = s.into_bytes();
 307     /// assert_eq!(bytes, vec![104, 101, 108, 108, 111]);
 308     /// ```
 309     #[inline]
 310     #[stable]
 311     pub fn into_bytes(self) -> Vec<u8> {
 312         self.vec
 313     }
 314
 315     /// Creates a string buffer by repeating a character `length` times.
 316     ///
 317     /// # Example
 318     ///
 319     /// ```
 320     /// let s = String::from_char(5, 'a');
 321     /// assert_eq!(s.as_slice(), "aaaaa");
 322     /// ```
 323     #[inline]
 324     #[unstable = "may be replaced with iterators, questionable usability, and \
 325                   the name may change"]
 326     pub fn from_char(length: uint, ch: char) -> String {
 327         if length == 0 {
 328             return String::new()
 329         }
 330
 331         let mut buf = String::new();
 332         buf.push(ch);
 333         let size = buf.len() * (length - 1);
 334         buf.reserve_exact(size);
 335         for _ in range(1, length) {
 336             buf.push(ch)
 337         }
 338         buf
 339     }
 340
 341     /// Pushes the given string onto this string buffer.
 342     ///
 343     /// # Example
 344     ///
 345     /// ```
 346     /// let mut s = String::from_str("foo");
 347     /// s.push_str("bar");
 348     /// assert_eq!(s.as_slice(), "foobar");
 349     /// ```
 350     #[inline]
 351     #[unstable = "extra variants of `push`, could possibly be based on iterators"]
 352     pub fn push_str(&mut self, string: &str) {
 353         self.vec.push_all(string.as_bytes())
 354     }
 355
 356     /// Pushes `ch` onto the given string `count` times.
 357     ///
 358     /// # Example
 359     ///
 360     /// ```
 361     /// let mut s = String::from_str("foo");
 362     /// s.grow(5, 'Z');
 363     /// assert_eq!(s.as_slice(), "fooZZZZZ");
 364     /// ```
 365     #[inline]
 366     #[unstable = "duplicate of iterator-based functionality"]
 367     pub fn grow(&mut self, count: uint, ch: char) {
 368         for _ in range(0, count) {
 369             self.push(ch)
 370         }
 371     }
 372
 373     /// Returns the number of bytes that this string buffer can hold without reallocating.
 374     ///
 375     /// # Example
 376     ///
 377     /// ```
 378     /// let s = String::with_capacity(10);
 379     /// assert!(s.capacity() >= 10);
 380     /// ```
 381     #[inline]
 382     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 383     pub fn capacity(&self) -> uint {
 384         self.vec.capacity()
 385     }
 386
 387     /// Deprecated: Renamed to `reserve`.
 388     #[deprecated = "Renamed to `reserve`"]
 389     pub fn reserve_additional(&mut self, extra: uint) {
 390         self.vec.reserve(extra)
 391     }
 392
 393     /// Reserves capacity for at least `additional` more bytes to be inserted in the given
 394     /// `String`. The collection may reserve more space to avoid frequent reallocations.
 395     ///
 396     /// # Panics
 397     ///
 398     /// Panics if the new capacity overflows `uint`.
 399     ///
 400     /// # Example
 401     ///
 402     /// ```
 403     /// let mut s = String::new();
 404     /// s.reserve(10);
 405     /// assert!(s.capacity() >= 10);
 406     /// ```
 407     #[inline]
 408     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 409     pub fn reserve(&mut self, additional: uint) {
 410         self.vec.reserve(additional)
 411     }
 412
 413     /// Reserves the minimum capacity for exactly `additional` more bytes to be inserted in the
 414     /// given `String`. Does nothing if the capacity is already sufficient.
 415     ///
 416     /// Note that the allocator may give the collection more space than it requests. Therefore
 417     /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
 418     /// insertions are expected.
 419     ///
 420     /// # Panics
 421     ///
 422     /// Panics if the new capacity overflows `uint`.
 423     ///
 424     /// # Example
 425     ///
 426     /// ```
 427     /// let mut s = String::new();
 428     /// s.reserve(10);
 429     /// assert!(s.capacity() >= 10);
 430     /// ```
 431     #[inline]
 432     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 433     pub fn reserve_exact(&mut self, additional: uint) {
 434         self.vec.reserve_exact(additional)
 435     }
 436
 437     /// Shrinks the capacity of this string buffer to match its length.
 438     ///
 439     /// # Example
 440     ///
 441     /// ```
 442     /// let mut s = String::from_str("foo");
 443     /// s.reserve(100);
 444     /// assert!(s.capacity() >= 100);
 445     /// s.shrink_to_fit();
 446     /// assert_eq!(s.capacity(), 3);
 447     /// ```
 448     #[inline]
 449     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 450     pub fn shrink_to_fit(&mut self) {
 451         self.vec.shrink_to_fit()
 452     }
 453
 454     /// Adds the given character to the end of the string.
 455     ///
 456     /// # Example
 457     ///
 458     /// ```
 459     /// let mut s = String::from_str("abc");
 460     /// s.push('1');
 461     /// s.push('2');
 462     /// s.push('3');
 463     /// assert_eq!(s.as_slice(), "abc123");
 464     /// ```
 465     #[inline]
 466     #[stable = "function just renamed from push_char"]
 467     pub fn push(&mut self, ch: char) {
 468         let cur_len = self.len();
 469         // This may use up to 4 bytes.
 470         self.vec.reserve(4);
 471
 472         unsafe {
 473             // Attempt to not use an intermediate buffer by just pushing bytes
 474             // directly onto this string.
 475             let slice = RawSlice {
 476                 data: self.vec.as_ptr().offset(cur_len as int),
 477                 len: 4,
 478             };
 479             let used = ch.encode_utf8(mem::transmute(slice)).unwrap_or(0);
 480             self.vec.set_len(cur_len + used);
 481         }
 482     }
 483
 484     /// Works with the underlying buffer as a byte slice.
 485     ///
 486     /// # Example
 487     ///
 488     /// ```
 489     /// let s = String::from_str("hello");
 490     /// let b: &[_] = &[104, 101, 108, 108, 111];
 491     /// assert_eq!(s.as_bytes(), b);
 492     /// ```
 493     #[inline]
 494     #[stable]
 495     pub fn as_bytes<'a>(&'a self) -> &'a [u8] {
 496         self.vec.as_slice()
 497     }
 498
 499     /// Shortens a string to the specified length.
 500     ///
 501     /// # Failure
 502     ///
 503     /// Fails if `new_len` > current length,
 504     /// or if `new_len` is not a character boundary.
 505     ///
 506     /// # Example
 507     ///
 508     /// ```
 509     /// let mut s = String::from_str("hello");
 510     /// s.truncate(2);
 511     /// assert_eq!(s.as_slice(), "he");
 512     /// ```
 513     #[inline]
 514     #[unstable = "the panic conventions for strings are under development"]
 515     pub fn truncate(&mut self, new_len: uint) {
 516         assert!(self.as_slice().is_char_boundary(new_len));
 517         self.vec.truncate(new_len)
 518     }
 519
 520     /// Removes the last character from the string buffer and returns it.
 521     /// Returns `None` if this string buffer is empty.
 522     ///
 523     /// # Example
 524     ///
 525     /// ```
 526     /// let mut s = String::from_str("foo");
 527     /// assert_eq!(s.pop(), Some('o'));
 528     /// assert_eq!(s.pop(), Some('o'));
 529     /// assert_eq!(s.pop(), Some('f'));
 530     /// assert_eq!(s.pop(), None);
 531     /// ```
 532     #[inline]
 533     #[unstable = "this function was just renamed from pop_char"]
 534     pub fn pop(&mut self) -> Option<char> {
 535         let len = self.len();
 536         if len == 0 {
 537             return None
 538         }
 539
 540         let CharRange {ch, next} = self.as_slice().char_range_at_reverse(len);
 541         unsafe {
 542             self.vec.set_len(next);
 543         }
 544         Some(ch)
 545     }
 546
 547     /// Removes the character from the string buffer at byte position `idx` and
 548     /// returns it. Returns `None` if `idx` is out of bounds.
 549     ///
 550     /// # Warning
 551     ///
 552     /// This is a O(n) operation as it requires copying every element in the
 553     /// buffer.
 554     ///
 555     /// # Panics
 556     ///
 557     /// If `idx` does not lie on a character boundary, then this function will
 558     /// panic.
 559     ///
 560     /// # Example
 561     ///
 562     /// ```
 563     /// let mut s = String::from_str("foo");
 564     /// assert_eq!(s.remove(0), Some('f'));
 565     /// assert_eq!(s.remove(1), Some('o'));
 566     /// assert_eq!(s.remove(0), Some('o'));
 567     /// assert_eq!(s.remove(0), None);
 568     /// ```
 569     #[unstable = "the panic semantics of this function and return type \
 570                   may change"]
 571     pub fn remove(&mut self, idx: uint) -> Option<char> {
 572         let len = self.len();
 573         if idx >= len { return None }
 574
 575         let CharRange { ch, next } = self.as_slice().char_range_at(idx);
 576         unsafe {
 577             ptr::copy_memory(self.vec.as_mut_ptr().offset(idx as int),
 578                              self.vec.as_ptr().offset(next as int),
 579                              len - next);
 580             self.vec.set_len(len - (next - idx));
 581         }
 582         Some(ch)
 583     }
 584
 585     /// Insert a character into the string buffer at byte position `idx`.
 586     ///
 587     /// # Warning
 588     ///
 589     /// This is a O(n) operation as it requires copying every element in the
 590     /// buffer.
 591     ///
 592     /// # Panics
 593     ///
 594     /// If `idx` does not lie on a character boundary or is out of bounds, then
 595     /// this function will panic.
 596     #[unstable = "the panic semantics of this function are uncertain"]
 597     pub fn insert(&mut self, idx: uint, ch: char) {
 598         let len = self.len();
 599         assert!(idx <= len);
 600         assert!(self.as_slice().is_char_boundary(idx));
 601         self.vec.reserve(4);
 602         let mut bits = [0, ..4];
 603         let amt = ch.encode_utf8(bits).unwrap();
 604
 605         unsafe {
 606             ptr::copy_memory(self.vec.as_mut_ptr().offset((idx + amt) as int),
 607                              self.vec.as_ptr().offset(idx as int),
 608                              len - idx);
 609             ptr::copy_memory(self.vec.as_mut_ptr().offset(idx as int),
 610                              bits.as_ptr(),
 611                              amt);
 612             self.vec.set_len(len + amt);
 613         }
 614     }
 615
 616     /// Views the string buffer as a mutable sequence of bytes.
 617     ///
 618     /// This is unsafe because it does not check
 619     /// to ensure that the resulting string will be valid UTF-8.
 620     ///
 621     /// # Example
 622     ///
 623     /// ```
 624     /// let mut s = String::from_str("hello");
 625     /// unsafe {
 626     ///     let vec = s.as_mut_vec();
 627     ///     assert!(vec == &mut vec![104, 101, 108, 108, 111]);
 628     ///     vec.reverse();
 629     /// }
 630     /// assert_eq!(s.as_slice(), "olleh");
 631     /// ```
 632     #[unstable = "the name of this method may be changed"]
 633     pub unsafe fn as_mut_vec<'a>(&'a mut self) -> &'a mut Vec<u8> {
 634         &mut self.vec
 635     }
 636
 637     /// Return the number of bytes in this string.
 638     ///
 639     /// # Example
 640     ///
 641     /// ```
 642     /// let a = "foo".to_string();
 643     /// assert_eq!(a.len(), 3);
 644     /// ```
 645     #[inline]
 646     #[stable]
 647     pub fn len(&self) -> uint { self.vec.len() }
 648
 649     /// Returns true if the string contains no bytes
 650     ///
 651     /// # Example
 652     ///
 653     /// ```
 654     /// let mut v = String::new();
 655     /// assert!(v.is_empty());
 656     /// v.push('a');
 657     /// assert!(!v.is_empty());
 658     /// ```
 659     pub fn is_empty(&self) -> bool { self.len() == 0 }
 660
 661     /// Truncates the string, returning it to 0 length.
 662     ///
 663     /// # Example
 664     ///
 665     /// ```
 666     /// let mut s = "foo".to_string();
 667     /// s.clear();
 668     /// assert!(s.is_empty());
 669     /// ```
 670     #[inline]
 671     #[stable]
 672     pub fn clear(&mut self) {
 673         self.vec.clear()
 674     }
 675 }
 676
 677 #[experimental = "waiting on FromIterator stabilization"]
 678 impl FromIterator<char> for String {
 679     fn from_iter<I:Iterator<char>>(iterator: I) -> String {
 680         let mut buf = String::new();
 681         buf.extend(iterator);
 682         buf
 683     }
 684 }
 685
 686 #[experimental = "waiting on Extend stabilization"]
 687 impl Extend<char> for String {
 688     fn extend<I:Iterator<char>>(&mut self, mut iterator: I) {
 689         for ch in iterator {
 690             self.push(ch)
 691         }
 692     }
 693 }
 694
 695 #[experimental = "waiting on Str stabilization"]
 696 impl Str for String {
 697     #[inline]
 698     #[stable]
 699     fn as_slice<'a>(&'a self) -> &'a str {
 700         unsafe {
 701             mem::transmute(self.vec.as_slice())
 702         }
 703     }
 704 }
 705
 706 #[experimental = "waiting on StrAllocating stabilization"]
 707 impl StrAllocating for String {
 708     #[inline]
 709     fn into_string(self) -> String {
 710         self
 711     }
 712 }
 713
 714 #[stable]
 715 impl Default for String {
 716     fn default() -> String {
 717         String::new()
 718     }
 719 }
 720
 721 #[experimental = "waiting on Show stabilization"]
 722 impl fmt::Show for String {
 723     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 724         self.as_slice().fmt(f)
 725     }
 726 }
 727
 728 #[experimental = "waiting on Hash stabilization"]
 729 impl<H: hash::Writer> hash::Hash<H> for String {
 730     #[inline]
 731     fn hash(&self, hasher: &mut H) {
 732         self.as_slice().hash(hasher)
 733     }
 734 }
 735
 736 #[experimental = "waiting on Equiv stabilization"]
 737 impl<'a, S: Str> Equiv<S> for String {
 738     #[inline]
 739     fn equiv(&self, other: &S) -> bool {
 740         self.as_slice() == other.as_slice()
 741     }
 742 }
 743
 744 #[experimental = "waiting on Add stabilization"]
 745 impl<S: Str> Add<S, String> for String {
 746     fn add(&self, other: &S) -> String {
 747         let mut s = String::from_str(self.as_slice());
 748         s.push_str(other.as_slice());
 749         return s;
 750     }
 751 }
 752
 753 impl ops::Slice<uint, str> for String {
 754     #[inline]
 755     fn as_slice_<'a>(&'a self) -> &'a str {
 756         self.as_slice()
 757     }
 758
 759     #[inline]
 760     fn slice_from_or_fail<'a>(&'a self, from: &uint) -> &'a str {
 761         self[][*from..]
 762     }
 763
 764     #[inline]
 765     fn slice_to_or_fail<'a>(&'a self, to: &uint) -> &'a str {
 766         self[][..*to]
 767     }
 768
 769     #[inline]
 770     fn slice_or_fail<'a>(&'a self, from: &uint, to: &uint) -> &'a str {
 771         self[][*from..*to]
 772     }
 773 }
 774
 775 #[experimental = "waiting on Deref stabilization"]
 776 impl ops::Deref<str> for String {
 777     fn deref<'a>(&'a self) -> &'a str { self.as_slice() }
 778 }
 779
 780 /// Wrapper type providing a `&String` reference via `Deref`.
 781 #[experimental]
 782 pub struct DerefString<'a> {
 783     x: DerefVec<'a, u8>
 784 }
 785
 786 impl<'a> Deref<String> for DerefString<'a> {
 787     fn deref<'b>(&'b self) -> &'b String {
 788         unsafe { mem::transmute(&*self.x) }
 789     }
 790 }
 791
 792 /// Convert a string slice to a wrapper type providing a `&String` reference.
 793 #[experimental]
 794 pub fn as_string<'a>(x: &'a str) -> DerefString<'a> {
 795     DerefString { x: as_vec(x.as_bytes()) }
 796 }
 797
 798 /// Unsafe operations
 799 #[unstable = "waiting on raw module conventions"]
 800 pub mod raw {
 801     use core::mem;
 802     use core::ptr::RawPtr;
 803     use core::raw::Slice;
 804
 805     use super::String;
 806     use vec::Vec;
 807
 808     /// Creates a new `String` from a length, capacity, and pointer.
 809     ///
 810     /// This is unsafe because:
 811     /// * We call `Vec::from_raw_parts` to get a `Vec<u8>`;
 812     /// * We assume that the `Vec` contains valid UTF-8.
 813     #[inline]
 814     pub unsafe fn from_parts(buf: *mut u8, length: uint, capacity: uint) -> String {
 815         String {
 816             vec: Vec::from_raw_parts(buf, length, capacity),
 817         }
 818     }
 819
 820     /// Creates a `String` from a `*const u8` buffer of the given length.
 821     ///
 822     /// This function is unsafe because of two reasons:
 823     /// * A raw pointer is dereferenced and transmuted to `&[u8]`;
 824     /// * The slice is not checked to see whether it contains valid UTF-8.
 825     pub unsafe fn from_buf_len(buf: *const u8, len: uint) -> String {
 826         use slice::CloneSliceAllocPrelude;
 827         let slice: &[u8] = mem::transmute(Slice {
 828             data: buf,
 829             len: len,
 830         });
 831         self::from_utf8(slice.to_vec())
 832     }
 833
 834     /// Creates a `String` from a null-terminated `*const u8` buffer.
 835     ///
 836     /// This function is unsafe because we dereference memory until we find the NUL character,
 837     /// which is not guaranteed to be present. Additionally, the slice is not checked to see
 838     /// whether it contains valid UTF-8
 839     pub unsafe fn from_buf(buf: *const u8) -> String {
 840         let mut len = 0;
 841         while *buf.offset(len) != 0 {
 842             len += 1;
 843         }
 844         self::from_buf_len(buf, len as uint)
 845     }
 846
 847     /// Converts a vector of bytes to a new `String` without checking if
 848     /// it contains valid UTF-8. This is unsafe because it assumes that
 849     /// the UTF-8-ness of the vector has already been validated.
 850     #[inline]
 851     pub unsafe fn from_utf8(bytes: Vec<u8>) -> String {
 852         String { vec: bytes }
 853     }
 854 }
 855
 856 #[cfg(test)]
 857 mod tests {
 858     use std::prelude::*;
 859     use test::Bencher;
 860
 861     use str;
 862     use str::{Str, StrPrelude, Owned};
 863     use super::{as_string, String};
 864     use vec::Vec;
 865     use slice::CloneSliceAllocPrelude;
 866
 867     #[test]
 868     fn test_as_string() {
 869         let x = "foo";
 870         assert_eq!(x, as_string(x).as_slice());
 871     }
 872
 873     #[test]
 874     fn test_from_str() {
 875       let owned: Option<::std::string::String> = from_str("string");
 876       assert_eq!(owned.as_ref().map(|s| s.as_slice()), Some("string"));
 877     }
 878
 879     #[test]
 880     fn test_from_utf8() {
 881         let xs = b"hello".to_vec();
 882         assert_eq!(String::from_utf8(xs), Ok(String::from_str("hello")));
 883
 884         let xs = "ศไทย中华Việt Nam".as_bytes().to_vec();
 885         assert_eq!(String::from_utf8(xs), Ok(String::from_str("ศไทย中华Việt Nam")));
 886
 887         let xs = b"hello\xFF".to_vec();
 888         assert_eq!(String::from_utf8(xs),
 889                    Err(b"hello\xFF".to_vec()));
 890     }
 891
 892     #[test]
 893     fn test_from_utf8_lossy() {
 894         let xs = b"hello";
 895         assert_eq!(String::from_utf8_lossy(xs), str::Slice("hello"));
 896
 897         let xs = "ศไทย中华Việt Nam".as_bytes();
 898         assert_eq!(String::from_utf8_lossy(xs), str::Slice("ศไทย中华Việt Nam"));
 899
 900         let xs = b"Hello\xC2 There\xFF Goodbye";
 901         assert_eq!(String::from_utf8_lossy(xs),
 902                    Owned(String::from_str("Hello\uFFFD There\uFFFD Goodbye")));
 903
 904         let xs = b"Hello\xC0\x80 There\xE6\x83 Goodbye";
 905         assert_eq!(String::from_utf8_lossy(xs),
 906                    Owned(String::from_str("Hello\uFFFD\uFFFD There\uFFFD Goodbye")));
 907
 908         let xs = b"\xF5foo\xF5\x80bar";
 909         assert_eq!(String::from_utf8_lossy(xs),
 910                    Owned(String::from_str("\uFFFDfoo\uFFFD\uFFFDbar")));
 911
 912         let xs = b"\xF1foo\xF1\x80bar\xF1\x80\x80baz";
 913         assert_eq!(String::from_utf8_lossy(xs),
 914                    Owned(String::from_str("\uFFFDfoo\uFFFDbar\uFFFDbaz")));
 915
 916         let xs = b"\xF4foo\xF4\x80bar\xF4\xBFbaz";
 917         assert_eq!(String::from_utf8_lossy(xs),
 918                    Owned(String::from_str("\uFFFDfoo\uFFFDbar\uFFFD\uFFFDbaz")));
 919
 920         let xs = b"\xF0\x80\x80\x80foo\xF0\x90\x80\x80bar";
 921         assert_eq!(String::from_utf8_lossy(xs), Owned(String::from_str("\uFFFD\uFFFD\uFFFD\uFFFD\
 922                                                foo\U00010000bar")));
 923
 924         // surrogates
 925         let xs = b"\xED\xA0\x80foo\xED\xBF\xBFbar";
 926         assert_eq!(String::from_utf8_lossy(xs), Owned(String::from_str("\uFFFD\uFFFD\uFFFDfoo\
 927                                                \uFFFD\uFFFD\uFFFDbar")));
 928     }
 929
 930     #[test]
 931     fn test_from_utf16() {
 932         let pairs =
 933             [(String::from_str("𐍅𐌿𐌻𐍆𐌹𐌻𐌰\n"),
 934               vec![0xd800_u16, 0xdf45_u16, 0xd800_u16, 0xdf3f_u16,
 935                 0xd800_u16, 0xdf3b_u16, 0xd800_u16, 0xdf46_u16,
 936                 0xd800_u16, 0xdf39_u16, 0xd800_u16, 0xdf3b_u16,
 937                 0xd800_u16, 0xdf30_u16, 0x000a_u16]),
 938
 939              (String::from_str("𐐒𐑉𐐮𐑀𐐲𐑋 𐐏𐐲𐑍\n"),
 940               vec![0xd801_u16, 0xdc12_u16, 0xd801_u16,
 941                 0xdc49_u16, 0xd801_u16, 0xdc2e_u16, 0xd801_u16,
 942                 0xdc40_u16, 0xd801_u16, 0xdc32_u16, 0xd801_u16,
 943                 0xdc4b_u16, 0x0020_u16, 0xd801_u16, 0xdc0f_u16,
 944                 0xd801_u16, 0xdc32_u16, 0xd801_u16, 0xdc4d_u16,
 945                 0x000a_u16]),
 946
 947              (String::from_str("𐌀𐌖𐌋𐌄𐌑𐌉·𐌌𐌄𐌕𐌄𐌋𐌉𐌑\n"),
 948               vec![0xd800_u16, 0xdf00_u16, 0xd800_u16, 0xdf16_u16,
 949                 0xd800_u16, 0xdf0b_u16, 0xd800_u16, 0xdf04_u16,
 950                 0xd800_u16, 0xdf11_u16, 0xd800_u16, 0xdf09_u16,
 951                 0x00b7_u16, 0xd800_u16, 0xdf0c_u16, 0xd800_u16,
 952                 0xdf04_u16, 0xd800_u16, 0xdf15_u16, 0xd800_u16,
 953                 0xdf04_u16, 0xd800_u16, 0xdf0b_u16, 0xd800_u16,
 954                 0xdf09_u16, 0xd800_u16, 0xdf11_u16, 0x000a_u16 ]),
 955
 956              (String::from_str("𐒋𐒘𐒈𐒑𐒛𐒒 𐒕𐒓 𐒈𐒚𐒍 𐒏𐒜𐒒𐒖𐒆 𐒕𐒆\n"),
 957               vec![0xd801_u16, 0xdc8b_u16, 0xd801_u16, 0xdc98_u16,
 958                 0xd801_u16, 0xdc88_u16, 0xd801_u16, 0xdc91_u16,
 959                 0xd801_u16, 0xdc9b_u16, 0xd801_u16, 0xdc92_u16,
 960                 0x0020_u16, 0xd801_u16, 0xdc95_u16, 0xd801_u16,
 961                 0xdc93_u16, 0x0020_u16, 0xd801_u16, 0xdc88_u16,
 962                 0xd801_u16, 0xdc9a_u16, 0xd801_u16, 0xdc8d_u16,
 963                 0x0020_u16, 0xd801_u16, 0xdc8f_u16, 0xd801_u16,
 964                 0xdc9c_u16, 0xd801_u16, 0xdc92_u16, 0xd801_u16,
 965                 0xdc96_u16, 0xd801_u16, 0xdc86_u16, 0x0020_u16,
 966                 0xd801_u16, 0xdc95_u16, 0xd801_u16, 0xdc86_u16,
 967                 0x000a_u16 ]),
 968              // Issue #12318, even-numbered non-BMP planes
 969              (String::from_str("\U00020000"),
 970               vec![0xD840, 0xDC00])];
 971
 972         for p in pairs.iter() {
 973             let (s, u) = (*p).clone();
 974             let s_as_utf16 = s.as_slice().utf16_units().collect::<Vec<u16>>();
 975             let u_as_string = String::from_utf16(u.as_slice()).unwrap();
 976
 977             assert!(str::is_utf16(u.as_slice()));
 978             assert_eq!(s_as_utf16, u);
 979
 980             assert_eq!(u_as_string, s);
 981             assert_eq!(String::from_utf16_lossy(u.as_slice()), s);
 982
 983             assert_eq!(String::from_utf16(s_as_utf16.as_slice()).unwrap(), s);
 984             assert_eq!(u_as_string.as_slice().utf16_units().collect::<Vec<u16>>(), u);
 985         }
 986     }
 987
 988     #[test]
 989     fn test_utf16_invalid() {
 990         // completely positive cases tested above.
 991         // lead + eof
 992         assert_eq!(String::from_utf16([0xD800]), None);
 993         // lead + lead
 994         assert_eq!(String::from_utf16([0xD800, 0xD800]), None);
 995
 996         // isolated trail
 997         assert_eq!(String::from_utf16([0x0061, 0xDC00]), None);
 998
 999         // general
1000         assert_eq!(String::from_utf16([0xD800, 0xd801, 0xdc8b, 0xD800]), None);
1001     }
1002
1003     #[test]
1004     fn test_from_utf16_lossy() {
1005         // completely positive cases tested above.
1006         // lead + eof
1007         assert_eq!(String::from_utf16_lossy([0xD800]), String::from_str("\uFFFD"));
1008         // lead + lead
1009         assert_eq!(String::from_utf16_lossy([0xD800, 0xD800]), String::from_str("\uFFFD\uFFFD"));
1010
1011         // isolated trail
1012         assert_eq!(String::from_utf16_lossy([0x0061, 0xDC00]), String::from_str("a\uFFFD"));
1013
1014         // general
1015         assert_eq!(String::from_utf16_lossy([0xD800, 0xd801, 0xdc8b, 0xD800]),
1016                    String::from_str("\uFFFD𐒋\uFFFD"));
1017     }
1018
1019     #[test]
1020     fn test_from_buf_len() {
1021         unsafe {
1022             let a = vec![65u8, 65, 65, 65, 65, 65, 65, 0];
1023             assert_eq!(super::raw::from_buf_len(a.as_ptr(), 3), String::from_str("AAA"));
1024         }
1025     }
1026
1027     #[test]
1028     fn test_from_buf() {
1029         unsafe {
1030             let a = vec![65, 65, 65, 65, 65, 65, 65, 0];
1031             let b = a.as_ptr();
1032             let c = super::raw::from_buf(b);
1033             assert_eq!(c, String::from_str("AAAAAAA"));
1034         }
1035     }
1036
1037     #[test]
1038     fn test_push_bytes() {
1039         let mut s = String::from_str("ABC");
1040         unsafe {
1041             let mv = s.as_mut_vec();
1042             mv.push_all([b'D']);
1043         }
1044         assert_eq!(s.as_slice(), "ABCD");
1045     }
1046
1047     #[test]
1048     fn test_push_str() {
1049         let mut s = String::new();
1050         s.push_str("");
1051         assert_eq!(s.as_slice().slice_from(0), "");
1052         s.push_str("abc");
1053         assert_eq!(s.as_slice().slice_from(0), "abc");
1054         s.push_str("ประเทศไทย中华Việt Nam");
1055         assert_eq!(s.as_slice().slice_from(0), "abcประเทศไทย中华Việt Nam");
1056     }
1057
1058     #[test]
1059     fn test_push() {
1060         let mut data = String::from_str("ประเทศไทย中");
1061         data.push('华');
1062         data.push('b'); // 1 byte
1063         data.push('¢'); // 2 byte
1064         data.push('€'); // 3 byte
1065         data.push('𤭢'); // 4 byte
1066         assert_eq!(data.as_slice(), "ประเทศไทย中华b¢€𤭢");
1067     }
1068
1069     #[test]
1070     fn test_pop() {
1071         let mut data = String::from_str("ประเทศไทย中华b¢€𤭢");
1072         assert_eq!(data.pop().unwrap(), '𤭢'); // 4 bytes
1073         assert_eq!(data.pop().unwrap(), '€'); // 3 bytes
1074         assert_eq!(data.pop().unwrap(), '¢'); // 2 bytes
1075         assert_eq!(data.pop().unwrap(), 'b'); // 1 bytes
1076         assert_eq!(data.pop().unwrap(), '华');
1077         assert_eq!(data.as_slice(), "ประเทศไทย中");
1078     }
1079
1080     #[test]
1081     fn test_str_truncate() {
1082         let mut s = String::from_str("12345");
1083         s.truncate(5);
1084         assert_eq!(s.as_slice(), "12345");
1085         s.truncate(3);
1086         assert_eq!(s.as_slice(), "123");
1087         s.truncate(0);
1088         assert_eq!(s.as_slice(), "");
1089
1090         let mut s = String::from_str("12345");
1091         let p = s.as_slice().as_ptr();
1092         s.truncate(3);
1093         s.push_str("6");
1094         let p_ = s.as_slice().as_ptr();
1095         assert_eq!(p_, p);
1096     }
1097
1098     #[test]
1099     #[should_fail]
1100     fn test_str_truncate_invalid_len() {
1101         let mut s = String::from_str("12345");
1102         s.truncate(6);
1103     }
1104
1105     #[test]
1106     #[should_fail]
1107     fn test_str_truncate_split_codepoint() {
1108         let mut s = String::from_str("\u00FC"); // ü
1109         s.truncate(1);
1110     }
1111
1112     #[test]
1113     fn test_str_clear() {
1114         let mut s = String::from_str("12345");
1115         s.clear();
1116         assert_eq!(s.len(), 0);
1117         assert_eq!(s.as_slice(), "");
1118     }
1119
1120     #[test]
1121     fn test_str_add() {
1122         let a = String::from_str("12345");
1123         let b = a + "2";
1124         let b = b + String::from_str("2");
1125         assert_eq!(b.len(), 7);
1126         assert_eq!(b.as_slice(), "1234522");
1127     }
1128
1129     #[test]
1130     fn remove() {
1131         let mut s = "ศไทย中华Việt Nam; foobar".to_string();;
1132         assert_eq!(s.remove(0), Some('ศ'));
1133         assert_eq!(s.len(), 33);
1134         assert_eq!(s.as_slice(), "ไทย中华Việt Nam; foobar");
1135         assert_eq!(s.remove(33), None);
1136         assert_eq!(s.remove(300), None);
1137         assert_eq!(s.remove(17), Some('ệ'));
1138         assert_eq!(s.as_slice(), "ไทย中华Vit Nam; foobar");
1139     }
1140
1141     #[test] #[should_fail]
1142     fn remove_bad() {
1143         "ศ".to_string().remove(1);
1144     }
1145
1146     #[test]
1147     fn insert() {
1148         let mut s = "foobar".to_string();
1149         s.insert(0, 'ệ');
1150         assert_eq!(s.as_slice(), "ệfoobar");
1151         s.insert(6, 'ย');
1152         assert_eq!(s.as_slice(), "ệfooยbar");
1153     }
1154
1155     #[test] #[should_fail] fn insert_bad1() { "".to_string().insert(1, 't'); }
1156     #[test] #[should_fail] fn insert_bad2() { "ệ".to_string().insert(1, 't'); }
1157
1158     #[test]
1159     fn test_slicing() {
1160         let s = "foobar".to_string();
1161         assert_eq!("foobar", s[]);
1162         assert_eq!("foo", s[..3]);
1163         assert_eq!("bar", s[3..]);
1164         assert_eq!("oob", s[1..4]);
1165     }
1166
1167     #[bench]
1168     fn bench_with_capacity(b: &mut Bencher) {
1169         b.iter(|| {
1170             String::with_capacity(100)
1171         });
1172     }
1173
1174     #[bench]
1175     fn bench_push_str(b: &mut Bencher) {
1176         let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
1177         b.iter(|| {
1178             let mut r = String::new();
1179             r.push_str(s);
1180         });
1181     }
1182
1183     #[bench]
1184     fn from_utf8_lossy_100_ascii(b: &mut Bencher) {
1185         let s = b"Hello there, the quick brown fox jumped over the lazy dog! \
1186                   Lorem ipsum dolor sit amet, consectetur. ";
1187
1188         assert_eq!(100, s.len());
1189         b.iter(|| {
1190             let _ = String::from_utf8_lossy(s);
1191         });
1192     }
1193
1194     #[bench]
1195     fn from_utf8_lossy_100_multibyte(b: &mut Bencher) {
1196         let s = "𐌀𐌖𐌋𐌄𐌑𐌉ปรدولة الكويتทศไทย中华𐍅𐌿𐌻𐍆𐌹𐌻𐌰".as_bytes();
1197         assert_eq!(100, s.len());
1198         b.iter(|| {
1199             let _ = String::from_utf8_lossy(s);
1200         });
1201     }
1202
1203     #[bench]
1204     fn from_utf8_lossy_invalid(b: &mut Bencher) {
1205         let s = b"Hello\xC0\x80 There\xE6\x83 Goodbye";
1206         b.iter(|| {
1207             let _ = String::from_utf8_lossy(s);
1208         });
1209     }
1210
1211     #[bench]
1212     fn from_utf8_lossy_100_invalid(b: &mut Bencher) {
1213         let s = Vec::from_elem(100, 0xF5u8);
1214         b.iter(|| {
1215             let _ = String::from_utf8_lossy(s.as_slice());
1216         });
1217     }
1218 }