후보 선호

Trait 목표와 NormalizesTo 목표를 증명하는 방법은 여러 가지가 있습니다. 이러한 각각의 선택지를 Candidate라고 부릅니다. 적용 가능한 후보가 여러 개인 경우, 일부 후보를 다른 후보보다 선호합니다. 관련 정보는 각 후보의 CandidateSource에 저장합니다.

이러한 선호는 잘못된 추론이나 영역 제약을 초래할 수 있으므로, 일관성(coherence) 검사 중에는 건전하지 않습니다. 이 때문에 일관성 검사에서는 단순히 모든 후보를 병합하려고 시도합니다.

Trait 목표

트레이트 목표는 적용 가능한 후보들을 fn merge_trait_candidates에서 병합합니다. 이 문서는 현재의 선호 규칙이 왜 이렇게 정해졌는지 설명하기 위한 추가 세부 사항과 참고 자료를 제공합니다.

CandidateSource::BuiltinImpl(BuiltinImplSource::Trivial))

자명한 내장 impl은 적격 타입에 대해 항상 적용 가능하다고 알려진 내장 impl입니다. 즉, 이러한 impl이 존재한다면 다른 후보를 사용해도 제약이 더 적어지는 일은 결코 없어야 합니다. 현재는 Sized impl과 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>,
{
    // Elaborating the `&'a str: Trait<T>` where-bound results in a
    // `&'a str: Sized` where-bound. We do not want to prefer this
    // over the builtin impl.
    is_sized(x);
}
}

내장 impl에 매개변수가 아닌 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,
{
    // The where-bound is trivial while the builtin `Sized` impl for tuples
    // requires proving `MyType<'a, T>: Sized` which can only be proven by
    // using the where-clause, adding an unnecessary `'static` constraint.
    is_sized::<(MyType<'a, T>,)>();
    //~^ ERROR lifetime may not live long enough
}
}

CandidateSource::ParamEnv

전역이 아닌 ParamEnv 후보가 하나라도 있으면, 다른 종류의 후보보다 모든 ParamEnv 후보를 선호합니다. where 바운드가 고차(higher-ranked)가 아니고 제네릭 매개변수를 전혀 포함하지 않으면 전역 where 바운드입니다. 전역 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>();
}
}

가려진(shadowed) 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>() {
    // We can use the elaborated `Super<SuperAssoc = Self::TraitAssoc>` where-bound
    // to prove the where-bound of the `T: Trait` implementation. This currently results in
    // overflow.
    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>
{
    // Need to prove `&'x str: Trait<'b>` with `'b: 'x`.
    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>,
{
    // Using the where-bound for `<T as Trait<'a>>::Assoc: Bound<'a>`
    // unnecessarily equates `<T as Trait<'a>>::Assoc` with the
    // `<T as Trait<'b>>::Assoc` from the env.
    impls_bound::<'a, <T as Trait<'a>>::Assoc>();
    // For a `<T as Trait<'b>>::Assoc: Bound<'b>` the self type of the
    // where-bound matches, but the arguments of the trait bound don't.
    impls_bound::<'b, <T as Trait<'b>>::Assoc>();
}
}

전역 where 바운드를 우선하지 않는 이유

전역 where 바운드는 impl에 의해 완전히 함의되거나, 충족될 수 없습니다. 충족될 수 없는 경우에는 어떤 일이 일어나든 크게 신경 쓰지 않습니다. where 바운드가 완전히 함의된다면, impl을 사용해 트레이트 목표를 증명하더라도 추가 제약이 생길 수 없습니다. 트레이트 목표의 경우, 이는 'static을 사용하는 where 바운드에서만 유용합니다:

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

fn foo(x: &dyn A)
where
    dyn A + 'static: A, // Using this bound would lead to a lifetime error.
{
    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();
    // Without the global `Vec: Into<f32>`  bound we'd
    // eagerly use the non-global `Vec: Into<Color>` bound
    // here, causing this to fail.
}

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

CandidateSource::AliasBound

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()
        // prove `Self::Word: Into<?0>` and then select a method
        // on `?0`, needs eager inference.
    }
}
}

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

fn main() {
    // There are two possible types for `x`:
    // - `u32` by using the "alias bound" of `impl Into<u32>`
    // - `impl Into<u32>`, i.e. `u16`, by using `impl<T> From<T> for T`
    //
    // We infer the type of `x` to be `u32` even though this is not
    // strictly necessary and can even lead to surprising errors.
    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>>() {
    // Should we infer this to `'a` or `'static`.
    impls_bound::<'_, T::Assoc>();
}
}

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

