Idea: making traits specialization safe over an edition boundary

I have a draft document[1] laying out a possible vision for (allegedly) sound specialization. The connecting thread between all such systems is that the bounds used for specialization MUST NOT be potentially dependent on any lifetime bounds, as that would be unsound[2]. Thus, because trait impls can introduce lifetime bounds, specialization cannot be bound on trait bounds.

The solution to this conundrum is what @nikomatsakis called “always applicable impls” — impls which introduce no bounds which are not entirely structural (i.e. are present on the type definition, and would be implied by the implied bounds RFC). Aside: note that impl Drop has always been required to be always applicable, so this concept already exists in the language. As part of feature(min_specialization), Rustc defines an attribute #[rustc_specialization_trait] for marking “specialization safe” traits where all impls are required to be “always applicable” (e.g. Sized) and then allows specialization to be bound on these traits. (My notes call this virtual trait, FWIW, as the keyword is available and vaguely appropriate.) Rustc also defines a separate #[rustc_unsafe_specialization_marker] which doesn't have the “always applicable” impl requirement as an unsafe escape hatch (e.g. for Copy).

What if: in a future edition, we mark all the marker traits as “specialization safe” and require all new impls of those traits to be always applicable? For compatibility with old editions, under the hood the compiler would remember if an impl is required to be always applicable and only use it for specialization bounds if so[3]. Given we'd want to lint impls in old editions which aren't new edition compatible, it'd be possible to have any always applicable from old editions (e.g. via #[derive(Copy)]) also participate in specialization, minimizing the surface area of impls that exist but don't get specialized on.

IIUC, the ability to have explicit Copy implementations that aren't specialization safe is mostly regarded as an unfortunate reality, rather than intentional or useful[4]. Removing that possibility to close a reasonably well-known soundness hole[5] is potentially justifiable.[6]

