Another specialization discussion: what about add a `or` clause

language design
1

TL;DR, I am proposing a grammar like

impl <T,const N>  Copy for [T;N] 
where N==0 {
    // currently N==0 is not a legal constrain, since we could directly evaluate N. But we could allow it later since we need it.
} or where T:Copy {}

trait Foo {
    fn foo() where Self:Bar {
        <Self as Bar>::bar()
    } or where Self:Baz {
        <Self as Baz>::baz()
    }
}

the or conjunction could be either removed(since it is not necessary, where clause after a } is currently an error.)

All of us know that, for array [T;N]

If the element T is Copy, then [T;N] should be Copy for all N

If the const parameter N is 0, then [T;N] is a ZST-type [T;0], which should also be Copy.

Thus, our constrains of impl<T,const N> Copy for [T;N] should be

where T:Copy *OR* N==0,

and for now, rust could not recognize or pattern in where clause, since we could not write a simple program that fits either constrains (otherwise, the constrains could be strengthen into T:Copy *AND* N==0)

Thus, a simple idea come up into my mind: is it possible add a or clause to impl block?

impl <T,const N>  Copy for [T;N] 
where N==0 {
    // currently N==0 is not a legal constrain, since we could directly evaluate N. But we could allow it later since we need it.
} or where T:Copy {}

Further, we could place where clause in the trait, evaluate it later.

Suppose we have

trait Foo {
    fn foo() where Self:Bar {
        <Self as Bar>::bar()
    } or where Self:Baz {
        <Self as Baz>::baz()
    }
}
trait Bar {
    fn bar();
}
trait Baz {
    fn baz();
}

the advantages of such implementation is that

Firstly, we could rely the specialization result, since all the specialization is controlled by crate owner rather than user.

Secondly, it allow us define different specialization trait for same object, for example

trait NaiveCalculation {...}
trait SimdCalculation {...}
trait ParallelCalculation {...}
trait ParallelSimdCalculation {...}
trait Calculation {...}
impl<T> Calculation for T
#[cfg(features="simd","rayon")]
where T:ParallelSimdCalculation {...}
or
#[cfg(features="simd")]
where T: SimdCalculation {...}
or 
#[cfg(features="rayon")]
where T: ParallelCalculation {...}
or where T:NaiveCalculation{...}

Currently, we could not define simple things like

impl <T:Bar> Foo for T{}
default impl <T:Baz> Foo for T{}

since we could not ensure T is never Bar+Baz

but if we have or where clause, things could be easy.

Is it possible? What's the shortcoming?

2

This can be solved by requiring an additional impl<T: Bar + Baz> Foo for T.

The most important problem on specialization is that lifetime specialization is unsound, and your proposal does not solve that. In fact I'm afraid your proposal is equivalent to full specialization regarding expressive power.

5 Likes
3

Are you talking about this thread

#![feature(specialization)]
#![allow(incomplete_features)]
#![allow(unused_variables)]

trait Is<T> {
    fn is(&self);
}

impl<A, B> Is<A> for B {
    default fn is(&self) {
        println!("no");
    }
}

impl<T> Is<T> for T {
    fn is(&self) {
        println!("yes");
    }
}

fn is_static_str<N: Is<&'static str>>(t: N) {
    t.is();
}

fn fully_generic_wrapper_function_without_trait_bound<N>(t: N) {
    is_static_str::<N>(t);
}

fn main() {
    let static_str: &'static str = "hey";

    let deallocated_at_end_of_main: String = "hello".to_string();
    let not_static_str: &'_ str = deallocated_at_end_of_main.as_str();

    is_static_str(static_str); // Ok, prints "yes"
    is_static_str(0u32); // Ok, prints "no"
    is_static_str(&0u32); // Ok, prints "no"
    // is_static_str(not_static_str); // Error, borrowed value does not live long enough

    fully_generic_wrapper_function_without_trait_bound(static_str); // yes
    fully_generic_wrapper_function_without_trait_bound(0u32); // no
    fully_generic_wrapper_function_without_trait_bound(&0u32); // no
    fully_generic_wrapper_function_without_trait_bound(not_static_str); // yes (no Error!)
}

In this case,

fn is_static_str<N: Is<&'static str>>(t: N) {
    t.is(); // fine, since t:N impl Is<...>
}
fn fully_generic_wrapper_function_without_trait_bound<N>(t: N) {
    // how we could ensure N: Is<&'static str>?
    is_static_str::<N>(t);
}

