Manual variance unsafe escape hatch?

language design
1

Currently, rust determines the variance (covariant/contravariant/invariant) of a type based on its contents. It is possible to make a type "less variant" by adding a PhantomData field.

However, there is no way to make a type "more variant". For example, a type that contains an invariant field can't be made to be covariant. One use case would be a conceptually-immutable container that lazily populates its contents as they're accessed. Such a container might be internally implemented as a Mutex (which is invariant), but the container could be soundly made covariant.

What if we had an unsafe way to forcibly declare a type to be a certain variant? Maybe something like a NoLifetimes unsafe wrapper type, similar to MaybeUninit and ManuallyDrop. The way it would work is that NoLifetimes<T> would be considered the same type as NoLifetimes<U> iff T and U are the same type when lifetimes are ignored. To use NoLifeTimes, a struct would put its data inside the NoLifetimes, wrapper, and have a PhantomData field that explicitly declares the desired variance.

Thoughts?

2

I can’t help but imagine what kind of language features would be needed to make this use-case safely possible… so here we go (and sorry if the reply might be a touch off-topic):

So for lifetime, I’m imagining a feature of “existential types” would be useful, and feasible (“relatively” straightforwardly) as lifetimes don’t influence how the type is represented.

So one could imagine some syntax for this like

struct Foo<'a><exists 'b: 'a>(Box<dyn Fn() -> Bar<'b>>, OnceCell<Bar<'b>>);

and then you could hide an invariant lifetime ('b) in this type with only a covariant lifetime 'a externally visible. Of course, the main difficulty is how exactly accessing the contents of this is type-checked, but generally, something like

let foo: Foo<'a> = …;

use_value(&foo.0, &foo.1);

would need to be checked so that use_value can generically work with any type Foo<'b> with 'b: 'a.

Such a thing is by the way already possibly to pull off, but inefficiently (via trait objects) and unergonomically.

However, to make this work with more than just lifetimes, one would need to think bigger. Let’s replace 'b: 'a with two types T :<: U (where “:<:” shall mean “subtype”), then one could imagine something like

struct Foo<U><exists T :<: U>(Box<dyn Fn() -> T>, OnceCell<T>);

making Foo<U> covariant again, despite of the contained Cell.

Except now… in order to access the contents, we need code that’s generic over types T that are subtypes of U. Worse it needs to be “polymorphic”[1] (i.e. generic without monomorphization) because this appears in a context where we can no longer have monomorphization on T. (By the way, there do exist types that are subtypes of one another but have different TypeId and monomorphization and everything, like Box<dyn for<'a> Fn(&'a ()) -> &'a str> which is a subtype of Box<dyn Fn(&'static ()) -> &'static str>.)

So we have a language feature that requires more complicated language features to even make sense… but to me it all seems – at least potentially / in principle – feasible, and it would mean that covariant, lazily initialized types might be possible to offer without unsafe.

Let me get a bit more closely back on topic… as I mentioned above, subtyping & variance in Rust does not just cover types differing in lifetimes. So if you want full covariance, “NoLifetimes” as described, in terms of “lifetimes are ignored”, is insufficient:

  1. such a “polimorphism” language feature itself is a very deep rabbit hole ↩︎

1 Like
3

Your idea of allowing this via safe code seems complicated, sounds about right. But I don't understand how this makes the NoLifetimes idea not work? HRTBs (for<'a>) should just be discarded inside NoLifetimes. And getting back covariance from "no-variance" would just be as easy as adding a PhantomData.

The Foo struct you have, with my NoLifetimes idea, would look like this:

struct Foo<T>(NoLifetimes<Mutex<(Box<dyn Fn() -> T>, OnceCell<T>)>>, PhantomData<T>);

A struct Foo<T> would be coercible to the struct Foo<U> whenever U is a subtype of T. And since subtyping doesn't affect non-lifetime portions of types, there would be no issues coercing the NoLifetimes inside to the correct type, since they're considered to be the exact same type. Whatever machinery already works for PhantomData in handling HRTBs would also work in this scenario.

4

The lack of variance is invariance, which is trivially achievable (the T in &mut T). Unconstrained variance is bivariance.

I actually hit a case that would've liked access to bivariance a bit back: channels. The sending side of a channel is similar to fn(T) and could be contravariant, and the receiving side is similar to fn() -> T and could be covariant. However, since the implementation typically uses Arc<Shared>, channels usually end up invariant. (Note: if dropping the sender can potentially access/drop T, it does need to be invariant; the impl synchronization would need to be careful to prevent this.)

If indirection before sized T is involved, variance can be manipulated by storing a type-erased pointer instead. If no indirection is present, MaybeUninit<UnsafeCell<[u8; {size_of::<T>()}]>> could provide storage space, although I don't know of a non-covariant method of correctly aligning it; some sort of UnsafelyBivariant wrapper type would indeed probably be required.

I think the most likely avenue toward this functionality is by applying the annotation that will hopefully eventually be available for controlling the (required) variance of trait generics and associated types.

The fact that the subtyping relationship doesn't preserve TypeId is already the cause of at least one I-unsound issue, and will surely result in difficulties in extending the capability to force variance in unsafe contexts.

1 Like
5

Just a passing note; I recently found out that what is called "bivariance" in rustc is not "co-and-contra-variant", but rather completely unconstrained.

Last paragraph here, linking to this example.

3 Likes
6

By "no-variance", I meant "completely unconstrained variance (ignore all lifetimes)". I went with that instead of bivariance (covariance or contravariance) because bivariance is not transitive, and I don't know how that would work.

Your use case with channels is a good one. Nice to know that a variance escape hatch would have more general use cases than I thought.

Your issue with subtyping not preserving TypeId is a huge issue though. With that in mind, the NoLifetimes wrapper idea doesn't work.

