#dlang Dの新しい名前修飾【抄訳】

この記事は D’s Newfangled Name Mangling – The D Blog を自分用に翻訳したものを許可を得て公開するものである。

ソース中にコメントの形で原文を残している。自分の能力が微妙に届かず誤字や誤訳などが多いと思うので、気になったら Pull request を投げつけてくれると喜ぶ。

Rainer SchuetzeはVisual StudioのD言語プラグイン、Visual Dの作者でありメンテナーです。最近、彼はDMD 2.077.0でリリースされたDの新しい名前修飾アルゴリズムを実装しました。この投稿では、何故それが必要で、どのように行われるのかを説明します。

シンボル名修飾とは何か？

Dはソースコードをオブジェクトファイルにコンパイルし、リンカを使いオブジェクトファイルを実行可能バイナリファイルにまとめるという分割コンパイルモデルを採用しています。これによって以前にコンパイルされたオブジェクトファイルやライブラリを再利用し、ビルドプロセスの高速化ができます。 C/C++やFortranのような同じコンパイルモデルを持つ言語でも同じリンカが使われるため、異なる言語のオブジェクトファイルを直接組み合わせられます。

オブジェクトファイルのなかでは呼び出したりアクセスしたりするために定義された各関数とグローバル変数にシンボル名が割り当てられています。リンカはそのシンボル名を利用する事で、シンボルに関する知識を持たずに同名の定義の参照をつなぎ合わせます。たとえば、このCの関数宣言のシンボルは、

extern(C) const(char)* find(int ch, const(char)* str);

Cがシンボル名として普通の名前 find を使うため（プラットフォームによってはシンボルの最初に_が付きます）、関数の引数や返値の型について何もリンカに伝えません。後で引数の順番をこのとおり変えたとしても、

extern(C) const(char)* find(const(char)* str, int ch);

更新と新しい宣言を使うすべてのソースファイルの再コンパイルは行われず、リンカはそのオブジェクトファイルを幸運なことにもくっつけてしまいます。この場合、関数に渡されたキャラクタが文字列ポインタとして解釈され、逆も同じように解釈されてしまうため、たぶんプログラムはクラッシュします。

DやC++はこの問題を回避するためシンボル名に情報を追加します。つまり、シンボルが定義されたスコープ、関数の引数や返り値の型をシンボル名にエンコードします。リンカは相変わらずこの情報を解釈しませんが、オブジェクトファイルのビルドに使われる宣言が一致しない場合、リンクは未定義シンボルエラーで失敗します。たとえば以下のDの関数宣言は

module test;

extern(D) const(char)* find(int ch, const(char)* str);

_D4test4findFiPxaZPxaというシンボル名になります。 _DはDのソースのシンボルから生成されたシンボルを識別するプレフィックス、4test4findはtestモジュールのfindが「完全修飾名」にエンコードされたもの、FiPxaZPxaは整数引数（iと呼ばれます）とCスタイルの文字列ポインタ型Pxaを単に繋げた引数の型のエンコーディングです。 Zで関数の引数リストを終わらせて、返り値の型が後に続き、それはCスタイル文字列ポインタのPxaです。一方、

extern(D) const(char)* find(const(char)* str, int ch);

は引数の型が逆になっているところが異なる _D4test4findFPxaiZPxaにエンコードされます。エンコーディングは型とスコープの表現をノーマライズし、最小限のソースコードよりも短いシンボルを提供します。このエンコーディングが「名前修飾」と呼ばれます。

資料: extern(C)やextern(D)はリンケージ属性です。 Dにおいて関数が明示的なリンケージ属性なしで宣言される時、extern(D)がデフォルトになります。

Dでは@safe、nothrow、pure、@nogcのような関数の属性のいくつかはシンボル名へと修飾されます。理屈の上ではパラメータ名、ユーザ定義属性、契約を修飾に含めることもできますが、いまのところそれは過剰だと考えられています。

