Collecting into a pre-allocated collection

[jaen]

So, I've been trying to prototype a parallel parser for the ninja format that can parse big ninja files very fast and at the scale of files I'm testing it on, allocations start to matter quite a bit. So far it was a hand-written parser, but I've been looking at using something like Logos+Chumsky to make it more maintainable.

I tried to write an extension parser using the extension API, but it didn't seem to expose what I needed. In the end I've vendored chumsky into my prototype and added a few methods for that (e.g. collect_counted_into which allows you to count parsed element and allocate the collection yourself), which basically marks the input stream, run a parser once (either a .count() over the base parser or something user-specified if you have a simpler heuristic for knowing how many elements you needs, such as a count of =s only), pre-allocates the collection, reverts to the mark and runs the parser again, pushing the result into the collection, which is then returned as the parse result. It did improve parse times noticeably.

I've recently noticed #901 being merged and hoped that means I can finally write it as an extension parser, but it turns out it's not enough for that — iter_parser.iter_parse() accepts an Input not an InputRef (and I don't see way to coerce one into the other), while InputRef only has a parse, not parse_iter method.

Am I missing some option to do what I want? If not, would extending parser extensions to support such an use case be acceptable?

I suppose #509 is somewhat related, except I don't think it solves the counting part nicely (correct me if I'm wrong)?

[jaen]

Also, to parse the file in parallel, I was looking for statement boundaries and for each chunk found in that way, I constructed an iterator using parser.parse_iter(stream).unwrap(). Now, that the iterator is provided as an argument to the passed closure (with the lifetime apparently bound to the closure scope) I noticed I can't create the statement iterator like that anymore.

Is there any other way to do that now? Or should I do on a level above chumsky, always providing it a complete statement to parse?

[zesterer]

Is the problem you're seeing because the compiler believes that the input lifetimes don't match? If so, maybe Cache will help you here.

[jaen]

Hmm, I'm not sure leaning towards "probably no"? Basically I have a parser for ninja statements, and those are separated by unindented newlines, so for each chunk I wanted to create an iterator that would return statements parsed by statement_parser().separated_by(just(LogosToken::Newline)). This is the code that worked before the PR:

pub struct LazyStatementIterator<'a, S>
where
   S : ValueInput<'a, Token = LogosToken<'a>, Span = SimpleSpan>,
{
    stream: S,
    phantom: PhantomCovariantLifetime<'a>,
}

impl<'a, S> LazyStatementIterator<'a, S>
where
  S : ValueInput<'a, Token = LogosToken<'a>, Span = SimpleSpan>,
{
    pub fn new(input: &'a Chunk<'a>) -> impl Iterator<Item = PartialAst<'a>> {
        let lexer = LogosToken::lexer(input);

        let token_iter = lexer
            .spanned()
            .map(|(tok, span)| match tok {
                Ok(tok) => (tok, span.into()),
                Err(()) => (LogosToken::Error, span.into()),
            });

        let stream = IterInput::new(token_iter, SimpleSpan::from(input.len() .. input.len()));

        let parser = statement_parser().separated_by(just(LogosToken::Newline));

        parser.parse_iter(stream).unwrap()
    }
}

Now, I fully acknowledge I might've been doing something stupid using it that way (it's my first time using chumsky and also a throw-away prototype to see if it can work), but it seemed to work. And since the new API seems to expect me to handle the iterator only within the lifetime of the closure, I can't seem to be able to return it. If there is some fundamental reason for this restriction, then I think I can work around this just by giving chumsky only a single complete statement (I have to discover statement boundaries anyway to produce the chunks).

[zesterer]

I tried to write an extension parser using the extension API, but it didn't seem to expose what I needed

I assume, given your use-case, this is because you need the ability to run IterParsers with InputRef and not just regular Parsers? Or was there something else missing?

[jaen]

I think so? As far as I can tell from https://docs.rs/chumsky/latest/chumsky/extension/index.html I have only parse or check that provide InputRef, while the new iter_parser.iter_parse() interface accepts only Input, so I can't find a way to wire them together. Something like this, except inp is of the wrong type (sorry for the bounds noise, but that's what got the compiler to stop complaining about them):

pub struct CollectCountedInto<A, O, C, PCount, AllocF>
where 
    AllocF : Fn(usize) -> C,
{
    parser: A,
    counter_parser: PCount,
    allocate: AllocF,
    #[allow(dead_code)]
    phantom: PhantomData<(O, C)>,
}

pub trait ParserExt<'src, I, O, E>
where
    I: Input<'src>,
    E: extra::ParserExtra<'src, I>
{
    fn collect_counted<C>(self) -> CollectCountedInto<Self, O, C, Collect<Self, O, usize>, fn(usize) -> C>
    where
        Self: Sized + Clone + IterParser<'src, I, O, E>,
        C : Container<O>,
    {
        let counter_parser = self.clone().count();
        let allocate: fn(usize) -> C = Container::<O>::with_capacity; 

        CollectCountedInto {
            parser: self,
            counter_parser,
            allocate,
            phantom: PhantomData,
        }
    }
}

impl<'src, I, O, Ex, A, C, PCount, AllocF, E, S, Ctx> ExtParser<'src, I, C, Ex> for CollectCountedInto<A, O, C, PCount, AllocF>
where
    I: Input<'src>,
    Ex: ParserExtra<'src, I, Error = E, State = S, Context = Ctx>,
    E: Error<'src, I>,
    S: Inspector<'src, I>,
    Ctx: 'src,
    A: IterParser<'src, I, O, Ex>,
    C: Container<O>,
    PCount: Parser<'src, I, usize, Ex>,
    AllocF : Fn(usize) -> C + Clone,
{
    fn parse(&self, inp: &mut InputRef<'src, '_, I, Ex>) -> Result<C, Ex::Error> {
        let checkpoint = inp.save();

        let count = inp.parse(self.counter_parser)?;

        let mut container: C = (self.allocate)(123);

        inp.rewind(checkpoint);

        self.parser.parse_iter(inp, |iter| iter.for_each(|item| container.push(item)));

        Ok(container)
    }
}

If it helps to make it clear what I tried to achieve, here's how I hacked it together inside the codebase, not as an extension — https://gist.github.com/jaen/342d2ce0987bd48a1b7b4e328de81f7f.