I'll have to think about how a manually-specified variance attribute would work, or if it works at all. Anyone have any ideas?

7

Yeah, it's a bit more complicated than purely "variant in both directions," but the example with the type parameter only used in an associated type equality bound is wild. The usual definitions for some type constructor W are

  • covariant: A :<: B => W<A> :<: W<B>
  • contravariant: A :<: B => W<B> :<: W<A>
  • bivariant: A :<: B => W<A> :=: W<B> (both covariance and contravariance apply)
  • variant: covariant, contravariant, and/or bivariant
  • invariant or nonvariant: not variant

In conclusion: firm agree that naming is hard

2 Likes
8

The linked example is a bug which is being fixed. See here

9

Actually... I found that there already exists a case where equal types can have different TypeIds. I'm very very confused on what's going on.

10

You should read all of that issue 56105 you cited. The "will be removed" is a lie; the plan is to accept approximately all code that triggers the lint, including that example. See here as well.

The goal of PR 118247 (which is where the comment I linked to is from) is to fix issue 97156 (which might be the issue @CAD97 was referring to) by no longer considering types to be equal if they are subtypes of one another.

1 Like
11

It’s not extremely wild IMO. I could imagine a situation where something like ! (never type) would be subtype of every other type, with the reasoning that ! can coerce into any other type.

(Okay it actually I can think of – probably multiple – technical reasons why it cannot just work like that, but anyways…)

If we had the situation that all types have a common subtype like ! (of if we had a situation of a common supertype, though that seems even harder in Rust[1]), then bivariance as you define it would mean

  • for any type A and any other type B: W<A> :=: W<B>

because transitively:

  • ! :<: A gives W<!> :=: W<A>, and
  • ! :<: B gives W<!> :=: W<B>, so
  • ! :<: A and ! :<: B gives W<A> :=: W<!> :=: W<B>

and the assumption that ! is a common subtype ofall types (so ! :<: A and ! :<: B are always true) thus gives

  • for any type A and any other type B: W<A> :=: W<B>

as promised.

(I suppose, the situation also doesn’t quite work out if W requires trait bounds on its parameter that ! doesn’t fulfill. Thus shouldn’t take away from the general idea though: transitivity makes bivariance way more powerful than just “covariant or contravariant both works”, as rather “the transitive closure of covariance and contravariance” needs to be considered.)

  1. whereas other languages, especially object oriented ones commonly have one base-class that is a super-class of all other classes; so for such languages “bivariance” would necessarily automatically mean “in this parameter, any class can coerce to any other class”, by the transitivity argument laid out below ↩︎

2 Likes
12

FWIW I initially misread the example a bit and thought it more wild than it is. The example creates a type parameter only constrained by an associated type equality bound projected from a separate type parameter, then uses contravariance on that parameter been two types with distinct type identity to coerce the loosely bound type variable between two unrelated types. Because I'd never before seen a type variable considered "used" without being covered by the type of a field, I somehow thought it was being "turned bivariant" by the disagreement between the implementation of the "mutually subtypes" and "equivalence" relations. "Activating" the bivariance in this manner does rely on the subtyping relationship crossing impl disjoint boundaries (which is the part I reacted to as wild) and the bivariant behavior just falls from that.

Had the example instead used a different coercion (e.g. unsizing or even !-as-anything) for the "anchor" type to "pivot" the bivariant type parameter it would've been a bit less impactfully wild. But still surprising to my mental typecheck, which wants variance to only apply between types which have a direct ordering relation (and other coercions to be)

Runtime erasure of lifetimes relies on the fact that it is impossible to write two non-overlapping impls for a family of types varrying exclusively in lifetime. (Thus specialization (potentially) on lifetimes being unsound.) My mental typechecker is applying a similar expectation to an informal idea of "variance reachable type families" in general, despite this being incorrect in the face of #97156 or ! as a bottom type.

I guess it comes down to asking if the bivariance relation is transitive. While I agree that in effect it might as well be (that a bottom type makes (transitive) coercion possible) it doesn't seem completely implausible that actual coercion would need to be done in two steps (W<A> -> W<!> -> W<B>) instead of directly. We already have nontransitive coercions (although I think so far all such cases are derivative of type inference limitations and don't apply when all types are known).

Somewhat amusingly (at least to me[1]) is that the "problem" comes out of nominal typing. Lifetimes are entirely structural, so variance works reasonably enough there. It's subtyping that crosses between type names that causes problems[2].

There's also some remnants of Java details itching the back of my mind here, since on the JVM generics are made up and variance is enforced by class cast exception (collections just use Object under the hood because Java didn't have parametric polymorphism initially). Does Java permit unrelated generic downcasting, or is it limited to runtime-enforced-variance upcasts? I legitimately don't recall.

(And an entirely tangential note: while I admit it unlikely, I'd like it if we could get automatically derived impl Trait for ! for object-safe Trait alongside the already present conceptual impl Trait for (dyn '_ + Trait).)

  1. Me, who's been considering abstract properties of structural versus nominal types recently, e.g. that C and C++ have "structurally nominal" types but Rust has "nominally nominal" types, due to how names are differentiated. ↩︎

  2. And which has made me realize I don't know how to model nominal empty types, since I've conceptualized nominal typing as tagging values with the name in order to make typesets disjoint, but empty types have no values to hold that name. Why does that make null as a "bottom value" start to look somewhat reasonable... ↩︎

13

I don't quite understand the entire conversation here. But... would a manual variance attribute be possible? A lazily-initialized immutable value might look like this:

#[unsafe_manual_variance(T = covariant)]
struct Foo<T>(Mutex<(Box<dyn Fn() -> T>, OnceCell<T>)>)

Is there some reason that this wouldn't just work?