Shipping specialization: a story of soundness

Example (T) for the problem with lifetime-monomorphizing strategies.

#![feature(specialization)]


trait TryCoerce<T> {
    fn try_coerce(self) -> Option<T>;
}

impl<U, V> TryCoerce<U> for V {
    default fn try_coerce(self) -> Option<U> { None }
}

impl<U> TryCoerce<U> for U {
    fn try_coerce(self) -> Option<U> { Some(self) }
}

// type parameters needed to work around smart-ass type checking.
fn coerce_lifetime_into<'a, 'b, U, V>(x: &'a U, y: &mut Option<&'b V>) {
    *y = <&'a U as TryCoerce<&'b V>>::try_coerce(x);
}

// This is a single function pointer. We can pass it around to C code. If
// we want "reliable" specialization, it must somehow tell whether the input
// and output lifetimes are equal
pub static COERCE_LIFETIME_INTO: for<'a, 'b> fn(&'a u32, &mut Option<&'b u32>)
    = coerce_lifetime_into;
    
fn main() {}

I don’t follow the first example in Going deeper.

The following is valid in current rust:

trait Special {
    fn special(&self);
}

impl<T> Special for (T, T) {
    fn special(&self) {
        println!("specialized");
    }
}

fn pair<'a, 'b, T>(a: &'a T, b: &'b T) {
    (a, b).special()
}

fn main() {
    pair(&"hi", &"there");
}

So the tuple impl can be used even if the lifetimes aren’t identical, and trans doesn’t need to know what the lifetimes are. Furthermore, given that is valid, I would find it surprising if adding a more general impl to that code would cause rust to start using it instead.

As a naive user, I expect specialization to work as follows:

  1. Find the most specific specialization without taking lifetime bounds into account.
  2. Validate that the lifetime bounds are met, and give a compile error if they aren’t.

That fits better with my mental model of how rust currently works, but maybe my mental model is flawed.

1 Like

I believe the first example in the "Going deeper" section is not a place where type check and trans actually disagree, but a place where they theoretically could disagree depending on how we decide specialization should work and how many layers of indirection are involved.

However, type check could deduce that the more specialized impl always applies when invoking special in pair, and you could imagine communicating that information down to trans.

I think the reason he was bringing this up at all was to demonstrate that the soundness issues described in the rest of the post are not necessarily unique to associated types, and that's why a truly complete solution can't focus purely on associated types but must deal with the type checker vs trans more generally.

As a naive user, I expect specialization to work as follows:

  1. Find the most specific specialization without taking lifetime bounds into account.
  2. Validate that the lifetime bounds are met, and give a compile error if they aren't.

I basically agree with this. I suspect there might be some legitimate exceptions like having a default impl for &str and a specialization for &'static str, or having a default impl with two unconstrained lifetimes and a specialization for when the lifetimes are the same or one is known to outlive the other. I can't come up with a concrete use case for doing either of those things myself, but I doubt it's safe to assume there aren't any.


My only concern with the proposed subset for stabilization is that the post sounds like it's proposing we stabilize at least some cases where the behavior is expected to require changing in the future, and get away with that via lints and epochs. As much as I want epochs, for a feature like this that's part of the core trait system and has massive ramifications for optimally efficient composability across the ecosystem, I don't like the idea of relying on epochs to "get away" with stabilizing unstable behavior...assuming that's a remotely accurate summary of the proposal. It also wasn't clear to me from the blog post whether there is any alternative in between "stabilize some stuff we'll have to epoch away later" and "never stabilize anything until we have a perfect solution".

Could you go into more detail on why "lifetime specialization" can't be a hard error? The post only mentions in passing that:

(This needs to be a lint, not a hard error, because the relevant impls aren’t always under your crate’s control.)

But I don't see how not owning all the impls means it can't be as hard of an error as, say, the orphan rules.

The correct solution seems to be to not erase lifetimes and pass them lifetimes to monomorphization, perhaps taking monomorphization out of trans and doing it as a separate MIR pass before it.

The only thing that matters however is whether lifetimes are 'static, and how they compare to each other, which means that they should just be abstract numbers without region information along with a partial order between them, and monomorphization needs to normalize them so that the first lifetime that appears in the signature being monomorphized is renamed to “0”, the first different one to “1” and so on, and the result augmented with the ordering information used as the key for monomorphization (and symbol mangling).

This basic normalization should already reduce code generation explosion, but an extra pass could be added before monomorphization that determines which lifetime comparisons specialization could depend on, allowing to do a more powerful normalization taking them in account.