名前修飾が関数のバイナリインタフェース（引数がレジスタやスタックにどのように渡されるかなど）の不一致を検知したとしても、エラーはキャッチされないことに注意してください。たとえば構造体、クラス、その他ユーザ定義型はその名前のみが修飾され、その定義の変更をリンカは検知しません。

シンボルの修飾名は.mangleofプロパティからコンパイル時に利用することもできます。これはコンパイル時にシンボルの型リフレクションをするために活用されていました。これは情報により速く、便利にアクセスできる新しい__traitsの導入により不要になりました。たとえば、

__traits(getLinkage,symbol);

または

__traits(getFunctionAttributes, symbol);

従って、.mangleof の使用はデバッグ用途を除き推奨されません。

“demangler（逆修飾器）“で修飾プロセスを逆回しして、エンコードされたすべての情報をユーザが利用できる形にしたとしても、それは必ずしも正しいDのシンタックスになりません。上で取り上げた最初の宣言は以下のように逆修飾されます。

const(char)* test.find(int, const(char)*)

モジュール名testが関数名に足されています。

テンプレートシンボル

上の2つのfindの定義はDとC++両方に存在できるもののため、名前修飾以外にもリンク時にエラーを検出する方法がありますが、オーバーロードを表現する必要もあります。そのため少なくとも同じスコープの識別子の異なるオーバーロードを識別するために必要な情報を含む必要があります。

これは通常引数の型ごとに異なる関数や変数の定義をインスタンス化するテンプレートのことを考えてみても明らかなことです。 Dでは、テンプレートのインスタンス化の情報はシンボルの修飾名に追加されます。

式テンプレートは、式の遅延評価を使うメタプログラミングの一般的な例です:

module expr;

struct Mul(X,Y)

{

    X x;

    Y y;

}

struct Add(X,Y)

{

    X x;

    Y y;

}

auto mul(X,Y)(X x, Y y) { return Mul!(X,Y)(x, y); }

auto add(X,Y)(X x, Y y) { return Add!(X,Y)(x, y); }

関数テンプレートはコンパイラによって冠名テンプレートに書き下されます:

template mul(X, Y)

{

    auto mul(X x, Y y) { return Mul!(X,Y)(x, y); }

}

テンプレート名は修飾関数名expr.mul!(X,Y).mulの一部となり、auto返値型は推論されMul!(X,Y)になります。これによりシンボルは型XとYを3回参照します。このテンプレートを型doubleとfloatでインスタンス化したものの修飾名を逆修飾するとこのようになります。

expr.Mul!(double,float) expr.mul!(double,float).mul(double,float)

バージョン2.077以前のDMDの修飾プロセスは宣言の抽象構文木をたどり、遭遇したすべての型の修飾表現を出力します。以下のような積み重ね操作を考えてみましょう。

auto square(X)(X x) { return mul(x, x); }

auto len = square("var");

pragma(msg, len.square.mangleof);

// S4expr66__T3MulTS4expr16__T3MulTAyaTAyaZ3MulTS4expr16__T3MulTAyaTAyaZ3MulZ3Mul

pragma(msg, typeof(len).mangleof.length);

pragma(msg, len.square.mangleof.length);

pragma(msg, len.square.square.mangleof.length);

pragma(msg, len.square.square.square.mangleof.length);

pragma(msg, len.square.square.square.square.mangleof.length);

pragma(msg, len.square.square.square.square.square.mangleof.length);

pragma(msg, len.square.square.square.square.square.square.mangleof.length);

DMD 2.076以前では、これは28u, 78u, 179u, 381u, 785u, 1594u, 3212uという、ソースコード内の式が線形にしか増えていないのにもかかわらず加速的に増える修飾シンボル名の長さを出力します。これはMul!(Mul!(string, string), Mul!(string, string))のような型が組み合わさり、それが参照されるたびに完全な表現を繰り返し修飾するために起こる現象です。

