読者です 読者をやめる 読者になる 読者になる

Rustマクロの衛生性はどのように実現されているか(1/2) 識別子に関する衛生性

Rust

概要: Rustマクロは2つの意味で衛生的である。その衛生性の説明とともに、それを実現するためのコンパイラの仕組みを説明する。

Rustマクロの2つの衛生性

Rustマクロ (ja) は次の2つの意味で衛生的(hygienic; 健全ともいう)である。

  • マクロ内で導入される変数名と、マクロ呼び出し側の変数名が衝突しない。(Lispマクロの意味での衛生性)
  • 構文の優先順位の違いによる非直感的な挙動が発生しない。

この記事では、識別子に関する衛生性を説明する。

識別子に関する衛生性とは

次のようなプログラムが直感的な動作をするのが、識別子に関する衛生性である。

macro_rules! copy_swap {
    ($x:expr, $y:expr) => {{
        let t = $x;
        $x = $y;
        $y = t;
    }};
}
fn main() {
    let (mut r, mut s, mut t, mut u) = (30, 40, 50, 60);
    copy_swap!(r, s);
    println!("{}, {}", r, s);
    copy_swap!(t, u);
    println!("{}, {}", t, u);
}

ここで、 copy_swap!(t, u) を単純に展開するようなマクロ展開器の場合、以下のようなコードが生成されてしまう。

{
    let t = t;
    t = u;
    u = t;
}

このコードを実行するとt=u=60になってしまうが、Rustではそうはならず、あたかもマクロ呼び出しの実引数がレキシカルスコープを持っているかのように振る舞う。

構文文脈によるローカル変数名の衛生性の実現

衛生性を実現する基本アイデアは、syntax::ast::Identの定義を見るとわかる。

/// An identifier contains a Name (index into the interner
/// table) and a SyntaxContext to track renaming and
/// macro expansion per Flatt et al., "Macros That Work Together"
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub struct Ident {
    pub name: Symbol,
    pub ctxt: SyntaxContext
}

なお、ここに出てくる Symbol はinternされた文字列である。

つまり、この SyntaxContext というもので、同名の識別子を区別するというのが基本アイデアである。

SyntaxContextの実体

結論から言うと、 SyntaxContext は、 Vec<Mark> をinternしたものと考えてよい。ただし、 Mark はマクロ呼び出しを識別するための整数である。

syntax::ext::hygiene::SyntaxContext は整数だが、これはinternパターンで特定の syntax::ext::hygiene::SyntaxContextData に紐付けられている。

#[derive(Copy, Clone)]
pub struct SyntaxContextData {
    pub outer_mark: Mark,
    pub prev_ctxt: SyntaxContext,
}

またここに出てくる syntax::ext::hygiene::Mark も整数である。これはgensymパターンで、マクロ展開ごとに異なる値が割り振られるようになっている。

SyntaxContext は次の2つの方法で生成される。

生成済みの構文文脈全体は根つき木をなすが、木そのものには特に興味はない。

文脈の追加と削除

文脈の追加と削除はsyntax::ext::hygiene::SyntaxContext::apply_markで行う。 ctx.apply_mark(mark) は以下を返す:

  • ctxmark で終わるなら、それを削除した文脈を返す。
  • それ以外の場合は、 ctxmark を追加した文脈を返す。

apply_mark を全ての識別子に適用する処理が syntax::ext::expand::Marker に実装されている。これは主に、次の2箇所で使われている。

ローカル変数の衛生性の実現例

以下のようなプログラムを考える。

macro_rules! foo {
    ($x:ident) => {
        let mut x = 0;
        $x = x;
        x = 2;
    }
}

fn main() {
    let mut x = 1;
    foo!(x);
    println!("{}", x);
}

これは0を出力する。

以下、これがどのように展開されるかを、擬似的なRustコードを用いて説明する。

まず、 macro_rules! はマクロ展開であるから、これにmarkが割り当てられる。これを A とおく。すると、 macro_rules! 内の解析前に、識別子には以下のように文脈が付与される。

macro_rules! foo {
    ($x:ident) => {
        let mut x@A = 0;
        $x = x@A;
        x@A = 2;
    }
}

