📛

Oxc Minifierの変数マングル仕組み

に公開
JavaScript
compiler
Oxc
tech

🌐 Read this post in English

この記事ではOxc Minifierの変数マングル処理の仕組みを解説します。

変数マングルとは？

まず、そもそも変数マングル (mangling)が何かを説明しましょう。

変数マングルは、変数名を短いものに置き換えることでコードサイズを削減する処理で、ミニファイ(minify)の処理の一種です。

例えば、

const foo = 1;
export function bar(baz) {
  return foo + baz;
}

というコードを

const a = 1;
export function bar(b) {
  return a + b;
}

に変換します。
この例だと、コードを8文字削減できています。

大雑把な説明

満たすべき性質と基本戦略

変数マングルにおいて最も重要なことはコードの意味を変えないことです。例えば、同じスコープにある複数の変数を同じ名前に変更すると、コードの意味が変わってしまいます。より具体的には以下のような変換はしてはいけません。

// 入力
const foo = 1;
const bar = 2;
export const baz = foo + bar;

// 出力
const a = 1;
const a = 2; // !
export const baz = a + a;

一方、変数マングルの目的はコードを短くすることです。Oxc Minifierでは、gzipなどのデータ圧縮後のサイズを小さくすることを重視しています。

そのために、変数マングルでは意味を保ちつつ、以下のような戦略で変数名を変更します：

  1. できる限り同じ変数名を使い回す
  2. できる限り短い変数名を使用する

ここからは、以下のコードを例に、Oxc Minifierがこれらをどのように実現しているかを説明します。

export function demo(input, flag) { // スコープ: SA
  let total = input;
  if (flag) { // スコープ: SB1
    let left = total + 1;
    use(left);
  }
  if (!flag) { // スコープ: SB2
    let right = total + 2;
    use(right);
  }
  return total;
}

ここでSAはdemo関数の関数本体のスコープ、SB1とSB2はそれぞれ2つのifブロックのスコープです。

ステップ1: 変数の生存区間の計算

まず、各変数の生存区間 (symbol liveness) を計算します。変数の生存区間とはその変数が参照できるスコープの範囲です（注：「ある地点以降で変数の値が使用される可能性がある範囲」ではありません）。例における各変数の生存区間は以下の通りです。

変数名 生存区間
input {SA}
flag {SA}
total {SA, SB1, SB2}
left {SB1}
right {SB2}

ステップ2: スロットの割り当て

ここで、スロットという概念を導入します。スロットは変数マングル後に同じ変数名を割り当てることのできる変数の集まりです。例えば、変数aとbが同じスロットに割り当てられれば、変数マングル後の名前も同じになります。

では、スロットに各変数を割り当てていきます。浅いスコープで宣言されているものから順に割り当てます。この際、生存区間が重複しない限りは既に割り当てられているスロットに追加で割り当てます。これにより、戦略1の「できる限り同じ変数名を使い回す」を達成します。

浅いスコープで宣言されている変数から順に割り当てているのは、深いスコープで宣言された変数ほど生存区間として取り得る範囲が狭いためです。直感的には、あとから深いスコープの変数を割り当てるときには、先に割り当てた変数と生存区間が重複しにくく、既存のスロットを再利用しやすくなると考えられます。

例における各スロットに割り当てられる変数は以下の通りです。

スロット そのスロットに割り当てられた変数
0 input, left, right
1 flag
2 total

inputはスコープSAでのみ生存していて、スコープSB1とスコープSB2では生存していません。そして、leftとrightはそれぞれスコープSAで生存していません。そのため、これらは同じスロットに割り当てられています。別の言い方をすると、leftとrightがinputをシャドーしても問題ないので、leftやrightはinputと同じスロットに割り当てられる、ということです。

ステップ3: 変数名の生成

今度は各スロットに対する変数名を生成します。これにより、戦略2の「できる限り短い変数名を使用する」を達成します。

