src/libstd/strbuf.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 c_vec::CVec;
  14 use char::Char;
  15 use cmp::Equiv;
  16 use container::{Container, Mutable};
  17 use fmt;
  18 use from_str::FromStr;
  19 use io::Writer;
  20 use iter::{Extendable, FromIterator, Iterator, range};
  21 use mem;
  22 use option::{None, Option, Some};
  23 use ptr::RawPtr;
  24 use ptr;
  25 use result::{Result, Ok, Err};
  26 use slice::Vector;
  27 use str::{CharRange, Str, StrSlice, StrAllocating};
  28 use str;
  29 use vec::Vec;
  30
  31 /// A growable string stored as a UTF-8 encoded buffer.
  32 #[deriving(Clone, Eq, Ord, TotalEq, TotalOrd)]
  33 pub struct StrBuf {
  34     vec: Vec<u8>,
  35 }
  36
  37 impl StrBuf {
  38     /// Creates a new string buffer initialized with the empty string.
  39     #[inline]
  40     pub fn new() -> StrBuf {
  41         StrBuf {
  42             vec: Vec::new(),
  43         }
  44     }
  45
  46     /// Creates a new string buffer with the given capacity.
  47     #[inline]
  48     pub fn with_capacity(capacity: uint) -> StrBuf {
  49         StrBuf {
  50             vec: Vec::with_capacity(capacity),
  51         }
  52     }
  53
  54     /// Creates a new string buffer from length, capacity, and a pointer.
  55     #[inline]
  56     pub unsafe fn from_raw_parts(length: uint, capacity: uint, ptr: *mut u8) -> StrBuf {
  57         StrBuf {
  58             vec: Vec::from_raw_parts(length, capacity, ptr),
  59         }
  60     }
  61
  62     /// Creates a new string buffer from the given string.
  63     #[inline]
  64     pub fn from_str(string: &str) -> StrBuf {
  65         StrBuf {
  66             vec: Vec::from_slice(string.as_bytes())
  67         }
  68     }
  69
  70     /// Creates a new string buffer from the given owned string, taking care not to copy it.
  71     #[inline]
  72     pub fn from_owned_str(string: StrBuf) -> StrBuf {
  73         string
  74     }
  75
  76     /// Returns the vector as a string buffer, if possible, taking care not to
  77     /// copy it.
  78     ///
  79     /// Returns `Err` with the original vector if the vector contains invalid
  80     /// UTF-8.
  81     #[inline]
  82     pub fn from_utf8(vec: Vec<u8>) -> Result<StrBuf, Vec<u8>> {
  83         if str::is_utf8(vec.as_slice()) {
  84             Ok(StrBuf { vec: vec })
  85         } else {
  86             Err(vec)
  87         }
  88     }
  89
  90     /// Return the underlying byte buffer, encoded as UTF-8.
  91     #[inline]
  92     pub fn into_bytes(self) -> Vec<u8> {
  93         self.vec
  94     }
  95
  96     /// Pushes the given string onto this buffer; then, returns `self` so that it can be used
  97     /// again.
  98     #[inline]
  99     pub fn append(mut self, second: &str) -> StrBuf {
 100         self.push_str(second);
 101         self
 102     }
 103
 104     /// Creates a string buffer by repeating a character `length` times.
 105     #[inline]
 106     pub fn from_char(length: uint, ch: char) -> StrBuf {
 107         if length == 0 {
 108             return StrBuf::new()
 109         }
 110
 111         let mut buf = StrBuf::new();
 112         buf.push_char(ch);
 113         let size = buf.len() * length;
 114         buf.reserve(size);
 115         for _ in range(1, length) {
 116             buf.push_char(ch)
 117         }
 118         buf
 119     }
 120
 121     /// Pushes the given string onto this string buffer.
 122     #[inline]
 123     pub fn push_str(&mut self, string: &str) {
 124         self.vec.push_all(string.as_bytes())
 125     }
 126
 127     /// Push `ch` onto the given string `count` times.
 128     #[inline]
 129     pub fn grow(&mut self, count: uint, ch: char) {
 130         for _ in range(0, count) {
 131             self.push_char(ch)
 132         }
 133     }
 134
 135     /// Returns the number of bytes that this string buffer can hold without reallocating.
 136     #[inline]
 137     pub fn byte_capacity(&self) -> uint {
 138         self.vec.capacity()
 139     }
 140
 141     /// Reserves capacity for at least `extra` additional bytes in this string buffer.
 142     #[inline]
 143     pub fn reserve_additional(&mut self, extra: uint) {
 144         self.vec.reserve_additional(extra)
 145     }
 146
 147     /// Reserves capacity for at least `capacity` bytes in this string buffer.
 148     #[inline]
 149     pub fn reserve(&mut self, capacity: uint) {
 150         self.vec.reserve(capacity)
 151     }
 152
 153     /// Reserves capacity for exactly `capacity` bytes in this string buffer.
 154     #[inline]
 155     pub fn reserve_exact(&mut self, capacity: uint) {
 156         self.vec.reserve_exact(capacity)
 157     }
 158
 159     /// Shrinks the capacity of this string buffer to match its length.
 160     #[inline]
 161     pub fn shrink_to_fit(&mut self) {
 162         self.vec.shrink_to_fit()
 163     }
 164
 165     /// Adds the given character to the end of the string.
 166     #[inline]
 167     pub fn push_char(&mut self, ch: char) {
 168         let cur_len = self.len();
 169         unsafe {
 170             // This may use up to 4 bytes.
 171             self.vec.reserve_additional(4);
 172
 173             // Attempt to not use an intermediate buffer by just pushing bytes
 174             // directly onto this string.
 175             let mut c_vector = CVec::new(self.vec.as_mut_ptr().offset(cur_len as int), 4);
 176             let used = ch.encode_utf8(c_vector.as_mut_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_slice()[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 Container for StrBuf {
 284     #[inline]
 285     fn len(&self) -> uint {
 286         self.vec.len()
 287     }
 288 }
 289
 290 impl Mutable for StrBuf {
 291     #[inline]
 292     fn clear(&mut self) {
 293         self.vec.clear()
 294     }
 295 }
 296
 297 impl FromIterator<char> for StrBuf {
 298     fn from_iter<I:Iterator<char>>(iterator: I) -> StrBuf {
 299         let mut buf = StrBuf::new();
 300         buf.extend(iterator);
 301         buf
 302     }
 303 }
 304
 305 impl Extendable<char> for StrBuf {
 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 StrBuf {
 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 StrBuf {
 323     #[inline]
 324     fn into_owned(self) -> StrBuf {
 325         self
 326     }
 327
 328     #[inline]
 329     fn into_strbuf(self) -> StrBuf {
 330         self
 331     }
 332 }
 333
 334 impl fmt::Show for StrBuf {
 335     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 336         self.as_slice().fmt(f)
 337     }
 338 }
 339
 340 impl<H:Writer> ::hash::Hash<H> for StrBuf {
 341     #[inline]
 342     fn hash(&self, hasher: &mut H) {
 343         self.as_slice().hash(hasher)
 344     }
 345 }
 346
 347 impl<'a, S: Str> Equiv<S> for StrBuf {
 348     #[inline]
 349     fn equiv(&self, other: &S) -> bool {
 350         self.as_slice() == other.as_slice()
 351     }
 352 }
 353
 354 impl FromStr for StrBuf {
 355     #[inline]
 356     fn from_str(s: &str) -> Option<StrBuf> {
 357         Some(s.to_strbuf())
 358     }
 359 }
 360
 361 #[cfg(test)]
 362 mod tests {
 363     extern crate test;
 364     use container::{Container, Mutable};
 365     use self::test::Bencher;
 366     use str::{Str, StrSlice};
 367     use super::StrBuf;
 368
 369     #[bench]
 370     fn bench_with_capacity(b: &mut Bencher) {
 371         b.iter(|| {
 372             StrBuf::with_capacity(100)
 373         });
 374     }
 375
 376     #[bench]
 377     fn bench_push_str(b: &mut Bencher) {
 378         let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
 379         b.iter(|| {
 380             let mut r = StrBuf::new();
 381             r.push_str(s);
 382         });
 383     }
 384
 385     #[test]
 386     fn test_push_bytes() {
 387         let mut s = StrBuf::from_str("ABC");
 388         unsafe {
 389             s.push_bytes([ 'D' as u8 ]);
 390         }
 391         assert_eq!(s.as_slice(), "ABCD");
 392     }
 393
 394     #[test]
 395     fn test_push_str() {
 396         let mut s = StrBuf::new();
 397         s.push_str("");
 398         assert_eq!(s.as_slice().slice_from(0), "");
 399         s.push_str("abc");
 400         assert_eq!(s.as_slice().slice_from(0), "abc");
 401         s.push_str("ประเทศไทย中华Việt Nam");
 402         assert_eq!(s.as_slice().slice_from(0), "abcประเทศไทย中华Việt Nam");
 403     }
 404
 405     #[test]
 406     fn test_push_char() {
 407         let mut data = StrBuf::from_str("ประเทศไทย中");
 408         data.push_char('华');
 409         data.push_char('b'); // 1 byte
 410         data.push_char('¢'); // 2 byte
 411         data.push_char('€'); // 3 byte
 412         data.push_char('𤭢'); // 4 byte
 413         assert_eq!(data.as_slice(), "ประเทศไทย中华b¢€𤭢");
 414     }
 415
 416     #[test]
 417     fn test_pop_char() {
 418         let mut data = StrBuf::from_str("ประเทศไทย中华b¢€𤭢");
 419         assert_eq!(data.pop_char().unwrap(), '𤭢'); // 4 bytes
 420         assert_eq!(data.pop_char().unwrap(), '€'); // 3 bytes
 421         assert_eq!(data.pop_char().unwrap(), '¢'); // 2 bytes
 422         assert_eq!(data.pop_char().unwrap(), 'b'); // 1 bytes
 423         assert_eq!(data.pop_char().unwrap(), '华');
 424         assert_eq!(data.as_slice(), "ประเทศไทย中");
 425     }
 426
 427     #[test]
 428     fn test_shift_char() {
 429         let mut data = StrBuf::from_str("𤭢€¢b华ประเทศไทย中");
 430         assert_eq!(data.shift_char().unwrap(), '𤭢'); // 4 bytes
 431         assert_eq!(data.shift_char().unwrap(), '€'); // 3 bytes
 432         assert_eq!(data.shift_char().unwrap(), '¢'); // 2 bytes
 433         assert_eq!(data.shift_char().unwrap(), 'b'); // 1 bytes
 434         assert_eq!(data.shift_char().unwrap(), '华');
 435         assert_eq!(data.as_slice(), "ประเทศไทย中");
 436     }
 437
 438     #[test]
 439     fn test_str_truncate() {
 440         let mut s = StrBuf::from_str("12345");
 441         s.truncate(5);
 442         assert_eq!(s.as_slice(), "12345");
 443         s.truncate(3);
 444         assert_eq!(s.as_slice(), "123");
 445         s.truncate(0);
 446         assert_eq!(s.as_slice(), "");
 447
 448         let mut s = StrBuf::from_str("12345");
 449         let p = s.as_slice().as_ptr();
 450         s.truncate(3);
 451         s.push_str("6");
 452         let p_ = s.as_slice().as_ptr();
 453         assert_eq!(p_, p);
 454     }
 455
 456     #[test]
 457     #[should_fail]
 458     fn test_str_truncate_invalid_len() {
 459         let mut s = StrBuf::from_str("12345");
 460         s.truncate(6);
 461     }
 462
 463     #[test]
 464     #[should_fail]
 465     fn test_str_truncate_split_codepoint() {
 466         let mut s = StrBuf::from_str("\u00FC"); // ü
 467         s.truncate(1);
 468     }
 469
 470     #[test]
 471     fn test_str_clear() {
 472         let mut s = StrBuf::from_str("12345");
 473         s.clear();
 474         assert_eq!(s.len(), 0);
 475         assert_eq!(s.as_slice(), "");
 476     }
 477 }