Xi-editor: [xi-rope][find][question] Allocations during multiline regex search are hurting performance.

[ngortheone]

@cmyr @raphlinus
I'm writing a parser for Org markup and I use xi-rope as underlying data structure.

There are numerous cases when I need to do a multilne regex search/match. Sometimes repeatedly. (Examples: poperty drawers are recognized by multiline regex)

In case of multiline regex search whole text of the rope is allocated into a temporary string.
https://github.com/xi-editor/xi-editor/blob/master/rust/rope/src/find.rs#L290

    if is_multiline_regex(pat) {
        // consume all of the text if regex is multi line matching
        text = Cow::from(String::from_iter(lines));
    } else {
        match lines.next() {
            Some(line) => text = line,
            _ => return None,
        }
    }

With big files and repeated multiline searches this really becomes a huge tax on performance.
I understand that this is due to the nature of the data structure at hand -the text stored in a set of chunks that are not connected to each other.

There are 2 questions I have:

• Is it possible to avoid/minimize allocations for multiline regex searches? I though about a buffer for storing allocated Cow::from(String::from_iter(lines)) to make it available for subsequent searches. But if I have to maintain a plain string alongside rope - what is the benefit of using a rope? That leads me to the next question
• Is rope a good fit for a parsing algorithm? I suspect that having simple &str would avoid any allocations altogether. And maybe I made a big mistake by using rope for a parser. In the beginning it seemed that having fast updates on the rope as user types would be a good thing to have. But now it seems that this benefit is negligible next to the allocation problem...
  I'd really appreciate your thoughts and comments.

[ngortheone]

I will post the essence of my conversation with @cmyr and @raphlinus on zulip chat.

This is a known downside of the Rope data structure. By being a non-contiguous data storage it is not directly compatible with existing tools like regex engine. Regex engine operates on String, so allocation to a contiguous memory area is necessary.

Possible workarounds:

• Do not use regexes
• Teach Regex engine how to work with non-contiguous data storage (rope is only one of many) using Cursor API for example

[cmyr]

@ngortheone Should we keep this open? It's not clear that it's really actionable for us at this point.

[ngortheone]

@cmyr I don't think this is actionable at the moment.
This question may come up again, so it is worth adding it to FAQ of some sort

[ngortheone]

I will leave this here for reference
https://github.com/rust-lang/regex/issues/425