Rustのv0 mangling scheme

昨年書きかけていた記事を発掘して、公開しないよりはしたほうがいいと思い、一部加筆修正して公開しました。

はじめに

この記事はRustの名前マングル方式 (name mangling scheme)についてまとめた記事です。 名前マングルとは、コンパイラが行うシンボル名の変換プロセスのことで、関数などをアセンブリとして出力する段階で行われます。 基本的に、名前空間などをサポートするコンパイラでは名前マングルを行います。

また、GDBなどのツールにはデマングラが搭載されており、マングルする前の名前を表示してくれます。

以下は、Rustのマングルの例になります。

godbolt.org

余談ですが、この記事を書いた経緯は、GCC Rust 上に v0マングル方式を実装する機会があったことと、マングルに関する日本語の文献がほとんどなかったからです。また、自分用ですがオンラインのデマングルツールを作ったので興味のある方は使ってみてください。

Rustのマングル方式

Rustには以下の2種類のマングル方式があります。

  • Legacy mangling scheme: Rustが始まってから現在でも使われている方式。(_Zで始まる)
  • v0 mangling scheme: 2018年にRFCとして提案された方式。(_Rで始まる)

この記事で解説するのは、v0 mangling schemeです。legacyは扱いません。

Legacyの欠点

legacyはこれまで長らく利用されていましたが、様々な問題を抱えていました。 例えば以下のような問題があります。

  • マングル後のシンボル名に$が含まれるが、一部のプラットホームでサポートされていない
  • コンパイラ内部の情報に依存している箇所が多い
  • 一部だけがItaniumABIに準拠しており一貫性がない
  • ジェネリックな引数をとる関数について、マングル後のシンボル名から、一部の情報(例えば引数の型)がとれない

v0はこれらの問題を解決、緩和することができ、サードパーティのツールや他のコンパイラがRustバイナリを扱いやすくなることが期待されます。

v0の基本

v0マングルの例として、最も簡単なケースを考えます。 以下の関数fooをマングルすると_RNvNtCs1234_7mycrate3foo3barになります。

// mycrate.rs
mod foo {
  fn foo() {}
}

それでは、このシンボルからマングル前のパス mycrate::foo::barを復元してみましょう。

1. 最初の_Rを取り除く

最初の_RはRustのv0マングル方式を表すプレフィックスなので取り除きます。

=> NvNtCs1234_7mycrate3foo3bar

2. 外側のNv...3barを取り除く

NvのNは名前空間を表します。vは特に意味はありません。 3barの3は直後の識別子の文字数を表します。barは3文字なので3なわけです。

=> NvNtCs1234_7mycrate3foo3bar

3. 外側のNt...3fooを取り除く

先程の手順と同様にして、識別子fooが得られます。これを先程のfooの前に繋げると、foo::barが得られます。

=> Cs1234_7mycrate

4. クレート名を得る

Cはクレートを表し、s1234_はcrate disambiguatorです。 実装上、crate disambiguatorにはコンパイラが管理するユニークな数字が入るようですが別になくても良いです。

7mycrateの部分は先程と同じように識別子を表します。この名前をfoo::barと繋げて、最終的にmycrate::foo::barが得られます。

v0の規則

Rustでは、先程見たようなクレート名から始まるパス mycrate::foo::bar を、正規パス (caninical paths) と言います。fooやbarなどの、パスの単位をセグメントと言います。マングルを行う際に必要となるのは、正規パスと単相化 (monomorphization) の際の型情報になります。単相化とは、ジェネリックスなコードを具体的な型に具体化するプロセスのことで、fn foo<T>(_: T);の場合、[T→i32]などが具体化の型情報になります。

マングルする際は正規パスの最初のパスセグメントから順に内側からシンボルを生成し、デマングルする際はシンボルを外側から見ていくため、終端のパスセグメントから正規パスを構築することになります。

v0のマングル規則はRust RFCにある規則表で定義されています。BNF記法に慣れている方はこちらの方がわかりやすいと思うので、参照してください。

Unicodeの識別子

先程まで見てきた、fooやmycrateは英数字の識別子でした。 Rustは Unicode Standard Annex #31 に準拠しており、漢字やキリル文字などの文字を識別子として使うことができます。こういった文字は、プラットホームやツールの問題により、英数字とアンダースコアにエンコードされることが好ましいです。

v0ではこのエンコードに Punycode の変換規則を利用します。 Punycodeは-(ハイフン)を含むため、厳密にはそのままでは利用可能ではないですが、普通の人は気にしなくても良いでしょう。

Punycode を使うとgödelはu8gdel_5qaになります。先頭のuがPunycodeで変換された識別子であることを表します。 (詳しい人は気づくかもしれませんが、gdelは RFC3492 の basic string で、 delimtier がアンダースコアになっています)

