Pre-RFC: Marker types for making parameters invariant

[RalfJung]

Turns out I was wrong assuming the Context type I quoted before was meant to make the lifetime invariant. I misinterpreted the PhantomData (and I don’t understand its purpose, but that a separate topic.)

I probably misunderstand, but wouldn’t negative terminology accurately express the constraint(s)?

struct WhatIsThis<T> {
  _marker1: NotContravariant<T>,
  _marker2: NotCovariant<T>,
}

That would be accurate, but really weird. In my experience this not how people think when designing such types.

@dhm

   type PhantomInvariant<T> = PhantomData<&'static mut T>;

This does not work because it requires T: 'static. Also, type aliases are strictly weaker than newtypes: they are structural, not nominal; a lifetime used here might actually be subject to subtyping when subject to type inference. (Thanks to @eddyb for reminding me of this.)

What is the right Send / Sync property of our UniqueId struct? We could think a lot about this, or just realise that by using a static we are effectively holding a shared (zero-sized) reference to the counter.

[…]

No need to think in terms of PhantomNotSend and/or PhantomNotSync , which could become overly strict if we changed StaticCounter to AtomicUsize , for instance.

Sometimes, that is the right abstraction. But sometimes, you really want to be sure that a parameter is invariant, and the question of what data is “owned” makes no sense.

Admittedly, I have only seen this for lifetimes.

[Centril]

Admittedly, I have only seen this for lifetimes.

struct Id<A: ?Sized, B: ?Sized>(PhantomData<(fn(A) -> A, fn(B) -> B)>);

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=64c30c6108f3065e6ac5d608b173baa9

(Well… this eventually boils down to lifetimes since all subtyping in Rust does…)

[RalfJung]

@Centril I gave another version of this above. I was not saying that I am not sure how to do this; I was just saying that I have not seen a use for it.

EDIT: Centril explained in private conversation that this was meant to be the equality type, used to witness that two types are equal – which needs to be invariant, of course.

[vorner]

I’m in favor of adding these new marker types, because (contrary to RFC 738) I find them more intuitive than using PhantomData directly. And as they are wrappers around PhantomData , they preserve the underlying simplicity of the implementation, adding no new lang items.

Can a crate do that instead of std?

As for myself, I find it more intuitive to write PhantomData<fn() -> T>, because my struct is an iterator that spits Ts instead of learning all the details and names for variances.

[RalfJung]

Can a crate do that instead of std?

Sure, but it seems unlikely someone is going to add a dependency for one type. Also, a big problem here is making people even aware that they have to look for this.

As for myself, I find it more intuitive to write PhantomData<fn() -> T> , because my struct is an iterator that spits T s instead of learning all the details and names for variances.

That’s anyway covariance and not invariance you are declaring here. I am not saying you should change your code, I am just saying there are cases where you want to be sure your parameters are invariant, and then you should have a clear, correct and concise way of saying that.

[vorner]

That’s anyway covariance and not invariance you are declaring here. I am not saying you should change your code, I am just saying there are cases where you want to be sure your parameters are invariant, and then you should have a clear, correct and concise way of saying that.

If there’s a way to state invariance, then all the others should have a way too.

My problem with stating Invariant<T> is if I didn’t study type theory I have no clue what the hell happens there when reading the code. Invariant is likely to be a foreing terminology for a lot of people. On the other hand, PhantomData<fn(T) -> T> gives at least a hint and you can figure out how the lifetimes need to behave just out of that.

[RalfJung]

If there’s a way to state invariance, then all the others should have a way too.

I sympathize with this, but (a) I do not know of a single example where this would be needed, and (b) it is not possible with a library-only extension. I think these are strong arguments in favor of having Invariance and not the others.

They also play a somewhat different role, so why it seems there is a symmetry being broken here, that is not really the case. When defining a type equipped with extra invariants for the purpose of unsafe code, you have a proof obligation to show that the invariant respects the variance(s) of the type parameters. Adding Invariant is a way to remove (or weaken) proof obligations. In contrast, adding Covariant would be adding a proof obligation.

It’s a bit like how we can make a type non-Copy by not doing impl Copy, but we cannot “force” a type to be Copy. We can opt-out of extra properties, but we don’t have a way to claim extra properties that are in contradiction with what the compiler inferred.

On the other hand, PhantomData<fn(T) -> T> gives at least a hint and you can figure out how the lifetimes need to behave just out of that.

I cannot imagine how seeing a &'a mut &'a () in something like this is going to teach someone an intuitive notion of the concept of invariance, to the extent that they will be able to understand why this is needed here. In contrast, with a more explicit marker like Invarinace, they can go read the docs for that type which will teach them what this is and why it is needed. So having a more explicit type is IMO better for reading the code even for people that haven’t understood the concept of (in)variance yet.

