A ‘marker’ is an abstraction over Rowan that makes working with it nicer, and also allows for some fancier parsing techniques. You can think of them as a fancy version of the checkpoints we’ve been using up to this point. Here’s a rough sketch of the API we’ll create:
impl Parser {
fn start(&mut self) -> Marker;
}
struct Marker { ... }
impl Marker {
fn complete(self, p: &mut Parser, kind: SyntaxKind) -> CompletedMarker;
}
struct CompletedMarker { ... }
impl CompletedMarker {
fn precede(self, p: &mut Parser) -> Marker;
}
Additionally, we will ensure that Marker panics if it has been dropped without being completed.
Parser::start creates a new marker at the parser’s current position. After creating a marker, we can bump tokens and start new nodes as normal; once we’re done we call complete on the marker, which wraps, in a SyntaxKind of our choice, all the tokens and nodes added since the marker’s creation.
Markers’ property of panicking if they haven’t been completed is one of the benefits they have over plain Parser::start_node and finish_node calls. If you forget to call finish_node you get a panic with a cryptic message from Rowan. If you forget to complete a marker, though, you instead get a clearer panic message with a backtrace that tells you where the marker was dropped.1
If we later decide that we really should have wrapped that node in another node, we can call precede on the CompletedMarker that Marker::complete returned to us. This precede method gives us a marker, meaning that we can once again add to the syntax tree and later call Marker::complete.
Note that the existence of Marker means that we won’t need Parser::start_node or finish_node; we can just create markers and complete them later. Similarly, CompletedMarker supersedes Parser::checkpoint and Parser::start_node_at.
Let’s begin by writing an implementation of Parser::start:
// parser.rs
impl<'l, 'input> Parser<'l, 'input> {
// snip
fn start(&mut self) -> Marker {
let pos = self.events.len();
Marker::new(pos)
}
// snip
}
Let’s define Marker:
mod event;
mod expr;
mod marker;
mod sink;
mod source;
use crate::lexer::{Lexeme, Lexer, SyntaxKind};
use crate::syntax::SyntaxNode;
use event::Event;
use expr::expr;
use marker::Marker;
use rowan::GreenNode;
use sink::Sink;
use source::Source;
// src/parser/marker.rs
pub(super) struct Marker {
pos: usize,
}
impl Marker {
pub(super) fn new(pos: usize) -> Self {
Self { pos }
}
}
The next step is to define Marker::complete. Remember that what this does is wrap, in a given SyntaxKind, all the nodes and tokens pushed to the syntax tree since the marker was instantiated. We could use Vec::insert to insert the appropriate Event::StartNode event at the marker’s position; this would throw off the positions of other markers. The solution is to add a ‘placeholder’ variant to Event that we push when the marker is created. When Marker::complete is called we can then replace this placeholder with the real StartNode event, and then finish the node:
// event.rs
#[derive(Debug, Clone, PartialEq)]
pub(super) enum Event {
StartNode { kind: SyntaxKind },
StartNodeAt { kind: SyntaxKind, checkpoint: usize },
AddToken { kind: SyntaxKind, text: SmolStr },
FinishNode,
Placeholder,
}
// parser.rs
impl<'l, 'input> Parser<'l, 'input> {
// snip
fn start(&mut self) -> Marker {
let pos = self.events.len();
self.events.push(Event::Placeholder);
Marker::new(pos)
}
// snip
}
// marker.rs
use super::event::Event;
use super::Parser;
use crate::lexer::SyntaxKind;
// snip
impl Marker {
// snip
// we aren’t making this method return a CompletedMarker just yet ...
pub(super) fn complete(self, p: &mut Parser, kind: SyntaxKind) {
let event_at_pos = &mut p.events[self.pos];
assert_eq!(*event_at_pos, Event::Placeholder);
*event_at_pos = Event::StartNode { kind };
p.events.push(Event::FinishNode);
}
}
Note how we include a sanity check to ensure the event we’re changing is a placeholder, allowing us to catch bugs earlier.
We have to tell the sink what to do if it encounters a placeholder event; this should never happen (they should all be removed by Marker::complete):
// sink.rs
impl<'l, 'input> Sink<'l, 'input> {
// snip
pub(super) fn finish(mut self) -> GreenNode {
// snip
for event in reordered_events {
match event {
Event::StartNode { kind } => {
// snip
}
Event::StartNodeAt { .. } => unreachable!(),
Event::AddToken { kind, text } => self.token(kind, text),
Event::FinishNode => self.builder.finish_node(),
Event::Placeholder => unreachable!(),
}
self.eat_trivia();
}
self.builder.finish()
}
// snip
}
Let’s ensure that markers are never accidentally dropped without being completed:
// marker.rs
pub(super) struct Marker {
pos: usize,
completed: bool,
}
impl Marker {
pub(super) fn new(pos: usize) -> Self {
Self {
pos,
completed: false,
}
}
pub(super) fn complete(mut self, p: &mut Parser, kind: SyntaxKind) {
self.completed = true;
let event_at_pos = &mut p.events[self.pos];
assert_eq!(*event_at_pos, Event::Placeholder);
*event_at_pos = Event::StartNode { kind };
p.events.push(Event::FinishNode);
}
}
impl Drop for Marker {
fn drop(&mut self) {
if !self.completed {
panic!("Markers need to be completed");
}
}
}
It’s annoying to have to maintain that boolean though; let’s use the drop_bomb crate to handle this for us:
# Cargo.toml
[dependencies]
drop_bomb = "0.1.5"
logos = "0.11.4"
num-derive = "0.3.3"
num-traits = "0.2.14"
rowan = "0.10.0"
// marker.rs
use super::event::Event;
use super::Parser;
use crate::lexer::SyntaxKind;
use drop_bomb::DropBomb;
pub(super) struct Marker {
pos: usize,
bomb: DropBomb,
}
impl Marker {
pub(super) fn new(pos: usize) -> Self {
Self {
pos,
bomb: DropBomb::new("Markers need to be completed"),
}
}
pub(super) fn complete(mut self, p: &mut Parser, kind: SyntaxKind) {
self.bomb.defuse();
let event_at_pos = &mut p.events[self.pos];
assert_eq!(*event_at_pos, Event::Placeholder);
*event_at_pos = Event::StartNode { kind };
p.events.push(Event::FinishNode);
}
}
DropBomb panics when it’s dropped unless its defuse method has been called.
Let’s try out our new marker support by replacing the usage of Parser::start_node in Parser::parse with markers:
// parser.rs
impl<'l, 'input> Parser<'l, 'input> {
// snip
fn parse(mut self) -> Vec<Event> {
let m = self.start();
expr(&mut self);
m.complete(&mut self, SyntaxKind::Root);
self.events
}
// snip
}
$ cargo t -q
running 35 tests
...................................
test result: ok. 35 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
It’s now time to remove our usage of checkpoints and transition to using precede on CompletedMarker. Fortunately for us there’s only one place where we use checkpoints: expr_binding_power. The first modification we need to make is to store a CompletedMarker of the the left-hand side of the binary expression, so that we can later call precede on it:
// expr.rs
fn expr_binding_power(p: &mut Parser, minimum_binding_power: u8) {
let lhs = match p.peek() {
Some(SyntaxKind::Number) | Some(SyntaxKind::Ident) => p.bump(),
Some(SyntaxKind::Minus) => {
let op = PrefixOp::Neg;
let ((), right_binding_power) = op.binding_power();
// Eat the operator’s token.
p.bump();
p.start_node_at(checkpoint, SyntaxKind::PrefixExpr);
expr_binding_power(p, right_binding_power);
p.finish_node();
}
Some(SyntaxKind::LParen) => {
p.bump();
expr_binding_power(p, 0);
assert_eq!(p.peek(), Some(SyntaxKind::RParen));
p.bump();
}
_ => return, // we’ll handle errors later.
};
// snip
}
None of the match’s arms have the type CompletedMarker, though. Remember that we can only obtain a CompletedMarker by completing a marker (what a surprise!); thus, it stands to reason that we have to both create a marker and complete it in each arm of the match. Each of the things we parse into lhs need their own SyntaxKind:
// lexer.rs
pub(crate) enum SyntaxKind {
// snip
Root,
BinaryExpr,
Literal,
ParenExpr,
PrefixExpr,
VariableRef,
}
We can now make lhs a CompletedMarker:
// expr.rs
fn expr_binding_power(p: &mut Parser, minimum_binding_power: u8) {
let lhs = match p.peek() {
Some(SyntaxKind::Number) => {
let m = p.start();
p.bump();
m.complete(p, SyntaxKind::Literal)
}
Some(SyntaxKind::Ident) => {
let m = p.start();
p.bump();
m.complete(p, SyntaxKind::VariableRef)
}
Some(SyntaxKind::Minus) => {
let m = p.start();
let op = PrefixOp::Neg;
let ((), right_binding_power) = op.binding_power();
// Eat the operator’s token.
p.bump();
expr_binding_power(p, right_binding_power);
m.complete(p, SyntaxKind::PrefixExpr)
}
Some(SyntaxKind::LParen) => {
let m = p.start();
p.bump();
expr_binding_power(p, 0);
assert_eq!(p.peek(), Some(SyntaxKind::RParen));
p.bump();
m.complete(p, SyntaxKind::ParenExpr)
}
_ => return, // we’ll handle errors later.
};
// snip
}
Let’s make use of lhs and eradicate the last remaining reference to checkpoints in expr_binding_power. We’ll do this by calling precede on lhs before recursing, giving us a marker we can complete afterwards:
fn expr_binding_power(p: &mut Parser, minimum_binding_power: u8) {
let mut lhs = match p.peek() {
// snip
};
loop {
let op = match p.peek() {
Some(SyntaxKind::Plus) => InfixOp::Add,
Some(SyntaxKind::Minus) => InfixOp::Sub,
Some(SyntaxKind::Star) => InfixOp::Mul,
Some(SyntaxKind::Slash) => InfixOp::Div,
_ => return, // we’ll handle errors later.
};
let (left_binding_power, right_binding_power) = op.binding_power();
if left_binding_power < minimum_binding_power {
return;
}
// Eat the operator’s token.
p.bump();
let m = lhs.precede(p);
expr_binding_power(p, right_binding_power);
lhs = m.complete(p, SyntaxKind::BinaryExpr);
}
}
To make sure that we keep ‘wrapping around’ the expressions we’re parsing, we assign the result of completing the marker to lhs.
We haven’t implemented CompletedMarker, though, so lhs really has the type of () and precede isn’t defined. First, let’s make Marker::complete return a CompletedMarker:
// marker.rs
impl Marker {
// snip
pub(super) fn complete(mut self, p: &mut Parser, kind: SyntaxKind) -> CompletedMarker {
self.bomb.defuse();
let event_at_pos = &mut p.events[self.pos];
assert_eq!(*event_at_pos, Event::Placeholder);
*event_at_pos = Event::StartNode { kind };
p.events.push(Event::FinishNode);
CompletedMarker { pos: self.pos }
}
}
pub(super) struct CompletedMarker {
pos: usize,
}
The next missing piece is CompletedMarker::precede. Implementing this is tricky; let’s think about how we might approach this problem as we write out a skeleton:
impl CompletedMarker {
pub(super) fn precede(self, p: &mut Parser) -> Marker {
let new_m = p.start();
todo!();
new_m
}
}
We have the same problem as with Marker::complete; we can’t use Vec::insert or a similar method to shuffle around p.events, as that would invalidate the indices into events that other Markers and CompletedMarkers use.
The solution is ingenious: we add another field to Event::StartNode that stores a relative offset from that event forward to its parent. We modify the event at the CompletedMarker’s position so that its forward parent is the marker returned by precede. We can get this forward parent offset with new_m.pos - self.pos.
↓ this distance here is the first event’s forward_parent
/- Event::StartNode { kind: Foo } <- the event at which
| ... the marker was created
| ... blah blah more events
| ...
\- Event::StartNode { kind: Placeholder } <- new_m
Here’s the implementation:
// event.rs
pub(super) enum Event {
StartNode {
kind: SyntaxKind,
forward_parent: Option<usize>,
},
StartNodeAt {
kind: SyntaxKind,
checkpoint: usize,
},
AddToken {
kind: SyntaxKind,
text: SmolStr,
},
FinishNode,
Placeholder,
}
// marker.rs
impl CompletedMarker {
pub(super) fn precede(self, p: &mut Parser) -> Marker {
let new_m = p.start();
if let Event::StartNode {
ref mut forward_parent,
..
} = p.events[self.pos]
{
*forward_parent = Some(new_m.pos - self.pos);
} else {
unreachable!();
}
new_m
}
}
Once again we panic (this time with unreachable!()) if the event we’re trying to modify isn’t what we expect.
There are a number of references to Event::StartNode that need to be updated due to the new field we’ve added:
impl Marker {
// snip
pub(super) fn complete(mut self, p: &mut Parser, kind: SyntaxKind) -> CompletedMarker {
self.bomb.defuse();
let event_at_pos = &mut p.events[self.pos];
assert_eq!(*event_at_pos, Event::Placeholder);
*event_at_pos = Event::StartNode {
kind,
forward_parent: None,
};
p.events.push(Event::FinishNode);
CompletedMarker { pos: self.pos }
}
}
// parser.rs
impl<'l, 'input> Parser<'l, 'input> {
// snip
fn start_node(&mut self, kind: SyntaxKind) {
self.events.push(Event::StartNode {
kind,
forward_parent: None,
});
}
// snip
}
The only other references to Event::StartNode that need to be updated are in Sink::finish, which we need to modify anyway to account for forward_parent.
Remove the first section of Sink::finish that handles checkpoints, since we aren’t using them anymore:
// sink.rs
impl<'l, 'input> Sink<'l, 'input> {
// snip
pub(super) fn finish(mut self) -> GreenNode {
for event in self.events {
match event {
Event::StartNode { kind } => {
self.builder.start_node(EldiroLanguage::kind_to_raw(kind))
}
Event::StartNodeAt { .. } => unreachable!(),
Event::AddToken { kind, text } => self.token(kind, text),
Event::FinishNode => self.builder.finish_node(),
Event::Placeholder => unreachable!(),
}
self.eat_trivia();
}
self.builder.finish()
}
// snip
}
To support forward_parent we need to ‘pull forward’ the parent, start its node, and then start the node of the event we’re currently looking at. Keep in mind that forward_parent is just an offset, so we need to add it to the index we’re currently up to:
impl<'l, 'input> Sink<'l, 'input> {
// snip
pub(super) fn finish(mut self) -> GreenNode {
for (idx, event) in self.events.into_iter().enumerate() {
match event {
Event::StartNode {
kind,
forward_parent,
} => {
if let Some(fp) = forward_parent {
if let Event::StartNode { kind, .. } = self.events[idx + fp] {
self.builder.start_node(EldiroLanguage::kind_to_raw(kind));
} else {
unreachable!()
}
}
self.builder.start_node(EldiroLanguage::kind_to_raw(kind));
}
Event::StartNodeAt { .. } => unreachable!(),
Event::AddToken { kind, text } => self.token(kind, text),
Event::FinishNode => self.builder.finish_node(),
Event::Placeholder => unreachable!(),
}
self.eat_trivia();
}
self.builder.finish()
}
// snip
}
We now have an error from trying to use self.events after it was moved by into_iter. Using references won’t work since we need to have ownership to call Sink::token. Let’s try using raw indices into self.events:
impl<'l, 'input> Sink<'l, 'input> {
// snip
pub(super) fn finish(mut self) -> GreenNode {
for idx in 0..self.events.len() {
match self.events[idx] {
Event::StartNode {
kind,
forward_parent,
} => {
if let Some(fp) = forward_parent {
if let Event::StartNode { kind, .. } = self.events[idx + fp] {
self.builder.start_node(EldiroLanguage::kind_to_raw(kind));
} else {
unreachable!()
}
}
self.builder.start_node(EldiroLanguage::kind_to_raw(kind));
}
Event::StartNodeAt { .. } => unreachable!(),
Event::AddToken { kind, text } => self.token(kind, text),
Event::FinishNode => self.builder.finish_node(),
Event::Placeholder => unreachable!(),
}
self.eat_trivia();
}
self.builder.finish()
}
// snip
}
We still have the same error, but now it’s situated at the match instead of the loop. To get ownership we can replace events we have processed with the placeholder:
use super::event::Event;
use crate::lexer::{Lexeme, SyntaxKind};
use crate::syntax::EldiroLanguage;
use rowan::{GreenNode, GreenNodeBuilder, Language, SmolStr};
use std::mem;
// snip
impl<'l, 'input> Sink<'l, 'input> {
// snip
pub(super) fn finish(mut self) -> GreenNode {
for idx in 0..self.events.len() {
match mem::replace(&mut self.events[idx], Event::Placeholder) {
Event::StartNode {
kind,
forward_parent,
} => {
if let Some(fp) = forward_parent {
if let Event::StartNode { kind, .. } = self.events[idx + fp] {
self.builder.start_node(EldiroLanguage::kind_to_raw(kind));
} else {
unreachable!()
}
}
self.builder.start_node(EldiroLanguage::kind_to_raw(kind));
}
Event::StartNodeAt { .. } => unreachable!(),
Event::AddToken { kind, text } => self.token(kind, text),
Event::FinishNode => self.builder.finish_node(),
Event::Placeholder => unreachable!(),
}
self.eat_trivia();
}
self.builder.finish()
}
// snip
}
Running the tests shows that a lot of the tests have diffs from those extra wrapping nodes we had to add to lhs. This is a great opportunity to use expect-test’s updating feature – wait, no, it isn’t! Look at the diffs; some of the tests that haven’t panicked are generating the wrong syntax trees. The ones that are panicking are doing so because the number of start_node didn’t match the number of finish_node calls.
Hmm, why is this happening?
Ah! When we index into self.events to extract the forward parent, we don’t replace this event with the placeholder. This means that it is iterated over again, causing an overabundance of start_node calls.
impl<'l, 'input> Sink<'l, 'input> {
// snip
pub(super) fn finish(mut self) -> GreenNode {
for idx in 0..self.events.len() {
match mem::replace(&mut self.events[idx], Event::Placeholder) {
Event::StartNode {
kind,
forward_parent,
} => {
if let Some(fp) = forward_parent {
if let Event::StartNode { kind, .. } =
mem::replace(&mut self.events[idx + fp], Event::Placeholder)
{
self.builder.start_node(EldiroLanguage::kind_to_raw(kind));
} else {
unreachable!()
}
}
self.builder.start_node(EldiroLanguage::kind_to_raw(kind));
}
Event::StartNodeAt { .. } => unreachable!(),
Event::AddToken { kind, text } => self.token(kind, text),
Event::FinishNode => self.builder.finish_node(),
Event::Placeholder => {}
}
self.eat_trivia();
}
self.builder.finish()
}
// snip
}
Note that we had to update the match arm that handles Event::Placeholder to do nothing, since we now intentionally encounter placeholders (i.e. it isn’t a bug anymore if we see a placeholder).
None of our tests panic now! For the majority of them the parser outputs the correct syntax tree. However, there are a few, more complex test cases for which the new version is wrong. Take, for example, parse_left_associative_binary_expression. We can run this test individually by running cargo t left_assoc (or any other unique substring of the test name). Let’s manually update the expected syntax tree so that we can tell whether the parser is broken:
// expr.rs
#[cfg(test)]
mod tests {
// snip
#[test]
fn parse_left_associative_binary_expression() {
check(
"1+2+3+4",
expect![[r#"
Root@0..7
BinaryExpr@0..7
BinaryExpr@0..5
BinaryExpr@0..3
Literal@0..1
Number@0..1 "1"
Plus@1..2 "+"
Literal@2..3
Number@2..3 "2"
Plus@3..4 "+"
Literal@4..5
Number@4..5 "3"
Plus@5..6 "+"
Literal@6..7
Number@6..7 "4""#]],
);
}
// snip
}
Running the test again shows that the parser is outputting an incorrect syntax tree:
Root@0..7
BinaryExpr@0..3
Literal@0..1
Number@0..1 "1"
Plus@1..2 "+"
Literal@2..3
Number@2..3 "2"
Plus@3..4 "+"
BinaryExpr@4..7
BinaryExpr@4..5
Literal@4..5
Number@4..5 "3"
Plus@5..6 "+"
Literal@6..7
Number@6..7 "4"
The BinaryExpr nodes aren’t being nested correctly. Let’s print self.events at the start of Sink::finish to see the events the parser generated:
// sink.rs
impl<'l, 'input> Sink<'l, 'input> {
// snip
pub(super) fn finish(mut self) -> GreenNode {
dbg!(&self.events);
// snip
}
// snip
}
Here’s what that gives us:
[crates/eldiro/src/parser/sink.rs:25] &self.events = [
StartNode {
kind: Root,
forward_parent: None,
},
StartNode {
kind: Literal,
forward_parent: Some(
4,
),
},
AddToken {
kind: Number,
text: "1",
},
FinishNode,
AddToken {
kind: Plus,
text: "+",
},
StartNode {
kind: BinaryExpr,
forward_parent: Some(
6,
),
},
StartNode {
kind: Literal,
forward_parent: None,
},
AddToken {
kind: Number,
text: "2",
},
FinishNode,
FinishNode,
AddToken {
kind: Plus,
text: "+",
},
StartNode {
kind: BinaryExpr,
forward_parent: Some(
6,
),
},
StartNode {
kind: Literal,
forward_parent: None,
},
AddToken {
kind: Number,
text: "3",
},
FinishNode,
FinishNode,
AddToken {
kind: Plus,
text: "+",
},
StartNode {
kind: BinaryExpr,
forward_parent: None,
},
StartNode {
kind: Literal,
forward_parent: None,
},
AddToken {
kind: Number,
text: "4",
},
FinishNode,
FinishNode,
FinishNode,
]
What a mess! I have a hunch that there’s something wrong with how we handle forward_parent in the sink, since the nesting of BinaryExprs – something that happens through CompletedMarker::precede and therefore forward_parent – is broken. Let’s start at the first occurrence of an event with a forward parent: the second event. This node’s forward parent is 4, meaning that it is four events down, which is a StartNode { kind: BinaryExpr }. Curiously, this node itself has a forward parent of 6, which also has a forward parent! We need to start_node the last forward parent in the chain first, then the one before that and the one before that until we get to the node that started the chain. Currently in the sink we only handle the original node and its forward parent, but no levels deeper than that. Instead, we should keep checking for forward parents in a loop, accumulating them in a vector. Afterwards we can loop through this vector in reverse (to ensure the last node in the chain of forward parents is started first) and call start_node on each one.
Enough talking, let’s write the code:
impl<'l, 'input> Sink<'l, 'input> {
// snip
pub(super) fn finish(mut self) -> GreenNode {
for idx in 0..self.events.len() {
match mem::replace(&mut self.events[idx], Event::Placeholder) {
Event::StartNode {
kind,
forward_parent,
} => {
let mut kinds = vec![kind];
let mut idx = idx;
let mut forward_parent = forward_parent;
// Walk through the forward parent of the forward parent, and the forward parent
// of that, and of that, etc. until we reach a StartNode event without a forward
// parent.
while let Some(fp) = forward_parent {
idx += fp;
forward_parent = if let Event::StartNode {
kind,
forward_parent,
} =
mem::replace(&mut self.events[idx], Event::Placeholder)
{
kinds.push(kind);
forward_parent
} else {
unreachable!()
};
}
for kind in kinds.into_iter().rev() {
self.builder.start_node(EldiroLanguage::kind_to_raw(kind));
}
}
Event::StartNodeAt { .. } => unreachable!(),
Event::AddToken { kind, text } => self.token(kind, text),
Event::FinishNode => self.builder.finish_node(),
Event::Placeholder => {}
}
self.eat_trivia();
}
self.builder.finish()
}
// snip
}
$ cargo t left_assoc
running 1 test
test parser::expr::tests::parse_left_associative_binary_expression ... ok
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 34 filtered out
At least that one test we’ve been looking at is passing. If we try running our entire suite, we’ll find that every single test failure is due to the changes we made to lhs. It is time to update all our failing tests automatically:
$ UPDATE_EXPECT=1 cargo t -q
running 35 tests
...................................
test result: ok. 35 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
All that’s left is to delete Parser::start_node, Parser::start_node_at, Parser::finish_node, Parser::checkpoint, Event::StartNodeAt, and the line from the match in Sink::finish that handles Event::StartNodeAt.
Thanks for following this series up to here! The next part will consist of a few refactorings to keep the code clean.
It would be ideal if this was a compile time error; linear typing is the ability of a language to enforce at compile time that objects are used once, not more or less, and would come in handy here. ↩︎