Note: This post is part of a multipart series on building a LilyPond lexer/parser. The code, as it is being built throughout the series, can be found at https://github.com/gpit2286/broucku.

The scanner is done. It produces a flat, stateless stream of tokens. This set of tokens accounts for every byte of the source (whitespace and comments included). But before we start building out the parser, there are some design choices that need to be made to support the parser.

The parser, holistically

The lexer generates the tokens and the parser owns them. Parser::parse_all() calls Scanner::lex_all and stores the resulting vector. Nothing outside the parser module ever needs to hold those tokens. The AST will then be comprised of spans and not tokens. With these spans, if anything wants to look at the lexical structure, it can call Scanner::lex_range to get its information. (Think like maybe a formatter)

Unlike the lexer, which streams chars through an iterator, the parser keeps the entire Vec<Token> and points a cursor into it. That is mostly because I anticipate needing to look ahead and parse tokens speculatively. The cursor methods come in two pairs: bump and first skip trivia on the way, while bump_raw and first_raw do not. Skipping is lazy as the Whitespace and Comment tokens are still there, but the cursor simply does not stop on them.

As of now, we have no error handling, and I’m still trying to suss out how I want to handle it. My primary conflict is how large a scope the future error type lives in. The scanner produces a couple of errors: non-terminated strings and commands that have no symbol attached to them. But are those the same class of errors the parser will emit? If the parser reinterprets them, are the parser errors the same as what the AST reports downstream to consumers? A unified error system makes some of the process easier, but it also means one large error class. Smaller error groups that get reinterpreted mean more remapping.

Checkpoints for save scumming

Because the parser saves its place in the token array via an Option<usize> cursor, saving and restoring its place is fairly cheap. This lets the parser be more optimistic about trying parsing strategies, since re-trying is as simple as reapplying a saved state.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

pub struct Checkpoint {
    pos: Option<usize>,
    context_len: usize,
}

impl Parser {
    fn create_checkpoint(&self) -> Checkpoint {
        Checkpoint {
            pos: self.pos,
            context_len: self.context.len(),
        }
    }

    fn restore_checkpoint(&mut self, checkpoint: Checkpoint) {
        self.pos = checkpoint.pos;
        self.context.truncate(checkpoint.context_len);
    }
}

context_len stores the length of the parsing context stack which is the only state we need to keep track of other than the token position. Eventually, as the parser grows other state, more will be saved here. restore_checkpoint reverts everything a snapshot records. By funneling save and restore through these two functions, we (hopefully) close off whole areas of logical errors. Simple in theory.

The checkpoint’s behavior is pinned by unit tests in the same file. One resets the cursor from mid-stream back to None, another pushes contexts and restores them to the recorded length.

From 8-bit to 2D

One of the goals is to map these tokens to spans that will be represented in the AST. However, it’s fairly useless to downstream consumers without being able to position them in a document somehow. Everything from formatters to highlighters to error marking all depend on being able to accurately show someone where a span is. There is one major conflict in how this is done.

LilyPond reports positions in a 1-based system, while most consumers (e.g., an LSP) use a 0-based one. On top of that, the LSP spec expects positions in UTF-16 code units, and LilyPond produces its positions in raw bytes. Rather than pick one, we will provide both for now. Because both conventions can be computed in a single pass over the source, we get everything we need at once.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

pub struct LineIndex {
    line_starts: Vec<usize>,
    wide_chars: HashMap<u32, Vec<WideChar>>,
}

impl LineIndex {
    pub fn new(src: &str) -> LineIndex {
        let mut line_starts = vec![0];
        let mut wide_chars: HashMap<u32, Vec<WideChar>> = HashMap::new();
        let mut line = 0usize;
        let mut units_in_line = 0usize;

        for (i, c) in src.char_indices() {
            // Check if utf-16, utf-32
            if c.len_utf8() > 1 {
                // line in incremented every time we find an \n, so this will
                // contain the byte index of the start of the last line
                let start = i - line_starts[line];
                wide_chars.entry(line as u32).or_default().push(WideChar {
                    bytes: (start, start + c.len_utf8()),
                    units: (units_in_line, units_in_line + c.len_utf16()),
                });
            }
            // Record the position in terms of utf-16 as that's what the LSP
            // expects.
            units_in_line += c.len_utf16();
            if c == '\n' {
                // +1 as that will be the beginning of the line. i is the \n
                // and therefore the end of the line
                line_starts.push(i + 1);
                line += 1;
                units_in_line = 0;
            }
        }
        Self { line_starts, wide_chars }
    }

