• Feature Name: os_str_pattern
• Start Date: 2018-01-16
• RFC PR: rust-lang/rfcs#2295
• Rust Issue: rust-lang/rust#49802

Summary

Generalize the WTF-8 encoding to allow

Motivation

OsStr is missing many common string methods compared

Over the past several years, there has been numerous requests and attempts to implement

The main difficulty applying

The solution proposed by RFC #1309 is to create two sets

The “pattern 2.0” API does not split into two sets

We feel that these designs

Guide-level explanation

The following new methods are now available to OsStr. They behave

#![allow(unused)]
fn main() {
impl OsStr {
    pub fn contains<'a, P>(&'a self, pat: P) -> bool
    where
        P: Pattern<&'a Self>;

    pub fn starts_with<'a, P>(&'a self, pat: P) -> bool
    where
        P: Pattern<&'a Self>;

    pub fn ends_with<'a, P>(&'a self, pat: P) -> bool
    where
        P: Pattern<&'a Self>,
        P::Searcher: ReverseSearcher<&'a Self>;

    pub fn find<'a, P>(&'a self, pat: P) -> Option<usize>
    where
        P: Pattern<&'a Self>;

    pub fn rfind<'a, P>(&'a self, pat: P) -> Option<usize>
    where
        P: Pattern<&'a Self>,
        P::Searcher: ReverseSearcher<&'a Self>;

    /// Finds the first range of this string which contains the pattern.
    ///
    /// # Examples
    ///
    /// ```rust
    /// let path = OsStr::new("/usr/bin/bash");
    /// let range = path.find_range("/b");
    /// assert_eq!(range, Some(4..6));
    /// assert_eq!(path[range.unwrap()], OsStr::new("/b"));
    /// ```
    pub fn find_range<'a, P>(&'a self, pat: P) -> Option<Range<usize>>
    where
        P: Pattern<&'a Self>;

    /// Finds the last range of this string which contains the pattern.
    ///
    /// # Examples
    ///
    /// ```rust
    /// let path = OsStr::new("/usr/bin/bash");
    /// let range = path.rfind_range("/b");
    /// assert_eq!(range, Some(8..10));
    /// assert_eq!(path[range.unwrap()], OsStr::new("/b"));
    /// ```
    pub fn rfind_range<'a, P>(&'a self, pat: P) -> Option<Range<usize>>
    where
        P: Pattern<&'a Self>,
        P::Searcher: ReverseSearcher<&'a Self>;

    // (Note: these should return a concrete iterator type instead of `impl Trait`.
    //  For ease of explanation the concrete type is not listed here.)
    pub fn split<'a, P>(&'a self, pat: P) -> impl Iterator<Item = &'a Self>
    where
        P: Pattern<&'a Self>;

    pub fn rsplit<'a, P>(&'a self, pat: P) -> impl Iterator<Item = &'a Self>
    where
        P: Pattern<&'a Self>,
        P::Searcher: ReverseSearcher<&'a Self>;

    pub fn split_terminator<'a, P>(&'a self, pat: P) -> impl Iterator<Item = &'a Self>
    where
        P: Pattern<&'a Self>;

    pub fn rsplit_terminator<'a, P>(&'a self, pat: P) -> impl Iterator<Item = &'a Self>
    where
        P: Pattern<&'a Self>,
        P::Searcher: ReverseSearcher<&'a Self>;

    pub fn splitn<'a, P>(&'a self, n: usize, pat: P) -> impl Iterator<Item = &'a Self>
    where
        P: Pattern<&'a Self>;

    pub fn rsplitn<'a, P>(&'a self, n: usize, pat: P) -> impl Iterator<Item = &'a Self>
    where
        P: Pattern<&'a Self>,
        P::Searcher: ReverseSearcher<&'a Self>;

    pub fn matches<'a, P>(&'a self, pat: P) -> impl Iterator<Item = &'a Self>
    where
        P: Pattern<&'a Self>;

    pub fn rmatches<'a, P>(&self, pat: P) -> impl Iterator<Item = &'a Self>
    where
        P: Pattern<&'a Self>,
        P::Searcher: ReverseSearcher<&'a Self>;

    pub fn match_indices<'a, P>(&self, pat: P) -> impl Iterator<Item = (usize, &'a Self)>
    where
        P: Pattern<&'a Self>;

    pub fn rmatch_indices<'a, P>(&self, pat: P) -> impl Iterator<Item = (usize, &'a Self)>
    where
        P: Pattern<&'a Self>,
        P::Searcher: ReverseSearcher<&'a Self>;

    // this is new
    pub fn match_ranges<'a, P>(&'a self, pat: P) -> impl Iterator<Item = (Range<usize>, &'a Self)>
    where
        P: Pattern<&'a Self>;

    // this is new
    pub fn rmatch_ranges<'a, P>(&'a self, pat: P) -> impl Iterator<Item = (Range<usize>, &'a Self)>
    where
        P: Pattern<&'a Self>,
        P::Searcher: ReverseSearcher<&'a Self>;

    pub fn trim_matches<'a, P>(&'a self, pat: P) -> &'a Self
    where
        P: Pattern<&'a Self>,
        P::Searcher: DoubleEndedSearcher<&'a Self>;

    pub fn trim_left_matches<'a, P>(&'a self, pat: P) -> &'a Self
    where
        P: Pattern<&'a Self>;

    pub fn trim_right_matches<'a, P>(&'a self, pat: P) -> &'a Self
    where
        P: Pattern<&'a Self>,
        P::Searcher: ReverseSearcher<&'a Self>;

    pub fn replace<'a, P>(&'a self, from: P, to: &'a Self) -> Self::Owned
    where
        P: Pattern<&'a Self>;

    pub fn replacen<'a, P>(&'a self, from: P, to: &'a Self, count: usize) -> Self::Owned
    where
        P: Pattern<&'a Self>;
}
}

