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

Rust構文解析器のトークン分割戦略

他の多くの言語と同様、Rustの字句解析器は貪欲にトークンを分割する。しかし構文解析の途中で必要に迫られて、さらに細かくトークンを分割する場合がある。

先にまとめ

以下の場合は、構文解析のタイミングで字句がさらに細かく分割される。

  • 式の位置に、前置の || が出現した場合。
  • 型・式・パターンの位置に、前置の && が出現した場合。
  • ジェネリクス引数や、修飾パスが期待される位置に、 << が出現した場合。
  • ジェネリクス引数や修飾パスの内部の > が期待される位置に、 >>, >=, >>= が出現した場合。

本編

他の多くの言語と同様、Rustの字句解析器は貪欲にトークンを分割する。

これは例えば次のようなコードを実行するとわかる。

macro_rules! stringify_each {
    ($($x:tt)*) => {
        stringify!($($x)/ *)
    }
}
fn main() {
    println!("{}", stringify_each!(abc a b c));
    println!("{}", stringify_each!(1.1.1.1.1));
    println!("{}", stringify_each!(&&&&&));
    println!("{}", stringify_each!(|||||));
    println!("{}", stringify_each!(<<<<<));
    println!("{}", stringify_each!(>>>>>));
    println!("{}", stringify_each!(=====));
}
abc / a / b / c
1.1 / . / 1.1 / . / 1
&& / && / &
|| / || / |
<< / << / <
>> / >> / >
== / == / =

ときには、この分割戦略が直感に反した挙動をすることがある。スペースで明示すれば対処できる話だが、いくつかのパターンでは構文解析時にリカバリーする戦略が取られている。

|| の処理

| を含む字句は |, ||, |= の3つであり、以下の場面で使われている。

これらの組み合わせで問題になるのは、クロージャの引数が0個の場合 | | { .. } である。

Rustではこれを || { .. } とも書けるようになっている。この実装はシンプルで、クロージャの予期される位置に || が出現したら引数なしと判断するだけでよい。

&& の処理

& を含む字句は &, &&, &= の3つであり、以下の場面で使われている。

  • ビットごとの論理積 & とその複合代入 &=
  • 短絡回路論理積 &&
  • 参照型 &, &mut およびそのselfショートカット &self, &mut self
  • 参照をとる操作 &, &mut
  • 参照外しパターン &, &mut

これらの組み合わせではいくつかの問題が発生しうる。最も考えやすいのは、二重参照の場合 & & x である。

fn f(x: &&u32) {}

Rustでは上記のようなソースコードも正しくパースする。これはexpect_andという関数で実現されている。この関数は以下のような動作をする。

  • & が来たら、そのトークンを消費して終了する。
  • && が来たら、該当トークンを破壊的に & に置き換える。トークンポインタは進めずに終了する。
  • それ以外が来たら失敗する。

つまり、参照型・参照操作・参照外しパターンのいずれかが期待される場所に && が現れたら、そのトークンは動的に2つの & に分割される。これにより上記のようなソースコードが正しくパースされるようになっている。Rustパーサーは深いバックトラックは行わないように設計されているため、復元処理は必要ない。

なお、A && BA & &B はどちらも構文的にありえるため、この位置に && が来ても分割は行われない。

fn main() {
    println!("{}", &1 & &2);
    // println!("{}", &1&&2); // Error
}

<<>> の処理

<, > を含む字句は <, >, <=, >=, <<, >>, <<=, >>=, <-, ->, => である。 (<- はplacementと呼ばれるunstable機能のためのトークン)

  • 比較の二項演算 <, ><=>=
  • 左/右シフト <<, >> とそれらの複合代入
  • placement X <- Y
  • fnFn*系トレイト、トレイト定義における戻り値型 ->
  • match の腕 =>
  • ジェネリクス引数の開始と終了 < .. >, ::< .. >
  • 修飾パスの開始 <SomeType>::, <SomeType as SomeTrait>::

なお、ジェネリクス引数の <, >二項演算子としての <, > は、構文レベルで注意深く区別されている。

この中でトークン分割が問題になるのは、 <<, >>ジェネリクスの文脈で出てくる場合である。例えば、

fn main() {
    let x:Vec<u32>=Vec::<<u32 as ::std::ops::Add<u32>>::Output>::new();
    let x:Vec<Vec<u32>>=vec![];
}

