Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

エイリアスと正規化

エイリアス

Rust には、何らかの「基になる」型と等しいと見なされる型がいくつかあります。たとえば、固有関連型、トレイト関連型、自由型エイリアス（type Foo = u32）、不透明型（-> impl RPIT）などです。こうした型を「エイリアス」と見なし、エイリアス型は TyKind::Alias バリアントで表現され、エイリアスの種類は AliasTyKind enum によって追跡されます。

正規化とは、これらのエイリアス型を取得し、それらが等しい基になる型で置き換える処理です。たとえば、型エイリアス type Foo = u32 がある場合、Foo を正規化すると u32 になります。

エイリアスという概念は型に固有のものではなく、この概念は定数/const generics にも適用されます。しかし、現在のコンパイラでは const エイリアスを「第一級の概念」として実際には扱っていないため、この章では主に型の文脈で説明します（ただし、概念自体は問題なく転用できます）。

リジッド、曖昧、および未正規化のエイリアス

エイリアスは「リジッド」、「曖昧」、または単に未正規化のいずれかです。

型の「形状」が変化しない場合、その型をリジッドと見なします。たとえば Box はリジッドです。どれだけ正規化しても Box を u32 に変えることはできないためです。一方、<vec::IntoIter<u32> as Iterator>::Item は u32 に正規化できるため、リジッドではありません。

エイリアスは、それ以上正規化できるようになることが決してない場合にリジッドです。リジッドなエイリアスの具体例は、T: Iterator<Item = ...> 境界がなく、単なる T: Iterator 境界だけがある環境における <T as Iterator>::Item です。

#![allow(unused)]
fn main() {
fn foo<T: Iterator>() {
    // このエイリアスは*リジッド*です
    let _: <T as Iterator>::Item;
}

fn bar<T: Iterator<Item = u32>>() {
    // このエイリアスは `u32` に正規化できるため、リジッド*ではありません*
    let _: <T as Iterator>::Item;
}
}

エイリアスがまだ正規化できないものの、現在の環境では最終的に正規化可能になるかもしれない場合、それを「曖昧」なエイリアスと見なします。これは、エイリアスに推論変数が含まれており、トレイトがどのように実装されているかを判断できない場合に発生することがあります。

#![allow(unused)]
fn main() {
fn foo<T: Iterator, U: Iterator>() {
    // このエイリアスは「曖昧」と見なされます
    let _: <_ as Iterator>::Item;
}
}

これらを「曖昧」なエイリアスと呼ぶ理由は、それがリジッドなエイリアスかどうかが曖昧だからです。

_: Iterator トレイト impl の由来は曖昧（つまり不明）です。それは何らかの impl Iterator for u32 かもしれませんし、何らかの T: Iterator トレイト境界かもしれません。まだ分かりません。_: Iterator が成り立つ理由に応じて、そのエイリアスは未正規化のエイリアスである場合もあれば、リジッドなエイリアスである場合もあります。このエイリアスがどの種類のエイリアスなのかは曖昧です。

最後に、エイリアスは単に未正規化である場合があります。<Vec<u32> as IntoIterator>::Iter は、すでに std::vec::IntoIter<u32> に正規化できるにもかかわらず、まだそれが行われていないため、未正規化のエイリアスです。

Free エイリアスと Inherent エイリアスは、リジッドにも曖昧にもなり得ないことに注意する価値があります。なぜなら、それらを名指しすることは、そのエイリアスの基になる型を指定するエイリアス定義が解決済みであることも意味するためです。

発散するエイリアス

エイリアスは、その定義が正規化先となる基になる非エイリアス型を指定していない場合、「発散する」と見なされます。発散するエイリアスの具体例は次のとおりです。

#![allow(unused)]
fn main() {
type Diverges = Diverges;

trait Trait {
    type DivergingAssoc;
}
impl Trait for () {
    type DivergingAssoc = <() as Trait>::DivergingAssoc;
}
}

この例では、Diverges と DivergingAssoc はどちらも、自分自身と等しいものとして定義されている発散する型エイリアスの「自明な」ケースです。Diverges が正規化され得る基になる型は存在しません。

発散するエイリアスが定義されたときには、一般にはエラーにしようとしますが、これは完全に「ベストエフォート」のチェックです。前の例では、定義が検出できるほど「十分に単純」なので、エラーが出力されます。しかし、より複雑なケースや、ジェネリックパラメーターの一部のインスタンス化だけが発散するエイリアスを生じるケースでは、エラーを出力しません。