IMHO, It is because calling is_static_str::<N> for a arbitary N is unsound that cause such problem.

What's more, currently, we could not impl <T:Bar or Baz> Foo for T (both [T; 0] and [T:Copy; N] could be Copy, but currently rustc just couldn't mark both of them as Copy)

error[E0119]: conflicting implementations of trait `Foo`
 --> test.rs:7:1
  |
6 | default impl <T:Bar> Foo for T{}
  | ------------------------------ first implementation here
7 | default impl <T:Baz> Foo for T{}
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation

error: aborting due to previous error

For more information about this error, try `rustc --explain E0119`.

code

#![allow(incomplete_features)]
#![feature(specialization)]
trait Foo{}
trait Bar{}
trait Baz{}
default impl <T:Bar> Foo for T{}
default impl <T:Baz> Foo for T{}
impl<T:Bar+Baz> Foo for T{}
impl Bar for i32{}
impl Baz for i32{}
fn main(){}
4

That's just because no one has implemented the feature in current rustc. We can have it when we feel like it.

There's quite a few blog posts on this topic. For example, this one.

That's quite a hand waving statement. We have impl<A, B> Is<A> for B , why can't we calling is_static_str::<N> with arbitary N?

Just like what I said before. Your proposal is equivalent to full specialization.

2 Likes
5

Maybe there could be a exponential explosion

fn call<N:Is<&'static i32>>(t:N) {}
fn check_array(a:(&i32,&i32,&i32,&i32,&i32,&i32,&i32,&i32,&i32,&i32,&i32,&i32)){
    call(a.0);
    call(a.1);
...
    call(a.11);
}

about 2^12 different functions may generated since call(...) is a static dispatch.

Thus, it is needed to unify the performances, make there only 1 call called 12 times, rather than 2 call called 12 times totally.

what's more, is it possible adding some special marks for &'static?

I means,

struct &T {*const ptr:usize, Metadata:...,PhantomData<NormalReference>}
struct &'a T {*const ptr:usize, Metadata:...,PhantomData<LongLiveReference>} // if 'a is longer than both trait item's lifetime
struct &'static T {*const ptr:usize, Metadata:...,PhantomData<StaticReference>}

in such case, we could send an additional PhantomData<StaticReference> into the functions, which may solve the 'static problem, at least we could recognize 'static lifetime.

6

In general this is not possible. In many places lifetimes are erased. For example for<'a> fn(&'a str) is a function pointer and so it has to point to a single function for every lifetime 'a, including 'static. It also works like this for normal functions (hence why 'static lifetime specialization is unsound and why there aren't 2^12 versions of your check_array), though it doesn't have to be like this (AFAIK it's mostly just for performance because doing otherwise would be really slow).

1 Like
7

I use 2^12 to show that, it is impossible to both enable &'static specialization and static dispatch.

Thus if we already specify a function to call, just call it or throw an error.

In this case, if we really want such, we could have a mark:

#![feature(specialization)]
#![allow(incomplete_features)]
#![allow(unused_variables)]

