#errortolerance — Public Fediverse posts

Sigh... I guess I need to ask this now

So #rust programmers, how does one do errors in lossless parsing?

Context

I'm working on the new nu parser for nushell. The current strategy is to have a giant vector of so called NodeId s which in turn refer other indices within that vector, and ultimately build a parse "tree" using those NodeId (variants in the AstNode may contain other metadata too)

Now, we just created a dummy NodeId for errors and pushed them and continued to parse on our way. We want to have error-resilient parsing, so that we can cover more errors at other locations. If something's badly borked, well, we just barf.

So this worked well for us devs, because it kept things simple easy, but this is not how I'd really like to build the parse tree. There are multiple problems.

Right off the bat, we lose all the type information in one big ball of AstNode enum vector. So even though there are some places where you know that an AstNode would be of a particular kind, you simply cannot do anything about it except explicitly match and check (we want to avoid unsafe memory reinterprets).

As an aside, most of the enum is empty, but due to some variants, the entire enum becomes 48 bytes, so we waste a lot of memory on basically nothing.

My solution to this was to use bumpalo to do allocations and store references, and let go of the vector altogether and build an actual parse tree (like, a node with children, which have further children, and so on)

This is basically doing the vector, but not wasting space on the emptiness of the enums, not lose the types at runtime to the enum, and not have to do hacky index-chasing (which effectively act like pointers now). Instead, we use actual references, which we know will be valid till the end of the arena lifetime (three cheers for bumpalo!)

The Problem

As mentioned before, we had NodeId for errors as well, and those had a dummy span. Now, with the existence of a concrete parse tree, we have... no such thing. So we lose out on the ease of creating an error and attaching it wherever we want. In order to do things the earlier way, we have to make everything into an Result<insert_type_here, Error> which is very, very bad, because with that comes the indirect habit of using ? to bubble upwards, which is a problem because we want to find as big of a parsed expression with as small of an error context (we basically want to minimize how much we weren't able to parse, because that's what any good parser should do)

Right now, I don't really have any concrete ideas to attach errors to the nodes in the parse tree. So finally

Questions

• How does one do it? I'm looking for suggestions, although I don't really have anything concrete in my mind
• Would this actually lead to better performance? I expect it to be both faster and cheaper resource-wise. I'd argue yes, but I have no idea since it's a massive rewrite and doesn't even compile yet (:

Code snippets

// NOTE(bumpalo_rewrite): This becomes the root of the AST
// TODO(bumpalo_rewrite): Change to the generic enum that block may contain
#[derive(Debug, Clone)]
pub struct Block<'a> {
    pub span_start: usize,
    pub span_end: usize,
    pub nodes: Vec<BlockEntities<'a>>,
}