macro_rules! はASTに展開されず、単に内部で構文拡張DBに記録されるだけなので、展開後の後処理で上の文脈が削除されるわけではない。

これを踏まえてmain内のマクロ呼び出しが展開される。まずこの foo! の呼び出しにmarkが割り当てられる。

fn main() {
    let mut x = 1;
    /* Mark B */
    foo!(x);
    println!("{}", x);
}

これに基づいて、まず foo! の呼び出し中に出現する識別子に B が付与される。

fn main() {
    let mut x = 1;
    @B[foo!(x@B);]
    println!("{}", x);
}

この状態で foo! が展開される。

fn main() {
    let mut x = 1;
    @B[
        let mut x@A = 0;
        x@B = x@A;
        x@A = 2;
    ]
    println!("{}", x);
}

展開後の列に対する後処理として B が追加または削除される。

fn main() {
    let mut x = 1;
    let mut x@A@B = 0;
    x = x@A@B;
    x@A@B = 2;
    println!("{}", x);
}

これにより識別子の衝突が回避される。

非ローカルなアイテムの衛生性を実現する $crate 置換

ここまで紹介した構文文脈は、ローカル変数の衛生性の実現に利用される。非ローカルなアイテムについては、マクロ定義で $crate を用いることで解決する。これは、 $crate が書かれた時点のcrateの最上位モジュールを指す。

$crate は、ドル記号の構文解析時に特別扱いされ、 $crate という特殊な名前をもった識別子として定義される。 (syntax::parse::parser 2558行目)

