# Bytecode-to-source mapping

A write-up from working the chapter 14 challenges in Robert Nystrom's *Crafting Interpreters*. The problem: when a bytecode instruction faults at runtime, the VM has to name the source line that produced it, so a chunk needs a line table. The interesting part is that the obvious compression makes random lookup worse, and the fix turns out to be a named problem from algorithms courses.

Bytecode in the book lives in a *chunk*, a flat byte sequence where each byte is either an opcode or an operand. Instructions are variable-width: `OP_RETURN` is one byte, `OP_CONSTANT` is followed by an index into the chunk's constant pool. That variability matters, because it means offsets — not instruction indices — are what a runtime error reports.

## Parallel array

Store a `lines` array alongside `code`, one entry per byte:

```
offset:       0  1  2  3  4  5  6  7
code:        00 01 00 02 01 00 03 01
line:         1  1  1  1  1  2  2  2
```

`O(1)` lookup, `O(n)` memory. The redundancy is obvious — consecutive bytes usually come from the same line.

## Run-length encoding

Store each line once with a count of bytes belonging to it. Writing `n` for bytecode bytes and `r` for the number of runs, the example above becomes `(5, 1) (3, 2)`, with `n = 8` and `r = 2`. In general `1 <= r <= n`: the best case is a whole chunk from one line, the worst changes line after every byte. Memory drops from `O(n)` to `O(r)`.

Random lookup now costs `O(r)`, because finding the run covering an offset means accumulating run lengths from the start. Doing that per byte during disassembly gives `O(nr)`, worst case `O(n²)`. But that quadratic is an artifact of how the disassembler is written, not of the encoding: since a disassembler visits offsets in increasing order, keeping a cursor on the current run visits each byte and each run once, for `O(n + r)` — which is `O(n)` since `r <= n`.

The cursor fixes traversal and does nothing for the case that motivated the line table in the first place. A runtime error hands you an offset in the middle of a chunk, and there is still no way to reach it except scanning from the beginning.

## Starting offsets, and the static predecessor problem

Record where each run *starts* rather than how long it is:

```
offset:          0  1  2 | 3  4 | 5
line:            1  1  1 | 2  2 | 3
starting pairs: (0, 1)    (3, 2) (5, 3)
```

Finding the line for offset 4 means finding the greatest starting offset less than or equal to 4. That is the [static predecessor problem](https://people.seas.harvard.edu/~cs224/spring17/lec/lec1.pdf) — the author found the name via the first lecture of Harvard's CS224, which also covers the dynamic variant and the word RAM model.

Because the pairs are sorted (bytecode is appended in order), a modified binary search solves it in `O(log r)`. The modification is in what happens when there's no exact match: `left` and `right` cross, and `pair[right]` is exactly the predecessor.

```rust
fn get_line(chunk: &Chunk, offset: usize) -> usize {
    let mut left = 0;
    let mut right = chunk.line_starts.len() - 1;
    while left <= right {
        let mid = left + (right - left) / 2;
        let (mid_offset, mid_line) = chunk.line_starts[mid];
        if offset < mid_offset {
            right = mid - 1;
        } else if offset > mid_offset {
            left = mid + 1;
        } else {
            return mid_line;
        }
    }
    let (_, line) = chunk.line_starts[right];
    line
}
```

The stated invariants — `get_line` is only called with a valid bytecode offset, and `line_starts` stays sorted — are load-bearing rather than decorative. `right` is a `usize` and the search does `right = mid - 1`, so an offset below the first recorded start would have to underflow to be reported as absent. It can't happen, because the first pair always starts at offset 0 and a valid offset is never less than that, but the code has no check standing between the invariant and the bug.

The two access patterns then coexist without a choice being forced: binary search for an arbitrary offset from an error report, cursor advance for ordered disassembly, both over the same structure.

| Approach | Memory | Random lookup | Full traversal |
|---|---|---|---|
| One line per byte | `O(n)` | `O(1)` | `O(n)` |
| Run lengths, fresh linear search | `O(r)` | `O(r)` | `O(nr)`, worst `O(n²)` |
| Run lengths + cursor | `O(r)` | `O(r)` | `O(n)` |
| Starting offsets + binary search | `O(r)` | `O(log r)` | `O(n log r)` |
| Starting offsets + cursor | `O(r)` | `O(log r)` when needed | `O(n)` |

## What production VMs do

The JVM's `LineNumberTable` is the starting-offset representation, as an optional attribute of each method's `Code` attribute, with `(start_pc, line_number)` entries marking where each source line begins. The spec notably does not require the entries to be sorted, which forecloses binary search — HotSpot's `line_number_from_bci` does a linear scan for the predecessor.

Lua keeps a parallel array like the book's first design, but stores a one-byte delta from the previous line rather than the absolute line, with occasional absolute checkpoints emitted when the delta won't fit in a byte:

```
instruction:  0   1    2    3    4
source line: 10  10  300  310   314
lineinfo:     0   0  ABS   +10   +4
```

Reading instruction 4 means starting at the checkpoint's line 300 and summing forward: `300 + 10 + 4 = 314`. It is the parallel-array memory profile compressed to a byte per instruction, with the checkpoints bounding how far a scan can run.

For the bytecode-VM context this sits in, [[retrofitting-jit-c-interpreters]] covers what happens to an interpreter of this shape when a JIT is added underneath it. [[intro-compilers-language-design]] is the textbook route into the same pipeline from the front end, and [[virtual-machines-versatile-platforms]] the taxonomy of the machines this line table lives inside.