This is intended to be a possible way of addressing one of the limitations of Maximally minimal specialization: always applicable impls.
I also want to simply mention Sound and ergonomic specialization for Rust as another proposal for solving a different problem with maximally minimal specialization, but my proposal is not related, and should be compatible therewith. I think it is still worth a read.
Please also note that I spent a long time researching and trying to learn as much as I can about the current state of specialization in rust, but there are many years of discussion regarding it, and I probably missed a lot. The above links point to articles that are already almost 4 years old, but they appear to be the most relevant discussions on getting specialization stabilized from what I found. If anyone knows more more recent information then I'd be grateful to hear about it.
One of the rules set by maximally minimal specialization is that "each type parameter can only be used once". This is an unfortunate limitation because it prevents using specialization to implement something like the following.
trait Is<T> {
fn is(&self);
}
impl<A, B> Is<A> for B {
default fn is(&self) {
println!("no");
}
}
// As per original RFC 1210, this is more specific since both input types are identical
// However, maximally minimal specialization prevents this since T is used twice.
// Lets assume this works here though
impl<T> Is<T> for T {
fn is(&self) {
println!("yes");
}
}
fn is_u32<N: Is<u32>>(t: N) {
t.is();
}
fn main() {
is_u32(0u32); // prints "yes"
is_u32(0i8); // prints "no"
}The above kind of trait implementation would be useful for something I had in mind here. I have also seen people ask if it is it possible to statically check generic type is a specific type, which could be solved with specialization if something like the above was possible. However, the above cannot be done if we cannot allow type parameters to be used more than once.
The rule, "each type parameter can only be used once", is for avoiding sneaky lifetime based dispatch such as below.
fn is_static_str<S: Is<&'static str>>(t: S) {
t.is()
}
fn main() {
let static_str: &'static str = "hey";
let deallocated_at_end_of_main: String = "hello".to_string();
// we cannot name the lifetime, but it clearly isn't static
let not_static_str: &'_ str = deallocated_at_end_of_main.as_str();
is_static_str(static_str); // expect to print "yes"
is_static_str(not_static_str); // expect to print "no"
}We know what we might expect each call to is_static_str to print, but the code generation stage does not know about lifetimes, so it does not know if static_str: 'static or if not_static_str: 'static, and cannot pick between the default and specialized implementations.
It is important to take my following understanding into consideration in order to understand my proposal. However, I am not 100% confident that my understanding is correct. Thus, if anyone can point out a problem with the below, then there may be an issue with my proposal
In a nutshell, I understand the compiler comprises the following stages (among others).
- Type checking
- Code generation
I further understand the following:
- Type checking happens before Code generation
- Type checking is supposed to ensure that all lifetime bounds are met
- Code generation does not need to care about lifetimes since the type checker already ensures everything is fine by the time the code generation stage is running
I understand that above works very nicely in stable rust today since there can be no overlap with trait implementations, and thus, the code generator just needs to generate code for the only possible implementation of a type, and the code generator is allowed to assume that lifetimes already checkout.
Specialization introduces overlapping trait implementations. Thus, the code generator needs to make a decision about what possible implementation of a type to use (specialization is about choosing the more specific applicable implementation). But the code generator has no lifetime information (due to lifetime erasure), and thus, cannot pick between two implementations if the only difference is lifetimes (and we don't ever want to pick based on lifetimes anyway).
I argue that the rule, "each type parameter can only be used once", is not necessary for soundness.
The goal is to ensure that the type checker and code generator can agree on what is the most specific trait implementation without needing to care about lifetime. The main point of my proposal is to make the type checker first consider the most specific implementation without considering lifetimes, check necessary lifetimes afterward, and generate errors as appropriate before code generation needs to care. In this way, the type checker and coder generator are able to choose the same trait implementation naturally.
I try to formalize and clarify what I mean with the below steps.
- The type checker chooses the most specific implementation based on the type without considering lifetimes.
- The type checker subsequently considers lifetime requirements on the already chosen implementation, and ensures the lifetime requirements are satisfied. A compiler error should be generated if the lifetime requirements are not satisfied on the already chosen implementation.
- If there is no type checking error, the code generator can safely choose the most specific implementation based on the type without considering lifetimes in the same way as in step 1.
If we apply the above rules when trying to call is_static_str, it should look like the following:
// recall fn is_static_str<S: Is<&'static str>>(t: S) ...
is_static_str(static_str); // compiles and prints "yes"
// 1. Type Checker: check without lifetimes
// S = &str
// &str: Is<&str> ?
// given impl<A, B> Is<A> for B, Yes
// given impl<T> Is<T> for T, Yes
// choose the more specific impl<T> Is<T> for T
// 2. Add the lifetimes
// &'static str: Is<&'static str> ?
// given the chosen impl<T> Is<T> for T, Yes
// OK!
// 3. Code Generator: choose implementation in the same way as in step 1.
is_static_str(not_static_str); // fails to compile, 'static bound not met
// 1. Type Checker: check without lifetimes
// S = &str
// &str: Is<&str> ?
// given impl<A, B> Is<A> for B, Yes
// given impl<T> Is<T> for T, Yes
// choose the more specific impl<T> Is<T> for T
// 2. Add the lifetimes
// &'_ str: Is<&'static str> ?
// given the chosen impl<T> Is<T> for T, No
// generate compile error
// 3. Code Generator: never runs.
is_static_str(0u32); // compiles and prints "no"
// 1. Type Checker: check without lifetimes
// S = u32
// u32: Is<&str> ?
// given impl<A, B> Is<A> for B, Yes
// given impl<T> Is<T> for T, No
// choose the default impl<A, B> Is<A> for B
// 2. Add the lifetimes
// u32: Is<&'static str> ?
// given the chosen impl<A, B> Is<A> for B, Yes
// OK!
// 3. Code Generator: choose implementation in the same way as in step 1.
is_static_str(&0u32); // compiles and prints "no"
// 1. Type Checker: check without lifetimes
// S = &u32
// &u32: Is<&str> ?
// given impl<A, B> Is<A> for B, Yes
// given impl<T> Is<T> for T, No
// choose the default impl<A, B> Is<A> for B
// 2. Add the lifetimes
// &'_ u32: Is<&'static str> ?
// given the chosen impl<A, B> Is<A> for B, Yes
// OK!
// 3. Code Generator: choose implementation in the same way as in step 1.As we can see from the above, we maintain the nice property that the code generator does not need to care about lifetimes, since it can assume that it is safe to choose an implementation when there is a difference other than lifetimes. The code generator still cannot pick between two implementations if the only difference is lifetimes, but it never needs to worry about this since the type checker handles it first. Thus, this should be sound.
With all the above said, it might surprise some people that the nightly compiler (as of 2/3/2022) already appears to behave in the manner described above. See the Playground.
However, since I have not seen any discussion about it, I consider the current behavior is likely not intentional, or even if it is intentional, I see no intention to stabilize it in this way.
I argue that the current behavior, or at least what I described above, is actually sound behavior and should be stabilized in that way (assuming specialization gets stabilized without to many substantial changes), since the code generator never deals with lifetimes similarly as in the stable compiler. Thus, I consider the rule proposed by maximally minimal specialization that "each type parameter can only be used once", is not necessary for soundness.
Given the above impl<A, B> Is<A> for B and the specialized impl<T> Is<T> for T, it is expected that any type will always be able to implement the Is trait. But as we saw above, when a specific lifetime bound is required, it will look like some types do not implement the Is trait.
Specifically, in the above, it looks like &'_ str does not implement Is<'static str>, even though impl<A, B> Is<A> for B is applicable.
Maybe to mitigate possible confusion from the above, there could be a warning when it looks like specific lifetime bounds will cause some types to have issues.
Another thing that might help is an improved error message when step 2 above fails. For Example, in the above Playground link, if you try to run is_static_str(not_static_str); you will see rust error E0597, "borrowed value does not live long enough". An improved error message could additionally indicate that impl<A, B> Is<A> for B is applicable, but cannot be selected since that would cause dispatch based on lifetimes.
I'd also like to point out that even though it might look strange when it looks like &'_ str does not implement Is<'static str>, it is still consistent with the idea that we do not specialize on lifetimes, which should be a concept that is taught to users very clearly if specialization is stabilized.
Some people might consider that it is strange enough to still insist that "each type parameter can only be used once" in order to avoid the above issue. However, I consider such a restriction is overboard when considering the possible gains (one idea I had here as mentioned above) of allowing type parameters to be used more than once in specialization.