上のsquareの呼び出しを12個繋げたものを作るとシンボルの長さは207,114まで増加します。さらに悪いことに、生成されるCOFF/64-bitのオブジェクトファイルは15MBを超えて大きくなりコンパイル時間は0.1秒から1分ほどに増加します。この時間のほとんどがコンパイル時にのみ使われるコードの生成に費やされます。

テンプレート関数から返されるヴォルデモート型は、型名の一部にテンプレート引数を含めた関数シグネチャをもつため似たような状態になる事があります。これも例よりも少ないコードで劇的なビルド時間の増加を見せます。

シンボル圧縮による解決

2016年の初期に、これらの長いシンボルを短くするいくつかの試みがなされました。

ある閾値を超えた時にシンボル名を切り詰め、代わりに完全なシンボルのチェックサムを追加する。これは既に255文字以上のシンボルを受け付けないOMFオブジェクトファイルフォーマットのDigitalMars Cコンパイラツールチェインのためにシンボルを出力する際にMD5ハッシュを用いて行われています。これの欠点はシンボルが逆修飾できなくなってしまい、リンカメッセージのシンボルが人間に理解できる名前に変換できなくなる事です。

シンボル名にバイナリ圧縮を適用する。完全なシンボル名の一部を辞書として、名前のなかの繰り返しをエンコードするスタンダードなやりかたです。これは通常の識別子セットに無い文字を使って位置と長さのペアをエンコードすることにより通常行われます。さらに、これは既にDMDがシンボルをOMFの225文字制限に合わせようとする際に（MD5ハッシュを適用する前に）使われていますが、これにもディスアドバンテージがあります。 ASCIIの範囲を超えた文字を使うとき、これはD言語のシンボル文字列として許容されるUTF8でエンコードされた文字と干渉します。また、コンソールがロケール特有のの文字エンコーディングと間違えてしまうことによってリンカの出力を壊してしまう可能性があります。これを回避するためにシンボルにbase64のようなバイナリからASCIIへの変換をかけてしまうと実際のシンボル名がますますわかりづらくなります。

修飾構文を拡張して既にエンコードされたエンティティへの参照をできるようにする。バイナリ圧縮と似ていますが、エンティティに構文組み込みの終端子があるので長さのエンコードが不要です。最も重要なエンティティは型です。これはここで説明する問題に影響するためC++が選んだ道です。 C++は名前修飾を標準化しておらず、コンパイラやプラットフォームが決めています。 GNU g++はItanium C++ ABI manglingを使っており、これはC++における上の例やヴォルデモート問題のようなコードに対してうまく動作します。 MicrosoftのVisual C++も繰り返し出現する型をエンコードできますが、引数リストの最初の10個の型までにエンコーディングを制限しているため非常に長い名前を生成します。

Dのシンボルの修飾に後者の案を適用した上での最初の試みは残念な結果に終わりました。結局、当時のそれらの実装はDMDフロントエンドの修飾器の、キャッシュした修飾型名の表現を組み合わせてより複雑な型を作るために再利用しているという小さな特徴を見逃していました。これによりキャッシュされた型名から繰り返しを探す事ができないでいました。

この時私はそれらの抜けを廃した修飾の実証バージョンを作り始めました。初期の結果は期待できるもので、私はシンボルの長さをさらに削減できないか探求しました:

完全修飾名は常にパッケージやモジュールの名前を含み、識別子は修飾名に繰り返し現れる傾向があります。

修飾名は同じモジュールまたはパッケージから来ることが多いので、1エンティティにエンコードするといい結果をもたらします。

Phobosランタイムライブラリのユニットテストはテンプレートをヘビーに使うコードのシンボルをたくさん含むため、それをユニットテスト候補としました。 Windowsのビルドのマップファイルでは、計測時点で127,172のシンボルが見つかりました。これが異なる修飾法での結果です:

後方参照	最大長	平均長
何もなし	416133	369
型	2095	157
型+識別子	1263	128
型+識別子+修飾名	1114	117

