1 // Copyright 2012-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.
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.
11 // ignore-lexer-test FIXME #15679
13 //! String manipulation
15 //! For more details, see std::str
17 #![doc(primitive = "str")]
24 use cmp::{PartialEq, Eq};
25 use collections::Collection;
27 use iter::{Map, Iterator};
28 use iter::{DoubleEndedIterator, ExactSize};
30 use num::{CheckedMul, Saturating};
31 use option::{Option, None, Some};
33 use slice::{ImmutableSlice, MutableSlice};
38 Section: Creating a string
41 /// Converts a vector to a string slice without performing any allocations.
43 /// Once the slice has been validated as utf-8, it is transmuted in-place and
44 /// returned as a '&str' instead of a '&[u8]'
46 /// Returns None if the slice is not utf-8.
47 pub fn from_utf8<'a>(v: &'a [u8]) -> Option<&'a str> {
49 Some(unsafe { raw::from_utf8(v) })
53 /// Something that can be used to compare against a character
55 /// Determine if the splitter should split at the given character
56 fn matches(&mut self, char) -> bool;
57 /// Indicate if this is only concerned about ASCII characters,
58 /// which can allow for a faster implementation.
59 fn only_ascii(&self) -> bool;
62 impl CharEq for char {
64 fn matches(&mut self, c: char) -> bool { *self == c }
67 fn only_ascii(&self) -> bool { (*self as uint) < 128 }
70 impl<'a> CharEq for |char|: 'a -> bool {
72 fn matches(&mut self, c: char) -> bool { (*self)(c) }
75 fn only_ascii(&self) -> bool { false }
78 impl CharEq for extern "Rust" fn(char) -> bool {
80 fn matches(&mut self, c: char) -> bool { (*self)(c) }
83 fn only_ascii(&self) -> bool { false }
86 impl<'a> CharEq for &'a [char] {
88 fn matches(&mut self, c: char) -> bool {
89 self.iter().any(|&mut m| m.matches(c))
93 fn only_ascii(&self) -> bool {
94 self.iter().all(|m| m.only_ascii())
102 /// Iterator for the char (representing *Unicode Scalar Values*) of a string
104 /// Created with the method `.chars()`.
106 pub struct Chars<'a> {
107 iter: slice::Items<'a, u8>
110 // Return the initial codepoint accumulator for the first byte.
111 // The first byte is special, only want bottom 5 bits for width 2, 4 bits
112 // for width 3, and 3 bits for width 4
113 macro_rules! utf8_first_byte(
114 ($byte:expr, $width:expr) => (($byte & (0x7F >> $width)) as u32)
117 // return the value of $ch updated with continuation byte $byte
118 macro_rules! utf8_acc_cont_byte(
119 ($ch:expr, $byte:expr) => (($ch << 6) | ($byte & CONT_MASK) as u32)
122 macro_rules! utf8_is_cont_byte(
123 ($byte:expr) => (($byte & !CONT_MASK) == TAG_CONT_U8)
127 fn unwrap_or_0(opt: Option<&u8>) -> u8 {
134 impl<'a> Iterator<char> for Chars<'a> {
136 fn next(&mut self) -> Option<char> {
137 // Decode UTF-8, using the valid UTF-8 invariant
138 let x = match self.iter.next() {
140 Some(&next_byte) if next_byte < 128 => return Some(next_byte as char),
141 Some(&next_byte) => next_byte,
144 // Multibyte case follows
145 // Decode from a byte combination out of: [[[x y] z] w]
146 // NOTE: Performance is sensitive to the exact formulation here
147 let init = utf8_first_byte!(x, 2);
148 let y = unwrap_or_0(self.iter.next());
149 let mut ch = utf8_acc_cont_byte!(init, y);
152 // 5th bit in 0xE0 .. 0xEF is always clear, so `init` is still valid
153 let z = unwrap_or_0(self.iter.next());
154 let y_z = utf8_acc_cont_byte!((y & CONT_MASK) as u32, z);
155 ch = init << 12 | y_z;
158 // use only the lower 3 bits of `init`
159 let w = unwrap_or_0(self.iter.next());
160 ch = (init & 7) << 18 | utf8_acc_cont_byte!(y_z, w);
164 // str invariant says `ch` is a valid Unicode Scalar Value
166 Some(mem::transmute(ch))
171 fn size_hint(&self) -> (uint, Option<uint>) {
172 let (len, _) = self.iter.size_hint();
173 (len.saturating_add(3) / 4, Some(len))
177 impl<'a> DoubleEndedIterator<char> for Chars<'a> {
179 fn next_back(&mut self) -> Option<char> {
180 let w = match self.iter.next_back() {
182 Some(&back_byte) if back_byte < 128 => return Some(back_byte as char),
183 Some(&back_byte) => back_byte,
186 // Multibyte case follows
187 // Decode from a byte combination out of: [x [y [z w]]]
189 let z = unwrap_or_0(self.iter.next_back());
190 ch = utf8_first_byte!(z, 2);
191 if utf8_is_cont_byte!(z) {
192 let y = unwrap_or_0(self.iter.next_back());
193 ch = utf8_first_byte!(y, 3);
194 if utf8_is_cont_byte!(y) {
195 let x = unwrap_or_0(self.iter.next_back());
196 ch = utf8_first_byte!(x, 4);
197 ch = utf8_acc_cont_byte!(ch, y);
199 ch = utf8_acc_cont_byte!(ch, z);
201 ch = utf8_acc_cont_byte!(ch, w);
203 // str invariant says `ch` is a valid Unicode Scalar Value
205 Some(mem::transmute(ch))
210 /// External iterator for a string's characters and their byte offsets.
211 /// Use with the `std::iter` module.
213 pub struct CharOffsets<'a> {
218 impl<'a> Iterator<(uint, char)> for CharOffsets<'a> {
220 fn next(&mut self) -> Option<(uint, char)> {
221 let (pre_len, _) = self.iter.iter.size_hint();
222 match self.iter.next() {
225 let index = self.front_offset;
226 let (len, _) = self.iter.iter.size_hint();
227 self.front_offset += pre_len - len;
234 fn size_hint(&self) -> (uint, Option<uint>) {
235 self.iter.size_hint()
239 impl<'a> DoubleEndedIterator<(uint, char)> for CharOffsets<'a> {
241 fn next_back(&mut self) -> Option<(uint, char)> {
242 match self.iter.next_back() {
245 let (len, _) = self.iter.iter.size_hint();
246 let index = self.front_offset + len;
253 /// External iterator for a string's bytes.
254 /// Use with the `std::iter` module.
256 Map<'a, &'a u8, u8, slice::Items<'a, u8>>;
258 /// An iterator over the substrings of a string, separated by `sep`.
260 pub struct CharSplits<'a, Sep> {
261 /// The slice remaining to be iterated
264 /// Whether an empty string at the end is allowed
265 allow_trailing_empty: bool,
270 /// An iterator over the substrings of a string, separated by `sep`,
271 /// splitting at most `count` times.
273 pub struct CharSplitsN<'a, Sep> {
274 iter: CharSplits<'a, Sep>,
275 /// The number of splits remaining
280 /// An iterator over the lines of a string, separated by either `\n` or (`\r\n`).
281 pub type AnyLines<'a> =
282 Map<'a, &'a str, &'a str, CharSplits<'a, char>>;
284 impl<'a, Sep> CharSplits<'a, Sep> {
286 fn get_end(&mut self) -> Option<&'a str> {
287 if !self.finished && (self.allow_trailing_empty || self.string.len() > 0) {
288 self.finished = true;
296 impl<'a, Sep: CharEq> Iterator<&'a str> for CharSplits<'a, Sep> {
298 fn next(&mut self) -> Option<&'a str> {
299 if self.finished { return None }
301 let mut next_split = None;
303 for (idx, byte) in self.string.bytes().enumerate() {
304 if self.sep.matches(byte as char) && byte < 128u8 {
305 next_split = Some((idx, idx + 1));
310 for (idx, ch) in self.string.char_indices() {
311 if self.sep.matches(ch) {
312 next_split = Some((idx, self.string.char_range_at(idx).next));
318 Some((a, b)) => unsafe {
319 let elt = raw::slice_unchecked(self.string, 0, a);
320 self.string = raw::slice_unchecked(self.string, b, self.string.len());
323 None => self.get_end(),
328 impl<'a, Sep: CharEq> DoubleEndedIterator<&'a str>
329 for CharSplits<'a, Sep> {
331 fn next_back(&mut self) -> Option<&'a str> {
332 if self.finished { return None }
334 if !self.allow_trailing_empty {
335 self.allow_trailing_empty = true;
336 match self.next_back() {
337 Some(elt) if !elt.is_empty() => return Some(elt),
338 _ => if self.finished { return None }
341 let len = self.string.len();
342 let mut next_split = None;
345 for (idx, byte) in self.string.bytes().enumerate().rev() {
346 if self.sep.matches(byte as char) && byte < 128u8 {
347 next_split = Some((idx, idx + 1));
352 for (idx, ch) in self.string.char_indices().rev() {
353 if self.sep.matches(ch) {
354 next_split = Some((idx, self.string.char_range_at(idx).next));
360 Some((a, b)) => unsafe {
361 let elt = raw::slice_unchecked(self.string, b, len);
362 self.string = raw::slice_unchecked(self.string, 0, a);
365 None => { self.finished = true; Some(self.string) }
370 impl<'a, Sep: CharEq> Iterator<&'a str> for CharSplitsN<'a, Sep> {
372 fn next(&mut self) -> Option<&'a str> {
375 if self.invert { self.iter.next_back() } else { self.iter.next() }
382 /// The internal state of an iterator that searches for matches of a substring
383 /// within a larger string using naive search
385 struct NaiveSearcher {
390 fn new() -> NaiveSearcher {
391 NaiveSearcher { position: 0 }
394 fn next(&mut self, haystack: &[u8], needle: &[u8]) -> Option<(uint, uint)> {
395 while self.position + needle.len() <= haystack.len() {
396 if haystack.slice(self.position, self.position + needle.len()) == needle {
397 let match_pos = self.position;
398 self.position += needle.len(); // add 1 for all matches
399 return Some((match_pos, match_pos + needle.len()));
408 /// The internal state of an iterator that searches for matches of a substring
409 /// within a larger string using two-way search
411 struct TwoWaySearcher {
422 // This is the Two-Way search algorithm, which was introduced in the paper:
423 // Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675.
424 impl TwoWaySearcher {
425 fn new(needle: &[u8]) -> TwoWaySearcher {
426 let (crit_pos1, period1) = TwoWaySearcher::maximal_suffix(needle, false);
427 let (crit_pos2, period2) = TwoWaySearcher::maximal_suffix(needle, true);
431 if crit_pos1 > crit_pos2 {
432 crit_pos = crit_pos1;
435 crit_pos = crit_pos2;
439 let byteset = needle.iter()
440 .fold(0, |a, &b| (1 << ((b & 0x3f) as uint)) | a);
442 // The logic here (calculating crit_pos and period, the final if statement to see which
443 // period to use for the TwoWaySearcher) is essentially an implementation of the
444 // "small-period" function from the paper (p. 670)
446 // In the paper they check whether `needle.slice_to(crit_pos)` is a suffix of
447 // `needle.slice(crit_pos, crit_pos + period)`, which is precisely what this does
448 if needle.slice_to(crit_pos) == needle.slice(period, period + crit_pos) {
460 period: cmp::max(crit_pos, needle.len() - crit_pos) + 1,
464 memory: uint::MAX // Dummy value to signify that the period is long
470 fn next(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> Option<(uint, uint)> {
472 // Check that we have room to search in
473 if self.position + needle.len() > haystack.len() {
477 // Quickly skip by large portions unrelated to our substring
479 ((haystack[self.position + needle.len() - 1] & 0x3f)
481 self.position += needle.len();
485 // See if the right part of the needle matches
486 let start = if long_period { self.crit_pos }
487 else { cmp::max(self.crit_pos, self.memory) };
488 for i in range(start, needle.len()) {
489 if needle[i] != haystack[self.position + i] {
490 self.position += i - self.crit_pos + 1;
498 // See if the left part of the needle matches
499 let start = if long_period { 0 } else { self.memory };
500 for i in range(start, self.crit_pos).rev() {
501 if needle[i] != haystack[self.position + i] {
502 self.position += self.period;
504 self.memory = needle.len() - self.period;
510 // We have found a match!
511 let match_pos = self.position;
512 self.position += needle.len(); // add self.period for all matches
514 self.memory = 0; // set to needle.len() - self.period for all matches
516 return Some((match_pos, match_pos + needle.len()));
520 // returns (i, p) where i is the "critical position", the starting index of
521 // of maximal suffix, and p is the period of the suffix
522 // see p. 668 of the paper
524 fn maximal_suffix(arr: &[u8], reversed: bool) -> (uint, uint) {
525 let mut left = -1; // Corresponds to i in the paper
526 let mut right = 0; // Corresponds to j in the paper
527 let mut offset = 1; // Corresponds to k in the paper
528 let mut period = 1; // Corresponds to p in the paper
530 while right + offset < arr.len() {
534 a = arr[left + offset];
535 b = arr[right + offset];
537 a = arr[right + offset];
538 b = arr[left + offset];
541 // Suffix is smaller, period is entire prefix so far.
544 period = right - left;
546 // Advance through repetition of the current period.
547 if offset == period {
554 // Suffix is larger, start over from current location.
565 /// The internal state of an iterator that searches for matches of a substring
566 /// within a larger string using a dynamically chosen search algorithm
569 Naive(NaiveSearcher),
570 TwoWay(TwoWaySearcher),
571 TwoWayLong(TwoWaySearcher)
575 fn new(haystack: &[u8], needle: &[u8]) -> Searcher {
577 // FIXME(#16715): This unsigned integer addition will probably not
578 // overflow because that would mean that the memory almost solely
579 // consists of the needle. Needs #16715 to be formally fixed.
580 if needle.len() + 20 > haystack.len() {
581 Naive(NaiveSearcher::new())
583 let searcher = TwoWaySearcher::new(needle);
584 if searcher.memory == uint::MAX { // If the period is long
593 /// An iterator over the start and end indices of the matches of a
594 /// substring within a larger string
596 pub struct MatchIndices<'a> {
603 /// An iterator over the substrings of a string separated by a given
606 pub struct StrSplits<'a> {
607 it: MatchIndices<'a>,
612 impl<'a> Iterator<(uint, uint)> for MatchIndices<'a> {
614 fn next(&mut self) -> Option<(uint, uint)> {
615 match self.searcher {
616 Naive(ref mut searcher)
617 => searcher.next(self.haystack.as_bytes(), self.needle.as_bytes()),
618 TwoWay(ref mut searcher)
619 => searcher.next(self.haystack.as_bytes(), self.needle.as_bytes(), false),
620 TwoWayLong(ref mut searcher)
621 => searcher.next(self.haystack.as_bytes(), self.needle.as_bytes(), true)
626 impl<'a> Iterator<&'a str> for StrSplits<'a> {
628 fn next(&mut self) -> Option<&'a str> {
629 if self.finished { return None; }
631 match self.it.next() {
632 Some((from, to)) => {
633 let ret = Some(self.it.haystack.slice(self.last_end, from));
638 self.finished = true;
639 Some(self.it.haystack.slice(self.last_end, self.it.haystack.len()))
645 /// External iterator for a string's UTF16 codeunits.
646 /// Use with the `std::iter` module.
648 pub struct Utf16CodeUnits<'a> {
653 impl<'a> Iterator<u16> for Utf16CodeUnits<'a> {
655 fn next(&mut self) -> Option<u16> {
657 let tmp = self.extra;
662 let mut buf = [0u16, ..2];
663 self.chars.next().map(|ch| {
664 let n = ch.encode_utf16(buf.as_mut_slice()).unwrap_or(0);
665 if n == 2 { self.extra = buf[1]; }
671 fn size_hint(&self) -> (uint, Option<uint>) {
672 let (low, high) = self.chars.size_hint();
673 // every char gets either one u16 or two u16,
674 // so this iterator is between 1 or 2 times as
675 // long as the underlying iterator.
676 (low, high.and_then(|n| n.checked_mul(&2)))
681 Section: Comparing strings
684 // share the implementation of the lang-item vs. non-lang-item
686 /// NOTE: This function is (ab)used in rustc::middle::trans::_match
687 /// to compare &[u8] byte slices that are not necessarily valid UTF-8.
689 fn eq_slice_(a: &str, b: &str) -> bool {
691 extern { fn memcmp(s1: *const i8, s2: *const i8, n: uint) -> i32; }
692 a.len() == b.len() && unsafe {
693 memcmp(a.as_ptr() as *const i8,
694 b.as_ptr() as *const i8,
699 /// Bytewise slice equality
700 /// NOTE: This function is (ab)used in rustc::middle::trans::_match
701 /// to compare &[u8] byte slices that are not necessarily valid UTF-8.
704 pub fn eq_slice(a: &str, b: &str) -> bool {
712 /// Walk through `iter` checking that it's a valid UTF-8 sequence,
713 /// returning `true` in that case, or, if it is invalid, `false` with
714 /// `iter` reset such that it is pointing at the first byte in the
715 /// invalid sequence.
717 fn run_utf8_validation_iterator(iter: &mut slice::Items<u8>) -> bool {
719 // save the current thing we're pointing at.
722 // restore the iterator we had at the start of this codepoint.
723 macro_rules! err ( () => { {*iter = old; return false} });
724 macro_rules! next ( () => {
727 // we needed data, but there was none: error!
732 let first = match iter.next() {
734 // we're at the end of the iterator and a codepoint
735 // boundary at the same time, so this string is valid.
739 // ASCII characters are always valid, so only large
740 // bytes need more examination.
742 let w = utf8_char_width(first);
743 let second = next!();
744 // 2-byte encoding is for codepoints \u0080 to \u07ff
745 // first C2 80 last DF BF
746 // 3-byte encoding is for codepoints \u0800 to \uffff
747 // first E0 A0 80 last EF BF BF
748 // excluding surrogates codepoints \ud800 to \udfff
749 // ED A0 80 to ED BF BF
750 // 4-byte encoding is for codepoints \u10000 to \u10ffff
751 // first F0 90 80 80 last F4 8F BF BF
753 // Use the UTF-8 syntax from the RFC
755 // https://tools.ietf.org/html/rfc3629
757 // UTF8-2 = %xC2-DF UTF8-tail
758 // UTF8-3 = %xE0 %xA0-BF UTF8-tail / %xE1-EC 2( UTF8-tail ) /
759 // %xED %x80-9F UTF8-tail / %xEE-EF 2( UTF8-tail )
760 // UTF8-4 = %xF0 %x90-BF 2( UTF8-tail ) / %xF1-F3 3( UTF8-tail ) /
761 // %xF4 %x80-8F 2( UTF8-tail )
763 2 => if second & !CONT_MASK != TAG_CONT_U8 {err!()},
765 match (first, second, next!() & !CONT_MASK) {
766 (0xE0 , 0xA0 .. 0xBF, TAG_CONT_U8) |
767 (0xE1 .. 0xEC, 0x80 .. 0xBF, TAG_CONT_U8) |
768 (0xED , 0x80 .. 0x9F, TAG_CONT_U8) |
769 (0xEE .. 0xEF, 0x80 .. 0xBF, TAG_CONT_U8) => {}
774 match (first, second, next!() & !CONT_MASK, next!() & !CONT_MASK) {
775 (0xF0 , 0x90 .. 0xBF, TAG_CONT_U8, TAG_CONT_U8) |
776 (0xF1 .. 0xF3, 0x80 .. 0xBF, TAG_CONT_U8, TAG_CONT_U8) |
777 (0xF4 , 0x80 .. 0x8F, TAG_CONT_U8, TAG_CONT_U8) => {}
787 /// Determines if a vector of bytes contains valid UTF-8.
788 pub fn is_utf8(v: &[u8]) -> bool {
789 run_utf8_validation_iterator(&mut v.iter())
792 /// Determines if a vector of `u16` contains valid UTF-16
793 pub fn is_utf16(v: &[u16]) -> bool {
794 let mut it = v.iter();
795 macro_rules! next ( ($ret:expr) => {
796 match it.next() { Some(u) => *u, None => return $ret }
802 match char::from_u32(u as u32) {
805 let u2 = next!(false);
806 if u < 0xD7FF || u > 0xDBFF ||
807 u2 < 0xDC00 || u2 > 0xDFFF { return false; }
813 /// An iterator that decodes UTF-16 encoded codepoints from a vector
816 pub struct Utf16Items<'a> {
817 iter: slice::Items<'a, u16>
819 /// The possibilities for values decoded from a `u16` stream.
820 #[deriving(PartialEq, Eq, Clone, Show)]
822 /// A valid codepoint.
824 /// An invalid surrogate without its pair.
829 /// Convert `self` to a `char`, taking `LoneSurrogate`s to the
830 /// replacement character (U+FFFD).
832 pub fn to_char_lossy(&self) -> char {
835 LoneSurrogate(_) => '\uFFFD'
840 impl<'a> Iterator<Utf16Item> for Utf16Items<'a> {
841 fn next(&mut self) -> Option<Utf16Item> {
842 let u = match self.iter.next() {
847 if u < 0xD800 || 0xDFFF < u {
849 Some(ScalarValue(unsafe {mem::transmute(u as u32)}))
850 } else if u >= 0xDC00 {
851 // a trailing surrogate
852 Some(LoneSurrogate(u))
854 // preserve state for rewinding.
857 let u2 = match self.iter.next() {
860 None => return Some(LoneSurrogate(u))
862 if u2 < 0xDC00 || u2 > 0xDFFF {
863 // not a trailing surrogate so we're not a valid
864 // surrogate pair, so rewind to redecode u2 next time.
866 return Some(LoneSurrogate(u))
869 // all ok, so lets decode it.
870 let c = ((u - 0xD800) as u32 << 10 | (u2 - 0xDC00) as u32) + 0x1_0000;
871 Some(ScalarValue(unsafe {mem::transmute(c)}))
876 fn size_hint(&self) -> (uint, Option<uint>) {
877 let (low, high) = self.iter.size_hint();
878 // we could be entirely valid surrogates (2 elements per
879 // char), or entirely non-surrogates (1 element per char)
884 /// Create an iterator over the UTF-16 encoded codepoints in `v`,
885 /// returning invalid surrogates as `LoneSurrogate`s.
891 /// use std::str::{ScalarValue, LoneSurrogate};
893 /// // 𝄞mus<invalid>ic<invalid>
894 /// let v = [0xD834, 0xDD1E, 0x006d, 0x0075,
895 /// 0x0073, 0xDD1E, 0x0069, 0x0063,
898 /// assert_eq!(str::utf16_items(v).collect::<Vec<_>>(),
899 /// vec![ScalarValue('𝄞'),
900 /// ScalarValue('m'), ScalarValue('u'), ScalarValue('s'),
901 /// LoneSurrogate(0xDD1E),
902 /// ScalarValue('i'), ScalarValue('c'),
903 /// LoneSurrogate(0xD834)]);
905 pub fn utf16_items<'a>(v: &'a [u16]) -> Utf16Items<'a> {
906 Utf16Items { iter : v.iter() }
909 /// Return a slice of `v` ending at (and not including) the first NUL
918 /// let mut v = ['a' as u16, 'b' as u16, 'c' as u16, 'd' as u16];
919 /// // no NULs so no change
920 /// assert_eq!(str::truncate_utf16_at_nul(v), v.as_slice());
924 /// let b: &[_] = &['a' as u16, 'b' as u16];
925 /// assert_eq!(str::truncate_utf16_at_nul(v), b);
927 pub fn truncate_utf16_at_nul<'a>(v: &'a [u16]) -> &'a [u16] {
928 match v.iter().position(|c| *c == 0) {
929 // don't include the 0
930 Some(i) => v.slice_to(i),
935 // https://tools.ietf.org/html/rfc3629
936 static UTF8_CHAR_WIDTH: [u8, ..256] = [
937 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
938 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x1F
939 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
940 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x3F
941 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
942 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x5F
943 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
944 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x7F
945 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
946 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0x9F
947 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
948 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0xBF
949 0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
950 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, // 0xDF
951 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3, // 0xEF
952 4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0, // 0xFF
955 /// Given a first byte, determine how many bytes are in this UTF-8 character
957 pub fn utf8_char_width(b: u8) -> uint {
958 return UTF8_CHAR_WIDTH[b as uint] as uint;
961 /// Struct that contains a `char` and the index of the first byte of
962 /// the next `char` in a string. This can be used as a data structure
963 /// for iterating over the UTF-8 bytes of a string.
964 pub struct CharRange {
967 /// Index of the first byte of the next `char`
971 /// Mask of the value bits of a continuation byte
972 static CONT_MASK: u8 = 0b0011_1111u8;
973 /// Value of the tag bits (tag mask is !CONT_MASK) of a continuation byte
974 static TAG_CONT_U8: u8 = 0b1000_0000u8;
976 /// Unsafe operations
979 use collections::Collection;
982 use slice::{ImmutableSlice};
983 use str::{is_utf8, StrSlice};
985 /// Converts a slice of bytes to a string slice without checking
986 /// that the string contains valid UTF-8.
987 pub unsafe fn from_utf8<'a>(v: &'a [u8]) -> &'a str {
991 /// Form a slice from a C string. Unsafe because the caller must ensure the
992 /// C string has the static lifetime, or else the return value may be
993 /// invalidated later.
994 pub unsafe fn c_str_to_static_slice(s: *const i8) -> &'static str {
995 let s = s as *const u8;
1000 curr = s.offset(len as int);
1002 let v = Slice { data: s, len: len };
1003 assert!(is_utf8(::mem::transmute(v)));
1007 /// Takes a bytewise (not UTF-8) slice from a string.
1009 /// Returns the substring from [`begin`..`end`).
1013 /// If begin is greater than end.
1014 /// If end is greater than the length of the string.
1016 pub unsafe fn slice_bytes<'a>(s: &'a str, begin: uint, end: uint) -> &'a str {
1017 assert!(begin <= end);
1018 assert!(end <= s.len());
1019 slice_unchecked(s, begin, end)
1022 /// Takes a bytewise (not UTF-8) slice from a string.
1024 /// Returns the substring from [`begin`..`end`).
1026 /// Caller must check slice boundaries!
1028 pub unsafe fn slice_unchecked<'a>(s: &'a str, begin: uint, end: uint) -> &'a str {
1029 mem::transmute(Slice {
1030 data: s.as_ptr().offset(begin as int),
1037 Section: Trait implementations
1040 #[allow(missing_doc)]
1042 use cmp::{Ord, Ordering, Less, Equal, Greater, PartialEq, PartialOrd, Equiv, Eq};
1043 use collections::Collection;
1045 use option::{Option, Some};
1046 use str::{Str, StrSlice, eq_slice};
1048 impl<'a> Ord for &'a str {
1050 fn cmp(&self, other: & &'a str) -> Ordering {
1051 for (s_b, o_b) in self.bytes().zip(other.bytes()) {
1052 match s_b.cmp(&o_b) {
1053 Greater => return Greater,
1054 Less => return Less,
1059 self.len().cmp(&other.len())
1063 impl<'a> PartialEq for &'a str {
1065 fn eq(&self, other: & &'a str) -> bool {
1066 eq_slice((*self), (*other))
1069 fn ne(&self, other: & &'a str) -> bool { !(*self).eq(other) }
1072 impl<'a> Eq for &'a str {}
1074 impl<'a> PartialOrd for &'a str {
1076 fn partial_cmp(&self, other: &&'a str) -> Option<Ordering> {
1077 Some(self.cmp(other))
1081 impl<'a, S: Str> Equiv<S> for &'a str {
1083 fn equiv(&self, other: &S) -> bool { eq_slice(*self, other.as_slice()) }
1087 /// Any string that can be represented as a slice
1089 /// Work with `self` as a slice.
1090 fn as_slice<'a>(&'a self) -> &'a str;
1093 impl<'a> Str for &'a str {
1095 fn as_slice<'a>(&'a self) -> &'a str { *self }
1098 impl<'a> Collection for &'a str {
1100 fn len(&self) -> uint {
1105 /// Methods for string slices
1106 pub trait StrSlice<'a> {
1107 /// Returns true if one string contains another
1111 /// - needle - The string to look for
1116 /// assert!("bananas".contains("nana"));
1118 fn contains<'a>(&self, needle: &'a str) -> bool;
1120 /// Returns true if a string contains a char.
1124 /// - needle - The char to look for
1129 /// assert!("hello".contains_char('e'));
1131 fn contains_char(&self, needle: char) -> bool;
1133 /// An iterator over the characters of `self`. Note, this iterates
1134 /// over Unicode code-points, not Unicode graphemes.
1139 /// let v: Vec<char> = "abc åäö".chars().collect();
1140 /// assert_eq!(v, vec!['a', 'b', 'c', ' ', 'å', 'ä', 'ö']);
1142 fn chars(&self) -> Chars<'a>;
1144 /// An iterator over the bytes of `self`
1149 /// let v: Vec<u8> = "bors".bytes().collect();
1150 /// assert_eq!(v, b"bors".to_vec());
1152 fn bytes(&self) -> Bytes<'a>;
1154 /// An iterator over the characters of `self` and their byte offsets.
1155 fn char_indices(&self) -> CharOffsets<'a>;
1157 /// An iterator over substrings of `self`, separated by characters
1158 /// matched by `sep`.
1163 /// let v: Vec<&str> = "Mary had a little lamb".split(' ').collect();
1164 /// assert_eq!(v, vec!["Mary", "had", "a", "little", "lamb"]);
1166 /// let v: Vec<&str> = "abc1def2ghi".split(|c: char| c.is_digit()).collect();
1167 /// assert_eq!(v, vec!["abc", "def", "ghi"]);
1169 /// let v: Vec<&str> = "lionXXtigerXleopard".split('X').collect();
1170 /// assert_eq!(v, vec!["lion", "", "tiger", "leopard"]);
1172 /// let v: Vec<&str> = "".split('X').collect();
1173 /// assert_eq!(v, vec![""]);
1175 fn split<Sep: CharEq>(&self, sep: Sep) -> CharSplits<'a, Sep>;
1177 /// An iterator over substrings of `self`, separated by characters
1178 /// matched by `sep`, restricted to splitting at most `count`
1184 /// let v: Vec<&str> = "Mary had a little lambda".splitn(2, ' ').collect();
1185 /// assert_eq!(v, vec!["Mary", "had", "a little lambda"]);
1187 /// let v: Vec<&str> = "abc1def2ghi".splitn(1, |c: char| c.is_digit()).collect();
1188 /// assert_eq!(v, vec!["abc", "def2ghi"]);
1190 /// let v: Vec<&str> = "lionXXtigerXleopard".splitn(2, 'X').collect();
1191 /// assert_eq!(v, vec!["lion", "", "tigerXleopard"]);
1193 /// let v: Vec<&str> = "abcXdef".splitn(0, 'X').collect();
1194 /// assert_eq!(v, vec!["abcXdef"]);
1196 /// let v: Vec<&str> = "".splitn(1, 'X').collect();
1197 /// assert_eq!(v, vec![""]);
1199 fn splitn<Sep: CharEq>(&self, count: uint, sep: Sep) -> CharSplitsN<'a, Sep>;
1201 /// An iterator over substrings of `self`, separated by characters
1202 /// matched by `sep`.
1204 /// Equivalent to `split`, except that the trailing substring
1205 /// is skipped if empty (terminator semantics).
1210 /// let v: Vec<&str> = "A.B.".split_terminator('.').collect();
1211 /// assert_eq!(v, vec!["A", "B"]);
1213 /// let v: Vec<&str> = "A..B..".split_terminator('.').collect();
1214 /// assert_eq!(v, vec!["A", "", "B", ""]);
1216 /// let v: Vec<&str> = "Mary had a little lamb".split(' ').rev().collect();
1217 /// assert_eq!(v, vec!["lamb", "little", "a", "had", "Mary"]);
1219 /// let v: Vec<&str> = "abc1def2ghi".split(|c: char| c.is_digit()).rev().collect();
1220 /// assert_eq!(v, vec!["ghi", "def", "abc"]);
1222 /// let v: Vec<&str> = "lionXXtigerXleopard".split('X').rev().collect();
1223 /// assert_eq!(v, vec!["leopard", "tiger", "", "lion"]);
1225 fn split_terminator<Sep: CharEq>(&self, sep: Sep) -> CharSplits<'a, Sep>;
1227 /// An iterator over substrings of `self`, separated by characters
1228 /// matched by `sep`, starting from the end of the string.
1229 /// Restricted to splitting at most `count` times.
1234 /// let v: Vec<&str> = "Mary had a little lamb".rsplitn(2, ' ').collect();
1235 /// assert_eq!(v, vec!["lamb", "little", "Mary had a"]);
1237 /// let v: Vec<&str> = "abc1def2ghi".rsplitn(1, |c: char| c.is_digit()).collect();
1238 /// assert_eq!(v, vec!["ghi", "abc1def"]);
1240 /// let v: Vec<&str> = "lionXXtigerXleopard".rsplitn(2, 'X').collect();
1241 /// assert_eq!(v, vec!["leopard", "tiger", "lionX"]);
1243 fn rsplitn<Sep: CharEq>(&self, count: uint, sep: Sep) -> CharSplitsN<'a, Sep>;
1245 /// An iterator over the start and end indices of the disjoint
1246 /// matches of `sep` within `self`.
1248 /// That is, each returned value `(start, end)` satisfies
1249 /// `self.slice(start, end) == sep`. For matches of `sep` within
1250 /// `self` that overlap, only the indices corresponding to the
1251 /// first match are returned.
1256 /// let v: Vec<(uint, uint)> = "abcXXXabcYYYabc".match_indices("abc").collect();
1257 /// assert_eq!(v, vec![(0,3), (6,9), (12,15)]);
1259 /// let v: Vec<(uint, uint)> = "1abcabc2".match_indices("abc").collect();
1260 /// assert_eq!(v, vec![(1,4), (4,7)]);
1262 /// let v: Vec<(uint, uint)> = "ababa".match_indices("aba").collect();
1263 /// assert_eq!(v, vec![(0, 3)]); // only the first `aba`
1265 fn match_indices(&self, sep: &'a str) -> MatchIndices<'a>;
1267 /// An iterator over the substrings of `self` separated by `sep`.
1272 /// let v: Vec<&str> = "abcXXXabcYYYabc".split_str("abc").collect();
1273 /// assert_eq!(v, vec!["", "XXX", "YYY", ""]);
1275 /// let v: Vec<&str> = "1abcabc2".split_str("abc").collect();
1276 /// assert_eq!(v, vec!["1", "", "2"]);
1278 fn split_str(&self, &'a str) -> StrSplits<'a>;
1280 /// An iterator over the lines of a string (subsequences separated
1281 /// by `\n`). This does not include the empty string after a
1287 /// let four_lines = "foo\nbar\n\nbaz\n";
1288 /// let v: Vec<&str> = four_lines.lines().collect();
1289 /// assert_eq!(v, vec!["foo", "bar", "", "baz"]);
1291 fn lines(&self) -> CharSplits<'a, char>;
1293 /// An iterator over the lines of a string, separated by either
1294 /// `\n` or `\r\n`. As with `.lines()`, this does not include an
1295 /// empty trailing line.
1300 /// let four_lines = "foo\r\nbar\n\r\nbaz\n";
1301 /// let v: Vec<&str> = four_lines.lines_any().collect();
1302 /// assert_eq!(v, vec!["foo", "bar", "", "baz"]);
1304 fn lines_any(&self) -> AnyLines<'a>;
1306 /// Returns the number of Unicode code points (`char`) that a
1309 /// This does not perform any normalization, and is `O(n)`, since
1310 /// UTF-8 is a variable width encoding of code points.
1312 /// *Warning*: The number of code points in a string does not directly
1313 /// correspond to the number of visible characters or width of the
1314 /// visible text due to composing characters, and double- and
1315 /// zero-width ones.
1317 /// See also `.len()` for the byte length.
1322 /// // composed forms of `ö` and `é`
1323 /// let c = "Löwe 老虎 Léopard"; // German, Simplified Chinese, French
1324 /// // decomposed forms of `ö` and `é`
1325 /// let d = "Lo\u0308we 老虎 Le\u0301opard";
1327 /// assert_eq!(c.char_len(), 15);
1328 /// assert_eq!(d.char_len(), 17);
1330 /// assert_eq!(c.len(), 21);
1331 /// assert_eq!(d.len(), 23);
1333 /// // the two strings *look* the same
1334 /// println!("{}", c);
1335 /// println!("{}", d);
1337 fn char_len(&self) -> uint;
1339 /// Returns a slice of the given string from the byte range
1340 /// [`begin`..`end`).
1342 /// This operation is `O(1)`.
1344 /// Fails when `begin` and `end` do not point to valid characters
1345 /// or point beyond the last character of the string.
1347 /// See also `slice_to` and `slice_from` for slicing prefixes and
1348 /// suffixes of strings, and `slice_chars` for slicing based on
1349 /// code point counts.
1354 /// let s = "Löwe 老虎 Léopard";
1355 /// assert_eq!(s.slice(0, 1), "L");
1357 /// assert_eq!(s.slice(1, 9), "öwe 老");
1359 /// // these will fail:
1360 /// // byte 2 lies within `ö`:
1361 /// // s.slice(2, 3);
1363 /// // byte 8 lies within `老`
1364 /// // s.slice(1, 8);
1366 /// // byte 100 is outside the string
1367 /// // s.slice(3, 100);
1369 fn slice(&self, begin: uint, end: uint) -> &'a str;
1371 /// Returns a slice of the string from `begin` to its end.
1373 /// Equivalent to `self.slice(begin, self.len())`.
1375 /// Fails when `begin` does not point to a valid character, or is
1378 /// See also `slice`, `slice_to` and `slice_chars`.
1379 fn slice_from(&self, begin: uint) -> &'a str;
1381 /// Returns a slice of the string from the beginning to byte
1384 /// Equivalent to `self.slice(0, end)`.
1386 /// Fails when `end` does not point to a valid character, or is
1389 /// See also `slice`, `slice_from` and `slice_chars`.
1390 fn slice_to(&self, end: uint) -> &'a str;
1392 /// Returns a slice of the string from the character range
1393 /// [`begin`..`end`).
1395 /// That is, start at the `begin`-th code point of the string and
1396 /// continue to the `end`-th code point. This does not detect or
1397 /// handle edge cases such as leaving a combining character as the
1398 /// first code point of the string.
1400 /// Due to the design of UTF-8, this operation is `O(end)`.
1401 /// See `slice`, `slice_to` and `slice_from` for `O(1)`
1402 /// variants that use byte indices rather than code point
1405 /// Fails if `begin` > `end` or the either `begin` or `end` are
1406 /// beyond the last character of the string.
1411 /// let s = "Löwe 老虎 Léopard";
1412 /// assert_eq!(s.slice_chars(0, 4), "Löwe");
1413 /// assert_eq!(s.slice_chars(5, 7), "老虎");
1415 fn slice_chars(&self, begin: uint, end: uint) -> &'a str;
1417 /// Returns true if `needle` is a prefix of the string.
1422 /// assert!("banana".starts_with("ba"));
1424 fn starts_with(&self, needle: &str) -> bool;
1426 /// Returns true if `needle` is a suffix of the string.
1431 /// assert!("banana".ends_with("nana"));
1433 fn ends_with(&self, needle: &str) -> bool;
1435 /// Returns a string with characters that match `to_trim` removed.
1439 /// * to_trim - a character matcher
1444 /// assert_eq!("11foo1bar11".trim_chars('1'), "foo1bar")
1445 /// let x: &[_] = &['1', '2'];
1446 /// assert_eq!("12foo1bar12".trim_chars(x), "foo1bar")
1447 /// assert_eq!("123foo1bar123".trim_chars(|c: char| c.is_digit()), "foo1bar")
1449 fn trim_chars<C: CharEq>(&self, to_trim: C) -> &'a str;
1451 /// Returns a string with leading `chars_to_trim` removed.
1455 /// * to_trim - a character matcher
1460 /// assert_eq!("11foo1bar11".trim_left_chars('1'), "foo1bar11")
1461 /// let x: &[_] = &['1', '2'];
1462 /// assert_eq!("12foo1bar12".trim_left_chars(x), "foo1bar12")
1463 /// assert_eq!("123foo1bar123".trim_left_chars(|c: char| c.is_digit()), "foo1bar123")
1465 fn trim_left_chars<C: CharEq>(&self, to_trim: C) -> &'a str;
1467 /// Returns a string with trailing `chars_to_trim` removed.
1471 /// * to_trim - a character matcher
1476 /// assert_eq!("11foo1bar11".trim_right_chars('1'), "11foo1bar")
1477 /// let x: &[_] = &['1', '2'];
1478 /// assert_eq!("12foo1bar12".trim_right_chars(x), "12foo1bar")
1479 /// assert_eq!("123foo1bar123".trim_right_chars(|c: char| c.is_digit()), "123foo1bar")
1481 fn trim_right_chars<C: CharEq>(&self, to_trim: C) -> &'a str;
1483 /// Check that `index`-th byte lies at the start and/or end of a
1484 /// UTF-8 code point sequence.
1486 /// The start and end of the string (when `index == self.len()`)
1487 /// are considered to be boundaries.
1489 /// Fails if `index` is greater than `self.len()`.
1494 /// let s = "Löwe 老虎 Léopard";
1495 /// assert!(s.is_char_boundary(0));
1497 /// assert!(s.is_char_boundary(6));
1498 /// assert!(s.is_char_boundary(s.len()));
1500 /// // second byte of `ö`
1501 /// assert!(!s.is_char_boundary(2));
1503 /// // third byte of `老`
1504 /// assert!(!s.is_char_boundary(8));
1506 fn is_char_boundary(&self, index: uint) -> bool;
1508 /// Pluck a character out of a string and return the index of the next
1511 /// This function can be used to iterate over the Unicode characters of a
1516 /// This example manually iterates through the characters of a
1517 /// string; this should normally be done by `.chars()` or
1518 /// `.char_indices`.
1521 /// use std::str::CharRange;
1523 /// let s = "中华Việt Nam";
1525 /// while i < s.len() {
1526 /// let CharRange {ch, next} = s.char_range_at(i);
1527 /// println!("{}: {}", i, ch);
1549 /// * s - The string
1550 /// * i - The byte offset of the char to extract
1554 /// A record {ch: char, next: uint} containing the char value and the byte
1555 /// index of the next Unicode character.
1559 /// If `i` is greater than or equal to the length of the string.
1560 /// If `i` is not the index of the beginning of a valid UTF-8 character.
1561 fn char_range_at(&self, start: uint) -> CharRange;
1563 /// Given a byte position and a str, return the previous char and its position.
1565 /// This function can be used to iterate over a Unicode string in reverse.
1567 /// Returns 0 for next index if called on start index 0.
1571 /// If `i` is greater than the length of the string.
1572 /// If `i` is not an index following a valid UTF-8 character.
1573 fn char_range_at_reverse(&self, start: uint) -> CharRange;
1575 /// Plucks the character starting at the `i`th byte of a string.
1581 /// assert_eq!(s.char_at(1), 'b');
1582 /// assert_eq!(s.char_at(2), 'π');
1583 /// assert_eq!(s.char_at(4), 'c');
1588 /// If `i` is greater than or equal to the length of the string.
1589 /// If `i` is not the index of the beginning of a valid UTF-8 character.
1590 fn char_at(&self, i: uint) -> char;
1592 /// Plucks the character ending at the `i`th byte of a string.
1596 /// If `i` is greater than the length of the string.
1597 /// If `i` is not an index following a valid UTF-8 character.
1598 fn char_at_reverse(&self, i: uint) -> char;
1600 /// Work with the byte buffer of a string as a byte slice.
1605 /// assert_eq!("bors".as_bytes(), b"bors");
1607 fn as_bytes(&self) -> &'a [u8];
1609 /// Returns the byte index of the first character of `self` that
1610 /// matches `search`.
1614 /// `Some` containing the byte index of the last matching character
1615 /// or `None` if there is no match
1620 /// let s = "Löwe 老虎 Léopard";
1622 /// assert_eq!(s.find('L'), Some(0));
1623 /// assert_eq!(s.find('é'), Some(14));
1625 /// // the first space
1626 /// assert_eq!(s.find(|c: char| c.is_whitespace()), Some(5));
1628 /// // neither are found
1629 /// let x: &[_] = &['1', '2'];
1630 /// assert_eq!(s.find(x), None);
1632 fn find<C: CharEq>(&self, search: C) -> Option<uint>;
1634 /// Returns the byte index of the last character of `self` that
1635 /// matches `search`.
1639 /// `Some` containing the byte index of the last matching character
1640 /// or `None` if there is no match.
1645 /// let s = "Löwe 老虎 Léopard";
1647 /// assert_eq!(s.rfind('L'), Some(13));
1648 /// assert_eq!(s.rfind('é'), Some(14));
1650 /// // the second space
1651 /// assert_eq!(s.rfind(|c: char| c.is_whitespace()), Some(12));
1653 /// // searches for an occurrence of either `1` or `2`, but neither are found
1654 /// let x: &[_] = &['1', '2'];
1655 /// assert_eq!(s.rfind(x), None);
1657 fn rfind<C: CharEq>(&self, search: C) -> Option<uint>;
1659 /// Returns the byte index of the first matching substring
1663 /// * `needle` - The string to search for
1667 /// `Some` containing the byte index of the first matching substring
1668 /// or `None` if there is no match.
1673 /// let s = "Löwe 老虎 Léopard";
1675 /// assert_eq!(s.find_str("老虎 L"), Some(6));
1676 /// assert_eq!(s.find_str("muffin man"), None);
1678 fn find_str(&self, &str) -> Option<uint>;
1680 /// Retrieves the first character from a string slice and returns
1681 /// it. This does not allocate a new string; instead, it returns a
1682 /// slice that point one character beyond the character that was
1683 /// shifted. If the string does not contain any characters,
1684 /// a tuple of None and an empty string is returned instead.
1689 /// let s = "Löwe 老虎 Léopard";
1690 /// let (c, s1) = s.slice_shift_char();
1691 /// assert_eq!(c, Some('L'));
1692 /// assert_eq!(s1, "öwe 老虎 Léopard");
1694 /// let (c, s2) = s1.slice_shift_char();
1695 /// assert_eq!(c, Some('ö'));
1696 /// assert_eq!(s2, "we 老虎 Léopard");
1698 fn slice_shift_char(&self) -> (Option<char>, &'a str);
1700 /// Returns the byte offset of an inner slice relative to an enclosing outer slice.
1702 /// Fails if `inner` is not a direct slice contained within self.
1707 /// let string = "a\nb\nc";
1708 /// let lines: Vec<&str> = string.lines().collect();
1709 /// let lines = lines.as_slice();
1711 /// assert!(string.subslice_offset(lines[0]) == 0); // &"a"
1712 /// assert!(string.subslice_offset(lines[1]) == 2); // &"b"
1713 /// assert!(string.subslice_offset(lines[2]) == 4); // &"c"
1715 fn subslice_offset(&self, inner: &str) -> uint;
1717 /// Return an unsafe pointer to the strings buffer.
1719 /// The caller must ensure that the string outlives this pointer,
1720 /// and that it is not reallocated (e.g. by pushing to the
1722 fn as_ptr(&self) -> *const u8;
1724 /// Return an iterator of `u16` over the string encoded as UTF-16.
1725 fn utf16_units(&self) -> Utf16CodeUnits<'a>;
1729 fn slice_error_fail(s: &str, begin: uint, end: uint) -> ! {
1730 assert!(begin <= end);
1731 fail!("index {} and/or {} in `{}` do not lie on character boundary",
1735 impl<'a> StrSlice<'a> for &'a str {
1737 fn contains<'a>(&self, needle: &'a str) -> bool {
1738 self.find_str(needle).is_some()
1742 fn contains_char(&self, needle: char) -> bool {
1743 self.find(needle).is_some()
1747 fn chars(&self) -> Chars<'a> {
1748 Chars{iter: self.as_bytes().iter()}
1752 fn bytes(&self) -> Bytes<'a> {
1753 self.as_bytes().iter().map(|&b| b)
1757 fn char_indices(&self) -> CharOffsets<'a> {
1758 CharOffsets{front_offset: 0, iter: self.chars()}
1762 fn split<Sep: CharEq>(&self, sep: Sep) -> CharSplits<'a, Sep> {
1765 only_ascii: sep.only_ascii(),
1767 allow_trailing_empty: true,
1773 fn splitn<Sep: CharEq>(&self, count: uint, sep: Sep)
1774 -> CharSplitsN<'a, Sep> {
1776 iter: self.split(sep),
1783 fn split_terminator<Sep: CharEq>(&self, sep: Sep)
1784 -> CharSplits<'a, Sep> {
1786 allow_trailing_empty: false,
1792 fn rsplitn<Sep: CharEq>(&self, count: uint, sep: Sep)
1793 -> CharSplitsN<'a, Sep> {
1795 iter: self.split(sep),
1802 fn match_indices(&self, sep: &'a str) -> MatchIndices<'a> {
1803 assert!(!sep.is_empty())
1807 searcher: Searcher::new(self.as_bytes(), sep.as_bytes())
1812 fn split_str(&self, sep: &'a str) -> StrSplits<'a> {
1814 it: self.match_indices(sep),
1821 fn lines(&self) -> CharSplits<'a, char> {
1822 self.split_terminator('\n')
1825 fn lines_any(&self) -> AnyLines<'a> {
1826 self.lines().map(|line| {
1828 if l > 0 && line.as_bytes()[l - 1] == b'\r' { line.slice(0, l - 1) }
1834 fn char_len(&self) -> uint { self.chars().count() }
1837 fn slice(&self, begin: uint, end: uint) -> &'a str {
1838 // is_char_boundary checks that the index is in [0, .len()]
1840 self.is_char_boundary(begin) &&
1841 self.is_char_boundary(end) {
1842 unsafe { raw::slice_unchecked(*self, begin, end) }
1844 slice_error_fail(*self, begin, end)
1849 fn slice_from(&self, begin: uint) -> &'a str {
1850 // is_char_boundary checks that the index is in [0, .len()]
1851 if self.is_char_boundary(begin) {
1852 unsafe { raw::slice_unchecked(*self, begin, self.len()) }
1854 slice_error_fail(*self, begin, self.len())
1859 fn slice_to(&self, end: uint) -> &'a str {
1860 // is_char_boundary checks that the index is in [0, .len()]
1861 if self.is_char_boundary(end) {
1862 unsafe { raw::slice_unchecked(*self, 0, end) }
1864 slice_error_fail(*self, 0, end)
1868 fn slice_chars(&self, begin: uint, end: uint) -> &'a str {
1869 assert!(begin <= end);
1871 let mut begin_byte = None;
1872 let mut end_byte = None;
1874 // This could be even more efficient by not decoding,
1875 // only finding the char boundaries
1876 for (idx, _) in self.char_indices() {
1877 if count == begin { begin_byte = Some(idx); }
1878 if count == end { end_byte = Some(idx); break; }
1881 if begin_byte.is_none() && count == begin { begin_byte = Some(self.len()) }
1882 if end_byte.is_none() && count == end { end_byte = Some(self.len()) }
1884 match (begin_byte, end_byte) {
1885 (None, _) => fail!("slice_chars: `begin` is beyond end of string"),
1886 (_, None) => fail!("slice_chars: `end` is beyond end of string"),
1887 (Some(a), Some(b)) => unsafe { raw::slice_bytes(*self, a, b) }
1892 fn starts_with<'a>(&self, needle: &'a str) -> bool {
1893 let n = needle.len();
1894 self.len() >= n && needle.as_bytes() == self.as_bytes().slice_to(n)
1898 fn ends_with(&self, needle: &str) -> bool {
1899 let (m, n) = (self.len(), needle.len());
1900 m >= n && needle.as_bytes() == self.as_bytes().slice_from(m - n)
1904 fn trim_chars<C: CharEq>(&self, mut to_trim: C) -> &'a str {
1905 let cur = match self.find(|c: char| !to_trim.matches(c)) {
1907 Some(i) => unsafe { raw::slice_bytes(*self, i, self.len()) }
1909 match cur.rfind(|c: char| !to_trim.matches(c)) {
1912 let right = cur.char_range_at(i).next;
1913 unsafe { raw::slice_bytes(cur, 0, right) }
1919 fn trim_left_chars<C: CharEq>(&self, mut to_trim: C) -> &'a str {
1920 match self.find(|c: char| !to_trim.matches(c)) {
1922 Some(first) => unsafe { raw::slice_bytes(*self, first, self.len()) }
1927 fn trim_right_chars<C: CharEq>(&self, mut to_trim: C) -> &'a str {
1928 match self.rfind(|c: char| !to_trim.matches(c)) {
1931 let next = self.char_range_at(last).next;
1932 unsafe { raw::slice_bytes(*self, 0u, next) }
1938 fn is_char_boundary(&self, index: uint) -> bool {
1939 if index == self.len() { return true; }
1940 match self.as_bytes().get(index) {
1942 Some(&b) => b < 128u8 || b >= 192u8,
1947 fn char_range_at(&self, i: uint) -> CharRange {
1948 if self.as_bytes()[i] < 128u8 {
1949 return CharRange {ch: self.as_bytes()[i] as char, next: i + 1 };
1952 // Multibyte case is a fn to allow char_range_at to inline cleanly
1953 fn multibyte_char_range_at(s: &str, i: uint) -> CharRange {
1954 let mut val = s.as_bytes()[i] as u32;
1955 let w = UTF8_CHAR_WIDTH[val as uint] as uint;
1958 val = utf8_first_byte!(val, w);
1959 val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 1]);
1960 if w > 2 { val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 2]); }
1961 if w > 3 { val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 3]); }
1963 return CharRange {ch: unsafe { mem::transmute(val) }, next: i + w};
1966 return multibyte_char_range_at(*self, i);
1970 fn char_range_at_reverse(&self, start: uint) -> CharRange {
1971 let mut prev = start;
1973 prev = prev.saturating_sub(1);
1974 if self.as_bytes()[prev] < 128 {
1975 return CharRange{ch: self.as_bytes()[prev] as char, next: prev}
1978 // Multibyte case is a fn to allow char_range_at_reverse to inline cleanly
1979 fn multibyte_char_range_at_reverse(s: &str, mut i: uint) -> CharRange {
1980 // while there is a previous byte == 10......
1981 while i > 0 && s.as_bytes()[i] & !CONT_MASK == TAG_CONT_U8 {
1985 let mut val = s.as_bytes()[i] as u32;
1986 let w = UTF8_CHAR_WIDTH[val as uint] as uint;
1989 val = utf8_first_byte!(val, w);
1990 val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 1]);
1991 if w > 2 { val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 2]); }
1992 if w > 3 { val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 3]); }
1994 return CharRange {ch: unsafe { mem::transmute(val) }, next: i};
1997 return multibyte_char_range_at_reverse(*self, prev);
2001 fn char_at(&self, i: uint) -> char {
2002 self.char_range_at(i).ch
2006 fn char_at_reverse(&self, i: uint) -> char {
2007 self.char_range_at_reverse(i).ch
2011 fn as_bytes(&self) -> &'a [u8] {
2012 unsafe { mem::transmute(*self) }
2015 fn find<C: CharEq>(&self, mut search: C) -> Option<uint> {
2016 if search.only_ascii() {
2017 self.bytes().position(|b| search.matches(b as char))
2019 for (index, c) in self.char_indices() {
2020 if search.matches(c) { return Some(index); }
2026 fn rfind<C: CharEq>(&self, mut search: C) -> Option<uint> {
2027 if search.only_ascii() {
2028 self.bytes().rposition(|b| search.matches(b as char))
2030 for (index, c) in self.char_indices().rev() {
2031 if search.matches(c) { return Some(index); }
2037 fn find_str(&self, needle: &str) -> Option<uint> {
2038 if needle.is_empty() {
2041 self.match_indices(needle)
2043 .map(|(start, _end)| start)
2048 fn slice_shift_char(&self) -> (Option<char>, &'a str) {
2049 if self.is_empty() {
2050 return (None, *self);
2052 let CharRange {ch, next} = self.char_range_at(0u);
2053 let next_s = unsafe { raw::slice_bytes(*self, next, self.len()) };
2054 return (Some(ch), next_s);
2058 fn subslice_offset(&self, inner: &str) -> uint {
2059 let a_start = self.as_ptr() as uint;
2060 let a_end = a_start + self.len();
2061 let b_start = inner.as_ptr() as uint;
2062 let b_end = b_start + inner.len();
2064 assert!(a_start <= b_start);
2065 assert!(b_end <= a_end);
2070 fn as_ptr(&self) -> *const u8 {
2075 fn utf16_units(&self) -> Utf16CodeUnits<'a> {
2076 Utf16CodeUnits{ chars: self.chars(), extra: 0}
2080 impl<'a> Default for &'a str {
2081 fn default() -> &'a str { "" }