Feature request: pipelined parsers

[Banyc]

Say we have the two parsers:

• fn lexer() -> impl Parser<char, Vec<Token>, Error = Simple<char>>;
• fn token_parser() -> impl Parser<Token, Expr, Error = Simple<Token>>;

Feature request

A way to merge the two parsers as one.

let parser = token_parser().inputed_from(lexer());
parser.parse(src)

Potential benefits

• Prevent the creation of Vec<Token> which takes up a bit of heap memory, so that it makes inter-procedures zero-copy.
• parser.parse(src) seems cooler than let tokens = lexer.parse(src); token_parser.parse(tokens) in user code. By "users" I mean those who use the built parser(s).

My questions

1. Is it possible to do this with current implementations?
2. Is the idea makes sense to most use cases so that it worths being implemented?

[Banyc]

Btw, thank you for making this project and the Veloren game, which make my at-work and off-work hours easier/happier. Also the tutorials of the two projects are great!

[zesterer]

This seems like a reasonable extension of the existing API. There is one problem I have with it though, and it's the one that's stalled the stabilisation of ParserIter: it's not clear how to deal with errors that occur. ParserIter treats an error as the end of the stream, but this isn't quite right. If something like this were to appear, we'd need a way to account for:

1. Errors generated by the inner parser: how do they get propagated or accounted for?

2. Ambiguity in the inner parser: what happens if there are two possible routes for the inner parser to take? Can a backtracing outer parser case an inner parser to also backtrace?

I'm interested to know your thoughts.

[Banyc]

I haven't fully look into ParserIter nor got the full picture on the Rust ecosystem so I am probably wrong, but I have some idea on the first one:

1. I want to mathematically reduce the next calling chain into something like this:

         /    /
        /    /
   ---->|-+->|-+
        | |  | |
   <----|-+  | |
        |    | |
   <----|----|-+
        \    \
         \    \
   

   • Each layer is a next call
2. tower::Service can also be reduced into this model
3. tower::Service takes a Request as input and Response as output. Error type is usually Box<dyn Error>
   • the official guide recommends to use Box<dyn Error> as the propagating error type
   • the guide reasons about why to do so
4. Therefore, it might be a good idea to Box<dyn std::error::Error> the error

[zesterer]

In your diagram, what do those distinct outflows represent? Would errors from the inner parser (i.e: the lexer, in most cases) get propagated up to become parser errors?

[Banyc]

       /     /
      /     /
----->|-+-->|-+
      | |   | |
<----1|-+   | |
      |     | |
<----2|----3|-+
      \     \
       \     \

• note 3 has the output type: Result<InnerResponse, Error>
  • Error is Box<dyn std::error::Error>
  • If the inner is a lexer, then:
    • InnerResponse will be a Token
• note 1 and 2 share the same type: Result<OuterResponse, Error>
  • If the outer is a expr-parser, then:
    • OuterResponse will be a Expr
  • Error is also Box<dyn std::error::Error> so that it can propagate the inner error while still be able to carry the outer error
    • the inner error could be a LexerError that can be converted into std::error::Error
    • the outer error could be a ParserError that can be converted into std::error::Error
• Sometimes the outer parser might call the inner parser several times, but the outer can just early returns the error if any of the call returns an error.

[zesterer]

The difficulty here, I think, is that you can't simply model a parser as if it were a function like fn(&str) -> Result<T, Error>. Parsers also track intermediate errors, memoisation state, and a bunch of other things that make conjoining them in this way non-trivial. I'll do some thinking about to what extent this could work, but it seems complex enough that it might not be worth implementing for the initial 1.0 release.

[TzviPM]

@zesterer is there an issue tracking a more reasonable API for iterator / stream parsers? I have a few ideas, but I especially like the two concepts together:

1. streaming parsers that emit error objects and continue parsing
2. chaining parsers together

In particular, I'd like to be able to have a lexer emit an error and then add contextual information to that error from the parser. Moreover, this could make error spans easier, because we could provide spans from the lexer in a way that removes the parser's need to re-compute source spans from token spans.

[zesterer]

There is not. I have had some ideas about this recently though. Here's a link to my spitballing on Discord about this (you'll need to be a member of the Rust Community Discord). I'll try to translate them into a less obtuse format tomorrow when I'm less tired. Also see #425.

[cosmicexplorer]

I don't have an answer to this yet:

streaming parsers that emit error objects and continue parsing

but before I was aware of that issue, I created #513, which proposes an API for:

chaining parsers together

consisting of a .stream(input) method which accepts an Input and produces a Stream of the output of the parser, which can be piped into another parser:

use chumsky::{prelude::*, text::ident, input::{Stream, ValueInput}};

#[derive(Copy, Clone, Eq, PartialEq)]
enum Token<'a> {
  Comma,
  Symbol(&'a str),
}

fn tokenize<'a>() -> impl Parser<'a, &'a str, Token<'a>> {
  choice((
    just(',').to(Token::Comma),
    ident().map(Token::Symbol),
  ))
}

#[derive(PartialEq, Eq, Debug)]
struct SymbolList<'a> {
  pub symbols: Vec<&'a str>,
}

fn list<'a, I>() -> impl Parser<'a, I, SymbolList<'a>>
where I: ValueInput<'a, Token=Token<'a>, Span=SimpleSpan> {
  fn symbol<'a, I>() -> impl Parser<'a, I, &'a str>
  where I: ValueInput<'a, Token=Token<'a>, Span=SimpleSpan> {
    select! {
      Token::Symbol(name) => name,
    }
  }

  let comma = select! { Token::Comma => () };

  symbol()
    .then(comma.ignore_then(symbol()).repeated().collect::<Vec<_>>())
    .map(|(head, tail)| SymbolList {
      symbols: vec![head].into_iter().chain(tail.into_iter()).collect(),
    })
}

let input = "a,bb,asdfe";
let token_stream = tokenize().repeated().stream(input).into_result().unwrap();
let result = list().parse(token_stream).into_result().unwrap();
assert_eq!(result, SymbolList { symbols: vec!["a", "bb", "asdfe"] });

I'm going to consider how to extend IterParser as @zesterer described such that we don't drop parse errors from the first parse in the pipeline, but wanted to know how others thought of that general API.

[zesterer]

Apologies, I was going to reply to this but have had a very mentally and emotionally taxing month (a close family member passed away).

I like this API in general. I am somewhat worried about the conflation between input::Stream and the stream method though, given that they appear to do slightly different things. That said, I think the thing to rename is the existing Stream, perhaps to IterInput or something.

In terms of implementation, I think that making an IterParser into an Input is probably possible, but - due to the way errors would need to be communicated between the initial parser and the consuming parser - might not be possible through the Input trait. I'm wondering whether this might actually be call for a slightly different API? Something like this:

tokenizer().repeated()
    .ingested_by(list())
    .parse(input)

(i.e: IngestedBy would have the input type of tokenizer().repeated() but the output type of list(). It would also require both parsers to emit the same error type)

I think ingested_by kind of sucks as a name, but I think it more readily communicates the idea of an IterParser's outputs acting as the basis for another parser's input.