On always-applicable trait impls

Specialization is cool and people really want it. We also already use it in the standard library a bunch for performance reasons.

We only have information about free regions available during analysis. If we have to decide whether to specialize during codegen we do not have any region information available.

One way around this is to require specialization to be lifetime independent. The used implementations have to be always applicable.

This rule can either apply to impls, making sure any use of them is always applicable by construction, or to specific trait bounds. Requiring all impls used by specialization to be always applicable is not workable. We’ve implemented this for #[feature(min_specialization)], an intended to be sound subset of full specialization for use in std.

The requirements on impls are too strict, so there’s an internal #[rustc_unsafe_specialization_marker] attribute you put on traits which disables the check for impls. We end up using this marker pretty much any time we want to specialize in the standard library.

If limiting trait implementations does not work, what about disallowing lifetime dependence when applying the impls?

The intended behavior

trait Trait {}
impl Trait for u32 {}

impl<'a> Trait for &'a i16 {}
impl Trait for &'static i32 {}

impl<'a, T: Trait + 'a> Trait for &'a T {}
impl<T> Trait for (T, T) {}

fn spec_check<T>() -> bool {
    // fake syntax :3 specializing on `T: Trait`
    if is_implemented!(T: Trait) {
        true // `T: Trait` holds
    } else {
        false // `T: Trait` does not hold or may be lifetime dependent
    }
}

fn main() {
    // no lifetimes, directly corresponds to whether `T: Trait` is implemented
    assert_eq!(spec_check::<u32>(), true);
    assert_eq!(spec_check::<i32>(), false);
    assert_eq!(spec_check::<(u32, u32)>(), true);

    // not lifetime dependent, applicable for all `'a`
    assert_eq!(spec_check::<&i16>(), true);

    // lifetime dependent, only implemented for `&'static i16`.
    assert_eq!(spec_check::<&i32>(), false);

    // not lifetime dependent, the outlives constraint of the
    // `impl<'a, T: Trait + 'a> Trait for &'a T {}` is required by
    // the well-formedness of the self type.
    //
    // Implementing this is slightly annoying :<
    assert_eq!(spec_check::<&u32>(), true);
    assert_eq!(spec_check::<&&u32>(), true);

    // lifetime dependent, only implemented for tuples where
    // the lifetimes in both fields are the same.
    assert_eq!(spec_check::<(&u32, &u32)>(), false);
}

The consequences

If a type parameter T of an impl is mentioned multiple times and instantiated with a type with free regions, the impl is now lifetime dependent. This has some annoying effects.

trait Trait<T> {}
impl<T> Trait for T {}
fn spec_check<T, U>() -> bool {
    // fake syntax :3 specializing on `T: Trait`
    if is_implemented!(T: Trait<U>) {
        true // `T: Trait` holds
    } else {
        false // `T: Trait` does not hold or may be lifetime dependent
    }
}

fn main() {
    assert_eq!(spec_check::<(u32, u32)>(), true);
    // `(&'a u32, &'b u32)` is not implemented while `(&'a u32, &'a u32)` is,
    // lifetime dependent.
    assert_eq!(spec_check::<(&u32, &u32)>(), false);
    // The lifetimes in `fn(&u32)` are higher-ranked, they don't
    // impact always applicable checking.
    assert_eq!(spec_check::<(fn(&u32), fn(&u32))>(), true);
}

Now, for a quick quiz:

If you’ve guessed that only Box<&u32>: PartialEq is lifetime dependent and the others are all fine, good job!

If you’re unsure why, look at the definition of PartialEq and how it is implemented:

trait PartialEq<RHS = Self> {}
impl<A: PointeeSized, B: PointeeSized> PartialEq<&B> for &A
where
    A: PartialEq<B>,
{}
impl<T: ?Sized + PartialEq, A: Allocator> PartialEq for Box<T, A> {}
impl<T, U, A1, A2> PartialEq<Vec<U, A2>> for Vec<T, A1>
where
    A1: Allocator,
    A2: Allocator,
    T: PartialEq<U>,
{}

The PartialEq impl for Box does not explicitly specify the defaulted type parameter, so it uses T twice. The other ones explicitly handle the case where the RHS is a different type. The same problem exists for other traits, like Add.

This not only affects existing traits, it also means that adding new type parameter defaults is a breaking change if that parameter default mentions another generic parameter. This is currently not the case and seems undesirable.

We do not need the always-applicable rule

Lets go back to the start.

We only have information about free regions available during analysis. If we have to decide whether to specialize during codegen we do not have any region information available.

If we decide whether to specialize during analysis we can properly check regions, allowing for lifetime dependent specialization. Let’s consider the code from the first example again:

