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")]
19 pub use self::Utf16Item::*;
20 pub use self::Searcher::{Naive, TwoWay, TwoWayLong};
26 use iter::{Map, Iterator, IteratorExt, DoubleEndedIterator};
27 use iter::{DoubleEndedIteratorExt, ExactSizeIterator};
29 use kinds::{Copy, Sized};
33 use option::Option::{None, Some};
35 use raw::{Repr, Slice};
36 use slice::{mod, SlicePrelude};
39 /// A trait to abstract the idea of creating a new instance of a type from a
41 #[experimental = "might need to return Result"]
43 /// Parses a string `s` to return an optional value of this type. If the
44 /// string is ill-formatted, the None is returned.
45 fn from_str(s: &str) -> Option<Self>;
48 /// A utility function that just calls FromStr::from_str
49 pub fn from_str<A: FromStr>(s: &str) -> Option<A> {
53 impl FromStr for bool {
54 /// Parse a `bool` from a string.
56 /// Yields an `Option<bool>`, because `s` may or may not actually be parseable.
61 /// assert_eq!(from_str::<bool>("true"), Some(true));
62 /// assert_eq!(from_str::<bool>("false"), Some(false));
63 /// assert_eq!(from_str::<bool>("not even a boolean"), None);
66 fn from_str(s: &str) -> Option<bool> {
69 "false" => Some(false),
76 Section: Creating a string
79 /// Converts a vector to a string slice without performing any allocations.
81 /// Once the slice has been validated as utf-8, it is transmuted in-place and
82 /// returned as a '&str' instead of a '&[u8]'
84 /// Returns None if the slice is not utf-8.
85 pub fn from_utf8<'a>(v: &'a [u8]) -> Option<&'a str> {
87 Some(unsafe { from_utf8_unchecked(v) })
93 /// Converts a slice of bytes to a string slice without checking
94 /// that the string contains valid UTF-8.
95 pub unsafe fn from_utf8_unchecked<'a>(v: &'a [u8]) -> &'a str {
99 /// Constructs a static string slice from a given raw pointer.
101 /// This function will read memory starting at `s` until it finds a 0, and then
102 /// transmute the memory up to that point as a string slice, returning the
103 /// corresponding `&'static str` value.
105 /// This function is unsafe because the caller must ensure the C string itself
106 /// has the static lifetime and that the memory `s` is valid up to and including
107 /// the first null byte.
111 /// This function will panic if the string pointed to by `s` is not valid UTF-8.
112 pub unsafe fn from_c_str(s: *const i8) -> &'static str {
113 let s = s as *const u8;
115 while *s.offset(len as int) != 0 {
118 let v: &'static [u8] = ::mem::transmute(Slice { data: s, len: len });
119 from_utf8(v).expect("from_c_str passed invalid utf-8 data")
122 /// Something that can be used to compare against a character
124 /// Determine if the splitter should split at the given character
125 fn matches(&mut self, char) -> bool;
126 /// Indicate if this is only concerned about ASCII characters,
127 /// which can allow for a faster implementation.
128 fn only_ascii(&self) -> bool;
131 impl CharEq for char {
133 fn matches(&mut self, c: char) -> bool { *self == c }
136 fn only_ascii(&self) -> bool { (*self as uint) < 128 }
139 impl<'a> CharEq for |char|: 'a -> bool {
141 fn matches(&mut self, c: char) -> bool { (*self)(c) }
144 fn only_ascii(&self) -> bool { false }
147 impl CharEq for extern "Rust" fn(char) -> bool {
149 fn matches(&mut self, c: char) -> bool { (*self)(c) }
152 fn only_ascii(&self) -> bool { false }
155 impl<'a> CharEq for &'a [char] {
157 fn matches(&mut self, c: char) -> bool {
158 self.iter().any(|&mut m| m.matches(c))
162 fn only_ascii(&self) -> bool {
163 self.iter().all(|m| m.only_ascii())
171 /// Iterator for the char (representing *Unicode Scalar Values*) of a string
173 /// Created with the method `.chars()`.
175 pub struct Chars<'a> {
176 iter: slice::Items<'a, u8>
179 impl<'a> Copy for Chars<'a> {}
181 // Return the initial codepoint accumulator for the first byte.
182 // The first byte is special, only want bottom 5 bits for width 2, 4 bits
183 // for width 3, and 3 bits for width 4
184 macro_rules! utf8_first_byte(
185 ($byte:expr, $width:expr) => (($byte & (0x7F >> $width)) as u32)
188 // return the value of $ch updated with continuation byte $byte
189 macro_rules! utf8_acc_cont_byte(
190 ($ch:expr, $byte:expr) => (($ch << 6) | ($byte & CONT_MASK) as u32)
193 macro_rules! utf8_is_cont_byte(
194 ($byte:expr) => (($byte & !CONT_MASK) == TAG_CONT_U8)
198 fn unwrap_or_0(opt: Option<&u8>) -> u8 {
205 impl<'a> Iterator<char> for Chars<'a> {
207 fn next(&mut self) -> Option<char> {
208 // Decode UTF-8, using the valid UTF-8 invariant
209 let x = match self.iter.next() {
211 Some(&next_byte) if next_byte < 128 => return Some(next_byte as char),
212 Some(&next_byte) => next_byte,
215 // Multibyte case follows
216 // Decode from a byte combination out of: [[[x y] z] w]
217 // NOTE: Performance is sensitive to the exact formulation here
218 let init = utf8_first_byte!(x, 2);
219 let y = unwrap_or_0(self.iter.next());
220 let mut ch = utf8_acc_cont_byte!(init, y);
223 // 5th bit in 0xE0 .. 0xEF is always clear, so `init` is still valid
224 let z = unwrap_or_0(self.iter.next());
225 let y_z = utf8_acc_cont_byte!((y & CONT_MASK) as u32, z);
226 ch = init << 12 | y_z;
229 // use only the lower 3 bits of `init`
230 let w = unwrap_or_0(self.iter.next());
231 ch = (init & 7) << 18 | utf8_acc_cont_byte!(y_z, w);
235 // str invariant says `ch` is a valid Unicode Scalar Value
237 Some(mem::transmute(ch))
242 fn size_hint(&self) -> (uint, Option<uint>) {
243 let (len, _) = self.iter.size_hint();
244 (len.saturating_add(3) / 4, Some(len))
248 impl<'a> DoubleEndedIterator<char> for Chars<'a> {
250 fn next_back(&mut self) -> Option<char> {
251 let w = match self.iter.next_back() {
253 Some(&back_byte) if back_byte < 128 => return Some(back_byte as char),
254 Some(&back_byte) => back_byte,
257 // Multibyte case follows
258 // Decode from a byte combination out of: [x [y [z w]]]
260 let z = unwrap_or_0(self.iter.next_back());
261 ch = utf8_first_byte!(z, 2);
262 if utf8_is_cont_byte!(z) {
263 let y = unwrap_or_0(self.iter.next_back());
264 ch = utf8_first_byte!(y, 3);
265 if utf8_is_cont_byte!(y) {
266 let x = unwrap_or_0(self.iter.next_back());
267 ch = utf8_first_byte!(x, 4);
268 ch = utf8_acc_cont_byte!(ch, y);
270 ch = utf8_acc_cont_byte!(ch, z);
272 ch = utf8_acc_cont_byte!(ch, w);
274 // str invariant says `ch` is a valid Unicode Scalar Value
276 Some(mem::transmute(ch))
281 /// External iterator for a string's characters and their byte offsets.
282 /// Use with the `std::iter` module.
284 pub struct CharOffsets<'a> {
289 impl<'a> Iterator<(uint, char)> for CharOffsets<'a> {
291 fn next(&mut self) -> Option<(uint, char)> {
292 let (pre_len, _) = self.iter.iter.size_hint();
293 match self.iter.next() {
296 let index = self.front_offset;
297 let (len, _) = self.iter.iter.size_hint();
298 self.front_offset += pre_len - len;
305 fn size_hint(&self) -> (uint, Option<uint>) {
306 self.iter.size_hint()
310 impl<'a> DoubleEndedIterator<(uint, char)> for CharOffsets<'a> {
312 fn next_back(&mut self) -> Option<(uint, char)> {
313 match self.iter.next_back() {
316 let (len, _) = self.iter.iter.size_hint();
317 let index = self.front_offset + len;
324 /// External iterator for a string's bytes.
325 /// Use with the `std::iter` module.
327 Map<'a, &'a u8, u8, slice::Items<'a, u8>>;
329 /// An iterator over the substrings of a string, separated by `sep`.
331 pub struct CharSplits<'a, Sep> {
332 /// The slice remaining to be iterated
335 /// Whether an empty string at the end is allowed
336 allow_trailing_empty: bool,
341 /// An iterator over the substrings of a string, separated by `sep`,
342 /// splitting at most `count` times.
344 pub struct CharSplitsN<'a, Sep> {
345 iter: CharSplits<'a, Sep>,
346 /// The number of splits remaining
351 /// An iterator over the lines of a string, separated by either `\n` or (`\r\n`).
352 pub type AnyLines<'a> =
353 Map<'a, &'a str, &'a str, CharSplits<'a, char>>;
355 impl<'a, Sep> CharSplits<'a, Sep> {
357 fn get_end(&mut self) -> Option<&'a str> {
358 if !self.finished && (self.allow_trailing_empty || self.string.len() > 0) {
359 self.finished = true;
367 impl<'a, Sep: CharEq> Iterator<&'a str> for CharSplits<'a, Sep> {
369 fn next(&mut self) -> Option<&'a str> {
370 if self.finished { return None }
372 let mut next_split = None;
374 for (idx, byte) in self.string.bytes().enumerate() {
375 if self.sep.matches(byte as char) && byte < 128u8 {
376 next_split = Some((idx, idx + 1));
381 for (idx, ch) in self.string.char_indices() {
382 if self.sep.matches(ch) {
383 next_split = Some((idx, self.string.char_range_at(idx).next));
389 Some((a, b)) => unsafe {
390 let elt = self.string.slice_unchecked(0, a);
391 self.string = self.string.slice_unchecked(b, self.string.len());
394 None => self.get_end(),
399 impl<'a, Sep: CharEq> DoubleEndedIterator<&'a str>
400 for CharSplits<'a, Sep> {
402 fn next_back(&mut self) -> Option<&'a str> {
403 if self.finished { return None }
405 if !self.allow_trailing_empty {
406 self.allow_trailing_empty = true;
407 match self.next_back() {
408 Some(elt) if !elt.is_empty() => return Some(elt),
409 _ => if self.finished { return None }
412 let len = self.string.len();
413 let mut next_split = None;
416 for (idx, byte) in self.string.bytes().enumerate().rev() {
417 if self.sep.matches(byte as char) && byte < 128u8 {
418 next_split = Some((idx, idx + 1));
423 for (idx, ch) in self.string.char_indices().rev() {
424 if self.sep.matches(ch) {
425 next_split = Some((idx, self.string.char_range_at(idx).next));
431 Some((a, b)) => unsafe {
432 let elt = self.string.slice_unchecked(b, len);
433 self.string = self.string.slice_unchecked(0, a);
436 None => { self.finished = true; Some(self.string) }
441 impl<'a, Sep: CharEq> Iterator<&'a str> for CharSplitsN<'a, Sep> {
443 fn next(&mut self) -> Option<&'a str> {
446 if self.invert { self.iter.next_back() } else { self.iter.next() }
453 /// The internal state of an iterator that searches for matches of a substring
454 /// within a larger string using naive search
456 struct NaiveSearcher {
461 fn new() -> NaiveSearcher {
462 NaiveSearcher { position: 0 }
465 fn next(&mut self, haystack: &[u8], needle: &[u8]) -> Option<(uint, uint)> {
466 while self.position + needle.len() <= haystack.len() {
467 if haystack[self.position .. self.position + needle.len()] == needle {
468 let match_pos = self.position;
469 self.position += needle.len(); // add 1 for all matches
470 return Some((match_pos, match_pos + needle.len()));
479 /// The internal state of an iterator that searches for matches of a substring
480 /// within a larger string using two-way search
482 struct TwoWaySearcher {
494 This is the Two-Way search algorithm, which was introduced in the paper:
495 Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675.
497 Here's some background information.
499 A *word* is a string of symbols. The *length* of a word should be a familiar
500 notion, and here we denote it for any word x by |x|.
501 (We also allow for the possibility of the *empty word*, a word of length zero).
503 If x is any non-empty word, then an integer p with 0 < p <= |x| is said to be a
504 *period* for x iff for all i with 0 <= i <= |x| - p - 1, we have x[i] == x[i+p].
505 For example, both 1 and 2 are periods for the string "aa". As another example,
506 the only period of the string "abcd" is 4.
508 We denote by period(x) the *smallest* period of x (provided that x is non-empty).
509 This is always well-defined since every non-empty word x has at least one period,
510 |x|. We sometimes call this *the period* of x.
512 If u, v and x are words such that x = uv, where uv is the concatenation of u and
513 v, then we say that (u, v) is a *factorization* of x.
515 Let (u, v) be a factorization for a word x. Then if w is a non-empty word such
516 that both of the following hold
518 - either w is a suffix of u or u is a suffix of w
519 - either w is a prefix of v or v is a prefix of w
521 then w is said to be a *repetition* for the factorization (u, v).
523 Just to unpack this, there are four possibilities here. Let w = "abc". Then we
526 - w is a suffix of u and w is a prefix of v. ex: ("lolabc", "abcde")
527 - w is a suffix of u and v is a prefix of w. ex: ("lolabc", "ab")
528 - u is a suffix of w and w is a prefix of v. ex: ("bc", "abchi")
529 - u is a suffix of w and v is a prefix of w. ex: ("bc", "a")
531 Note that the word vu is a repetition for any factorization (u,v) of x = uv,
532 so every factorization has at least one repetition.
534 If x is a string and (u, v) is a factorization for x, then a *local period* for
535 (u, v) is an integer r such that there is some word w such that |w| = r and w is
536 a repetition for (u, v).
538 We denote by local_period(u, v) the smallest local period of (u, v). We sometimes
539 call this *the local period* of (u, v). Provided that x = uv is non-empty, this
540 is well-defined (because each non-empty word has at least one factorization, as
543 It can be proven that the following is an equivalent definition of a local period
544 for a factorization (u, v): any positive integer r such that x[i] == x[i+r] for
545 all i such that |u| - r <= i <= |u| - 1 and such that both x[i] and x[i+r] are
546 defined. (i.e. i > 0 and i + r < |x|).
548 Using the above reformulation, it is easy to prove that
550 1 <= local_period(u, v) <= period(uv)
552 A factorization (u, v) of x such that local_period(u,v) = period(x) is called a
553 *critical factorization*.
555 The algorithm hinges on the following theorem, which is stated without proof:
557 **Critical Factorization Theorem** Any word x has at least one critical
558 factorization (u, v) such that |u| < period(x).
560 The purpose of maximal_suffix is to find such a critical factorization.
563 impl TwoWaySearcher {
564 fn new(needle: &[u8]) -> TwoWaySearcher {
565 let (crit_pos1, period1) = TwoWaySearcher::maximal_suffix(needle, false);
566 let (crit_pos2, period2) = TwoWaySearcher::maximal_suffix(needle, true);
570 if crit_pos1 > crit_pos2 {
571 crit_pos = crit_pos1;
574 crit_pos = crit_pos2;
578 // This isn't in the original algorithm, as far as I'm aware.
579 let byteset = needle.iter()
580 .fold(0, |a, &b| (1 << ((b & 0x3f) as uint)) | a);
582 // A particularly readable explanation of what's going on here can be found
583 // in Crochemore and Rytter's book "Text Algorithms", ch 13. Specifically
584 // see the code for "Algorithm CP" on p. 323.
586 // What's going on is we have some critical factorization (u, v) of the
587 // needle, and we want to determine whether u is a suffix of
588 // v[..period]. If it is, we use "Algorithm CP1". Otherwise we use
589 // "Algorithm CP2", which is optimized for when the period of the needle
591 if needle[..crit_pos] == needle[period.. period + crit_pos] {
603 period: cmp::max(crit_pos, needle.len() - crit_pos) + 1,
607 memory: uint::MAX // Dummy value to signify that the period is long
612 // One of the main ideas of Two-Way is that we factorize the needle into
613 // two halves, (u, v), and begin trying to find v in the haystack by scanning
614 // left to right. If v matches, we try to match u by scanning right to left.
615 // How far we can jump when we encounter a mismatch is all based on the fact
616 // that (u, v) is a critical factorization for the needle.
618 fn next(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> Option<(uint, uint)> {
620 // Check that we have room to search in
621 if self.position + needle.len() > haystack.len() {
625 // Quickly skip by large portions unrelated to our substring
627 ((haystack[self.position + needle.len() - 1] & 0x3f)
629 self.position += needle.len();
636 // See if the right part of the needle matches
637 let start = if long_period { self.crit_pos }
638 else { cmp::max(self.crit_pos, self.memory) };
639 for i in range(start, needle.len()) {
640 if needle[i] != haystack[self.position + i] {
641 self.position += i - self.crit_pos + 1;
649 // See if the left part of the needle matches
650 let start = if long_period { 0 } else { self.memory };
651 for i in range(start, self.crit_pos).rev() {
652 if needle[i] != haystack[self.position + i] {
653 self.position += self.period;
655 self.memory = needle.len() - self.period;
661 // We have found a match!
662 let match_pos = self.position;
663 self.position += needle.len(); // add self.period for all matches
665 self.memory = 0; // set to needle.len() - self.period for all matches
667 return Some((match_pos, match_pos + needle.len()));
671 // Computes a critical factorization (u, v) of `arr`.
672 // Specifically, returns (i, p), where i is the starting index of v in some
673 // critical factorization (u, v) and p = period(v)
675 fn maximal_suffix(arr: &[u8], reversed: bool) -> (uint, uint) {
676 let mut left = -1; // Corresponds to i in the paper
677 let mut right = 0; // Corresponds to j in the paper
678 let mut offset = 1; // Corresponds to k in the paper
679 let mut period = 1; // Corresponds to p in the paper
681 while right + offset < arr.len() {
685 a = arr[left + offset];
686 b = arr[right + offset];
688 a = arr[right + offset];
689 b = arr[left + offset];
692 // Suffix is smaller, period is entire prefix so far.
695 period = right - left;
697 // Advance through repetition of the current period.
698 if offset == period {
705 // Suffix is larger, start over from current location.
716 /// The internal state of an iterator that searches for matches of a substring
717 /// within a larger string using a dynamically chosen search algorithm
720 Naive(NaiveSearcher),
721 TwoWay(TwoWaySearcher),
722 TwoWayLong(TwoWaySearcher)
726 fn new(haystack: &[u8], needle: &[u8]) -> Searcher {
728 // FIXME(#16715): This unsigned integer addition will probably not
729 // overflow because that would mean that the memory almost solely
730 // consists of the needle. Needs #16715 to be formally fixed.
731 if needle.len() + 20 > haystack.len() {
732 Naive(NaiveSearcher::new())
734 let searcher = TwoWaySearcher::new(needle);
735 if searcher.memory == uint::MAX { // If the period is long
744 /// An iterator over the start and end indices of the matches of a
745 /// substring within a larger string
747 pub struct MatchIndices<'a> {
754 /// An iterator over the substrings of a string separated by a given
757 pub struct StrSplits<'a> {
758 it: MatchIndices<'a>,
763 impl<'a> Iterator<(uint, uint)> for MatchIndices<'a> {
765 fn next(&mut self) -> Option<(uint, uint)> {
766 match self.searcher {
767 Naive(ref mut searcher)
768 => searcher.next(self.haystack.as_bytes(), self.needle.as_bytes()),
769 TwoWay(ref mut searcher)
770 => searcher.next(self.haystack.as_bytes(), self.needle.as_bytes(), false),
771 TwoWayLong(ref mut searcher)
772 => searcher.next(self.haystack.as_bytes(), self.needle.as_bytes(), true)
777 impl<'a> Iterator<&'a str> for StrSplits<'a> {
779 fn next(&mut self) -> Option<&'a str> {
780 if self.finished { return None; }
782 match self.it.next() {
783 Some((from, to)) => {
784 let ret = Some(self.it.haystack.slice(self.last_end, from));
789 self.finished = true;
790 Some(self.it.haystack.slice(self.last_end, self.it.haystack.len()))
796 /// External iterator for a string's UTF16 codeunits.
797 /// Use with the `std::iter` module.
799 pub struct Utf16CodeUnits<'a> {
800 encoder: Utf16Encoder<Chars<'a>>
803 impl<'a> Iterator<u16> for Utf16CodeUnits<'a> {
805 fn next(&mut self) -> Option<u16> { self.encoder.next() }
808 fn size_hint(&self) -> (uint, Option<uint>) { self.encoder.size_hint() }
812 /// Iterator adaptor for encoding `char`s to UTF-16.
814 pub struct Utf16Encoder<I> {
819 impl<I> Utf16Encoder<I> {
820 /// Create an UTF-16 encoder from any `char` iterator.
821 pub fn new(chars: I) -> Utf16Encoder<I> where I: Iterator<char> {
822 Utf16Encoder { chars: chars, extra: 0 }
826 impl<I> Iterator<u16> for Utf16Encoder<I> where I: Iterator<char> {
828 fn next(&mut self) -> Option<u16> {
830 let tmp = self.extra;
835 let mut buf = [0u16, ..2];
836 self.chars.next().map(|ch| {
837 let n = ch.encode_utf16(buf[mut]).unwrap_or(0);
838 if n == 2 { self.extra = buf[1]; }
844 fn size_hint(&self) -> (uint, Option<uint>) {
845 let (low, high) = self.chars.size_hint();
846 // every char gets either one u16 or two u16,
847 // so this iterator is between 1 or 2 times as
848 // long as the underlying iterator.
849 (low, high.and_then(|n| n.checked_mul(2)))
854 Section: Comparing strings
857 // share the implementation of the lang-item vs. non-lang-item
859 /// NOTE: This function is (ab)used in rustc::middle::trans::_match
860 /// to compare &[u8] byte slices that are not necessarily valid UTF-8.
862 fn eq_slice_(a: &str, b: &str) -> bool {
863 #[allow(improper_ctypes)]
864 extern { fn memcmp(s1: *const i8, s2: *const i8, n: uint) -> i32; }
865 a.len() == b.len() && unsafe {
866 memcmp(a.as_ptr() as *const i8,
867 b.as_ptr() as *const i8,
872 /// Bytewise slice equality
873 /// NOTE: This function is (ab)used in rustc::middle::trans::_match
874 /// to compare &[u8] byte slices that are not necessarily valid UTF-8.
877 pub fn eq_slice(a: &str, b: &str) -> bool {
885 /// Walk through `iter` checking that it's a valid UTF-8 sequence,
886 /// returning `true` in that case, or, if it is invalid, `false` with
887 /// `iter` reset such that it is pointing at the first byte in the
888 /// invalid sequence.
890 fn run_utf8_validation_iterator(iter: &mut slice::Items<u8>) -> bool {
892 // save the current thing we're pointing at.
895 // restore the iterator we had at the start of this codepoint.
896 macro_rules! err ( () => { {*iter = old; return false} });
897 macro_rules! next ( () => {
900 // we needed data, but there was none: error!
905 let first = match iter.next() {
907 // we're at the end of the iterator and a codepoint
908 // boundary at the same time, so this string is valid.
912 // ASCII characters are always valid, so only large
913 // bytes need more examination.
915 let w = utf8_char_width(first);
916 let second = next!();
917 // 2-byte encoding is for codepoints \u0080 to \u07ff
918 // first C2 80 last DF BF
919 // 3-byte encoding is for codepoints \u0800 to \uffff
920 // first E0 A0 80 last EF BF BF
921 // excluding surrogates codepoints \ud800 to \udfff
922 // ED A0 80 to ED BF BF
923 // 4-byte encoding is for codepoints \u10000 to \u10ffff
924 // first F0 90 80 80 last F4 8F BF BF
926 // Use the UTF-8 syntax from the RFC
928 // https://tools.ietf.org/html/rfc3629
930 // UTF8-2 = %xC2-DF UTF8-tail
931 // UTF8-3 = %xE0 %xA0-BF UTF8-tail / %xE1-EC 2( UTF8-tail ) /
932 // %xED %x80-9F UTF8-tail / %xEE-EF 2( UTF8-tail )
933 // UTF8-4 = %xF0 %x90-BF 2( UTF8-tail ) / %xF1-F3 3( UTF8-tail ) /
934 // %xF4 %x80-8F 2( UTF8-tail )
936 2 => if second & !CONT_MASK != TAG_CONT_U8 {err!()},
938 match (first, second, next!() & !CONT_MASK) {
939 (0xE0 , 0xA0 ... 0xBF, TAG_CONT_U8) |
940 (0xE1 ... 0xEC, 0x80 ... 0xBF, TAG_CONT_U8) |
941 (0xED , 0x80 ... 0x9F, TAG_CONT_U8) |
942 (0xEE ... 0xEF, 0x80 ... 0xBF, TAG_CONT_U8) => {}
947 match (first, second, next!() & !CONT_MASK, next!() & !CONT_MASK) {
948 (0xF0 , 0x90 ... 0xBF, TAG_CONT_U8, TAG_CONT_U8) |
949 (0xF1 ... 0xF3, 0x80 ... 0xBF, TAG_CONT_U8, TAG_CONT_U8) |
950 (0xF4 , 0x80 ... 0x8F, TAG_CONT_U8, TAG_CONT_U8) => {}
960 /// Determines if a vector of bytes contains valid UTF-8.
961 pub fn is_utf8(v: &[u8]) -> bool {
962 run_utf8_validation_iterator(&mut v.iter())
965 /// Determines if a vector of `u16` contains valid UTF-16
966 pub fn is_utf16(v: &[u16]) -> bool {
967 let mut it = v.iter();
968 macro_rules! next ( ($ret:expr) => {
969 match it.next() { Some(u) => *u, None => return $ret }
975 match char::from_u32(u as u32) {
978 let u2 = next!(false);
979 if u < 0xD7FF || u > 0xDBFF ||
980 u2 < 0xDC00 || u2 > 0xDFFF { return false; }
986 /// An iterator that decodes UTF-16 encoded codepoints from a vector
989 pub struct Utf16Items<'a> {
990 iter: slice::Items<'a, u16>
992 /// The possibilities for values decoded from a `u16` stream.
993 #[deriving(PartialEq, Eq, Clone, Show)]
995 /// A valid codepoint.
997 /// An invalid surrogate without its pair.
1001 impl Copy for Utf16Item {}
1004 /// Convert `self` to a `char`, taking `LoneSurrogate`s to the
1005 /// replacement character (U+FFFD).
1007 pub fn to_char_lossy(&self) -> char {
1009 ScalarValue(c) => c,
1010 LoneSurrogate(_) => '\uFFFD'
1015 impl<'a> Iterator<Utf16Item> for Utf16Items<'a> {
1016 fn next(&mut self) -> Option<Utf16Item> {
1017 let u = match self.iter.next() {
1022 if u < 0xD800 || 0xDFFF < u {
1024 Some(ScalarValue(unsafe {mem::transmute(u as u32)}))
1025 } else if u >= 0xDC00 {
1026 // a trailing surrogate
1027 Some(LoneSurrogate(u))
1029 // preserve state for rewinding.
1030 let old = self.iter;
1032 let u2 = match self.iter.next() {
1035 None => return Some(LoneSurrogate(u))
1037 if u2 < 0xDC00 || u2 > 0xDFFF {
1038 // not a trailing surrogate so we're not a valid
1039 // surrogate pair, so rewind to redecode u2 next time.
1041 return Some(LoneSurrogate(u))
1044 // all ok, so lets decode it.
1045 let c = ((u - 0xD800) as u32 << 10 | (u2 - 0xDC00) as u32) + 0x1_0000;
1046 Some(ScalarValue(unsafe {mem::transmute(c)}))
1051 fn size_hint(&self) -> (uint, Option<uint>) {
1052 let (low, high) = self.iter.size_hint();
1053 // we could be entirely valid surrogates (2 elements per
1054 // char), or entirely non-surrogates (1 element per char)
1059 /// Create an iterator over the UTF-16 encoded codepoints in `v`,
1060 /// returning invalid surrogates as `LoneSurrogate`s.
1066 /// use std::str::{ScalarValue, LoneSurrogate};
1068 /// // 𝄞mus<invalid>ic<invalid>
1069 /// let v = [0xD834, 0xDD1E, 0x006d, 0x0075,
1070 /// 0x0073, 0xDD1E, 0x0069, 0x0063,
1073 /// assert_eq!(str::utf16_items(&v).collect::<Vec<_>>(),
1074 /// vec![ScalarValue('𝄞'),
1075 /// ScalarValue('m'), ScalarValue('u'), ScalarValue('s'),
1076 /// LoneSurrogate(0xDD1E),
1077 /// ScalarValue('i'), ScalarValue('c'),
1078 /// LoneSurrogate(0xD834)]);
1080 pub fn utf16_items<'a>(v: &'a [u16]) -> Utf16Items<'a> {
1081 Utf16Items { iter : v.iter() }
1084 /// Return a slice of `v` ending at (and not including) the first NUL
1093 /// let mut v = ['a' as u16, 'b' as u16, 'c' as u16, 'd' as u16];
1094 /// // no NULs so no change
1095 /// assert_eq!(str::truncate_utf16_at_nul(&v), v.as_slice());
1099 /// let b: &[_] = &['a' as u16, 'b' as u16];
1100 /// assert_eq!(str::truncate_utf16_at_nul(&v), b);
1102 pub fn truncate_utf16_at_nul<'a>(v: &'a [u16]) -> &'a [u16] {
1103 match v.iter().position(|c| *c == 0) {
1104 // don't include the 0
1110 // https://tools.ietf.org/html/rfc3629
1111 static UTF8_CHAR_WIDTH: [u8, ..256] = [
1112 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1113 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x1F
1114 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1115 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x3F
1116 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1117 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x5F
1118 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1119 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x7F
1120 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1121 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0x9F
1122 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1123 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0xBF
1124 0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
1125 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, // 0xDF
1126 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3, // 0xEF
1127 4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0, // 0xFF
1130 /// Given a first byte, determine how many bytes are in this UTF-8 character
1132 pub fn utf8_char_width(b: u8) -> uint {
1133 return UTF8_CHAR_WIDTH[b as uint] as uint;
1136 /// Struct that contains a `char` and the index of the first byte of
1137 /// the next `char` in a string. This can be used as a data structure
1138 /// for iterating over the UTF-8 bytes of a string.
1139 pub struct CharRange {
1142 /// Index of the first byte of the next `char`
1146 impl Copy for CharRange {}
1148 /// Mask of the value bits of a continuation byte
1149 const CONT_MASK: u8 = 0b0011_1111u8;
1150 /// Value of the tag bits (tag mask is !CONT_MASK) of a continuation byte
1151 const TAG_CONT_U8: u8 = 0b1000_0000u8;
1153 /// Unsafe operations
1158 use slice::SlicePrelude;
1159 use str::{is_utf8, StrPrelude};
1161 /// Converts a slice of bytes to a string slice without checking
1162 /// that the string contains valid UTF-8.
1163 #[deprecated = "renamed to str::from_utf8_unchecked"]
1164 pub unsafe fn from_utf8<'a>(v: &'a [u8]) -> &'a str {
1165 super::from_utf8_unchecked(v)
1168 /// Form a slice from a C string. Unsafe because the caller must ensure the
1169 /// C string has the static lifetime, or else the return value may be
1170 /// invalidated later.
1171 #[deprecated = "renamed to str::from_c_str"]
1172 pub unsafe fn c_str_to_static_slice(s: *const i8) -> &'static str {
1173 let s = s as *const u8;
1176 while *curr != 0u8 {
1178 curr = s.offset(len as int);
1180 let v = Slice { data: s, len: len };
1181 assert!(is_utf8(::mem::transmute(v)));
1185 /// Takes a bytewise (not UTF-8) slice from a string.
1187 /// Returns the substring from [`begin`..`end`).
1191 /// If begin is greater than end.
1192 /// If end is greater than the length of the string.
1194 #[deprecated = "call the slice_unchecked method instead"]
1195 pub unsafe fn slice_bytes<'a>(s: &'a str, begin: uint, end: uint) -> &'a str {
1196 assert!(begin <= end);
1197 assert!(end <= s.len());
1198 s.slice_unchecked(begin, end)
1201 /// Takes a bytewise (not UTF-8) slice from a string.
1203 /// Returns the substring from [`begin`..`end`).
1205 /// Caller must check slice boundaries!
1207 #[deprecated = "this has moved to a method on `str` directly"]
1208 pub unsafe fn slice_unchecked<'a>(s: &'a str, begin: uint, end: uint) -> &'a str {
1209 s.slice_unchecked(begin, end)
1214 Section: Trait implementations
1217 #[allow(missing_docs)]
1219 use cmp::{Ordering, Ord, PartialEq, PartialOrd, Equiv, Eq};
1220 use cmp::Ordering::{Less, Equal, Greater};
1221 use iter::IteratorExt;
1223 use option::Option::Some;
1225 use str::{Str, StrPrelude, eq_slice};
1229 fn cmp(&self, other: &str) -> Ordering {
1230 for (s_b, o_b) in self.bytes().zip(other.bytes()) {
1231 match s_b.cmp(&o_b) {
1232 Greater => return Greater,
1233 Less => return Less,
1238 self.len().cmp(&other.len())
1242 impl PartialEq for str {
1244 fn eq(&self, other: &str) -> bool {
1245 eq_slice(self, other)
1248 fn ne(&self, other: &str) -> bool { !(*self).eq(other) }
1253 impl PartialOrd for str {
1255 fn partial_cmp(&self, other: &str) -> Option<Ordering> {
1256 Some(self.cmp(other))
1260 #[allow(deprecated)]
1261 #[deprecated = "Use overloaded `core::cmp::PartialEq`"]
1262 impl<S: Str> Equiv<S> for str {
1264 fn equiv(&self, other: &S) -> bool { eq_slice(self, other.as_slice()) }
1267 impl ops::Slice<uint, str> for str {
1269 fn as_slice_<'a>(&'a self) -> &'a str {
1274 fn slice_from_or_fail<'a>(&'a self, from: &uint) -> &'a str {
1275 self.slice_from(*from)
1279 fn slice_to_or_fail<'a>(&'a self, to: &uint) -> &'a str {
1284 fn slice_or_fail<'a>(&'a self, from: &uint, to: &uint) -> &'a str {
1285 self.slice(*from, *to)
1290 /// Any string that can be represented as a slice
1291 pub trait Str for Sized? {
1292 /// Work with `self` as a slice.
1293 fn as_slice<'a>(&'a self) -> &'a str;
1298 fn as_slice<'a>(&'a self) -> &'a str { self }
1301 impl<'a, Sized? S> Str for &'a S where S: Str {
1303 fn as_slice(&self) -> &str { Str::as_slice(*self) }
1306 /// Methods for string slices
1307 pub trait StrPrelude for Sized? {
1308 /// Returns true if one string contains another
1312 /// - needle - The string to look for
1317 /// assert!("bananas".contains("nana"));
1319 fn contains(&self, needle: &str) -> bool;
1321 /// Returns true if a string contains a char.
1325 /// - needle - The char to look for
1330 /// assert!("hello".contains_char('e'));
1332 fn contains_char(&self, needle: char) -> bool;
1334 /// An iterator over the characters of `self`. Note, this iterates
1335 /// over Unicode code-points, not Unicode graphemes.
1340 /// let v: Vec<char> = "abc åäö".chars().collect();
1341 /// assert_eq!(v, vec!['a', 'b', 'c', ' ', 'å', 'ä', 'ö']);
1343 fn chars<'a>(&'a self) -> Chars<'a>;
1345 /// An iterator over the bytes of `self`
1350 /// let v: Vec<u8> = "bors".bytes().collect();
1351 /// assert_eq!(v, b"bors".to_vec());
1353 fn bytes<'a>(&'a self) -> Bytes<'a>;
1355 /// An iterator over the characters of `self` and their byte offsets.
1356 fn char_indices<'a>(&'a self) -> CharOffsets<'a>;
1358 /// An iterator over substrings of `self`, separated by characters
1359 /// matched by `sep`.
1364 /// let v: Vec<&str> = "Mary had a little lamb".split(' ').collect();
1365 /// assert_eq!(v, vec!["Mary", "had", "a", "little", "lamb"]);
1367 /// let v: Vec<&str> = "abc1def2ghi".split(|c: char| c.is_numeric()).collect();
1368 /// assert_eq!(v, vec!["abc", "def", "ghi"]);
1370 /// let v: Vec<&str> = "lionXXtigerXleopard".split('X').collect();
1371 /// assert_eq!(v, vec!["lion", "", "tiger", "leopard"]);
1373 /// let v: Vec<&str> = "".split('X').collect();
1374 /// assert_eq!(v, vec![""]);
1376 fn split<'a, Sep: CharEq>(&'a self, sep: Sep) -> CharSplits<'a, Sep>;
1378 /// An iterator over substrings of `self`, separated by characters
1379 /// matched by `sep`, restricted to splitting at most `count`
1385 /// let v: Vec<&str> = "Mary had a little lambda".splitn(2, ' ').collect();
1386 /// assert_eq!(v, vec!["Mary", "had", "a little lambda"]);
1388 /// let v: Vec<&str> = "abc1def2ghi".splitn(1, |c: char| c.is_numeric()).collect();
1389 /// assert_eq!(v, vec!["abc", "def2ghi"]);
1391 /// let v: Vec<&str> = "lionXXtigerXleopard".splitn(2, 'X').collect();
1392 /// assert_eq!(v, vec!["lion", "", "tigerXleopard"]);
1394 /// let v: Vec<&str> = "abcXdef".splitn(0, 'X').collect();
1395 /// assert_eq!(v, vec!["abcXdef"]);
1397 /// let v: Vec<&str> = "".splitn(1, 'X').collect();
1398 /// assert_eq!(v, vec![""]);
1400 fn splitn<'a, Sep: CharEq>(&'a self, count: uint, sep: Sep) -> CharSplitsN<'a, Sep>;
1402 /// An iterator over substrings of `self`, separated by characters
1403 /// matched by `sep`.
1405 /// Equivalent to `split`, except that the trailing substring
1406 /// is skipped if empty (terminator semantics).
1411 /// let v: Vec<&str> = "A.B.".split_terminator('.').collect();
1412 /// assert_eq!(v, vec!["A", "B"]);
1414 /// let v: Vec<&str> = "A..B..".split_terminator('.').collect();
1415 /// assert_eq!(v, vec!["A", "", "B", ""]);
1417 /// let v: Vec<&str> = "Mary had a little lamb".split(' ').rev().collect();
1418 /// assert_eq!(v, vec!["lamb", "little", "a", "had", "Mary"]);
1420 /// let v: Vec<&str> = "abc1def2ghi".split(|c: char| c.is_numeric()).rev().collect();
1421 /// assert_eq!(v, vec!["ghi", "def", "abc"]);
1423 /// let v: Vec<&str> = "lionXXtigerXleopard".split('X').rev().collect();
1424 /// assert_eq!(v, vec!["leopard", "tiger", "", "lion"]);
1426 fn split_terminator<'a, Sep: CharEq>(&'a self, sep: Sep) -> CharSplits<'a, Sep>;
1428 /// An iterator over substrings of `self`, separated by characters
1429 /// matched by `sep`, starting from the end of the string.
1430 /// Restricted to splitting at most `count` times.
1435 /// let v: Vec<&str> = "Mary had a little lamb".rsplitn(2, ' ').collect();
1436 /// assert_eq!(v, vec!["lamb", "little", "Mary had a"]);
1438 /// let v: Vec<&str> = "abc1def2ghi".rsplitn(1, |c: char| c.is_numeric()).collect();
1439 /// assert_eq!(v, vec!["ghi", "abc1def"]);
1441 /// let v: Vec<&str> = "lionXXtigerXleopard".rsplitn(2, 'X').collect();
1442 /// assert_eq!(v, vec!["leopard", "tiger", "lionX"]);
1444 fn rsplitn<'a, Sep: CharEq>(&'a self, count: uint, sep: Sep) -> CharSplitsN<'a, Sep>;
1446 /// An iterator over the start and end indices of the disjoint
1447 /// matches of `sep` within `self`.
1449 /// That is, each returned value `(start, end)` satisfies
1450 /// `self.slice(start, end) == sep`. For matches of `sep` within
1451 /// `self` that overlap, only the indices corresponding to the
1452 /// first match are returned.
1457 /// let v: Vec<(uint, uint)> = "abcXXXabcYYYabc".match_indices("abc").collect();
1458 /// assert_eq!(v, vec![(0,3), (6,9), (12,15)]);
1460 /// let v: Vec<(uint, uint)> = "1abcabc2".match_indices("abc").collect();
1461 /// assert_eq!(v, vec![(1,4), (4,7)]);
1463 /// let v: Vec<(uint, uint)> = "ababa".match_indices("aba").collect();
1464 /// assert_eq!(v, vec![(0, 3)]); // only the first `aba`
1466 fn match_indices<'a>(&'a self, sep: &'a str) -> MatchIndices<'a>;
1468 /// An iterator over the substrings of `self` separated by `sep`.
1473 /// let v: Vec<&str> = "abcXXXabcYYYabc".split_str("abc").collect();
1474 /// assert_eq!(v, vec!["", "XXX", "YYY", ""]);
1476 /// let v: Vec<&str> = "1abcabc2".split_str("abc").collect();
1477 /// assert_eq!(v, vec!["1", "", "2"]);
1479 fn split_str<'a>(&'a self, &'a str) -> StrSplits<'a>;
1481 /// An iterator over the lines of a string (subsequences separated
1482 /// by `\n`). This does not include the empty string after a
1488 /// let four_lines = "foo\nbar\n\nbaz\n";
1489 /// let v: Vec<&str> = four_lines.lines().collect();
1490 /// assert_eq!(v, vec!["foo", "bar", "", "baz"]);
1492 fn lines<'a>(&'a self) -> CharSplits<'a, char>;
1494 /// An iterator over the lines of a string, separated by either
1495 /// `\n` or `\r\n`. As with `.lines()`, this does not include an
1496 /// empty trailing line.
1501 /// let four_lines = "foo\r\nbar\n\r\nbaz\n";
1502 /// let v: Vec<&str> = four_lines.lines_any().collect();
1503 /// assert_eq!(v, vec!["foo", "bar", "", "baz"]);
1505 fn lines_any<'a>(&'a self) -> AnyLines<'a>;
1507 /// Returns the number of Unicode code points (`char`) that a
1510 /// This does not perform any normalization, and is `O(n)`, since
1511 /// UTF-8 is a variable width encoding of code points.
1513 /// *Warning*: The number of code points in a string does not directly
1514 /// correspond to the number of visible characters or width of the
1515 /// visible text due to composing characters, and double- and
1516 /// zero-width ones.
1518 /// See also `.len()` for the byte length.
1523 /// // composed forms of `ö` and `é`
1524 /// let c = "Löwe 老虎 Léopard"; // German, Simplified Chinese, French
1525 /// // decomposed forms of `ö` and `é`
1526 /// let d = "Lo\u0308we 老虎 Le\u0301opard";
1528 /// assert_eq!(c.char_len(), 15);
1529 /// assert_eq!(d.char_len(), 17);
1531 /// assert_eq!(c.len(), 21);
1532 /// assert_eq!(d.len(), 23);
1534 /// // the two strings *look* the same
1535 /// println!("{}", c);
1536 /// println!("{}", d);
1538 fn char_len(&self) -> uint;
1540 /// Returns a slice of the given string from the byte range
1541 /// [`begin`..`end`).
1543 /// This operation is `O(1)`.
1545 /// Panics when `begin` and `end` do not point to valid characters
1546 /// or point beyond the last character of the string.
1548 /// See also `slice_to` and `slice_from` for slicing prefixes and
1549 /// suffixes of strings, and `slice_chars` for slicing based on
1550 /// code point counts.
1555 /// let s = "Löwe 老虎 Léopard";
1556 /// assert_eq!(s.slice(0, 1), "L");
1558 /// assert_eq!(s.slice(1, 9), "öwe 老");
1560 /// // these will panic:
1561 /// // byte 2 lies within `ö`:
1562 /// // s.slice(2, 3);
1564 /// // byte 8 lies within `老`
1565 /// // s.slice(1, 8);
1567 /// // byte 100 is outside the string
1568 /// // s.slice(3, 100);
1570 fn slice<'a>(&'a self, begin: uint, end: uint) -> &'a str;
1572 /// Returns a slice of the string from `begin` to its end.
1574 /// Equivalent to `self.slice(begin, self.len())`.
1576 /// Panics when `begin` does not point to a valid character, or is
1579 /// See also `slice`, `slice_to` and `slice_chars`.
1580 fn slice_from<'a>(&'a self, begin: uint) -> &'a str;
1582 /// Returns a slice of the string from the beginning to byte
1585 /// Equivalent to `self.slice(0, end)`.
1587 /// Panics when `end` does not point to a valid character, or is
1590 /// See also `slice`, `slice_from` and `slice_chars`.
1591 fn slice_to<'a>(&'a self, end: uint) -> &'a str;
1593 /// Returns a slice of the string from the character range
1594 /// [`begin`..`end`).
1596 /// That is, start at the `begin`-th code point of the string and
1597 /// continue to the `end`-th code point. This does not detect or
1598 /// handle edge cases such as leaving a combining character as the
1599 /// first code point of the string.
1601 /// Due to the design of UTF-8, this operation is `O(end)`.
1602 /// See `slice`, `slice_to` and `slice_from` for `O(1)`
1603 /// variants that use byte indices rather than code point
1606 /// Panics if `begin` > `end` or the either `begin` or `end` are
1607 /// beyond the last character of the string.
1612 /// let s = "Löwe 老虎 Léopard";
1613 /// assert_eq!(s.slice_chars(0, 4), "Löwe");
1614 /// assert_eq!(s.slice_chars(5, 7), "老虎");
1616 fn slice_chars<'a>(&'a self, begin: uint, end: uint) -> &'a str;
1618 /// Takes a bytewise (not UTF-8) slice from a string.
1620 /// Returns the substring from [`begin`..`end`).
1622 /// Caller must check both UTF-8 character boundaries and the boundaries of
1623 /// the entire slice as well.
1624 unsafe fn slice_unchecked<'a>(&'a self, begin: uint, end: uint) -> &'a str;
1626 /// Returns true if `needle` is a prefix of the string.
1631 /// assert!("banana".starts_with("ba"));
1633 fn starts_with(&self, needle: &str) -> bool;
1635 /// Returns true if `needle` is a suffix of the string.
1640 /// assert!("banana".ends_with("nana"));
1642 fn ends_with(&self, needle: &str) -> bool;
1644 /// Returns a string with characters that match `to_trim` removed from the left and the right.
1648 /// * to_trim - a character matcher
1653 /// assert_eq!("11foo1bar11".trim_chars('1'), "foo1bar")
1654 /// let x: &[_] = &['1', '2'];
1655 /// assert_eq!("12foo1bar12".trim_chars(x), "foo1bar")
1656 /// assert_eq!("123foo1bar123".trim_chars(|c: char| c.is_numeric()), "foo1bar")
1658 fn trim_chars<'a, C: CharEq>(&'a self, to_trim: C) -> &'a str;
1660 /// Returns a string with leading `chars_to_trim` removed.
1664 /// * to_trim - a character matcher
1669 /// assert_eq!("11foo1bar11".trim_left_chars('1'), "foo1bar11")
1670 /// let x: &[_] = &['1', '2'];
1671 /// assert_eq!("12foo1bar12".trim_left_chars(x), "foo1bar12")
1672 /// assert_eq!("123foo1bar123".trim_left_chars(|c: char| c.is_numeric()), "foo1bar123")
1674 fn trim_left_chars<'a, C: CharEq>(&'a self, to_trim: C) -> &'a str;
1676 /// Returns a string with trailing `chars_to_trim` removed.
1680 /// * to_trim - a character matcher
1685 /// assert_eq!("11foo1bar11".trim_right_chars('1'), "11foo1bar")
1686 /// let x: &[_] = &['1', '2'];
1687 /// assert_eq!("12foo1bar12".trim_right_chars(x), "12foo1bar")
1688 /// assert_eq!("123foo1bar123".trim_right_chars(|c: char| c.is_numeric()), "123foo1bar")
1690 fn trim_right_chars<'a, C: CharEq>(&'a self, to_trim: C) -> &'a str;
1692 /// Check that `index`-th byte lies at the start and/or end of a
1693 /// UTF-8 code point sequence.
1695 /// The start and end of the string (when `index == self.len()`)
1696 /// are considered to be boundaries.
1698 /// Panics if `index` is greater than `self.len()`.
1703 /// let s = "Löwe 老虎 Léopard";
1704 /// assert!(s.is_char_boundary(0));
1706 /// assert!(s.is_char_boundary(6));
1707 /// assert!(s.is_char_boundary(s.len()));
1709 /// // second byte of `ö`
1710 /// assert!(!s.is_char_boundary(2));
1712 /// // third byte of `老`
1713 /// assert!(!s.is_char_boundary(8));
1715 fn is_char_boundary(&self, index: uint) -> bool;
1717 /// Pluck a character out of a string and return the index of the next
1720 /// This function can be used to iterate over the Unicode characters of a
1725 /// This example manually iterates through the characters of a
1726 /// string; this should normally be done by `.chars()` or
1727 /// `.char_indices`.
1730 /// use std::str::CharRange;
1732 /// let s = "中华Việt Nam";
1734 /// while i < s.len() {
1735 /// let CharRange {ch, next} = s.char_range_at(i);
1736 /// println!("{}: {}", i, ch);
1758 /// * s - The string
1759 /// * i - The byte offset of the char to extract
1763 /// A record {ch: char, next: uint} containing the char value and the byte
1764 /// index of the next Unicode character.
1768 /// If `i` is greater than or equal to the length of the string.
1769 /// If `i` is not the index of the beginning of a valid UTF-8 character.
1770 fn char_range_at(&self, start: uint) -> CharRange;
1772 /// Given a byte position and a str, return the previous char and its position.
1774 /// This function can be used to iterate over a Unicode string in reverse.
1776 /// Returns 0 for next index if called on start index 0.
1780 /// If `i` is greater than the length of the string.
1781 /// If `i` is not an index following a valid UTF-8 character.
1782 fn char_range_at_reverse(&self, start: uint) -> CharRange;
1784 /// Plucks the character starting at the `i`th byte of a string.
1790 /// assert_eq!(s.char_at(1), 'b');
1791 /// assert_eq!(s.char_at(2), 'π');
1792 /// assert_eq!(s.char_at(4), 'c');
1797 /// If `i` is greater than or equal to the length of the string.
1798 /// If `i` is not the index of the beginning of a valid UTF-8 character.
1799 fn char_at(&self, i: uint) -> char;
1801 /// Plucks the character ending at the `i`th byte of a string.
1805 /// If `i` is greater than the length of the string.
1806 /// If `i` is not an index following a valid UTF-8 character.
1807 fn char_at_reverse(&self, i: uint) -> char;
1809 /// Work with the byte buffer of a string as a byte slice.
1814 /// assert_eq!("bors".as_bytes(), b"bors");
1816 fn as_bytes<'a>(&'a self) -> &'a [u8];
1818 /// Returns the byte index of the first character of `self` that
1819 /// matches `search`.
1823 /// `Some` containing the byte index of the last matching character
1824 /// or `None` if there is no match
1829 /// let s = "Löwe 老虎 Léopard";
1831 /// assert_eq!(s.find('L'), Some(0));
1832 /// assert_eq!(s.find('é'), Some(14));
1834 /// // the first space
1835 /// assert_eq!(s.find(|c: char| c.is_whitespace()), Some(5));
1837 /// // neither are found
1838 /// let x: &[_] = &['1', '2'];
1839 /// assert_eq!(s.find(x), None);
1841 fn find<C: CharEq>(&self, search: C) -> Option<uint>;
1843 /// Returns the byte index of the last character of `self` that
1844 /// matches `search`.
1848 /// `Some` containing the byte index of the last matching character
1849 /// or `None` if there is no match.
1854 /// let s = "Löwe 老虎 Léopard";
1856 /// assert_eq!(s.rfind('L'), Some(13));
1857 /// assert_eq!(s.rfind('é'), Some(14));
1859 /// // the second space
1860 /// assert_eq!(s.rfind(|c: char| c.is_whitespace()), Some(12));
1862 /// // searches for an occurrence of either `1` or `2`, but neither are found
1863 /// let x: &[_] = &['1', '2'];
1864 /// assert_eq!(s.rfind(x), None);
1866 fn rfind<C: CharEq>(&self, search: C) -> Option<uint>;
1868 /// Returns the byte index of the first matching substring
1872 /// * `needle` - The string to search for
1876 /// `Some` containing the byte index of the first matching substring
1877 /// or `None` if there is no match.
1882 /// let s = "Löwe 老虎 Léopard";
1884 /// assert_eq!(s.find_str("老虎 L"), Some(6));
1885 /// assert_eq!(s.find_str("muffin man"), None);
1887 fn find_str(&self, &str) -> Option<uint>;
1889 /// Retrieves the first character from a string slice and returns
1890 /// it. This does not allocate a new string; instead, it returns a
1891 /// slice that point one character beyond the character that was
1892 /// shifted. If the string does not contain any characters,
1893 /// None is returned instead.
1898 /// let s = "Löwe 老虎 Léopard";
1899 /// let (c, s1) = s.slice_shift_char().unwrap();
1900 /// assert_eq!(c, 'L');
1901 /// assert_eq!(s1, "öwe 老虎 Léopard");
1903 /// let (c, s2) = s1.slice_shift_char().unwrap();
1904 /// assert_eq!(c, 'ö');
1905 /// assert_eq!(s2, "we 老虎 Léopard");
1907 fn slice_shift_char<'a>(&'a self) -> Option<(char, &'a str)>;
1909 /// Returns the byte offset of an inner slice relative to an enclosing outer slice.
1911 /// Panics if `inner` is not a direct slice contained within self.
1916 /// let string = "a\nb\nc";
1917 /// let lines: Vec<&str> = string.lines().collect();
1919 /// assert!(string.subslice_offset(lines[0]) == 0); // &"a"
1920 /// assert!(string.subslice_offset(lines[1]) == 2); // &"b"
1921 /// assert!(string.subslice_offset(lines[2]) == 4); // &"c"
1923 fn subslice_offset(&self, inner: &str) -> uint;
1925 /// Return an unsafe pointer to the strings buffer.
1927 /// The caller must ensure that the string outlives this pointer,
1928 /// and that it is not reallocated (e.g. by pushing to the
1930 fn as_ptr(&self) -> *const u8;
1932 /// Return an iterator of `u16` over the string encoded as UTF-16.
1933 fn utf16_units<'a>(&'a self) -> Utf16CodeUnits<'a>;
1935 /// Return the number of bytes in this string
1940 /// assert_eq!("foo".len(), 3);
1941 /// assert_eq!("ƒoo".len(), 4);
1943 #[experimental = "not triaged yet"]
1944 fn len(&self) -> uint;
1946 /// Returns true if this slice contains no bytes
1951 /// assert!("".is_empty());
1954 #[experimental = "not triaged yet"]
1955 fn is_empty(&self) -> bool { self.len() == 0 }
1959 fn slice_error_fail(s: &str, begin: uint, end: uint) -> ! {
1960 assert!(begin <= end);
1961 panic!("index {} and/or {} in `{}` do not lie on character boundary",
1965 impl StrPrelude for str {
1967 fn contains(&self, needle: &str) -> bool {
1968 self.find_str(needle).is_some()
1972 fn contains_char(&self, needle: char) -> bool {
1973 self.find(needle).is_some()
1977 fn chars(&self) -> Chars {
1978 Chars{iter: self.as_bytes().iter()}
1982 fn bytes(&self) -> Bytes {
1983 self.as_bytes().iter().map(|&b| b)
1987 fn char_indices(&self) -> CharOffsets {
1988 CharOffsets{front_offset: 0, iter: self.chars()}
1992 fn split<Sep: CharEq>(&self, sep: Sep) -> CharSplits<Sep> {
1995 only_ascii: sep.only_ascii(),
1997 allow_trailing_empty: true,
2003 fn splitn<Sep: CharEq>(&self, count: uint, sep: Sep)
2004 -> CharSplitsN<Sep> {
2006 iter: self.split(sep),
2013 fn split_terminator<Sep: CharEq>(&self, sep: Sep)
2014 -> CharSplits<Sep> {
2016 allow_trailing_empty: false,
2022 fn rsplitn<Sep: CharEq>(&self, count: uint, sep: Sep)
2023 -> CharSplitsN<Sep> {
2025 iter: self.split(sep),
2032 fn match_indices<'a>(&'a self, sep: &'a str) -> MatchIndices<'a> {
2033 assert!(!sep.is_empty())
2037 searcher: Searcher::new(self.as_bytes(), sep.as_bytes())
2042 fn split_str<'a>(&'a self, sep: &'a str) -> StrSplits<'a> {
2044 it: self.match_indices(sep),
2051 fn lines(&self) -> CharSplits<char> {
2052 self.split_terminator('\n')
2055 fn lines_any(&self) -> AnyLines {
2056 self.lines().map(|line| {
2058 if l > 0 && line.as_bytes()[l - 1] == b'\r' { line.slice(0, l - 1) }
2064 fn char_len(&self) -> uint { self.chars().count() }
2067 fn slice(&self, begin: uint, end: uint) -> &str {
2068 // is_char_boundary checks that the index is in [0, .len()]
2070 self.is_char_boundary(begin) &&
2071 self.is_char_boundary(end) {
2072 unsafe { self.slice_unchecked(begin, end) }
2074 slice_error_fail(self, begin, end)
2079 fn slice_from(&self, begin: uint) -> &str {
2080 // is_char_boundary checks that the index is in [0, .len()]
2081 if self.is_char_boundary(begin) {
2082 unsafe { self.slice_unchecked(begin, self.len()) }
2084 slice_error_fail(self, begin, self.len())
2089 fn slice_to(&self, end: uint) -> &str {
2090 // is_char_boundary checks that the index is in [0, .len()]
2091 if self.is_char_boundary(end) {
2092 unsafe { self.slice_unchecked(0, end) }
2094 slice_error_fail(self, 0, end)
2098 fn slice_chars(&self, begin: uint, end: uint) -> &str {
2099 assert!(begin <= end);
2101 let mut begin_byte = None;
2102 let mut end_byte = None;
2104 // This could be even more efficient by not decoding,
2105 // only finding the char boundaries
2106 for (idx, _) in self.char_indices() {
2107 if count == begin { begin_byte = Some(idx); }
2108 if count == end { end_byte = Some(idx); break; }
2111 if begin_byte.is_none() && count == begin { begin_byte = Some(self.len()) }
2112 if end_byte.is_none() && count == end { end_byte = Some(self.len()) }
2114 match (begin_byte, end_byte) {
2115 (None, _) => panic!("slice_chars: `begin` is beyond end of string"),
2116 (_, None) => panic!("slice_chars: `end` is beyond end of string"),
2117 (Some(a), Some(b)) => unsafe { self.slice_unchecked(a, b) }
2122 unsafe fn slice_unchecked(&self, begin: uint, end: uint) -> &str {
2123 mem::transmute(Slice {
2124 data: self.as_ptr().offset(begin as int),
2130 fn starts_with(&self, needle: &str) -> bool {
2131 let n = needle.len();
2132 self.len() >= n && needle.as_bytes() == self.as_bytes()[..n]
2136 fn ends_with(&self, needle: &str) -> bool {
2137 let (m, n) = (self.len(), needle.len());
2138 m >= n && needle.as_bytes() == self.as_bytes()[m-n..]
2142 fn trim_chars<C: CharEq>(&self, mut to_trim: C) -> &str {
2143 let cur = match self.find(|c: char| !to_trim.matches(c)) {
2145 Some(i) => unsafe { self.slice_unchecked(i, self.len()) }
2147 match cur.rfind(|c: char| !to_trim.matches(c)) {
2150 let right = cur.char_range_at(i).next;
2151 unsafe { cur.slice_unchecked(0, right) }
2157 fn trim_left_chars<C: CharEq>(&self, mut to_trim: C) -> &str {
2158 match self.find(|c: char| !to_trim.matches(c)) {
2160 Some(first) => unsafe { self.slice_unchecked(first, self.len()) }
2165 fn trim_right_chars<C: CharEq>(&self, mut to_trim: C) -> &str {
2166 match self.rfind(|c: char| !to_trim.matches(c)) {
2169 let next = self.char_range_at(last).next;
2170 unsafe { self.slice_unchecked(0u, next) }
2176 fn is_char_boundary(&self, index: uint) -> bool {
2177 if index == self.len() { return true; }
2178 match self.as_bytes().get(index) {
2180 Some(&b) => b < 128u8 || b >= 192u8,
2185 fn char_range_at(&self, i: uint) -> CharRange {
2186 if self.as_bytes()[i] < 128u8 {
2187 return CharRange {ch: self.as_bytes()[i] as char, next: i + 1 };
2190 // Multibyte case is a fn to allow char_range_at to inline cleanly
2191 fn multibyte_char_range_at(s: &str, i: uint) -> CharRange {
2192 let mut val = s.as_bytes()[i] as u32;
2193 let w = UTF8_CHAR_WIDTH[val as uint] as uint;
2196 val = utf8_first_byte!(val, w);
2197 val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 1]);
2198 if w > 2 { val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 2]); }
2199 if w > 3 { val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 3]); }
2201 return CharRange {ch: unsafe { mem::transmute(val) }, next: i + w};
2204 return multibyte_char_range_at(self, i);
2208 fn char_range_at_reverse(&self, start: uint) -> CharRange {
2209 let mut prev = start;
2211 prev = prev.saturating_sub(1);
2212 if self.as_bytes()[prev] < 128 {
2213 return CharRange{ch: self.as_bytes()[prev] as char, next: prev}
2216 // Multibyte case is a fn to allow char_range_at_reverse to inline cleanly
2217 fn multibyte_char_range_at_reverse(s: &str, mut i: uint) -> CharRange {
2218 // while there is a previous byte == 10......
2219 while i > 0 && s.as_bytes()[i] & !CONT_MASK == TAG_CONT_U8 {
2223 let mut val = s.as_bytes()[i] as u32;
2224 let w = UTF8_CHAR_WIDTH[val as uint] as uint;
2227 val = utf8_first_byte!(val, w);
2228 val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 1]);
2229 if w > 2 { val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 2]); }
2230 if w > 3 { val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 3]); }
2232 return CharRange {ch: unsafe { mem::transmute(val) }, next: i};
2235 return multibyte_char_range_at_reverse(self, prev);
2239 fn char_at(&self, i: uint) -> char {
2240 self.char_range_at(i).ch
2244 fn char_at_reverse(&self, i: uint) -> char {
2245 self.char_range_at_reverse(i).ch
2249 fn as_bytes(&self) -> &[u8] {
2250 unsafe { mem::transmute(self) }
2253 fn find<C: CharEq>(&self, mut search: C) -> Option<uint> {
2254 if search.only_ascii() {
2255 self.bytes().position(|b| search.matches(b as char))
2257 for (index, c) in self.char_indices() {
2258 if search.matches(c) { return Some(index); }
2264 fn rfind<C: CharEq>(&self, mut search: C) -> Option<uint> {
2265 if search.only_ascii() {
2266 self.bytes().rposition(|b| search.matches(b as char))
2268 for (index, c) in self.char_indices().rev() {
2269 if search.matches(c) { return Some(index); }
2275 fn find_str(&self, needle: &str) -> Option<uint> {
2276 if needle.is_empty() {
2279 self.match_indices(needle)
2281 .map(|(start, _end)| start)
2286 fn slice_shift_char(&self) -> Option<(char, &str)> {
2287 if self.is_empty() {
2290 let CharRange {ch, next} = self.char_range_at(0u);
2291 let next_s = unsafe { self.slice_unchecked(next, self.len()) };
2296 fn subslice_offset(&self, inner: &str) -> uint {
2297 let a_start = self.as_ptr() as uint;
2298 let a_end = a_start + self.len();
2299 let b_start = inner.as_ptr() as uint;
2300 let b_end = b_start + inner.len();
2302 assert!(a_start <= b_start);
2303 assert!(b_end <= a_end);
2308 fn as_ptr(&self) -> *const u8 {
2313 fn utf16_units(&self) -> Utf16CodeUnits {
2314 Utf16CodeUnits { encoder: Utf16Encoder::new(self.chars()) }
2318 fn len(&self) -> uint { self.repr().len }
2321 impl<'a> Default for &'a str {
2322 fn default() -> &'a str { "" }