バイトコードからソースコードへのマッピング
Bytecode-to-Source Mapping (tidefield.dev)
要約
この記事では、インタープリタにおいてバイトコードのオフセットをソースコードの行番号にマッピングする手法について解説しています。単純な配列から、ランレングスエンコーディング、そして二分探索やカーソルベースの走査が可能な「開始オフセット」方式まで、効率的なマッピング方法を比較検討しています。JVMやLuaなどの他の仮想マシンでの実装方法にも触れています。
全文翻訳
バイトコードからソースコードへのマッピング
Robert Nystrom の著書『Crafting Interpreters』の第14章の課題に取り組んでいる際に、この問題に遭遇しました。
注: 本番環境のVMはより洗練されていますが、JVMやLuaのような他のVMとどのように類似しているかについては、この記事の最後で共有します。
背景
書籍の前半では、字句解析(lexing)と構文解析(parsing)から始めてASTを構築し、それを解釈するトップダウン方式で、jloxというトイ言語を実装しています。後半では、バイトコード構造から始めるボトムアップ方式で、同じ言語を再実装しています。
[画像: ソース行メタデータ、定数、コードを含むバイトコードチャンク]
出典: Crafting Interpreters, 第14章
バイトコードはチャンクに格納され、バイトのシーケンスを含みます。各バイトは、オペコード(opcode)またはオペコードのオペランド(operand)のいずれかです。したがって、命令は異なるバイト数を占める可能性があります。例えば、OP_RETURNは1バイトですが、OP_CONSTANTの後には、チャンクの定数プールへのインデックスを含むオペランドが続きます。
offset 0 1 2
byte OP_CONSTANT constant index OP_RETURN
\___________________/
one instruction another instruction
命令が実行時エラーを引き起こした場合、VMはバイトコードオフセットを、それを生成したソース行に変換する方法を必要とします。そのため、チャンクは行番号を格納する必要があります。
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
code: 00 01 00 02 01 00 03 01
line: 1 1 1 1 1 2 2 2
この設計はシンプルで、O(1)のルックアップを提供します。しかし、nバイトのバイトコードに対してO(n)のメモリを消費します。
上記の lines 配列を見ると、複数の連続するバイトが同じソース行から来ているという事実を利用できます。
ランレングスエンコーディング
ランレングスエンコーディングは、各行番号とその行に属する連続バイト数をペアで格納します。
line per byte: 1 1 1 1 1 | 2 2 2
encoded runs: (5, 1) | (3, 2)
count,line
nはバイトコードバイト数です。rは連続する行の実行数です。
ここでは、n = 8、r = 2です。一般に、1 <= r <= nです。最良の場合は、チャンク全体が1つのソース行から生成される場合で、r = 1です。最悪の場合は、バイトごとにソース行が変わる場合で、r = nです。ランレングスエンコーディングは、行テーブルのメモリをO(n)からO(r)に削減します。
線形探索
任意のオフセットの行を見つけるために、実行の長さを累積しながら実行をたどることができます。オフセット6の場合:
(5, 1) -> covers offsets 0..4
(3, 2) -> covers offsets 5..7 <- offset 6 is here
したがって、ランダムなルックアップは最悪の場合O(r)の時間を要します。チャンクを逆アセンブルする際に、バイトごとに新しい線形スキャンを実行すると、合計コストはO(nr)になります。rはnに等しくなる可能性があるため、最悪の場合はO(n²)です。
ワンパス走査
しかし、ランレングスエンコーディングは本質的に二次的ではありません。ディスアセンブラがオフセットを昇順に訪れる場合、現在の実行を指すカーソルを保持できます。各バイトと各実行は一度だけ訪問されるため、O(n + r)となり、r <= nなのでO(n)に単純化されます。
このアプローチは逐次走査に理想的ですが、任意のルックアップを改善するものではなく、O(r)のままです。エラーが発生してチャンクの途中のオフセットが得られた場合、より多くの情報を格納しない限り、実行を最初からスキャンする必要があります。
前者問題
実行長を記録する代わりに、実行の開始オフセットを記録できます。
offset: 0 1 2 | 3 4 | 5
line: 1 1 1 | 2 2 | 3
starting pairs: (0, 1) (3, 2) (5, 3)
各ペアは、このバイトコードオフセットから始まる後続バイトがこのソース行に属することを示します。本質的に、これは静的前者問題です。1
二分探索
ペアは開始オフセットでソートされているため、変更された二分探索によって静的前者問題を解決できます。
以下を検討してください:
starting pairs: (0, 1) (3, 2) (5, 3)
ターゲットオフセット4を与えると、4以下の最大の開始オフセットである(3, 2)を見つけます。
二分探索中、leftとrightはまだ正確な一致を含む可能性のある領域を区切ります。正確な一致が存在しない場合、それらは最終的に交差します。
target 4
v
starting offsets: 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はソートされたままです。
開始オフセットによるワンパス走査
二分探索は任意のルックアップに役立ちます。逐次的な逆アセンブリ中、カーソルは代わりに現在の開始ペアを指すことができます。次のペアの開始オフセットが現在のバイトコードオフセット以下になるたびに、カーソルを進めます。カーソルは前方のみ移動するため、各ペアを最大1回訪問し、全体でO(n)の走査を提供します。
これにより、開始オフセットデータ構造は2つの有用なアクセスパターンが得られます:
- ランダムオフセットには二分探索を使用:
O(log r)。 - 順序走査にはカーソルを使用: 全体で
O(n)。
優れた点は、二分探索とカーソルアプローチのどちらかを選択する必要がないことです。シナリオに応じてどちらかを選択できます。
ランタイム分析
| アプローチ | メモリ | ランダムルックアップ | 全体走査 |
|---|---|---|---|
| 1バイトあたり1行 | 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) |
他のVMのアプローチ
JVM
JVMのLineNumberTableは、基本的に同じ開始オフセット表現を使用しています。これは、各メソッドのCode属性のオプション属性であり、各(start_pc, line_number)エントリはソース行の開始位置を示します。1つの違いは、仕様がペアをソートすることを要求していないことです。HotSpotがライン番号を見つける必要がある場合、line_number_from_bciは線形探索を実行して前方を見つけます。
Lua
Luaは、書籍の実装と同様に、並列配列に行情報を格納します。各命令の正確な行番号を格納する代わりに、前の行番号からの1バイトの差分と、ルックアップスキャンを制限するための時折の絶対チェックポイント(ソース)を格納します(ライター、リーダー)。
例えば、(pc 2, line 300)の絶対チェックポイントが与えられた場合:
instruction: 0 1 2 3 4
source line: 10 10 300 310 314 (linesを格納する代わりに)
lineinfo: 0 0 ABS +10 +4 (line deltaを格納)
^
|-- deltaが1バイトを超える場合のチェックポイント
命令4の行を見つけるために、Luaは行300から開始し、次の差分を追加します: 300 + 10 + 4 = 314。
フットノート
- この問題について調査している際に、ハーバード大学のCS224: Advanced Algorithmsコースの最初の講義で静的前者問題として参照されていることを発見しました。講義では動的前者問題とword RAMモデルも紹介されています。私はこれらのトピックをざっと読んだだけですが、バイトコードVMまたは他の場所で実用的な用途に遭遇できることを願っています。↩