>=, >>=, >>, << が分割され、正しくコンパイルされる。

二項演算子の位置では << を分割することはできないから、以下のような場合はパースできない。

fn main() {
    println!("{}", 0 < <u32 as ::std::ops::Add<u32>>::add(1, 2));
    // println!("{}", 0 <<u32 as ::std::ops::Add<u32>>::add(1, 2)); // Error
}

0.0 の処理

次のような場合はエラーになる。

fn main() {
    println!("{}", ((0, 1), (2, 3)).0.0); // Error
}

ドットの直後に浮動小数点数が来る場合は、このように2つのフィールドの組み合わせを意図していると考えられる。コンパイラは、曖昧性をなくすために括弧をつけることを提案してくれるが、そのまま解釈はしてくれないようだ(1.16.0時点)。

括弧をつけるのではなく、スペースをつけることで回避することもできる。

fn main() {
    println!("{}", (((0, 1), (2, 3)).0).0);
    println!("{}", ((0, 1), (2, 3)).0 .0);
}

このパースが通るようにするのは原理的には可能であるように思えるが、少なくとも現在は実行されていない。

Rustでグラフを表現するにはTyped Arenaが便利

概要: Rustでグラフのように相互参照を含むデータ構造を表現するには、Typed Arenaという方法が適している。これについて説明する

整数による表現

グラフの表現方法で、最も簡単なのは、ノードを整数で表し、グラフのデータを別に持つ方法である。

fn main() {
    let mut edges = vec![vec![]];
    edges[0].push(0);
    edges.push(vec![]);
    edges[1].push(0);
}

これは大抵どんな言語でも同じように使えるし、場合によってはこちらで済ませてしまったほうが簡単かもしれない。特に競技プログラミングではノードに付与されている情報が少なかったり、ノードに明示的に整数が付番されていたりするため、ほとんどの場合整数で表現するほうが扱いやすい。

しかしこの方法では、整数とグラフデータとの対応関係を見失いやすいと考えられる。整数を別の構造体で包んだり、indexingというライブラリを使うなどして、マーカーをつける手はあるが、それにしてもやや面倒なことが多い。

参照による表現の問題点

そこで、ノードを構造体で表し、その参照を持ち回すことを考える。

ノードは複数の別のノードから参照されるから、 &mut は使えない。しかしグラフを途中で変更する必要が出るかもしれない。そのような場合、つまり & をimmutable referenceではなくshared mutable referenceとして使いたいときは、 RefCell を使うのであった。

例えば、グラフのノードは以下のように表現できる。

use std::cell::RefCell;

struct NodeData<'a> {
    references: RefCell<Vec<Node<'a>>>
}
type Node<'a> = &'a NodeData<'a>;

この定義自体は問題ない、しかしグラフを次のように構築しようとすると問題が発生する。

fn main() {
    let node0 = NodeData { references: RefCell::new(vec![]) };
    node0.references.borrow_mut().push(&node0);
    let node1 = NodeData { references: RefCell::new(vec![]) };
    node0.references.borrow_mut().push(&node1);
}
rustc 1.16.0 (30cf806ef 2017-03-10)
error: `node1` does not live long enough
  --> <anon>:13:1
   |
12 |     node0.references.borrow_mut().push(&node1);
   |                                         ----- borrow occurs here
13 | }
   | ^ `node1` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

error: aborting due to previous error

要するに、ノードは相互に参照しあうため、きっかり同一の生存期間を持たなければならない。

ノードの個数が決まっていれば、次のように Vec で確保するといった方法をとることができる。

use std::cell::RefCell;

struct NodeData<'a> {
    references: RefCell<Vec<Node<'a>>>
}
type Node<'a> = &'a NodeData<'a>;

fn main() {
    let mut nodes = vec![];
    nodes.push(NodeData { references: RefCell::new(vec![]) });
    nodes.push(NodeData { references: RefCell::new(vec![]) });
    let node0 = &nodes[0];
    let node1 = &nodes[1];
    node0.references.borrow_mut().push(node0);
    node0.references.borrow_mut().push(node1);
}

しかし、この方法では、動的にノードを追加することはできない。

Typed Arena を使ったメモリ確保