#[repr(transparent)]
pub struct Static<T:'static+?Sized>{field:&'static T}
impl<T:'static+?Sized> Clone for Static<T>{
    fn clone(&self)->Self {
        Self{field:self.field}
    }
}
impl<T:'static+?Sized> Copy for Static<T>{}
impl<T:'static+?Sized> From<&'static T> for Static<T> {
    fn from(field:&'static T)->Self{Self{field}}
}
impl<T:'static+?Sized> Static<T> {
    /// only T:'static could call new function, thus only static reference could be generated.
    pub fn new(field:&'static T)->Self{Self{field}}
}
pub trait IsStatic{}
impl<T> IsStatic for Static<T>{}

trait Is<T> {
    fn is(&self);
}

impl<A, B> Is<A> for B {
    default fn is(&self) {
        println!("no");
    }
}

impl<T> Is<T> for T {
    fn is(&self) {
        println!("yes");
    }
}

fn is_static_str<N: Is<Static<str>>>(t: N) {
    t.is();
}

fn fully_generic_wrapper_function_without_trait_bound<N>(t: N) {
    is_static_str::<N>(t);
}


fn main() {
    let static_str: &'static str = "hey";

    let deallocated_at_end_of_main: String = "hello".to_string();
    let not_static_str: &'_ str = deallocated_at_end_of_main.as_str();

    let static_str:Static<str>=static_str.into();
    let not_static_str:Static<str>=not_static_str.into(); // Error, borrowed value does not live long enough

    is_static_str(static_str); // Ok, prints "yes"
    is_static_str(0u32); // Ok, prints "no"
    is_static_str(&0u32); // Ok, prints "no"
    // is_static_str(not_static_str); // Error, could not define not_static_str as Static<str>

    fully_generic_wrapper_function_without_trait_bound(static_str); // yes
    fully_generic_wrapper_function_without_trait_bound(0u32); // no
    fully_generic_wrapper_function_without_trait_bound(&0u32); // no
    // fully_generic_wrapper_function_without_trait_bound(not_static_str); // Error
}
8

In my propose, enable 'static dispatch seems not very impossible:

trait Static{}
trait Normal{}
impl<T:'static+?Sized> Static for &T {} // does not touch such grammar before, have no idea whether it is legal.
impl<'a,T:'a+?Sized> Normal for &T {} // does not touch such grammar before, have no idea whether it is legal.
trait Foo{}
impl<'a,T> Foo for &T 
where &T: Static{/*specialized impls*/}
where &T: Normal{/*normal impls*/}

compiler could recognize T:Static or not (since we allow impl<T:'static> .. for &T) and thus the specialization is automated done.

9

I'm not sure what you're trying to do with this... You're just showing an example of 'static specialization, which is unsound and should not compile.

10

The code is shown as 3 parts, the most important part is that, define a trait for T:'static, which works even without specialization

#[repr(transparent)]
pub struct Static<T:'static+?Sized>{field:&'static T}
impl<T:'static+?Sized> Clone for Static<T>{
    fn clone(&self)->Self {
        Self{field:self.field}
    }
}
impl<T:'static+?Sized> Copy for Static<T>{}
impl<T:'static+?Sized> From<&'static T> for Static<T> {
    fn from(field:&'static T)->Self{Self{field}}
}
impl<T:'static+?Sized> Static<T> {
    /// only T:'static could call new function, thus only static reference could be generated.
    pub fn new(field:&'static T)->Self{Self{field}}
}
pub trait IsStatic{}
impl<T> IsStatic for Static<T>{}

the second part is a normal specialization without considering 'static lifetime.

Here, instead of mark 'static directly, I just test whether a struct impls Is<Static>

trait Is<T> {
    fn is(&self);
}

impl<A, B> Is<A> for B {
    default fn is(&self) {
        println!("no");
    }
}

impl<T> Is<T> for T {
    fn is(&self) {
        println!("yes");
    }
}

fn is_static_str<N: Is<Static<str>>>(t: N) {
    t.is();
}

fn fully_generic_wrapper_function_without_trait_bound<N>(t: N) {
    is_static_str::<N>(t);
}

Notice that we could only create Static<T> with &'static T(in safe code), the second part always generate correct result, or fails before calling it.

And the final part, just a test


fn main() {
    let static_str: &'static str = "hey";

    let deallocated_at_end_of_main: String = "hello".to_string();
    let not_static_str: &'_ str = deallocated_at_end_of_main.as_str();

    let static_str:Static<str>=static_str.into();
    let not_static_str:Static<str>=not_static_str.into(); // Error, borrowed value does not live long enough

    is_static_str(static_str); // Ok, prints "yes"
    is_static_str(0u32); // Ok, prints "no"
    is_static_str(&0u32); // Ok, prints "no"
    // is_static_str(not_static_str); // Error, could not define not_static_str as Static<str>

    fully_generic_wrapper_function_without_trait_bound(static_str); // yes
    fully_generic_wrapper_function_without_trait_bound(0u32); // no
    fully_generic_wrapper_function_without_trait_bound(&0u32); // no
    // fully_generic_wrapper_function_without_trait_bound(not_static_str); // Error
}

it is worth mention that, we could not create Static<str> from not_static_str.into(), thus all the results are either legal or could not compile.

This came up to my next thread:

when rustc found

impl<'a,T> Foo for &T 
where &T: Static{/*specialized impls*/}
where &T: Normal{/*normal impls*/}

it should firstly create test whether the following code compiles:

impl<'a,T> Foo for &T 
where &T: Static{/*specialized impls*/}

if error generates, the code cannot be specialized.

After finising calculation of where &T: Static{/*specialized impls*/}, rustc should move to next where clause, test whether impl<'a,T> Foo for &T where &T: Normal{/*normal impls*/} compiles.

since gcc could recognize some simple error (e.g., send 'a lifetime to function require 'static lifetime is illegal.), the procedure could yield the specialized version for 'static, and normal version for the rest 'a

11

This is lifetime-dependent specialization, and is currently believed to be unsound. I've not followed the arguments for why this is unsound, thus I cannot explain what you need to do to make it become sound, if you want to be able to specialize based on lifetime parameters.

It also needs significant compiler changes; at the point the compiler chooses which specialization to use, it doesn't know whether the lifetime is 'static or 'a - it just knows it has an item of type &T, and that the borrow checker has confirmed that the lifetime rules are met by this code. So it needs to choose the specialization without knowing if what it has is &'static T or &'a T - but you've got a choice for it based on which of those two it has.

2 Likes
12

Firstly, rust have some ability recognize &'a T and &'static T (at least for borrow checker)

we could utilize such implementations, convert &'a T and &'static T to Normal<'a,T> and Static when a generic function is called.

since rustc could recognize the difference between two different types, further implementation could be sound.

13

This would make a function which is only generic over lifetimes also generic over types, which is very problematic because lifetimes are assumed to be eraseable and thus a function generic over lifetimes only is equivalent to a non-generic function.

You also seem to assume that since &'a T and &'static T can be distinguished at some point, they are always distinguishable. This is not the case, during codegen and monomorphization lifetimes are already erased, i.e. &'a T and &'static T are exactly the same and they can't be distinguished anymore. Those are also the phases where the "specialized" implementation is selected, and thus &'a T and &'static T need to be distinguished (but they can't).

