Transitive traits

I have a trait that defines a partial order between certain types ( SubsetOf<T>). Is there any way to add bounds to this so that the compiler understands A: SubsetOf<B> and B: SubsetOf<C> implies A: SubsetOf<C>?

The implementations already ensure that this is true, but not in a way that the compiler is able to reason about, apparently.

No, and you can't even add a blanket impl because if there are two B1, B2 such that A: SubsetOf<B1>, A: SubsetOf<B2>, B1: SubsetOf<C>, B2: SubsetOf<C>, then such a blanket impl would generate two impls of A: SubsetOf<C>, which is not allowed.

1 Like

Thanks; that's what I suspected the answer would be, but I hoped there was something I was missing.

I like that you point out that this is not about implementations, as blanket impls don’t really work, like @alice explained. But even making the compiler know that all those manual implementations really are transitive won’t work.

The problem is, assume we have found a “trick” (or added a new feature) that would allow the compiler to know that A: SubsetOf<B> and B: SubsetOf<C> implies A: SubsetOf<C>, for all A, B, C.
Then this trick/feature would also make the compiler enforce that A: SubsetOf<B> and B: SubsetOf<C> implies A: SubsetOf<C> (because if it didn’t enforce this, how could it know?)
But trait implementations can come from multiple places and you can’t check transitivity locally: For example, if crate a defines type A and the SubsetOf trait and sets up the trick/feature to only allow transitive implementations. Then crate b depending on crate a, could define type B and implement B: SubsetOf<A>. This way the relation is still transitive. Similarly, crate c, depending on only a, could define type C and implement A: SubsetOf<C>. With in the local view of only considering a and c, the transitivity is not broken either. But if you combine a, b, and c, you now have B: SubsetOf<A> and A: SubsetOf<C> but not B: SubsetOf<C>.

A way thay would work would be a feature that also changes the orphan rules for some traits, so that c couldn’t even implement A: SubsetOf<C>. The rules could be that you can only implement FOO: SubsetOf<BAR> if FOO is (possibly reference type of) a type you defined locally, unlike the current rules where it is sufficient that FOO or BAR are local types (or references to local types, and a few more exceptions). This is basically what object oriented programming languages do, where you can only add subclasses but not superclasses.

5 Likes

Well, I'm sure I'm missing something with this, but here is my shot at it: Rust Playground

I'm taking 'subset of' to mean that A can always be From<B>, and same for B being From<C> (but the reverse is not guaranteed). So I used increasing sizes of ints to contain the subsets of the smaller ints.

At best I can say my attempt at least looks like it works... for primitives... which already follow that behavior...

I suppose the better comparison would be: squares are a subset of rectangles, which are a subset of parallelograms, etc... But I don't suppose my implementation actually transfers any functionality UP the transitive relation, it just knows From<T> conversions exist to make things work.

Oh... I hard-coded in the A is a subset of C case... Maybe not helpful...

Maybe I'm getting a little closer: Rust Playground

Still jumps the A to C shark in one blanket impl, but does so in a semi-cognizant way...

To set my answer into context, I was answering this question

which I interpreted as

is there a way to make this compile (except for the “trivial solution” of a full blanket implementation like impl<S,T> SubsetOf<T> for S {/*...*/} which would defeat the point)

fn assert_subset_of<S,U>()
where S: SubsetOf<U>
{}

fn only_works_if_compiler_understands_the_transitivity<S, T, U>()
where S: SubsetOf<T>, T: SubsetOf<U>
{ assert_subset_of::<S,U>() }

and my answer was “no, not even in a modified Rust language unless you start changing orphan rules”.

1 Like

That is indeed the question I meant to ask, but couldn't come up with a good way to phrase it. In my actual application, A, B, and C are all sets of types, implemented similarly to the typenum type-system numbers. X: SubsetOf<Y> then means that it's possible to convert a Y into an X by dropping the extra inner types.

In the A < B < C case, I was hoping to be able to convert C to A directly. The implementation is there, but I can't work an A: SubsetOf<C> bound into the piece of generic code I'm working with, as A, B, and C are all specified in different places:

  • A is a type parameter on a trait method
  • B is an associated type of Self::Trait
  • C is an associated type of <self.inner as Trait>

You can get the benefit of the benefit of direct conversion without needing A: SubsetOf<C>, with specialization. Like this:

#![feature(specialization)]
#![allow(incomplete_features)]
trait SubsetOf<T>: Sized {
    fn convert(self) -> T;
}
trait SubsetOfChain<X,T>
where Self: SubsetOf<X>, X: SubsetOf<T>
{
    fn convert_chain(self) -> T;
}
impl<S, T, X> SubsetOfChain<X, T> for S
where S: SubsetOf<X>, X: SubsetOf<T> {
    default fn convert_chain(self) -> T {
        self.convert().convert()
    } 
}
impl<S, T, X> SubsetOfChain<X, T> for S
where S: SubsetOf<X>, X: SubsetOf<T>,
      S: SubsetOf<T>
{
    fn convert_chain(self) -> T {
        self.convert()
    }
}


