I am trying to implement some parsing combinators. Each parser combinator is a mutable closure but outside code refers to each combinator as a trait that provides a blanket implementation for calling the combinator function.
// Region of external code, CANNOT modify
type ParseResult<I, T> = Result<(I, T), String>;
trait Parser<T> {
fn parse<'a>(&mut self, input: &'a str) -> ParseResult<&'a str, T>;
}
// Blanket implementation for parser combinators
impl<F, T> Parser<T> for F
where F: FnMut(&str) -> ParseResult<&str, T> {
fn parse<'a>(&mut self, input: &'a str) -> ParseResult<&'a str, T> {
self(input)
}
}
// Example of an external combinator
fn external_combinator<P, T>(parser: P) -> impl FnMut(&str) -> ParseResult<&str, T>
where P: Parser<T> {
preceded_by(char_parser('a'), parser)
}
// My code begins here
fn char_parser(c: char) -> impl Fn(&str) -> ParseResult<&str, char> {
move |input: &str| {
let Some(rest) = input.strip_prefix(c) else {
return Err(format!("Input does not begin with {c}"));
};
Ok((rest, c))
}
}
fn delimited_by<Extracted>(
begin_char: char,
final_char: char,
mut parser: impl Parser<Extracted>
) -> impl FnMut(&str) -> ParseResult<&str, Extracted> {
move |input: &str| {
let parse_begin = char_parser(begin_char);
// Why cannot I move parser to preceded_by? <-- ERROR HERE
let precede = preceded_by(parse_begin, &mut parser);
let parse_final = char_parser(final_char);
followed_by(precede, parse_final)(input)
}
}
fn followed_by<Extracted, _Discard>(
mut parser_a: impl Parser<Extracted>,
mut parser_b: impl Parser<_Discard>
) -> impl FnMut(&str) -> ParseResult<&str, Extracted> {
move |input: &str| {
let (rest, new_value) = parser_a.parse(input)?;
let (rest, _) = parser_b.parse(rest)?;
Ok((rest, new_value))
}
}
fn preceded_by<Extracted, _Discard>(
mut parser_a: impl Parser<_Discard>,
mut parser_b: impl Parser<Extracted>
) -> impl FnMut(&str) -> ParseResult<&str, Extracted> {
move |input: &str| {
let (rest, _) = parser_a.parse(input)?;
parser_b.parse(rest)
}
}
// Region of external code, cannot modify
fn main() {
let my_combinator = delimited_by('a', 'b', char_parser('c'));
let mut final_combinator = external_combinator(my_combinator);
match final_combinator("data") {
Ok(_) => println!("OK"),
Err(_) => println!("Error")
}
}
When I try to compile this demo, I get the following errors.
error[E0277]: the trait bound `&mut impl Parser<Extracted>: Parser<_>` is not satisfied
--> src/main.rs:43:48
|
43 | let precede = preceded_by(parse_begin, &mut parser);
| ----------- ^^^^^^^^^^^ the trait `for<'a> FnMut(&'a str)` is not implemented for `impl Parser<Extracted>`, which is required by `&mut impl Parser<Extracted>: Parser<_>`
| |
| required by a bound introduced by this call
|
= note: required for `&mut impl Parser<Extracted>` to implement `for<'a> FnOnce(&'a str)`
note: required for `&mut impl Parser<Extracted>` to implement `Parser<_>`
--> src/main.rs:10:12
|
10 | impl<F, T> Parser<T> for F
| ^^^^^^^^^ ^
11 | where F: FnMut(&str) -> ParseResult<&str, T> {
| -------------------- unsatisfied trait bound introduced here
note: required by a bound in `preceded_by`
--> src/main.rs:63:24
|
61 | fn preceded_by<Extracted, _Discard>(
| ----------- required by a bound in this function
62 | mut parser_a: impl Parser<_Discard>,
63 | mut parser_b: impl Parser<Extracted>
| ^^^^^^^^^^^^^^^^^ required by this bound in `preceded_by`
help: consider further restricting this bound
|
37 | mut parser: impl Parser<Extracted> + for<'a> FnMut(&'a str)
| ++++++++++++++++++++++++
I tried applying + for<'a> FnMut(&'a str) but it leads to more errors and in the end the compiler wants me to change the Parser<T> but I cannot do that because in production Parser<T> is provided by an external code.
I have a few questions:
parser from delimited_by to preceded_by without using dyn or Box?external_combinator? Remember, I can't change the signature or the implementation of anything in the external region.parser, please post it, that would be helpful too.I'll start with a solution that only involves the type of small fixes that result from addressing specific compiler errors.
First, note that, in delimited_by, &mut (impl SomeTrait) does not implement SomeTrait. Our first modification is to remove mut and &mut:
fn delimited_by<Extracted>(
begin_char: char,
final_char: char,
parser: impl Parser<Extracted> // removed mut
) -> impl FnMut(&str) -> ParseResult<&str, Extracted> {
move |input: &str| {
let parse_begin = char_parser(begin_char);
let precede = preceded_by(parse_begin, parser); // removed &mut
let parse_final = char_parser(final_char);
followed_by(precede, parse_final)(input)
}
}
Now, we encounter a second problem. When a function takes impl SomeTrait, in this case impl Parser<Extracted>, Rust defaults to assuming no extra traits like Copy or Clone. This means that parser cannot be implicitly or explicitly duplicated, respectively. However, since delimited_by returns a closure that needs parser every time it executes, we do need multiple copies or clones of parser.
We can add a Clone bound to the argument, allowing us to clone it each time the closure runs. We must also explicitly say that char_parser returns a Cloneable function.
fn char_parser(c: char) -> impl Fn(&str) -> ParseResult<&str, char> + Clone // Added Clone {
move |input: &str| {
let Some(rest) = input.strip_prefix(c) else {
return Err(format!("Input does not begin with {c}"));
};
Ok((rest, c))
}
}
fn delimited_by<Extracted>(
begin_char: char,
final_char: char,
parser: impl Parser<Extracted> + Clone // Added Clone
) -> impl FnMut(&str) -> ParseResult<&str, Extracted> {
move |input: &str| {
let parse_begin = char_parser(begin_char);
let precede = preceded_by(parse_begin, parser.clone()); // Added clone
let parse_final = char_parser(final_char);
followed_by(precede, parse_final)(input)
}
}
If you run final_combinator on "aacb", it parses!
Here is a solution that is more efficient, and doesn't require Clone. It accomplishes this by building the parsing machinery outside the repeatedly-executing closure:
fn delimited_by<Extracted>(
begin_char: char,
final_char: char,
parser: impl Parser<Extracted>
) -> impl FnMut(&str) -> ParseResult<&str, Extracted> {
let parse_begin = char_parser(begin_char);
let precede = preceded_by(parse_begin, parser);
let parse_final = char_parser(final_char);
let mut parser = followed_by(precede, parse_final);
move |input: &str| {
parser(input)
}
}
This can be abbreviated by factoring out the closure:
fn delimited_by<Extracted>(
begin_char: char,
final_char: char,
parser: impl Parser<Extracted>
) -> impl FnMut(&str) -> ParseResult<&str, Extracted> {
let parse_begin = char_parser(begin_char);
let precede = preceded_by(parse_begin, parser);
let parse_final = char_parser(final_char);
followed_by(precede, parse_final)
}