Have you read this blog post? Shipping specialization: a story of soundness · Aaron Turon It explains why some naive solutions to this problem are not viable.

4 Likes
14

And just to summarise, the issue with not erasing lifetimes is compile resource usage blowup. If you allow us to choose a different implementation based on lifetimes, then every call to func from below has to have a unique monomorphization until you show that we're choosing the same implementation as another lifetime.

fn func<'a>(p1: &'a Type) -> usize

In today's Rust, borrowcheck can confirm that my call to func is legitimate, and erase the lifetime. Similarly, func can be borrowchecked, and then the lifetime erased before func gets codegen.

If we said that every call to func was a unique monomorphization, then we get rid of the soundness issue. But now you have a compile resource issue - if I call func 100 times in my code with different parameters (hence possibly different lifetimes), instead of one monomorphization of func, I have 100 monomorphizations to sort through, and confirm that they're all the same before I generate code. Or I generate lots of copies, and then merge them.

1 Like
15

Is it necessarily the case though that we would have to monomorphize for every lifetime? Don't we only have to distinguish between 'static and non-'static lifetimes because that's the only case where you can have different implementations (AFAIR)?

16

You'd still have the problem - until you've finished analysing the entire program, you don't know whether a given lifetime is actually 'static, or a shorter lifetime. And if you simply assume shorter unless you know it's 'static, you get surprises like:

trait Print {
    fn print(&self);
}

impl<'a> Print for &'a str {
    fn print(&self) { println!("short {}", self); }
}

impl Print for &'static str {
    fn print(&self) { println!("static {}", self); }
}

fn func<'a>(p1: &'a str) {
    p1.print()
}

fn main() {
    let hello = &*"hello"';
    let world = "world":

    func(hello);
    func(world);
}

printing:

short hello
static world

despite it being possible for both references to have 'static lifetime (hello does not, because we pick the shortest lifetime that works at the moment).

And you can have different implementations for two non-'static lifetimes. For example:

impl<'a, T> Print for (&'a T, &'a T) {
    fn print(&self) { println!("Two same lifetime"); }
}

impl<'a, 'b, T> Print for (&'a T, &'b T) {
    fn print(&self) { println!("Two different lifetime"); }
}

While I'm not clever enough to work out how to do it, there's apparently a way to abuse specialization if you don't correctly handle this pair so that you can extend a lifetime arbitrarily via specialization. The only sound way to avoid that is to handle pairs like this, and distinguish "two different non-'static lifetimes" from "two non-'static lifetimes, both the same".

17

The impl-level version of this sounds like Purescript's instance chains

1 Like
18

No. You can have something like this:

impl<'a, 'b> S for T<'a, 'b> {
    // default impl body
}

impl<'a: 'b, 'b> S for T<'a, 'b> {
   // specialized impl body
}

Neither 'a or 'b requires 'static.

1 Like
19

Ah, okay, didn't realize this. Thanks!

1 Like
20

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.