この $crate は名前解決時に発見され、この識別子が定義された当時のmarkからcrate名が復元される。(rustc_resolve 2426行目

まとめ

Rustマクロの2つの衛生性のうち、識別子の衝突を防ぐ衛生性は、識別子に文脈を付与することによって巧妙に実現されている。

Rustは構文解析をしてからマクロを展開する

Rust

C言語では字句解析の次が前処理で、前処理のあとに構文解析が行われるが、Rustでは構文解析が終わってからマクロが展開される。

より正確に説明すると、Rustのコンパイルはcrate単位で行われ、crateのコンパイル処理の冒頭部は以下の2フェーズに分かれている。

  1. crateの冒頭から字句解析と構文解析を行う。 mod foo; のようなアイテムがある場合、そのインクルード処理はこのフェーズの中で行われる。これにより1つのcrateに対応する単一のAST(抽象構文木)が生成される。
  2. 構文拡張を展開する。構文拡張にはマクロ呼び出しや #[cfg(...)]#[derive(...)] などが含まれている。これによりASTから構文拡張が取り除かれる。

マクロのスキップ

初回の構文解析では、マクロは展開されないままの状態で抽象構文木に格納される。抽象構文木の定義に、マクロをそのまま格納するための構築子が含まれている。

この初回の構文解析では、「マクロ呼び出しの終端はどこか」「マクロ展開後の構文要素の種類は何か」を確定させる必要がある。

終端を探す

Rustの構文には、「マクロ呼び出しとその展開を含む全ての構文要素は、括弧 ()[]{} の対応が取れている」という重要な制約がある。そのため、正確な構文がわからなくても、括弧の対応を追うことで、マクロの終端を決定することができる

このため、マクロは「1トークン」を処理することはできず、かわりに「1トークンツリー」単位で処理するようになっている。トークンツリーは、以下のうちの1つである。

構文要素を確定する

構文要素は、マクロ呼び出しの位置により、パターンアイテムトレイトアイテム実装アイテムのいずれに展開されるかが、展開前に確定する。

ExprKind::Mac(Mac) … マクロは式に展開される。(文脈によっては、0個か1個の式に展開される)

macro_rules! my_macro {
    ($a:expr) => {$a + 1}
}

fn main() {
    println!("{}", my_macro!(10));
    println!("{}", my_macro![10]);
    println!("{}", my_macro!{10});
}

PatKind::Mac(Mac) … マクロはパターンに展開される。

macro_rules! my_macro {
    ($a:pat) => {($a, _)}
}

fn main() {
    let my_macro!(x) = (11, 20);
    println!("{}", x);
    let my_macro![y] = (11, 20);
    println!("{}", y);
    let my_macro!{z} = (11, 20);
    println!("{}", z);
}

TyKind::Mac(Mac) … マクロは型に展開される。

macro_rules! my_macro {
    ($a:ty) => {($a, u32)}
}

fn f(x: my_macro!(u8), y: my_macro![u8], z: my_macro!{u8}) {
    println!("{:?}, {:?}, {:?}", x, y, z);
}
fn main() {
    f((1, 2), (3, 4), (5, 6));
}

StmtKind::Mac(P<(Mac, MacStmtStyle, ThinVec<Attribute>)>) … マクロは0個以上の文(let束縛またはアイテム定義または式文)に展開される。

macro_rules! my_macro {
    ($($a:tt)*) => {$($a)*}
}

fn main() {
    // (), []の場合は直後にセミコロンが必要だが、 {}の場合は不要。
    // このセミコロンは展開後の文の挙動に影響を与える
    my_macro!(let x = 10;);
    my_macro!{println!("{}", x + 1);}
    my_macro![println!("{}", x + 1)];
}

ItemKind::Mac(Mac) … 0個以上のアイテムに展開される。この種類のマクロ呼び出しは特別に、 ! の直後に識別子を与えることができるが、現在この構文が使えるのは macro_rules! のみである。

// macro_rules! 自身も特殊なアイテムマクロである
macro_rules! my_macro1 {
    ($($a:tt)*) => {$($a)*}
}
macro_rules! my_macro2 (
    ($($a:tt)*) => {$($a)*}
);
macro_rules! my_macro3 [
    ($($a:tt)*) => {$($a)*}
];

// (), []の場合は直後にセミコロンが必要だが、 {}の場合は不要。
// このセミコロンはマクロ展開後のアイテムには影響を与えない
my_macro3! {
    fn f1() -> u32 { 32 }
}
my_macro1!(
    fn f2() -> u32 { 33 }
);
my_macro2![
    fn f3() -> u32 { 34 }
];

fn main() {
    println!("{},{},{}", f1(), f2(), f3());
}

TraitItemKind::Macro(Mac) … 0個以上のトレイトアイテムに展開される。

macro_rules! my_macro {
    ($($a:tt)*) => {$($a)*}
}

trait Foo {
    // (), []の場合は直後にセミコロンが必要だが、 {}の場合は不要。
    // このセミコロンはマクロ展開後のアイテムには影響を与えない
    my_macro!(fn f1() -> u32;);
    my_macro!{fn f2() -> u32;}
    my_macro![fn f3() -> u32;];
}

fn main() {
}

TraitItemKind::Macro(Mac) … 0個以上の実装アイテムに展開される。

macro_rules! my_macro {
    ($($a:tt)*) => {$($a)*}
}

struct A;
impl A {
    // (), []の場合は直後にセミコロンが必要だが、 {}の場合は不要。
    // このセミコロンはマクロ展開後のアイテムには影響を与えない
    my_macro!(fn f1() -> u32 { 32 });
    my_macro!{fn f2() -> u32 { 33 }}
    my_macro![fn f3() -> u32 { 34 }];
}

fn main() {
}

構文拡張を展開する

構文拡張は、マクロ呼び出しと属性からなる。これらはコンパイラのフェーズ2で、syntax::ext::expand で処理される。

展開処理は、ASTを先頭から順に走査することで行われる。走査の途中でマクロ呼び出しに遭遇した場合、以下の処理が行われる。

  1. 構文拡張のデータベースからマクロ定義を検索する。
  2. マクロ定義に、マクロ呼び出しの実引数(トークンツリーの列)を入力する。
  3. 得られた出力(トークンツリーの列)を構文解析する。
  4. 得られたASTに再帰的に構文拡張の展開処理を行う。

まとめ

Rustは構文解析をしてからマクロを展開するため、CではできてしまういくつかのマクロがRustではできない場合がある。これは大抵の場合よい方向にはたらくだろう。

Rustのself引数まとめ

Rust

概要: Rustの随所でself引数は特別扱いされている。それらの挙動について調べた。

self引数とメソッド

Rustではnon-staticメソッドは self という特殊な名前の引数を持つ関数として定義されている。例えば、

struct A;

// parse_self_arg
impl A {
    fn f1(self: A) {}
    fn f2(self: &mut A) {}
    fn f3(self: &A) {}
    fn f4(self: Box<A>) {}
    // 生存期間を明示すると以下の通り
    // fn f2<'a>(self: &'a mut A) {}
    // fn f3<'a>(self: &'a A) {}
}

と書くと、 f1, f2, f3 はメソッドになる。

self はキーワードであり、この名前の引数は特定の条件下でのみ宣言できる。それは以下の場合である。

  • traitまたはimpl内の関数の引数である。
  • 第一引数である。
  • Self, &Self, &mut Self, Box<Self> のいずれかの型をもつ。(引数自体は mut であってもなくてもよい)

selfショートカット構文

self 引数は頻出するため、以下の構文糖衣が用意されている。

struct A;

// parse_self_arg
impl A {
    fn f1(self) {}
    fn f1mut(mut self) {}
    fn f2(&mut self) {}
    fn f3(&self) {}
    // 生存期間を明示すると以下の通り
    // fn f2<'a>(&'a mut self) {}
    // fn f3<'a>(&'a self) {}

    // 以下と同じ
    // fn f1(self: Self) {}
    // fn f1mut(mut self: Self) {}
    // fn f2(self: &mut Self) {}
    // fn f3(self: &Self) {}
    // fn f2<'a>(self: &'a mut Self) {}
    // fn f3<'a>(self: &'a Self) {}
}

生存期間の省略

関数宣言で生存期間の指定を省略した場合、一定の規則に基づいて生存期間が復元される。このときに self 変数が特別扱いされる。具体的には、以下の規則に基づいている。

  • 入力側で生存期間が省略された場合、出現位置ごとに別々のfreshな生存期間が割り当てられる。
  • 出力側で生存期間が省略された場合、以下の規則に基づき、全て同じ生存期間が割り当てられる。
    1. もし、参照型の self 引数がある場合、その参照の生存期間が用いられる。
    2. もし、入力側に生存期間が1つだけ出現する場合、その生存期間が用いられる。
    3. それ以外の場合、コンパイルエラー。

メソッド記法

レシーバーにドットをつける receiver.method(args) という記法は、 self 引数を持つメソッドにのみ有効である。

object safety

trait objectを生成できるtraitには条件がある。これをobject safetyというのであった。

あるtraitがobject safeであるとは、

  • Self: Sized 制約がない、かつ
  • 束縛/where/スーパートレイトの制約におけるトレイトの型引数に Self が出現しない、かつ
  • 全てのメソッドがobject safeである。

ただし、あるメソッドがobject safeであるとは、そのメソッドに Self: Sized 制約がついているか、以下が満たされていることである。

  • self 引数を持ち、かつ
  • self 引数以外の引数・戻り値型に Self を含まず、かつ
  • メソッドが型引数をとらない。

ObsoleteVisiblePrivateTypesVisitor

後方互換性のために残されているprivateness checkerで、 self 引数が特別扱いされている。詳細は不明

self 引数を回避する利点

ほとんどの場合、上記の条件を満たす引数は self にしてしまうほうが便利である。しかし std::rc::Rcstd::sync::Arcself を使わない。

impl<T: ?Sized> Rc<T> {
    pub fn downgrade(this: &Self) -> Weak<T> {
        ...
    }
    ...
}

この場合、同じ型をもつ関数でも、 self 引数のもつ利点は受けられない。 RcArcself を使わないのは、これが Deref を実装するコンテナであり、 Rc<T> のメソッド記法が T のメソッド記法の名前空間を汚染しないようにしたいからである。

コンパイラの該当箇所

まとめ

Rustではメソッドの第一引数に self という特別な名前をつけることができる。これによりメソッドに has_self フラグが立ち、構文のみならず型システムにも影響を与える。

Rustトレイトの既定実装と否定実装

Rust

概要: SendやSyncなど一部のトレイトで採用されている機能である、既定実装と否定実装の挙動を調べた。

既定実装と否定実装について

既定実装(デフォルト実装, 自動実装, オート実装, default impl, auto impl)と否定実装(negative impl)はRust RFC 0019: Opt-in Builtin Traits (OIBITs)にて、unsafeトレイトとともに規定されている機能である。

OIBITsは、その名前に反して、「言語に組み込みとは限らないマーカートレイトについて、オプトアウト方式での実装を可能にする」という、非常に天邪鬼な機能である。

既定実装と否定実装は組み合わせて使われる。実際の標準ライブラリの例を見るとわかりやすい。

#![feature(optin_builtin_traits)]

// unsafeトレイト
unsafe trait Send {}
// unsafeな既定実装
unsafe impl Send for .. {}
// 否定実装
impl<T:?Sized> !Send for Arc<T> {}

標準ライブラリのOIBITs

1.16.0現在、標準ライブラリで既定実装と否定実装が使われているのは以下の4つである。

既定実装

既定実装は以下のような構文を持つ。

unsafe impl Trait for .. {}
impl Trait for .. {}

ただし、以下の制約がある。

  • この実装は生存期間・型パラメーターをとることができない。
  • 実装対象のトレイトは生存期間・型パラメーターをとることができない。
  • 既定実装は中身を持つことができない。したがってマーカートレイトに対してしか使うことができない。 (このトレイトがwhere節をもつことは可能である。)

既定実装の適用規則

既定実装をもつトレイトは、トレイト束縛の解決時にその内容が参照される。以下の条件で、既定実装が適用される。 (rustc::traits::select 2104行目)

  • 否定実装を含め、他の実装が見つかっていない。 (rustc::traits::select 1122行目)
    • where制約を満たしていない実装でも、型のパターンが一致していれば、この時点では「見つかっている」と見なす。
  • トレイト自身にwhere制約がある場合、それを満たしている。
  • この型を構成する型も、同じトレイトを実装している。ただし、「構成する型」は以下のように定義される。
    • PhantomData<T> は、 T から構成される。
    • それ以外の構造体や列挙体は、メンバ全てから構成される。 (クロージャも似ているが #27086 が関係してくる)
    • 配列もポインタも参照も、その元の型から構成される。

これらが where に追加されたのと同様に振る舞うと考えればよい。

既定実装の上書き

上に書いてあるように、既定実装の生成するwhere制約が所望のものではなかったときは、自分で定義した実装で上書きできる。

例えば、

#![feature(optin_builtin_traits)]

trait Foo {}

impl Foo for .. {}

struct B<X>(X);

の場合、 B<X> には以下の実装が生成されたような扱いになる。

impl<X: Foo> Foo for B<X> {}

例えば、以下のように書くと、 B に対しては既定実装は適用されなくなり、かわりに明記された実装が使われるようになる。 XはFooでなくてもよいが、Barである必要があるようになる。

trait Bar {}
impl<X: Bar> Foo for B<X> {}

以下の場合、 B<u32> については上記の実装を適用し、それ以外については B<X> であっても既定実装を適用することになる。

impl Foo for B<u32> {}

否定実装

否定実装は以下のような構文を持つ。

impl<'a, X> !Trait for Type<'a, X> {}

ただし、以下の制約がある。

  • 当たり前だが、inherent implとして (impl !Type {}のように) 使うことはできない。
  • 実装対象のトレイトは既定実装を持つ必要がある。したがって否定実装は中身を持たないし、マーカートレイトに対してしか使うことができない。 (このトレイトがwhere節をもつことは可能である。)

否定実装は、この実装が採用されたときにエラーとなるという点以外は、普通の実装と同様である。これは既定実装の上書きをするときに、where条件を変えるのではなく実装を丸ごと禁止するのに使う。

まとめ

既定実装と否定実装は Send/Sync/UnwindSafe/RefUnwindSafe のように、基本的には特定の継承ルールに基づいてマーカートレイトを実装させたいが、特定の型に対しては異なるルールを適用したいときに用いる。

Rustの組み込みマクロ

Rust

Rustのマクロの多くは macro_rules! で定義されるが、トークン列をトークン列に変換するものなら何でもマクロとして実装されうる。

Rustの標準ライブラリのマクロの多くは core::macros にて定義されている。

以下のマクロは通常の macro_rules! により定義される。

  • panic!
  • assert!
  • assert_eq!
  • assert_ne!
  • debug_assert!
  • debug_assert_eq!
  • debug_assert_ne!
  • try!
  • write!
  • writeln!
  • unreachable!
  • unimplemented!

以下のマクロは core::macros::builtin に宣言だけ存在するが、実装はコンパイラ組み込みである。

  • format_args!
  • env!
  • option_env!
  • concat_idents!
  • concat!
  • line!
  • column!
  • file!
  • stringify!
  • include_str!
  • include_bytes!
  • module_path!
  • cfg!
  • include!

これらはコンパイラ組み込みであり、 syntax_ext::register_builtins で登録されている。

これはマクロに限らない一般の構文拡張を管理するデータベース syntax::ext::base で管理されている。このデータベースには以下のようなエントリがある(抜粋):

  • MultiModifier: Pythonの属性のように、itemを受け取り別のitemに変換する構文拡張。
  • ProcMacro: トークン列をトークン列に変換する、構文拡張の一般的なインターフェース。
  • AttrProcMacro: ProcMacro に似ているが、属性込みで変換できるインターフェース。
  • NormalTT: ProcMacro に似ているが、よりマクロ呼び出しに特化したインターフェースになっている。トークン列ではなく、構文要素を返す。
  • IdentTT: 識別子を識別子に変換する。

マクロ構文では ProcMacro, NormalTT, IdentTT のみ取り扱われる。他の構文拡張はattrやderiveで使われる。

macro_rules! で定義されるマクロは syntax::ext::tt::macro_rulesNormalTT に変換される。また組み込みマクロも NormalTT である。なお、 macro_rules! 自身はかなり特殊な扱いで、構文解析器が場合分けを行う。

組み込みマクロは、上で説明したように、トークン列を構文要素に変換する関数がコンパイラ内に実装されているという以上のことはない。 include_str!stringify! のようなCプリプロセッサのような処理は syntax::ext::source_util で実装されている。それ以外の組み込みマクロの実装は src/libsyntax_ext内の各ソースファイルが提供している。

まとめ

Rustにおけるマクロは、トークン列を構文要素に変換するメタ関数に他ならない。多くは macro_rules! により構文解析時に定義されるが、これで定義できるのはごく簡単なマクロだけである。より複雑だったり、処理系組み込みの機能を提供するマクロは、コンパイラに組み込みであったり、 別のcrateでプロシージャマクロとして定義されていたりする。

Rustのマングリング(名前修飾)

Rust

Rustの生成したネイティブコードを見ると、 _ZN6thread5sleep20h87eee61de4645181cAbE のようなシンボル名が見える。この例は std::thread::sleep に対応している。このようにRustの(単相化された)アイテム(関数や変数など)の名前をリンカが認識できる文字列にエンコードする処理はマングリングと呼ばれている。

Rustのマングリングは一見してわかるようにC++互換になっている。実際に上の関数をデマングルすると

$ c++filt _ZN6thread5sleep20h87eee61de4645181cAbE
thread::sleep::h87eee61de4645181cAb

と、それらしき名前が出てくる。

しかし、これは表層上C++互換になっているというだけで、Rustのマングリングの本質はこのハッシュ部分 h87eee61de4645181cAb に依拠している。

以下、Rust 1.15.1の rustc_trans::back::symbol_names に基づいて、Rustのマングリングについて説明する。これはコンパイラのバージョンアップにより情報が古くなる可能性がある。

DefPathを計算する

まず、Rustのアイテムの単相化前の部分を一定の形にエンコードする必要があるが、これには rustc::hir::map::definitions::DefPath が使われる。

DefPathは簡単に言うと、 std::result::Result::map のように、単相化前のアイテムの位置を、crateのルートからの相対パスとして保持したものである。ただしそれだけでは関数内関数など、同じ名前で複数のアイテムを定義できる場合がある。そのため、 foo[1]::bar[0], foo[1]::bar[1] といった感じで番号 (disambiguator) を与えて区別する。disambiguatorは0から順に振られるため、通常は 0 である。

DefPathの定義を抜粋すると以下のようになる。

pub struct DefPath {
    pub data: Vec<DisambiguatedDefPathData>,
    pub krate: CrateNum,
}

pub struct DisambiguatedDefPathData {
    pub data: DefPathData,
    pub disambiguator: u32
}

pub enum DefPathData {
    CrateRoot,
    InlinedRoot(Box<InlinedRootPath>),
    Misc,
    Impl,
    TypeNs(InternedString),
    ValueNs(InternedString),
    Module(InternedString),
    MacroDef(InternedString),
    ClosureExpr,
    TypeParam(InternedString),
    LifetimeDef(InternedString),
    EnumVariant(InternedString),
    Field(InternedString),
    StructCtor,
    Initializer,
    Binding(InternedString),
    ImplTrait
}

DefPathDisambiguatedDefPathDataHash をderiveしているが、今回のハッシュ化に DefPath:Hash の実装は使わない。というのも krate: CrateNum は内部的なu32のidで表現されており、これをそのまま使うとコンパイラの実行ごとにハッシュが安定しないからである。

安定ハッシュを用意する

Rustにはオブジェクトをハッシュ化するための Hash というトレイトが用意されているが、通常のハッシュ実装ではアーキテクチャ依存性が発生するためにクロスコンパイルで問題が生じる可能性がある。というのも、 Hash が利用する Hasher は以下のようなインターフェースを持ち、……

pub trait Hasher {
    fn finish(&self) -> u64;
    fn write(&mut self, bytes: &[u8]);

    fn write_u8(&mut self, i: u8) { ... }
    fn write_u16(&mut self, i: u16) { ... }
    fn write_u32(&mut self, i: u32) { ... }
    fn write_u64(&mut self, i: u64) { ... }
    fn write_usize(&mut self, i: usize) { ... }
    fn write_i8(&mut self, i: i8) { ... }
    fn write_i16(&mut self, i: i16) { ... }
    fn write_i32(&mut self, i: i32) { ... }
    fn write_i64(&mut self, i: i64) { ... }
    fn write_isize(&mut self, i: isize) { ... }
}

……しかもこれらのデフォルト実装は、「現在のアーキテクチャエンディアンでバイト列に変換して write に突っ込む」となっているからである。

Rustのコンパイラはこれに対処するため、 isizeusize を使っても常に同じようにハッシュされるHasherである rustc_data_structures::stable_hasher::StableHasher を用意している。これはblake2bのラッパーだが以下のように動作する:

  • i8u8 は1バイトとして書き込む。
  • 残りの全ての整数型は、リトルエンディアンの128bit整数に変換して書き込む。

型パラメーターとあわせてハッシュ化する

64bitの安定ハッシャーを用意して、以下の順に突っ込む。

  • DefPath (ただしcrateが安定するように工夫してある)
  • アイテム自身の型 (単相化する前)
  • 多相ならば、その型代入

ハッシュを64bitで取り出し、16進表記して接頭辞 h をつける。 (例: h87eee61de4645181cAb)

飾り付けをする

再び、アイテムの絶対パスを計算して、先ほど生成したハッシュと連結する。 (例: thread/sleep/h87eee61de4645181cAb)

サニタイズする

変な文字が入っているかもしれないので、簡単な文字だけからなるように変換する。

  • @$SP$
  • *$BP$
  • &$RF$
  • <$LT$
  • >$GT$
  • ($LP$
  • )$RP$
  • ,$C$
  • :.
  • -.
  • aからz, AからZ, 0から9, _, ., $ → そのまま
  • それ以外のUnicode文字 → $u2764$ のようにコードポイントを16進数で

C++互換でマングリングする

_ZN + (文字数を10進数で + 文字列) ×任意個 + E

できあがり

以上の処理は rustc_trans::trans_item::TransItem::compute_symbol_name で使われている。

まとめ

Rustはアイテムの位置と型引数をできるだけ安定性の高い方法でハッシュ化し、それをシンボル名として使っている。読みやすさのために、C++互換の情報も付与されている。

ハッシュは h + 64bit で17文字のはずなのに実例をみると20文字になっている原因がまだ把握できていない。

Rustのvtableの内部構造

Rust

trait objectは、型情報を忘れるかわりにvtableへの参照を持ち回すことで動的ディスパッチを実現している。

vtableを生成するコードはrustc_trans::meth 112行目にある。これによると、vtableの構造は以下のとおり。

  • 0番目: Drop Glue をあらわす関数ポインタ (デストラクタ)
  • 1番目: 元の型のバイト数
  • 2番目: 元の型のアラインメント
  • 3番目以降: メソッドへのポインタ (宣言順)
    • Self: Sized 制約のついたメソッドに対応するスロットには0が代入される。

trait objectはSizedではないので、値をコピー渡しすることはなく、fat pointerで渡す。fat pointerの0番目は、もとのデータと同じ先頭番地を指すポインタで、fat pointerの1番目が、vtableの先頭番地を指すポインタである。

実際にvtableを手動で取り出して実験してみたものが以下のコードである。

use std::mem::transmute;

trait Foo {
    fn fn1(&self, u32);
    fn fn2(&self, u32) where Self: Sized;
    fn fn3(&self, u32);
}

#[derive(Debug)]
struct S1(u64, u64, u64);

impl Foo for S1 {
    fn fn1(&self, x: u32) {
        println!("fn1({:?}, {})", self, x);
    }
    fn fn2(&self, x: u32) where Self: Sized {
        println!("fn2({:?}, {})", self, x);
    }
    fn fn3(&self, x: u32) {
        println!("fn3({:?}, {})", self, x);
    }
}

impl std::ops::Drop for S1 {
    fn drop(&mut self) {
        println!("drop({:?})", self);
    }
}

struct FooVtable {
    drop_glue: fn(&mut S1),
    size: usize,
    align: usize,
    fn1_ptr: fn(&S1, u32),
    fn2_ptr: fn(&S1, u32),
    fn3_ptr: fn(&S1, u32),
}

fn recover_S1(foo: &mut Foo) -> (&mut S1, &'static FooVtable) {
    unsafe { transmute(foo) }
}

fn main() {
    let mut x = S1(3, 4, 5);
    let foo : &mut Foo = &mut x;
    let (xx, vtbl) = recover_S1(foo);
    println!("vtbl.drop_glue = {:x}", vtbl.drop_glue as usize);
    println!("vtbl.size = {:x}", vtbl.size);
    println!("vtbl.align = {:x}", vtbl.align);
    println!("vtbl.fn1_ptr = {:x}", vtbl.fn1_ptr as usize);
    println!("vtbl.fn2_ptr = {:x}", vtbl.fn2_ptr as usize);
    println!("vtbl.fn3_ptr = {:x}", vtbl.fn3_ptr as usize);
    println!("S1::fn1 = {:x}", S1::fn1 as usize);
    println!("S1::fn2 = {:x}", S1::fn2 as usize);
    println!("S1::fn3 = {:x}", S1::fn3 as usize);
    (vtbl.drop_glue)(xx);
    (vtbl.fn1_ptr)(xx, 88);
    (vtbl.fn3_ptr)(xx, 188);
}
vtbl.drop_glue = 55c14c8def80
vtbl.size = 18
vtbl.align = 8
vtbl.fn1_ptr = 55c14c8df0c0
vtbl.fn2_ptr = 0
vtbl.fn3_ptr = 55c14c8df340
S1::fn1 = 55c14c8df0c0
S1::fn2 = 55c14c8df200
S1::fn3 = 55c14c8df340
drop(S1(3, 4, 5))
fn1(S1(3, 4, 5), 88)
fn3(S1(3, 4, 5), 188)
drop(S1(3, 4, 5))

drop glueは別として、メソッドテーブルに入っている関数ポインタは元のメソッドの使い回しであることがわかる。

むろん、このような荒技を実験以外に使うのは好ましくない。