候補の優先順位

Trait ゴールと NormalizesTo ゴールを証明する方法は複数あります。 そのような各選択肢は Candidate と呼ばれます。 適用可能な候補が複数ある場合、一部の候補を他の候補より優先します。 関連情報はそれらの CandidateSource に保存します。

この優先順位は、不正な推論やリージョン制約を引き起こす可能性があるため、コヒーレンス中には不健全になります。 そのため、コヒーレンスでは単にすべての候補のマージを試みます。

Trait ゴール

Trait ゴールは、適用可能な候補を fn merge_trait_candidates でマージします。 このドキュメントでは、現在の優先順位ルールが なぜ 存在するのかを説明するための追加の詳細と参照を提供します。

CandidateSource::BuiltinImpl(BuiltinImplSource::Trivial))

自明な builtin impl は、well-formed な型に対して常に適用可能であることが分かっている builtin impl です。 これは、もしそれが存在するなら、別の候補を使用しても制約が少なくなることは決してない、ということを意味します。 現在、自明であると見なしているのは Sized と MetaSized の impl のみです。

これは、次のパターンでライフタイムエラーを防ぐために必要です。

#![allow(unused)]
fn main() {
trait Trait<T>: Sized {}
impl<'a> Trait<u32> for &'a str {}
impl<'a> Trait<i32> for &'a str {}
fn is_sized<T: Sized>(_: T) {}
fn foo<'a, 'b, T>(x: &'b str)
where
    &'a str: Trait<T>,
{
    // `&'a str: Trait<T>` の where 境界を展開すると、
    // `&'a str: Sized` の where 境界になります。これを builtin impl より
    // 優先したくありません。
    is_sized(x);
}
}

この優先順位は、builtin impl が非 param の where 節に依存するネストされたゴールを持つ場合には正しくありません。

#![allow(unused)]
fn main() {
struct MyType<'a, T: ?Sized>(&'a (), T);
fn is_sized<T>() {}
fn foo<'a, T: ?Sized>()
where
    (MyType<'a, T>,): Sized,
    MyType<'static, T>: Sized,
{
    // where 境界は自明ですが、タプルに対する builtin の `Sized` impl は
    // `MyType<'a, T>: Sized` の証明を要求し、これは where 節を使用することでしか
    // 証明できず、不要な `'static` 制約を追加します。
    is_sized::<(MyType<'a, T>,)>();
    //~^ ERROR lifetime may not live long enough
}
}

CandidateSource::ParamEnv

少なくとも 1 つの 非グローバル な ParamEnv 候補が存在すると、すべての ParamEnv 候補を他の候補種別より優先します。 where 境界がグローバルであるとは、それが高ランクでなく、かつジェネリックパラメーターを一切含まない場合です。 それには 'static を含めることができます。

where 境界はユーザーが最も制御しやすい傾向があるため、他の候補よりも where 境界を適用しようとします。これにより、候補の優先順位が誤っている場合でも、ユーザーが最も簡単に調整できます。

Impl 候補より優先する理由

これは、次の例でリージョンエラーを回避するために必要です。

#![allow(unused)]
fn main() {
trait Trait<'a> {}
impl<T> Trait<'static> for T {}
fn impls_trait<'a, T: Trait<'a>>() {}
fn foo<'a, T: Trait<'a>>() {
    impls_trait::<'a, T>();
}
}

シャドウされた impl は、現在あいまいなソルバーサイクルを引き起こす可能性があるため、これも必要です: trait-system-refactor-initiative#76。 優先順位がない場合、不完全性を避けるために where 境界がリージョン制約を生じさせるなら、あいまい性エラーで失敗せざるを得ません。

#![allow(unused)]
fn main() {
trait Super {
    type SuperAssoc;
}

trait Trait: Super<SuperAssoc = Self::TraitAssoc> {
    type TraitAssoc;
}

impl<T, U> Trait for T
where
    T: Super<SuperAssoc = U>,
{
    type TraitAssoc = U;
}

fn overflow<T: Trait>() {
    // 展開された `Super<SuperAssoc = Self::TraitAssoc>` の where 境界を使用して、
    // `T: Trait` 実装の where 境界を証明できます。これは現在、
    // オーバーフローを引き起こします。
    let x: <T as Trait>::TraitAssoc;
}
}

この優先順位は多くの問題を引き起こします。 #24066 を参照してください。 問題の大部分は、where 境界が型推論を誘導する場合であっても、impl より where 境界を優先することによって引き起こされます。

#![allow(unused)]
fn main() {
trait Trait<T> {
    fn call_me(&self, x: T) {}
}
impl<T> Trait<u32> for T {}
impl<T> Trait<i32> for T {}
fn bug<T: Trait<U>, U>(x: T) {
    x.call_me(1u32);
    //~^ ERROR mismatched types
}
}

しかし、where 境界が推論を誘導しない場合にのみこの優先順位を適用するとしても、それでも不正なライフタイム制約を引き起こす可能性があります。

#![allow(unused)]
fn main() {
trait Trait<'a> {}
impl<'a> Trait<'a> for &'a str {}
fn impls_trait<'a, T: Trait<'a>>(_: T) {}
fn foo<'a, 'b>(x: &'b str)
where
    &'a str: Trait<'b>
{
    // `'b: 'x` を伴って `&'x str: Trait<'b>` を証明する必要があります。
    impls_trait::<'b, _>(x);
    //~^ ERROR lifetime may not live long enough
}
}

AliasBound 候補より優先する理由

これは、次の例でリージョンエラーを回避するために必要です。

#![allow(unused)]
fn main() {
trait Bound<'a> {}
trait Trait<'a> {
    type Assoc: Bound<'a>;
}

fn impls_bound<'b, T: Bound<'b>>() {}
fn foo<'a, 'b, 'c, T>()
where
    T: Trait<'a>,
    for<'hr> T::Assoc: Bound<'hr>,
{
    impls_bound::<'b, T::Assoc>();
    impls_bound::<'c, T::Assoc>();
}
}

これは不要な制約を引き起こすこともあります。

#![allow(unused)]
fn main() {
trait Bound<'a> {}
trait Trait<'a> {
    type Assoc: Bound<'a>;
}

fn impls_bound<'b, T: Bound<'b>>() {}
fn foo<'a, 'b, T>()
where
    T: for<'hr> Trait<'hr>,
    <T as Trait<'b>>::Assoc: Bound<'a>,
{
    // `<T as Trait<'a>>::Assoc: Bound<'a>` に where 境界を使用すると、
    // `<T as Trait<'a>>::Assoc` が env からの
    // `<T as Trait<'b>>::Assoc` と不要に等価とされます。
    impls_bound::<'a, <T as Trait<'a>>::Assoc>();
    // `<T as Trait<'b>>::Assoc: Bound<'b>` については、where 境界の self 型は
    // 一致しますが、trait 境界の引数は一致しません。
    impls_bound::<'b, <T as Trait<'b>>::Assoc>();
}
}

グローバルな where 境界を優先しない理由

グローバルな where 境界は、impl に完全に含意されるか、満たせないかのどちらかです。 満たせない場合、何が起きるかは実際には気にしません。 where 境界が完全に含意される場合、trait ゴールを証明するために impl を使用しても追加の制約が発生することはありません。 trait ゴールにおいて、これは 'static を使用する where 境界に対してのみ有用です。

#![allow(unused)]
fn main() {
trait A {
    fn test(&self);
}

fn foo(x: &dyn A)
where
    dyn A + 'static: A, // この境界を使用するとライフタイムエラーにつながります。
{
    x.test();
}
}

さらに重要なこととして、ここで impl を使用することで、関連型を正規化するときにグローバルな where 境界が impl をシャドウするのを防ぎます。 グローバルな where 境界より impl を優先することによる既知の問題はありません。

それでもグローバルな where 境界を考慮する理由

グローバルな where 境界が存在していても単に impl を使用するのであれば、なぜこれらのグローバルな where 境界を完全に無視しないのか、と疑問に思うかもしれません。非グローバルな where 境界からの推論の誘導を弱めるために、それらを使用します。

グローバルな where 境界がない場合、適用可能な impl も存在するにもかかわらず、現在は非グローバルな where 境界を優先します。 非グローバルな where 境界を追加することで、この不要な推論の誘導が無効化され、次のコードがコンパイルできるようになります。

#![allow(unused)]
fn main() {
fn check<Color>(color: Color)
where
    Vec: Into<Color> + Into<f32>,
{
    let _: f32 = Vec.into();
    // グローバルな `Vec: Into<f32>` 境界がなければ、
    // ここで非グローバルな `Vec: Into<Color>` 境界を
    // 積極的に使用してしまい、これが失敗します。
}

struct Vec;
impl From<Vec> for f32 {
    fn from(_: Vec) -> Self {
        loop {}
    }
}
}

CandidateSource::AliasBound

alias-bound 候補を impl より優先します。 現在、この優先順位を型推論の誘導に使用しており、その結果、以下がコンパイルされます。 個人的には、この優先順位が望ましいとは思いません 🤷

#![allow(unused)]
fn main() {
pub trait Dyn {
    type Word: Into<u64>;
    fn d_tag(&self) -> Self::Word;
    fn tag32(&self) -> Option<u32> {
        self.d_tag().into().try_into().ok()
        // `Self::Word: Into<?0>` を証明してから、`?0` 上の
        // メソッドを選択する。eager な推論が必要。
    }
}
}

fn impl_trait() -> impl Into<u32> {
    0u16
}

fn main() {
    // `x` には 2 つの可能な型がある:
    // - `impl Into<u32>` の「alias bound」を使うことによる `u32`
    // - `impl<T> From<T> for T` を使うことによる `impl Into<u32>`、すなわち `u16`
    //
    // `x` の型を `u32` と推論する。ただし、これは厳密には
    // 必要ではなく、驚くようなエラーにつながることさえある。
    let x = impl_trait().into();
    println!("{}", std::mem::size_of_val(&x));
}

この優先により、リージョン制約による曖昧さも回避されますが、実際に人々がこれに依存しているかはわかりません。

#![allow(unused)]
fn main() {
trait Bound<'a> {}
impl<T> Bound<'static> for T {}
trait Trait<'a> {
    type Assoc: Bound<'a>;
}

fn impls_bound<'b, T: Bound<'b>>() {}
fn foo<'a, T: Trait<'a>>() {
    // これを `'a` と推論すべきか、それとも `'static` と推論すべきか。
    impls_bound::<'_, T::Assoc>();
}
}

