バイトコードからソースコードへのマッピング

Robert Nystrom の著書『Crafting Interpreters』の第14章の課題に取り組んでいる際に、この問題に遭遇しました。注: 本番環境の VM はより洗練されていますが、この記事の最後で JVM や Lua のような他の VM との類似点について共有します。 背景 この本の前半では、字句解析と構文解析から始めて AST を構築し、それを解釈することで、トイ言語 jlox をトップダウンで実装しています。後半では、バイトコード構造から始めて、ボトムアップで同じ言語を再実装しています。 Source: Crafting Interpreters, chapter 14 バイトコードはチャンクに格納され、チャンクはバイトのシーケンスを含みます。各バイトは、オペコードであるか、オペコードのオペランドのいずれかです。したがって、命令は異なるバイト数を占める可能性があります。例えば、OP_RETURN は 1 バイトですが、OP_CONSTANT にはチャンクの定数プールへのインデックスを含むオペランドが続きます。 offset 0 1 2 byte OP_CONSTANT constant index OP_RETURN ___________________ | 1つの命令 別の命令 命令が実行時エラーを引き起こした場合、VM はバイトコードオフセットを生成したソース行に逆変換する方法が必要です。そのため、チャンクはソース行を格納する必要があります。簡単な解決策は、バイトコードと並列に 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) のメモリを消費します。上記の 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) -> オフセット 0..4 をカバー (3, 2) -> オフセット 5..7 をカバー <- オフセット 6 はここ したがって、ランダムな検索は最悪の場合 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)。 美しさは、二分探索とカーソルアプローチのどちらかを選択する必要がないことです。シナリオに応じてどちらかを選択できます。 実行時分析 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-case 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) 他の VM のアプローチ JVM JVM の LineNumberTable は、実質的に同じ開始オフセット表現を使用しています。これは各メソッドの Code のオプション属性であり、各 (start_pc, line_number) エントリはソース行が始まる場所を示します。1 つの違いは、仕様でペアがソートされていることを要求していないことです。HotSpot が行番号を見つける必要がある場合、line_number_from_bci は線形検索を実行して先行者を見つけます。 Lua Lua は、本の С реализацииに似た並列配列に行情報を格納します。ただし、すべての命令の正確な行番号を格納する代わりに、前の行番号からの 1 バイトの差分と、検索スキャンを制限するための時折の絶対チェックポイント (source) を格納します。 例えば、絶対チェックポイントが (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 を格納) ^ |-- checkpoint when delta exceeds one byte 命令 4 の行を見つけるために、Lua は行 300 から開始し、次の差分を加算します: 300 + 10 + 4 = 314。 脚注 この問題について調査している際に、Harvard の CS224: Advanced Algorithms コースの最初の講義で、静的先行問題として参照されていることを発見しました。この講義では、動的先行問題とワード RAM モデルも紹介されています。それらのトピックはざっと目を通しただけですが、バイトコード VM やその他の場所で実用的な用途に出会えることを願っています。↩