For the past year I had been seriously thinking of doing a major refactor of muon's internals. In particular, the entire parser/interpreter was the first I had ever written and I felt like there were a lot of things I would have done differently if given the opportunity to start over.
Bytecode interpreter
The biggest change was porting muon over to using a bytecode interpreter rather than a treewalk interpreter. In a treewalk interpreter, you evaluate expressions by just walking the AST. This approach is appealing because it is very easy to implement and you don't need to do any additional processing after parsing. For example, the expression:
a = 1 + 2
might be parsed into a tree like this:
=
/ \
a +
/ \
1 2
And you can have a function, maybe called eval_node() that first gets called
on =, and then recursively for each child.
eval_node(node *n)
{
switch (n->type) {
case node_type_equal: return assign_variable(eval_node(n->left), eval_node(n->right));
case node_type_plus: return eval_node(n->left) + eval_node(n->right);
...
}
}
Unfortunately, there are several issues to this approach. The biggest one in my opinion is that it makes the interpreter very unwieldy to work on. The backtrace of anything even a little bit compilcated can easily grow into 100+ frames, and it makes it difficult to do any sort of control flow since you have to unwind so many frames to get back to the control flow statement. Muon used to use a global variable called loop_state to perform break and continue for example. Another alternative for handling this unwinding state would be exceptions. Thankfully, no such mechanism exists in C (and it comes with its own share of problems).
Bytecode, contrasted with the above interpreter, is far more simple and makes things like control flow and debugging easier. A break or continue is just a modification of the instruction pointer. Additionally, if your VM manages the program stack, you get the added bonus that your program is less likely to overflow its stack, and you have more insight into when a stack overflow might be imminent.
Bytecode can also be much faster, since the representation is more compact and the operations are smaller. Muon's small bytecode compiler even preforms a few optimizations like function lookup at compile time.
This rewrite required the entire analyzer be rewritten as well, and I took care to make sure the interpreter and analyzer share as much code as possible this time. In the previous analyzer, many of the basic interpreter operations were re-implemented as analyzer specific versions. Now, however, various hooks have been added to the VM where the analyzer can inject behavior that it needs to run with minimal changes to how the bytecode actually executes. The resulting analyzer is far less hacky than the original and in some cases provides better diagnostic information. It lost a little bit of maturity that the previous analyzer had, and probably regressed in some edge cases. The new analyzer is a much more solid platform to build on though so patching these should be easier.
I also had to rewrite the way the debugger steps through code, but this turned out to be basically free since we don't have to instrument a certain node type to add the break point. We can just break after every instruction in the core VM loop. Combined with the new source location underlining system, it is pretty cool to just step through a program and see how it is executing:
Pratt parser
As part of this overhaul, muon also got a completely rewritten parser. meson's parser is notorious for allowing completely busted expressions. This is due to it's parser returning an "empty node" in many cases which then has to be manually checked. For example, the below code is valid according to the parser (tested with meson 1.5):
project('parser')
if false
if
+ 1
a = endif
.call()
c = b[]
endif
message('all good')
Here we have 4 cases where the expression is broken because it is missing a key part:
+ 1- missing left hand sidea =- missing right hand side.call()- missing method receiverc = b[]- missing index argument
Meson's parser has inserted an empty node for all of these missing elements, and gone on with its day. Actually executing any of these bad nodes doesn't work of course, typically it leads to Meson dying with the last words: "Unknown statement".
Muon's parser was originally just a port of meson's parser so it suffered from the same issues. Over time, I tried to patch over these issues by adding lots of checks for empty nodes. Every time muon parsed a sub-expression it typically had to check the parse had actually returned something and cases where I missed that check were probably lurking error cases.
I am happy to report that muon's new parser doesn't have empty nodes at all. This means that there is no need to check for empty nodes as they can't occur. So if a parse succeeds you can be confident that the resulting AST is actually valid. The new parser also uses less recursion, parses various expressions (like f-strings) more robustly, and uses a Pratt Parser core which makes the implementation pretty clean.
The rewritten parser produces an incompatibly ast from the previous parser so I also had to rewrite the formatter. The formatter code was pretty gnarly at this point though so it was a good time for a rewrite. I also took the opportunity to bring muon fmt up to par with the new meson formatter. muon fmt should support all options meson format supports, as well as lots of little fixes like newline preservation.
So, essentially all of muon's interpreter core was rewritten. I think this was an excellent way to pay down tech debt and muon is now way more flexible. For example, supporting per-file scopes or some other more complex scoping system is now something the interpreter supports, but is disabled for meson.build files. The new vm also fully supports meson-native functions with type signatures and return types. muon 0.3.0 will ship with a few modules implemented this way and I hope that this lowers the contributor barrier to adding new modules to muon. I have some big ideas of things to do with this new more powerful core but I'll save that for another time.