Présentation

Le problème de mappage de bytecode vers source se pose lors de la mise en œuvre d'un langage de programmation. Il s'agit de trouver un moyen de traduire les offsets de bytecode en lignes de code source correspondantes. Cela est nécessaire pour les débogages et les erreurs de runtime.

Contexte technique

Un bytecode est stocké dans un chunk, qui contient une séquence d'octets. Chaque octet est soit un opcode, soit un opérande appartenant à un opcode. Les instructions peuvent donc occuper différents nombres d'octets. Par exemple, OP_RETURN est un seul octet, tandis que OP_CONSTANT est suivi d'un opérande contenant un index dans le pool de constantes du chunk.

offset       0                 1                 2
byte     OP_CONSTANT     constant index      OP_RETURN
             ___________________/               |
                une instruction         une autre instruction

Pour résoudre le problème de mappage, nous pouvons stocker un tableau de lignes en parallèle avec le bytecode, de sorte que chaque octet corresponde à une ligne de code source. Cependant, cette solution prend O(n) mémoire pour n octets de bytecode.

Run-length encoding

Le run-length encoding stocke chaque numéro de ligne une fois, ainsi que le nombre d'octets consécutifs qui lui appartiennent. Cela réduit la table de lignes de O(n) à O(r) mémoire, où r est le nombre de séquences consécutives de lignes.

Par exemple, si nous avons les lignes suivantes : 1 1 1 1 1 | 2 2 2, nous pouvons les encoder comme suit : (5, 1) | (3, 2). Ici, n = 8 et r = 2.

Recherche linéaire et binaire

Pour trouver la ligne pour un offset arbitraire, nous pouvons parcourir les séquences de lignes tout en accumulant leurs longueurs. Cela prend O(r) temps dans le pire des cas. Cependant, si nous utilisons une recherche linéaire pour chaque octet, le coût total est O(nr), ce qui peut être O(n²) dans le pire des cas.

En revanche, la recherche binaire peut résoudre le problème de prédécesseur statique en O(log r) temps. Nous pouvons stocker les paires de lignes avec leurs offsets de début et utiliser une recherche binaire pour trouver la ligne pour un offset donné.

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
   }

Cette fonction dépend des invariants suivants : get_line est appelé uniquement pour un offset de bytecode valide, et line_starts reste trié car le bytecode est ajouté dans l'ordre.

Analyse de runtime

La complexité de la recherche linéaire est O(r), tandis que la complexité de la recherche binaire est O(log r). La complexité de la traversée séquentielle est O(n), ce qui est idéal pour la disassembly séquentielle.

En résumé, le mappage de bytecode vers source peut être résolu en utilisant le run-length encoding, la recherche linéaire et la recherche binaire. La recherche binaire est particulièrement utile pour les recherches aléatoires, tandis que la traversée séquentielle est idéale pour la disassembly séquentielle.