Support integration with cstree

[zesterer]

With the eventual merge of #82, it might be possible to have chumsky integrate with cstree, a library for lossless parsing using untyped syntax tree. This might be achieved by allowing implementers of the Input trait to specify functions that should be run when sequences of the input are consumed by the parser. For a dedicated Input implementation (that wraps another internally) we could specify these functions, allowing the emission of parse events.

[zesterer]

This is probably possible with zero-copy, but it's not on the roadmap for release.

[robo9k]

What does zero-copy refer to (a Git branch?), the mentioned pull request has been merged already?
Are we talking about InputRef (not Input) here and if so, how would that work given it's not a trait?
What would chumsky's role be; parse input (possibly from a separate lexer) and output .. events to construct a cstree CST?

[CraftSpider]

zero-copy used to be a git branch, but has since been merged and is now the main branch of the repository, anything after 1.0.0-alpha.1 is zero-copy.

Most likely this would involve both Input and InputRef - InputRef would gain methods that the parsers call, that it delegates to implementors of the Input trait (or possible a new sub-trait of it, similar to SliceInput or ValueInput, if I understand the original idea correctly.

I can't answer this one as zesterer, but personally, that sounds about right, given my limited knowledge of cstree.

[zesterer]

Yep, that's about right: we'd expand the input traits to allow collecting 'parsing events'. For most imputs, this would just be a stub that does nothing, allowing the optimiser to swallow the overhead. For a cstree input, these parsing events could be consumed by cstree's node builder and used to track token inputs.

Unfortunately I don't have the time to put together a proof of concept for this at the moment, but it probably wouldn't be the most difficult thing in the world to do (for those that understand how cstree works well).

[jyn514]

@zesterer helped me got something working that functions pretty well:

struct RowanNode_<'a, O, P: CSTParser<'a, O>> {
    parser: P,
    kind: SyntaxKind,
    _marker: PhantomData<(&'a str, fn() -> O)>,
}

type RowanNode<'a, O, P> = Ext<RowanNode_<'a, O, P>>;

/// This needs to be an extension, not a combinator using `map_with`, because map_with can be evaluated multiple times in the case of backtracking.
impl<'a, O, P: CSTParser<'a, O>> ExtParser<'a, &'a str, O, CSTExtra<'a>> for RowanNode_<'a, O, P> {
    fn parse(&self, inp: &mut InputRef<'a, '_, &'a str, CSTExtra<'a>>) -> Result<O, CSTError<'a>> {
        let checkpoint = inp.state().checkpoint();

        let output = inp.parse(&self.parser)?;
        let builder = inp.state();
        builder.start_node_at(checkpoint, self.kind.into());
        builder.finish_node();
        Ok(output)
    }

    fn check(&self, inp: &mut InputRef<'a, '_, &'a str, CSTExtra<'a>>) -> Result<(), CSTError<'a>> {
        let checkpoint = inp.state().checkpoint();

        inp.check(&self.parser)?;
        let builder = inp.state();
        builder.start_node_at(checkpoint, self.kind.into());
        builder.finish_node();
        Ok(())
    }
}

fn node<'a, O, P: CSTParser<'a, O>>(kind: SyntaxKind, parser: P) -> RowanNode<'a, O, P> {
    Ext(RowanNode_ {
        parser,
        kind,
        _marker: PhantomData,
    })
}

there also needs to be a combinator for tokens, but the general principle is working pretty well :)

the stuff with CSTParser is just because i didn't feel like making it more generic, it would be pretty easy to change. CSTExtra is kinda locked in because it needs the builder though, you'd need either that or yet another trait that gives you back &mut GreenNodeBuilder.

[zesterer]

Reopening since there's still need for a combinator for this, I think.