（これは現時点の実装で計測したもので、最終的な修飾法と一緒にはならないかもしれません。後方参照型に特殊文字を使いましたが、これはいい考えではありませんでした。 Dの修飾はすべてのプラットフォームで同じであると仮定していましたが、いくつかのプラットフォームでその文字は特殊な意味を持っていました。）

DMDにおいて識別子と型の区別は、後者が修飾に従ってマージされるためかなり簡単です。それでも修飾名とそれに関連したシンボルはさまざまな問題を生み出しました。関数引数のstringとして与えられた完全修飾名と、テンプレート引数で指定された型から関数の修飾名を構築するcore.demangleのmangleFuncです。これを実行時用に実装するには完全な修飾機構とイントロスペクション機能のコピーが必要で、それは現実的ではありません。上のPhobosの統計が示す限られた利益を考えた結果、修飾名のエンコードのアイデアは却下されました。

新しい修飾法についてまとめると:

後方参照は文字列Qでエンコードされ、同じ識別子や型の元の出現箇所の相対位置が続きます。これらの位置は最後の桁を小文字、それ以外の桁を大文字でエンコードするbase 26を参考にエンコードされます。そうすることで、ほとんどの後方参照は2、3文字になり、4文字になることは稀です。最後の桁だけ異なる形式にすることで次の文字を見ずに数値の終わりを識別できます。これによって曖昧さがなくなります。（Itanium C++ ABI修飾では、数字と文字を組み合わせて終端文字_を使うbase 36を使います。）

C++の修飾をエンコード可能なエンティティとして数えると修飾名が少し短くなりますが、修飾器がそれぞれの位置の動的リストを持ち続けなければならなくなります。現在の逆修飾器は十分な大きさの出力バッファをアロケートするようにはできていません。

シンボルの再エンコードなしに_Dプレフィックスを追加するために絶対位置ではなく相対位置が選ばれました。プラットフォームによってはアンダースコアが多かったりしますが、相対位置なら関係ありません。

修飾構文は型と識別子が同じ場所にあるのを許容するため、逆修飾器はそれが後方参照であっても2つを区別する必要があります。そのため参照位置のルックアップが逆修飾の際に必要となります。識別子は常に数値から始まり、型は常に文字から始まります。

Using Q for back references grabs the last free letter used to encode types, but there is at least one type defined in the mangling grammar that is not supposed to appear in a mangling anyway (namely TypeIdent), so it can be resurrected if the necessity appears. ¹

たとえば、上の式テンプレート型は以下のように修飾されます。

pragma(msg, len.square.mangleof);
// S4expr__T3MulTSQo__TQlTAyaTQeZQvTQtZQBb
//                ^^   ^^     ^^ ^^ ^^ ^^^ decode to:
//                |    |      |  |  |  |
//                |    |      |  |  |  +- 3Mul
//                |    |      |  |  +---- S4expr__T3MulTAyaTAyaZ3Mul
//                |    |      |  +------- 3Mul
//                |    |      +---------- Aya
//                |    +----------------- 3Mul
//                +---------------------- 4expr

長さは後方参照を使わない時の78から39になっています。結果の長さは23, 39, 57, 76, 95, 114, 133と線形に増えます。 squareの呼び出しの12連鎖は207,114文字から247、つまり800分の1以下にまで小さくなります。

上で言及していた後方参照を使った修飾のmangleFuncの実装はどうなったのでしょうか。完全修飾名は型（たとえば構造体テンプレートの引数として）を含んでいないはずですが、修飾名の識別子は関数型に再び現れることがあります。これは逆修飾器を“Design by Introspection” (DbI)（Andrei Alexandrescuの作ったものです）を使って拡張することで解決されました。

Demangle構造体という、フックを提供する構造体をパラメータ化するテンプレートを作る。

    struct NoHooks {}  // supports: static bool parseLName(ref Demangle); ...
    private struct Demangle(Hooks = NoHooks)
    {
    Hooks hooks;
        // ...
        void parseLName()
        {
            static if(__traits(hasMember, Hooks, "parseLName"))
                if (hooks.parseLName(this))
                    return;
                // 普通のデコード...
        }
    }

