Xi-editor: Make Rope::slice_to_string return a Cow

[cmyr]

Currently this function always allocates a new string, which is only necessary when the slice spans multiple leaves. It should be returning a &str where possible.

This shouldn't be too tricky, it's just something we've never managed to get around to.

[brizental]

I'd like to work on this!

[cmyr]

@brizental great, it’s all yours :)

[brizental]

Hey guys, just to make sure I'm in the right track here. I have to change the return value of Rope::slice_to_string and then adjust anywhere that might be expecting something else. So the function would become:

pub fn slice_to_string(&self, start: usize, end: usize) -> Cow<str> {
    let mut result = String::new();
    for chunk in self.iter_chunks(start, end) {
        result.push_str(chunk);
    }
    Cow::from(result)
}

Is that right?

[cmyr]

This is correct at a high level, but it's missing a little bit in the implementation. The thing that Cow gives us is that it allows us to abstract away whether the underlying str is backed by a borrowed &str or an owned String. The concrete advantage of this is that it lets us avoid allocating a String when that isn't necessary.

To back up: the Rope data structure stores its contents in a tree. The node of each tree is a String. In many cases (for instance iterating through lines) we only need to access a single node. It is only in certain less frequent cases where we need to access a region that spans multiple nodes.

If we knew that the range we were passing to slice_to_string was contained in a single node, we could just borrow that node's contents as a &str. Unfortunately, though, we can't know this, so currently we allocate a new string regardless. What we would _like_ to do is to only allocate this string when self.iter_chunks returns more than one chunk. Otherwise we want just return a borrow.

Check out the docs for Cow if you haven't already, and let me know if anything isn't clear. :)

We might also want to change the name of slice_to_string to something like get_slice or slice_to_cow.

[martin-fink]

Hi,

since the last comment on this issue was in July, I decided that I'd look into that, if that's ok with you.

The following is the code I came up with, handling the cases if there is no returned element, only one returned element (which is the reason Cow should be used here) and if there is more than one returned element.

    pub fn slice_to_string<T>(&self, range: T) -> Cow<str>
        where T: RangeBounds<usize>
    {
        let mut iter: ChunkIter = self.iter_chunks(range);
        match iter.end {
            0 => Cow::from(""),
            1 => Cow::from(iter.next().unwrap()),
            _ => {
                let mut result = String::new();
                for chunk in iter {
                    result.push_str(chunk);
                }
                result
            }
        }
    }

[cmyr]

I think the approach is basically correct, I don't think end does quite what you want; iirc it refers to the end of the range to be sliced, and doesn't have anything to do with the number of chunks.

I would do something like,

let mut iter = self.iter_chunks(range);
iet first = iter.next();
let second = iter.next();
match (first, second) {
    (None, None) => Cow::from(""),
    (Some(s), None) => Cow::from(s),
    (Some(one), Some(two)) => {
        let mut result = [one, two].concat();
        for chunk in iter {
            result.push_str(chunk);
        }
        Cow::from(result)
    }
    (None, Some(_)) => panic!("something has gone terribly wrong"),
}

You might be able to come up with something more elegant than this, just trying to give a general idea. 👍

[cmyr]

fixed in #861