We also allow

#![allow(unused)]
fn main() {
impl Index<RangeFull> for OsStr { ... }
impl Index<RangeFrom<usize>> for OsStr { ... }
impl Index<RangeTo<usize>> for OsStr { ... }
impl Index<Range<usize>> for OsStr { ... }
}

Example:

#![allow(unused)]
fn main() {
// (assume we are on Windows)

let path = OsStr::new(r"C:\Users\Admin\😀\😁😂😃😄.txt");
// can use starts_with, ends_with
assert!(path.starts_with(OsStr::new(r"C:\")));
assert!(path.ends_with(OsStr::new(".txt"));
// can use rfind_range to get the range of substring
let last_backslash = path.rfind_range(OsStr::new(r"\")).unwrap();
assert_eq!(last_backslash, 16..17);
// can perform slicing.
let file_name = &path[last_backslash.end..];
// can perform splitting, even if it results in invalid Unicode!
let mut parts = file_name.split(&*OsString::from_wide(&[0xd83d]));
assert_eq!(parts.next(), Some(OsStr::new("")));
assert_eq!(parts.next(), Some(&*OsString::from_wide(&[0xde01])));
assert_eq!(parts.next(), Some(&*OsString::from_wide(&[0xde02])));
assert_eq!(parts.next(), Some(&*OsString::from_wide(&[0xde03])));
assert_eq!(parts.next(), Some(&*OsString::from_wide(&[0xde04, 0x2e, 0x74, 0x78, 0x74])));
assert_eq!(parts.next(), None);
}

Reference-level explanation

It is trivial to apply

We will generalize the encoding of OsStr to “OMG-WTF-8” which specifies

1. Slicing a surrogate pair in half:

   
   #![allow(unused)]
   fn main() {
   let s = OsStr::new("\u{10000}");
   assert_eq!(&s[..2], &*OsString::from_wide(&[0xd800]));
   assert_eq!(&s[2..], &*OsString::from_wide(&[0xdc00]));
   }
   

2. Finding a surrogate code point, no matter paired or unpaired:

   
   #![allow(unused)]
   fn main() {
   let needle = OsString::from_wide(&[0xdc00]);
   assert_eq!(OsStr::new("\u{10000}").find(&needle), Some(2));
   assert_eq!(OsString::from_wide(&[0x3f, 0xdc00]).find(&needle), Some(1));
   }
   

These allow

Slicing

A surrogate pair is a 4-byte sequence

"\u{10000}"      = f0 90 80 80
"\u{10000}"[..2] = f0 90 80
"\u{10000}"[2..] =    90 80 80

The index splitting the surrogate pair will be positioned at the middle of the 4-byte sequence

Note that this means:

1. x[..i] and x[i..] will have overlapping
   重なる/重なり
   parts. This makes OsStr::split_at_mut (if exists) unable to split a surrogate pair in half. This also means Pattern<&mut OsStr> cannot be implemented
   実装する
   for &OsStr.
2. The length of x[..n] may be longer than n.

Platform-agnostic guarantees

保証する

If an index points to an invalid position (e.g. \u{1000}[1..] or "\u{10000}"[1..] or "\u{10000}"[3..]), a panic will be raised, similar

• 0.
• self.len().
• The returned indices from find(), rfind(), match_indices() and rmatch_indices().
• The returned ranges
  範囲
  from find_range(), rfind_range(), match_ranges() and rmatch_ranges().

Index arithmetic

For WTF-8 encoding on Windows, we define:

• boundary of a character
  文字
  or surrogate byte sequence
  連なり、並び
  is Valid.
  有効な、正しい
• middle (byte 2) of a 4-byte sequence
  連なり、並び
  is Valid.
  有効な、正しい
• interior of a 2- or 3-byte sequence
  連なり、並び
  is Invalid.
• byte 1 or 3 of a 4-byte sequence
  連なり、並び
  is Invalid.

Outside of Windows where the OsStr consists

Note that we have never guaranteed

Comparison

比較

and storage

保存場所、保管スペース

All OsStr strings with sliced

• If the string starts with [\x80-\xbf]{3}, replace these 3 bytes with the canonical low surrogate encoding.
• If the string ends with [\xf0-\xf4][\x80-\xbf]{2}, replace these 3 bytes with the canonical high surrogate encoding.

We can this transformation “canonicalization”.

All owned OsStr should be canonicalized

Two OsStr are compared

Matching

一致する、マッチさせる

When an OsStr is used for matching,

xxxx(
    \xed\xa6\xab        # canonical representation
|
    \xf2\x86[\xb0-\xbf] # split representation
)

and matching

(
    \xed\xb3\xaf                        # canonical representation
|
    [\x80-\xbf][\x83\x93\xa3\xb3]\xaf   # split representation
)xxxx

After finding a match,

Pattern API

As of Rust 1.25, we can search a &str using a character,

There are some drafts to generalize this so that we could retain mutability and search in more types such as &[T] and &OsStr, as described

This RFC assumes the target of generalizing

Assuming we do want to generalize Pattern API, the implementor should note the issue of splitting a surrogate pair:

1. A match
   一致する、マッチさせる
   which starts with a low surrogate will point to byte 1 of the 4-byte sequence
   連なり、並び
2. An index always point to byte 2 of the 4-byte sequence
   連なり、並び
3. A match
   一致する、マッチさせる
   which ends with a high surrogate will point to byte 3 of the 4-byte sequence
   連なり、並び

Implementation

The following outlines the generalized Pattern API which could work for &OsStr:

#![allow(unused)]
fn main() {
// in module `core::pattern`:

pub trait Pattern<H: Haystack>: Sized {
    type Searcher: Searcher<H>;
    fn into_searcher(self, haystack: H) -> Self::Searcher;
    fn is_contained_in(self, haystack: H) -> bool;
    fn is_prefix_of(self, haystack: H) -> bool;
    fn is_suffix_of(self, haystack: H) -> bool where Self::Searcher: ReverseSearcher<H>;
}

pub trait Searcher<H: Haystack> {
    fn haystack(&self) -> H;
    fn next_match(&mut self) -> Option<(H::StartCursor, H::EndCursor)>;
    fn next_reject(&mut self) -> Option<(H::StartCursor, H::EndCursor)>;
}

pub trait ReverseSearcher<H: Haystack>: Searcher<H> {
    fn next_match_back(&mut self) -> Option<(H::StartCursor, H::EndCursor)>;
    fn next_reject_back(&mut self) -> Option<(H::StartCursor, H::EndCursor)>;
}

pub trait DoubleEndedSearcher<H: Haystack>: ReverseSearcher<H> {}

// equivalent to SearchPtrs in "Pattern API 1.5"
// and PatternHaystack in "Pattern API 2.0"
pub trait Haystack: Sized {
    type StartCursor: Copy + PartialOrd<Self::EndCursor>;
    type EndCursor: Copy + PartialOrd<Self::StartCursor>;

    // The following 5 methods are same as those in "Pattern API 1.5"
    // except the cursor type is split into two.
    fn cursor_at_front(hs: &Self) -> Self::StartCursor;
    fn cursor_at_back(hs: &Self) -> Self::EndCursor;
    unsafe fn start_cursor_to_offset(hs: &Self, cur: Self::StartCursor) -> usize;
    unsafe fn end_cursor_to_offset(hs: &Self, cur: Self::EndCursor) -> usize;
    unsafe fn range_to_self(hs: Self, start: Self::StartCursor, end: Self::EndCursor) -> Self;

    // And then we want to swap between the two cursor types
    unsafe fn start_to_end_cursor(hs: &Self, cur: Self::StartCursor) -> Self::EndCursor;
    unsafe fn end_to_start_cursor(hs: &Self, cur: Self::EndCursor) -> Self::StartCursor;
}
}

For the &OsStr haystack, we define

The start_to_end_cursor function will return cur + 2 if we find that cur points to the middle of a 4-byte sequence.

The start_cursor_to_offset function will return cur - hs + 1 if we find that cur points to the middle of a 4-byte sequenced.

These type safety measures ensure

#![allow(unused)]
fn main() {
// (actual code implementing `.split()`)
match self.matcher.next_match() {
    Some((a, b)) => unsafe {
        let haystack = self.matcher.haystack();
        let a = H::start_to_end_cursor(&haystack, a);
        let b = H::end_to_start_cursor(&haystack, b);
        let elt = H::range_to_self(haystack, self.start, a);
        // ^ without `start_to_end_cursor`, the slice `elt` may be short by 2 bytes
        self.start = b;
        // ^ without `end_to_start_cursor`, the next starting position may skip 2 bytes
        Some(elt)
    },
    None => self.get_end(),
}
}

Drawbacks

• It breaks the invariant x[..n].len() == n.

  Note that OsStr did not provide a slicing operator,

  演算子
  and it already violated
  違反する
  the invariant (x + y).len() == x.len() + y.len().

• A surrogate code point may be 2 or 3 indices long depending on context.

  文脈、背景

  This means code using x[i..(i+n)] may give wrong result.

  結果、戻り値

  
  #![allow(unused)]
  fn main() {
  let needle = OsString::from_wide(&[0xdc00]);
  let haystack = OsStr::new("\u{10000}a");
  let index = haystack.find(&needle).unwrap();
  let matched = &haystack[index..(index + needle.len())];
  // `matched` will contain "\u{dc00}a" instead of "\u{dc00}".
  }
  

  As a workaround, we introduced find_range and match_ranges. Note that this is already a problem to solve if we want to make Regex a pattern of strings.

Rationale and alternatives

代わりのもの、選択肢

Indivisible surrogate pair

This RFC is the only design

An alternative

• The pattern API becomes a simple substring
  部分文字列
  search.
• Slicing behavior
  ふるまい
  is consistent with str.

There are two potential implementations

1. Declare

   宣言する
   that a surrogate pair does not contain
   含む
   the unpaired surrogate, i.e. make "\u{10000}".find("\u{d800}") return None. An unpaired surrogate can only be used to match
   一致する、マッチさせる
   another unpaired surrogate.

   If we choose this, it means x.find(z).is_some() does not imply (x + y).find(z).is_some().

2. Disallow

   許可しない
   matching
   一致する、マッチさせる
   when the pattern contains
   含む
   an unpaired surrogate at the boundary, i.e. make "\u{10000}".find("\u{d800}") panic. This is the approach chosen by “Pattern API 2.0”.

Note that, for consistency, we need to make "\u{10000}".starts_with("\u{d800}") return false or panic.

Slicing at real byte offset

The current RFC defines

"\u{10000}"      = f0 90 80 80
"\u{10000}"[..2] = f0 90 80
"\u{10000}"[2..] =    90 80 80

The main advantage of this scheme is we could use the same number as the start and end index.

#![allow(unused)]
fn main() {
let s = OsStr::new("\u{10000}");
assert_eq!(s.len(), 4);
let index = s.find('\u{dc00}').unwrap();
let right = &s[index..];  // [90 80 80]
let left = &s[..index];   // [f0 90 80]
}

An alternative

"\u{10000}"      = f0 90 80 80
"\u{10000}"[..3] = f0 90 80
"\u{10000}"[1..] =    90 80 80

However the question would be, what should s[..1] do?

• Panic — But this means we cannot get left. We could inspect the raw

  生の
  bytes of s itself and perform &s[..(index + 2)], but we never explicitly
  明示的に
  exposed the encoding of OsStr, so we cannot read a single
  単一の
  byte and thus
  それゆえに、従って、
  impossible to do this.

• Treat

  取り扱う
  as same as s[..3] — But then this inherits
  継承する
  all the disadvantages of using 2 as valid
  有効な、正しい
  index, plus we need to consider
  考える、みなす
  whether s[1..3] and s[3..1] should be valid.
  有効な、正しい

Given

Unresolved questions

None yet.