And it is certainly better for people that are experienced enough to be able to write or review that kind of code, which arguably is at least as important of a audience for this code than less experienced developers reading very advanced code with the goal of understanding it better. (I’d argue a guide is better suited for teaching such concepts than just diving into some crazy complicated examples.) In fact, that code already uses the notion of invariance to explain what is going on. People writing such code already think in these terms, we just currently don’t offer them the right vocabulary.

Notice than an understanding of variance is requried for some kinds of unsafe code, and we cannot work around that by pretending it isn’t the case. There’s a reason that the Nomicon has a long section on this topic. Complex topics don’t become easier by sweeping them under the rug.

[RalfJung]

@eddyb you wrote

Part of it is that I saw someone do this recently:

type Invariant<'a> = PhantomData<fn(&'a ()) -> &'a ()>;

And, that’s not actually invariant.

I thought I had understood how this can be a problem, but I realized I did not. Could you elaborate?

[eddyb]

The alias will cause invariance when used as the type of a field, so that is thankfully not a concern.

But if you’re experimenting with it elsewhere, to test what is allowed and what isn’t, you might find some weird examples that differ from how it behaves once put in a struct.

[RalfJung]

Could you give an example? I tried using it for the type of a local variable but could not find an undesired interaction.

[dhm]

While waiting for @eddyb’s counter-example, I can already see another reason against type aliases for the markers: while looking at the error messages of this example, we get:

• type aliases (debug playground)

  note: expected type `std::marker::PhantomData<fn(std::boxed::Box<&'short ()>) -> std::boxed::Box<&'short ()>>`
            found type `std::marker::PhantomData<fn(std::boxed::Box<&'long ()>) -> std::boxed::Box<&'long ()>>`
  

• Newtypes (release playground)

  note: expected type `std::marker::InvariantLifetime<'short>`
            found type `std::marker::InvariantLifetime<'long>`
  

I don’t know how it pans out accross crates, though.

Remains, however, the question of using newtypes based on PhantomData (more elegant, but would require using constructors to “instanciate” them instead of being able to just use “unit struct literals”: it would thus be inconsistent with PhantomData), vs defining and using new #[lang]s and unit structs.

So it seems we can’t have them all: nice error messages, not defining new lang items, and being able to instanciate these marker structs with “unit struct literals”.

[Centril]

So it seems we can’t have them all: nice error messages, not defining new lang items, and being able to instanciate these marker structs with “unit struct literals”.

I think we can have better than that:

0. Introduce value inference with _ for all singleton types (~ZSTs where all fields (if any) are visible and the type is not #[non_exhaustive]).
1. Introduce default field values, e.g.

   struct Foo<T> { _marker: core::marker::PhantomData<T> = _ }
   

   Now you can say Foo { .. } to make one.
2. Define:

   pub struct Invariant<T: ?Sized>(pub PhantomData<fn(Box<T>) -> Box<T>);
   pub struct InvariantLifetime<'a>(pub Invariant<&'a ()>);
   
   pub struct MyType<'a> {
       field: u8,
       _marker: InvariantLifetime<'a> = _
   }
   
   fn make<'a>() -> MyType<'a> { MyType { field: 0, .. } }
   
   // Elaborates to:
   fn make<'a>() -> MyType { MyType { field: 0, _marker: _ } }
   fn make<'a>() -> MyType { MyType { field: 0, _marker: InvariantLifetime(_) } }
   fn make<'a>() -> MyType {
       MyType { field: 0, _marker: InvariantLifetime(Invariant(_))
   }
   fn make<'a>() -> MyType {
       MyType { field: 0, _marker: InvariantLifetime(Invariant(PhantomData)) }
   }
   

(+ this works well for many other purposes also)

[eddyb]

I am not at my computer right now, but for variance you probably always want to use a function to check “can values of this type be used as this other type?”.

I just sketched a quick example:

// All the same if you wrap in PhantomData or not.
type L2<'a, 'b> = fn(&'a ()) -> &'b ();
fn foo<'a>(x: L2<'a, 'static>) -> L2<'static, 'a> {
    x
}
fn bar<'a: 'b, 'b>(x: L2<'a, 'a>) -> L2<'static, 'b> {
    x
}

