高階トレイト境界
トレイト解決におけるより微妙な概念の 1 つに、高階トレイト
境界があります。そのような境界の例は for<'a> MyTrait<&'a isize> です。
高階トレイト参照に対する選択がどのように機能するかを見ていきましょう。
基本的なマッチングとプレースホルダーリーク
Foo というトレイトがあるとします。
#![allow(unused)]
fn main() {
trait Foo<X> {
fn foo(&self, x: X) { }
}
}任意の 'a について Foo<&'a isize> を実装する型を必要とする
関数 want_hrtb があるとしましょう。
fn want_hrtb<T>() where T : for<'a> Foo<&'a isize> { ... }ここで、任意の 'a について Foo<&'a isize> を実装する構造体
AnyInt があるとします。
struct AnyInt;
impl<'a> Foo<&'a isize> for AnyInt { }そして問題は、AnyInt : for<'a> Foo<&'a isize> が成り立つかどうかです。
答えは yes であってほしいところです。これを判断するアルゴリズムは、
高階型のサブタイピング（こちらで説明されており、
SPJ による論文にも記載されています。高階サブタイピングを理解したい場合は、
その論文を読むことをお勧めします）と密接に関連しています。いくつかの部分があります。
- 義務内の束縛領域をプレースホルダーに置き換える。
- impl をプレースホルダー義務とマッチさせる。
- _プレースホルダーリーク_を確認する。
では、この例を順に見ていきましょう。
-
最初に行うことは、義務内の束縛領域をプレースホルダーに置き換えることで、
AnyInt : Foo<&'0 isize>が得られます（ここで'0はプレースホルダー領域 #0 を表します）。 この時点で量化子がなくなっていることに注意してください。 コンパイラの型で言えば、これはty::PolyTraitRefからTraitRefへ変わるということです。次に impl からTraitRefを作成し、 その束縛領域には新しい変数を使用します（したがってFoo<&'$a isize>が得られます。ここで'$aは'aの推論変数です）。 -
次に、2 つのトレイト参照を関連付けると、
'0 == '$aという制約を持つグラフが得られます。 -
最後に、プレースホルダーの「リーク」を確認します。リークとは基本的に、 プレースホルダー領域を別のプレースホルダー領域、または impl のマッチ以前から存在していた 任意の領域に関連付けようとするあらゆる試みのことです。 リークチェックは、プレースホルダー領域から探索して、それが何らかの形で関連付けられている 領域の集合を見つけることで行われます。これは「汚染」集合と呼ばれます。 チェックに合格するには、その集合はそれ自身と impl 由来の領域変数のみで 構成されていなければなりません。汚染集合に他の領域が含まれている場合、 マッチは失敗します。この場合、
'0の汚染集合は{'0, '$a}であり、 したがってチェックは成功します。
失敗するケースを考えてみましょう。次のような構造体もあるとします。
struct StaticInt;
impl Foo<&'static isize> for StaticInt;義務 StaticInt : for<'a> Foo<&'a isize> は満たされていないと
見なされてほしいところです。チェックは以前と同じように始まります。'a は
プレースホルダー '0 に置き換えられ、impl のトレイト参照は
Foo<&'static isize> としてインスタンス化されます。この 2 つを関連付けると、
'static == '0 のような制約が得られます。これは、'0 の汚染集合が {'0, 'static} であることを意味し、リークチェックに失敗します。
TODO: これは、'static が領域変数ではないにもかかわらず
汚染集合に含まれているため、という理解で正しいですか？
高階トレイト義務
基本的なマッチングが終わると、次の興味深い話題に移ります。
impl 義務をどのように扱うかです。ここでは単純な例を順に見ていきます。
Foo と Bar というトレイトと、関連する impl があるとします。
#![allow(unused)]
fn main() {
trait Foo<X> {
fn foo(&self, x: X) { }
}
trait Bar<X> {
fn bar(&self, x: X) { }
}
impl<X,F> Foo<X> for F
where F : Bar<X>
{
}
}ここで、義務 Baz: for<'a> Foo<&'a isize> があり、この impl とマッチするとしましょう。
その結果としてどのような義務が生成されるでしょうか。得たいものは
Baz: for<'a> Bar<&'a isize> ですが、それはどのようにして起こるのでしょうか。
マッチング後、X => &'0 isize のようなプレースホルダー置換を持つ状態になります。
この置換を impl 義務に適用すると、F : Bar<&'0 isize> が得られます。
もちろん、これは直接使用できません。なぜならプレースホルダー領域 '0 は
この計算の外へリークできないからです。
そこで、'0 の汚染集合から、それの元になった元の束縛領域（ここでは 'a）への
逆マッピングを作成します。（これは higher_ranked::plug_leaks で行われます。）
リークチェックに合格していることは分かっているので、この汚染集合はプレースホルダー領域自身と
さまざまな中間領域変数のみで構成されています。次にトレイト参照を走査し、
その汚染集合内のすべての領域を後期束縛領域に戻します。そのため、この場合は最終的に
Baz: for<'a> Bar<&'a isize> になります。