#![allow(unused)]
fn main() {
trait Trait {
    type DivergingAssoc<U: Trait>;
}
impl<T: ?Sized> Trait for T {
    // このエイリアスは常に発散しますが、コンパイラにはそれが
    // 「見えない」ため、エラーを出力しません。
    type DivergingAssoc<U: Trait> = <U as Trait>::DivergingAssoc<U>;
}
}

最終的に、これは型システム内のエイリアスが発散しないという保証がないことを意味します。エイリアスは一部の特定のジェネリック引数でのみ発散する場合があるため、エイリアスが発散するかどうかは、それが完全に具体化されて初めて分かるということでもあります。つまり、コード生成/const 評価も発散するエイリアスを扱わなければなりません。

trait Trait {
    type Diverges<U: Trait>;
}
impl<T: ?Sized> Trait for T {
    type Diverges<U: Trait> = <U as Trait>::Diverges<U>;
}

fn foo<T: Trait>() {
    let a: T::Diverges<T>;
}

fn main() {
    foo::<()>();
}

この例では、foo::<()> のコード生成中にのみ、発散するエイリアスによるエラーに遭遇します。foo への呼び出しが削除されると、コンパイルエラーは出力されません。

不透明型

不透明型は比較的特殊な種類のエイリアスであり、独自の章で扱われています: 不透明型。

Const エイリアス

型エイリアスとは異なり、const エイリアスは型システム内で直接表現されません。代わりに、const エイリアスは常に、const アイテムへのパス式を含む匿名ボディです。これは、型システムにおける唯一の「const エイリアス」が、匿名の未評価 const 本体であることを意味します。

したがって、ConstKind::Alias(AliasCtKind::Projection/Inherent/Free, _) は存在せず、代わりに匿名定数を表現するために使用される ConstKind::Unevaluated だけがあります。

#![allow(unused)]
fn main() {
fn foo<const N: usize>() {}

const FREE_CONST: usize = 1 + 1;

fn bar() {
    foo::<{ FREE_CONST }>();
    // const 引数は何らかの匿名定数で表現されます:
    // ```pseudo-rust
    // const ANON: usize = FREE_CONST;
    // foo::<ConstKind::Unevaluated(DefId(ANON), [])>();
    // ```
}
}

これは const generics の機能が改善されるにつれて変わる可能性が高いです。たとえば、feature(associated_const_equality) と feature(min_generic_const_args) はどちらも、const エイリアスを型と同様に扱うこと（すべての const 引数を匿名定数でラップしないこと）を必要とします。

正規化とは何か

構造的正規化と深い正規化

正規化には、構造的（浅いとも呼ばれることがあります）と深いものの 2 つの形式があります。構造的正規化は、型の「最外層」の部分だけを正規化するものと考えるべきです。一方、深い正規化は型内のすべてのエイリアスを正規化します。

実際には、構造的正規化によって型の外側の層だけでなくそれ以上が正規化される場合がありますが、この振る舞いに依存すべきではありません。束縛変数（for<'a>）を利用する、正規化不能な非リジッドエイリアスは、どちらの種類の正規化によっても正規化できません。 例として、概念的には、型 Vec<<u8 as Identity>::Assoc> を構造的に正規化しても no-op になりますが、深く正規化すると Vec<u8> になります。ただし実際には、構造的正規化でも Vec<u8> になりますが、繰り返しになりますが、これに依存すべきではありません。

エイリアスを束縛変数を使うように変更すると、異なる挙動になります。Vec<for<'a> fn(<&'a u8 as Identity>::Assoc)> は、構造的に正規化した場合は変化しませんが、深く正規化した場合は Vec<for<'a> fn(&'a u8)> になります。

コア正規化ロジック

エイリアスを構造的に正規化することは、そのエイリアスを定義内で等しいものとして定義されているものに置き換えるよりも、少し微妙です。エイリアスを正規化した結果は、剛性型か推論変数（後で剛性型に推論される）のいずれかであるべきです。これを実現するために、2 つのことを行います。

