Rustの名前解決(3/5) パス解決
概要: Rustの名前解決の詳細について解説する。本記事では、パス解決について説明する。
パス解決とは
Rustで foo::bar のようにパスを書いたとき、これが具体的にどこで定義されているどのアイテムの、どの特殊化を指すのかは、自明ではない。これを確定させるのがパス解決である。パス解決が行われると、パスは Def や Ty に紐付けられる。これにより、インポートによる曖昧性がなくなる。
PathとQPath
パスはhirの Path または QPath に解決される。
Path は例えば、 std::vec::Vec<T> のような通常のパス(型パラメーターを含んでもよい)である。一方 QPath はこれに加えて、 <BufReader<R> as Read>::read のように、Selfが関係するアイテムも含んでいる。
特に、型に関連づけられているがトレイト情報のないアイテムはlowering時点のパス解決では完全には解決できず、型検査の後に解決される。
パス解決のタイミング
次のような順番でパスが解決される。
useは、インポート解決中に同時に解決される。- loweringの前に、アイテム定義(関連アイテム以外)までのパスの解決が行われ、
def_mapが構築される。 - lowering時に、パスが定義部分と関連アイテム部分に分割され、
PathまたはQPathに解決される。 - 型検査後に、関連アイテムが解決される。
use の解決
インポート解決中に、resolve_import が resolve_path を呼び出している。これにより、 use のパスが解決される。
def_map の作成
lowering前に、rustc_resolveのビジター がAST中に出現するパスを走査し、定義までのパスの解決を行う。
パスの解決結果は、 Def と非負整数の組である。例えば、以下のようなコードを考える。
fn main() { use std::fs; let f = fs::File::open("hoge.txt").unwrap(); }
ここで fs::File::open は、 ::std::fs::File に対応するDefと、非負整数1で表される。この1は、関連アイテム部分の流さが1 (openで1個)であることをあらわしている。
この解決結果を、NodeId から引けるHashMapに保存する。この NodeId は、このパスのAST上の出現に対して割り当てられているものを使う。上の例では、
let f = fs::File::open("hoge.txt").unwrap();
^^^^^^^^^^^^^^ この部分
のノードに割り当てられているNodeIdが使われる。
lowering中のパス解決
lowering中のパス解決はlower_qpathで行われる。 def_map の情報をもとにパスの前半を切り出し、パスの後半(関連アイテム部分)をさらに解析する。例えば、 std::vec::Vec::<T>::IntoIter::Item::clone の場合、前半は std::vec::Vec<T> で、後半は IntoIter, Item, clone となっている。これらはすべて直前の型に関連づけられたアイテム(それぞれ、関連型、関連型、メソッド)であるから、 <<<std::vec::Vec<T>>::IntoIter>::Item>::clone と解釈される。
パス解決関数
パス解決に用いられる関数は場所により異なる。 def_map への記録は record_def 関数 により行われるが、その引数の多くは resolve_qpath で解決される。
QSelfとQPath処理
パス解決前のQPathは、QSelfという追加情報を持つパスとして表されている。 syntax::ast::QSelfは以下のように定義されている。
/// The explicit Self type in a "qualified path". The actual /// path, including the trait and the associated item, is stored /// separately. `position` represents the index of the associated /// item qualified with this Self type. /// /// ```rust,ignore /// <Vec<T> as a::b::Trait>::AssociatedItem /// ^~~~~ ~~~~~~~~~~~~~~^ /// ty position = 3 /// /// <Vec<T>>::AssociatedItem /// ^~~~~ ^ /// ty position = 0 /// ``` #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)] pub struct QSelf { pub ty: P<Ty>, pub position: usize }
ここの説明にあるように、 <A as T>::Fooのような式を書いたとき、ASTでは T::Foo に追加情報として (A, 1) という情報が与えられたものと考える。positionが 0 の場合は特殊で、トレイトが省略されたものとみなす。
QSelfを含むパスのパス解決を担当するのが resolve_qpath である。 resolve_qpath の基本動作は、 QSelf があるならばそこの情報をもとにし、なけれba resolve_path に移譲する、というものである。
u32 や f64 などのプリミティブ型は、 std::u32 のように同名のモジュールを持つ。この処理もここで行われる。
パス解決
パス解決の本体は、その次の resolve_path にある。これはざっくり言うと左側のパス要素から順に処理して進んでいくというものである。
具体的には以下のことが読み取れる。
- 最初が
selfやsuperで開始されるときは、識別子のある字句上のモジュールのnormal ancestorから開始する。 superがパスの冒頭部に連続して現れるときは、出現回数だけ(normal ancestorの)親モジュールに移動する。::から始まるときは、ルートから開始する。マクロ変数$crateから始まるときは、$crateが元々あった位置のcrateのルートモジュールが使われる。- 最後の要素の名前空間は原則として指定できる。途中の要素(モジュール例)は型名前空間に属する。
normal ancestor
各モジュールにはnormal ancestorと呼ばれる、他のモジュールへのリンクが存在する。これは、主に次のような特殊なモジュールで使われる。
fn f() -> u32 { 2 } fn main() { { println!("{}", self::f()); } }
ここで、 println! のすぐ外側の {} はパス解決時にはモジュールの一種と見なされている。しかし、ここで self::f の self が指しているのは、 f と main の両方を含むルートモジュールである。このギャップを埋めるのがnormal ancestorである。
明示的な mod 以外のmodでは、大抵、normal ancestorは親のnormal ancestorをそのまま使う。例えば、 build_reduced_graph_for_block を見ると、以下のようになっている。
let module = self.new_module(parent, ModuleKind::Block(block.id), parent.normal_ancestor_id);
まとめ
Rustのパス解決は簡単なようで、実際にはいくつかの理由で複雑になっている。1つは名前空間、1つは相対パスと絶対パス、1つはSelfの指定である。
Rustの名前解決(2/5) インポート解決
概要: Rustの名前解決の詳細について解説する。本記事では、インポート解決について説明する。
- 名前解決にかかわる構文
- インポート解決
- パス解決
- メソッド記法とメンバ変数と関連アイテムの解決
- 可視性判定
名前解決のタイミング
コンパイラの名前解決に関するコードを探す上で重要な点のひとつは、「 use や extern 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::NameResolution と rustc_resolve::NameBinding と rustc_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/5) 名前解決にかかわる構文
概要: Rustの名前解決の詳細について解説する。本記事では、名前解決に関する構文を紹介する。
- 名前解決にかかわる構文
- インポート解決
- パス解決
- メソッド記法とメンバ変数と関連アイテムの解決
- 可視性判定
Rustのモジュール
Rustのコンパイルはcrate単位で行われ、必ずcrateのトップレベルモジュールに相当するファイルが存在する。これには lib.rs や main.rs という名前がついていることが多い。
モジュール内にさらにモジュールを宣言する方法は2つある。 (parse_item_mod)
- ひとつは
mod foo;と書き、内容を別のファイルに書く方法でである。 - もうひとつは
mod foo { ... }のように内容を親モジュールと同じファイルに書く方法である。
mod foo 形式の場合は、以下の条件でファイル名が選択される。(submod_path)
#[path="custom_path"]があれば、これが採用される。- それがなければ、
foo.rsまたはfoo/mod.rsのいずれかが採用される。両方ある場合はエラーになる。
上記のファイル名は、モジュールに対応するディレクトリからの相対パスとして扱われる。モジュールに対するディレクトリ割り当ては以下の規則に従う。
- トップレベルのファイル (
lib.rsやmain.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)
まとめ
Rustの名前解決について扱うために、まずは手始めとして文法を説明した。
Rustのthread local gensym/internパターン
概要: 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パターンの使用例
syntax::symbolでStringをSymbolにinternしている。syntax::ext::hygieneでMarkをgensymしている。syntax::ext::hygieneでVec<Mark>をSyntaxContextにinternしている。
まとめ
gensymとinternは文脈依存のIDを生成するデザインパターンである。Rustではこれをスレッドローカル変数を用いて実装する場合がある。
Rustマクロの衛生性はどのように実現されているか(2/2) 構文の優先度に関する衛生性
概要: 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の断片に他ならない。
Nonterminal は macro_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マクロは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::empty… 空の文脈を返す。実体はsyntax::ext::hygiene::SyntaxContextData::newで生成されている。outer_markは0番(crate全体をあらわす特別なマーク)で、prev_ctxtはこれ自身を参照している。syntax::ext::hygiene::SyntaxContext::apply_mark… markを1つ追加した文脈を生成する。実体はこの関数内で生成されている。outer_markとprev_ctxtは関数の引数self,markに一致する。
生成済みの構文文脈全体は根つき木をなすが、木そのものには特に興味はない。
文脈の追加と削除
文脈の追加と削除はsyntax::ext::hygiene::SyntaxContext::apply_markで行う。 ctx.apply_mark(mark) は以下を返す:
ctxがmarkで終わるなら、それを削除した文脈を返す。- それ以外の場合は、
ctxにmarkを追加した文脈を返す。
apply_mark を全ての識別子に適用する処理が syntax::ext::expand::Marker に実装されている。これは主に、次の2箇所で使われている。
syntax::ext::expand396行目: マクロ展開前のトークンツリー列にapply_markを適用している。syntax::ext::expand483行目: マクロ展開後のASTにapply_markを再び適用している。
ローカル変数の衛生性の実現例
以下のようなプログラムを考える。
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は構文解析をしてからマクロを展開する
C言語では字句解析の次が前処理で、前処理のあとに構文解析が行われるが、Rustでは構文解析が終わってからマクロが展開される。
より正確に説明すると、Rustのコンパイルはcrate単位で行われ、crateのコンパイル処理の冒頭部は以下の2フェーズに分かれている。
- crateの冒頭から字句解析と構文解析を行う。
mod foo;のようなアイテムがある場合、そのインクルード処理はこのフェーズの中で行われる。これにより1つのcrateに対応する単一のAST(抽象構文木)が生成される。 - 構文拡張を展開する。構文拡張にはマクロ呼び出しや
#[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を先頭から順に走査することで行われる。走査の途中でマクロ呼び出しに遭遇した場合、以下の処理が行われる。
- 構文拡張のデータベースからマクロ定義を検索する。
- マクロ定義に、マクロ呼び出しの実引数(トークンツリーの列)を入力する。
- 得られた出力(トークンツリーの列)を構文解析する。
- 得られたASTに再帰的に構文拡張の展開処理を行う。
まとめ
Rustは構文解析をしてからマクロを展開するため、CではできてしまういくつかのマクロがRustではできない場合がある。これは大抵の場合よい方向にはたらくだろう。