CandidateSource::BuiltinImpl(BuiltinImplSource::Object(_))

組み込みの trait object impl を、ユーザーが書いた impl より優先します。 これは 不健全 であり、将来削除されるべきです。 詳細については #57893 と #141347 を参照してください。

NormalizesTo ゴール

正規化中の候補の優先順位の挙動は fn assemble_and_merge_candidates に実装されています。

AliasBound 候補を常に考慮します

where-bound が関連アイテムを指定していない場合、trait ゴールが ParamEnv 候補によって証明されていたとしても、エイリアスを固定的なものとして扱う代わりに AliasBound 候補を考慮します。

#![allow(unused)]
fn main() {
trait Super {
    type Assoc;
}
trait Bound {
    type Assoc: Super<Assoc = u32>;
}
trait Trait: Super {}

// 環境を展開すると、`T::Assoc: Super` where-bound が得られる。
// この where-bound は、`Super<Assoc = u32>`
// item bound による正規化を妨げてはならない。
fn heck<T: Bound<Assoc: Trait>>(x: <T::Assoc as Super>::Assoc) -> u32 {
    x
}
}

このようなエイリアスを使用すると、追加のリージョン制約が生じる可能性があります。cc #133044。

#![allow(unused)]
fn main() {
trait Bound<'a> {
    type Assoc;
}
trait Trait {
    type Assoc: Bound<'static, Assoc = u32>;
}

