Add `substr_range`, `elem_offset`, and `subslice_range` methods

[wr7]

Proposal

Add the following methods

impl str {
    fn substr_range(&self, item: &str) -> Option<Range<usize>>;
}
impl<T> [T] {
    fn subslice_range(&self, item: &[T]) -> Option<Range<usize>>;
    fn elem_offset(&self, item: &T) -> Option<usize>;
}

NOTE: These methods are completely different in both behavior and functionality from str::find and friends. They do not compare characters/items inside of the str/slices. Instead they utilize pointer arithmetic to find where a subslice/item is located in the str/slice.

Problem statement

This change attempts to fix two distinct issue. The first of which is the inflexibility of slice::split, str::split, str::matches, and related methods. The second is for parse errors.

Problem 1

str::split and its related functions are really convenient, but I find myself having to manually implement them if I want more complex logic.

For instance, lets say that I want to split up a string by commas. Specifically, I want to do something like str::split_inclusive, but I want to include the separators at the beginning instead of the end.

You cannot do this with str::split

let foo = "a,bc,d";
for sub in foo.split(",") {
    // Now I have the split up string, but it doesn't have the comma at the beginning :-(
}

Instead, you have to manually do it yourself

    let mut foo = "a,bc,d";

    while let Some(comma_idx) = foo.get(1..).map(|f| 1+f.find(",").unwrap_or(f.len())) {
        let sub = &foo[..comma_idx];
        foo = &foo[comma_idx..];

        // sub now has leading comma
    }

Problem 2

Say I have a function for parsing and a helper function. The Range denotes where in the string the error occurs. We can use that Range to tell the user where the error is if one occurs.

pub fn parse<'a>(in: &'a str) -> Result<usize, Range<usize>> {
    // omitted //
    let a = parse_helper(&in[x..y])?;
    let b = parse_helper(&in[y+1..])?;
   // omitted //
}
fn parse_helper<'a>(in: &'a str) -> Result<usize, Range<usize>> { /* omitted */ }

The issue with this is that the range error from parse_helper is relative to the substring passed to it. This means that we have to manually offset the Range inside of parse.

pub fn parse<'a>(in: &'a str) -> Result<usize, Range<usize>> {
    // omitted //
    let a = parse_helper(&in[x..y]).map_err(|e| e.start + x..e.end + x)?;
    let b = parse_helper(&in[y+1..]).map_err(|e| e.start + y+1..e.end + y+1)?;
   // omitted //
}
// ... //

We could also pass an offset to parse_helper and use that to adjust the returned Range, but that would just move the complexity to the parse_helper function.

This gets even worse if instead of a Range, we have an enum that contains Ranges. Say

enum ParseError {
   Error1(Range<usize>),
   Error2(Range<usize>, Range<usize>),
}

Motivating examples or use cases

Split and similar methods

subslice_offset would allow using indices to extend methods like str::split. We can implement the aforementioned inclusive str::split like so:

let foo = "a,bc,d,";
for sub in foo.split(",") {
    let idx = foo.substr_range(sub).unwrap();
    let sub = &foo[idx.start.saturating_sub(1)..idx.end];
    // Now `sub` is "a", ",bc", ",d", and ","
}

Error handling with string input data

We can also use this method to remove complexity from the code described in Problem 2.

pub fn parse<'a>(in: &'a str) -> Result<usize, &'a str> {
    // omitted //
    let a = parse_helper(&in[x..y])?;
    let b = parse_helper(&in[y+1..])?;
   // omitted //
}
fn parse_helper<'a>(in: &'a str) -> Result<usize, &'a str> { /* omitted */ }

Instead of returning Ranges, we can return &'a str. Then, if a caller of parse wants to find where the error occurred, they can do

