Struct chalk_solve::rust_ir::TraitDatum

pub struct TraitDatum<I: Interner> {
    pub id: TraitId<I>,
    pub binders: Binders<TraitDatumBound<I>>,
    pub flags: TraitFlags,
    pub associated_ty_ids: Vec<AssocTypeId<I>>,
    pub well_known: Option<WellKnownTrait>,
}

A rust intermediate representation (rust_ir) of a Trait Definition. For example, given the following rust code:

use std::fmt::Debug;

trait Foo<T>
where
    T: Debug,
{
    type Bar<U>;
}

This would represent the trait Foo declaration. Note that the details of the trait members (e.g., the associated type declaration (type Bar<U>) are not contained in this type, and are represented separately (e.g., in AssociatedTyDatum).

Not to be confused with the rust_ir for a Trait Implementation, which is represented by ImplDatum

Fields

id: TraitId<I>

binders: Binders<TraitDatumBound<I>>

flags: TraitFlags

"Flags" indicate special kinds of traits, like auto traits. In Rust syntax these are represented in different ways, but in chalk we add annotations like #[auto].

associated_ty_ids: Vec<AssocTypeId<I>>

well_known: Option<WellKnownTrait>

If this is a well-known trait, which one? If None, this is a regular, user-defined trait.

Implementations

impl<I: Interner> TraitDatum<I>

pub fn is_auto_trait(&self) -> bool

pub fn is_non_enumerable_trait(&self) -> bool

pub fn is_coinductive_trait(&self) -> bool

pub fn where_clauses(&self) -> Binders<&Vec<QuantifiedWhereClause<I>>>

Gives access to the where clauses of the trait, quantified over the type parameters of the trait:

trait Foo<T> where T: Debug { }
             ^^^^^^^^^^^^^^

Trait Implementations

impl<I: Clone + Interner> Clone for TraitDatum<I>

fn clone(&self) -> TraitDatum<I>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<I: Debug + Interner> Debug for TraitDatum<I>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<I: Eq + Interner> Eq for TraitDatum<I>

impl<I: Hash + Interner> Hash for TraitDatum<I>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl<I: PartialEq + Interner> PartialEq<TraitDatum<I>> for TraitDatum<I>

fn eq(&self, other: &TraitDatum<I>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &TraitDatum<I>) -> bool

This method tests for !=.

impl<I: Interner> StructuralEq for TraitDatum<I>

impl<I: Interner> StructuralPartialEq for TraitDatum<I>

impl<I: Interner> ToProgramClauses<I> for TraitDatum<I>

fn to_program_clauses(
    &self,
    builder: &mut ClauseBuilder<'_, I>,
    environment: &Environment<I>
)

Given the following trait declaration: trait Ord<T> where Self: Eq<T> { ... }, generate:

-- Rule WellFormed-TraitRef
forall<Self, T> {
   WF(Self: Ord<T>) :- Implemented(Self: Ord<T>), WF(Self: Eq<T>).
}

and the reverse rules:

-- Rule Implemented-From-Env
forall<Self, T> {
   (Self: Ord<T>) :- FromEnv(Self: Ord<T>).
}

-- Rule Implied-Bound-From-Trait
forall<Self, T> {
    FromEnv(Self: Eq<T>) :- FromEnv(Self: Ord<T>).
}

As specified in the orphan rules, if a trait is not marked #[upstream], the current crate can implement it for any type. To represent that, we generate:

// `Ord<T>` would not be `#[upstream]` when compiling `std`
forall<Self, T> { LocalImplAllowed(Self: Ord<T>). }

For traits that are #[upstream] (i.e. not in the current crate), the orphan rules dictate that impls are allowed as long as at least one type parameter is local and each type prior to that is fully visible. That means that each type prior to the first local type cannot contain any of the type parameters of the impl.

This rule is fairly complex, so we expand it and generate a program clause for each possible case. This is represented as follows:

// for `#[upstream] trait Foo<T, U, V> where Self: Eq<T> { ... }`
forall<Self, T, U, V> {
    LocalImplAllowed(Self: Foo<T, U, V>) :- IsLocal(Self).
}

forall<Self, T, U, V> {
    LocalImplAllowed(Self: Foo<T, U, V>) :-
        IsFullyVisible(Self),
        IsLocal(T).
}

forall<Self, T, U, V> {
    LocalImplAllowed(Self: Foo<T, U, V>) :-
        IsFullyVisible(Self),
        IsFullyVisible(T),
        IsLocal(U).
}

forall<Self, T, U, V> {
    LocalImplAllowed(Self: Foo<T, U, V>) :-
        IsFullyVisible(Self),
        IsFullyVisible(T),
        IsFullyVisible(U),
        IsLocal(V).
}

The overlap check uses compatible { ... } mode to ensure that it accounts for impls that may exist in some other compatible world. For every upstream trait, we add a rule to account for the fact that upstream crates are able to compatibly add impls of upstream traits for upstream types.

// For `#[upstream] trait Foo<T, U, V> where Self: Eq<T> { ... }`
forall<Self, T, U, V> {
    Implemented(Self: Foo<T, U, V>) :-
        Implemented(Self: Eq<T>), // where clauses
        Compatible,               // compatible modality
        IsUpstream(Self),
        IsUpstream(T),
        IsUpstream(U),
        IsUpstream(V),
        CannotProve.              // returns ambiguous
}

In certain situations, this is too restrictive. Consider the following code:

/* In crate std */
trait Sized { }
struct str { }

/* In crate bar (depends on std) */
trait Bar { }
impl Bar for str { }
impl<T> Bar for T where T: Sized { }

Here, because of the rules we've defined, these two impls overlap. The std crate is upstream to bar, and thus it is allowed to compatibly implement Sized for str. If str can implement Sized in a compatible future, these two impls definitely overlap since the second impl covers all types that implement Sized.

The solution we've got right now is to mark Sized as "fundamental" when it is defined. This signals to the Rust compiler that it can rely on the fact that str does not implement Sized in all contexts. A consequence of this is that we can no longer add an implementation of Sized compatibly for str. This is the trade off you make when defining a fundamental trait.

To implement fundamental traits, we simply just do not add the rule above that allows upstream types to implement upstream traits. Fundamental traits are not allowed to compatibly do that.

impl<I: Interner> Visit<I> for TraitDatum<I>

fn visit_with<'i, R: VisitResult>(
    &self,
    visitor: &mut dyn Visitor<'i, I, Result = R>,
    outer_binder: DebruijnIndex
) -> R where
    I: 'i, 

Apply the given visitor visitor to self; binders is the number of binders that are in scope when beginning the visitor. Typically binders starts as 0, but is adjusted when we encounter Binders<T> in the IR or other similar constructs.