Bytecode-to-Source Mapping
I encountered this problem while working through the challenges in chapter 14 of Robert Nystrom’s Crafting Interpreters.
Note: Production VMs are more sophisticated, though I’ll share how this is similar to other VMs like JVM and Lua at the end of this post.
Background
The first half of the book implements a toy language, jlox, from the top down, starting with lexing and parsing to build an AST and then interpreting it. The second half re-implements the same language but from the bottom up, beginning with the bytecode structure.
Source: Crafting Interpreters, chapter 14
It stores bytecode in a chunk , which contains a sequence of bytes. Each byte is either an opcode or an operand belonging to an opcode. Instructions can therefore occupy different numbers of bytes. For example, OP_RETURN is a single byte, while OP_CONSTANT is followed by an operand containing an index into the chunk’s constant pool:
offset 0 1 2<br>byte OP_CONSTANT constant index OP_RETURN<br>\___________________/ |<br>one instruction another instruction<br>When an instruction causes a runtime error, the VM needs a way to translate the bytecode offset back to the source line that produced it. So the chunk needs to store the line numbers.
A straightforward solution is to store a second array, lines, in parallel with the bytecode so that every byte gets a corresponding source line:
offset: 0 1 2 3 4 5 6 7<br>code: 00 01 00 02 01 00 03 01<br>line: 1 1 1 1 1 2 2 2<br>This design is simple and gives us O(1) lookup. However, it takes up O(n) memory for n bytes of bytecode.
Looking at the lines array above, we can exploit the fact that several consecutive bytes can come from the same source line.
Run-length encoding
Run-length encoding stores each line number once along with the number of consecutive bytes belonging to it:
line per byte: 1 1 1 1 1 | 2 2 2<br>encoded runs: (5, 1) | (3, 2)<br>count,line
n is the number of bytecode bytes.
r is the number of consecutive line runs.
Here, n = 8 and r = 2. In general, 1 . The best case is an entire chunk produced from one source line, where r = 1. The worst case changes source lines after every byte, where r = n. Run-length encoding reduces the line table from O(n) to O(r) memory.
Linear search
To find the line for an arbitrary offset, we can walk through the runs while accumulating their lengths. For offset 6:
(5, 1) -> covers offsets 0..4<br>(3, 2) -> covers offsets 5..7<br>A random lookup therefore takes O(r) time in the worst case. If we perform a new linear scan for every byte while disassembling a chunk, the total cost is O(nr). Since r can equal n, the worst case is O(n²).
One-pass traversal
However, run-length encoding is not inherently quadratic. If a disassembler visits offsets in increasing order, it can keep a cursor pointing to the current run. Each byte and each run is then visited only once, giving O(n + r), which simplifies to O(n) because r .
This approach is ideal for sequential traversal, but it does not improve arbitrary lookups, which remain O(r). If an error gives us an offset somewhere in the middle of a chunk, we still need to scan runs from the beginning unless we store more information.
Predecessor problem
Instead of recording run length, we can record the run’s starting offset:
offset: 0 1 2 | 3 4 | 5<br>line: 1 1 1 | 2 2 | 3<br>starting pairs: (0, 1) (3, 2) (5, 3)<br>Each pair means starting at this bytecode offset, this number of subsequent bytes belong to this source line. Essentially, this is now a static predecessor problem.1
Binary search
Because the pairs are sorted by their starting offsets, we can solve the static predecessor problem via a modified binary search.
Consider:
starting pairs: (0, 1) (3, 2) (5, 3)<br>Given a target offset of 4, we find the greatest starting offset that is less than or equal to 4 which is (3, 2).
During binary search, left and right delimit the region that could still contain an exact match. If no exact match exists, they eventually cross:
target 4<br>starting offsets: 0 3 | 5<br>^ ^<br>right left<br>If there is no exact match, pair[right] points to the greatest starting offset below the target. Together with the exact-match case, this finds the greatest starting offset less than or equal to the target.
fn get_line(chunk: &Chunk, offset: usize) -> usize {<br>let mut left = 0;<br>let mut right = chunk.line_starts.len() - 1;<br>while left right {<br>let mid = left + (right - left) / 2;<br>let (mid_offset, mid_line) = chunk.line_starts[mid];<br>if offset mid_offset {<br>right = mid - 1;<br>} else if offset > mid_offset {<br>left = mid + 1;<br>} else {<br>return mid_line;<br>let (_, line) = chunk.line_starts[right];<br>line<br>This code depends on the invariants:
get_line is called only for a valid bytecode offset.
line_starts remain sorted because bytecode is appended in order.
One-pass traversal with starting offsets
Binary search is useful for an arbitrary lookup. During sequential disassembly, a cursor can instead point to the current starting pair. Whenever the next pair’s...