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 //! String manipulation
13 //! For more details, see std::str
15 #![doc(primitive = "str")]
17 use self::OldSearcher
::{TwoWay, TwoWayLong}
;
18 use self::pattern
::Pattern
;
19 use self::pattern
::{Searcher, ReverseSearcher, DoubleEndedSearcher}
;
27 use iter
::ExactSizeIterator
;
28 use iter
::{Map, Iterator, DoubleEndedIterator}
;
30 use ops
::{Fn, FnMut, FnOnce}
;
31 use option
::Option
::{self, None, Some}
;
32 use raw
::{Repr, Slice}
;
33 use result
::Result
::{self, Ok, Err}
;
34 use slice
::{self, SliceExt}
;
39 /// A trait to abstract the idea of creating a new instance of a type from a
41 #[stable(feature = "rust1", since = "1.0.0")]
43 /// The associated error which can be returned from parsing.
44 #[stable(feature = "rust1", since = "1.0.0")]
47 /// Parses a string `s` to return a value of this type.
49 /// If parsing succeeds, return the value inside `Ok`, otherwise
50 /// when the string is ill-formatted return an error specific to the
51 /// inside `Err`. The error type is specific to implementation of the trait.
52 #[stable(feature = "rust1", since = "1.0.0")]
53 fn from_str(s
: &str) -> Result
<Self, Self::Err
>;
56 #[stable(feature = "rust1", since = "1.0.0")]
57 impl FromStr
for bool
{
58 type Err
= ParseBoolError
;
60 /// Parse a `bool` from a string.
62 /// Yields a `Result<bool, ParseBoolError>`, because `s` may or may not
63 /// actually be parseable.
68 /// use std::str::FromStr;
70 /// assert_eq!(FromStr::from_str("true"), Ok(true));
71 /// assert_eq!(FromStr::from_str("false"), Ok(false));
72 /// assert!(<bool as FromStr>::from_str("not even a boolean").is_err());
75 /// Note, in many cases, the `.parse()` method on `str` is more proper.
78 /// assert_eq!("true".parse(), Ok(true));
79 /// assert_eq!("false".parse(), Ok(false));
80 /// assert!("not even a boolean".parse::<bool>().is_err());
83 fn from_str(s
: &str) -> Result
<bool
, ParseBoolError
> {
87 _
=> Err(ParseBoolError { _priv: () }
),
92 /// An error returned when parsing a `bool` from a string fails.
93 #[derive(Debug, Clone, PartialEq)]
94 #[stable(feature = "rust1", since = "1.0.0")]
95 pub struct ParseBoolError { _priv: () }
97 #[stable(feature = "rust1", since = "1.0.0")]
98 impl fmt
::Display
for ParseBoolError
{
99 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
100 "provided string was not `true` or `false`".fmt(f
)
105 Section: Creating a string
108 /// Errors which can occur when attempting to interpret a byte slice as a `str`.
109 #[derive(Copy, Eq, PartialEq, Clone, Debug)]
110 #[stable(feature = "rust1", since = "1.0.0")]
111 pub struct Utf8Error
{
116 /// Returns the index in the given string up to which valid UTF-8 was
119 /// Starting at the index provided, but not necessarily at it precisely, an
120 /// invalid UTF-8 encoding sequence was found.
121 #[unstable(feature = "utf8_error", reason = "method just added")]
122 pub fn valid_up_to(&self) -> usize { self.valid_up_to }
125 /// Converts a slice of bytes to a string slice without performing any
128 /// Once the slice has been validated as utf-8, it is transmuted in-place and
129 /// returned as a '&str' instead of a '&[u8]'
133 /// Returns `Err` if the slice is not utf-8 with a description as to why the
134 /// provided slice is not utf-8.
135 #[stable(feature = "rust1", since = "1.0.0")]
136 pub fn from_utf8(v
: &[u8]) -> Result
<&str, Utf8Error
> {
137 try
!(run_utf8_validation_iterator(&mut v
.iter()));
138 Ok(unsafe { from_utf8_unchecked(v) }
)
141 /// Converts a slice of bytes to a string slice without checking
142 /// that the string contains valid UTF-8.
144 #[stable(feature = "rust1", since = "1.0.0")]
145 pub unsafe fn from_utf8_unchecked
<'a
>(v
: &'a
[u8]) -> &'a
str {
149 #[stable(feature = "rust1", since = "1.0.0")]
150 impl fmt
::Display
for Utf8Error
{
151 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
152 write
!(f
, "invalid utf-8: invalid byte near index {}", self.valid_up_to
)
160 /// Iterator for the char (representing *Unicode Scalar Values*) of a string
162 /// Created with the method `.chars()`.
164 #[stable(feature = "rust1", since = "1.0.0")]
165 pub struct Chars
<'a
> {
166 iter
: slice
::Iter
<'a
, u8>
169 /// Return the initial codepoint accumulator for the first byte.
170 /// The first byte is special, only want bottom 5 bits for width 2, 4 bits
171 /// for width 3, and 3 bits for width 4.
173 fn utf8_first_byte(byte
: u8, width
: u32) -> u32 { (byte & (0x7F >> width)) as u32 }
175 /// Return the value of `ch` updated with continuation byte `byte`.
177 fn utf8_acc_cont_byte(ch
: u32, byte
: u8) -> u32 { (ch << 6) | (byte & CONT_MASK) as u32 }
179 /// Checks whether the byte is a UTF-8 continuation byte (i.e. starts with the
182 fn utf8_is_cont_byte(byte
: u8) -> bool { (byte & !CONT_MASK) == TAG_CONT_U8 }
185 fn unwrap_or_0(opt
: Option
<&u8>) -> u8 {
192 /// Reads the next code point out of a byte iterator (assuming a
193 /// UTF-8-like encoding).
194 #[unstable(feature = "core")]
196 pub fn next_code_point(bytes
: &mut slice
::Iter
<u8>) -> Option
<u32> {
198 let x
= match bytes
.next() {
200 Some(&next_byte
) if next_byte
< 128 => return Some(next_byte
as u32),
201 Some(&next_byte
) => next_byte
,
204 // Multibyte case follows
205 // Decode from a byte combination out of: [[[x y] z] w]
206 // NOTE: Performance is sensitive to the exact formulation here
207 let init
= utf8_first_byte(x
, 2);
208 let y
= unwrap_or_0(bytes
.next());
209 let mut ch
= utf8_acc_cont_byte(init
, y
);
212 // 5th bit in 0xE0 .. 0xEF is always clear, so `init` is still valid
213 let z
= unwrap_or_0(bytes
.next());
214 let y_z
= utf8_acc_cont_byte((y
& CONT_MASK
) as u32, z
);
215 ch
= init
<< 12 | y_z
;
218 // use only the lower 3 bits of `init`
219 let w
= unwrap_or_0(bytes
.next());
220 ch
= (init
& 7) << 18 | utf8_acc_cont_byte(y_z
, w
);
227 /// Reads the last code point out of a byte iterator (assuming a
228 /// UTF-8-like encoding).
229 #[unstable(feature = "core")]
231 pub fn next_code_point_reverse(bytes
: &mut slice
::Iter
<u8>) -> Option
<u32> {
233 let w
= match bytes
.next_back() {
235 Some(&next_byte
) if next_byte
< 128 => return Some(next_byte
as u32),
236 Some(&back_byte
) => back_byte
,
239 // Multibyte case follows
240 // Decode from a byte combination out of: [x [y [z w]]]
242 let z
= unwrap_or_0(bytes
.next_back());
243 ch
= utf8_first_byte(z
, 2);
244 if utf8_is_cont_byte(z
) {
245 let y
= unwrap_or_0(bytes
.next_back());
246 ch
= utf8_first_byte(y
, 3);
247 if utf8_is_cont_byte(y
) {
248 let x
= unwrap_or_0(bytes
.next_back());
249 ch
= utf8_first_byte(x
, 4);
250 ch
= utf8_acc_cont_byte(ch
, y
);
252 ch
= utf8_acc_cont_byte(ch
, z
);
254 ch
= utf8_acc_cont_byte(ch
, w
);
259 #[stable(feature = "rust1", since = "1.0.0")]
260 impl<'a
> Iterator
for Chars
<'a
> {
264 fn next(&mut self) -> Option
<char> {
265 next_code_point(&mut self.iter
).map(|ch
| {
266 // str invariant says `ch` is a valid Unicode Scalar Value
274 fn size_hint(&self) -> (usize, Option
<usize>) {
275 let (len
, _
) = self.iter
.size_hint();
276 // `(len + 3)` can't overflow, because we know that the `slice::Iter`
277 // belongs to a slice in memory which has a maximum length of
278 // `isize::MAX` (that's well below `usize::MAX`).
279 ((len
+ 3) / 4, Some(len
))
283 #[stable(feature = "rust1", since = "1.0.0")]
284 impl<'a
> DoubleEndedIterator
for Chars
<'a
> {
286 fn next_back(&mut self) -> Option
<char> {
287 next_code_point_reverse(&mut self.iter
).map(|ch
| {
288 // str invariant says `ch` is a valid Unicode Scalar Value
296 /// Iterator for a string's characters and their byte offsets.
298 #[stable(feature = "rust1", since = "1.0.0")]
299 pub struct CharIndices
<'a
> {
304 #[stable(feature = "rust1", since = "1.0.0")]
305 impl<'a
> Iterator
for CharIndices
<'a
> {
306 type Item
= (usize, char);
309 fn next(&mut self) -> Option
<(usize, char)> {
310 let (pre_len
, _
) = self.iter
.iter
.size_hint();
311 match self.iter
.next() {
314 let index
= self.front_offset
;
315 let (len
, _
) = self.iter
.iter
.size_hint();
316 self.front_offset
+= pre_len
- len
;
323 fn size_hint(&self) -> (usize, Option
<usize>) {
324 self.iter
.size_hint()
328 #[stable(feature = "rust1", since = "1.0.0")]
329 impl<'a
> DoubleEndedIterator
for CharIndices
<'a
> {
331 fn next_back(&mut self) -> Option
<(usize, char)> {
332 match self.iter
.next_back() {
335 let (len
, _
) = self.iter
.iter
.size_hint();
336 let index
= self.front_offset
+ len
;
343 /// External iterator for a string's bytes.
344 /// Use with the `std::iter` module.
346 /// Created with the method `.bytes()`.
347 #[stable(feature = "rust1", since = "1.0.0")]
349 pub struct Bytes
<'a
>(Map
<slice
::Iter
<'a
, u8>, BytesDeref
>);
351 /// A nameable, clonable fn type
355 impl<'a
> Fn
<(&'a
u8,)> for BytesDeref
{
357 extern "rust-call" fn call(&self, (ptr
,): (&'a
u8,)) -> u8 {
362 impl<'a
> FnMut
<(&'a
u8,)> for BytesDeref
{
364 extern "rust-call" fn call_mut(&mut self, (ptr
,): (&'a
u8,)) -> u8 {
365 Fn
::call(&*self, (ptr
,))
369 impl<'a
> FnOnce
<(&'a
u8,)> for BytesDeref
{
373 extern "rust-call" fn call_once(self, (ptr
,): (&'a
u8,)) -> u8 {
374 Fn
::call(&self, (ptr
,))
378 #[stable(feature = "rust1", since = "1.0.0")]
379 impl<'a
> Iterator
for Bytes
<'a
> {
383 fn next(&mut self) -> Option
<u8> {
388 fn size_hint(&self) -> (usize, Option
<usize>) {
393 #[stable(feature = "rust1", since = "1.0.0")]
394 impl<'a
> DoubleEndedIterator
for Bytes
<'a
> {
396 fn next_back(&mut self) -> Option
<u8> {
401 #[stable(feature = "rust1", since = "1.0.0")]
402 impl<'a
> ExactSizeIterator
for Bytes
<'a
> {
404 fn len(&self) -> usize {
409 /// This macro generates a Clone impl for string pattern API
410 /// wrapper types of the form X<'a, P>
411 macro_rules
! derive_pattern_clone
{
412 (clone $t
:ident with
|$s
:ident
| $e
:expr
) => {
413 impl<'a
, P
: Pattern
<'a
>> Clone
for $t
<'a
, P
>
414 where P
::Searcher
: Clone
416 fn clone(&self) -> Self {
424 /// This macro generates two public iterator structs
425 /// wrapping an private internal one that makes use of the `Pattern` API.
427 /// For all patterns `P: Pattern<'a>` the following items will be
428 /// generated (generics omitted):
430 /// struct $forward_iterator($internal_iterator);
431 /// struct $reverse_iterator($internal_iterator);
433 /// impl Iterator for $forward_iterator
434 /// { /* internal ends up calling Searcher::next_match() */ }
436 /// impl DoubleEndedIterator for $forward_iterator
437 /// where P::Searcher: DoubleEndedSearcher
438 /// { /* internal ends up calling Searcher::next_match_back() */ }
440 /// impl Iterator for $reverse_iterator
441 /// where P::Searcher: ReverseSearcher
442 /// { /* internal ends up calling Searcher::next_match_back() */ }
444 /// impl DoubleEndedIterator for $reverse_iterator
445 /// where P::Searcher: DoubleEndedSearcher
446 /// { /* internal ends up calling Searcher::next_match() */ }
448 /// The internal one is defined outside the macro, and has almost the same
449 /// semantic as a DoubleEndedIterator by delegating to `pattern::Searcher` and
450 /// `pattern::ReverseSearcher` for both forward and reverse iteration.
452 /// "Almost", because a `Searcher` and a `ReverseSearcher` for a given
453 /// `Pattern` might not return the same elements, so actually implementing
454 /// `DoubleEndedIterator` for it would be incorrect.
455 /// (See the docs in `str::pattern` for more details)
457 /// However, the internal struct still represents a single ended iterator from
458 /// either end, and depending on pattern is also a valid double ended iterator,
459 /// so the two wrapper structs implement `Iterator`
460 /// and `DoubleEndedIterator` depending on the concrete pattern type, leading
461 /// to the complex impls seen above.
462 macro_rules
! generate_pattern_iterators
{
466 $
(#[$forward_iterator_attribute:meta])*
467 struct $forward_iterator
:ident
;
471 $
(#[$reverse_iterator_attribute:meta])*
472 struct $reverse_iterator
:ident
;
474 // Stability of all generated items
476 $
(#[$common_stability_attribute:meta])*
478 // Internal almost-iterator that is being delegated to
480 $internal_iterator
:ident
yielding ($iterty
:ty
);
482 // Kind of delgation - either single ended or double ended
485 $
(#[$forward_iterator_attribute])*
486 $
(#[$common_stability_attribute])*
487 pub struct $forward_iterator
<'a
, P
: Pattern
<'a
>>($internal_iterator
<'a
, P
>);
489 $
(#[$common_stability_attribute])*
490 impl<'a
, P
: Pattern
<'a
>> Iterator
for $forward_iterator
<'a
, P
> {
494 fn next(&mut self) -> Option
<$iterty
> {
499 $
(#[$common_stability_attribute])*
500 impl<'a
, P
: Pattern
<'a
>> Clone
for $forward_iterator
<'a
, P
>
501 where P
::Searcher
: Clone
503 fn clone(&self) -> Self {
504 $
forward_iterator(self.0.clone())
508 $
(#[$reverse_iterator_attribute])*
509 $
(#[$common_stability_attribute])*
510 pub struct $reverse_iterator
<'a
, P
: Pattern
<'a
>>($internal_iterator
<'a
, P
>);
512 $
(#[$common_stability_attribute])*
513 impl<'a
, P
: Pattern
<'a
>> Iterator
for $reverse_iterator
<'a
, P
>
514 where P
::Searcher
: ReverseSearcher
<'a
>
519 fn next(&mut self) -> Option
<$iterty
> {
524 $
(#[$common_stability_attribute])*
525 impl<'a
, P
: Pattern
<'a
>> Clone
for $reverse_iterator
<'a
, P
>
526 where P
::Searcher
: Clone
528 fn clone(&self) -> Self {
529 $
reverse_iterator(self.0.clone())
533 generate_pattern_iterators
!($
($t
)* with $
(#[$common_stability_attribute])*,
535 $reverse_iterator
, $iterty
);
538 double ended
; with $
(#[$common_stability_attribute:meta])*,
539 $forward_iterator
:ident
,
540 $reverse_iterator
:ident
, $iterty
:ty
542 $
(#[$common_stability_attribute])*
543 impl<'a
, P
: Pattern
<'a
>> DoubleEndedIterator
for $forward_iterator
<'a
, P
>
544 where P
::Searcher
: DoubleEndedSearcher
<'a
>
547 fn next_back(&mut self) -> Option
<$iterty
> {
552 $
(#[$common_stability_attribute])*
553 impl<'a
, P
: Pattern
<'a
>> DoubleEndedIterator
for $reverse_iterator
<'a
, P
>
554 where P
::Searcher
: DoubleEndedSearcher
<'a
>
557 fn next_back(&mut self) -> Option
<$iterty
> {
563 single ended
; with $
(#[$common_stability_attribute:meta])*,
564 $forward_iterator
:ident
,
565 $reverse_iterator
:ident
, $iterty
:ty
569 derive_pattern_clone
!{
571 with
|s
| SplitInternal { matcher: s.matcher.clone(), ..*s }
573 struct SplitInternal
<'a
, P
: Pattern
<'a
>> {
576 matcher
: P
::Searcher
,
577 allow_trailing_empty
: bool
,
581 impl<'a
, P
: Pattern
<'a
>> SplitInternal
<'a
, P
> {
583 fn get_end(&mut self) -> Option
<&'a
str> {
584 if !self.finished
&& (self.allow_trailing_empty
|| self.end
- self.start
> 0) {
585 self.finished
= true;
587 let string
= self.matcher
.haystack().slice_unchecked(self.start
, self.end
);
596 fn next(&mut self) -> Option
<&'a
str> {
597 if self.finished { return None }
599 let haystack
= self.matcher
.haystack();
600 match self.matcher
.next_match() {
601 Some((a
, b
)) => unsafe {
602 let elt
= haystack
.slice_unchecked(self.start
, a
);
606 None
=> self.get_end(),
611 fn next_back(&mut self) -> Option
<&'a
str>
612 where P
::Searcher
: ReverseSearcher
<'a
>
614 if self.finished { return None }
616 if !self.allow_trailing_empty
{
617 self.allow_trailing_empty
= true;
618 match self.next_back() {
619 Some(elt
) if !elt
.is_empty() => return Some(elt
),
620 _
=> if self.finished { return None }
624 let haystack
= self.matcher
.haystack();
625 match self.matcher
.next_match_back() {
626 Some((a
, b
)) => unsafe {
627 let elt
= haystack
.slice_unchecked(b
, self.end
);
632 self.finished
= true;
633 Some(haystack
.slice_unchecked(self.start
, self.end
))
639 generate_pattern_iterators
! {
641 /// Created with the method `.split()`.
644 /// Created with the method `.rsplit()`.
647 #[stable(feature = "rust1", since = "1.0.0")]
649 SplitInternal
yielding (&'a
str);
650 delegate double ended
;
653 generate_pattern_iterators
! {
655 /// Created with the method `.split_terminator()`.
656 struct SplitTerminator
;
658 /// Created with the method `.rsplit_terminator()`.
659 struct RSplitTerminator
;
661 #[stable(feature = "rust1", since = "1.0.0")]
663 SplitInternal
yielding (&'a
str);
664 delegate double ended
;
667 derive_pattern_clone
!{
669 with
|s
| SplitNInternal { iter: s.iter.clone(), ..*s }
671 struct SplitNInternal
<'a
, P
: Pattern
<'a
>> {
672 iter
: SplitInternal
<'a
, P
>,
673 /// The number of splits remaining
677 impl<'a
, P
: Pattern
<'a
>> SplitNInternal
<'a
, P
> {
679 fn next(&mut self) -> Option
<&'a
str> {
682 1 => { self.count = 0; self.iter.get_end() }
683 _
=> { self.count -= 1; self.iter.next() }
688 fn next_back(&mut self) -> Option
<&'a
str>
689 where P
::Searcher
: ReverseSearcher
<'a
>
693 1 => { self.count = 0; self.iter.get_end() }
694 _
=> { self.count -= 1; self.iter.next_back() }
699 generate_pattern_iterators
! {
701 /// Created with the method `.splitn()`.
704 /// Created with the method `.rsplitn()`.
707 #[stable(feature = "rust1", since = "1.0.0")]
709 SplitNInternal
yielding (&'a
str);
710 delegate single ended
;
713 derive_pattern_clone
!{
714 clone MatchIndicesInternal
715 with
|s
| MatchIndicesInternal(s
.0.clone())
717 struct MatchIndicesInternal
<'a
, P
: Pattern
<'a
>>(P
::Searcher
);
719 impl<'a
, P
: Pattern
<'a
>> MatchIndicesInternal
<'a
, P
> {
721 fn next(&mut self) -> Option
<(usize, usize)> {
726 fn next_back(&mut self) -> Option
<(usize, usize)>
727 where P
::Searcher
: ReverseSearcher
<'a
>
729 self.0.next_match_back()
733 generate_pattern_iterators
! {
735 /// Created with the method `.match_indices()`.
738 /// Created with the method `.rmatch_indices()`.
739 struct RMatchIndices
;
741 #[unstable(feature = "core",
742 reason
= "type may be removed or have its iterator impl changed")]
744 MatchIndicesInternal
yielding ((usize, usize));
745 delegate double ended
;
748 derive_pattern_clone
!{
749 clone MatchesInternal
750 with
|s
| MatchesInternal(s
.0.clone())
752 struct MatchesInternal
<'a
, P
: Pattern
<'a
>>(P
::Searcher
);
754 impl<'a
, P
: Pattern
<'a
>> MatchesInternal
<'a
, P
> {
756 fn next(&mut self) -> Option
<&'a
str> {
757 self.0.next_match().map(|(a
, b
)| unsafe {
758 // Indices are known to be on utf8 boundaries
759 self.0.haystack().slice_unchecked(a
, b
)
764 fn next_back(&mut self) -> Option
<&'a
str>
765 where P
::Searcher
: ReverseSearcher
<'a
>
767 self.0.next_match_back().map(|(a
, b
)| unsafe {
768 // Indices are known to be on utf8 boundaries
769 self.0.haystack().slice_unchecked(a
, b
)
774 generate_pattern_iterators
! {
776 /// Created with the method `.matches()`.
779 /// Created with the method `.rmatches()`.
782 #[unstable(feature = "core", reason = "type got recently added")]
784 MatchesInternal
yielding (&'a
str);
785 delegate double ended
;
788 /// Created with the method `.lines()`.
789 #[stable(feature = "rust1", since = "1.0.0")]
791 pub struct Lines
<'a
>(SplitTerminator
<'a
, char>);
793 #[stable(feature = "rust1", since = "1.0.0")]
794 impl<'a
> Iterator
for Lines
<'a
> {
798 fn next(&mut self) -> Option
<&'a
str> {
803 fn size_hint(&self) -> (usize, Option
<usize>) {
808 #[stable(feature = "rust1", since = "1.0.0")]
809 impl<'a
> DoubleEndedIterator
for Lines
<'a
> {
811 fn next_back(&mut self) -> Option
<&'a
str> {
816 /// Created with the method `.lines_any()`.
817 #[stable(feature = "rust1", since = "1.0.0")]
819 pub struct LinesAny
<'a
>(Map
<Lines
<'a
>, LinesAnyMap
>);
821 /// A nameable, clonable fn type
825 impl<'a
> Fn
<(&'a
str,)> for LinesAnyMap
{
827 extern "rust-call" fn call(&self, (line
,): (&'a
str,)) -> &'a
str {
829 if l
> 0 && line
.as_bytes()[l
- 1] == b'
\r' { &line[0 .. l - 1] }
834 impl<'a
> FnMut
<(&'a
str,)> for LinesAnyMap
{
836 extern "rust-call" fn call_mut(&mut self, (line
,): (&'a
str,)) -> &'a
str {
837 Fn
::call(&*self, (line
,))
841 impl<'a
> FnOnce
<(&'a
str,)> for LinesAnyMap
{
842 type Output
= &'a
str;
845 extern "rust-call" fn call_once(self, (line
,): (&'a
str,)) -> &'a
str {
846 Fn
::call(&self, (line
,))
850 #[stable(feature = "rust1", since = "1.0.0")]
851 impl<'a
> Iterator
for LinesAny
<'a
> {
855 fn next(&mut self) -> Option
<&'a
str> {
860 fn size_hint(&self) -> (usize, Option
<usize>) {
865 #[stable(feature = "rust1", since = "1.0.0")]
866 impl<'a
> DoubleEndedIterator
for LinesAny
<'a
> {
868 fn next_back(&mut self) -> Option
<&'a
str> {
873 /// The internal state of an iterator that searches for matches of a substring
874 /// within a larger string using two-way search
876 struct TwoWaySearcher
{
888 This is the Two-Way search algorithm, which was introduced in the paper:
889 Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675.
891 Here's some background information.
893 A *word* is a string of symbols. The *length* of a word should be a familiar
894 notion, and here we denote it for any word x by |x|.
895 (We also allow for the possibility of the *empty word*, a word of length zero).
897 If x is any non-empty word, then an integer p with 0 < p <= |x| is said to be a
898 *period* for x iff for all i with 0 <= i <= |x| - p - 1, we have x[i] == x[i+p].
899 For example, both 1 and 2 are periods for the string "aa". As another example,
900 the only period of the string "abcd" is 4.
902 We denote by period(x) the *smallest* period of x (provided that x is non-empty).
903 This is always well-defined since every non-empty word x has at least one period,
904 |x|. We sometimes call this *the period* of x.
906 If u, v and x are words such that x = uv, where uv is the concatenation of u and
907 v, then we say that (u, v) is a *factorization* of x.
909 Let (u, v) be a factorization for a word x. Then if w is a non-empty word such
910 that both of the following hold
912 - either w is a suffix of u or u is a suffix of w
913 - either w is a prefix of v or v is a prefix of w
915 then w is said to be a *repetition* for the factorization (u, v).
917 Just to unpack this, there are four possibilities here. Let w = "abc". Then we
920 - w is a suffix of u and w is a prefix of v. ex: ("lolabc", "abcde")
921 - w is a suffix of u and v is a prefix of w. ex: ("lolabc", "ab")
922 - u is a suffix of w and w is a prefix of v. ex: ("bc", "abchi")
923 - u is a suffix of w and v is a prefix of w. ex: ("bc", "a")
925 Note that the word vu is a repetition for any factorization (u,v) of x = uv,
926 so every factorization has at least one repetition.
928 If x is a string and (u, v) is a factorization for x, then a *local period* for
929 (u, v) is an integer r such that there is some word w such that |w| = r and w is
930 a repetition for (u, v).
932 We denote by local_period(u, v) the smallest local period of (u, v). We sometimes
933 call this *the local period* of (u, v). Provided that x = uv is non-empty, this
934 is well-defined (because each non-empty word has at least one factorization, as
937 It can be proven that the following is an equivalent definition of a local period
938 for a factorization (u, v): any positive integer r such that x[i] == x[i+r] for
939 all i such that |u| - r <= i <= |u| - 1 and such that both x[i] and x[i+r] are
940 defined. (i.e. i > 0 and i + r < |x|).
942 Using the above reformulation, it is easy to prove that
944 1 <= local_period(u, v) <= period(uv)
946 A factorization (u, v) of x such that local_period(u,v) = period(x) is called a
947 *critical factorization*.
949 The algorithm hinges on the following theorem, which is stated without proof:
951 **Critical Factorization Theorem** Any word x has at least one critical
952 factorization (u, v) such that |u| < period(x).
954 The purpose of maximal_suffix is to find such a critical factorization.
957 impl TwoWaySearcher
{
959 fn new(needle
: &[u8]) -> TwoWaySearcher
{
960 let (crit_pos_false
, period_false
) = TwoWaySearcher
::maximal_suffix(needle
, false);
961 let (crit_pos_true
, period_true
) = TwoWaySearcher
::maximal_suffix(needle
, true);
963 let (crit_pos
, period
) =
964 if crit_pos_false
> crit_pos_true
{
965 (crit_pos_false
, period_false
)
967 (crit_pos_true
, period_true
)
970 // This isn't in the original algorithm, as far as I'm aware.
971 let byteset
= needle
.iter()
972 .fold(0, |a
, &b
| (1 << ((b
& 0x3f) as usize)) | a
);
974 // A particularly readable explanation of what's going on here can be found
975 // in Crochemore and Rytter's book "Text Algorithms", ch 13. Specifically
976 // see the code for "Algorithm CP" on p. 323.
978 // What's going on is we have some critical factorization (u, v) of the
979 // needle, and we want to determine whether u is a suffix of
980 // &v[..period]. If it is, we use "Algorithm CP1". Otherwise we use
981 // "Algorithm CP2", which is optimized for when the period of the needle
983 if &needle
[..crit_pos
] == &needle
[period
.. period
+ crit_pos
] {
995 period
: cmp
::max(crit_pos
, needle
.len() - crit_pos
) + 1,
999 memory
: usize::MAX
// Dummy value to signify that the period is long
1004 // One of the main ideas of Two-Way is that we factorize the needle into
1005 // two halves, (u, v), and begin trying to find v in the haystack by scanning
1006 // left to right. If v matches, we try to match u by scanning right to left.
1007 // How far we can jump when we encounter a mismatch is all based on the fact
1008 // that (u, v) is a critical factorization for the needle.
1010 fn next(&mut self, haystack
: &[u8], needle
: &[u8], long_period
: bool
)
1011 -> Option
<(usize, usize)> {
1013 // Check that we have room to search in
1014 if self.position
+ needle
.len() > haystack
.len() {
1018 // Quickly skip by large portions unrelated to our substring
1020 ((haystack
[self.position
+ needle
.len() - 1] & 0x3f)
1021 as usize)) & 1 == 0 {
1022 self.position
+= needle
.len();
1029 // See if the right part of the needle matches
1030 let start
= if long_period { self.crit_pos }
1031 else { cmp::max(self.crit_pos, self.memory) }
;
1032 for i
in start
..needle
.len() {
1033 if needle
[i
] != haystack
[self.position
+ i
] {
1034 self.position
+= i
- self.crit_pos
+ 1;
1042 // See if the left part of the needle matches
1043 let start
= if long_period { 0 }
else { self.memory }
;
1044 for i
in (start
..self.crit_pos
).rev() {
1045 if needle
[i
] != haystack
[self.position
+ i
] {
1046 self.position
+= self.period
;
1048 self.memory
= needle
.len() - self.period
;
1054 // We have found a match!
1055 let match_pos
= self.position
;
1056 self.position
+= needle
.len(); // add self.period for all matches
1058 self.memory
= 0; // set to needle.len() - self.period for all matches
1060 return Some((match_pos
, match_pos
+ needle
.len()));
1064 // Computes a critical factorization (u, v) of `arr`.
1065 // Specifically, returns (i, p), where i is the starting index of v in some
1066 // critical factorization (u, v) and p = period(v)
1069 #[allow(deprecated)]
1070 fn maximal_suffix(arr
: &[u8], reversed
: bool
) -> (usize, usize) {
1071 let mut left
: usize = !0; // Corresponds to i in the paper
1072 let mut right
= 0; // Corresponds to j in the paper
1073 let mut offset
= 1; // Corresponds to k in the paper
1074 let mut period
= 1; // Corresponds to p in the paper
1076 while right
+ offset
< arr
.len() {
1080 a
= arr
[left
.wrapping_add(offset
)];
1081 b
= arr
[right
+ offset
];
1083 a
= arr
[right
+ offset
];
1084 b
= arr
[left
.wrapping_add(offset
)];
1087 // Suffix is smaller, period is entire prefix so far.
1090 period
= right
.wrapping_sub(left
);
1092 // Advance through repetition of the current period.
1093 if offset
== period
{
1100 // Suffix is larger, start over from current location.
1107 (left
.wrapping_add(1), period
)
1111 /// The internal state of an iterator that searches for matches of a substring
1112 /// within a larger string using a dynamically chosen search algorithm
1114 // NB: This is kept around for convenience because
1115 // it is planned to be used again in the future
1117 TwoWay(TwoWaySearcher
),
1118 TwoWayLong(TwoWaySearcher
),
1123 fn new(haystack
: &[u8], needle
: &[u8]) -> OldSearcher
{
1124 if needle
.is_empty() {
1127 // FIXME: Tune this.
1128 // FIXME(#16715): This unsigned integer addition will probably not
1129 // overflow because that would mean that the memory almost solely
1130 // consists of the needle. Needs #16715 to be formally fixed.
1131 } else if needle
.len() + 20 > haystack
.len() {
1132 // Use naive searcher
1135 let searcher
= TwoWaySearcher
::new(needle
);
1136 if searcher
.memory
== usize::MAX
{ // If the period is long
1137 TwoWayLong(searcher
)
1146 // NB: This is kept around for convenience because
1147 // it is planned to be used again in the future
1148 struct OldMatchIndices
<'a
, 'b
> {
1152 searcher
: OldSearcher
1155 impl<'a
, 'b
> OldMatchIndices
<'a
, 'b
> {
1158 fn next(&mut self) -> Option
<(usize, usize)> {
1159 match self.searcher
{
1160 TwoWay(ref mut searcher
)
1161 => searcher
.next(self.haystack
.as_bytes(), self.needle
.as_bytes(), false),
1162 TwoWayLong(ref mut searcher
)
1163 => searcher
.next(self.haystack
.as_bytes(), self.needle
.as_bytes(), true),
1169 Section: Comparing strings
1172 // share the implementation of the lang-item vs. non-lang-item
1174 /// NOTE: This function is (ab)used in rustc::middle::trans::_match
1175 /// to compare &[u8] byte slices that are not necessarily valid UTF-8.
1177 fn eq_slice_(a
: &str, b
: &str) -> bool
{
1178 // NOTE: In theory n should be libc::size_t and not usize, but libc is not available here
1179 #[allow(improper_ctypes)]
1180 extern { fn memcmp(s1: *const i8, s2: *const i8, n: usize) -> i32; }
1181 a
.len() == b
.len() && unsafe {
1182 memcmp(a
.as_ptr() as *const i8,
1183 b
.as_ptr() as *const i8,
1188 /// Bytewise slice equality
1189 /// NOTE: This function is (ab)used in rustc::middle::trans::_match
1190 /// to compare &[u8] byte slices that are not necessarily valid UTF-8.
1193 fn eq_slice(a
: &str, b
: &str) -> bool
{
1201 /// Walk through `iter` checking that it's a valid UTF-8 sequence,
1202 /// returning `true` in that case, or, if it is invalid, `false` with
1203 /// `iter` reset such that it is pointing at the first byte in the
1204 /// invalid sequence.
1206 fn run_utf8_validation_iterator(iter
: &mut slice
::Iter
<u8>)
1207 -> Result
<(), Utf8Error
> {
1208 let whole
= iter
.as_slice();
1210 // save the current thing we're pointing at.
1211 let old
= iter
.clone();
1213 // restore the iterator we had at the start of this codepoint.
1214 macro_rules
! err
{ () => {{
1215 *iter
= old
.clone();
1216 return Err(Utf8Error
{
1217 valid_up_to
: whole
.len() - iter
.as_slice().len()
1221 macro_rules
! next
{ () => {
1224 // we needed data, but there was none: error!
1229 let first
= match iter
.next() {
1231 // we're at the end of the iterator and a codepoint
1232 // boundary at the same time, so this string is valid.
1233 None
=> return Ok(())
1236 // ASCII characters are always valid, so only large
1237 // bytes need more examination.
1239 let w
= UTF8_CHAR_WIDTH
[first
as usize];
1240 let second
= next
!();
1241 // 2-byte encoding is for codepoints \u{0080} to \u{07ff}
1242 // first C2 80 last DF BF
1243 // 3-byte encoding is for codepoints \u{0800} to \u{ffff}
1244 // first E0 A0 80 last EF BF BF
1245 // excluding surrogates codepoints \u{d800} to \u{dfff}
1246 // ED A0 80 to ED BF BF
1247 // 4-byte encoding is for codepoints \u{1000}0 to \u{10ff}ff
1248 // first F0 90 80 80 last F4 8F BF BF
1250 // Use the UTF-8 syntax from the RFC
1252 // https://tools.ietf.org/html/rfc3629
1254 // UTF8-2 = %xC2-DF UTF8-tail
1255 // UTF8-3 = %xE0 %xA0-BF UTF8-tail / %xE1-EC 2( UTF8-tail ) /
1256 // %xED %x80-9F UTF8-tail / %xEE-EF 2( UTF8-tail )
1257 // UTF8-4 = %xF0 %x90-BF 2( UTF8-tail ) / %xF1-F3 3( UTF8-tail ) /
1258 // %xF4 %x80-8F 2( UTF8-tail )
1260 2 => if second
& !CONT_MASK
!= TAG_CONT_U8 {err!()}
,
1262 match (first
, second
, next
!() & !CONT_MASK
) {
1263 (0xE0 , 0xA0 ... 0xBF, TAG_CONT_U8
) |
1264 (0xE1 ... 0xEC, 0x80 ... 0xBF, TAG_CONT_U8
) |
1265 (0xED , 0x80 ... 0x9F, TAG_CONT_U8
) |
1266 (0xEE ... 0xEF, 0x80 ... 0xBF, TAG_CONT_U8
) => {}
1271 match (first
, second
, next
!() & !CONT_MASK
, next
!() & !CONT_MASK
) {
1272 (0xF0 , 0x90 ... 0xBF, TAG_CONT_U8
, TAG_CONT_U8
) |
1273 (0xF1 ... 0xF3, 0x80 ... 0xBF, TAG_CONT_U8
, TAG_CONT_U8
) |
1274 (0xF4 , 0x80 ... 0x8F, TAG_CONT_U8
, TAG_CONT_U8
) => {}
1284 // https://tools.ietf.org/html/rfc3629
1285 static UTF8_CHAR_WIDTH
: [u8; 256] = [
1286 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1287 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x1F
1288 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1289 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x3F
1290 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1291 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x5F
1292 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1293 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x7F
1294 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1295 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0x9F
1296 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1297 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0xBF
1298 0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
1299 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, // 0xDF
1300 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3, // 0xEF
1301 4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0, // 0xFF
1304 /// Struct that contains a `char` and the index of the first byte of
1305 /// the next `char` in a string. This can be used as a data structure
1306 /// for iterating over the UTF-8 bytes of a string.
1307 #[derive(Copy, Clone)]
1308 #[unstable(feature = "str_char",
1309 reason
= "existence of this struct is uncertain as it is frequently \
1310 able to be replaced with char.len_utf8() and/or \
1311 char/char_indices iterators")]
1312 pub struct CharRange
{
1315 /// Index of the first byte of the next `char`
1319 /// Mask of the value bits of a continuation byte
1320 const CONT_MASK
: u8 = 0b0011_1111;
1321 /// Value of the tag bits (tag mask is !CONT_MASK) of a continuation byte
1322 const TAG_CONT_U8
: u8 = 0b1000_0000;
1325 Section: Trait implementations
1329 use cmp
::{Ordering, Ord, PartialEq, PartialOrd, Eq}
;
1330 use cmp
::Ordering
::{Less, Equal, Greater}
;
1333 use option
::Option
::Some
;
1335 use str::{StrExt, eq_slice}
;
1337 #[stable(feature = "rust1", since = "1.0.0")]
1340 fn cmp(&self, other
: &str) -> Ordering
{
1341 for (s_b
, o_b
) in self.bytes().zip(other
.bytes()) {
1342 match s_b
.cmp(&o_b
) {
1343 Greater
=> return Greater
,
1344 Less
=> return Less
,
1349 self.len().cmp(&other
.len())
1353 #[stable(feature = "rust1", since = "1.0.0")]
1354 impl PartialEq
for str {
1356 fn eq(&self, other
: &str) -> bool
{
1357 eq_slice(self, other
)
1360 fn ne(&self, other
: &str) -> bool { !(*self).eq(other) }
1363 #[stable(feature = "rust1", since = "1.0.0")]
1366 #[stable(feature = "rust1", since = "1.0.0")]
1367 impl PartialOrd
for str {
1369 fn partial_cmp(&self, other
: &str) -> Option
<Ordering
> {
1370 Some(self.cmp(other
))
1374 /// Returns a slice of the given string from the byte range
1375 /// [`begin`..`end`).
1377 /// This operation is `O(1)`.
1379 /// Panics when `begin` and `end` do not point to valid characters
1380 /// or point beyond the last character of the string.
1385 /// let s = "Löwe 老虎 Léopard";
1386 /// assert_eq!(&s[0 .. 1], "L");
1388 /// assert_eq!(&s[1 .. 9], "öwe 老");
1390 /// // these will panic:
1391 /// // byte 2 lies within `ö`:
1394 /// // byte 8 lies within `老`
1397 /// // byte 100 is outside the string
1398 /// // &s[3 .. 100];
1400 #[stable(feature = "rust1", since = "1.0.0")]
1401 impl ops
::Index
<ops
::Range
<usize>> for str {
1404 fn index(&self, index
: ops
::Range
<usize>) -> &str {
1405 // is_char_boundary checks that the index is in [0, .len()]
1406 if index
.start
<= index
.end
&&
1407 self.is_char_boundary(index
.start
) &&
1408 self.is_char_boundary(index
.end
) {
1409 unsafe { self.slice_unchecked(index.start, index.end) }
1411 super::slice_error_fail(self, index
.start
, index
.end
)
1416 /// Returns a slice of the string from the beginning to byte
1419 /// Equivalent to `self[0 .. end]`.
1421 /// Panics when `end` does not point to a valid character, or is
1423 #[stable(feature = "rust1", since = "1.0.0")]
1424 impl ops
::Index
<ops
::RangeTo
<usize>> for str {
1428 fn index(&self, index
: ops
::RangeTo
<usize>) -> &str {
1429 // is_char_boundary checks that the index is in [0, .len()]
1430 if self.is_char_boundary(index
.end
) {
1431 unsafe { self.slice_unchecked(0, index.end) }
1433 super::slice_error_fail(self, 0, index
.end
)
1438 /// Returns a slice of the string from `begin` to its end.
1440 /// Equivalent to `self[begin .. self.len()]`.
1442 /// Panics when `begin` does not point to a valid character, or is
1444 #[stable(feature = "rust1", since = "1.0.0")]
1445 impl ops
::Index
<ops
::RangeFrom
<usize>> for str {
1449 fn index(&self, index
: ops
::RangeFrom
<usize>) -> &str {
1450 // is_char_boundary checks that the index is in [0, .len()]
1451 if self.is_char_boundary(index
.start
) {
1452 unsafe { self.slice_unchecked(index.start, self.len()) }
1454 super::slice_error_fail(self, index
.start
, self.len())
1459 #[stable(feature = "rust1", since = "1.0.0")]
1460 impl ops
::Index
<ops
::RangeFull
> for str {
1464 fn index(&self, _index
: ops
::RangeFull
) -> &str {
1470 /// Methods for string slices
1471 #[allow(missing_docs)]
1474 // NB there are no docs here are they're all located on the StrExt trait in
1475 // libcollections, not here.
1477 fn contains
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> bool
;
1478 fn contains_char
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> bool
;
1479 fn chars
<'a
>(&'a
self) -> Chars
<'a
>;
1480 fn bytes
<'a
>(&'a
self) -> Bytes
<'a
>;
1481 fn char_indices
<'a
>(&'a
self) -> CharIndices
<'a
>;
1482 fn split
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> Split
<'a
, P
>;
1483 fn rsplit
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> RSplit
<'a
, P
>
1484 where P
::Searcher
: ReverseSearcher
<'a
>;
1485 fn splitn
<'a
, P
: Pattern
<'a
>>(&'a
self, count
: usize, pat
: P
) -> SplitN
<'a
, P
>;
1486 fn rsplitn
<'a
, P
: Pattern
<'a
>>(&'a
self, count
: usize, pat
: P
) -> RSplitN
<'a
, P
>
1487 where P
::Searcher
: ReverseSearcher
<'a
>;
1488 fn split_terminator
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> SplitTerminator
<'a
, P
>;
1489 fn rsplit_terminator
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> RSplitTerminator
<'a
, P
>
1490 where P
::Searcher
: ReverseSearcher
<'a
>;
1491 fn matches
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> Matches
<'a
, P
>;
1492 fn rmatches
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> RMatches
<'a
, P
>
1493 where P
::Searcher
: ReverseSearcher
<'a
>;
1494 fn match_indices
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> MatchIndices
<'a
, P
>;
1495 fn rmatch_indices
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> RMatchIndices
<'a
, P
>
1496 where P
::Searcher
: ReverseSearcher
<'a
>;
1497 fn lines
<'a
>(&'a
self) -> Lines
<'a
>;
1498 fn lines_any
<'a
>(&'a
self) -> LinesAny
<'a
>;
1499 fn char_len(&self) -> usize;
1500 fn slice_chars
<'a
>(&'a
self, begin
: usize, end
: usize) -> &'a
str;
1501 unsafe fn slice_unchecked
<'a
>(&'a
self, begin
: usize, end
: usize) -> &'a
str;
1502 fn starts_with
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> bool
;
1503 fn ends_with
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> bool
1504 where P
::Searcher
: ReverseSearcher
<'a
>;
1505 fn trim_matches
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> &'a
str
1506 where P
::Searcher
: DoubleEndedSearcher
<'a
>;
1507 fn trim_left_matches
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> &'a
str;
1508 fn trim_right_matches
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> &'a
str
1509 where P
::Searcher
: ReverseSearcher
<'a
>;
1510 fn is_char_boundary(&self, index
: usize) -> bool
;
1511 fn char_range_at(&self, start
: usize) -> CharRange
;
1512 fn char_range_at_reverse(&self, start
: usize) -> CharRange
;
1513 fn char_at(&self, i
: usize) -> char;
1514 fn char_at_reverse(&self, i
: usize) -> char;
1515 fn as_bytes
<'a
>(&'a
self) -> &'a
[u8];
1516 fn find
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> Option
<usize>;
1517 fn rfind
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> Option
<usize>
1518 where P
::Searcher
: ReverseSearcher
<'a
>;
1519 fn find_str
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> Option
<usize>;
1520 fn slice_shift_char
<'a
>(&'a
self) -> Option
<(char, &'a
str)>;
1521 fn subslice_offset(&self, inner
: &str) -> usize;
1522 fn as_ptr(&self) -> *const u8;
1523 fn len(&self) -> usize;
1524 fn is_empty(&self) -> bool
;
1525 fn parse
<T
: FromStr
>(&self) -> Result
<T
, T
::Err
>;
1529 fn slice_error_fail(s
: &str, begin
: usize, end
: usize) -> ! {
1530 assert
!(begin
<= end
);
1531 panic
!("index {} and/or {} in `{}` do not lie on character boundary",
1535 impl StrExt
for str {
1537 fn contains
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> bool
{
1538 pat
.is_contained_in(self)
1542 fn contains_char
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> bool
{
1543 pat
.is_contained_in(self)
1547 fn chars(&self) -> Chars
{
1548 Chars{iter: self.as_bytes().iter()}
1552 fn bytes(&self) -> Bytes
{
1553 Bytes(self.as_bytes().iter().map(BytesDeref
))
1557 fn char_indices(&self) -> CharIndices
{
1558 CharIndices { front_offset: 0, iter: self.chars() }
1562 fn split
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> Split
<'a
, P
> {
1563 Split(SplitInternal
{
1566 matcher
: pat
.into_searcher(self),
1567 allow_trailing_empty
: true,
1573 fn rsplit
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> RSplit
<'a
, P
>
1574 where P
::Searcher
: ReverseSearcher
<'a
>
1576 RSplit(self.split(pat
).0)
1580 fn splitn
<'a
, P
: Pattern
<'a
>>(&'a
self, count
: usize, pat
: P
) -> SplitN
<'a
, P
> {
1581 SplitN(SplitNInternal
{
1582 iter
: self.split(pat
).0,
1588 fn rsplitn
<'a
, P
: Pattern
<'a
>>(&'a
self, count
: usize, pat
: P
) -> RSplitN
<'a
, P
>
1589 where P
::Searcher
: ReverseSearcher
<'a
>
1591 RSplitN(self.splitn(count
, pat
).0)
1595 fn split_terminator
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> SplitTerminator
<'a
, P
> {
1596 SplitTerminator(SplitInternal
{
1597 allow_trailing_empty
: false,
1603 fn rsplit_terminator
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> RSplitTerminator
<'a
, P
>
1604 where P
::Searcher
: ReverseSearcher
<'a
>
1606 RSplitTerminator(self.split_terminator(pat
).0)
1610 fn matches
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> Matches
<'a
, P
> {
1611 Matches(MatchesInternal(pat
.into_searcher(self)))
1615 fn rmatches
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> RMatches
<'a
, P
>
1616 where P
::Searcher
: ReverseSearcher
<'a
>
1618 RMatches(self.matches(pat
).0)
1622 fn match_indices
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> MatchIndices
<'a
, P
> {
1623 MatchIndices(MatchIndicesInternal(pat
.into_searcher(self)))
1627 fn rmatch_indices
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> RMatchIndices
<'a
, P
>
1628 where P
::Searcher
: ReverseSearcher
<'a
>
1630 RMatchIndices(self.match_indices(pat
).0)
1633 fn lines(&self) -> Lines
{
1634 Lines(self.split_terminator('
\n'
))
1638 fn lines_any(&self) -> LinesAny
{
1639 LinesAny(self.lines().map(LinesAnyMap
))
1643 fn char_len(&self) -> usize { self.chars().count() }
1645 fn slice_chars(&self, begin
: usize, end
: usize) -> &str {
1646 assert
!(begin
<= end
);
1648 let mut begin_byte
= None
;
1649 let mut end_byte
= None
;
1651 // This could be even more efficient by not decoding,
1652 // only finding the char boundaries
1653 for (idx
, _
) in self.char_indices() {
1654 if count
== begin { begin_byte = Some(idx); }
1655 if count
== end { end_byte = Some(idx); break; }
1658 if begin_byte
.is_none() && count
== begin { begin_byte = Some(self.len()) }
1659 if end_byte
.is_none() && count
== end { end_byte = Some(self.len()) }
1661 match (begin_byte
, end_byte
) {
1662 (None
, _
) => panic
!("slice_chars: `begin` is beyond end of string"),
1663 (_
, None
) => panic
!("slice_chars: `end` is beyond end of string"),
1664 (Some(a
), Some(b
)) => unsafe { self.slice_unchecked(a, b) }
1669 unsafe fn slice_unchecked(&self, begin
: usize, end
: usize) -> &str {
1670 mem
::transmute(Slice
{
1671 data
: self.as_ptr().offset(begin
as isize),
1677 fn starts_with
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> bool
{
1678 pat
.is_prefix_of(self)
1682 fn ends_with
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> bool
1683 where P
::Searcher
: ReverseSearcher
<'a
>
1685 pat
.is_suffix_of(self)
1689 fn trim_matches
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> &'a
str
1690 where P
::Searcher
: DoubleEndedSearcher
<'a
>
1694 let mut matcher
= pat
.into_searcher(self);
1695 if let Some((a
, b
)) = matcher
.next_reject() {
1697 j
= b
; // Rember earliest known match, correct it below if
1698 // last match is different
1700 if let Some((_
, b
)) = matcher
.next_reject_back() {
1704 // Searcher is known to return valid indices
1705 self.slice_unchecked(i
, j
)
1710 fn trim_left_matches
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> &'a
str {
1711 let mut i
= self.len();
1712 let mut matcher
= pat
.into_searcher(self);
1713 if let Some((a
, _
)) = matcher
.next_reject() {
1717 // Searcher is known to return valid indices
1718 self.slice_unchecked(i
, self.len())
1723 fn trim_right_matches
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> &'a
str
1724 where P
::Searcher
: ReverseSearcher
<'a
>
1727 let mut matcher
= pat
.into_searcher(self);
1728 if let Some((_
, b
)) = matcher
.next_reject_back() {
1732 // Searcher is known to return valid indices
1733 self.slice_unchecked(0, j
)
1738 fn is_char_boundary(&self, index
: usize) -> bool
{
1739 if index
== self.len() { return true; }
1740 match self.as_bytes().get(index
) {
1742 Some(&b
) => b
< 128 || b
>= 192,
1747 fn char_range_at(&self, i
: usize) -> CharRange
{
1748 let (c
, n
) = char_range_at_raw(self.as_bytes(), i
);
1749 CharRange { ch: unsafe { mem::transmute(c) }
, next
: n
}
1753 fn char_range_at_reverse(&self, start
: usize) -> CharRange
{
1754 let mut prev
= start
;
1756 prev
= prev
.saturating_sub(1);
1757 if self.as_bytes()[prev
] < 128 {
1758 return CharRange{ch: self.as_bytes()[prev] as char, next: prev}
1761 // Multibyte case is a fn to allow char_range_at_reverse to inline cleanly
1762 fn multibyte_char_range_at_reverse(s
: &str, mut i
: usize) -> CharRange
{
1763 // while there is a previous byte == 10......
1764 while i
> 0 && s
.as_bytes()[i
] & !CONT_MASK
== TAG_CONT_U8
{
1768 let first
= s
.as_bytes()[i
];
1769 let w
= UTF8_CHAR_WIDTH
[first
as usize];
1772 let mut val
= utf8_first_byte(first
, w
as u32);
1773 val
= utf8_acc_cont_byte(val
, s
.as_bytes()[i
+ 1]);
1774 if w
> 2 { val = utf8_acc_cont_byte(val, s.as_bytes()[i + 2]); }
1775 if w
> 3 { val = utf8_acc_cont_byte(val, s.as_bytes()[i + 3]); }
1777 return CharRange {ch: unsafe { mem::transmute(val) }
, next
: i
};
1780 return multibyte_char_range_at_reverse(self, prev
);
1784 fn char_at(&self, i
: usize) -> char {
1785 self.char_range_at(i
).ch
1789 fn char_at_reverse(&self, i
: usize) -> char {
1790 self.char_range_at_reverse(i
).ch
1794 fn as_bytes(&self) -> &[u8] {
1795 unsafe { mem::transmute(self) }
1798 fn find
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> Option
<usize> {
1799 pat
.into_searcher(self).next_match().map(|(i
, _
)| i
)
1802 fn rfind
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> Option
<usize>
1803 where P
::Searcher
: ReverseSearcher
<'a
>
1805 pat
.into_searcher(self).next_match_back().map(|(i
, _
)| i
)
1808 fn find_str
<'a
, P
: Pattern
<'a
>>(&'a
self, pat
: P
) -> Option
<usize> {
1813 fn slice_shift_char(&self) -> Option
<(char, &str)> {
1814 if self.is_empty() {
1817 let ch
= self.char_at(0);
1818 let next_s
= unsafe { self.slice_unchecked(ch.len_utf8(), self.len()) }
;
1823 fn subslice_offset(&self, inner
: &str) -> usize {
1824 let a_start
= self.as_ptr() as usize;
1825 let a_end
= a_start
+ self.len();
1826 let b_start
= inner
.as_ptr() as usize;
1827 let b_end
= b_start
+ inner
.len();
1829 assert
!(a_start
<= b_start
);
1830 assert
!(b_end
<= a_end
);
1835 fn as_ptr(&self) -> *const u8 {
1840 fn len(&self) -> usize { self.repr().len }
1843 fn is_empty(&self) -> bool { self.len() == 0 }
1846 fn parse
<T
: FromStr
>(&self) -> Result
<T
, T
::Err
> { FromStr::from_str(self) }
1849 #[stable(feature = "rust1", since = "1.0.0")]
1850 impl AsRef
<[u8]> for str {
1852 fn as_ref(&self) -> &[u8] {
1857 /// Pluck a code point out of a UTF-8-like byte slice and return the
1858 /// index of the next code point.
1860 #[unstable(feature = "core")]
1861 pub fn char_range_at_raw(bytes
: &[u8], i
: usize) -> (u32, usize) {
1863 return (bytes
[i
] as u32, i
+ 1);
1866 // Multibyte case is a fn to allow char_range_at to inline cleanly
1867 fn multibyte_char_range_at(bytes
: &[u8], i
: usize) -> (u32, usize) {
1868 let first
= bytes
[i
];
1869 let w
= UTF8_CHAR_WIDTH
[first
as usize];
1872 let mut val
= utf8_first_byte(first
, w
as u32);
1873 val
= utf8_acc_cont_byte(val
, bytes
[i
+ 1]);
1874 if w
> 2 { val = utf8_acc_cont_byte(val, bytes[i + 2]); }
1875 if w
> 3 { val = utf8_acc_cont_byte(val, bytes[i + 3]); }
1877 return (val
, i
+ w
as usize);
1880 multibyte_char_range_at(bytes
, i
)
1883 #[stable(feature = "rust1", since = "1.0.0")]
1884 impl<'a
> Default
for &'a
str {
1885 #[stable(feature = "rust1", since = "1.0.0")]
1886 fn default() -> &'a
str { "" }