Typed Arenaと呼ばれるライブラリを使うと、同一生存期間を持ったメモリを複数回に分けて確保することができる。

Typed Arenaは、 arena crateの arena::TypedArenatyped_arena crateの typed_arena::Arena がある。これらはほぼ同じ内容だが、 arenaコンパイラ内部で使うためにあり、通常はnightlyでしか使えない。通常の用途では typed_arena を使う。

[dependencies]
typed-arena = "1.2.0"
extern crate typed_arena;

use std::cell::RefCell;
use typed_arena::Arena;

struct NodeData<'a> {
    references: RefCell<Vec<Node<'a>>>
}
type Node<'a> = &'a NodeData<'a>;

fn main() {
    let nodes = Arena::new(); // mut は不要
    let node0 = nodes.alloc(NodeData { references: RefCell::new(vec![]) });
    node0.references.borrow_mut().push(node0);
    let node1 = nodes.alloc(NodeData { references: RefCell::new(vec![]) });
    node0.references.borrow_mut().push(node1);
}

まとめ

相互参照を含むデータ構造では2つの問題があり、それぞれに解決策がある。

  • 複数の参照を保持しつつ、データを書き換えたい場合がある。→ RefCell を使う。
  • 相互に参照するため、同一生存期間をもつデータを複数用意したい。→ 最初に一括で確保するなら Vec 等でよい。動的に確保したければ typed_arena::Arena (または arena::TypedArena) を使う。

TypedArena はRustコンパイラでも使われている。例えばインポート解決はグラフを扱うため TypedArena を用いる。

Rustの基本型の名前解決

Rustの基本型の名前はキーワードではない。したがって基本型の名前は名前解決と同時に処理されることになる。ところがややこしい点として、基本型と同名のモジュールに解決される場合もある。この挙動について調べた。

基本型の名前は PrimitiveTypeTable::new で列挙されており、以下の名前を含んでいる。

  • bool
  • char
  • i8, i16, i32, i64, i128, isize
  • u8, u16, u32, u64, u128, usize
  • f32, f64
  • str

なお、これらに含まれない(記号で表される)基本型としては、&'a T, &mut 'a T, *const T, *mut T, [T; n], [T] がある。処理系が特別扱いする Box<T>, PhantomData<T>, NonZero<T>, UnsafeCell<T> なども基本型に準じると考える場合があるかもしれない。

基本型の名前の処理は resolve_qpathの中 で行われている。QPathは式や型などに出てくるものであり、例えば use のパスはこの処理の対象外であり、常に通常の名前として解決されるということになる。

このコードによると、パスの最初の要素が基本型として処理される条件は

  • パスはQSelf (<A as Foo>:: のような部分) を含まない。
  • パスの最初の要素が、上記の基本型の名前のいずれかである。
  • パスの最初の要素が、型名前空間で解決されようとしている。
  • 通常の方法でのパスの解決に失敗したか、またはパス全体が正規モジュール(ルートモジュールまたは mod)に解決された。

である。

これにより、例えば

use std::f64;

fn main() {
    let x : f64 = 0.0f64;
    println!("{}", f64::sin(f64::consts::PI + x));
}

というコードがうまく動作することになる。ここで、 x の型と、 f64::sinf64 は、基本型に解決される。一方、 f64::consts::PIf64 は、 ::std::f64 モジュールとして解決される。

ソースコードには、この挙動は「後方互換性のため」と書いてあるが、これが将来のサポート廃止を意図しているのか、そうではないのかは、判断がつかない。(少なくともサポート廃止という話を聞いたことはない)

なお、以下の2つは別の場所で解決される。

  • 0.0f64 のように、リテラルの型を明示する機能で出てくる型名は、構文解析のタイミングで処理される。
  • 標準ライブラリの impl f64 は、実際にはSelf型の部分は関係なく、 #[lang="f64"] により発見される。

Rustのモジュールの復習

以前名前解決についてまとめたが、やはり調べ損ねている部分があるので、もう一度まとめてみた。

DefとModuleとNameBindingKind

DefId はRust中に出現する定義(enum, enum のバリアント、 fn, let, macro_rules! foo など)を指している。これはcrateのID + crate内の識別番号で表される。 Def は大雑把に言うと DefId に追加の情報を加えたものである。