fn heck<'a, T: Trait<Assoc: Bound<'a>>>(x: <T::Assoc as Bound<'a>>::Assoc) {
    // 関連型を正規化するには `T::Assoc: Bound<'static>` が必要になる。これは、
    // エイリアスを固定的なままにせず、`Bound<'static>` alias-bound を使うため。
    drop(x);
}
}

ParamEnv 候補を AliasBound より優先します

where-bound が関連型を指定していない場合は AliasBound 候補を使用しますが、指定している場合は where-bound を優先します。 これは以下の例で必要です:

#![allow(unused)]
fn main() {
// `I::IntoIterator: Iterator<Item = ()>`
// where-bound を、`I::Intoiterator: Iterator<Item = I::Item>`
// alias-bound より優先することを確認する。

trait Iterator {
    type Item;
}

trait IntoIterator {
    type Item;
    type IntoIter: Iterator<Item = Self::Item>;
}

fn normalize<I: Iterator<Item = ()>>() {}

fn foo<I>()
where
    I: IntoIterator,
    I::IntoIter: Iterator<Item = ()>,
{
    // `I::IntoIterator: Iterator<Item = ()>`
    // where-bound を、`I::Intoiterator: Iterator<Item = I::Item>`
    // alias-bound より優先する必要がある。
    normalize::<I::IntoIter>();
}
}

where-bound を常に考慮します

trait ゴールが impl によって証明されていたとしても、ParamEnv 候補が存在するなら、依然としてそれらを優先します。

「orphaned」where-bound を優先します

fn check_type_bounds で GAT と RPITIT の item bound を正規化するとき、「orphaned」Projection 句を ParamEnv に追加します。 これらの ParamEnv 候補を、impl や他の where-bound より優先する必要があります。

