Info
I'm making a crate (tentatively named variance-family) for requiring that a family of types parameterized by a 'varying lifetime (like T<'varying>, using a made-up HRT syntax) is covariant or contravariant over 'varying.
TLDR of the below is that I want to know when transmuting &'a mut T<'v1> to &'a mut T<'v2> is sound; is "manually-proven" bivariance sufficient? (As opposed to needing compiler-proven bivariance, where the compiler can prove that 'varying is entirely unused in T<'varying>, making T<'varying> bivariant over 'varying.)
("Bivariance" over 'varying, at least in this post, means being both covariant and contravariant over 'varying. I read that the compiler doesn't internally represent bivariance as covariance + contravariance, but I don't know much about that.)
I want to permit manually-proven variance; that is, I want to permit people to unsafely assert that transmuting a lifetime in a covariant (or contravariant, or bivariant) way is sound even if the compiler considers the lifetime invariant. For instance,
/// # Variance
/// `unsafe` code (such as usage of `mem::transmute`) is allowed to assume that
/// covariantly changing the `'varying` lifetime of `Foo<'varying>` is sound.
//
// Safety of asserted guarantee to `unsafe` code:
// This struct trivially only uses `'varying` in a soundness-relevant covariant way.
// `PhantomData` is a ZST without any typestate-ish guarantees about its generic
// parameter, so even though the `PhantomData` here is invariant over `'varying`, the
// lifetime can soundly be transmuted in a covariant way.
struct Foo<'varying>(
&'varying u32,
PhantomData<fn(&'varying ()) -> &'varying ()>,
);
// This type could implement an `unsafe` trait from `variance_family` which
// indicates that transmuting `Foo<'v1>` to `Foo<'v2>` in a covariant way is sound.
I'm fairly sure that manually-proven variance is useful in nontrivial cases as well; for instance, when I made a concurrent skiplist (one supporting only insertions and not removal/deletions, if that's relevant), the nodes used in the skiplist had the following definition:
pub(super) struct Node<'herd> {
/// The `AtomicErasedLink`s have internal mutability that allow the pointers' values to be
/// changed. Nothing else is allowed to be changed.
///
/// Vital invariant: for any `AtomicErasedLink` in `skips` which semantically refers to another
/// node `node`, that `node` must have been allocated in the same [`Herd`] allocator as `self`.
///
/// Callers in this crate also generally put `Some` skips at the start and `None` skips at the
/// end, though that is not a crucial invariant.
///
/// [`Herd`]: bumpalo_herd::Herd
skips: &'herd [AtomicErasedLink],
entry: &'herd [u8],
}
(The entry values are immutable after a node's creation. A "link" is an Option<&'herd Node<'herd>>, and an AtomicErasedLink is a lifetime-erased link that wraps AtomicPtr<()> to let the link be changed atomically.)
That struct is covariant over 'herd, though if AtomicErasedLink were not lifetime-erased, it would be invariant over 'herd. The only parts of the struct's interface which write to the skips field are unsafe methods. (In other words, all parts of the type's interface which are contravariant over 'herd are gated behind unsafe with safety conditions that are sufficient to let all the covariant parts of the interface be safe.) In that particular case, I think covariance was largely a coincidence and my main goal was just "nail down the bump allocators", but I imagine that there's also code out there doing similar tricks for the sake of getting covariance. I might as well, then, support manually-proven covariance and contravariance in variance-family.
Is this sound, both with respect to std and third-party crates using generics?
In particular, as far as I'm aware, covariance and contravariance are additive, like Send or (most) crate features, so attaching importance (beyond something like "being !Send and not covariant in a parameter are infectious, it will make my wrapper type be !Send and not covariant in that parameter") to some generic parameter not being covariant or being !Send is immensely likely to be unsound. AFAIK it'd be perfectly sound for a particular !Send type to provide some means of sending values of that type to other threads... or for a T<'varying> invariant over 'varying to provide methods that are effectively covariant casts of 'varying. I think, then, that it'd also be sound for a T<'varying> type to document that using mem::transmute to covariantly change the 'variant parameter in T<'varying> is sound (and that it'd be sound for unsafe code to actually use mem::transmute to do so).
On the other hand, a type might force itself to be !Send or invariant over a parameter in order to allow unsafe code associated with that particular type to soundly make some assumptions. One concern I'm not at all worried about is someone using a Foo<'varying> field to force invariance (where Foo is the struct defined near the start of this post); AFAIK, it would actually be sound to use Foo to force invariance; there's no good reason for someone to peek into a struct's definition, see "aha, you must not actually be invariant in any important way", and proceed to write or use unsafe code that ignores the invariance. Whether a hypothetical counterexample relies on auto-traits, derive macros and specialization, or someone just reading the source code, I'm fairly sure that using Foo<'varying> to force invariance over 'varying does not let sound code be broken even if using mem::transmute to change the 'varying lifetime of Foo<'varying> is permitted. Of course, I don't think someone writing unsafe code should rely on Foo<'varying> to force invariance over 'varying, but any unsoundness that could result from composing a covariant transmute of Foo<'varying> with other unsafe code really seems like it'd be the fault of the other code.
If manually-proven covariance and contravariance are acceptable, then AFAIK, together they imply manually-proven bivariance. As far as I'm aware, the only way for the compiler to prove that T<'varying> is bivariant over 'varying is for 'varying to be entirely unused in T<'varying>; e.g., maybe T is a type constructor that always returns u32. Manually-proven bivariance would allow for other examples, but I can't imagine any useful examples. At the very least, there's something like Baz<'varying>(PhantomData<*mut &'varying ()>); where Baz promises not to do anything reliant on the 'varying lifetime.
I suspect that if T<'varying> unsafely asserts that bivariant casts of its 'varying parameter are sound, then transmuting &'a mut T<'v1> to &'a mut T<'v2> should be sound (where both types are well-formed).
Another way to phrase this claim is that if T<'v1> can be soundly transmuted to T<'v2>, and T<'v2> can be soundly transmuted to T<'v1>, then &'a mut T<'v1> can be soundly transmuted to &'a mut T<'v2> (if both types are well-formed). Perhaps I could even go so far as saying that "T<'v1> and T<'v2> are the same type" (modulo a 'static bound that could provide access to a TypeId) since codegen cannot (soundly) depend on a lifetime parameter.
What makes me so cautious is that I know U being a subtype of V and V being a subtype of U do not together imply U = V; in particular, two higher-ranked types without canonical normalizations may be subtypes of each other while being distinct types. Therefore, even if both covariant casts and contravariant casts of U to V are sound, it seems unlikely to generally be sound to cast U to V in an invariant position like &mut U, as they could be distinguished by their TypeIds. However, as the problem in #97156 could be seen as the compiler effectively transmuting a private field and/or transmuting a struct with private fields with safety invariants... maybe it'd still be sound to transmute any public &mut U value to &mut V (and other transmutes of a publicly-reachable U to V in invariant positions) when U and V are subtypes of each other? I don't know if there's any sound code capable of escalating that to UB. However, without for<T> binders I don't think it's useful (even if sound). Someday, if for<T> binders are possible, I might revisit that thought.
In any case, that concern about higher-ranked types shouldn't apply to two types which differ only in a lifetime parameter. Am I missing anything that would make transmuting &'a mut T<'v1> to &'a mut T<'v2> unsound (when T<'v1> can be soundly transmuted to or from T<'v2> in both covariant and contravariant positions)?
Maybe, in some future version of Rust, it'd be nice to have something similar to unsafe impl Send for _ but for unsafely asserting that covariant (or contravariant) casts of a parameter are sound. See also Manual variance unsafe escape hatch? - language design - Rust Internals. We already stabilized unsafe attributes, so I think something like struct Foo<#[unsafe(covariant)] 'varying, ..> { .. } would be nice to have at least for lifetime parameters; that is, effectively, what variance-family would implement (modulo support for more than one lifetime with unsafe variance, which, for ease of implementation, variance-family will not include).
I don't think it's critical, though, as absent more support for type constructors or higher-ranked types and a way to require that a type constructor is covariant/contravariant/bivariant in its parameters, my use case(s) for variance-family will still need custom traits. Support for manually-proven / unsafely-asserted variance beyond the variance proven by the compiler is merely a small detail on top of those traits.
1 post - 1 participant
🏷️ Rust_feed