字节码到源代码映射

# 字节码到源码映射 来源：https://tidefield.dev/bytecode-to-source-mapping/ > 我在完成 Robert Nystrom 所著 *Crafting Interpreters* 第 14 章挑战时遇到了这个问题 (https://craftinginterpreters.com/chunks-of-bytecode.html#challenges)。 > **注意：** 生产环境中的虚拟机要复杂得多，不过我将在本文末尾分享这与 JVM、Lua 等其他虚拟机的相似之处 (https://tidefield.dev/bytecode-to-source-mapping/#how-other-vms-approach-this)。 ## 背景 本书前半部分自上而下实现了一个玩具语言 jlox：从词法分析和语法分析开始，构建 AST，然后解释执行。后半部分则从底部向上重新实现同一语言，从字节码结构开始。 包含代码、常量和源代码行号元数据的字节码块 来源：*Crafting Interpreters*，第 14 章 (https://craftinginterpreters.com/chunks-of-bytecode.html#what-is-bytecode) 它将字节码存储在一个**块（chunk）**中，该块包含一序列字节。每个字节要么是操作码（opcode），要么是操作码的操作数。因此，指令可能占用不同数量的字节。例如，`OP_RETURN` 是单字节，而 `OP_CONSTANT` 后跟一个操作数，该操作数指向块常量池的索引： ``` offset 0 1 2 byte OP_CONSTANT constant index OP_RETURN \___________________/ | 一条指令 另一条指令 ``` 当一条指令导致运行时错误时，虚拟机需要一种方法将字节码偏移量转换回产生它的源代码行。因此，块需要存储行号。一个简单的解决方案是并行存储第二个数组 `lines`，使每个字节都有对应的源代码行： ``` 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) 查找。然而，对于 n 字节的字节码，它占用 O(n) 内存。观察上面的行数组，我们可以利用一个事实：多个连续字节可能来自同一个源代码行。 ## 游程编码 游程编码 (https://en.wikipedia.org/wiki/Run-length_encoding) 只存储每个行号一次，以及属于该行号的连续字节数： ``` 每字节行： 1 1 1 1 1 | 2 2 2 编码后的游程： (5, 1) | (3, 2) 计数，行号 ``` - `n` 是字节码的字节数。 - `r` 是连续行游程的数量。这里 `n = 8`，`r = 2`。一般情况下，`1 <= r <= n`。最好的情况是整个块来自同一源代码行，此时 `r = 1`。最坏的情况是每字节后都改变源代码行，此时 `r = n`。游程编码将行表从 O(n) 内存降低到 O(r) 内存。 ### 线性搜索 要查找任意偏移量对应的行，我们可以遍历游程并累加其长度。对于偏移量 6： ``` (5, 1) -> 覆盖偏移量 0..4 (3, 2) -> 覆盖偏移量 5..7 <- 偏移量 6 在这里 ``` 因此，随机查找在最坏情况下需要 O(r) 时间。如果在反汇编块时对每个字节都执行一次新的线性扫描，总成本为 O(nr)。由于 `r` 可能等于 `n`，最坏情况为 O(n²)。 ### 单遍遍历 然而，游程编码并非本质上是二次的。如果反汇编器按递增顺序访问偏移量，它可以维护一个指向当前游程的游标。这样，每个字节和每个游程只被访问一次，得到 O(n + r)，由于 `r <= n`，简化为 O(n)。这种方法适合顺序遍历，但不能改善任意查找，查找仍然需要 O(r) 时间。如果错误给出的偏移量位于块的中间某处，我们仍然需要从头扫描游程，除非我们存储更多信息。 ## 前驱问题 我们可以不记录游程长度，而是记录游程的起始偏移量： ``` 偏移量： 0 1 2 | 3 4 | 5 行号： 1 1 1 | 2 2 | 3 起始对： (0, 1) (3, 2) (5, 3) ``` 每一对表示：从该字节码偏移量开始，后续这些数量的字节属于该源代码行。本质上，这变成了一个静态前驱问题 (https://people.seas.harvard.edu/~cs224/spring17/lec/lec1.pdf)¹ (https://tidefield.dev/bytecode-to-source-mapping/#user-content-fn-1)。 ### 二分查找 由于这些对是按起始偏移量排序的，我们可以通过修改过的二分查找来解决静态前驱问题。考虑： ``` 起始对： (0, 1) (3, 2) (5, 3) ``` 给定目标偏移量 4，我们要找到小于等于 4 的最大起始偏移量，即 `(3, 2)`。在二分查找过程中，`left` 和 `right` 界定仍可能包含精确匹配的区域。如果没有精确匹配，它们最终会交叉： ``` 目标 4 v 起始偏移量： 0 3 | 5 ^ ^ right left ``` 如果没有精确匹配，`pair[right]` 指向小于目标的最大起始偏移量。结合精确匹配的情况，这就能找到小于等于目标的最大起始偏移量。 ``` 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 } ``` 这段代码依赖于以下不变性： - `get_line` 仅在有效的字节码偏移量下调用。 - `line_starts` 保持有序，因为字节码是按顺序追加的。 ### 使用起始偏移量的单遍遍历 二分查找对于任意查找很有用。在顺序反汇编过程中，游标可以指向当前的起始对。每当下一对的起始偏移量小于等于当前字节码偏移量时，我们就推进游标。由于游标只向前移动，它最多访问每对一次，因此整体遍历为 O(n)。这就使得起始偏移量数据结构拥有两种有用的访问模式： - 对于随机偏移量使用二分查找：O(log r)。 - 对于有序遍历使用游标：整体 O(n)。 美妙之处在于我们不必在二分查找和游标方法之间做选择，而是可以根据场景选择任意一种。 ## 运行时分析 | 方法 | 内存 | 随机查找 | 完整遍历 | | --- | --- | --- | --- | | 每字节一行 | O(n) | O(1) | O(n) | | 游程长度 + 每次新线性搜索 | O(r) | O(r) | O(nr)，最坏情况 O(n²) | | 游程长度 + 游标 | O(r) | O(r) | O(n) | | 起始偏移量 + 二分查找 | O(r) | O(log r) | O(n log r) | | 起始偏移量 + 游标 | O(r) | 需要时 O(log r) | O(n) | ## 其他虚拟机如何处理 ### JVM JVM 的 `LineNumberTable` (https://docs.oracle.com/javase/specs/jvms/se25/html/jvms-4.html#jvms-4.7.12) 本质上使用与上述起始偏移量相同的表示。它是每个方法的 `Code` 属性 (https://docs.oracle.com/javase/specs/jvms/se25/html/jvms-4.html#jvms-4.7.3) 的可选属性，每个 `(start_pc, line_number)` 条目标记源代码行的起始位置。一个区别是规范不要求这些对排序。HotSpot 需要查找行号时，`line_number_from_bci` (https://code.googlesource.com/edge/openjdk/+/4c9e8b056de9eaa7412d42edfe4bf0b29e02250e/hotspot/src/share/vm/oops/method.cpp#628) 会进行线性搜索以找到前驱。 ### Lua Lua 使用并行数组存储行信息，类似于本书中的实现。但它不是为每条指令存储精确的行号，而是存储与上一行号的一个字节差，并偶尔设置绝对检查点（来源 (https://github.com/lua/lua/blob/84938a7d2b680d2d28ec99606e84fe712efd9a69/lobject.h#L568-L577)），以限制查找扫描的范围（写入 (https://github.com/lua/lua/blob/84938a7d2b680d2d28ec99606e84fe712efd9a69/lcode.c#L324-L346), 读取 (https://github.com/lua/lua/blob/84938a7d2b680d2d28ec99606e84fe712efd9a69/ldebug.c#L80-L97)）。例如，给定一个绝对检查点 `(pc 2, line 300)`： ``` 指令： 0 1 2 3 4 源码行： 10 10 300 310 314 （不存储行号，而是） lineinfo: 0 0 ABS +10 +4 （存储行差） ^ |-- 当差超过一个字节时的检查点 ``` 要查找指令 4 的行，Lua 从行 300 开始，加上随后的差值：`300 + 10 + 4 = 314`。 1. 在研究这个问题时，我发现它在哈佛大学 CS224：高级算法课程的第一讲中被称为静态前驱问题 (https://youtu.be/0JUN9aDxVmI?si=ZqUIW5ZrwZuBPvAU&t=629)。该讲座还介绍了动态前驱问题和字 RAM 模型。我只略读了那些主题，但我希望能在字节码虚拟机或其他地方遇到它们的实际用途。↩ (https://tidefield.dev/bytecode-to-source-mapping/#user-content-fnref-1)