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 //! An owned, growable string that enforces that its contents are valid UTF-8.
  12
  13 use core::prelude::*;
  14
  15 use core::default::Default;
  16 use core::fmt;
  17 use core::mem;
  18 use core::ptr;
  19 use core::raw::Slice;
  20
  21 use {Collection, Mutable};
  22 use hash;
  23 use str;
  24 use str::{CharRange, StrAllocating};
  25 use vec::Vec;
  26
  27 /// A growable string stored as a UTF-8 encoded buffer.
  28 #[deriving(Clone, PartialEq, PartialOrd, Eq, Ord)]
  29 pub struct String {
  30     vec: Vec<u8>,
  31 }
  32
  33 impl String {
  34     /// Creates a new string buffer initialized with the empty string.
  35     #[inline]
  36     pub fn new() -> String {
  37         String {
  38             vec: Vec::new(),
  39         }
  40     }
  41
  42     /// Creates a new string buffer with the given capacity.
  43     #[inline]
  44     pub fn with_capacity(capacity: uint) -> String {
  45         String {
  46             vec: Vec::with_capacity(capacity),
  47         }
  48     }
  49
  50     /// Creates a new string buffer from length, capacity, and a pointer.
  51     #[inline]
  52     pub unsafe fn from_raw_parts(length: uint, capacity: uint, ptr: *mut u8) -> String {
  53         String {
  54             vec: Vec::from_raw_parts(length, capacity, ptr),
  55         }
  56     }
  57
  58     /// Creates a new string buffer from the given string.
  59     #[inline]
  60     pub fn from_str(string: &str) -> String {
  61         String {
  62             vec: Vec::from_slice(string.as_bytes())
  63         }
  64     }
  65
  66     #[allow(missing_doc)]
  67     #[deprecated = "obsoleted by the removal of ~str"]
  68     #[inline]
  69     pub fn from_owned_str(string: String) -> String {
  70         string
  71     }
  72
  73     /// Returns the vector as a string buffer, if possible, taking care not to
  74     /// copy it.
  75     ///
  76     /// Returns `Err` with the original vector if the vector contains invalid
  77     /// UTF-8.
  78     #[inline]
  79     pub fn from_utf8(vec: Vec<u8>) -> Result<String, Vec<u8>> {
  80         if str::is_utf8(vec.as_slice()) {
  81             Ok(String { vec: vec })
  82         } else {
  83             Err(vec)
  84         }
  85     }
  86
  87     /// Return the underlying byte buffer, encoded as UTF-8.
  88     #[inline]
  89     pub fn into_bytes(self) -> Vec<u8> {
  90         self.vec
  91     }
  92
  93     /// Pushes the given string onto this buffer; then, returns `self` so that it can be used
  94     /// again.
  95     #[inline]
  96     pub fn append(mut self, second: &str) -> String {
  97         self.push_str(second);
  98         self
  99     }
 100
 101     /// Creates a string buffer by repeating a character `length` times.
 102     #[inline]
 103     pub fn from_char(length: uint, ch: char) -> String {
 104         if length == 0 {
 105             return String::new()
 106         }
 107
 108         let mut buf = String::new();
 109         buf.push_char(ch);
 110         let size = buf.len() * length;
 111         buf.reserve(size);
 112         for _ in range(1, length) {
 113             buf.push_char(ch)
 114         }
 115         buf
 116     }
 117
 118     /// Pushes the given string onto this string buffer.
 119     #[inline]
 120     pub fn push_str(&mut self, string: &str) {
 121         self.vec.push_all(string.as_bytes())
 122     }
 123
 124     /// Push `ch` onto the given string `count` times.
 125     #[inline]
 126     pub fn grow(&mut self, count: uint, ch: char) {
 127         for _ in range(0, count) {
 128             self.push_char(ch)
 129         }
 130     }
 131
 132     /// Returns the number of bytes that this string buffer can hold without reallocating.
 133     #[inline]
 134     pub fn byte_capacity(&self) -> uint {
 135         self.vec.capacity()
 136     }
 137
 138     /// Reserves capacity for at least `extra` additional bytes in this string buffer.
 139     #[inline]
 140     pub fn reserve_additional(&mut self, extra: uint) {
 141         self.vec.reserve_additional(extra)
 142     }
 143
 144     /// Reserves capacity for at least `capacity` bytes in this string buffer.
 145     #[inline]
 146     pub fn reserve(&mut self, capacity: uint) {
 147         self.vec.reserve(capacity)
 148     }
 149
 150     /// Reserves capacity for exactly `capacity` bytes in this string buffer.
 151     #[inline]
 152     pub fn reserve_exact(&mut self, capacity: uint) {
 153         self.vec.reserve_exact(capacity)
 154     }
 155
 156     /// Shrinks the capacity of this string buffer to match its length.
 157     #[inline]
 158     pub fn shrink_to_fit(&mut self) {
 159         self.vec.shrink_to_fit()
 160     }
 161
 162     /// Adds the given character to the end of the string.
 163     #[inline]
 164     pub fn push_char(&mut self, ch: char) {
 165         let cur_len = self.len();
 166         // This may use up to 4 bytes.
 167         self.vec.reserve_additional(4);
 168
 169         unsafe {
 170             // Attempt to not use an intermediate buffer by just pushing bytes
 171             // directly onto this string.
 172             let slice = Slice {
 173                 data: self.vec.as_ptr().offset(cur_len as int),
 174                 len: 4,
 175             };
 176             let used = ch.encode_utf8(mem::transmute(slice));
 177             self.vec.set_len(cur_len + used);
 178         }
 179     }
 180
 181     /// Pushes the given bytes onto this string buffer. This is unsafe because it does not check
 182     /// to ensure that the resulting string will be valid UTF-8.
 183     #[inline]
 184     pub unsafe fn push_bytes(&mut self, bytes: &[u8]) {
 185         self.vec.push_all(bytes)
 186     }
 187
 188     /// Works with the underlying buffer as a byte slice.
 189     #[inline]
 190     pub fn as_bytes<'a>(&'a self) -> &'a [u8] {
 191         self.vec.as_slice()
 192     }
 193
 194     /// Works with the underlying buffer as a mutable byte slice. Unsafe
 195     /// because this can be used to violate the UTF-8 property.
 196     #[inline]
 197     pub unsafe fn as_mut_bytes<'a>(&'a mut self) -> &'a mut [u8] {
 198         self.vec.as_mut_slice()
 199     }
 200
 201     /// Shorten a string to the specified length (which must be <= the current length)
 202     #[inline]
 203     pub fn truncate(&mut self, len: uint) {
 204         assert!(self.as_slice().is_char_boundary(len));
 205         self.vec.truncate(len)
 206     }
 207
 208     /// Appends a byte to this string buffer. The caller must preserve the valid UTF-8 property.
 209     #[inline]
 210     pub unsafe fn push_byte(&mut self, byte: u8) {
 211         self.push_bytes([byte])
 212     }
 213
 214     /// Removes the last byte from the string buffer and returns it. Returns `None` if this string
 215     /// buffer is empty.
 216     ///
 217     /// The caller must preserve the valid UTF-8 property.
 218     #[inline]
 219     pub unsafe fn pop_byte(&mut self) -> Option<u8> {
 220         let len = self.len();
 221         if len == 0 {
 222             return None
 223         }
 224
 225         let byte = self.as_bytes()[len - 1];
 226         self.vec.set_len(len - 1);
 227         Some(byte)
 228     }
 229
 230     /// Removes the last character from the string buffer and returns it. Returns `None` if this
 231     /// string buffer is empty.
 232     #[inline]
 233     pub fn pop_char(&mut self) -> Option<char> {
 234         let len = self.len();
 235         if len == 0 {
 236             return None
 237         }
 238
 239         let CharRange {ch, next} = self.as_slice().char_range_at_reverse(len);
 240         unsafe {
 241             self.vec.set_len(next);
 242         }
 243         Some(ch)
 244     }
 245
 246     /// Removes the first byte from the string buffer and returns it. Returns `None` if this string
 247     /// buffer is empty.
 248     ///
 249     /// The caller must preserve the valid UTF-8 property.
 250     pub unsafe fn shift_byte(&mut self) -> Option<u8> {
 251         self.vec.shift()
 252     }
 253
 254     /// Removes the first character from the string buffer and returns it. Returns `None` if this
 255     /// string buffer is empty.
 256     ///
 257     /// # Warning
 258     ///
 259     /// This is a O(n) operation as it requires copying every element in the buffer.
 260     pub fn shift_char (&mut self) -> Option<char> {
 261         let len = self.len();
 262         if len == 0 {
 263             return None
 264         }
 265
 266         let CharRange {ch, next} = self.as_slice().char_range_at(0);
 267         let new_len = len - next;
 268         unsafe {
 269             ptr::copy_memory(self.vec.as_mut_ptr(), self.vec.as_ptr().offset(next as int), new_len);
 270             self.vec.set_len(new_len);
 271         }
 272         Some(ch)
 273     }
 274
 275     /// Views the string buffer as a mutable sequence of bytes.
 276     ///
 277     /// Callers must preserve the valid UTF-8 property.
 278     pub unsafe fn as_mut_vec<'a>(&'a mut self) -> &'a mut Vec<u8> {
 279         &mut self.vec
 280     }
 281 }
 282
 283 impl Collection for String {
 284     #[inline]
 285     fn len(&self) -> uint {
 286         self.vec.len()
 287     }
 288 }
 289
 290 impl Mutable for String {
 291     #[inline]
 292     fn clear(&mut self) {
 293         self.vec.clear()
 294     }
 295 }
 296
 297 impl FromIterator<char> for String {
 298     fn from_iter<I:Iterator<char>>(iterator: I) -> String {
 299         let mut buf = String::new();
 300         buf.extend(iterator);
 301         buf
 302     }
 303 }
 304
 305 impl Extendable<char> for String {
 306     fn extend<I:Iterator<char>>(&mut self, mut iterator: I) {
 307         for ch in iterator {
 308             self.push_char(ch)
 309         }
 310     }
 311 }
 312
 313 impl Str for String {
 314     #[inline]
 315     fn as_slice<'a>(&'a self) -> &'a str {
 316         unsafe {
 317             mem::transmute(self.vec.as_slice())
 318         }
 319     }
 320 }
 321
 322 impl StrAllocating for String {
 323     #[inline]
 324     fn into_string(self) -> String {
 325         self
 326     }
 327 }
 328
 329 impl Default for String {
 330     fn default() -> String {
 331         String::new()
 332     }
 333 }
 334
 335 impl fmt::Show for String {
 336     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 337         self.as_slice().fmt(f)
 338     }
 339 }
 340
 341 impl<H: hash::Writer> hash::Hash<H> for String {
 342     #[inline]
 343     fn hash(&self, hasher: &mut H) {
 344         self.as_slice().hash(hasher)
 345     }
 346 }
 347
 348 impl<'a, S: Str> Equiv<S> for String {
 349     #[inline]
 350     fn equiv(&self, other: &S) -> bool {
 351         self.as_slice() == other.as_slice()
 352     }
 353 }
 354
 355 impl<S: Str> Add<S, String> for String {
 356     fn add(&self, other: &S) -> String {
 357         let mut s = self.to_string();
 358         s.push_str(other.as_slice());
 359         return s;
 360     }
 361 }
 362
 363 #[cfg(test)]
 364 mod tests {
 365     use std::prelude::*;
 366     use test::Bencher;
 367
 368     use Mutable;
 369     use str::{Str, StrSlice};
 370     use super::String;
 371
 372     #[bench]
 373     fn bench_with_capacity(b: &mut Bencher) {
 374         b.iter(|| {
 375             String::with_capacity(100)
 376         });
 377     }
 378
 379     #[bench]
 380     fn bench_push_str(b: &mut Bencher) {
 381         let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
 382         b.iter(|| {
 383             let mut r = String::new();
 384             r.push_str(s);
 385         });
 386     }
 387
 388     #[test]
 389     fn test_push_bytes() {
 390         let mut s = String::from_str("ABC");
 391         unsafe {
 392             s.push_bytes([ 'D' as u8 ]);
 393         }
 394         assert_eq!(s.as_slice(), "ABCD");
 395     }
 396
 397     #[test]
 398     fn test_push_str() {
 399         let mut s = String::new();
 400         s.push_str("");
 401         assert_eq!(s.as_slice().slice_from(0), "");
 402         s.push_str("abc");
 403         assert_eq!(s.as_slice().slice_from(0), "abc");
 404         s.push_str("ประเทศไทย中华Việt Nam");
 405         assert_eq!(s.as_slice().slice_from(0), "abcประเทศไทย中华Việt Nam");
 406     }
 407
 408     #[test]
 409     fn test_push_char() {
 410         let mut data = String::from_str("ประเทศไทย中");
 411         data.push_char('华');
 412         data.push_char('b'); // 1 byte
 413         data.push_char('¢'); // 2 byte
 414         data.push_char('€'); // 3 byte
 415         data.push_char('𤭢'); // 4 byte
 416         assert_eq!(data.as_slice(), "ประเทศไทย中华b¢€𤭢");
 417     }
 418
 419     #[test]
 420     fn test_pop_char() {
 421         let mut data = String::from_str("ประเทศไทย中华b¢€𤭢");
 422         assert_eq!(data.pop_char().unwrap(), '𤭢'); // 4 bytes
 423         assert_eq!(data.pop_char().unwrap(), '€'); // 3 bytes
 424         assert_eq!(data.pop_char().unwrap(), '¢'); // 2 bytes
 425         assert_eq!(data.pop_char().unwrap(), 'b'); // 1 bytes
 426         assert_eq!(data.pop_char().unwrap(), '华');
 427         assert_eq!(data.as_slice(), "ประเทศไทย中");
 428     }
 429
 430     #[test]
 431     fn test_shift_char() {
 432         let mut data = String::from_str("𤭢€¢b华ประเทศไทย中");
 433         assert_eq!(data.shift_char().unwrap(), '𤭢'); // 4 bytes
 434         assert_eq!(data.shift_char().unwrap(), '€'); // 3 bytes
 435         assert_eq!(data.shift_char().unwrap(), '¢'); // 2 bytes
 436         assert_eq!(data.shift_char().unwrap(), 'b'); // 1 bytes
 437         assert_eq!(data.shift_char().unwrap(), '华');
 438         assert_eq!(data.as_slice(), "ประเทศไทย中");
 439     }
 440
 441     #[test]
 442     fn test_str_truncate() {
 443         let mut s = String::from_str("12345");
 444         s.truncate(5);
 445         assert_eq!(s.as_slice(), "12345");
 446         s.truncate(3);
 447         assert_eq!(s.as_slice(), "123");
 448         s.truncate(0);
 449         assert_eq!(s.as_slice(), "");
 450
 451         let mut s = String::from_str("12345");
 452         let p = s.as_slice().as_ptr();
 453         s.truncate(3);
 454         s.push_str("6");
 455         let p_ = s.as_slice().as_ptr();
 456         assert_eq!(p_, p);
 457     }
 458
 459     #[test]
 460     #[should_fail]
 461     fn test_str_truncate_invalid_len() {
 462         let mut s = String::from_str("12345");
 463         s.truncate(6);
 464     }
 465
 466     #[test]
 467     #[should_fail]
 468     fn test_str_truncate_split_codepoint() {
 469         let mut s = String::from_str("\u00FC"); // ü
 470         s.truncate(1);
 471     }
 472
 473     #[test]
 474     fn test_str_clear() {
 475         let mut s = String::from_str("12345");
 476         s.clear();
 477         assert_eq!(s.len(), 0);
 478         assert_eq!(s.as_slice(), "");
 479     }
 480
 481     #[test]
 482     fn test_str_add() {
 483         let a = String::from_str("12345");
 484         let b = a + "2";
 485         let b = b + String::from_str("2");
 486         assert_eq!(b.len(), 7);
 487         assert_eq!(b.as_slice(), "1234522");
 488     }
 489 }