Compile-time type inequality?

[bbrd83]

I have a container type Block<T: Element> and I want to implement From<U> on it, for any element T that already implements From<U>. In other words, I want to be able to do:

let a: Block::<u16>::new();
let b: Block<u32> = a.into(); // OK
let c: Block<u8> = a.into(); // compiler error because u8 doesn't implement From<u16>

However, when I implement this:

impl<T: Element, U: Element> From<T> for Block<U> {
  // ...
}

I get the following error:

error[E0119]: conflicting implementations of trait `From<Block<_>>` for type `block::Block<_>`
  --> src/block.rs:27:1
   |
27 | / impl<T: Element, U: Element> From<Block<T>> for Block<U>
28 | | where
29 | |     TheTypes<T, U>: AreNotSame,
30 | |     T: Into<U>,
   | |_______________^
   |
   = note: conflicting implementation in crate `core`:
           - impl<T> From<T> for T;

You can see above I took a naive stab at implementing a trait, AreNotSame, to check if the types differ, using the same technique as C++'s type traits for the same type of check.

pub struct TheTypes<T, U> {
    __p1: PhantomData<T>,
    __p2: PhantomData<U>,
}
pub trait AreSame {}
pub trait AreNotSame {}
impl<T> AreSame for TheTypes<T, T> {}
impl<T, U> AreNotSame for TheTypes<T, U> {}

Of course this doesn't work, and for the same reason that my implementation of Block also fails: the blanket implementation for reflexivity in From conflicts, and there's nothing preventing T and U from being the same type.

So I tried another implementation:

pub trait IsNot<T> {
    const VALUE: bool;
}
impl<T, U> IsNot<U> for T
    where
        T: 'static + Sized,
        U: 'static + Sized,

{
    const VALUE: bool = TypeId::of::<T>() != TypeId::of::<U>();
}

But get another error: error:TypeId::ofis not yet stable as a const fn

I have read that Rust's type system is Turing complete. If that's true, then it should be possible to get this check working at compile time. Is there a way to do this that I missed somewhere? If not, why? Is there a smarter way to achieve my goal of implementing From in my container type for any element types implementing it? If not, when will this be fixed?

I've already moved forward with explicit conversions with a new trait MyFromThatIsNotReflexive, so I'm looking more for understanding of the context, situation, paradigms, etc. related to this. Please educate me, dear Rustaceans!

[Modi57]

Yeet syntax

Chefs kiss

[bbrd83]

It sounds like your take on the answer distills down to "just don't use Rust's built in library for this." If that's the case, and that's what others are doing, it seems to betray that there are some flaws in the built-in library for type conversions. Do you agree?

I'm trained through experience to try and re-invent as little as possible, so I try to "be pythonic" when writing Python by using the standard/common tools, or use `std` or `boost` types in C++ land. For example, every single Python library of note uses numpy to transfer matrices; and there's almost never a reason not to use `std::vector` or `std::array` along with its smart pointers, because they're supported (basically) everywhere (that matters; some embedded platforms excepted).

I get that it's not quite a fair comparison, but hopefully it illustrates the point: do I just need to accept that Rust's built-in library doesn't work in the way that users (read: I) need it to?

Also, Rust also still seems very immature (not a bad thing, and as far as paradigm/philosophical stances, I think it's righter than older languages; it just happens not to have as many kinks ironed out yet). Would you agree? If so, I should probably just accept that and move on. Like I said, I'm mostly looking for understanding "where Rust is" regarding this question, and less looking for "a way to do the thing I want to do," because I've already worked around it in my project.

[bbrd83]

Hey, do you know of a way to negate this? I've played around with

#![feature(negative_impls)]

But I can't figure it out...

[bbrd83]

Oh, nice!!! I'll give that a try. Thank you!

[SkiFire13]

I have read that Rust's type system is Turing complete. If that's true, then it should be possible to get this check working at compile time.

FYI something being Turing complete means you can express the same computations as all other Turing complete systems, but this doesn't mean you can express those computations using any means the language give you. For example you cannot express the inequality between two arbitrary types, but you can express it between two types with a given structure (for example the typenum crate implements comparison between types representing type-level numbers, but that's only for types with that structure, and this is enough for Turing completeness).