사용자가 작성한 impl보다 내장 트레이트 객체 impl을 우선합니다. 이는 건전하지 않으며 향후 제거되어야 합니다. 자세한 내용은 #57893과 #141347을 참조하십시오.

NormalizesTo 목표

정규화 중의 후보 우선순위 동작은 fn assemble_and_merge_candidates에 구현되어 있습니다.

항상 AliasBound 후보를 고려합니다

where 바운드가 연관 항목을 지정하지 않는 경우, 트레이트 목표가 ParamEnv 후보를 통해 증명되었더라도 별칭을 고정된(rigid) 것으로 취급하는 대신 AliasBound 후보를 고려합니다.

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

// Elaborating the environment results in a `T::Assoc: Super` where-bound.
// This where-bound must not prevent normalization via the `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) {
    // Normalizing the associated type requires `T::Assoc: Bound<'static>` as it
    // uses the `Bound<'static>` alias-bound instead of keeping the alias rigid.
    drop(x);
}
}

AliasBound보다 ParamEnv 후보를 우선합니다

where 바운드가 연관 타입을 지정하지 않으면 AliasBound 후보를 사용하지만, 지정하는 경우에는 where 바운드를 우선합니다. 이는 다음 예제를 위해 필요합니다:

#![allow(unused)]
fn main() {
// Make sure we prefer the `I::IntoIterator: Iterator<Item = ()>`
// where-bound over the `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 = ()>,
{
    // We need to prefer the `I::IntoIterator: Iterator<Item = ()>`
    // where-bound over the `I::Intoiterator: Iterator<Item = I::Item>`
    // alias-bound.
    normalize::<I::IntoIter>();
}
}

항상 where 바운드를 고려합니다

트레이트 목표가 impl을 통해 증명되었더라도, ParamEnv 후보가 존재한다면 여전히 이를 우선합니다.

“고아(orphaned)” where 바운드를 우선합니다

fn check_type_bounds에서 GAT와 RPITIT의 항목 바운드를 정규화할 때 “고아(orphaned)” Projection 절을 ParamEnv에 추가합니다. 이러한 ParamEnv 후보를 impl 및 다른 where 바운드보다 우선해야 합니다.

#![allow(unused)]
#![feature(associated_type_defaults)]
fn main() {
trait Foo {
    // We should be able to prove that `i32: Baz<Self>` because of
    // the impl below, which requires that `Self::Bar<()>: Eq<i32>`
    // which is true, because we assume `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 바운드를 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, proven via impl
    normalize::<&'a u32>(); // error, proven via where-bound
}
}

트레이트 where 바운드가 impl을 가립니다

연관 항목의 정규화는 해당 트레이트 목표가 ParamEnv 또는 AliasBound 후보를 통해 증명된 경우 impl을 고려하지 않습니다. 즉, 연관 타입을 제약하지 않는 where 바운드의 경우 연관 타입은 경직된(rigid) 상태로 남습니다.

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>,
{
    // Normalizing the return type would use the impl, proving
    // the `T: Trait` where-bound would use the where-bound, resulting
    // in different region constraints.
    bar::<'_, u32>();
}
}

RPITIT type_of 순환

현재는 RPITIT의 쿼리 순환을 피하기 위해 where 바운드가 있으면 impl 후보를 피해야 합니다. #139762를 참고하십시오. 이 문제를 없애기 위해 RPITIT 계산 중 자동 트레이트 누출에 의존하지 않도록 하는 것이 바람직하다고 생각합니다. #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) {
        // We're awaiting `<V as AttributeValue>::{synthetic#0}` here.
        // Normalizing that one via the the impl we're currently in
        // relies on `collect_return_position_impl_trait_in_trait_tys` which
        // ends up relying on auto-trait leakage when checking that the
        // opaque return type of this function implements the `Send` item
        // bound of the trait definition.
        self.invoke().resolve().await
    }
}
}

트레이트 정의에서는 항상 적용 가능한 impl의 연관 타입을 사용할 수 없습니다

트레이트 정의에 있는 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 the trait bound `Self: Eq<<Self as Trait>::Assoc>` is not satisfied
        todo!()
    }
}

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