trait Trait {}
impl Trait for &'static u32 {}

fn spec_check<T>() -> bool {
    // fake syntax :3 specializing on `T: Trait`
    if is_implemented!(T: Trait) {
        true // `T: Trait` holds
    } else {
        false // `T: Trait` does not hold or may be lifetime dependent
    }
}

fn main() {
    // We want this to succeed.
    assert_eq!(spec_check::<&'static u32>(), true)
}

For this example to work, we need to know that spec_check relies on whether T implements Trait so that we can check whether this holds while type checking fn main. This can be done by adding a maybe Trait bounds to spec_check, allowing the caller to decide whether to provide spec_check with a proof of T: Trait.

fn spec_check<T: maybe Trait>() -> bool {
    // fake syntax :3 specializing on `T: Trait`
    if is_implemented!(T: Trait) {
        true // `T: Trait` holds
    } else {
        false // `T: Trait` does not hold or may be lifetime dependent
    }
}

fn main() {
    // Calling `spec_check` will now try to prove `T: Trait` during type checking.
    // If we succeed, pass in the information that it is implemented.
    assert_eq!(spec_check::<&'static u32>(), true)
}

More thoughts

Maybe bounds need to be proven when using an item. If we’re unable to prove a maybe bound in a generic context we should emit a lint.

fn foo<T: maybe Clone>() {
    if is_implemented!(T: Clone) {
        
    }
}

fn bar<T: Clone>() {
     // always clone
    foo::<T>();
}

fn baz<T>() {
    // never clone
    foo::<T>();
    //~^ WARN: discarding maybe bound for generic type
    //~| NOTE: `T` may implement `Clone`
    //~| NOTE: this disables any specialization in `foo`
    //~| HELP: consider propagating the `maybe Clone` bound to the caller  
}

fn yeet() {
    bar::<u32>();
    baz::<u32>();
}

While we can check region constraints during analysis, we cannot decide whether to prove a maybe bound depending on whether doing so would result in a region error. However, we can explicitly avoid providing the relevant bound in this case, e.g.

struct CloneIfStatic<'a>(&'a ());
impl Clone for CloneIfStatic<'static> {
    // ...
}

fn call_direct<'a>() {
    foo::<CloneIfStatic<'a>>(); //~ ERROR lifetime error, `'a` is required to outlive `'static`
}

fn foo_indir<T>() {
    #[expect(discarded_maybe_bound)]
    foo::<T>();
}
fn call_indir<'a>() {
    foo_indir::<CloneIfStatic<'a>(); // ok
}

We can have maybe bounds in super trait position to always allow specializing on them. A good candidate here would be trait Clone: maybe Copy. This would allow any item with a T: Clone bound to specialize on T: Copy in a sound way. Other candidates involve trait Iterator to enable its giant mess of specializations.

We can also allow the use of maybe bounds in types by having some type-level matching on whether a trait is implemented, unsure about the syntax, but one could imagine the following:

trait Foo {
    type Assoc;
}

impl<T: maybe Copy> Foo for T {
    type Assoc = type_if T: Copy { T } else { Rc<T> };
}

We could also support maybe-bounds in trait objects, something like

// The vtable of this trait object would store an `Option<&'static CloneVtable>`.
fn foo<T: maybe Clone>(x: &T) -> &dyn maybe Clone {
    x
}

fn downcast(x: &dyn maybe Clone) -> Option<&dyn Clone> {
    x.try_downcast::<dyn Clone>();
}

Unlike specialization, maybe-bounds are trivially soundness

Having pattern matching introduce new things in the environment is less so :3

One way to think of trait bounds in Rust is that every trait bound actually lowers to an implicitly provided dictionary. This is a separate topic I should also write about, for now, here’s a project goal.

Here’s the 2 minute explanation

fn foo<T: Clone>(x: &T) -> T  {
    x.clone();
}

// would be lowered/desugared to
struct CloneDict<T> {
    clone_fn: fn(&T) -> T,
}

fn foo<T: Clone, const DICT: CloneDict<T>>(x: &T) -> T {
    (DICT.clone_fn)(x)
}

fn bar<T: maybe Clone>(x: &T) -> Option<T> {
    if is_implemented!(T: Clone) {
        Some(x.clone())
    } else {
        None
    }
}

// would be lowered/desugared to
fn bar<T: Clone, const DICT: Option<CloneDict<T>>>(x: &T) -> T {
    if let Some(dict) = DICT {
        Some((dict.clone_fn)(x))
    } else {
        None
    }
}
if you find any typos or errors in this post, please pm me on zulip or discord

back

impressum rss