let input = "9+10-21";
match parse(input) {
    Ok(val) => { /* omitted */ },
    Err(err) => {
        display_error(input.substr_range(err).unwrap());
    },

Solution sketch

impl str {
    fn substr_range(&self, substr: &str) -> Option<Range<usize>> {
        self.as_bytes().subslice_range(substr.as_bytes())
    }
}

impl<T> [T] {
    fn subslice_range(&self, subslice: &[T]) -> Option<Range<usize>> {
        if core::mem::size_of::<T>() == 0 {
            panic!();
        }

        let self_start = self.as_ptr() as usize;
        let subslice_start = subslice.as_ptr() as usize;

        let byte_start = subslice_start.wrapping_sub(self_start);
        let start = byte_start / core::mem::size_of::<T>();
        let end = start.wrapping_add(subslice.len());

        if byte_start % core::mem::size_of::<T>() != 0 {
            return None;
        }

        if start <= self.len() && end <= self.len() {
            Some(start..end)
        } else {
            None
        }
    }

    fn elem_offset(&self, element: &T) -> Option<usize> {
        if core::mem::size_of::<T>() == 0 {
            panic!();
        }

        let self_start = self.as_ptr() as usize;
        let elem_start = element as *const T as usize;

        let byte_offset = elem_start.wrapping_sub(self_start);
        let offset = byte_offset / core::mem::size_of::<T>();

        if byte_offset % core::mem::size_of::<T>() != 0 {
            return None;
        }

        if offset < self.len() {
            Some(offset)
        } else {
            None
        }
    }
}

The following code demonstrates the above behavior

    let foo = "mississippi".to_owned();
    let is = &foo[4..6];

    assert_eq!(is, "is");
    assert_eq!(foo.substr_offset(is), Some(4..6));

    assert_eq!(foo.substr_offset("is"), None); 

Alternatives

• subslice_offset crate
• str::find (significantly less efficient and has the aforementioned issue)

Links and related work

subslice_offset crate

Old, deprecated str::subslice_offset. (deprecated here).
This was deprecated with str::find being listed as its replacement, but as mentioned before, this has different functionality.

Original subslice_offset PR

rust-lang/rfcs#2796 (an RFC similar to this but only for slices). The PR for this was abandoned because the author did not have time to make suggested changes.

https://github.com/wr7/rfcs/blob/substr_range/text/3648-substr-range.md - An RFC that I wrote for this

https://stackoverflow.com/questions/50781561/how-to-find-the-starting-offset-of-a-string-slice-of-another-string

[joshtriplett]

We reviewed this in today's @rust-lang/libs-api meeting. We felt that the concept was reasonable, but the names and signatures needed some adjustment.

• These should return an Option, and return None if out of bounds.
• Since these have different return types and semantics, they should have different naming: substr_range for the str method, and elem_offset for the [T] method.

(In theory we could also add a subslice_range method that takes &[T] and returns Option<Range<usize>>, but that wasn't part of this ACP.)

[scottmcm]

subslice_range does seem quite reasonable, since one can always .start if needed, and the rest will optimize out easily.

[wr7]

EDIT: It seems that I was confused about the RFC/ACP process (see rust-lang/rfcs#3648 (comment)). I've updated the ACP with your suggestions.

Thank you for reviewing my APC. I also like the elem_offset and substr_range names. The subslice_range method also makes sense.

I've made an RFC PR for this.

[wr7]

I think that panicking instead of returning None might make sense though. This isn't a hill that I'm willing to die on, but returning an Option requires an unwrap which makes using this more verbose. I feel like in most cases (such as when using it with str::split or str::lines), substr_range should never return None.

[kennytm]

These functions are essentially doing pointer::offset_from. However, these functions are marketed as "safe" and thus can't assume the input is really a subslice of self, and thus must use self.as_ptr() as usize - subslice.as_ptr() as usize and forego potential optimization opportunity.

Also note that the current implementation can give nonsense result without invoking unsafe code.

fn main() {
    let a = [1, 2, 3, 4];
    let b = [5, 6, 7, 8];
    dbg!(a.subslice_range(&a[4..4])); // good, Some(4..4)
    dbg!(b.subslice_range(&a[4..4])); // bad!, expected None got Some(0..0)
}

[scottmcm]

However, these functions are marketed as "safe" and thus can't assume the input is really a subslice of self

Hmm, and provenance causes a mess here, doesn't it. Checking that the pointers meet slice.begin <= item <= slice.end isn't enough to be able to sub_ptr, since that can be true even if item comes from a separate allocation that just so happens to be right after self in memory -- especially with item = &[] :/

[programmerjake]

I think elem_offset can be implemented reliably since it doesn't have to handle the one-past-the-end edge-case which the others have to. it would be kinda a pain but you can still use it to retrieve string offsets:

fn str_offset_if_non_empty(a: &str, b: &str) -> Option<usize> {
    let b = b.as_bytes().first()?;
    a.as_bytes().elem_offset(b)
}

[programmerjake]

actually, elem_offset still has a gotcha: what if you pass it a pointer to an element that overlaps two elements?

let arr = [[0, 1], [2, 3]];
let weird_elm: &[_; 2] = &arr.flatten()[1..3].try_into().unwrap();
assert_eq!(weird_elm, [1, 2]);
let offset = arr.elem_offset(weird_elm);
assert_eq!(offset, None); // what I expect, since it isn't exactly at any one element