    fn line_of(&self, byte: usize) -> usize {
        // Lines are stored sorted so we can do a binary search
        match self.line_starts.binary_search(&byte) {
            // Exact match was found
            Ok(lno) => lno,
            // If not found, returns the idx where it could be inserted. So
            // take and subtract 1 to get the line. Saturating to prevent
            // underflow
            Err(lno) => lno.saturating_sub(1),
        }
    }

A lot of this is self-explanatory, but the wide-character handling is one place to dive into. One of the things to remember is that for programming languages, and markup languages for that matter, are mostly written in English. Because of this, they primarily us characters in the ASCII unicode space. So the guard checking for characters larger than 1 byte barely ever fires. For those lines the len_utf8() > 1 check is a cheap test that simply fails. But when it does detect a character wider than one byte, we add its position to the wide_chars table, which records the character’s raw byte range within its line and its width in UTF-16 code units. The byte offsets are relative to the start of the line and the unit counts are relative to all of the units seen in the line so far.

That leaves position reporting, which is done differently depending on which method you call.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

    /// Returns 0-based line and column of byte using utf-16 code units
    pub fn position_utf16(&self, byte: usize) -> Position {
        // find the line we're looking for
        let line = self.line_of(byte);
        // and then look at the byte # of the first char
        let line_start = self.line_starts[line];
        // This would be the character if we were guaranteed to not have any
        // wide chars. But we are not
        let byte_col = byte - line_start;
        let mut col = byte_col;
        if let Some(wides) = self.wide_chars.get(&(line as u32)) {
            for w in wides {
                // col will stagnate as we add wide_chars so we always need
                // to be comparing against the raw byte col and not where we
                // left off with the utf-16 coded column
                if w.bytes.1 <= byte_col {
                    col -= (w.bytes.1 - w.bytes.0) - (w.units.1 - w.units.0);
                } else {
                    break;
                }
            }
        }
        Position { line, col }
    }

    /// Returns 1-based line and column of raw bytes. Format is used in
    /// LilyPond
    pub fn position_byte(&self, byte: usize) -> Position {
        // Same logic as position_utf16.
        let line = self.line_of(byte);
        // and then look at the byte # of the first char
        let line_start = self.line_starts[line];
        Position {
            line: line + 1,
            col: byte - line_start + 1,
        }
    }
}

The context stack arrives

We also finally have to address the statefulness part of the LilyPond language. After going through the states in the Flex lexer, I have removed the states that were only there to set file metadata (filename, line number, version, etc.) After all of that, this is the list of the states that were left.

1
2
3
4
5
6
7
8
9

#[rustfmt::skip]
pub enum Context {
    Initial,    // output-def bodies: \paper, \midi, \layout
    Notes,      // startup & top level; \notemode, \with, embedded #{ ... #}
    Chords,     // \chordmode, \chords
    Lyrics,     // \lyricmode, \lyrics, \addlyrics
    Figures,    // \figuremode, \figures
    Markup,     // \markup, \markuplist
}

Now, one would incorrectly assume that we should start in the Initial context. The LilyPond parser actually starts in the Notes context, which is why a user can skip setting up a score and just write c4 to get a glorious quarter note C. As the flex lexer is being initialized, before the first token is scanned, the Notes state is pushed onto the stack. (lily-lexer.cc @129, @154)¹ The Notes context also covers top-level expressions and assignments.

This may lead you to believe that INITIAL is a blank canvas the designers never got around to using. It isn’t. The grammar switches to it in exactly one place, the output_def_head_with_mode_switch rule, for the bodies of the output definitions such as \paper, \midi, and \layout blocks. (parser.yy @1368) The name is a trap.

These output definitions are special because they can appear in many different places. Placed at the top level, an output definition applies its settings to all of the books and scores that follow. Placing header blocks before scores are a common example. There’s one more level of nuance to this as well.

Technically these output definitions can appear at the top level (parser.yy @507), inside \book (the paper_block reduction, parser.yy @1046), inside \bookpart (@1132), and inside \score (score_item, @1232). But the kinds are limited. A \paper block is explicitly disallowed inside \score (“use \layout instead”, parser.yy @1247). All of this to say, “it’s complicated.”

What is the point of it all?

The goal, after all of this, is a public entry point of pub fn parse_all(source: &str) -> Result<Document, ()>. Document will be the AST, and the () will eventually be a real error type. On the way to making that “work,” we have set up a system where we can walk tokens, remember our place, report positions with line numbers, and keep track of which context we are operating in. It parses nothing yet. The next part is where the grammar starts for real: pitch names and easily parsed grammars like durations.