This compiles, which shows L2<'a, 'a> (aka the InvariantLifetime<'a> type alias) is not truly invariant, just covariant+contravariant, separately.

They only become combined once placed in an ADT, and only because our generic system doesn’t support specifying/inferring both covariant and contravariant versions of one generic paramter (this may be a feature of some typesystems but I am not sure at the moment) - which you can always do manually by having more generic parameters.

Whereas *mut T and &mut T are primitively invariant over T (until we get a way to specify the two types separately, if ever - kind of like the generic ADT situation!)

Anyway, I don’t have a strong preference, as long as it’s a newtype wrapper with a private PhantomData field.

[dhm]

Some remarks:

1. This behaves the same with newtypes;

2. Given that @RalfJung’s examples used a single lifetime parameter in both non-covariant (arg spot) and non-contravariant (return type) spot, doesn’t it imply invariance? The examples you gave used two distinct lifetimes parameters ('a and 'b) which showed indeed that in that case each parameter can have its own variance rules;

3. *mut T : !Send + !Sync

   raw pointers are, strictly speaking, marked as thread-unsafe as more of a lint

   Hence using *mut T over fn(Box<T>)-> Box<T> would require adding:

   unsafe impl<T : ?Sized> Send for PhantomInvariant<T> {}
   unsafe impl<T : ?Sized> Sync for PhantomInvariant<T> {}
   

   (Which is not a bad thing per se, specially if the non-covariant + non-contravariant stuff somehow turned out to not always imply invariance)

4. &'_ mut T requires having a lifetime “outlived” by T, which is not possible if we want our PhantomInvariant to have only one generic unconstrained parameter T (unless we had some lifetime literal for that, e.g. an 'empty/'nil lifetime).

[ExpHP]

Note that _ expressions are also a desirable feature for destructuring assignment, and I’m not sure how compatible these two different meanings are for it.

let x;
(x, _) = func();

At first glance I don’t see any serious conflicts between the two meanings (the meaning proposed here could always be suppressed in the LHS of an assignment), but I’ve seen more surprising conflicts in the past.

What might be a simpler solution (a libs solution rather than a lang solution) is ConstDefault or <T: const Default>, possibly reexported as a generic const.

[drXor]

Actually, I take this idea back. If we’re going to give _: T in structs a magic meaning, then it should behave exactly like _marker: PhantomData<T> behaves today, except as before

• _ cannot be initialized in struct expressions or extracted in struct patterns, or accessed with a dot.
• _ can be repeated.

But really it feels silly to leave out tuple structs at this point, so maybe we should just introduce the syntax struct K { phantom T, u: U } (note: no colon), where phantom T is the same as _: T above, except struct K(phantom T); is now reasonable, too. (Syntactically it’s something like a visibility?) PhantomData is no longer a lang item and is instead defined as struct PhantomData<T>(phantom T);

Bonus extra-silly footgunny version: introduce the phantom visibility, introduce _ as a valid field name (with the semantics of not-accessible-and-no-drop-glue, behaving like a inaccessible [u8; size_of::<T>()]; you could now instead define PhantomData as

struct Phantom<T> {
  phantom _: T,
}

As a bonus, you get a slightly cleaner way to play stupid games with transmute

// Must fit in %eax for the purposes of sysexit
#[repr(packed)]
struct SyscallErrorPadded {
  inner_err: Option<SyscallError>,
  _: [u8; size_of::<u32>() - size_of::<SyscallError>()],
}
// ...
asm!("sysexit" :: "{eax}"(transmute::<_, u32>(SyscallErrorPadded{ inner_err: err }) ));

[TimDiekmann]

I really like the idea of having such types in the core library.

Personally I have those typedefs:

pub type PhantomVariant<T> = PhantomData<fn() -> T>;
pub type PhantomInvariant<T> = PhantomData<fn(T) -> T>;
pub type PhantomContravariant<T> = PhantomData<fn(T)>;
pub type LifetimeVariant<'a> = PhantomData<&'a ()>;
pub type LifetimeInvariant<'a> = PhantomData<&'a mut ()>;

using type instead of a newtype has the huge advantage in initializing a struct: _marker: PhantomData, which is much more comfortable than writing PhantomContravariant::default()

[dhm]

I really like the idea of having such types in the core library.

Personally I have those typedefs:

pub type PhantomVariant<T> = PhantomData<fn() -> T>;
pub type PhantomInvariant<T> = PhantomData<fn(T) -> T>;
pub type PhantomContravariant<T> = PhantomData<fn(T)>;
pub type LifetimeVariant<'a> = PhantomData<&'a ()>;
pub type LifetimeInvariant<'a> = PhantomData<&'a mut ()>;

using type instead of a newtype has the huge advantage in initializing a struct: _marker: PhantomData , which is much more comfortable than writing PhantomContravariant::default()

Well, you are then indeed a good example of the OP’s point: your LifetimeInvariant definition is wrong! (and your other definitions require that T be Sized, but that’s acceptable for custom typedefs, given the unlikelyhood of using these type aliases with DSTs).

[TimDiekmann]

Well, you are then indeed a good example of the OP’s point: your LifetimeInvariant definition is wrong! (and your other definitions require that T be Sized , but that’s acceptable for custom typedefs, given the unlikelyhood of using these type aliases with DSTs).

Then I’m glad I posted this!

[Yato]

For reference LifetimeInvariant would be:

pub type LifetimeInvariant<'a> = PhantomData<&'a mut &'a ()>;

Because the T in &mut T is invariant.