Alternatively, make all editions behave the same and merely warn for non-specialization-safe impls instead of erroring. Or perhaps make participating in specialization explicitly opt-in; perhaps virtual impl? (Using virtual in the sense of “participates in specialization” which, while not the OOP virtual, I think is compatible meaning to it.)


  1. Far from ready to be seen, unfortunately; what notes I do already have are barely comprehensible to me, and even then only because they prompt me to remember the various ideas I've had, rather than actually stating useful domain information and/or context. ↩︎

  2. This is because lifetimes are not (and cannot be) monomorohically compiled. Because of this, a single lifetime-polymorphic function cannot possibly select which of a called lifetime-dependent specialization set to invoke. I suppose we could “just” declare that invoking a more general implementation in a specialization set is “sound,” and we could even potentially exactly specify how lifetime-dependent specialization selection works, but nobody is particularly keen on calling such pseudo-nondeterminism “sound.” And it'd require the compiler being particularly careful to select the more general implementation instead of the more strongly bound one, to avoid actual unsound lifetime extension (IIRC the current trait selection can do this.) ↩︎

  3. Potentially, and as if, via splitting the traits into the current and a TrustedMarker version, like is done in std specialization already in practice. (An internal unstable StructuralClone and/or TrustedCopy could work to remove #[rustc_unsafe_specialization_marker] from Copy today, if that's considered desirable.) ↩︎

  4. Even the case of a typestate marker recording that type-erased data is[n't] Copy can straightforwardly be specialization safe by making their custom marker trait also specialization safe. ↩︎

  5. Although in fairness, one that's quite difficult to actually exploit and turn into unsoundness in practice, since it requires a conditionally-Copy type where copying a non-Copy instance instead of cloning it is in some way unsound and not only logically incorrect. ↩︎

  6. It could, however, likely mean that I'd need to replace my habit of writing things like unsafe impl<T> Sync for MyType<T> where Arc<T>: Sync {} with writing the elaborated, more clearly specialization safe form like unsafe impl<T> Sync for MyType<T> where T: Send + Sync {} instead. (The former only adds specialization safe bounds, so should be specialization safe, but the mention of an unrelated type makes that non-obvious.) ↩︎

4 Likes

Reading this I couldn't help but think of a possible equivalence with the following:

  • Introduce replacements for each of the marker traits
  • The same paths refer to the different traits in different editions, for instance std::marker::Sync (or just Sync from the prelude) means OldSync in older editions, NewSync in new edition
  • unsafe impl<T: NewSync> OldSync for T

Does that mean we couldn't have impl<T: Marker> Marker for Foo<T>? AIUI this wouldn't be always-applicable, unless the requirement was also on Foo itself, but this is what built-in derives and auto-traits will give you today. I hope I'm misunderstanding...

My language was a bit imprecise here; I meant to say "specialization safe" such that adding non-structural bounds on other "specialization safe" traits is permitted.

2 Likes

Note that the always-applicable rules about specialization traits are annoyingly restrictive.

  • they don't take coherence into account.
    Given impl<I> LocalTrait for LocalStruct<I> where I: LocalTrait
    I can write impl<I> SpecTrait for LocalStruct<I> where Self: LocalTrait
    but not impl<I> SpecTrait for LocalStruct<I> where I: LocalTrait
    even though based on coherence rules those are identical requirements as long as the same crate doesn't add another impl.
  • can't write impl<T> SpecFoo<T> for Bar<T> because T gets repeated, which often prevents adding essential helper functions to specializations

Additionally min_specialization lacks a bunch of features

  • no general solution for overlapping impls - sometimes additional specialization helpers work, but not always
  • no associated type and const specialization

Additionally it lacks some safety features (though those seem fixable) such as an option to require specializing impls to implement all methods (unsafe code can make mixing specialized and non-specialized methods unsound)

The current state of specialization manages to be useful and yet fails to cover a lot of cases where it's desirable. So if these limitations can't be fixed with future extensions to the current design then it seems like a tantalizing dead end, even if the current state could be stabilized.

So it seems necessary to me to check not only if the current state could be stabilized but also if there's any hope that its shortcomings can be addressed later.

Though even without stabilization fixing the Copy soundness hole does sound nice.

2 Likes

What's your plan for specializing on Copy? Would we need a new CopyButWorksForSpecialization, since existing Copy impls might not meet the rules?

I guess that could be trait UnconditionalCopy: Copy {} like Niko's example for Seek.

My draft concept doesn't (yet) cover migration of existing traits, it just sets out a framework for determining what bounds are safe to be specialized on.

But that transition is exactly what this post's "what if" is about — take std::marker::Copy and logically split it into today's Copy (which wouldn't be specialized on) and a specialization-safe TrustedCopy, with the compiler doing some sort of inference for which one to use.

Without relying on that inference magic, an alternative way to model it that might be a StructuralClone (like how StructuralPartialEq works), which would ensure the unsound specialization case is still unobservable.

Note that as currently implemented, any specialized impls are required to be marked as default, at least if it can be partially specialized (it's been a while since I've played around with the current state). My draft maintains this syntactical indication of specializable impls for the very reason you mention, so the impl knows it could be.

I don't particularly like the use of default there (it's more indictive of default method bodies / partial trait impls to me, which are related to but still distinct from specialization[1]), the draft using virtual doesn't really sufficiently distinguish between impls that can be specialized and impls that can be used for specialization in most (all?) of the modes it considers. That contributes to why the draft isn't ready yet. (I also have a mild preference for "static if" style specialization over "impl replacement" style for similar reasons.)

My full vision for "specialization safe" is more permissive than "always applicable;" the latter doesn't even permit adding marker trait bounds. min_specialization effectively only supports (partially) concrete specialization and not bound specialization.

I think I have a reasonable grasp on what the fundamental constraints on sound specialization are, but I haven't yet been able to satisfactorily express them. For one particular wrinkle, while virtual trait TrustedTrait: Trait should certainly allow specializing default impl<T: Trait> with impl<T: TrustedTrait>, it could also permit specializing a base default impl<T> at the cost of constraining impl TrustedTrait further. Both can be desirable and I've yet to work that into my model.

I can't think of a use case for writing this specializing impl which isn't actually unsound; the sound cases don't have a separate SpecFoo<U> for Bar<T> and should thus be using an associated type instead.

A symptom of min_specialization mostly being for (partially) concrete specialization. The solution is known; lattice specialization, where if you have overlapping impls, you write an impl which specializes both and covers the overlap. Although tbf this is limited in application since the lattice impl must safely specialize both base impls independently to be sound, so the base impls can't differ by any non-specialization-safe bounds.

AFAICT this is because specializing (potential) type information plays havok on type/impl resolution. I think the work around opaque TAIT should make it possible to have specializable associated type/const, but if they aren't yet implemented as "final" (forbidding further specialization), generic code mustn't be allowed to know any concrete information about the type.


  1. The default impl must be "specialized" by a specific trait impl in order to be used, even if by an empty specialization, and can't ever be used directly without selecting one of the "specializations" (trait impls). ↩︎

I'm not sure if we're talking about the same thing. What I meant there is that in some cases, such as StepBy the default impl block and the specializing impl must not be mixed. I.e. all methods must be specialized and an instance created for one impl must not be coercible into another. Coercion has been a source of unsoundness before.

In the StepBy case it's even worse. If there's a specializing impl for one of the Iterator (well, the internal helper trait) then there must also be a specializing impl for DoubleEndedIterator. Although if the current specialization rules weren't so restrictive that could maybe have been solved by where Self: ... rules to shove both forward and backward iteration into a single impl.

I have previously mentioned this in the tracking issue but that got buried by github's horrendous pagination.

Having more distinguishable naming for specialization-marker-trait vs. trait-impls-that-can-be-specialized would be nice.

:+1:

Hrrm, I'll have to try that again. Maybe I just missed that approach. Or maybe I ran into other limitations.

Specific use-cases:

  • using an associated type to store and access extra fields that are only used by specializing impls. It'd go through MyStruct { extra: <Self as SpecTrait>::Assoc } or something like that.
  • one possible solution for the non-miscible implementations approach that I mentioned above
  • to populate associated consts of a single impl in a struct where the a field has has specializing impls where the consts take different values. E.g. iterator specialization traits carry various Option<NonZeroUsize> and bool consts where it would be useful if they could be calculated based on associated consts from specializing impls.