Shipping specialization: a story of soundness

[jmst]

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.

[steven099]

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

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.

[withoutboats]

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.

[burakumin]

@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)

[dtolnay]

@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);
}

[withoutboats]

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.

[Fylwind]

Some possibly relevant literature regarding the conflict between associated types and overlap / specialization from a Haskell perspective: http://okmij.org/ftp/Haskell/typeEQ.html#anti-over

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.

[withoutboats]

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.

[arielb1]

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.

[RalfJung]

Something probably has to give, but I do hope it’s not lifetime parametricity.

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

[Ericson2314]

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?

[glaebhoerl]

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

[Ericson2314]

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.

[glaebhoerl]

I was sorta thinking there’s very little true invariance in the heart of Rust if the “latent” ontravariance can be used

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

[Ericson2314]

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?!

[rkjnsn]

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?

[philipc]

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.

[comex]

Necropost:

I recently read in a random Hacker News comment about “type roles” in Haskell:

https://ghc.haskell.org/trac/ghc/wiki/Roles

…and it occurred to me that the problem the feature was meant to solve is pretty similar to the soundness hole here.

The compiler expects to be able to use the same trait/typeclass implementations for two types based on the assumption that they have identical representations:

• Haskell: A newtype versus the type it wraps
• Rust: Types that differ only in lifetime parameters

This works for normal (parametric) generic code, but is broken by the ability to create a type-to-type ‘lookup table’:

• Haskell: …using type families (which are just associated types, in Rust terminology, but because Haskell’s type system treats newtypes as separate types, there’s nothing preventing you from impl’ing something for a newtype and its base type with different associated types)
• Rust: …using associated types + specialization (specialization is required because the language has only a single concrete lifetime, 'static, so there’s no other way to have two separate impls of the same trait for two types differing only in a lifetime parameter)

Haskell’s solution is to differentiate between two ‘roles’ of type parameters: “representational” parameters, which allow coercions but not lookup, and “nominal” parameters, which allow lookup but not coercions. (By “coercions” I mean the features in first set of bullets, and by “lookup” I mean the second set.)

However, @glaebhoerl once wrote, about the roles feature:

The opinion of many leading members of the Haskell community is that this solution was ill-conceived and brings more complexity than it’s worth.

And I’m not really sure what an equivalent feature would look like in Rust, anyway.

[vi0]

“representational” parameters …, and “representational” parameters,

Probaby one of them should be changed.

[aturon]

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