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 use self::Searcher
::{Naive, TwoWay, TwoWayLong}
;
26 use iter
::ExactSizeIterator
;
27 use iter
::{Map, Iterator, IteratorExt, DoubleEndedIterator}
;
32 use option
::Option
::{self, None, Some}
;
34 use raw
::{Repr, Slice}
;
35 use result
::Result
::{self, Ok, Err}
;
36 use slice
::{self, SliceExt}
;
39 macro_rules
! delegate_iter
{
40 (exact $te
:ty
: $ti
:ty
) => {
41 delegate_iter
!{$te : $ti}
42 impl<'a
> ExactSizeIterator
for $ti
{
44 fn len(&self) -> usize {
49 ($te
:ty
: $ti
:ty
) => {
50 #[stable(feature = "rust1", since = "1.0.0")]
51 impl<'a
> Iterator
for $ti
{
55 fn next(&mut self) -> Option
<$te
> {
59 fn size_hint(&self) -> (usize, Option
<usize>) {
63 #[stable(feature = "rust1", since = "1.0.0")]
64 impl<'a
> DoubleEndedIterator
for $ti
{
66 fn next_back(&mut self) -> Option
<$te
> {
71 (pattern $te
:ty
: $ti
:ty
) => {
72 #[stable(feature = "rust1", since = "1.0.0")]
73 impl<'a
, P
: CharEq
> Iterator
for $ti
{
77 fn next(&mut self) -> Option
<$te
> {
81 fn size_hint(&self) -> (usize, Option
<usize>) {
85 #[stable(feature = "rust1", since = "1.0.0")]
86 impl<'a
, P
: CharEq
> DoubleEndedIterator
for $ti
{
88 fn next_back(&mut self) -> Option
<$te
> {
93 (pattern forward $te
:ty
: $ti
:ty
) => {
94 #[stable(feature = "rust1", since = "1.0.0")]
95 impl<'a
, P
: CharEq
> Iterator
for $ti
{
99 fn next(&mut self) -> Option
<$te
> {
103 fn size_hint(&self) -> (usize, Option
<usize>) {
110 /// A trait to abstract the idea of creating a new instance of a type from a
112 #[stable(feature = "rust1", since = "1.0.0")]
114 /// The associated error which can be returned from parsing.
115 #[stable(feature = "rust1", since = "1.0.0")]
118 /// Parses a string `s` to return an optional value of this type. If the
119 /// string is ill-formatted, the None is returned.
120 #[stable(feature = "rust1", since = "1.0.0")]
121 fn from_str(s
: &str) -> Result
<Self, Self::Err
>;
124 #[stable(feature = "rust1", since = "1.0.0")]
125 impl FromStr
for bool
{
126 type Err
= ParseBoolError
;
128 /// Parse a `bool` from a string.
130 /// Yields an `Option<bool>`, because `s` may or may not actually be
136 /// assert_eq!("true".parse(), Ok(true));
137 /// assert_eq!("false".parse(), Ok(false));
138 /// assert!("not even a boolean".parse::<bool>().is_err());
141 fn from_str(s
: &str) -> Result
<bool
, ParseBoolError
> {
144 "false" => Ok(false),
145 _
=> Err(ParseBoolError { _priv: () }
),
150 /// An error returned when parsing a `bool` from a string fails.
151 #[derive(Debug, Clone, PartialEq)]
152 #[stable(feature = "rust1", since = "1.0.0")]
153 pub struct ParseBoolError { _priv: () }
155 #[stable(feature = "rust1", since = "1.0.0")]
156 impl fmt
::Display
for ParseBoolError
{
157 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
158 "provided string was not `true` or `false`".fmt(f
)
162 #[stable(feature = "rust1", since = "1.0.0")]
163 impl Error
for ParseBoolError
{
164 fn description(&self) -> &str { "failed to parse bool" }
168 Section: Creating a string
171 /// Errors which can occur when attempting to interpret a byte slice as a `str`.
172 #[derive(Copy, Eq, PartialEq, Clone, Debug)]
173 #[unstable(feature = "core",
174 reason
= "error enumeration recently added and definitions may be refined")]
176 /// An invalid byte was detected at the byte offset given.
178 /// The offset is guaranteed to be in bounds of the slice in question, and
179 /// the byte at the specified offset was the first invalid byte in the
180 /// sequence detected.
183 /// The byte slice was invalid because more bytes were needed but no more
184 /// bytes were available.
188 /// Converts a slice of bytes to a string slice without performing any
191 /// Once the slice has been validated as utf-8, it is transmuted in-place and
192 /// returned as a '&str' instead of a '&[u8]'
196 /// Returns `Err` if the slice is not utf-8 with a description as to why the
197 /// provided slice is not utf-8.
198 #[stable(feature = "rust1", since = "1.0.0")]
199 pub fn from_utf8(v
: &[u8]) -> Result
<&str, Utf8Error
> {
200 try
!(run_utf8_validation_iterator(&mut v
.iter()));
201 Ok(unsafe { from_utf8_unchecked(v) }
)
204 /// Converts a slice of bytes to a string slice without checking
205 /// that the string contains valid UTF-8.
206 #[stable(feature = "rust1", since = "1.0.0")]
207 pub unsafe fn from_utf8_unchecked
<'a
>(v
: &'a
[u8]) -> &'a
str {
211 /// Constructs a static string slice from a given raw pointer.
213 /// This function will read memory starting at `s` until it finds a 0, and then
214 /// transmute the memory up to that point as a string slice, returning the
215 /// corresponding `&'static str` value.
217 /// This function is unsafe because the caller must ensure the C string itself
218 /// has the static lifetime and that the memory `s` is valid up to and including
219 /// the first null byte.
223 /// This function will panic if the string pointed to by `s` is not valid UTF-8.
224 #[unstable(feature = "core")]
225 #[deprecated(since = "1.0.0",
226 reason
= "use std::ffi::c_str_to_bytes + str::from_utf8")]
227 pub unsafe fn from_c_str(s
: *const i8) -> &'
static str {
228 let s
= s
as *const u8;
230 while *s
.offset(len
as isize) != 0 {
233 let v
: &'
static [u8] = ::mem
::transmute(Slice { data: s, len: len }
);
234 from_utf8(v
).ok().expect("from_c_str passed invalid utf-8 data")
237 /// Something that can be used to compare against a character
238 #[unstable(feature = "core",
239 reason
= "definition may change as pattern-related methods are stabilized")]
241 /// Determine if the splitter should split at the given character
242 fn matches(&mut self, char) -> bool
;
243 /// Indicate if this is only concerned about ASCII characters,
244 /// which can allow for a faster implementation.
245 fn only_ascii(&self) -> bool
;
248 impl CharEq
for char {
250 fn matches(&mut self, c
: char) -> bool { *self == c }
253 fn only_ascii(&self) -> bool { (*self as u32) < 128 }
256 impl<F
> CharEq
for F
where F
: FnMut(char) -> bool
{
258 fn matches(&mut self, c
: char) -> bool { (*self)(c) }
261 fn only_ascii(&self) -> bool { false }
264 impl<'a
> CharEq
for &'a
[char] {
266 fn matches(&mut self, c
: char) -> bool
{
267 self.iter().any(|&m
| { let mut m = m; m.matches(c) }
)
271 fn only_ascii(&self) -> bool
{
272 self.iter().all(|m
| m
.only_ascii())
276 #[stable(feature = "rust1", since = "1.0.0")]
277 impl Error
for Utf8Error
{
278 fn description(&self) -> &str {
280 Utf8Error
::TooShort
=> "invalid utf-8: not enough bytes",
281 Utf8Error
::InvalidByte(..) => "invalid utf-8: corrupt contents",
286 #[stable(feature = "rust1", since = "1.0.0")]
287 impl fmt
::Display
for Utf8Error
{
288 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
290 Utf8Error
::InvalidByte(n
) => {
291 write
!(f
, "invalid utf-8: invalid byte at index {}", n
)
293 Utf8Error
::TooShort
=> {
294 write
!(f
, "invalid utf-8: byte slice too short")
304 /// Iterator for the char (representing *Unicode Scalar Values*) of a string
306 /// Created with the method `.chars()`.
308 #[stable(feature = "rust1", since = "1.0.0")]
309 pub struct Chars
<'a
> {
310 iter
: slice
::Iter
<'a
, u8>
313 // Return the initial codepoint accumulator for the first byte.
314 // The first byte is special, only want bottom 5 bits for width 2, 4 bits
315 // for width 3, and 3 bits for width 4
316 macro_rules
! utf8_first_byte
{
317 ($byte
:expr
, $width
:expr
) => (($byte
& (0x7F >> $width
)) as u32)
320 // return the value of $ch updated with continuation byte $byte
321 macro_rules
! utf8_acc_cont_byte
{
322 ($ch
:expr
, $byte
:expr
) => (($ch
<< 6) | ($byte
& CONT_MASK
) as u32)
325 macro_rules
! utf8_is_cont_byte
{
326 ($byte
:expr
) => (($byte
& !CONT_MASK
) == TAG_CONT_U8
)
330 fn unwrap_or_0(opt
: Option
<&u8>) -> u8 {
337 /// Reads the next code point out of a byte iterator (assuming a
338 /// UTF-8-like encoding).
339 #[unstable(feature = "core")]
340 pub fn next_code_point(bytes
: &mut slice
::Iter
<u8>) -> Option
<u32> {
342 let x
= match bytes
.next() {
344 Some(&next_byte
) if next_byte
< 128 => return Some(next_byte
as u32),
345 Some(&next_byte
) => next_byte
,
348 // Multibyte case follows
349 // Decode from a byte combination out of: [[[x y] z] w]
350 // NOTE: Performance is sensitive to the exact formulation here
351 let init
= utf8_first_byte
!(x
, 2);
352 let y
= unwrap_or_0(bytes
.next());
353 let mut ch
= utf8_acc_cont_byte
!(init
, y
);
356 // 5th bit in 0xE0 .. 0xEF is always clear, so `init` is still valid
357 let z
= unwrap_or_0(bytes
.next());
358 let y_z
= utf8_acc_cont_byte
!((y
& CONT_MASK
) as u32, z
);
359 ch
= init
<< 12 | y_z
;
362 // use only the lower 3 bits of `init`
363 let w
= unwrap_or_0(bytes
.next());
364 ch
= (init
& 7) << 18 | utf8_acc_cont_byte
!(y_z
, w
);
371 #[stable(feature = "rust1", since = "1.0.0")]
372 impl<'a
> Iterator
for Chars
<'a
> {
376 fn next(&mut self) -> Option
<char> {
377 next_code_point(&mut self.iter
).map(|ch
| {
378 // str invariant says `ch` is a valid Unicode Scalar Value
386 fn size_hint(&self) -> (usize, Option
<usize>) {
387 let (len
, _
) = self.iter
.size_hint();
388 (len
.saturating_add(3) / 4, Some(len
))
392 #[stable(feature = "rust1", since = "1.0.0")]
393 impl<'a
> DoubleEndedIterator
for Chars
<'a
> {
395 fn next_back(&mut self) -> Option
<char> {
396 let w
= match self.iter
.next_back() {
398 Some(&back_byte
) if back_byte
< 128 => return Some(back_byte
as char),
399 Some(&back_byte
) => back_byte
,
402 // Multibyte case follows
403 // Decode from a byte combination out of: [x [y [z w]]]
405 let z
= unwrap_or_0(self.iter
.next_back());
406 ch
= utf8_first_byte
!(z
, 2);
407 if utf8_is_cont_byte
!(z
) {
408 let y
= unwrap_or_0(self.iter
.next_back());
409 ch
= utf8_first_byte
!(y
, 3);
410 if utf8_is_cont_byte
!(y
) {
411 let x
= unwrap_or_0(self.iter
.next_back());
412 ch
= utf8_first_byte
!(x
, 4);
413 ch
= utf8_acc_cont_byte
!(ch
, y
);
415 ch
= utf8_acc_cont_byte
!(ch
, z
);
417 ch
= utf8_acc_cont_byte
!(ch
, w
);
419 // str invariant says `ch` is a valid Unicode Scalar Value
421 Some(mem
::transmute(ch
))
426 /// External iterator for a string's characters and their byte offsets.
427 /// Use with the `std::iter` module.
429 #[stable(feature = "rust1", since = "1.0.0")]
430 pub struct CharIndices
<'a
> {
435 #[stable(feature = "rust1", since = "1.0.0")]
436 impl<'a
> Iterator
for CharIndices
<'a
> {
437 type Item
= (usize, char);
440 fn next(&mut self) -> Option
<(usize, char)> {
441 let (pre_len
, _
) = self.iter
.iter
.size_hint();
442 match self.iter
.next() {
445 let index
= self.front_offset
;
446 let (len
, _
) = self.iter
.iter
.size_hint();
447 self.front_offset
+= pre_len
- len
;
454 fn size_hint(&self) -> (usize, Option
<usize>) {
455 self.iter
.size_hint()
459 #[stable(feature = "rust1", since = "1.0.0")]
460 impl<'a
> DoubleEndedIterator
for CharIndices
<'a
> {
462 fn next_back(&mut self) -> Option
<(usize, char)> {
463 match self.iter
.next_back() {
466 let (len
, _
) = self.iter
.iter
.size_hint();
467 let index
= self.front_offset
+ len
;
474 /// External iterator for a string's bytes.
475 /// Use with the `std::iter` module.
477 /// Created with `StrExt::bytes`
478 #[stable(feature = "rust1", since = "1.0.0")]
480 pub struct Bytes
<'a
>(Map
<slice
::Iter
<'a
, u8>, BytesDeref
>);
481 delegate_iter
!{exact u8 : Bytes<'a>}
483 /// A temporary fn new type that ensures that the `Bytes` iterator
485 #[derive(Copy, Clone)]
488 impl<'a
> Fn
<(&'a
u8,)> for BytesDeref
{
492 extern "rust-call" fn call(&self, (ptr
,): (&'a
u8,)) -> u8 {
497 /// An iterator over the substrings of a string, separated by `sep`.
499 struct CharSplits
<'a
, Sep
> {
500 /// The slice remaining to be iterated
503 /// Whether an empty string at the end is allowed
504 allow_trailing_empty
: bool
,
509 /// An iterator over the substrings of a string, separated by `sep`,
510 /// splitting at most `count` times.
512 struct CharSplitsN
<'a
, Sep
> {
513 iter
: CharSplits
<'a
, Sep
>,
514 /// The number of splits remaining
519 /// An iterator over the lines of a string, separated by `\n`.
520 #[stable(feature = "rust1", since = "1.0.0")]
521 pub struct Lines
<'a
> {
522 inner
: CharSplits
<'a
, char>,
525 /// An iterator over the lines of a string, separated by either `\n` or (`\r\n`).
526 #[stable(feature = "rust1", since = "1.0.0")]
527 pub struct LinesAny
<'a
> {
528 inner
: Map
<Lines
<'a
>, fn(&str) -> &str>,
531 impl<'a
, Sep
> CharSplits
<'a
, Sep
> {
533 fn get_end(&mut self) -> Option
<&'a
str> {
534 if !self.finished
&& (self.allow_trailing_empty
|| self.string
.len() > 0) {
535 self.finished
= true;
543 #[stable(feature = "rust1", since = "1.0.0")]
544 impl<'a
, Sep
: CharEq
> Iterator
for CharSplits
<'a
, Sep
> {
548 fn next(&mut self) -> Option
<&'a
str> {
549 if self.finished { return None }
551 let mut next_split
= None
;
553 for (idx
, byte
) in self.string
.bytes().enumerate() {
554 if self.sep
.matches(byte
as char) && byte
< 128u8 {
555 next_split
= Some((idx
, idx
+ 1));
560 for (idx
, ch
) in self.string
.char_indices() {
561 if self.sep
.matches(ch
) {
562 next_split
= Some((idx
, self.string
.char_range_at(idx
).next
));
568 Some((a
, b
)) => unsafe {
569 let elt
= self.string
.slice_unchecked(0, a
);
570 self.string
= self.string
.slice_unchecked(b
, self.string
.len());
573 None
=> self.get_end(),
578 #[stable(feature = "rust1", since = "1.0.0")]
579 impl<'a
, Sep
: CharEq
> DoubleEndedIterator
for CharSplits
<'a
, Sep
> {
581 fn next_back(&mut self) -> Option
<&'a
str> {
582 if self.finished { return None }
584 if !self.allow_trailing_empty
{
585 self.allow_trailing_empty
= true;
586 match self.next_back() {
587 Some(elt
) if !elt
.is_empty() => return Some(elt
),
588 _
=> if self.finished { return None }
591 let len
= self.string
.len();
592 let mut next_split
= None
;
595 for (idx
, byte
) in self.string
.bytes().enumerate().rev() {
596 if self.sep
.matches(byte
as char) && byte
< 128u8 {
597 next_split
= Some((idx
, idx
+ 1));
602 for (idx
, ch
) in self.string
.char_indices().rev() {
603 if self.sep
.matches(ch
) {
604 next_split
= Some((idx
, self.string
.char_range_at(idx
).next
));
610 Some((a
, b
)) => unsafe {
611 let elt
= self.string
.slice_unchecked(b
, len
);
612 self.string
= self.string
.slice_unchecked(0, a
);
615 None
=> { self.finished = true; Some(self.string) }
620 #[stable(feature = "rust1", since = "1.0.0")]
621 impl<'a
, Sep
: CharEq
> Iterator
for CharSplitsN
<'a
, Sep
> {
625 fn next(&mut self) -> Option
<&'a
str> {
628 if self.invert { self.iter.next_back() }
else { self.iter.next() }
635 /// The internal state of an iterator that searches for matches of a substring
636 /// within a larger string using naive search
638 struct NaiveSearcher
{
643 fn new() -> NaiveSearcher
{
644 NaiveSearcher { position: 0 }
647 fn next(&mut self, haystack
: &[u8], needle
: &[u8]) -> Option
<(usize, usize)> {
648 while self.position
+ needle
.len() <= haystack
.len() {
649 if &haystack
[self.position
.. self.position
+ needle
.len()] == needle
{
650 let match_pos
= self.position
;
651 self.position
+= needle
.len(); // add 1 for all matches
652 return Some((match_pos
, match_pos
+ needle
.len()));
661 /// The internal state of an iterator that searches for matches of a substring
662 /// within a larger string using two-way search
664 struct TwoWaySearcher
{
676 This is the Two-Way search algorithm, which was introduced in the paper:
677 Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675.
679 Here's some background information.
681 A *word* is a string of symbols. The *length* of a word should be a familiar
682 notion, and here we denote it for any word x by |x|.
683 (We also allow for the possibility of the *empty word*, a word of length zero).
685 If x is any non-empty word, then an integer p with 0 < p <= |x| is said to be a
686 *period* for x iff for all i with 0 <= i <= |x| - p - 1, we have x[i] == x[i+p].
687 For example, both 1 and 2 are periods for the string "aa". As another example,
688 the only period of the string "abcd" is 4.
690 We denote by period(x) the *smallest* period of x (provided that x is non-empty).
691 This is always well-defined since every non-empty word x has at least one period,
692 |x|. We sometimes call this *the period* of x.
694 If u, v and x are words such that x = uv, where uv is the concatenation of u and
695 v, then we say that (u, v) is a *factorization* of x.
697 Let (u, v) be a factorization for a word x. Then if w is a non-empty word such
698 that both of the following hold
700 - either w is a suffix of u or u is a suffix of w
701 - either w is a prefix of v or v is a prefix of w
703 then w is said to be a *repetition* for the factorization (u, v).
705 Just to unpack this, there are four possibilities here. Let w = "abc". Then we
708 - w is a suffix of u and w is a prefix of v. ex: ("lolabc", "abcde")
709 - w is a suffix of u and v is a prefix of w. ex: ("lolabc", "ab")
710 - u is a suffix of w and w is a prefix of v. ex: ("bc", "abchi")
711 - u is a suffix of w and v is a prefix of w. ex: ("bc", "a")
713 Note that the word vu is a repetition for any factorization (u,v) of x = uv,
714 so every factorization has at least one repetition.
716 If x is a string and (u, v) is a factorization for x, then a *local period* for
717 (u, v) is an integer r such that there is some word w such that |w| = r and w is
718 a repetition for (u, v).
720 We denote by local_period(u, v) the smallest local period of (u, v). We sometimes
721 call this *the local period* of (u, v). Provided that x = uv is non-empty, this
722 is well-defined (because each non-empty word has at least one factorization, as
725 It can be proven that the following is an equivalent definition of a local period
726 for a factorization (u, v): any positive integer r such that x[i] == x[i+r] for
727 all i such that |u| - r <= i <= |u| - 1 and such that both x[i] and x[i+r] are
728 defined. (i.e. i > 0 and i + r < |x|).
730 Using the above reformulation, it is easy to prove that
732 1 <= local_period(u, v) <= period(uv)
734 A factorization (u, v) of x such that local_period(u,v) = period(x) is called a
735 *critical factorization*.
737 The algorithm hinges on the following theorem, which is stated without proof:
739 **Critical Factorization Theorem** Any word x has at least one critical
740 factorization (u, v) such that |u| < period(x).
742 The purpose of maximal_suffix is to find such a critical factorization.
745 impl TwoWaySearcher
{
746 fn new(needle
: &[u8]) -> TwoWaySearcher
{
747 let (crit_pos_false
, period_false
) = TwoWaySearcher
::maximal_suffix(needle
, false);
748 let (crit_pos_true
, period_true
) = TwoWaySearcher
::maximal_suffix(needle
, true);
750 let (crit_pos
, period
) =
751 if crit_pos_false
> crit_pos_true
{
752 (crit_pos_false
, period_false
)
754 (crit_pos_true
, period_true
)
757 // This isn't in the original algorithm, as far as I'm aware.
758 let byteset
= needle
.iter()
759 .fold(0, |a
, &b
| (1 << ((b
& 0x3f) as usize)) | a
);
761 // A particularly readable explanation of what's going on here can be found
762 // in Crochemore and Rytter's book "Text Algorithms", ch 13. Specifically
763 // see the code for "Algorithm CP" on p. 323.
765 // What's going on is we have some critical factorization (u, v) of the
766 // needle, and we want to determine whether u is a suffix of
767 // &v[..period]. If it is, we use "Algorithm CP1". Otherwise we use
768 // "Algorithm CP2", which is optimized for when the period of the needle
770 if &needle
[..crit_pos
] == &needle
[period
.. period
+ crit_pos
] {
782 period
: cmp
::max(crit_pos
, needle
.len() - crit_pos
) + 1,
786 memory
: usize::MAX
// Dummy value to signify that the period is long
791 // One of the main ideas of Two-Way is that we factorize the needle into
792 // two halves, (u, v), and begin trying to find v in the haystack by scanning
793 // left to right. If v matches, we try to match u by scanning right to left.
794 // How far we can jump when we encounter a mismatch is all based on the fact
795 // that (u, v) is a critical factorization for the needle.
797 fn next(&mut self, haystack
: &[u8], needle
: &[u8], long_period
: bool
)
798 -> Option
<(usize, usize)> {
800 // Check that we have room to search in
801 if self.position
+ needle
.len() > haystack
.len() {
805 // Quickly skip by large portions unrelated to our substring
807 ((haystack
[self.position
+ needle
.len() - 1] & 0x3f)
808 as usize)) & 1 == 0 {
809 self.position
+= needle
.len();
816 // See if the right part of the needle matches
817 let start
= if long_period { self.crit_pos }
818 else { cmp::max(self.crit_pos, self.memory) }
;
819 for i
in start
..needle
.len() {
820 if needle
[i
] != haystack
[self.position
+ i
] {
821 self.position
+= i
- self.crit_pos
+ 1;
829 // See if the left part of the needle matches
830 let start
= if long_period { 0 }
else { self.memory }
;
831 for i
in (start
..self.crit_pos
).rev() {
832 if needle
[i
] != haystack
[self.position
+ i
] {
833 self.position
+= self.period
;
835 self.memory
= needle
.len() - self.period
;
841 // We have found a match!
842 let match_pos
= self.position
;
843 self.position
+= needle
.len(); // add self.period for all matches
845 self.memory
= 0; // set to needle.len() - self.period for all matches
847 return Some((match_pos
, match_pos
+ needle
.len()));
851 // Computes a critical factorization (u, v) of `arr`.
852 // Specifically, returns (i, p), where i is the starting index of v in some
853 // critical factorization (u, v) and p = period(v)
855 fn maximal_suffix(arr
: &[u8], reversed
: bool
) -> (usize, usize) {
856 let mut left
= -1; // Corresponds to i in the paper
857 let mut right
= 0; // Corresponds to j in the paper
858 let mut offset
= 1; // Corresponds to k in the paper
859 let mut period
= 1; // Corresponds to p in the paper
861 while right
+ offset
< arr
.len() {
865 a
= arr
[left
+ offset
];
866 b
= arr
[right
+ offset
];
868 a
= arr
[right
+ offset
];
869 b
= arr
[left
+ offset
];
872 // Suffix is smaller, period is entire prefix so far.
875 period
= right
- left
;
877 // Advance through repetition of the current period.
878 if offset
== period
{
885 // Suffix is larger, start over from current location.
896 /// The internal state of an iterator that searches for matches of a substring
897 /// within a larger string using a dynamically chosen search algorithm
900 Naive(NaiveSearcher
),
901 TwoWay(TwoWaySearcher
),
902 TwoWayLong(TwoWaySearcher
)
906 fn new(haystack
: &[u8], needle
: &[u8]) -> Searcher
{
908 // FIXME(#16715): This unsigned integer addition will probably not
909 // overflow because that would mean that the memory almost solely
910 // consists of the needle. Needs #16715 to be formally fixed.
911 if needle
.len() + 20 > haystack
.len() {
912 Naive(NaiveSearcher
::new())
914 let searcher
= TwoWaySearcher
::new(needle
);
915 if searcher
.memory
== usize::MAX
{ // If the period is long
924 /// An iterator over the start and end indices of the matches of a
925 /// substring within a larger string
927 #[unstable(feature = "core", reason = "type may be removed")]
928 pub struct MatchIndices
<'a
> {
935 /// An iterator over the substrings of a string separated by a given
938 #[unstable(feature = "core", reason = "type may be removed")]
939 pub struct SplitStr
<'a
> {
940 it
: MatchIndices
<'a
>,
945 #[stable(feature = "rust1", since = "1.0.0")]
946 impl<'a
> Iterator
for MatchIndices
<'a
> {
947 type Item
= (usize, usize);
950 fn next(&mut self) -> Option
<(usize, usize)> {
951 match self.searcher
{
952 Naive(ref mut searcher
)
953 => searcher
.next(self.haystack
.as_bytes(), self.needle
.as_bytes()),
954 TwoWay(ref mut searcher
)
955 => searcher
.next(self.haystack
.as_bytes(), self.needle
.as_bytes(), false),
956 TwoWayLong(ref mut searcher
)
957 => searcher
.next(self.haystack
.as_bytes(), self.needle
.as_bytes(), true)
962 #[stable(feature = "rust1", since = "1.0.0")]
963 impl<'a
> Iterator
for SplitStr
<'a
> {
967 fn next(&mut self) -> Option
<&'a
str> {
968 if self.finished { return None; }
970 match self.it
.next() {
971 Some((from
, to
)) => {
972 let ret
= Some(&self.it
.haystack
[self.last_end
.. from
]);
977 self.finished
= true;
978 Some(&self.it
.haystack
[self.last_end
.. self.it
.haystack
.len()])
986 Section: Comparing strings
989 // share the implementation of the lang-item vs. non-lang-item
991 /// NOTE: This function is (ab)used in rustc::middle::trans::_match
992 /// to compare &[u8] byte slices that are not necessarily valid UTF-8.
994 fn eq_slice_(a
: &str, b
: &str) -> bool
{
995 // NOTE: In theory n should be libc::size_t and not usize, but libc is not available here
996 #[allow(improper_ctypes)]
997 extern { fn memcmp(s1: *const i8, s2: *const i8, n: usize) -> i32; }
998 a
.len() == b
.len() && unsafe {
999 memcmp(a
.as_ptr() as *const i8,
1000 b
.as_ptr() as *const i8,
1005 /// Bytewise slice equality
1006 /// NOTE: This function is (ab)used in rustc::middle::trans::_match
1007 /// to compare &[u8] byte slices that are not necessarily valid UTF-8.
1010 fn eq_slice(a
: &str, b
: &str) -> bool
{
1018 /// Walk through `iter` checking that it's a valid UTF-8 sequence,
1019 /// returning `true` in that case, or, if it is invalid, `false` with
1020 /// `iter` reset such that it is pointing at the first byte in the
1021 /// invalid sequence.
1023 fn run_utf8_validation_iterator(iter
: &mut slice
::Iter
<u8>)
1024 -> Result
<(), Utf8Error
> {
1025 let whole
= iter
.as_slice();
1027 // save the current thing we're pointing at.
1028 let old
= iter
.clone();
1030 // restore the iterator we had at the start of this codepoint.
1031 macro_rules
! err
{ () => {{
1032 *iter
= old
.clone();
1033 return Err(Utf8Error
::InvalidByte(whole
.len() - iter
.as_slice().len()))
1036 macro_rules
! next
{ () => {
1039 // we needed data, but there was none: error!
1040 None
=> return Err(Utf8Error
::TooShort
),
1044 let first
= match iter
.next() {
1046 // we're at the end of the iterator and a codepoint
1047 // boundary at the same time, so this string is valid.
1048 None
=> return Ok(())
1051 // ASCII characters are always valid, so only large
1052 // bytes need more examination.
1054 let w
= UTF8_CHAR_WIDTH
[first
as usize] as usize;
1055 let second
= next
!();
1056 // 2-byte encoding is for codepoints \u{0080} to \u{07ff}
1057 // first C2 80 last DF BF
1058 // 3-byte encoding is for codepoints \u{0800} to \u{ffff}
1059 // first E0 A0 80 last EF BF BF
1060 // excluding surrogates codepoints \u{d800} to \u{dfff}
1061 // ED A0 80 to ED BF BF
1062 // 4-byte encoding is for codepoints \u{1000}0 to \u{10ff}ff
1063 // first F0 90 80 80 last F4 8F BF BF
1065 // Use the UTF-8 syntax from the RFC
1067 // https://tools.ietf.org/html/rfc3629
1069 // UTF8-2 = %xC2-DF UTF8-tail
1070 // UTF8-3 = %xE0 %xA0-BF UTF8-tail / %xE1-EC 2( UTF8-tail ) /
1071 // %xED %x80-9F UTF8-tail / %xEE-EF 2( UTF8-tail )
1072 // UTF8-4 = %xF0 %x90-BF 2( UTF8-tail ) / %xF1-F3 3( UTF8-tail ) /
1073 // %xF4 %x80-8F 2( UTF8-tail )
1075 2 => if second
& !CONT_MASK
!= TAG_CONT_U8 {err!()}
,
1077 match (first
, second
, next
!() & !CONT_MASK
) {
1078 (0xE0 , 0xA0 ... 0xBF, TAG_CONT_U8
) |
1079 (0xE1 ... 0xEC, 0x80 ... 0xBF, TAG_CONT_U8
) |
1080 (0xED , 0x80 ... 0x9F, TAG_CONT_U8
) |
1081 (0xEE ... 0xEF, 0x80 ... 0xBF, TAG_CONT_U8
) => {}
1086 match (first
, second
, next
!() & !CONT_MASK
, next
!() & !CONT_MASK
) {
1087 (0xF0 , 0x90 ... 0xBF, TAG_CONT_U8
, TAG_CONT_U8
) |
1088 (0xF1 ... 0xF3, 0x80 ... 0xBF, TAG_CONT_U8
, TAG_CONT_U8
) |
1089 (0xF4 , 0x80 ... 0x8F, TAG_CONT_U8
, TAG_CONT_U8
) => {}
1099 // https://tools.ietf.org/html/rfc3629
1100 static UTF8_CHAR_WIDTH
: [u8; 256] = [
1101 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1102 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x1F
1103 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1104 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x3F
1105 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1106 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x5F
1107 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1108 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x7F
1109 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1110 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0x9F
1111 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1112 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0xBF
1113 0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
1114 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, // 0xDF
1115 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3, // 0xEF
1116 4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0, // 0xFF
1119 /// Struct that contains a `char` and the index of the first byte of
1120 /// the next `char` in a string. This can be used as a data structure
1121 /// for iterating over the UTF-8 bytes of a string.
1123 #[unstable(feature = "core",
1124 reason
= "naming is uncertain with container conventions")]
1125 pub struct CharRange
{
1128 /// Index of the first byte of the next `char`
1132 /// Mask of the value bits of a continuation byte
1133 const CONT_MASK
: u8 = 0b0011_1111u8;
1134 /// Value of the tag bits (tag mask is !CONT_MASK) of a continuation byte
1135 const TAG_CONT_U8
: u8 = 0b1000_0000u8;
1138 Section: Trait implementations
1142 use cmp
::{Ordering, Ord, PartialEq, PartialOrd, Eq}
;
1143 use cmp
::Ordering
::{Less, Equal, Greater}
;
1144 use iter
::IteratorExt
;
1146 use option
::Option
::Some
;
1148 use str::{StrExt, eq_slice}
;
1150 #[stable(feature = "rust1", since = "1.0.0")]
1153 fn cmp(&self, other
: &str) -> Ordering
{
1154 for (s_b
, o_b
) in self.bytes().zip(other
.bytes()) {
1155 match s_b
.cmp(&o_b
) {
1156 Greater
=> return Greater
,
1157 Less
=> return Less
,
1162 self.len().cmp(&other
.len())
1166 #[stable(feature = "rust1", since = "1.0.0")]
1167 impl PartialEq
for str {
1169 fn eq(&self, other
: &str) -> bool
{
1170 eq_slice(self, other
)
1173 fn ne(&self, other
: &str) -> bool { !(*self).eq(other) }
1176 #[stable(feature = "rust1", since = "1.0.0")]
1179 #[stable(feature = "rust1", since = "1.0.0")]
1180 impl PartialOrd
for str {
1182 fn partial_cmp(&self, other
: &str) -> Option
<Ordering
> {
1183 Some(self.cmp(other
))
1187 /// Returns a slice of the given string from the byte range
1188 /// [`begin`..`end`).
1190 /// This operation is `O(1)`.
1192 /// Panics when `begin` and `end` do not point to valid characters
1193 /// or point beyond the last character of the string.
1198 /// let s = "Löwe 老虎 Léopard";
1199 /// assert_eq!(&s[0 .. 1], "L");
1201 /// assert_eq!(&s[1 .. 9], "öwe 老");
1203 /// // these will panic:
1204 /// // byte 2 lies within `ö`:
1207 /// // byte 8 lies within `老`
1210 /// // byte 100 is outside the string
1211 /// // &s[3 .. 100];
1213 #[stable(feature = "rust1", since = "1.0.0")]
1214 impl ops
::Index
<ops
::Range
<usize>> for str {
1217 fn index(&self, index
: &ops
::Range
<usize>) -> &str {
1218 // is_char_boundary checks that the index is in [0, .len()]
1219 if index
.start
<= index
.end
&&
1220 self.is_char_boundary(index
.start
) &&
1221 self.is_char_boundary(index
.end
) {
1222 unsafe { self.slice_unchecked(index.start, index.end) }
1224 super::slice_error_fail(self, index
.start
, index
.end
)
1229 /// Returns a slice of the string from the beginning to byte
1232 /// Equivalent to `self[0 .. end]`.
1234 /// Panics when `end` does not point to a valid character, or is
1236 #[stable(feature = "rust1", since = "1.0.0")]
1237 impl ops
::Index
<ops
::RangeTo
<usize>> for str {
1240 fn index(&self, index
: &ops
::RangeTo
<usize>) -> &str {
1241 // is_char_boundary checks that the index is in [0, .len()]
1242 if self.is_char_boundary(index
.end
) {
1243 unsafe { self.slice_unchecked(0, index.end) }
1245 super::slice_error_fail(self, 0, index
.end
)
1250 /// Returns a slice of the string from `begin` to its end.
1252 /// Equivalent to `self[begin .. self.len()]`.
1254 /// Panics when `begin` does not point to a valid character, or is
1256 #[stable(feature = "rust1", since = "1.0.0")]
1257 impl ops
::Index
<ops
::RangeFrom
<usize>> for str {
1260 fn index(&self, index
: &ops
::RangeFrom
<usize>) -> &str {
1261 // is_char_boundary checks that the index is in [0, .len()]
1262 if self.is_char_boundary(index
.start
) {
1263 unsafe { self.slice_unchecked(index.start, self.len()) }
1265 super::slice_error_fail(self, index
.start
, self.len())
1270 #[stable(feature = "rust1", since = "1.0.0")]
1271 impl ops
::Index
<ops
::RangeFull
> for str {
1274 fn index(&self, _index
: &ops
::RangeFull
) -> &str {
1280 /// Any string that can be represented as a slice
1281 #[unstable(feature = "core",
1282 reason
= "Instead of taking this bound generically, this trait will be \
1283 replaced with one of slicing syntax (&foo[..]), deref coercions, or \
1284 a more generic conversion trait")]
1286 /// Work with `self` as a slice.
1287 fn as_slice
<'a
>(&'a
self) -> &'a
str;
1292 fn as_slice
<'a
>(&'a
self) -> &'a
str { self }
1295 impl<'a
, S
: ?Sized
> Str
for &'a S
where S
: Str
{
1297 fn as_slice(&self) -> &str { Str::as_slice(*self) }
1300 /// Return type of `StrExt::split`
1302 #[stable(feature = "rust1", since = "1.0.0")]
1303 pub struct Split
<'a
, P
>(CharSplits
<'a
, P
>);
1304 delegate_iter
!{pattern &'a str : Split<'a, P>}
1306 /// Return type of `StrExt::split_terminator`
1308 #[unstable(feature = "core",
1309 reason
= "might get removed in favour of a constructor method on Split")]
1310 pub struct SplitTerminator
<'a
, P
>(CharSplits
<'a
, P
>);
1311 delegate_iter
!{pattern &'a str : SplitTerminator<'a, P>}
1313 /// Return type of `StrExt::splitn`
1315 #[stable(feature = "rust1", since = "1.0.0")]
1316 pub struct SplitN
<'a
, P
>(CharSplitsN
<'a
, P
>);
1317 delegate_iter
!{pattern forward &'a str : SplitN<'a, P>}
1319 /// Return type of `StrExt::rsplitn`
1321 #[stable(feature = "rust1", since = "1.0.0")]
1322 pub struct RSplitN
<'a
, P
>(CharSplitsN
<'a
, P
>);
1323 delegate_iter
!{pattern forward &'a str : RSplitN<'a, P>}
1325 /// Methods for string slices
1326 #[allow(missing_docs)]
1328 // NB there are no docs here are they're all located on the StrExt trait in
1329 // libcollections, not here.
1331 fn contains(&self, pat
: &str) -> bool
;
1332 fn contains_char
<P
: CharEq
>(&self, pat
: P
) -> bool
;
1333 fn chars
<'a
>(&'a
self) -> Chars
<'a
>;
1334 fn bytes
<'a
>(&'a
self) -> Bytes
<'a
>;
1335 fn char_indices
<'a
>(&'a
self) -> CharIndices
<'a
>;
1336 fn split
<'a
, P
: CharEq
>(&'a
self, pat
: P
) -> Split
<'a
, P
>;
1337 fn splitn
<'a
, P
: CharEq
>(&'a
self, count
: usize, pat
: P
) -> SplitN
<'a
, P
>;
1338 fn split_terminator
<'a
, P
: CharEq
>(&'a
self, pat
: P
) -> SplitTerminator
<'a
, P
>;
1339 fn rsplitn
<'a
, P
: CharEq
>(&'a
self, count
: usize, pat
: P
) -> RSplitN
<'a
, P
>;
1340 fn match_indices
<'a
>(&'a
self, sep
: &'a
str) -> MatchIndices
<'a
>;
1341 fn split_str
<'a
>(&'a
self, pat
: &'a
str) -> SplitStr
<'a
>;
1342 fn lines
<'a
>(&'a
self) -> Lines
<'a
>;
1343 fn lines_any
<'a
>(&'a
self) -> LinesAny
<'a
>;
1344 fn char_len(&self) -> usize;
1345 fn slice_chars
<'a
>(&'a
self, begin
: usize, end
: usize) -> &'a
str;
1346 unsafe fn slice_unchecked
<'a
>(&'a
self, begin
: usize, end
: usize) -> &'a
str;
1347 fn starts_with(&self, pat
: &str) -> bool
;
1348 fn ends_with(&self, pat
: &str) -> bool
;
1349 fn trim_matches
<'a
, P
: CharEq
>(&'a
self, pat
: P
) -> &'a
str;
1350 fn trim_left_matches
<'a
, P
: CharEq
>(&'a
self, pat
: P
) -> &'a
str;
1351 fn trim_right_matches
<'a
, P
: CharEq
>(&'a
self, pat
: P
) -> &'a
str;
1352 fn is_char_boundary(&self, index
: usize) -> bool
;
1353 fn char_range_at(&self, start
: usize) -> CharRange
;
1354 fn char_range_at_reverse(&self, start
: usize) -> CharRange
;
1355 fn char_at(&self, i
: usize) -> char;
1356 fn char_at_reverse(&self, i
: usize) -> char;
1357 fn as_bytes
<'a
>(&'a
self) -> &'a
[u8];
1358 fn find
<P
: CharEq
>(&self, pat
: P
) -> Option
<usize>;
1359 fn rfind
<P
: CharEq
>(&self, pat
: P
) -> Option
<usize>;
1360 fn find_str(&self, pat
: &str) -> Option
<usize>;
1361 fn slice_shift_char
<'a
>(&'a
self) -> Option
<(char, &'a
str)>;
1362 fn subslice_offset(&self, inner
: &str) -> usize;
1363 fn as_ptr(&self) -> *const u8;
1364 fn len(&self) -> usize;
1365 fn is_empty(&self) -> bool
;
1366 fn parse
<T
: FromStr
>(&self) -> Result
<T
, T
::Err
>;
1370 fn slice_error_fail(s
: &str, begin
: usize, end
: usize) -> ! {
1371 assert
!(begin
<= end
);
1372 panic
!("index {} and/or {} in `{}` do not lie on character boundary",
1376 impl StrExt
for str {
1378 fn contains(&self, needle
: &str) -> bool
{
1379 self.find_str(needle
).is_some()
1383 fn contains_char
<P
: CharEq
>(&self, pat
: P
) -> bool
{
1384 self.find(pat
).is_some()
1388 fn chars(&self) -> Chars
{
1389 Chars{iter: self.as_bytes().iter()}
1393 fn bytes(&self) -> Bytes
{
1394 Bytes(self.as_bytes().iter().map(BytesDeref
))
1398 fn char_indices(&self) -> CharIndices
{
1399 CharIndices { front_offset: 0, iter: self.chars() }
1403 fn split
<P
: CharEq
>(&self, pat
: P
) -> Split
<P
> {
1406 only_ascii
: pat
.only_ascii(),
1408 allow_trailing_empty
: true,
1414 fn splitn
<P
: CharEq
>(&self, count
: usize, pat
: P
) -> SplitN
<P
> {
1415 SplitN(CharSplitsN
{
1416 iter
: self.split(pat
).0,
1423 fn split_terminator
<P
: CharEq
>(&self, pat
: P
) -> SplitTerminator
<P
> {
1424 SplitTerminator(CharSplits
{
1425 allow_trailing_empty
: false,
1431 fn rsplitn
<P
: CharEq
>(&self, count
: usize, pat
: P
) -> RSplitN
<P
> {
1432 RSplitN(CharSplitsN
{
1433 iter
: self.split(pat
).0,
1440 fn match_indices
<'a
>(&'a
self, sep
: &'a
str) -> MatchIndices
<'a
> {
1441 assert
!(!sep
.is_empty());
1445 searcher
: Searcher
::new(self.as_bytes(), sep
.as_bytes())
1450 fn split_str
<'a
>(&'a
self, sep
: &'a
str) -> SplitStr
<'a
> {
1452 it
: self.match_indices(sep
),
1459 fn lines(&self) -> Lines
{
1460 Lines { inner: self.split_terminator('\n').0 }
1463 fn lines_any(&self) -> LinesAny
{
1464 fn f(line
: &str) -> &str {
1466 if l
> 0 && line
.as_bytes()[l
- 1] == b'
\r' { &line[0 .. l - 1] }
1470 let f
: fn(&str) -> &str = f
; // coerce to fn pointer
1471 LinesAny { inner: self.lines().map(f) }
1475 fn char_len(&self) -> usize { self.chars().count() }
1477 fn slice_chars(&self, begin
: usize, end
: usize) -> &str {
1478 assert
!(begin
<= end
);
1480 let mut begin_byte
= None
;
1481 let mut end_byte
= None
;
1483 // This could be even more efficient by not decoding,
1484 // only finding the char boundaries
1485 for (idx
, _
) in self.char_indices() {
1486 if count
== begin { begin_byte = Some(idx); }
1487 if count
== end { end_byte = Some(idx); break; }
1490 if begin_byte
.is_none() && count
== begin { begin_byte = Some(self.len()) }
1491 if end_byte
.is_none() && count
== end { end_byte = Some(self.len()) }
1493 match (begin_byte
, end_byte
) {
1494 (None
, _
) => panic
!("slice_chars: `begin` is beyond end of string"),
1495 (_
, None
) => panic
!("slice_chars: `end` is beyond end of string"),
1496 (Some(a
), Some(b
)) => unsafe { self.slice_unchecked(a, b) }
1501 unsafe fn slice_unchecked(&self, begin
: usize, end
: usize) -> &str {
1502 mem
::transmute(Slice
{
1503 data
: self.as_ptr().offset(begin
as isize),
1509 fn starts_with(&self, needle
: &str) -> bool
{
1510 let n
= needle
.len();
1511 self.len() >= n
&& needle
.as_bytes() == &self.as_bytes()[..n
]
1515 fn ends_with(&self, needle
: &str) -> bool
{
1516 let (m
, n
) = (self.len(), needle
.len());
1517 m
>= n
&& needle
.as_bytes() == &self.as_bytes()[m
-n
..]
1521 fn trim_matches
<P
: CharEq
>(&self, mut pat
: P
) -> &str {
1522 let cur
= match self.find(|c
: char| !pat
.matches(c
)) {
1524 Some(i
) => unsafe { self.slice_unchecked(i, self.len()) }
1526 match cur
.rfind(|c
: char| !pat
.matches(c
)) {
1529 let right
= cur
.char_range_at(i
).next
;
1530 unsafe { cur.slice_unchecked(0, right) }
1536 fn trim_left_matches
<P
: CharEq
>(&self, mut pat
: P
) -> &str {
1537 match self.find(|c
: char| !pat
.matches(c
)) {
1539 Some(first
) => unsafe { self.slice_unchecked(first, self.len()) }
1544 fn trim_right_matches
<P
: CharEq
>(&self, mut pat
: P
) -> &str {
1545 match self.rfind(|c
: char| !pat
.matches(c
)) {
1548 let next
= self.char_range_at(last
).next
;
1549 unsafe { self.slice_unchecked(0, next) }
1555 fn is_char_boundary(&self, index
: usize) -> bool
{
1556 if index
== self.len() { return true; }
1557 match self.as_bytes().get(index
) {
1559 Some(&b
) => b
< 128u8 || b
>= 192u8,
1564 fn char_range_at(&self, i
: usize) -> CharRange
{
1565 let (c
, n
) = char_range_at_raw(self.as_bytes(), i
);
1566 CharRange { ch: unsafe { mem::transmute(c) }
, next
: n
}
1570 fn char_range_at_reverse(&self, start
: usize) -> CharRange
{
1571 let mut prev
= start
;
1573 prev
= prev
.saturating_sub(1);
1574 if self.as_bytes()[prev
] < 128 {
1575 return CharRange{ch: self.as_bytes()[prev] as char, next: prev}
1578 // Multibyte case is a fn to allow char_range_at_reverse to inline cleanly
1579 fn multibyte_char_range_at_reverse(s
: &str, mut i
: usize) -> CharRange
{
1580 // while there is a previous byte == 10......
1581 while i
> 0 && s
.as_bytes()[i
] & !CONT_MASK
== TAG_CONT_U8
{
1585 let mut val
= s
.as_bytes()[i
] as u32;
1586 let w
= UTF8_CHAR_WIDTH
[val
as usize] as usize;
1589 val
= utf8_first_byte
!(val
, w
);
1590 val
= utf8_acc_cont_byte
!(val
, s
.as_bytes()[i
+ 1]);
1591 if w
> 2 { val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 2]); }
1592 if w
> 3 { val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 3]); }
1594 return CharRange {ch: unsafe { mem::transmute(val) }
, next
: i
};
1597 return multibyte_char_range_at_reverse(self, prev
);
1601 fn char_at(&self, i
: usize) -> char {
1602 self.char_range_at(i
).ch
1606 fn char_at_reverse(&self, i
: usize) -> char {
1607 self.char_range_at_reverse(i
).ch
1611 fn as_bytes(&self) -> &[u8] {
1612 unsafe { mem::transmute(self) }
1615 fn find
<P
: CharEq
>(&self, mut pat
: P
) -> Option
<usize> {
1616 if pat
.only_ascii() {
1617 self.bytes().position(|b
| pat
.matches(b
as char))
1619 for (index
, c
) in self.char_indices() {
1620 if pat
.matches(c
) { return Some(index); }
1626 fn rfind
<P
: CharEq
>(&self, mut pat
: P
) -> Option
<usize> {
1627 if pat
.only_ascii() {
1628 self.bytes().rposition(|b
| pat
.matches(b
as char))
1630 for (index
, c
) in self.char_indices().rev() {
1631 if pat
.matches(c
) { return Some(index); }
1637 fn find_str(&self, needle
: &str) -> Option
<usize> {
1638 if needle
.is_empty() {
1641 self.match_indices(needle
)
1643 .map(|(start
, _end
)| start
)
1648 fn slice_shift_char(&self) -> Option
<(char, &str)> {
1649 if self.is_empty() {
1652 let CharRange {ch, next}
= self.char_range_at(0);
1653 let next_s
= unsafe { self.slice_unchecked(next, self.len()) }
;
1658 fn subslice_offset(&self, inner
: &str) -> usize {
1659 let a_start
= self.as_ptr() as usize;
1660 let a_end
= a_start
+ self.len();
1661 let b_start
= inner
.as_ptr() as usize;
1662 let b_end
= b_start
+ inner
.len();
1664 assert
!(a_start
<= b_start
);
1665 assert
!(b_end
<= a_end
);
1670 fn as_ptr(&self) -> *const u8 {
1675 fn len(&self) -> usize { self.repr().len }
1678 fn is_empty(&self) -> bool { self.len() == 0 }
1681 fn parse
<T
: FromStr
>(&self) -> Result
<T
, T
::Err
> { FromStr::from_str(self) }
1684 /// Pluck a code point out of a UTF-8-like byte slice and return the
1685 /// index of the next code point.
1687 #[unstable(feature = "core")]
1688 pub fn char_range_at_raw(bytes
: &[u8], i
: usize) -> (u32, usize) {
1689 if bytes
[i
] < 128u8 {
1690 return (bytes
[i
] as u32, i
+ 1);
1693 // Multibyte case is a fn to allow char_range_at to inline cleanly
1694 fn multibyte_char_range_at(bytes
: &[u8], i
: usize) -> (u32, usize) {
1695 let mut val
= bytes
[i
] as u32;
1696 let w
= UTF8_CHAR_WIDTH
[val
as usize] as usize;
1699 val
= utf8_first_byte
!(val
, w
);
1700 val
= utf8_acc_cont_byte
!(val
, bytes
[i
+ 1]);
1701 if w
> 2 { val = utf8_acc_cont_byte!(val, bytes[i + 2]); }
1702 if w
> 3 { val = utf8_acc_cont_byte!(val, bytes[i + 3]); }
1704 return (val
, i
+ w
);
1707 multibyte_char_range_at(bytes
, i
)
1710 #[stable(feature = "rust1", since = "1.0.0")]
1711 impl<'a
> Default
for &'a
str {
1712 #[stable(feature = "rust1", since = "1.0.0")]
1713 fn default() -> &'a
str { "" }
1716 #[stable(feature = "rust1", since = "1.0.0")]
1717 impl<'a
> Iterator
for Lines
<'a
> {
1718 type Item
= &'a
str;
1721 fn next(&mut self) -> Option
<&'a
str> { self.inner.next() }
1723 fn size_hint(&self) -> (usize, Option
<usize>) { self.inner.size_hint() }
1726 #[stable(feature = "rust1", since = "1.0.0")]
1727 impl<'a
> DoubleEndedIterator
for Lines
<'a
> {
1729 fn next_back(&mut self) -> Option
<&'a
str> { self.inner.next_back() }
1732 #[stable(feature = "rust1", since = "1.0.0")]
1733 impl<'a
> Iterator
for LinesAny
<'a
> {
1734 type Item
= &'a
str;
1737 fn next(&mut self) -> Option
<&'a
str> { self.inner.next() }
1739 fn size_hint(&self) -> (usize, Option
<usize>) { self.inner.size_hint() }
1742 #[stable(feature = "rust1", since = "1.0.0")]
1743 impl<'a
> DoubleEndedIterator
for LinesAny
<'a
> {
1745 fn next_back(&mut self) -> Option
<&'a
str> { self.inner.next_back() }