Rustの(広義の)モジュールはModuleDataで表されている。広義のモジュールは以下からなる。

  • 各crateのルートモジュール
  • mod
  • enum
  • trait
  • ブロック

ブロック以外は Def でありしかも名前をもつため ModuleKind::Def(Def, Name) で定義される。一方ブロックは ModuleKind::Block(NodeId) で定義される。

モジュールには様々な名前を束縛することができる。束縛される値は NameBindingKind で列挙されている。

  • NameBindingKind::Def: Def
  • NameBindingKind::Module: 狭義のモジュール (ルートモジュールと mod)
  • NameBindingKind::Import: use

親モジュール

広義のモジュールは高々1つの親モジュールを持つ。これによりモジュールは森構造をなす。根となるのは各crateのルートモジュールのみである。

モジュールの親子関係はASTの祖先/子孫関係と対応していると考えてよい。

親子関係は、次に述べる正規祖先と組み合わせて super の解決に用いられるほか、可視性の基準に用いられる。

正規祖先

親リンクとは別に、各モジュールは正規祖先へのリンクを持つ。正規祖先は以下のように定義される。

  • 狭義のモジュール (ルートモジュールと mod) の正規祖先はそれ自身である。
  • それ以外 (enumtrait とブロック) の正規祖先は、その親モジュールの正規祖先である。
    • 現行のソースを見る限り、内部的には、非ローカルcrateの enum の正規祖先はそれ自身であるように見えるが、これはよくわからない……

正規祖先へのリンクは DefId で保持しているが、利用するときは Module を取り出す。

正規祖先は super/self の解決に用いられる。

解決

各モジュールは解決の一覧を持つ。解決は以下のような辞書エントリである。

  • キー: 識別子と名前空間(型、値、マクロのいずれか)の組。識別子は非衛生化された状態で保存される。
  • 値: NameBindingKind と衛生性マークと可視性の組。

パスの種類

パスは以下の3形式のいずれかからなる。

  • 相対パス: self または super と、追加の0個以上の super から始まるもの。
    • ただし、 self のみからなり、型またはモジュール以外の文脈の場合は、レキシカルスコープのパスとして扱われる。
  • 絶対パス: :: または $crate から始まるもの。
  • レキシカルスコープのパス: 通常の識別子のみ(1個以上)からなるもの。

相対パスの場合、 selfsuper は以下のように解決される。

  • self は、現在のモジュールの正規祖先である。
  • super 1個につき、「親モジュールの正規祖先」を辿る操作が1回行われる。

絶対パスの場合、解決の開始位置は以下のように決定される。

  • :: の場合、ローカルcrate (現在コンパイル中のcrate) のルートモジュールから解決が開始される。
  • $crate は、該当マクロ定義のあったcrateのルートモジュールから解決が開始される。詳しくは過去の記事を参照。

レキシカルスコープのパスの場合、最初の識別子はレキシカルスコープで解決される(後述)。

レキシカルスコープからの解決

レキシカルスコープはコンパイラ内ではRibという単位で管理されている。Ribは以下の地点で発生する。

  • ルートモジュールと mod: ModuleRibKind (値と型)
  • 関数: ItemRibKind (値とラベル)
  • enum, type, struct, union, fn: ItemRibKind (型)
  • メソッド(trait, impl 内の fn): MethodRibKind (値とラベルと型)
  • クロージャ: ClosureRibKind (値とラベル)
  • trait, impl: ItemRibKind (型)
  • ラベルつきブロック: NormalRibKind (ラベル)
  • 配列型の長さ、バリアントの判別子、 const, traitconst: ConstantItemRibKind (値と型)
  • traitimpl: NormalRibKind (型)
  • matchの各節: NormalRibKind (値)
  • ブロック (匿名モジュールの場合): ModuleRibKind (値と型)
  • ブロック (匿名モジュールでない場合): NormalRibKind (値)
  • block / macros_at_scope: MacroDefinition (値とラベル)
  • with_module_lexical_scope: ModuleRibKind (値と型)
  • if let, while let, for in: NormalRibKind (値)

Rib は識別子と解決先の一覧を保持している。ただしこれらの更新のタイミングはRibの種類によって異なる。例えば、

  • ModuleRibKind は、モジュールに入った時点で全ての一覧が完成した状態になる。構文上の位置は関係ない。
  • NormalRibKind は、モジュールに入った時点では一覧は存在せず、パス解決と同時に更新されていく。例えば let の前後で名前解決の挙動が違うのはこの仕様により実現されている。