まず、曖昧なエイリアスを正規化する際には、それをそのまま残すのではなく推論変数に正規化します。これには主に 2 つの効果があります。

  • 推論変数は剛性型ではありませんが、常に剛性型へ推論されることになるため、正規化の結果を再度正規化する必要がないことを保証できます
  • 推論変数は、型が非剛性であるすべての場合に使用されるため、コンパイラの他の部分が曖昧なエイリアスと推論変数の両方を扱う必要がなくなります

次に、正規化がエイリアスの定義で指定された型を直接返すのではなく、返す前にまずその型を正規化します1。これは、正規化が冪等であり、呼び出し元がループ内で実行する必要がないようにするためです。

#![allow(unused)]
#![feature(lazy_type_alias)]

fn main() {
type Foo<T: Iterator> = Bar<T>;
type Bar<T: Iterator> = <T as Iterator>::Item;

fn foo() {
    let a_: Foo<_>;
}
}

この例では次のようになります。

  • Foo<?x> を正規化すると Bar<?x> になりますが、Foo が等しいものとして定義されている型内のエイリアスを正規化したい
  • Bar<?x> を正規化すると <?x as Iterator>::Item になりますが、ここでも、Bar が等しいものとして定義されている型内のエイリアスを正規化したい
  • <?x as Iterator>::Item を正規化すると、<?x as Iterator>::Item は曖昧なエイリアスであるため、新しい推論変数 ?y になります
  • 最終結果として、Foo<?x> を正規化すると ?y になります

正規化の方法

型システムとやり取りする際には、型の正規化を要求する必要があることがよくあります。基礎となる正規化ロジックにはさまざまなエントリーポイントがあり、それぞれのエントリーポイントはコンパイラの特定の部分でのみ使用すべきです。

追加の複雑さとして、コンパイラは現在、古い trait ソルバーから新しい trait ソルバーへの移行中です。 この移行の一環として、コンパイラにおける正規化へのアプローチはかなり大きく変わっており、その結果、一部の正規化エントリーポイントは「古いソルバー専用」となり、新しいソルバーが安定化した後、長期的には削除される予定です。 この移行は、Github の WG-trait-system-refactor ラベルで追跡できます。

以下は、コンパイラにおける正規化のさまざまなエントリーポイントの大まかな概要です。

  • infcx.at.structurally_normalize
  • infcx.at.(deeply_)?normalize
  • infcx.query_normalize
  • tcx.normalize_erasing_regions
  • traits::normalize_with_depth(_to)
  • EvalCtxt::structurally_normalize

trait ソルバーの外部

InferCtxt 型は、解析中に正規化するための「主要な」方法である normalize、deeply_normalize、structurally_normalize を公開しています。これらの関数は、多くの場合、FnCtxt や ObligationCtxt のような各種 InferCtxt ラッパー型上でラップされ、いくつかの引数や戻り値の一部を自動的に扱うための小さな API 調整を加えて再公開されています。

構造的な InferCtxt 正規化

infcx.at.structurally_normalize は、推論変数とリージョンを扱える構造的正規化を公開しています。通常、型の kind を調べる場合には必ず使用すべきです。

HIR Typeck の内部には、関連する正規化メソッドである fcx.structurally_resolve があります。これは、解決対象の型が未解決の推論変数である場合にエラーになります。新しいソルバーが有効な場合は、その型を構造的に正規化することも試みます。

このため、HIR typeck には、型をまず normalize で正規化し（古いソルバーでのみ正規化）、その後 structurally_resolve する（新しいソルバーでのみ正規化）というパターンがあります。HIR typeck 中は、structurally_normalize を呼び出すよりもこのパターンを優先すべきです。なぜなら、structurally_resolve は goal を評価することで推論を進めようとする一方、structurally_normalize はそうしないためです。

深い InferCtxt 正規化

infcx.at.(deeply_)?normalize

InferCtxt で深く正規化する方法は、normalize と deeply_normalize の 2 つがあります。その理由は、normalize が古いソルバーでのみ使用される「レガシー」な正規化エントリーポイントである一方、deeply_normalize は長期的に深い正規化を行う方法として意図されているためです。これらのメソッドはいずれもリージョンを扱えます。

新しいソルバーが安定化すると、infcx.at.normalize 関数は削除され、すべてが新しい深い正規化または構造的正規化メソッドへ移行済みになります。このため、normalize 関数は新しいソルバーの下では no-op であり、古いソルバーでは正規化が必要だが新しいソルバーでは不要な場合にのみ適しています。