#![allow(unused)]
#![feature(associated_type_defaults)]
fn main() {
trait Foo {
    // 以下の impl によって `i32: Baz<Self>` を証明できるはずである。
    // その impl は `Self::Bar<()>: Eq<i32>` を必要とするが、
    // `for<T> Self::Bar<T> = i32` と仮定するため、これは真である。
    type Bar<T>: Baz<Self> = i32;
}
trait Baz<T: ?Sized> {}
impl<T: Foo + ?Sized> Baz<T> for i32 where T::Bar<()>: Eq<i32> {}
trait Eq<T> {}
impl<T> Eq<T> for T {}
}

この優先が実際に必要になるケースを完全には理解しておらず、まだ面白い形でこれを悪用できてもいませんが 🤷

グローバルな where-bound を impl より優先します

以下がコンパイルされるためにはこれが必要です。 実際に何かがこれに依存しているかはわかりません 🤷

#![allow(unused)]
fn main() {
trait Id {
    type This;
}
impl<T> Id for T {
    type This = T;
}

fn foo<T>(x: T) -> <u32 as Id>::This
where
    u32: Id<This = T>,
{
    x
}
}

これは、正規化が追加のリージョン制約を生じさせる可能性があることを意味します。cc #133044。

#![allow(unused)]
fn main() {
trait Trait {
    type Assoc;
}

impl Trait for &u32 {
    type Assoc = u32;
}

fn trait_bound<T: Trait>() {}
fn normalize<T: Trait<Assoc = u32>>() {}

fn foo<'a>()
where
    &'static u32: Trait<Assoc = u32>,
{
    trait_bound::<&'a u32>(); // ok、impl によって証明される
    normalize::<&'a u32>(); // エラー、where-bound によって証明される
}
}

Trait の where-bound は impl をシャドウします

対応する trait ゴールが ParamEnv または AliasBound 候補によって証明されている場合、関連アイテムの正規化は impl を考慮しません。 これは、関連型を制約しない where-bound については、関連型が 固定的 なままになることを意味します。

impl を使用すると異なるリージョン制約が生じます

これは、impl を適用することによる不要なリージョン制約を避けるために必要です。

#![allow(unused)]
fn main() {
trait Trait<'a> {
    type Assoc;
}
impl Trait<'static> for u32 {
    type Assoc = u32;
}

fn bar<'b, T: Trait<'b>>() -> T::Assoc { todo!() }
fn foo<'a>()
where
    u32: Trait<'a>,
{
    // 戻り値の型を正規化すると impl が使用され、
    // `T: Trait` where-bound の証明では where-bound が使用されるため、
    // 異なるリージョン制約が生じる。
    bar::<'_, u32>();
}
}

RPITIT type_of サイクル

現在、RPITIT のクエリサイクルを避けるため、where-bound がある場合は impl 候補を避ける必要があります。#139762 を参照してください。 この問題を取り除くために、RPITIT の計算中に auto-trait leakage に依存するのをやめるのが望ましいように感じます。#139788 を参照してください。

#![allow(unused)]
fn main() {
use std::future::Future;
pub trait ReactiveFunction: Send {
    type Output;

    fn invoke(self) -> Self::Output;
}

trait AttributeValue {
    fn resolve(self) -> impl Future<Output = ()> + Send;
}

impl<F, V> AttributeValue for F
where
    F: ReactiveFunction<Output = V>,
    V: AttributeValue,
{
    async fn resolve(self) {
        // ここでは `<V as AttributeValue>::{synthetic#0}` を await している。
        // 現在入っている impl を介してこれを正規化するには
        // `collect_return_position_impl_trait_in_trait_tys` に依存するが、これは
        // 最終的に、この関数の opaque return type がトレイト定義の `Send` item
        // bound を実装していることを確認する際の auto-trait leakage に依存する。
        self.invoke().resolve().await
    }
}
}

トレイト定義では、常に適用可能な impl の associated type を使用できない

トレイト定義内の T: Trait という仮定により、blanket impl を使用して <Self as Trait>::Assoc を T に正規化することはできません。 これは、非常に強いものではないにせよ、ある程度望ましい制約のように感じられます。

#![allow(unused)]
fn main() {
trait Eq<T> {}
impl<T> Eq<T> for T {}
struct IsEqual<T: Eq<U>, U>(T, U);

trait Trait: Sized {
    type Assoc;
    fn foo() -> IsEqual<Self, Self::Assoc> {
        //~^ ERROR トレイト境界 `Self: Eq<<Self as Trait>::Assoc>` が満たされていません
        todo!()
    }
}

impl<T> Trait for T {
    type Assoc = T;
}
}