Then lifetime assignment rules need to made more precise, probably defined to be such that a lifetime is assigned to be, if possible, equal to the largest other lifetime it can be equal to (so if it can be 'static it should be). Or, with a global view, lifetimes are assigned so that the number of distinct lifetimes including 'static is minimized. Not totally sure if these criterias are correct though.

Of course this is assuming that lifetime specialization is a desirable feature in the first place, which for instance means being able to have a function that takes &'a T and turns it into a Cow, either assigning to the Borrowed variant or cloning and assigning to the Owned variant depending on 'a.

2 Likes

You're squeaking by based on lifetime variance here. It's trivial to construct an example where variance doesn't apply:

trait Special {
    fn special(&mut self);
}

impl<T> Special for (T, T) {
    fn special(&mut self) {
        println!("specialized");
    }
}

fn pair<'a, 'b, T>(ts: &mut (&'a T, &'b T)) {
    ts.special();
}

fn main() {
    pair(&mut (&"hi", &"there"));
}

Playground

Mutability forces the lifetimes to be invariant, so now the impl doesn't apply unless the lifetimes are identical.

The comment on monomorphization and lifetime erasure is interesting in that fundamentally the problem is that at no point during compilation do we have a “completely typed” program, with all of both life and type parameters resolved. If we had such a pass we could, with a small hole*, just allow lifetime based specialization. It would be a terrible UX to actually try to depend on it, and we’d probably want to warn when you have those impls and leave it out of our stability guarantee. But it would be sound.

*higher rank function pointers, which would just have to perform no lifetime based specialization for the parameters they’re higher rank in.


I’m worried that if we stabilize specialization without a story for assoc_specialization, we will be boxed in for our options for assoc_specialization, because some choices would involve changing the specialization order of lifetime-based specializations.

3 Likes

@aturon: a very simple and naive question from someone who’s interested but not very likely to crack the nut: are there any known examples of soundness issues due to interactions between specialization and lifetimes that do not involve 'static ? From the various explanations I’ve read so far it looks like 'static is the only value that creates problems (and as far as I know it is the only litteral lifetime in Rust)

@burakumin here is one that does not involve 'static.

#![feature(specialization)]

// Convert &'a T to Self
trait FromRef<'a, T: ?Sized> {
    fn from_ref(r: &'a T) -> Self;
}

// &'a T can be converted to &'a T
// But with specialization this impl incorrectly converts &'a T to &'any T
impl<'a, T: ?Sized> FromRef<'a, T> for &'a T {
    fn from_ref(r: &'a T) -> Self {
        r
    }
}

// &'a T cannot be converted to any other type
impl<'a, T: ?Sized, R> FromRef<'a, T> for R {
    default fn from_ref(_: &'a T) -> Self {
        unimplemented!()
    }
}

fn extend_lifetime<'any, T: ?Sized>(data: &T) -> &'any T {
    fn helper<T: ?Sized, R>(data: &T) -> R {
        // If R is &'any T then convert &T to &'any T
        R::from_ref(data)
    }
    // Instantiate helper::<T, &'any T>
    helper(data)
}

fn main() {
    let unsound = {
        let s = "specialization".to_owned();
        extend_lifetime(s.as_str())
        // s is dropped
    };
    // reference is still ok
    println!("{:?}", unsound);
}
1 Like

Anything which constrains any lifetimes is sufficient. Using a literal lifetime (as you note, 'static is the only one), but as in @dtolnay’s example, having the same lifetime appear twice in the signature of the impl constrains those two appearances to be equal to one another.

Some possibly relevant literature regarding the conflict between associated types and overlap / specialization from a Haskell perspective: Type Equalities, Disequalities and obsoleting of Overlapping Instances

If a type class includes associated data or types, overlapping is unsound -- as in segmentation-fault unsound.

I guess open world + negative reasoning makes a rather nasty combination. Something probably has to give, but I do hope it's not lifetime parametricity.

1 Like

The orphan rules are our protection against that problem in Haskell: given a fully concrete constraint (e.g. i32: Clone), no future crate can add a new impl for that constraint. This is part of what’s great about the orphan rules.

I have noticed though that there’s a symmetry with this problem and that problem in Haskell, which is that we don’t have complete information about a constraint at any 1 point in time.

I'm not sure. With our current type-system, the "only" issue is that reliable lifetime specialization destroys lifetime parametricity, and therefore our compilation strategy and ABI. A Rust interpreter could implement lifetime specialization, including associated types, fully reliably.

However,with NLL and its "conditional outlives relationships", it might not be actually be possible to know how lifetimes are related before code that depends on them is run.

It can't be. We rely on it for soundness (e.g. in RefMut::map).

I suppose that types that only differ re lifetimes have a common supertype? Can we use that semilattice to prevent lifetime specialization with things like the (T, T) example?

@Ericson2314 Does that idea still work if taking into account invariant type parameters?

:confused: I was sorta thinking there’s very little true invariance in the heart of Rust if the “latent” ontravariance can be used, but custom parameterized nominal types can’t soundly be replaced with their bodies, of course.

But the heart of Rust is &mut and it's invariant. (;

I forgot about that too :O. (In stateful MIR I do point out that splitting the intial and final type gets rid of the invariance, but that doesn’t help here.)

Maybe we should disallow aliasing of type parameters unless we forbid their substition with anything involving invariant lifetimes?!

That gives us leverage to use something like epochs to make trans smarter over time, while still shipping some version of specialization relatively soon.

I may be misunderstanding something, but isn't trans explicitly out of scope of the epochs RFC, which is targeted at front-end changes?

For the final bomb example, since trans knows that the code satisfies typeck, can it switch to treating the associated types as ‘in’ type parameters? So can it use the fact that s: String to select the correct specialization? This is assuming that the issues related to lifetime specialization have already been solved for cases that don’t involve associated types.

Or in other words, can trans treat the final bomb example the same as the following code:

trait Bomb<Assoc: Default> {}

impl<T> Bomb<()> for T {}

impl<T> Bomb<String> for (T, T) {}

fn indirect<T: Bomb<A>, A: Default>() -> A {
    A::default()
}

fn build<T, A1, A2>(t: T) -> A2
    where T: Bomb<A1>,
          (T, T): Bomb<A2>,
          A1: Default,
          A2: Default
{
    indirect::<(T, T), A2>()
}

fn main() {
    let s: String = build("Uh oh");
    drop(s)
}

I’m still learning the details of rust, so hope my posts here aren’t too much noise.