余談ですが、Unicode の識別子を Punycode でマングルするアイデアは Swift のマングル方式を参考にしているようです。

Identifiers that contain non-ASCII characters are encoded using the Punycode algorithm specified in RFC 3492, with the modifications that _ is used as the encoding delimiter, and uppercase letters A through J are used in place of digits 0 through 9 in the encoding character set. The mangling then consists of an 00 followed by the run length of the encoded string and the encoded string itself. For example, the identifier vergüenza is mangled to 0012vergenza_JFa. (The encoding in standard Punycode would be vergenza-95a)

(https://github.com/apple/swift/blob/9f225d6fa89cad101a8ced83eff08dee8cf17baf/docs/ABI/Mangling.rst#identifiers より引用)

複雑なケース: ジェネリックス

まずは少し複雑な例として以下のようなジェネリック関数を考えます。

std::mem::align_of::<f64>

ジェネリック関数は、パスとジェネリック引数に分けて扱われます。すなわち、今回のケースではパスstd::mem::align_ofと型f64になります。

前者はNvNtC3std3mem8align_ofにマングルされます。

f64はdにマングルされます。基本型の場合はアルファベット1文字で、ユーザー定義の型の場合は通常通りマングルします。

つづいて、マングルされたパスと型を<パス> = I<パス><ジェネリック引数>Eという規則に基づいて組み立てると、 INvNtC3std3mem8align_ofdEになります。

最後にプレフィックスの_Rを追加して、_RINvNtC3std3mem8align_ofdEが得られます。

複雑なケース: impl と trait

traitやimpl内で定義された関数をマングルする場合はもっと複雑になります。

考えるべきケースは以下の2つになります。

  1. 型に固有のimpl (inherent impl): impl S { ... }
  2. traitのimpll: impl T for S { ... }

inherent impl

trait implは以下のような impl のコードを表します。

impl Trait for Type { fn method() {} }

M <impl対象の型> <メソッドのパス>と変換されます。

trait impl

trait implは以下のような impl のコードを表します。

impl Trait for Type { fn method() {} }

ここでメソッド method の正規パスは.. ::<Type as Trait>::methodの形式になります。

<Type as Trait>の部分は<path> = X <Type><Trait>の規則が適用され、 <Type as Trait>::methodはNvX <Type><Trait><method>としてマングルされることになります。(Nvのvは任意)

例えば、以下のコードの変数MSGをマングルしてみます。

struct Foo<T>(T);

impl<T> From<T> for Foo<T> {
  fn from(x: T) -> Self {
    static MSG: &str = "...";
    panic!("{}", MSG)
  }
}

マングルすると_RNvNvXINtC7mycrate3FoopEINtNtC3std7convert4FrompE4from3MSGというシンボルが得られます。これを少しわかりやすくすると以下のようになります。

_R (プレフィックス)
Nv // MSG
- Nv // from
  - X // <Foo<T> as From<T>>
    - INtC7mycrate3FoopE // Foo<T>
    - INtNtC3std7convert4FrompE // From<T>
  - 4from // method name
- 3MSG

また、この規則では、2つのimplが同じシンボル名にマングルされる場合があります。 以下の例では、2つのMSGが_RNvNvXINtC7mycrate3FoopEINtNtC3std7convert4FrompE4from3MSGにマングルされてしまいます。 このような場合に備えて、コンパイラはXの直後に impl-path という impl ノードへの正規パスと disambiguator を挿入することになっています。実装上、この disambiguator は、 AST (HIR) の impl ノードのIDが使われることが想定されています。

struct Foo<T>(T);

impl<T> From<T> for Foo<T> {
  default fn from(x: T) -> Self {
    static MSG: &str = "...";
    panic!("{}", MSG)
  }
}

impl<T: Default> From<T> for Foo<T> {
  fn from(x: T) -> Self {
    static MSG: &str = "123";
    panic!("{}", MSG)
  }
}

これによって、以下のように２つのシンボルが区別できるようになります。

_RNvNvXs2_C7mycrateINtC7mycrate3FoopEINtNtC3std7convert4FrompE4from3MSG
_RNvNvXs3_C7mycrateINtC7mycrate3FoopEINtNtC3std7convert4FrompE4from3MSG
       <----------><----------------><----------------------->
        impl-path      selfの型            トレイㇳ名

Instantiating crate

例えば、グローバル名前空間にジェネリック関数fn foo<T>()が定義されている場合、 2つの異なるクレートがfn foo<i32>()に単相化しコード生成することがよくあります。 しかし、これまで述べた方式では、2つのクレートで同じシンボル名を持つ関数が生成され、シンボルが衝突してしまいます。 このような衝突を避ける仕組みとして、instantiating crateがあります。これにより各クレートでマングルされたシンボル名の末尾にそのクレート名を追加し、シンボルの衝突を避けることができます。

詳しくはソースコード中に細かい説明があります。

参考