deeply_normalize を使用すると、曖昧なエイリアス2に遭遇したときにエラーが発行されます。これは、すべての曖昧なエイリアスを推論変数へ正規化することをサポートするのは不可能であるためです3。deeply_normalize は通常、曖昧なエイリアスに遭遇することを想定しない場合、たとえばアイテムシグネチャ由来の型を扱う場合にのみ使用すべきです。

infcx.query_normalize

infcx.query_normalize はごくまれに使用されます。これは normalize_erasing_regions とほぼ同じ制限（推論変数を扱えない、診断サポートがない）を持ちますが、主な違いはライフタイム情報を保持することです。このため、ほとんどすべての状況では normalize_erasing_regions の方が適切な選択です。ライフタイムを消去したクエリをキャッシュするため、より効率的だからです。

実際には、query_normalize は borrow checker での正規化に使われ、また他の箇所では infcx.normalize よりも性能面で最適化するために使われています。新しいソルバーが安定化した後は、新しいソルバーの正規化実装が性能低下にならない程度に十分高性能であるはずなので、query_normalize はコンパイラから削除できると期待されています。

tcx.normalize_erasing_regions

normalize_erasing_regions は、一般に型システム解析を行っていないコンパイラの部分で使用されます。この正規化エントリポイントは、推論変数、ライフタイム、診断を扱いません。リントとコード生成では、通常、整形式であると仮定できる（または少なくとも、それに対してエラーを出す責任を持たない）完全に推論済みのエイリアスを扱うため、このエントリポイントが多用されます。

トレイトソルバーの内部

traits::normalize_with_depth(_to) と EvalCtxt::structurally_normalize は、トレイトソルバーの内部（それぞれ旧ソルバーと新ソルバー）でのみ使用されます。これは、実質的に、各トレイトソルバーによって正規化がどのように実装されているかという内部への生のエントリポイントです。他の正規化エントリポイントは、トレイト解決の内部からは使用できません。そうすると、ゴールの循環と再帰深度を正しく扱えないためです。

いつ/どこで正規化するか（旧ソルバーと新ソルバー）

旧ソルバーと新ソルバーの大きな変更点の 1 つは、エイリアスがいつ正規化されるべきだと期待するかについてのアプローチです。

旧ソルバー

すべての型はできるだけ早く正規化されることが期待されます。これにより、型システムで遭遇するすべての型は、リジッドであるか、推論変数（後でリジッドな項へと推論される）のいずれかになります。

具体例として、エイリアスの等価性は、それらがリジッドであると仮定し、エイリアスのジェネリック引数を再帰的に等価化することで実装されています。

新ソルバー

すべての型は、曖昧なエイリアスや未正規化のエイリアスを含み得るものと期待されます。エイリアスが正規化されていることを必要とする操作が実行されるたびに、そのエイリアスを正規化する責任はそのロジックにあります（これは、ty.kind() でのマッチングは、ほぼ常に最初に構造的に正規化する必要があることを意味します）。

具体例として、エイリアスの等価性は、カスタムのゴール種別（PredicateKind::AliasRelate）によって実装されます。これにより、等価化されるすべてのエイリアス型がリジッドであると仮定する代わりに、エイリアスの正規化を自身で扱えるようになります。

このアプローチにもかかわらず、パフォーマンスと単純さのために、書き戻し中には依然として深く正規化します。これにより、MIR 内の型は引き続き深く正規化済みであると仮定できます。

新ソルバーで変更を行う動機となった、正規化に対する旧ソルバーのアプローチには、いくつかの主な問題がありました。

正規化呼び出しの欠落

正規化呼び出しが欠落していることはよくあり、その結果、すべてがすでに正規化されていることを期待する API に未正規化の型を渡してしまっていました。曖昧なエイリアスや未正規化のエイリアスをリジッドとして扱うと、エイリアス同士が等しいと見なされないことによるさまざまな奇妙なエラーや、未正規化エイリアスのジェネリック引数を等価化することによる予期しない推論の誘導が発生していました。

パラメータ環境の正規化

もう 1 つの問題は、旧ソルバーでは ParamEnv を正しく正規化できなかったことです。正規化自体が正しい結果を返すために、正規化済みの ParamEnv を期待するためです。詳細については、ParamEnv に関する章を参照してください: Typing/ParamEnvs: すべての境界の正規化