fn assert_subset_chain<S,T,U>()
where S: SubsetOfChain<T,U>, T: SubsetOf<U>
{}

fn works_without_the_compiler_knowing_about_transitivity<S, T, U>()
where S: SubsetOf<T>, T: SubsetOf<U>
{ assert_subset_chain::<S,T,U>() }
1 Like

Oh dang, that's pretty nifty!

But wouldn't the S: SubsetOf<T> included on top of the S: SubsetOf<X> in the second chain impl already imply that the A to C conversion exists and is what is being used? Oh, or is that providing the shorter pathway for when that condition exists?

I'm still tinkering with an A<=B and B<=C method that works without a known direct A<=C: Playground
It's not pretty AND it doesn't work!

Just for fun, I generalized it to an arbitrary amount of steps.

2 Likes

This may just be another way of stating what was said at the beginning about unknown B1/B2 options as the intermediary, but...

If I use an explicitly chosen intermediary, I can get a chained trait to know how to get an i64 from i8 without a direct conversion (as far as I can tell): Playground

Bah. I'm still not convinced that I'm not just secretly accidentally using direct i64 from i8, but here it is again with recast types hoping to avoid that shortcut: Playground

Or if I'm just providing an overly fancy format to say A::from(B::from(c_var: C)) must be possible.

I get the impression that you’re trying to solve a slightly different problem than I was having: the goal is to skip the intermediate step when there’s a direct implementation, but there’s no place to require it. Here’s a reduced version of my code that illustrates the problem:

impl<T:Comparator, U> Comparator for ProxyCmp<T,U>
where T::Stored: MyInto<U> {
    type Stored = U;
    fn into_inner(self)->Self::Stored { self.0.into_inner().my_into() }

    fn is_eq<T2>(&self, rhs:T2)->bool where Self::Stored: MyInto<T2> {
        // What goes here?
        unimplemented!();
    }
}

We know that T::Stored can be converted into U, and that U can be converted into T2, so T::Stored is convertable to T2. Thus, I would like to proxy is_eq through to the underlying implementation— There’s no way to make the compiler do this.

To get around this, I ended up adding an is_eq_unchecked that has no type bound and panics if the conversion isn’t possible. Once I’ve used the type system to guarantee success, I use the unchecked call for proxying. This means I have to manually ensure the type bounds match properly in order to not panic unnecessarily, which isn’t ideal.

I'm using From as a proxy, because 'a from b' is just the reverse way of stating that 'b can be converted into a'.

If you just care that it can be converted directly (and know how that's done):

fn is_eq<T2: From<Self::Stored>>(&self, rhs:T2)->bool {
    T2::from(&self) == rhs
}

Am I still missing something about the direction the conversion-ability requirement must be passed?

Can't you just add the implementation to link in the known conversion?

impl<T: Comparator> From<T::Stored> for T2 {
    fn from(&stored: &T::Stored) -> Self {
        convert_t_to_t2(&stored: &T::Stored)
    }
}

Well, the biggest trick I had to pull was making sure T and U were Copy so that the From implementations could work without consuming self, but here is a working version: Playground

Also: From and Into

This doesn’t work because T2 is a generic type parameter on the method. There already is a direct From / MyInto implementation between the two concrete types, and my question was about whether it was possible for the compiler to let me use it.


NB: The rest of this post is more to help me straighten out my own thoughts than make a point. Feel free to ignore if it doesn’t make sense.

The goal of the proxy object is to transmit operations to its source, and only generate the final result when necessary. Consider something like a list cross-product: it’s going to generate n*m results; if you then filter this, you’ll need to do n*m comparisons to produce the result.

On the other hand, if the filter only operates on information from the first list, you get the same result from filtering it before doing the cross-product, with only n comparisons. Since the proxy object is supposed to be completely interchangable with the calculated result, I can’t have any bounds on the source type unless they can be expressed when creating the proxy.

Due to the specific nature of the domain I’m working in, I know that all possible conversions have implementations, but Rust has no way to express that in terms of traits: I’d need to say something like

trait T: for<T2: T> PartialEq<T2> {}

but the for<...> syntax is only for lifetimes, and not general type parameters.

Did you give this a look? It compiles, but I really had no idea what kind of testing to run on it.

It works, but this is the situation I wanted to avoid:

fn is_eq<T2:Eq + From<Self::Stored>>(&self, rhs:T2)->bool {
        T2::from(self.into_inner()) == rhs
    }

In my actual code, self.into_inner() and T2::from(Self::Stored) are both expensive to calculate, but self.0.is_eq(rhs) is expressly defined and cheap. Since the two calculation paths will produce the same output, I naturally would prefer to use the cheaper one.

The issue is that there’s no way to prove to the compiler that the fast path will always be available, and without specialization there appears to be no way to use the fast path when available but fall back to the slow one otherwise.

In practice, this proxy object represents a virtually-joined database table, and is_eq represents some relational operation, like select. I’d prefer to filter the source tables and then join if possible, instead of calculating the join and then filtering.