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

Rustの名前解決(2/4) インポート解決

Rust

概要: Rustの名前解決の詳細について解説する。本記事では、インポート解決について説明する。

名前解決のタイミング

コンパイラの名前解決に関するコードを探す上で重要な点のひとつは、「 useextern crate などの主要な構文要素は対応するHIRの要素をもつにもかかわらず、これらはloweringの前に解釈される」という点である。ASTからHIRへの変換で最も大きな仕事の一つが名前解決だから、ASTの時点で use が解釈させることは当たり前なのだが、それにもかかわらず use に対応するHIRの要素があるのは、おそらくdocの生成などで用いられるためである。

モジュール構造

Rustの名前解決において最も中心的な役割を果たすデータ構造はモジュール構造である。これは rustc_resolve::ModuleData で定義されている。

/// One node in the tree of modules.
pub struct ModuleData<'a> {
    parent: Option<Module<'a>>,
    kind: ModuleKind,
    ...
    resolutions: RefCell<FxHashMap<(Ident, Namespace), &'a RefCell<NameResolution<'a>>>>,
    ...
    glob_importers: RefCell<Vec<&'a ImportDirective<'a>>>,
    globs: RefCell<Vec<&'a ImportDirective<'a>>>,
    ...
}

ModuleData に含まれる rustc_resolve::resolve_imports::NameResolutionrustc_resolve::NameBindingrustc_resolve::resolve_imports::ImportDirective も重要である。

pub struct NameResolution<'a> {
    /// The single imports that define the name in the namespace.
    single_imports: SingleImports<'a>,
    /// The least shadowable known binding for this name, or None if there are no known bindings.
    pub binding: Option<&'a NameBinding<'a>>,
    shadows_glob: Option<&'a NameBinding<'a>>,
}
pub struct NameBinding<'a> {
    kind: NameBindingKind<'a>,
    ...
    vis: ty::Visibility,
}
...
enum NameBindingKind<'a> {
    Def(Def),
    Module(Module<'a>),
    Import {
        binding: &'a NameBinding<'a>,
        directive: &'a ImportDirective<'a>,
        used: Cell<bool>,
        legacy_self_import: bool,
    },
    Ambiguity {
        b1: &'a NameBinding<'a>,
        b2: &'a NameBinding<'a>,
        legacy: bool,
    }
}
pub struct ImportDirective<'a> {
    ...
    pub subclass: ImportDirectiveSubclass<'a>,
    ...
    pub vis: Cell<ty::Visibility>,
    ...
}

...

pub enum ImportDirectiveSubclass<'a> {
    SingleImport {
        target: Ident,
        source: Ident,
        result: PerNS<Cell<Result<&'a NameBinding<'a>, Determinacy>>>,
        type_ns_only: bool,
    },
    GlobImport {
        is_prelude: bool,
        max_vis: Cell<ty::Visibility>, // The visibility of the greatest reexport.
        // n.b. `max_vis` is only used in `finalize_import` to check for reexport errors.
    },
    ExternCrate,
    MacroUse,
}

以上をまとめると以下のようになる。

  • use/extern crate を無視すると、モジュールは森構造をなす。 use/extern crate を考慮するとグラフ構造になる。
  • 各モジュールは、そのモジュールから辿れる名前の一覧を所有している。これは以下の4種類のうちのいずれかである。
    • 通常の定義 (fn, static, const, struct, enum など)
    • mod で定義された子モジュール
    • use によるインポート
    • 複数の候補がありうる場合
  • * によるインポートははじめそのままの形で管理されており、インポート解決が進行するにつれて binding として解決されていく。

インポート解決の仕事

インポート解決の目的は、以下の内容を把握することである。

  • 各モジュールが、どのような名前を子供として持っているか。
  • それが定義ではなくインポートだった場合は、その参照先。

これらの困難は基本的に * によるglob importに由来する。これのせいで、子供の一覧を一発で収集することができないのである。

例えば、以下のように、 2段階のglob importで間接的にインポートされる場合がある。

mod m1 {
    pub use m2::*;
}
mod m2 {
    pub use m3::*;
}
mod m3 {
    pub const X : u32 = 0;
}

fn main() {
    println!("{}", m1::X);
}

また以下の例では、 use m2::* が解決されるまでは、 self::m4 の実体がどこにあるのかわからない。

mod m1 {
    pub use self::m4::X;
    pub use m2::*;
    pub use m3::*;
}
mod m2 {
    pub mod m4 {
        pub const X : u32 = 0;
    }
}
mod m3 {
    pub mod m5 {
        pub const X : u32 = 1;
    }
}