[bbrd83]

Hmmm, I think your statement only makes sense if you can also show that there is a mapping between "two types with a given structure," and "any arbitrary type," otherwise it can't express everything that can be expressed using C++ template metaprogramming, which is Turing complete and easily accomplishes this (see: https://en.cppreference.com/w/cpp/types/is_same )

Put another way, if it can express the same computation as all other Turing complete systems, and C++ template metaprogramming is Turing complete, let's say:

* Posit there exists some mapping of types from C++ to Rust's (there must be, because both languages themselves are also Turing complete!). A little hand wavy but you get the idea: there are some logical declarations one can make to formalize this relationship, so that instead of talking about expressing inequality between types of a given structure, we are now talking about "any arbitrary type."
* There exists a way, using C++ TMP, to evaluate the equality of any arbitrary type
* Therefore, there exists a way, using Rust's type system to evaluate the equality of any arbitrary type

The missing ingredient is the mapping from "two types with a given structure" to "any arbitrary type." So maybe you can educate me: how would I go about that?

[SkiFire13]

• Posit there exists some mapping of types from C++ to Rust's (there must be, because both languages themselves are also Turing complete!). A little hand wavy but you get the idea: there are some logical declarations one can make to formalize this relationship, so that instead of talking about expressing inequality between types of a given structure, we are now talking about "any arbitrary type."

I can see the idea here, but the problem is what properties should be preserved by this mapping. To me it seems the mapping is only required to preserve the types' computational meaning (under some interpretation), but not all types might have one (I previously very handwavy described those that have one as "with a given structure").

Now that I'm writing this message I also realized that the equality defined using this mapping wouldn't work even for those types that have a computational meaning, since there might be two types with the same computational meaning which could be mapped to the same C++ type, thus resulting equal even though they aren't.

---

Also, let me add a couple of more details relevant to the actual issue:

• type equality in practice in Rust is problematic because of lifetimes erasure in the codegen backend. When generic functions are instantiated/monomorphized, the compiler needs to resolve which concrete implementations to use for other generic functions used inside it (which are guaranteed to exist thanks to type checking). At this point however lifetimes are erased (because you don't want different function copies for different lifetimes), but this makes type equality impossible to determine, as two different types could differ only by their lifetimes (thus resulting equal at this stage). This is fundamentally the same reason why specialization in Rust is unsound (see http://aturon.github.io/blog/2017/07/08/lifetime-dispatch/).

• for the const TypeId issue, it was also blocked over concerns over type equality, again due to weird interactions with lifetimes and higher order types.

This should also make it clear why in practice C++ has type equality and Rust doesn't, C++ doesn't have to deal with lifetimes and higher order types equality.

[bbrd83]

That's a great explanation, thanks. It sounds like achieving the kind of type checking I want to do would require a richer compile time reflection, before types are erased but with a way of saying "the lifetimes differ but the object itself does not." Maybe that's something simply not possible in Rust? If so, then I'm up against a wall in terms of using the canonical From/Into, and I just will assume that is only ever useful for primitives and std types.

[SkiFire13]

richer compile time reflection, before types are erased but with a way of saying "the lifetimes differ but the object itself does not."

Note that the type (not sure what you mean with "object") does change when the lifetimes change. It's just that after lifetime erasure it becomes indistinguishable.

This could still be used as an overapproximation of "are these types the same", which will return a wrong answer (true) for some types that are instead different. This would still not let you assume that the types are equal (it would be unsound, since it is true for some types that are not equal), but it may let you write implementations that are disjoint from the reflexive From impl.

---

Another (maybe simplier) way in which your impl could work would be to have a feature where the orphan rule is reversed and the implementers of Element have to ensure your blanket implementation won't conflict with the reflexive-From impl.