変数名にはアルファベットと数字と_と$を利用します。これらの文字は、変数名に使えるもののうち、UTF-8において1バイトで表せるものです。一方、それ以外の文字はUTF-8では2バイト以上になるため、コードサイズの観点では1バイトの文字を複数使う場合に対する利点がありません。また、JavaScriptのコード自体にもアルファベットや数字が頻繁に現れるため、gzipなどで圧縮した際にもこれらの文字を使うほうが有利になります。

これらの文字は、etnriaoscludfpmhg_vybxSCwTEDOkAjMNPFILRzBVHUWGKqJYXZQ$1024368579の順に使用されます（数字は2文字目以降にのみ使用）。これは、いくつかのライブラリのバンドル後のコードをミニファイした結果を結合したテキストにおける各文字の出現頻度によって並んでいます。この順は、ミニファイされたコードにおける文字の出現頻度を近似し、最終的なコードの圧縮効率を高めることを狙っています。

次に、スロットに属する変数のコードでの出現回数が多い順に、使用する変数名の文字数を決めます。例えば、最も出現回数の多いスロットは1文字、100番目に出現回数の多いスロットは2文字です。その後、スロットの変数の出現順にその文字数を満たす変数名を割り当てます。例における各スロットの変数名は以下の通りです。

スロット 変数名 そのスロットに割り当てられた変数
0 e input, left, right
1 t flag
2 n total

こうして、最終的に以下のコードが得られます。

export function demo(e, t) {
  let n = e;
  if (t) {
    let e = n + 1;
    use(e);
  }
  if (!t) {
    let e = n + 2;
    use(e);
  }
  return n;
}

数学の概念を使用した各アルゴリズムの補足

ここからは、より詳しく知りたい方向けに、数学の概念を持ち込んでさらに踏み込んだ説明をしていきます。

スコープと変数の生存区間について

JavaScriptのスコープは、木構造になっています。モジュールのスコープが存在して、そのモジュールのスコープの子として、モジュールに含まれるスコープが存在します（例えば、ifブロックのスコープ）。

変数の生存区間はこの木上の部分木です。ある変数が2つのスコープで参照可能なら、スコープ木上でそれらを結ぶ経路にあるスコープでも、その変数を参照できます。

let foo = 0;
{
  // ここでもfooは参照できる
  // 仮にここにfooが宣言されていると、
  // 下のブロック内でもfooが参照できない

  {
    console.log(foo)
  }
}

スロットの割り当てアルゴリズム

スロットの割り当てでは、全ての変数をできる限り少ないスロットに割り当てることが目標です。

実はこれは最小の色数で頂点彩色をする問題（グラフ彩色問題）として見ることができます。グラフの頂点を「変数」とし、生存区間が重複する2変数の間に辺を張ります。そして、それぞれの色を「スロット」に対応させます。例に対するこのグラフは以下のようになります。

さらに、このグラフは部分木の交差グラフでもあります。変数の生存区間が部分木になっていて、辺がその生存区間の交差であるからです。部分木の交差グラフは弦グラフ (chordal graph) であることが知られています。

一般のグラフについて、そのグラフ彩色問題はNP困難です。しかし、弦グラフでは多項式時間で最適な彩色を求められることも知られています。また、弦グラフでは、彩色に必要な最小の色数が最大クリークの大きさと一致します。今回のグラフでは、これは「あるスコープで同時に生存している変数の最大数」に対応します。

そして、浅いスコープで宣言された変数から順に処理する順序は、このグラフにおけるPerfect Elimination Ordering（完全消去順序）の逆順になっています。弦グラフでは、この順序で貪欲に彩色することで、最小の色数で彩色できることが知られています。つまり、Oxc Minifierのスロット割り当ては、このモデルのもとでは必要最小限のスロット数を実現できます。

最後に

実際は元の変数名を維持しないといけないケースがあったりですが、基礎となる仕組みはこのようになっています。

最初から全てがわかっていたかのように説明していますが（特に弦グラフのところ）、実際にはそうではないです。直感を元に書いたコードが結果的に完全消去順序の逆順になっていて、あとから理論的に理解しようとしたら、そのことに気づいたというのが真実です🙂

後半のより詳しい説明のところは友人に確認してもらいました。ありがとうございます。

Discussion