resolve_ident_in_lexical_scope は、このRibを内側から外側に順番に調べ、ローカル定義またはアイテムがあれば終了する。ただし、探索途中で、ブロック(匿名モジュール)以外の ModuleRibKind に遭遇した場合は、この探索を打ち切る。この規則により、上位モジュールでの use が下位モジュールに影響を与えるのを防いでいる。

なお、レキシカルスコープからの解決では、値名前空間は構文文脈を含めた状態で解決されるが、型名前空間は識別子を非衛生化した状態で解決される。

use のレキシカルスコープ解決

use に出現するパスは、他のパス解決よりも前に行われる。このときはRibはルートモジュールのみ存在するため、レキシカルスコープのパスは絶対パスとほぼ同じ意味になる。

パスの途中の要素の解決

パスの要素について、名前空間は以下のように決定される。

  • 最後以外の全ての要素は、型名前空間として扱われる。
  • 最後の要素は、型またはモジュールの文脈であれば型名前空間、値の文脈であれば値名前空間として扱われる。

パスの途中の要素の解決は、だいたい想像される通りのことが起こっている。ただし識別子は非衛生化される。

また、パス解決が途中で失敗した場合(直前がモジュールでなかった or モジュールだったが、名前を検索しても見つからなかった場合)も、この時点ではエラーにはならない。残りの部分は関連型やメソッドなどの名前かもしれないからである。この時点では、パスのどの要素まで解決されたかを含めて返し、残りはloweringや型検査の途中で処理することになる。

まとめ

とりわけ注意が必要なのは以下の点

  • 狭義のモジュールと広義のモジュールがある。 enum, trait, そしてブロックはモジュールの一種とみなされる。(正規祖先の定義も要確認)
  • パスは相対パス絶対パス・レキシカルスコープのパスの3種類がある。
  • use とそれ以外では解決のタイミングが異なる。 use でレキシカルスコープ形式のパスが使われた場合、実際には絶対パスとほぼ同義になる。
  • use 以外でレキシカルスコープ形式のパスが使われた場合、レキシカルスコープの探索は狭義のモジュールの境界で打ち切られる。
  • 同じ識別子でも、名前空間や構文文脈により区別されることがある。

Rustの文でセミコロンを省略してよい条件

Rustの文でセミコロンを省略してよい条件を説明する。

意味論的な原則

Rustのセミコロンは意味と構文からそれぞれ説明できる。意味論的には、以下の原則を覚えておけば十分である。

  • セミコロンで終端された文は強制的に () 型となる。
  • ブロックの途中の文は () 型でなければならない。ブロックの型はブロックの最後の文の型と等しい。(文がひとつもない場合は ())
fn main() {
    let x = { let x = 10; x + 1 }; // x + 1 を返したいので、セミコロンをつけてはいけない
    if true { 1 } else { 0 }; // 構文上は省略できるが、 () 型にするためにセミコロンをつける
    println!("Hello!\n"); // 値を返したいわけではないので、セミコロンをつける
}

構文上の大原則

大原則は、「文同士はセミコロンで区切らなければならない。ただし } で終わる文のセミコロンは省略できる」である。

しかし実際には以下の例外を考慮する必要がある。

例外1: } で終わる式文の場合

文は式文let文文マクロアイテム文 にわかれている。式文は、式をそのまま文とみなすという規則のことである。

if, if let (elseを含む), while, while let, loop, for in, match およびブロック式は } で終わる(これらはC/C++では文だが、Rustでは式であることに注意)。これらの式のパースは、特定条件下で打ち切られる。具体的には、以下の2つの条件を満たしている必要があるようだ。

  • これらの式の直前に別のトークンがパースされていない。例えば、let x = if .., (if .., 1 + if .. は対象外となる。
  • これらの式の直後に ?.some_method(..) が後続しない。例えば、 { }?{ }.f() は対象外となる。

例えば以下の例で、最初の if 文は } でパースが打ち切られている。しかし、次の if 文は ( 10 ) まででひとつの文となる。つまりこの main 関数には3つの文があることになる。

