Recent searches
Search options
Administered by:
@janriemer@floss.socialMany people say that #Rust is very hard to #prototype with or to #refactor. This couldn't be further from the truth! It is the exact opposite!
Let me share with you one of the most profound experiences I had with #RustLang on a casual sunday - a thread 
I'm currently rewriting my #transpiler from #nom to #chumsky and until now everything has turned out great so far, until I've hit the following road block:
Implementing parsers by using #parser functions that have indirect #recursion.
1/11
With nom (at least for version 4.*, which I'm using) this hasn't been a problem, because parser functions are executed
_lazily_ (you don't actually _call_ your parser function, but rather provide it as a callback).
Of course, chumsky supports recursion, too, with its `recursive` function, but this only works for _direct_ recursion (afaik). With indirect recursion you run into infinite recursion, because you always have to _call_ your (`Parser`-returning) functions. Meh...
2/11
So what is the solution? Well, implement a new `recurse` primitive for chumsky that accepts functions returning `Parser`. ¯\_(ツ)_/¯
But wait...do you have any idea of the advanced type-trickery chumsky is doing under the hood!? What am I even thinking that I could possibly have the skills to navigate that code base! And then on top of that _recursion_!? - I'm too stupid for this!
3/11
So I've sat there in my chair for quite a while, starring at the screen, questioning my life-choices. Until the following thought crossed my mind: "Well, maybe I can just look at a simple combinator chumsky has to offer, like `padded_by`, just "copy" it, adapt it to accept callbacks and see if it compiles!?" So here we go...
4/11
Hm...so `OA` and `OB` seem to be outputs of the parser (gets more obvious, when looking at `then` combinator). We only need one output in our `recurse` primitive, so let's ignore that `OB` generic for now. `I` is for input to the parser and `E`...I'm not quite sure, but I think it is for attaching extra info to the parser (e.g. for error info).
Ok, let us carry the other generics with us, they seem to be important.
5/11
![pub struct PaddedBy<A, B, OB> {
pub(crate) parser: A,
pub(crate) padding: B,
#[allow(dead_code)]
pub(crate) phantom: EmptyPhantom<OB>,
}
impl<A: Copy, B: Copy, OB> Copy for PaddedBy<A, B, OB> {}
impl<A: Clone, B: Clone, OB> Clone for PaddedBy<A, B, OB> {
fn clone(&self) -> Self {
Self {
parser: self.parser.clone(),
padding: self.padding.clone(),
phantom: EmptyPhantom::new(),
}
}
}
impl<'a, I, E, A, B, OA, OB> ParserSealed<'a, I, OA, E> for PaddedBy<A, B, OB>
where
I: Input<'a>,
E: ParserExtra<'a, I>,
A: Parser<'a, I, OA, E>,
B: Parser<'a, I, OB, E>,
{
#[inline(always)]
fn go<M: Mode>(&self, inp: &mut InputRef<'a, '_, I, E>) -> PResult<M, OA> {
self.padding.go::<Check>(inp)?;
let a = self.parser.go::<M>(inp)?;
self.padding.go::<Check>(inp)?;
Ok(a)
}
go_extra!(OA);
}](https://cdn.masto.host/floss/media_attachments/files/112/151/751/650/583/812/original/6416ef3d2ce1067c.png "pub struct PaddedBy<A, B, OB> {
pub(crate) parser: A,
pub(crate) padding: B,
#[allow(dead_code)]
pub(crate) phantom: EmptyPhantom<OB>,
}
impl<A: Copy, B: Copy, OB> Copy for PaddedBy<A, B, OB> {}
impl<A: Clone, B: Clone, OB> Clone for PaddedBy<A, B, OB> {
fn clone(&self) -> Self {
Self {
parser: self.parser.clone(),
padding: self.padding.clone(),
phantom: EmptyPhantom::new(),
}
}
}
impl<'a, I, E, A, B, OA, OB> ParserSealed<'a, I, OA, E> for PaddedBy<A, B, OB>
where
I: Input<'a>,
E: ParserExtra<'a, I>,
A: Parser<'a, I, OA, E>,
B: Parser<'a, I, OB, E>,
{
#[inline(always)]
fn go<M: Mode>(&self, inp: &mut InputRef<'a, '_, I, E>) -> PResult<M, OA> {
self.padding.go::<Check>(inp)?;
let a = self.parser.go::<M>(inp)?;
self.padding.go::<Check>(inp)?;
Ok(a)
}
go_extra!(OA);
}")
![pub struct Recurse<F> {
parser_func: F,
}
impl<F: Copy> Copy for Recurse<F> {}
impl<F: Clone> Clone for Recurse<F> {
fn clone(&self) -> Self {
Self {
parser_func: self.parser_func.clone(),
}
}
}
impl<'a, I, E, F, A, OA> ParserSealed<'a, I, OA, E> for Recurse<F>
where
I: Input<'a>,
E: ParserExtra<'a, I>,
A: Parser<'a, I, OA, E>,
F: Fn() -> A,
{
#[inline(always)]
fn go<M: Mode>(&self, inp: &mut InputRef<'a, '_, I, E>) -> PResult<M, OA> {
let a = (self.parser_func)().go::<M>(inp)?;
Ok(M::map(a, |a: OA| a))
}
go_extra!(OA);
}](https://cdn.masto.host/floss/media_attachments/files/112/151/752/428/241/560/original/f046481a88780e95.png "pub struct Recurse<F> {
parser_func: F,
}
impl<F: Copy> Copy for Recurse<F> {}
impl<F: Clone> Clone for Recurse<F> {
fn clone(&self) -> Self {
Self {
parser_func: self.parser_func.clone(),
}
}
}
impl<'a, I, E, F, A, OA> ParserSealed<'a, I, OA, E> for Recurse<F>
where
I: Input<'a>,
E: ParserExtra<'a, I>,
A: Parser<'a, I, OA, E>,
F: Fn() -> A,
{
#[inline(always)]
fn go<M: Mode>(&self, inp: &mut InputRef<'a, '_, I, E>) -> PResult<M, OA> {
let a = (self.parser_func)().go::<M>(inp)?;
Ok(M::map(a, |a: OA| a))
}
go_extra!(OA);
}")
So this is now how our `recurse` primitive looks. And it compiles! Phew! But as you might know you shouldn't trust that comfy feeling until you actually _use_ your new API.
So let's do that (also note that there is nothing preventing us from using our new primitive in _non-recursive_ contexts, so let's do that first to start small).
Nice, it works!
6/11
Ok, now to the crucial part: Trying out our new primitive with _indirect recursion_. The exact grammar is not important here and doesn't make much sense, but this is a minimal example of a grammar with indirect recursion.
7/11
![Code, showing the AST types of this grammar that can be parsed with indirect recursion:
#[derive(Debug, Clone, PartialEq)]
enum PlusOrMinus {
Plus,
Minus,
Recursive(Box<SimpleExpr>),
}
#[derive(Debug, Clone, PartialEq)]
struct SimpleExpr {
dot: Dot,
plus_or_minus: Box<PlusOrMinus>,
}
#[derive(Debug, Clone, PartialEq)]
struct Dot;](https://cdn.masto.host/floss/media_attachments/files/112/151/778/907/277/016/original/e5b3310c1cd67ca2.png "Code, showing the AST types of this grammar that can be parsed with indirect recursion:
#[derive(Debug, Clone, PartialEq)]
enum PlusOrMinus {
Plus,
Minus,
Recursive(Box<SimpleExpr>),
}
#[derive(Debug, Clone, PartialEq)]
struct SimpleExpr {
dot: Dot,
plus_or_minus: Box<PlusOrMinus>,
}
#[derive(Debug, Clone, PartialEq)]
struct Dot;")
Aaaaaand...oh noooes, what in the name of Ferris is that!?
"error[E0275]: overflow evaluating the requirement `&str: chumsky::input::Input<'_>`".
Urgh, my brain hurts looking at this error. It's because our type gets infinitely large when the compiler tries to resolve it tries to resolve it tries to resolve it...
So we probably should just give up here... after all, we don't even know, whether our approach makes any sense, right!?
8/11
![A compiler error:
error[E0275]: overflow evaluating the requirement `&str: chumsky::input::Input<'_>`
|
= help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`selector`)
It tries to compile the following code:
fn simple_expr<'a>() -> impl Parser<'a, &'a str, SimpleExpr, extra::Err<Rich<'a, char>>> + Clone {
just('.')
.to(Dot)
.ignore_then(recurse(plus_or_minus))
.map(|test| SimpleExpr {
dot: Dot,
plus_or_minus: Box::new(test),
})
}
fn plus_or_minus<'a>() -> impl Parser<'a, &'a str, PlusOrMinus, extra::Err<Rich<'a, char>>> + Clone
{
just('+')
.padded()
.to(PlusOrMinus::Plus)
.or(just('-').padded().to(PlusOrMinus::Minus))
.or(recurse(simple_expr).map(|s| PlusOrMinus::Recursive(Box::new(s))))
}](https://cdn.masto.host/floss/media_attachments/files/112/151/787/329/934/871/original/0fc9c66a9e0efb64.png "A compiler error:
error[E0275]: overflow evaluating the requirement `&str: chumsky::input::Input<'_>`
|
= help: consider increasing the recursion limit by adding a `#![recursion_limit = \"256\"]` attribute to your crate (`selector`)
It tries to compile the following code:
fn simple_expr<'a>() -> impl Parser<'a, &'a str, SimpleExpr, extra::Err<Rich<'a, char>>> + Clone {
just('.')
.to(Dot)
.ignore_then(recurse(plus_or_minus))
.map(|test| SimpleExpr {
dot: Dot,
plus_or_minus: Box::new(test),
})
}
fn plus_or_minus<'a>() -> impl Parser<'a, &'a str, PlusOrMinus, extra::Err<Rich<'a, char>>> + Clone
{
just('+')
.padded()
.to(PlusOrMinus::Plus)
.or(just('-').padded().to(PlusOrMinus::Minus))
.or(recurse(simple_expr).map(|s| PlusOrMinus::Recursive(Box::new(s))))
}")
Ok, let me try one more thing: my intuition tells me that we need to break the cycle with a level of indirection. I also remember that e.g. you need to (Pin-)`Box` your async function when called recursively. So what happens if we put our parser in a `Box` by calling chumsky's `boxed()`?
Hoooraayy! It compiles! And you know the saying in Rust "if it compiles it works", right!? So does it work?
Well, passing tests don't lie, do they!? 
9/11
![The actual test:
#[test]
fn works() {
let actual = plus_or_minus().parse(".. +").into_output();
let expected = PlusOrMinus::Recursive(Box::new(SimpleExpr {
dot: Dot,
plus_or_minus: Box::new(PlusOrMinus::Recursive(Box::new(SimpleExpr {
dot: Dot,
plus_or_minus: Box::new(PlusOrMinus::Plus),
}))),
}));
assert_eq!(actual, expected.into())
}](https://cdn.masto.host/floss/media_attachments/files/112/151/823/357/778/591/original/f505d6a7996c1bb7.png "The actual test:
#[test]
fn works() {
let actual = plus_or_minus().parse(\".. +\").into_output();
let expected = PlusOrMinus::Recursive(Box::new(SimpleExpr {
dot: Dot,
plus_or_minus: Box::new(PlusOrMinus::Recursive(Box::new(SimpleExpr {
dot: Dot,
plus_or_minus: Box::new(PlusOrMinus::Plus),
}))),
}));
assert_eq!(actual, expected.into())
}")
So what should this all tell you? It should tell you that:
- #Rust enables fearless prototyping, refactoring and maintenance of software
- you shouldn't be afraid of stepping into the unknown
- despite seeming very scary at first, #chumsky is more approachable than you might think - thank you to chumsky contributors for such an amazing crate!
10/11
Don't believe those that say "Rust will slow you down" or "Rust is bad for prototyping". I can guarantee you in almost any other language the above story would have ended up in countless hours of tracking down exceptions and weird behavior and very likely me _giving up entirely_, because I _wasn't even sure at the beginning if this could work or not_.
11/11
@janriemer
My general opinion when someone says something in programming "slows you down" is that it actually slows down your speed of typing code, not the speed of getting something ready.
When you type less and think more you make less mistakes and complete tasks faster.
@heikkiket Absolutely THIS! 
@heikkiket @janriemer also works in reverse... "code^H^H^H^Htype 55% faster with copilot"
> [...] when the compiler tries to resolve it tries to resolve it tries to resolve it...
I chuckled 
@fritschy Haha, thank you!
@janriemer also, in light of your thread; you are absolutely right!
I did have arguments with colleagues that wrote poorly typed code, in order to "get it done quickly" because Rust's type system "slows you down"... they also did not come around, but ultimately a management decision was made 
@fritschy Yes, it's always the same: taking shortcuts _will_ bite you some time in the future.
I often experience this with unit tests as well: nah, we don't really need a unit test for _that_ case...we already have enough.
*2 month later* "Houston, we have a problem".