高ランク型における正規化不可能な非リジッドエイリアス

for<'a> fn(<?x as Trait<'a>::Assoc>) のような型が与えられた場合、正規化に対する旧ソルバーのアプローチでは、これを正しく扱うことはできません。

これを for<'a> fn(?y) に正規化し、for<'a> <?x as Trait<'a>>::Assoc -> ?y を正規化するゴールを登録すると、<?x as Trait<'a>>::Assoc が &'a u32 に正規化されるケースでエラーになります。推論変数 ?y は、for<'a> バインダーをインスタンス化するときに作成されるプレースホルダーよりも低い[ユニバース]に存在することになります。

エイリアスを未正規化のままにしておくことも誤りです。旧ソルバーはすべてのエイリアスがリジッドであることを期待するためです。これは、新ソルバーがコヒーレンスで安定化される前には健全性バグでした: coherence 中に projection substs を関連付けるのは不健全である。

最終的に、これは値の内部にあるすべてのエイリアスがリジッドであることを常に保証できるわけではない、ということを意味します。

発散するエイリアスの使用の扱い

発散するエイリアスは、曖昧なエイリアスと同様に、推論変数へと正規化されます。発散するエイリアスを正規化するとトレイトソルバーの循環が発生するため、旧ソルバーでは常にエラーになります。新ソルバーでは、現在のコンテキストですべてのゴールが成立することを要求するに至った場合にのみエラーになります。たとえば、HIR typeck 中に発散するエイリアスを正規化すると、どちらのソルバーでもエラーになります。

エイリアスの整形式性は、そのエイリアスが発散しないことを要求しません4。これは、エイリアスが整形式であることを確認するだけでは、発散するエイリアスに対してエラーを発行させるには十分ではないことを意味します。実際にそのエイリアスを正規化しようとする必要があります。

発散するエイリアスをエラーにすることが正規化の副作用であるということは、実際にエラーを発行するかどうかが非常に 恣意的 であることを意味します。また、現在は正規化する箇所が減っているため、旧ソルバーと新ソルバーの間でも異なります。 発散するエイリアスをエラーにすることが「問題」を引き起こす場当たり的な性質の例:

#![allow(unused)]
fn main() {
trait Trait {
    type Diverges<D: Trait>;
}

impl<T> Trait for T {
    type Diverges<D: Trait> = D::Diverges<D>;
}

struct Bar<T: ?Sized = <u8 as Trait>::Diverges<u8>>(Box<T>);
}

この例では発散するエイリアスが使われていますが、ジェネリックパラメーターのデフォルトを明示的に正規化することがないため、たまたまエラーを出力しません。?Sized によるオプトアウトを削除すると、<u8 as Trait>::Diverges<u8>: Sized ゴールをたまたま正規化することになり、その副作用として発散するエイリアスに関するエラーが発生します。

const エイリアスはここで型エイリアスと少し異なります。const エイリアスの整形式性には、それらが正常に評価できることが必要です（ConstEvaluatable ゴールによって）。つまり、const 引数の整形式性を単にチェックするだけで、それらが評価に失敗する場合にはエラーにするのに十分です。これを型エイリアスにも採用することに意味があるのか、それとも const エイリアスが整形式性のためにこれを要求するのをやめるべきなのかは、やや不明確です5。

  1. 新しいソルバーでは、これは暗黙的に行われます ↩

  2. バインダー内の曖昧なエイリアスの扱い方には、古いソルバーと新しいソルバーの間で微妙な違いがあります。古いソルバーでは、高階ランク型の内部にある一部の曖昧なエイリアスでエラーを出せませんが、新しいソルバーは正しくエラーにします。 ↩

  3. バインダー内の曖昧なエイリアスは推論変数へ正規化できません。これについては後ほど詳しく扱います。 ↩

  4. エイリアスが発散しないことのチェックは、それらが完全に具象化されるまで行えないため、これは、コード生成/定数評価の前にエイリアスが整形式であることをチェックできないか、単相化の後にエイリアスが整形式から非整形式へ変わるかのどちらかを意味します。 ↩

  5. これをやめたとしても、const エイリアスが型エイリアスより 安全性が低く なることは確かにありません ↩