fn main() {
    println!("{}", m1::X);
}

このようにちょっとだけ複雑なglob importを解決するのが、インポート解決の主な仕事である。

インポート解決のメインループ

Rustコンパイラのインポート解決のアルゴリズムは単純で、「できるところから解決していって、何もできなくなったら停止する」である。 (rustc_resolve::resolve_imports::ImportResolver::resolve_imports)

    /// Resolves all imports for the crate. This method performs the fixed-
    /// point iteration.
    pub fn resolve_imports(&mut self) {
        let mut prev_num_indeterminates = self.indeterminate_imports.len() + 1;
        while self.indeterminate_imports.len() < prev_num_indeterminates {
            prev_num_indeterminates = self.indeterminate_imports.len();
            for import in mem::replace(&mut self.indeterminate_imports, Vec::new()) {
                match self.resolve_import(&import) {
                    true => self.determined_imports.push(import),
                    false => self.indeterminate_imports.push(import),
                }
            }
        }
    }

典型的な不動点計算アルゴリズムといってもよい。

ここで中心的な役割を果たす変数は以下の4つである。

  • globsソースコード中に実際に書かれているglob import命令の一覧である。
  • determined_imports … glob import命令のうち、解決済みのもの(これ以上処理しなくてよいもの)の一覧である。
  • indeterminate_imports … glob import命令のうち、未解決のもの(まだ処理が必要なもの)の一覧である。これはさらに二種類に分けられる。
    • インポート元のモジュールがどこか判明していないもの。
    • インポート元のモジュールは判明しているが、そのモジュールにある名前がまだ増えるかもしれないもの。
  • glob_importers … glob import命令のうち、インポート元までは判明しているもの。

resolve_imports は、 indeterminate_imports に入っているglob importを一つずつ取り出して、 resolve_import を試す。これは以下の処理を行う。

  • まず、そのglob importのインポート元のモジュールの解決を試みる。
  • 成功したら、 glob_importers にそれを追加する。さらに、インポート元の全ての名前が列挙済みかを調べる。
  • 列挙済みなら、それらを全てインポート先にも束縛して、成功とする。そうでなければ失敗する。(失敗でも、列挙できた名前はすべて追加する)

この処理が進むにつれて、 indeterminate_imports が減っていく。これが減らなくなった時点で終了とする。もちろん、未解決のインポートが残っている場合はどこかにエラーがある。

インポートの優先度

glob importは他の定義と比べて優先度が低く、特定のルールでシャドウされる。(rustc_resolve::resolve_imports::ImportResolver::try_define)

  • glob importと、glob import以外の定義がある場合、glob import以外の定義が優先される。
    • マクロ名前空間についてはこの優先規則が適用されない場合がある。
  • glob import以外の定義が2つあるときは、エラーになる。
  • glob import由来の同名の定義が2つあるときは、それぞれのimportを辿ったときのDefIdが比較される。等しければ特に問題はない。等しくない場合はambiguousとなり、使った時点でエラーになる。DefIdはNodeIdに由来するので、だいたい「同じ定義ならglobで二重importしてOK」と思えばよい。
    • DefIdが等しいが、2つのglob importの可視性が異なる場合は、可視性の高いほうが優先される。

まとめ

ここまでで、Rustのどのモジュールに何があるかがわかるようになった。

Rustの名前解決(1/4) 名前解決にかかわる構文

Rust

概要: Rustの名前解決の詳細について解説する。本記事では、名前解決に関する構文を紹介する。

Rustのモジュール

Rustのコンパイルはcrate単位で行われ、必ずcrateのトップレベルモジュールに相当するファイルが存在する。これには lib.rsmain.rs という名前がついていることが多い。

モジュール内にさらにモジュールを宣言する方法は2つある。 (parse_item_mod)

  • ひとつは mod foo; と書き、内容を別のファイルに書く方法でである。
  • もうひとつは mod foo { ... } のように内容を親モジュールと同じファイルに書く方法である。

mod foo 形式の場合は、以下の条件でファイル名が選択される。(submod_path)

  1. #[path="custom_path"] があれば、これが採用される。
  2. それがなければ、 foo.rs または foo/mod.rs のいずれかが採用される。両方ある場合はエラーになる。

上記のファイル名は、モジュールに対応するディレクトリからの相対パスとして扱われる。モジュールに対するディレクトリ割り当ては以下の規則に従う。

  • トップレベルのファイル ( lib.rsmain.rs という名前のことが多い) には、直近の親ディレクトリが割り当てられる。
  • ファイル名が mod.rs のモジュールファイルには、直近の親ディレクトリが割り当てられる。
  • それ以外の名前のモジュールファイルには、ディレクトリは割り当てられない。
  • mod foo { ... } 形式で定義した場合は、親モジュール直下の foo ディレクトリが仮想的に割り当てられる。