fn f(x: u32) -> u32 { println!("f({})", x); 10 }
fn main() {
    if true { () } else { () } ( 10 );
    1 + if true { f } else { f } ( 10 );
}

(なお、この打ち切り規則はRESTRICTION_STMT_EXPRと呼ばれ、式文のほかに match の各節の右辺にも適用される。)

例外2: let 文の場合

let 文ではセミコロンの省略はできない。これはブロックの末尾でも同様である。

fn main() {
    let x = if true { 0 } else { 0 }; // セミコロンが必要
    let x = 0; // セミコロンが必要
}

例外3: } で終わる文マクロの場合

マクロは {}, (), [] のいずれの括弧でも呼び出せるが、括弧の種類によって構文上の挙動が変わる。文の位置に出現するマクロについては、 {} で呼び出すとセミコロンを省略できる。

fn main() {
    println!{"Hello!"}
    println!{"World!"}
}

ただし、書いたマクロが文マクロとして認識されるか、式マクロとして認識されるかには注意が必要である。具体的には以下の条件でマクロが文マクロと認識される。

  • 文の位置で始まっている。例えば 1 + foo!{ } では foo!{ } は式マクロとして認識される。
  • {} で呼び出されているか、または ; で終端されている。例えば foo!{} - 1;foo!(); - 1; は2つの文として解釈されるが、 foo!() - 1; は1つの文として解釈される。

例外4: } で終わるアイテム文の場合

アイテムのうちセミコロンを必要としないものは、アイテム文でも同様にセミコロンを必要としない。

fn main() {
    struct A {} // セミコロン不要
    let x = A {};
}

まとめ

Rustの文におけるセミコロンは、意味論的には「型を () に強制するために必要」、構文的には「区切り文字として必要。ただし } の直後では不要」という原則を理解すればそれほど難しくはなさそうだ。しかし、実際には構文解析の一貫性等の問題から、この原則に対する例外があることは、記憶の片隅に留めておいてもいいかもしれない。

Rust トレイトオブジェクトの生存期間境界の既定値

概要: トレイトオブジェクト型には生存期間を指定できるが、省略した場合既定値が適用される。この既定値を決定する規則について説明する。

トレイトオブジェクトの生存期間境界

トレイトオブジェクトは正確には以下の構文を持つ。

// obligation 1: only Send, Sync, or lifetimes are allowed in TraitObjectBound.
//               (multiple occurences of Send or Sync are allowed)
// obligation 2: at most one occurence of lifetime is allowed in TraitObjectBound.

TyTraitObject ::= PolyTraitRef ("+" TraitObjectBound)* "+"?

TraitObjectBound ::= PolyTraitRef | Lifetime

PolyTraitRef ::= ("for" "<" LifetimeParams ">")? TraitRef

LifetimeParams ::= ( )
                 | LifetimeParam ("," LifetimeParam)* ","?

LifetimeParam ::= Lifetime (":" LifetimeBounds)?

LifetimeBounds ::= ( )
                 | Lifetime ("+" Lifetime)* "+"?

文章で説明すると、以下のようになる。

  • 原則として、 Foo のようにトレイト名を書くと、これがそのままトレイトオブジェクト型になる。
  • for<'a> Foo<'a> のように、全称量化を書くことができる。引数には生存期間のみ指定できる。
  • Foo + Send + 'a のように、 + で複数の境界を繋ぐことができる。この時最初の要素はトレイトでなければならない。
  • 最初以外の要素にトレイトを指定する場合は、 Send または Sync を指していないといけない。それ以外のトレイトを指定した場合はエラーになる。
  • 生存期間は最大1個だけ指定できる。(Foo + 'a + 'a のように同じものを書くのも禁止されているようだ)

例えば、行儀は良くないが、以下のようなコードが書ける。

trait Foo {}

fn f<'a>(_: &(for<'b: 'a +> Foo + std::marker::Send + 'a + Send + Sync + for<'b:, 'c> Send +)) {}

fn main() {
}

トレイトオブジェクトの生存期間境界の既定値

上記のように、トレイトオブジェクトには生存期間を最大1個指定できるが、指定されなかった場合は既定値が適用される。

トレイトオブジェクトの生存期間境界の既定値は、Rust RFC 1156 にて (Rust RFC 0599を上書きする形で)規定されている。