頻出する識別子を適切な後方参照に置き換えるフックを作る。

    struct RemangleHooks
    {
        char[] result;
        size_t[const(char)[]] idpos;
        // ...
        bool parseLName(ref Demangler!RemangleHooks d)
        {
            // これまでのresult[]をフラッシュする
            if (d.front == 'Q')
            {
                // 後方参照を再エンコード...
            }
            else if (auto ppos = currentIdentifier in idpos)
            {
                // 後方参照を識別子 *ppos にエンコード
            }
            else
            {
                idpos[currentIdentifier] = currentPos;
            }
            return true;
        }
    }

修飾名と先の型（core.demangleにはデコードする能力があります）を組み合わせて、フックされた逆修飾器を実行します

    char[] mangleFunc(FuncType)(const(char)[] qualifiedName)
    {
        const(char)mangledQualifiedName = encodeLNames(qualifiedName);
        const(char)mangled = mangledQualifiedName ~ FuncType.mangleof;
        auto d = Demangle!RemangleHooks(mangled, null);
        d.mute = true; // 逆修飾は出力されません
        d.parseMangledName();
        return d.hooks.result;
    }

新しい修飾法は健全か？

後方参照は既存の修飾法を拡張した修飾法でエンコードされます。残念ながら、既存のものは曖昧さがDのイシュートラッキングシステムに報告されており、まだ見つかっていない問題もあるでしょう。 core.demangleの逆修飾器はPhobosのユニットテストの未修正のシンボルのうち3%ほどを受け付けず、15%ほどが部分的にしか逆修飾されませんでした。

修飾法の変更はツール（逆修飾器、デバッガ）の更新を必要とするので、既に複雑で脆弱な定義への追加の健全性を検証するのは大変です。とにかく、それらを取り除くいい機会でした。

既存の定義の再調査が必要でした。機械的に調査を行うために、ウェブサイトから得られる修飾の仕様をbisonパーサジェネレーターが解釈できる文法に変換しました。 BisonはLALR(1)パーサテーブル、基本的には修飾されたシンボルをスキャンしつつ、文字とそのサクセサを見るだけで文字が前のエンティティのものか新しいエンティティの最初かを決定できるものを作ることができます。文法の処理中に競合が報告された時は、より大きなコンテキストで解決できることもありますが、本当の問題や望ましくない複雑さのヒントになります。手動パーサ制御フローを表す疑似トークンを追加することで競合を回避できます。

このgistは後方参照のないDの修飾スキームの文法です。これはまだBisonで走らせるといくつか競合がありますが、そのうちの1つが本当の定義の曖昧さです。後方参照を文法に追加しても競合は発生しませんでした。

加えて、core.demangleは曖昧さのあるものを除くすべてのシンボルで動作するよう修正されました。

影響

std.traitsの実装のうちいくつかはリンケージの決定などのコンパイル時プロパティのintrospectのためにシンボルの修飾を利用していました。これはシンプルになった逆修飾器を使って行われました。後方参照の導入により、これらはシンプルなシンボル名を除き何もする必要がなくなりました。 core.mangleFuncを使った方法はうまくいきそうに見えますが、CTFEで逆修飾を実行する必要があるためコンパイルを顕著に遅くします。幸運にも、修飾で得られるすべての情報をカバーする新しい__traitsが追加されました。

ほとんどのユーザはオブジェクトファイルや実行ファイルのサイズが小さくなること以外の変化に気付くことはないでしょうが、新しい修飾法はリンカやデバッガなどの外部ツールにとっての破壊的変更になるかもしれません。これらは動作はしますが、アップデートされるまでは逆修飾されたものの代わりに新しい修飾名を見ることになると思うので心の準備をしておいてください。

レビューをしてくれたMike Parker、Walter Bright、Steven Schveighofferに感謝します。

ここ意味が取れなかった ↩︎