外部モジュールの取り込み処理は構文解析時に行われる。したがって1つのcrateのコンパイルの途中では、1つの大きなASTが生成される。

アイテム

モジュールはアイテムを含むことができる。これには mod, use, extern crate, extern{ fn ... }, fn, static, const, type, enum, struct, union, trait, impl などがある。 (parse_item_)

mod, use, extern crate は名前解決で特殊扱いされるが、それ以外はほぼ同様に扱われる。ただし、 enum のコンストラクタは SomeEnum::Constr のように参照するため、 enum 自体がモジュールのように振る舞う。

モジュールではないが子要素を持つアイテムもある。例えば、型やトレイトにはメソッドが関連づけられている。

パス

識別子を :: で繋いだものをパスという。ただし例えば以下のような変種がある。 (parse_path, parse_qualified_path, parse_view_path)

  • :: で始めることで、絶対パスであることを明示できる。
  • self:: で始めると、相対パスであることを明示できる。
  • super という特殊なパス要素を使うと、親モジュールを参照できる。
  • 各パス要素に、 <> により型引数や生存期間引数を与えることができる場合がある。この記法は型であることが明白な文脈では Foo<Bar> のように書き、式と紛らわしい文脈では Foo::<Bar> のように書く。
  • <> のかわりに () で囲まれた型のリストや、 -> Type を与えることができる場合がある。
  • パスの最初の要素として <A as Foo> のような形の指定をとることができる場合がある。
  • パスの最後に foo::{bar1, bar2}foo::* のような複数指定が可能な場合がある。

extern crate

それぞれのcrateが、Rustのモジュールツリーを1つ有している。 extern crate をすると、特定のcrateを現在コンパイル中のcrateのツリーから参照できるようになる。*NIXのファイルシステムに慣れた人なら、これはデバイスを特定のディレクトリにマウントするようなものだと考えるとわかりやすいだろう。

通常 extern crate crate_name; の形で使うが、 extern crate some_crate as mount_point; のように別名を与えることもできる。 (parse_item_extern_crate)

use

use は異なるモジュールに属するアイテムに対する参照を張る。*NIXのファイルシステムに慣れた人なら、これはシンボリックリンクと考えるとわかりやすいだろう。

use の基本形は以下の2つである。

// simple import
use foo::bar as baz;
// glob import
use foo::bar::*;

このうち、simple importに対しては以下のような構文糖衣がある。 (parse_view_path)

use foo::bar; // use foo::bar as bar;
use foo::{bar as baz, bar2}; // use foo::bar as baz; use foo::bar2 as bar2;

pub による可視範囲指定

以下の位置には、 pub による可視範囲を指定できる。 (parse_visibility)

  • fn, struct, enum など、ほぼ全てのアイテム。 (parse_item_ 内)
  • impl { ... } の中にある実装アイテム。 (parse_impl_item 内)
  • extern { ... } の中にある外部アイテム。 (parse_foreign_item 内)
  • 構造体および列挙体のフィールド型(タプル形式の場合)またはフィールド名(波括弧形式の場合)。ただし列挙体のそれについては冗長であり不要。 (parse_tuple_struct_body 内および parse_struct_decl_field 内)
    • struct A(pub u32);
    • struct A { pub x: u32 }
    • enum A { A0(pub u32) } // 冗長
    • enum A { A0 { pub x: u32 } } // 冗長

Rust 1.16.0 では可視範囲は pub と無印の2択だが、Rust RFC 1422: pub(restricted)による拡張がnightlyには実装されている。1.16.0に実装されているものと異なる構文だが、現在のnightlyでは以下のような構文になっている。 (現時点での最新版の parse_visibility)

  • pub … あらゆる場所から可視。
  • pub(crate) … 現在のcrateから可視。
  • pub(in path::to::somewhere) … 特定モジュールの子孫からのみ可視。
  • pub(self), pub(super)pub(in self)/pub(in super) の略記。
  • 指定なし … pub(in self) と同義。

名前空間

Rustでいうところの「名前空間」は、C++名前空間ではなくCの名前空間(default namespace, struct namespace, labels, member names)のようなものを指す。

Rustには3つの名前空間がある: 型の名前空間、値の名前空間、マクロの名前空間である。 (rustc_resolve::Namespace)