Rust RFC 1156によると、これは以下の規則に基づく。

  • トレイトオブジェクトの生存期間境界は、たとえ省略されていても、生存期間の省略規則(lifetime elision)の適用対象外となる。つまり生存期間の省略規則 (lifetime elision) の解決後も、未解決のまま残っている。本規則は、生存期間の省略規則 (lifetime elision) の解決後に適用される。
  • 該当トレイトオブジェクトの生存期間境界は、その外側の型に応じて決定される。
    • 外側が参照の場合は、その参照の生存期間が採用される。
    • 外側がユーザー定義型(構造体、列挙型、共用体)の場合は、以下の規則に基づいて決定される。
      • 該当型引数に生存期間による境界 T: 'a がただ1つある場合は、それが採用される。
      • 生存期間による境界 T: 'a が2つ以上ある場合は、コンパイルエラーとなる(プログラマは生存期間を明示しなければならない)。
      • 生存期間による境界がない場合は、構文上の位置に依存して、さらに以下の規則に従う。
        • 関数本体では、新たな生存期間変数が生成される。
        • それ以外(関数シグネチャや構造体定義など)では、 'static が採用される。
    • それ以外の型や、外側がない場合は、 'static が採用される。

実際のコンパイラではastconvの関数内 でこの処理が行われている。これを読み解くと、より正確な規則は以下のようになる。

  • トレイトオブジェクトの生存期間境界は、生存期間の省略規則(lifetime elision)の適用対象外となる。 (GatherLifetimesの該当部分)
  • Rust RFC 1156に従って生存期間の解決を試み、 map (named_region_map) に追加する。 resolve_object_lifetime_default
    • 生存期間が明示されていれば、以下の処理は実行されない。 (LifetimeContextの該当部分)
    • スコープを内側から外側に走査し、 Scope::ObjectLifetimeDefault という指示が最初に見つかったところで終了する。
    • みつからなかった場合は 'static が採用される。
    • Scope::ObjectLifetimeDefault は以下の2つの位置に生成される。
    • 1つ目は参照の内側である。 (LifetimeContextの該当部分)
    • 2つ目はパス(識別子)で表される名前全般(構造体、共用体、列挙型、型別名、トレイト、関連型、列挙型のバリアント)の型実引数の内側である。 (LifetimeContextの該当部分)
    • 2つ目については、対応する仮引数に対する境界 (T: 'a)が検索される。 (object_lifetime_defaults_for_item)
    • 検索された境界に対して、以下のような判定が行われる。 (LifetimeContextの該当部分)
      • ひとつもないとき: 関数本体なら、この時点では生存期間を割り当てない。それ以外の文脈の場合は 'static を割り当てる。
      • ちょうど1つあるとき: その生存期間引数が採用される。
      • 2つ以上あるとき: 「曖昧」とする。この時点では生存期間を割り当てない。
  • 上記で部分的に解決された named_region_map を用いて、 hir::TyTraitObjectty::TyDynamic に変換する (astconvの関数内)
    • 生存期間が明示されている場合は、それを採用する。
    • それ以外の場合は、該当トレイトの Self: 'a 境界を(おそらく再帰的に)検索する。 (compute_object_lifetime_bound)
      • 推測だが、これは「生存期間」ではなく「リージョン」の境界を検索している。したがって関数本体の外では'static以外の境界が実際には列挙されないものと思われる。
      • Self: 'static 境界がある場合、 'static が採用される。
      • それ以外に、 Self: 'a 境界がちょうど1つあるとき(Self: 'a + 'a のような重複も1つと数える)、その生存期間が採用される。
      • Self: 'a 境界が2つ以上あるとき、「曖昧」でエラーとなる。
      • Self: 'a 境界がない場合は、次の手段を試す。
    • 上の方法でうまくいかない場合は、先ほど生成した named_region_map から解決済みの生存期間を取り出す。
    • それも見つからない場合は、リージョン推論を試みる(新しいリージョン変数を生成する)。
    • それもできない場合(関数本体ではなく、外側のユーザー定義型に2個以上の境界が指定されていた場合)は、エラーになる。
    • 解決済みでない場合は、「関数本体内かつ、外側のユーザー定義型に境界が指定されていなかった」場合か、「外側のユーザー定義型に2個以上の境界が指定されていた」場合のいずれかである。

まとめ

トレイトオブジェクトは生存期間境界を1つ指定できるが、省略された場合は一定の規則にしたがって既定値が与えられる。既定値はRFC1156に指定されているように、原則として型の構造とその型に指定された境界によって決められるが、関数本体で使われている型についてはさらに複雑な規則が与えられている。Rustの細かい仕様を追っているといつも思うが、比較的若い言語にしてはかなり複雑な仕様(あるいはコンパイラ実装上生じてしまった複雑性)を抱えている部分が多く、綺麗な見た目と比較して驚きを覚える。

トレイトオブジェクトのメソッド解決

Rustのこのissueで知ったが、トレイトオブジェクトのメソッド解決はやや特殊らしい。

特殊といっても特に難しいことはない。トレイトオブジェクトは、元となったトレイトを実装するが、それだけではなく、元のトレイトのメソッドを、固有メソッドとしても解決できるようになっている。

例えば以下のように動作する。トレイトメソッドの解決の一般論は過去の記事を参照。

// Fooを実装するとBarも実装される。FooとBarはm1の中にある
mod m1 {
    pub trait Foo {
        fn foo(&self) -> String;
    }
    pub trait Bar {
        fn bar(&self) -> String;
    }
    impl<T: Foo + ?Sized> Bar for T {
        fn bar(&self) -> String {
            format!("T::bar(_) from {}", self.foo())
        }
    }
}

struct A;
impl m1::Foo for A {
    fn foo(&self) -> String { String::from("<A as m1::Foo>::foo(_)") }
}

fn main() {
    // AはFooを実装している(したがってAはBarも実装している)
    let x = A;
    // FooはFooを実装している(したがってFooはBarも実装している)
    let y : &m1::Foo = &x;

    {
        // 通常、メソッド記法はトレイトがスコープ内になければ解決されない。
        use m1::Foo; // これが必要
        println!("1 {}", x.foo());
    }
    {
        // trait objectのメソッドは固有メソッドとして再定義されているかのように振る舞う。
        // use m1::Foo; // 不要
        println!("2 {}", y.foo());
    }
    {
        // Foo: Barではあるが、barはtrait Foo自身のメソッドではないため、固有メソッドにはならない。
        use m1::Bar; // これが必要
        println!("3 {}", y.bar());
    }
}

つまり、トレイトオブジェクト型 Foo は、トレイト Foo で宣言されているメソッドを固有メソッドとして再定義するFoo: Foo から誘導される他のトレイト実装のメソッドは再定義の対象とはならない。

ただし、スーパートレイト境界 (またはwhere節における Self に対する等価なトレイト境界) が指定されている場合、このスーパートレイトのメソッドも再定義の対象となる

mod m1 {
    pub trait Foo : Bar {
        fn foo(&self) -> String;
    }
    pub trait Bar {
        fn bar(&self) -> String;
    }
}
struct A;
impl m1::Foo for A {
    fn foo(&self) -> String { String::from("<A as m1::Foo>::foo(_)") }
}
impl m1::Bar for A {
    fn bar(&self) -> String { String::from("<A as m1::Bar>::bar(_)") }
}

fn main() {
    let x = A;
    let y : &m1::Foo = &x;
    {
        use m1::Foo; // これが必要
        println!("1 {}", x.foo());
    }
    {
        // use m1::Foo; // 不要
        println!("2 {}", y.foo());
    }
    {
        // use m1::Bar; // 不要
        println!("3 {}", y.bar());
    }
}

さて、この処理はコンパイラassemble_probe で行われているようだ。

    fn assemble_probe(&mut self, self_ty: Ty<'tcx>) {
        debug!("assemble_probe: self_ty={:?}", self_ty);

        match self_ty.sty {
            ty::TyDynamic(ref data, ..) => {
                if let Some(p) = data.principal() {
                    self.assemble_inherent_candidates_from_object(self_ty, p);
                    self.assemble_inherent_impl_candidates_for_type(p.def_id());
                }
            }
            ty::TyAdt(def, _) => {
                self.assemble_inherent_impl_candidates_for_type(def.did);
            }
            ...
        }
    }

このassemble_inherent_candidates_from_objectが、元トレイトのメソッドを固有メソッドとして再収集していると思われる。