Help with min_specialization

I have been learning about specialization and const generics by implementing a classic matrix data structure. Here is what my struct declaration looks like :

pub struct Matrix<K: Scalar, const N: usize, const P: usize> {
    coeffs: [[K; P]; N],
}

I've hit a wall trying to convert for example from a Matrix<u32,3,3> into a Matrix<f32,3,3> with the following From implementation :

impl<K1: Scalar, K2: Scalar, const N: usize, const P: usize> From<Matrix<K2, N, P>> for Matrix<K1, N, P>
where
    K1: From<K2>,
{
    fn from(m2: Matrix<K2, N, P>) -> Matrix<K1, N, P> {
       /* code ommited */
    }
}

With the #![feature(min_specialization)] at the top of my lib.rs, in the latest nightly the compiler tells me the following

error[E0119]: conflicting implementations of trait `std::convert::From<matrix::Matrix<_, {_: usize}, {_: usize}>>` for type `matrix::Matrix<_, {_: usize}, {_: usize}>`:
   --> data_structures/src/matrix.rs:95:1
    |
95  | / impl<K1: Scalar, K2: Scalar, const N: usize, const P: usize> From<Matrix<K2, N, P>>
96  | |     for Matrix<K1, N, P>
97  | | where
98  | |     K1: From<K2>,
...   |
108 | |     }
109 | | }
    | |_^
    |
    = note: conflicting implementation in crate `core`:
            - impl<T> From<T> for T;

Maybe I am misunderstanding min_specialization ?

Specialization is about writing impl blocks that overlap but where one is more specialized than the other. Neither your impl nor impl<T> From<T> for T is more specialized than the other so you can't use specialization rules here.

Maybe the following playground helps illustrate the nuance here:

#![feature(specialization)]

struct Wrapper<T>(T);

trait MyFrom<Src> {
    fn from (src: Src) -> Self;
}

// 𝓒: (Wrapper<T>, Wrapper<T>)
impl<T> MyFrom<Wrapper<T>> for Wrapper<T> {
    fn from (
        it: Wrapper<T>
    ) -> Wrapper<T>
    {
        it
    }
}

    // 𝓑: (Wrapper<T>, Wrapper<U>)
    impl<T, U : MyFrom<T>> MyFrom<Wrapper<T>> for Wrapper<U> {
        default
        fn from (
            Wrapper(t): Wrapper<T>
        ) -> Wrapper<U>
        {
            Wrapper(MyFrom::from(t))
        }
    }
    
    // 𝓐: (X, X)
    impl<X> MyFrom<X> for X {
        default
        fn from (src: X) -> X { src }
    }

We have three "sets of types":

  • The (X, X) family on the one hand. Let's call it 𝓐

  • The (Wrapper<T>, Wrapper<U>) family on the other hand. Let's call it 𝓑

  • And their intersection, the (Wrapper<T>, Wrapper<T>) family. Let's call it 𝓒.

Without specialization, impls must range over disjoint "families of types". The standard library, on the case of the From trait, provides an impl that ranges over 𝓐.

You tried to implement it over 𝓑, and since they have a non-empty intersection (𝓒) ⇔ they are not disjoint, the coherence rules of Rust traits kick in and trigger an error.

With specialization, there may be a non-empty intersection, but only for the very specific case of one family being contained within the other. Since neither 𝓐 is contained within 𝓑, nor the inverse, you get an error. That's what @SkiFire13 meant.


That being said, once we consider 𝓒, we realize there could be a solution here (but one that Rust does not yet support, as you can verify by running the above code in the Playground).

Since 𝓒 is the intersection of 𝓐 and 𝓑, it is a subset of both, so it would be allowed to specialize each, individually (which you can check on the Playground by commenting either the 𝓐 impl or the 𝓑 one). And once that's done, the other one could be added, and it shouldn't conflict.

Some remarks:

  • For that to be applicable for the From trait, it's impl (𝓐) would have to be rewritten to be specializable (default fn from). Otherwise you'd need to use your own helper trait, such as MyFrom in the example.

  • The specialization from 𝓑 to 𝓒 (Wrapper<T>, Wrapper<U> to Wrapper<T>, Wrapper<U>) is based on type equality / inequality. This, in turn, unless we are dealing with : 'static types, involves the question of lifetime equality within the trait solver, which currently cannot be implemented and is the main blocker behind the full specialization feature. You will notice that if you try to write that specialization using min_specialization, it won't work (curiously, that seems to be the case even if we add : 'static everywhere, sadly).

    • Playground (where we can see it currently doesn't work either even with specialization)

    Whereas the specialization from 𝓐 to 𝓒 (X, X to Wrapper<T>, Wrapper<T>) is a trivial one, one that is covered by min_specialization (provided 𝓐 is written with default fn, as I said).

    So if you intend to keep poking at specialization, you maximize your chances of success if you manage to write stuff like that specialzation of 𝓐 to 𝓒.

3 Likes

Are you saying that because C is within A, and C is within B, that a valid B specialization is somehow resolved by the compiler?... I don’t see how to infer anything about a B and C subset relation (intersection exists where they both share C, but not more). Right? Or completely missing it :))

Thanks you so much for that detailed answer ! This really cleared things up, as I have never seen specialization seen from that point of view. @SkiFire13's answer makes sense to me now.

Note that I am talking about a possible extension of specialization that doesn't exist yet, and which may never exist, so this is more of a personal theoretical consideration more than anything else: the main question being,

  • why does specialization has that "subset" requirement?

    We could imagine assigning "priorities" to impl Trait … blocks, and then the impl with higher priority is the one specializing the intersection.

    I initially thought that's how default fn worked, by the way, but that doesn't work.

    I thought that by making something default fn, we were making it have "lower priority" / "lower precendence" than a non-default fn, and that that would suffice to solve the problem with overlapping impls.

    But even if that were to work, we'd have the problem of nested specializations: an first impl specializes a second one which, in turn, specializes a third one: then since the second one is specialized, it would need default fn, but in that case it would have the same priority as the third one. So indeed, without, at least, a numerical-based priority system (where default fn would be a "boolean" based one), nested specializations are not possible.


    Moreover, it wouldn't make sense to call such "overriding logic" specialization, if it weren't for that subset property.

  • But now that we observe why specialization seems to require that subset relation between the impls, if we define 𝓒 = 𝓐 ∩ 𝓑, then 𝓒 βŠ† 𝓐 and 𝓒 βŠ† 𝓑, so we can,

    • on the one hand, have an impl over 𝓒 specialize an impl over 𝓐;

    • on the other hand, have an impl over 𝓒 specialize an impl over 𝓑.

    The problem being that "both hands" can't co-exist a priori. And my theoretical consideration is that by having 𝓒 specialize over 𝓐 and 𝓑, the effective impls over 𝓐 and 𝓑 become, in practice, impls over 𝓐 \ 𝓒 and 𝓑 \ 𝓒. And these two last sets are disjoint! Hence why it wouldn't be problematic. :slight_smile:

But we are getting into a very hypothetical world, so let's not dwell on this too much :upside_down_face:

Agree with the emphasis and relevance. This said, a good conversation and useful for understanding how the types interact.

B and A only relate (overlap) where B and C overlap. But is that enough given β€œthere is more to B”? What you are conveying here is, yes that is enough for specialization to work. Exactly where β€œthere is more to B” is the specialization.

All in all, this seems to capture that while A is a specialization of T U (not described, call it D), we can create a specialization, Wrapped T U, that is more general type parameter T -> U vs T -> T, yet more specialized concrete type, Wrapper vs T.

PS: how are you including the math symbols?

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.