同じ識別子でも、名前空間が異なれば、別のものとして扱われる。主要な識別子の名前空間は以下の通りである。 (rustc_resolve::build_reduced_graph::Resolver::build_reduced_graph_for_item)

  • 型の名前空間に属するもの
    • mod
    • extern crate
    • struct (タプル形式の場合は、型と値の両方の名前空間に属する。)
    • enum
    • enum のバリアント名 (型と値の両方の名前空間に属する。)
    • union
    • type
    • trait
    • trait の関連型
  • 値の名前空間に属するもの
    • static
    • const
    • fn
    • extern { ... } の中身
    • タプル形式の struct (型と値の両方の名前空間に属する。)
    • enum のバリアント名 (型と値の両方の名前空間に属する。タプル形式でも波括弧形式でも適用される。)
    • trait の関連アイテムで、型以外のもの
  • マクロ名前空間に属するもの
    • マクロ定義
  • その他
    • use (インポートされたものの名前空間を引き継ぐ)

まとめ

Rustの名前解決について扱うために、まずは手始めとして文法を説明した。

Rustのthread local gensym/internパターン

Rust

概要: Rustでgensymおよびinternを行う方法を説明する。

gensymとinternとは何か

  • gensymパターンは、「まだ使われていない整数」を返す fresh() 関数を実装するというパターンである。型推論などで一時変数を作成するなどの用途で用いられる。
  • internパターンは、文字列などの複雑なデータに対し、データの同値性に基づいて整数を振ることで簡単に比較等できるようにするというパターンである。

Rustによるthread local gensym

gensymは以下のように実現される。

  • スレッドローカル変数に、今まで払出した整数の最大値を記録する。
  • 必要に応じてこの変数をインクリメントする。

このとき生成されたIDは他スレッドと共有できないため、 !Send をつける。

use std::cell::Cell;

// u32を包む
#[derive(Debug, Clone, Copy, Eq, PartialEq, Hash)]
pub struct Symbol(u32);
impl !Send for Symbol {}

impl Symbol {
    pub fn fresh() -> Self {
        thread_local! {
            static NEXT_SYMBOL_ID : Cell<u32> = Cell::new(0);
        }
        NEXT_SYMBOL_ID.with(|next_symbol_id| {
            let symbol_id = next_symbol_id.get();
            next_symbol_id.set(symbol_id + 1);
            Symbol(symbol_id)
        })
    }
}

Rustによるthread local intern

internは以下のように実現される。

  • スレッドローカル変数に、今まで割り当て済みの文字列の一覧を、正引きと逆引きの組で保持する。
  • 必要に応じてエントリを追加する。

このとき生成されたIDは他スレッドと共有できないため、 !Send をつける。

use std::borrow::Borrow;
use std::cell::RefCell;
use std::collections::HashMap;
use std::hash::Hash;

#[derive(Debug, Clone, Copy, Eq, PartialEq, Hash)]
pub struct Symbol(u32);
impl !Send for Symbol {}

struct SymbolTable {
    strings: Vec<String>,
    symbols: HashMap<String, Symbol>,
}

thread_local! {
    static SYMBOL_TABLE : RefCell<SymbolTable> = RefCell::new(SymbolTable {
        strings: Vec::new(),
        symbols: HashMap::new(),
    });
}

impl Symbol {
    pub fn intern<Q:?Sized + Hash + Eq + ToOwned<Owned=String>>(s: &Q) -> Self where String: Borrow<Q> {
        SYMBOL_TABLE.with(|symbol_table_cell| {
            let SymbolTable {
                ref mut strings,
                ref mut symbols,
            } = *symbol_table_cell.borrow_mut();
            if let Some(&symbol) = symbols.get(s) {
                symbol
            } else {
                let symbol = Symbol(strings.len() as u32);
                strings.push(s.to_owned());
                symbols.insert(s.to_owned(), symbol);
                symbol
            }
        })
    }
    pub fn to_str(self) -> String {
        SYMBOL_TABLE.with(|symbol_table_cell| {
            let symbol_table = symbol_table_cell.borrow();
            symbol_table.strings[self.0 as usize].clone()
        })
    }
}

Rustコンパイラ内でのthread local gensym/internパターンの使用例

まとめ

gensymとinternは文脈依存のIDを生成するデザインパターンである。Rustではこれをスレッドローカル変数を用いて実装する場合がある。

Rustマクロの衛生性はどのように実現されているか(2/2) 構文の優先度に関する衛生性

Rust

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

Rustマクロの2つの衛生性

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

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

この記事では、構文の優先度に関する衛生性を説明する。(識別子に関する衛生性については前記事を参照)

構文の優先度に関する衛生性とは

