Feedback on ParseElem::Element: Copy

[csnover]

Hello,

First, thanks for publishing this library. I’ve experimented with a few different libs in Rust for parsing text, and rust-peg is by far the best one I’ve tried.

The breaking change in 0.8 to require elements to be copyable is creating some extra complexity in a set of parsers I’ve written and I just wanted to describe my situation in case anything useful can come from it, either in showing me a better way, or else to have the constraint relaxed again.

I’m reimplementing a language parser that originally consisted of a hand-written lexer and Pratt (I think? I am very unknowledgeable here) parser. The lexer was used for a couple of totally different DSLs in the application, and to maximise compatibility and improve the clarity of implementation I am taking the same basic approach.

The problematic thing that the lexer does is transform multi-line string literals into single strings, which means that the Token type contains a Cow<'input, str> and cannot be Copy.

Right now as a stopgap solution I’m just creating a second Vec<&Token> and then have the parsers operate on that instead, which is not great.

At some point I was already planning to try making the lexer implement the Parse trait for some currently missing features, and I think that this may also solve the problem since backtracking should be limited enough that I think I can just store a small buffer of tokens and return references to them instead, but I haven’t tried doing this yet to know how difficult it will be, and I don’t know if this is a generalisable solution for everyone in a similar situation (though I also don’t know how frequently this ‘similar’ situation will be for anyone, since I don’t expect most parsers to have a separate lexer like this).

Thank you again for the library, and eager to hear feedback from your greater knowledge and experience.

Best,

[kevinmehall]

Thanks for the feedback!

The Copy bound is actually guiding you away from a performance pitfall you had unexpectedly stepped into: the previous implementation was actually cloning your Token every time the parser tested a match for any token with [] at that position. So if you had a large Cow::Owned string literal, it would have been allocating and dropping a String for any alternative tested at that position before it finally found the branch matching a string literal.

Instead of requiring Copy, one alternative I considered is making the ParseElem for [T] return &T instead of T. This would have been ideal for your use case, but for simpler types like [u8], passing around &u8 would have been awkward and potentially less performant.

The custom Parse + ParseElem impls are the best solution here. You don't have to go all the way to integrating it with the lexer; you could start with a simpler wrapper around your array that produces references instead of copies or clones:

use peg::{Parse, ParseElem, RuleResult};

pub struct SliceByRef<'a, T>(pub &'a [T]);

impl<'a , T> Parse for SliceByRef<'a, T> {
    type PositionRepr = usize;
    fn start(&self) -> usize {
        0
    }

    fn is_eof(&self, pos: usize) -> bool {
        pos >= self.0.len()
    }

    fn position_repr(&self, pos: usize) -> usize {
        pos
    }
}

impl<'a, T: 'a> ParseElem<'a> for SliceByRef<'a, T> {
    type Element = &'a T;

    fn parse_elem(&'a self, pos: usize) -> RuleResult<&'a T> {
        match self.0[pos..].first() {
            Some(c) => RuleResult::Matched(pos + 1, c),
            None => RuleResult::Failed,
        }
    }
}

Given that this happens in a trait impl, using a wrapper type is really the only way to choose an alternative implementation. Perhaps something like this wrapper should be included in the peg-runtime crate.

[csnover]

In my specific case, the use of multi-line strings is so rare and scripts so small that I don’t think (though haven’t profiled and have had bad intuition before about things like this :-)) it would have made much of a difference to the overall performance in practice, though I understand the rationale behind the change and appreciate the attention to keeping things fast.

Given how easily the wrapper solves the problem, I can’t think of any practical reason to remove the constraint right now. It makes sense to me to include the wrapper (+ impl ParseSlice) in the library as a documented alternative for parsing slices of non-Copyable objects (or even large copyable objects). The rationale regarding [u8] seems sound to me as well, since that is almost certainly going to be the most common non-str input type.

Just out of curiosity, is there a specific reason you used match self.0[pos..].first() instead of match self.0.get(pos) in the example code?

Thank you again!

[kevinmehall]

Just out of curiosity, is there a specific reason you used match self.0[pos..].first() instead of match self.0.get(pos) in the example code?

Nope, I think it was just based on the str implementation, which does self[pos..].chars().next() since the size of a UTF8 character is not fixed. get would be clearer here.