// TODO(bumpalo_rewrite): Fill with all the possible BlockEntities
// NOTE(bumpalo_rewrite): See Parser::block() for the entity types
#[derive(Debug, Clone)]
pub enum BlockEntities<'a> {
    Def(&'a Def<'a>),
    Let(&'a Let<'a>),
    While(&'a While<'a>),
    For(&'a For<'a>),
    Loop(&'a Loop<'a>),
    Return(&'a Return<'a>),
    Continue(&'a Continue),
    Break(&'a Break),
    Alias(&'a Alias),
    Extern(&'a Extern),
    PipelineOrExprOrAssign(PipelineOrExprOrAssign<'a>),
    Statement(PipelineOrExprOrAssign<'a>),
}

This is kind of what it is like right now. The function that parses a block:

            else if self.is_keyword(b"while") {
                match self.while_statement(arena) {
                    Some(while_) => {
                        code_body.push(BlockEntities::While(while_));
                    }
                    None => {}
                };
            }

has cases like these, where the error context is lost (ignore using Option instead of Result, I'm prototyping null

So really, how do I preserve the error contexts?

Git Repo

Here. You'd want to mostly look through the diff between this commit and the previous one in src/parser.rs

Any help is appreciated because I'm close to losing my mind lol XD

#programming #parsing #rust #errortolerance #compilers #parsers

Sigh... I guess I need to ask this now

So #rust programmers, how does one do errors in lossless parsing?

Context

I'm working on the new nu parser for nushell. The current strategy is to have a giant vector of so called NodeId s which in turn refer other indices within that vector, and ultimately build a parse "tree" using those NodeId (variants in the AstNode may contain other metadata too)

Now, we just created a dummy NodeId for errors and pushed them and continued to parse on our way. We want to have error-resilient parsing, so that we can cover more errors at other locations. If something's badly borked, well, we just barf.

So this worked well for us devs, because it kept things simple easy, but this is not how I'd really like to build the parse tree. There are multiple problems.

Right off the bat, we lose all the type information in one big ball of AstNode enum vector. So even though there are some places where you know that an AstNode would be of a particular kind, you simply cannot do anything about it except explicitly match and check (we want to avoid unsafe memory reinterprets).

As an aside, most of the enum is empty, but due to some variants, the entire enum becomes 48 bytes, so we waste a lot of memory on basically nothing.

My solution to this was to use bumpalo to do allocations and store references, and let go of the vector altogether and build an actual parse tree (like, a node with children, which have further children, and so on)

This is basically doing the vector, but not wasting space on the emptiness of the enums, not lose the types at runtime to the enum, and not have to do hacky index-chasing (which effectively act like pointers now). Instead, we use actual references, which we know will be valid till the end of the arena lifetime (three cheers for bumpalo!)

The Problem

As mentioned before, we had NodeId for errors as well, and those had a dummy span. Now, with the existence of a concrete parse tree, we have... no such thing. So we lose out on the ease of creating an error and attaching it wherever we want. In order to do things the earlier way, we have to make everything into an Result<insert_type_here, Error> which is very, very bad, because with that comes the indirect habit of using ? to bubble upwards, which is a problem because we want to find as big of a parsed expression with as small of an error context (we basically want to minimize how much we weren't able to parse, because that's what any good parser should do)

Right now, I don't really have any concrete ideas to attach errors to the nodes in the parse tree. So finally

Questions

• How does one do it? I'm looking for suggestions, although I don't really have anything concrete in my mind
• Would this actually lead to better performance? I expect it to be both faster and cheaper resource-wise. I'd argue yes, but I have no idea since it's a massive rewrite and doesn't even compile yet (:

Code snippets

// NOTE(bumpalo_rewrite): This becomes the root of the AST
// TODO(bumpalo_rewrite): Change to the generic enum that block may contain
#[derive(Debug, Clone)]
pub struct Block<'a> {
    pub span_start: usize,
    pub span_end: usize,
    pub nodes: Vec<BlockEntities<'a>>,
}

// TODO(bumpalo_rewrite): Fill with all the possible BlockEntities
// NOTE(bumpalo_rewrite): See Parser::block() for the entity types
#[derive(Debug, Clone)]
pub enum BlockEntities<'a> {
    Def(&'a Def<'a>),
    Let(&'a Let<'a>),
    While(&'a While<'a>),
    For(&'a For<'a>),
    Loop(&'a Loop<'a>),
    Return(&'a Return<'a>),
    Continue(&'a Continue),
    Break(&'a Break),
    Alias(&'a Alias),
    Extern(&'a Extern),
    PipelineOrExprOrAssign(PipelineOrExprOrAssign<'a>),
    Statement(PipelineOrExprOrAssign<'a>),
}

This is kind of what it is like right now. The function that parses a block:

            else if self.is_keyword(b"while") {
                match self.while_statement(arena) {
                    Some(while_) => {
                        code_body.push(BlockEntities::While(while_));
                    }
                    None => {}
                };
            }

has cases like these, where the error context is lost (ignore using Option instead of Result, I'm prototyping null

So really, how do I preserve the error contexts?

Git Repo

Here. You'd want to mostly look through the diff between this commit and the previous one in src/parser.rs

Any help is appreciated because I'm close to losing my mind lol XD

#programming #parsing #rust #errortolerance #compilers #parsers