次のようなプログラムが直感的な動作をするのが、構文の優先度に関する衛生性である。Lispマクロの衛生性とは別だが、Rustではこの種類の性質も衛生性と呼んでいる。

macro_rules! prod {
    ($x: expr, $y: expr) => ($x * $y);
}
macro_rules! sum {
    ($x: expr, $y: expr) => ($x + $y);
}
fn main() {
    println!("{}", (4 + 5) * (6 + 7));
    println!("{}", sum!(4, 5) * sum!(6, 7));
    println!("{}", prod!(4 + 5, 6 + 7));
}

このプログラムを字句通りに展開すると構文の優先順位が変化してしまい、異なる結果が得られる。しかしRustのマクロではそのようなことは発生しない。

つまり、次の2点について構文の優先順位の影響を回避する設計になっていることになる。

  • マクロ展開後の内容を再結合から保護する。
  • マクロの実引数を再結合から保護する。

マクロの構文要素化

以前の記事で指摘したように、Rustは展開前のマクロ呼び出しをダミーの構文要素としてあらかじめ解釈してしまう。そのため、マクロ展開後の内容が構文の優先順位の影響を受けることはない。

補間トーク

それでは、マクロの実引数についてはどのように保護しているのだろうか。

Rustではこれを実現するために、補間トークというものを導入している。

補間トークンはsyntax::parse::tokenにて以下のように定義されている。

#[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Hash, Debug)]
pub enum Token {
    Eq,
    Lt,
    Le,
    ...

    /* For interpolation */
    Interpolated(Rc<Nonterminal>),

    ...
}

補完トークンは上のように Nonterminal (nonterminal = 非終端記号) という型の値を保持している。ではこの Nonterminal の定義はというと、次のようになっている。

#[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Hash)]
/// For interpolation during macro expansion.
pub enum Nonterminal {
    NtItem(P<ast::Item>),
    NtBlock(P<ast::Block>),
    NtStmt(ast::Stmt),
    ...
}

見てわかるように、 Nonterminal はASTの断片に他ならない。

Nonterminalmacro_rules! の節のマッチングの段階で発生する。この段階でマクロ呼び出しの実引数が構文解析されるからである。

こうして生成された非終端要素は、マクロ定義中の仮引数を置き換える。このときに Token::Interpolated を使って、非終端要素を1つのトークンと見なすのである。

このように、マクロ展開の時点で実引数を構文解析し、構文解析済みの部分は分解せずにそのままの形で保持することで、マクロの実引数を再結合から保護している。

例による説明

先ほどの例

prod!(4 + 5, 6 + 7)

をもとに説明する。

この例の場合、最初のパース時点では次のようなASTが生成される。この時点ではマクロ呼び出しの実引数は構文解析されていない生のトークンツリー列である。

Mac { path: "prod", tts: [Literal(4), BinOp(Plus), Literal(5), Comma, Literal(6), BinOp(Plus), Literal(7)] }

マクロ展開器により、 prod! マクロの定義が検索される。 prod!macro_rules! により定義されているから、中のトークンツリー列をマッチャーと照らし合わせる。この時点で実引数に対する構文解析が行われる。

[
    ("x", NtExpr(Binary(Plus, Lit(4), Lit(5)))),
    ("y", NtExpr(Binary(Plus, Lit(6), Lit(7)))),
]

マッチに成功したため、このマッチャーに対応する中身にこれが代入される。これにより以下のようなトークン列が生成される。

[NtExpr(Binary(Plus, Lit(4), Lit(5))), BinOp(Mult), NtExpr(Binary(Plus, Lit(6), Lit(7)))]

マクロ呼び出しは式の位置にあったため、これが再び式として構文解析される。このときsyntax::parse::parser 2025行目にある maybe_whole_expr! の処理

        if let token::Interpolated(nt) = $p.token.clone() {
            match *nt {
                token::NtExpr(ref e) => {
                    $p.bump();
                    return Ok((*e).clone());
                }
                ...
            };
        }

により、式が要求される部分にトークInterpolated(NtExpr(e)) が来たら、 e がそのまま式として使われる。

したがって、これを構文解析すると、式のAST

Binary(Mult, Binary(Plus, Lit(4), Lit(5)), Binary(Plus, Lit(6), Lit(7)))

が得られる。

まとめ

Rustマクロの2つの衛生性のうち、構文の優先度の違いによる再結合を防ぐ衛生性は、マクロ呼び出しやその実引数を比較的早い段階で構文解析してしまうことで、実現されている。

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 フラグが立ち、構文のみならず型システムにも影響を与える。