Understanding Lua Expressions - Live Posts
Posts I made while trying to understand how lua expressions work.
Table of Contents
What is this about?
This is a collection of live posts I made on the Fediverse while diving into Lua expressions. I'm releasing these in the hopes that they'll be useful, not just to future me, but also to other people. The corresponding proper blog post is stuck in its draft stage until I pick the project back up again.
On Jumplists
Okay, time to take those jumplists the lua 5.4 compiler talks about all the time apart:
They seem to be for patching jump instructions to their proper destination, until then the destination of a jump instruction is either the address of another instruction (linked list) or NO_JUMP (= -1, jump to self) to end the list. The entry point is the intermediate expression descriptor (which represents an expression that isn’t fully compiled yet), which hosts a t (true jump) and f (false jump) index, they have the same semantics as the unpatched destination addresses.
Now I’m curious about the functions that manipulate those lists so I have them on my cheatsheet for quick lookup.
Also I want to find out what “true jump” and “false jump” mean exactly, where are they patched with which addresses.
And I want to find out if that mechanism interacts or is reused outside of expressions.
Update: I also want to find out which part generates the TESTSET instructions, they seem important.
Just had an idea … searching noises … looks like @alcinnz@floss.social was in there before me: https://adrian.geek.nz/gnu_docs/scripting-langs.html#lua
Note from future Slatian: Adrian explains Lua on a higher level than I do here, which is very useful for getting an overview.
Lua makes pretty important split between jumplists that need a value and jumplists that are entirely controlled by TESTSET instructions and therefore bring their own value (this seems to be an optimization for or and and).
There are a lot of places in the code that treat TESTSET specially.
As a little context: Each jump instruction is indirectly connected to its corresponding testcase as the testcase, if present always is the previous instruction in the bytecode array (Lua has a lookup to know which instructions are testcases), if the testcase succeeds, it skips the jump, if not the jump is executed.
There is also the patchlistaux() function that is at the core of a lot of the compiler inner workings. It patches destination addresses and destination registers simply based on whether a value is provided (TESTSET) or not. Looks quite intimidating when one cones across it, but its actually a very peaceful critter.
The comment helps understanding it, but doesn’t make the TESTSET part obvious.
It’ll probably also be used to convert TESTSET to regular TEST Instructions (if the value isn’t needed), because the underlying helpers are capable of that.
Update: luaK_patchlist() does exactly that, patch a list to a destination address discarding the values in potential TESTSETs.
This seems like one of those optimizations the Lua people like to write papers and even more papers about, why not about this one ???
Another important function I didn’t have look at until now is luaK_getlabel, this returns the index (pc — program counter) of the next to be generated instruction for use as a jump target and stores that address in the function state as the last instruction that was a jump target, so that when soon after the jump logic the code that tries to merge multiple instructions runs, it knows that there is a good reason for two instructions.
There is a possibility for multiple expression descriptions (and therefore no limit on how many jumplists are active at any given time) as indicated by there being two expression descriptions needed for many kinds of table operations.
Which means I have to update my rewrite code to reflect that, fun!
For the rewrite I’ll opt to attach a Vec directly to the expression description to help with readability, even if it costs a few bytes extra.
Onto where the TESTSETs come from:
They are generated using condjump() in the jumpcond() (“jump_on_cond”) function, which I haven’t fully read yet, it takes an expression, generates a jump, adds the jump to the jumplists ….
jumpcond() takes an expression, a thruthyness boolean and generatios a jump if the expression is truthy (evaluates to something not false and not nil). It is used in luaK_goiftrue() and luaK_goiffalse() they are a “fall through if given expression is {bool_from_name}, otherwise jump somewhere”. These are used by and, or, if (why is that in the parser file ???), for and when parsing conditions (cond()) in general (I guess other kinds of loop).
What makes that hard to read is, that the jumplists are all indirectly passed by modifying expressions by pointer and it isn’t really obvious where that happens …
Maybe relevant: The exp2reg function, which compiles an expression description to bytecode that makes sure a value ends up in a specified register assumes that a VJMP (jump/test) expression is a true jump, which gets patched to a LOADTRUE instruction.
exp2reg also, after letting discharge2reg take care of any data shuffling uses the jump lists to patch all “true jumps” to an instruction that loads true into the given destination register and all “false jumps” to an instruction that loads false, all tests that bring their own value are patched straight to the end of the expressions bytecode, independent of the jumplist they are in.
So “true jumps” are all jumps that go to a LOADTRUE just before the end of the expression and “false jumps” go to a LOADFALSESKIP¹ just before the end of the expression.
This also explains why need_value returns false for empty lists: An empty list has nothing to be patched to a LOAD… instruction.
I’m curious how that is used to implement if and loops, because those probably reuse the lists with slightly different semantics.
¹: The SKIP part skips the LOADTRUE directly after.
On Re-Implementing jumplists
I’ll try to implement what I know so far about jumplists in Lua as long as that knowlege is cached.
Step one: Make my ExpressionDescription a struct that contains the enum for the different kinds of expression description+Jumplists (In my code that will be a Vec<usize>, each item being an offset in the bytecode array, for readablility reasons). And then I have to fix the code I’ve already written that relies on ExpressionDescription being an enum …
My luaK_getlabel equivalent fits neatly into the instruction builder struct, less code in the compiler to confuse myself.
patchlistaux is also very cute when written down in rust with my readability optimization:
/// Patches all offsets in the given `list` using the [patch_testset_register] and [patch_jump_target] functions.
///
/// If `patch_testset_register` returns true the destintion jump is patched to `vtarget`
/// ("value target"), which handels paths that bring their own value via testset.
///
/// All other test result jumps are patched to `dtarget` ("default target"), they don't
/// bring a value along.
///
/// There is also the possibility to use this with `to_reg` set to `None` and `vtarget` equal
/// to `dtartget` to make all jump sources equal in that they don't bring a value.
///
/// Equivalent to `patchlistaux` in the original Lua source.
Yep, most of that is documentation :P.
exp2reg is implemented. Without support for variables right now, lets see if I can now connect the compiler frontend to the backend and compile a first expression. Maybe even something non-trivial like:
not true
Yes, that looks ridiculously simple, but it requires unary operator parsing, hooking that true up to the not, reversing the true and then discharging everything into a register. (Plus some jumpliist bookkeeping for more complex expressions later on)
I happen to know (because I tried earlier) that compiling a not is implemented in codenot, which:
- takes some shortcuts for constants, easy I already have that
- for a Jump/Test expression it calls
negatecondition(probably missing in my re-implementation right now) - for Relocatable (
VRELOC) and NonRelocatable (VNONRELOC) results it makes sure they end up in a free register, generates aNOTopcode and stores the instructions address as a relocateable expression.
In any case it swaps the jumplists, which now that I know their purpose makes perfect sense. It also removes all values that would be brought by the jump tables as the original value is indeed useless when one just needs a true or false that is the exact opposite of the original truthiness.
negatecondiotion simply toggles the k flag that is attached to all test instruction which negates the outcome of the test. Except for the excluded by assertion TESTSET and TEST instructions? I guess they don't become Jump (VJMP) expressions.
Note: NonRelocatable and Relocatable expressions are two kinds of variable expressions where the bytecode that generates the expression result has already been generated. For NonRelocatable ones the expression result is already assigned to a fixed register. For Relocatable ones the offset of the last instruction that generates the final result is stored so it can be patched to point to any desirable register.
Conveniently the destination register always has the same representation in bytecode, so one doesn't have to care which instruction is being patched.
Note from future Slatian: At this point I went onto a small sidequest to fix number parsing and then decided to get a connection to binary operators.
Almost overlooked the freeexp function, which has nothing to do with C memory management, but releases the register a NonRelocateable expression description might be holding onto.
The discharge2… family apparently never really does anything but turn an expression into a NonRelocatable (they also don’t touch the jump tables) just for the C code to naively read the register … changed that to non mutable borrows of the expression descriptions in the rust code.
I hope that doesn’t come back to haunt me when I get around to implementing luaK_dischargevars, but for now I got less stuff to keep track of in my brain, which is good.
codenot implemented, this one is called from luaK_prefix, which gets called from subexpr (function for unary and binary expressions, recursively calls itself) which I already have a sleleton of, getting close!
On Binary Operands
As in operationm that involve two arguments.
Okay new thread for binary operands in lua 5.4.7:
I’m trying to understand how the Lua compiler translates binary operands into bytecode.
I’ve just connected the frontend with the backend of the lua compiler using the not unary operator and some simple expressions (true, false, nil, numbers).
For now to connect with the jumptable thread I’ll focus on how the and and or operators work.
My main questions are:
What exactly does the parsing loop in subexpr (which can recursively parse binary, unary and simple expressions) do?
How do luaK_goiftrue and luaK_goiffalse help in generating valid bytecode for and and or expressions.
One of the challanges is that subexpr when calling itself returns the next operator, I already return an expression and want to avoid returning a tuple, so I also wonder if the recursive self calling could be flattened into some loops. Or the operator determined via some other way.
Wrote a little script (in lua of course) to visualize what subexpr is doing and it turns out that I can just grab the next operation where op gets assigned, to nextop, though that isn’t very efficient, which is why the lua devs chose to do it the way they did.
1 v = simpleexp()
* op = getbinopr(peek())
| while (op.is_some and 11 > 0)
`- next()
nextop, v2 = subexp(11)
vvv vvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
2 v = simpleexp()
+ op = getbinopr(peek())
| while (X)
| *skip*
| return +, 2
^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| v = postfix(op, v, v2) // *, 1, 2
| op = nextop // +
| while (op.is_some and 10 > 0)
`- next()
nextop, v2 = subexp(10)
vvv vvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
3 v = simpleexp()
* op = getbinopr(peek())
| while (op.is_some and 11 > 10)
`- next()
nextop, v2 = subexp(11)
vvv vvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
4 v = simpleexp()
[ ] op = getbinopr(peek())
| while (X)
| *skip*
| return [ ], 4
^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| v = postfix(op, v, v2) // *, 3, 4
| op = nextop // [ ]
| while (X)
| *skip*
| return [ ], (* 3 4)
^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| v = postfix(op, v, v2) // +, (* 1 2), (* 3 4)
| op = nextop // [ ]
| while (X)
| *skip*
| return [ ], (+ (* 1 2) (* 3 4))
When running it with something like 1 + 2 + 3 + 4 one can see that it is already flattened as far as possible (we are trying to parse a tree structure after all) for the usual left associate functions and is fully recursive for the right associative ones (like 1 ^ 2 ^ 3 ^ 4), so I’ll keep the lua implementation.
Someone probably already fried their brain over this, Thank You!
Note: This also pretty stupidly follows the EBNF syntax notation, so a beautiful solution too, just not obvious in the C code.
Now that its sorted out that the loop and recursion simply follow the grammar notation, what do luaK_infix and luaK_posfix do?
luaK_infix does whatever needs to be done with the first operand before the second operand is involved, setting up jump logic for and and or or making sure that the operand is in a register or the constant array, depending on available opcodes.
luaK_posfix does … almost everything else … folding constants (evaluating expressions that only involve constants t compile time), merging the operands jumplists, making sure the second operand is in a register and dispatching operator specific implmenetations (like codenot, but for binary operations)