Pre-RFC: Marker types for making parameters invariant

libs
1

Sometimes one wants to explicitly make a lifetime parameter of a struct invariant, meaning that it allows no subtyping at all. For example, this is needed when using the “generative lifetime” trick, and sometimes it is also done for future-compatibility reasons. However, since variance is inferred in Rust, expressing invariance can get quite awkward. A common pattern I have seen is to add

  _marker: PhantomData<&'a mut &'a ()> // the T in &mut T is invariant

or

  _marker: PhantomData<fn(&'a ()) -> &'a ()> // both covariant and contravariant occurrence -> invariant

or

  _marker: PhantomData<Cell<&'a ()>> // the T in Cell<T> is invariant (this also kills `Sync`)

but all of these are far from self-explaining. It turns out even seasoned Rust programmers can get this wrong (in that case &'a mut () was used, which however does not make 'a invariant).
(EDIT: Turns out I misinterpreted their intent, and the lifetime was not meant to be invariant.)

So I propose that we add two marker types to the standard library:

pub struct Invariant<T: ?Sized>(pub PhantomData<fn(Box<T>) -> Box<T>);
pub struct InvariantLifetime<'a>(pub Invariant<&'a ()>);

// both have trivial constructors

that can be used in situations like the above. I have not seen an example where a type parameter (as opposed to a lifetime parameter) needs to be invariant, but that is an obvious extension so I included it.

The generative-lifetime-based bounds check already defines a type Id for this purpose, demonstrating that this kind of marker type is useful. It (a) removes the risk of accidentally having the wrong variance due to a typo, and (b) expresses the intent much more clearly and hence does not need a comment explaining how this achieves invariance.

Other languages such as Scala have explicit variance annotations. Rust decided against that. This proposal does not change that decision, but it provides a way for programmers to more explicitly express variance when needed without requiring new language features.

An obvious future extension of this proposal is to also have Covariant and Contravariant types, but I have not yet seen an example where one would actually want that. Also, adding a _marker: Covarant<T> does not mean the type is actually covariant, it just means it is no more than covariant:

struct WhatIsThis<T> {
  _marker1: Covariant<T>,
  _marker2: Contravariant<T>,
}

This type is neither covariant nor contravariant – it is actually invariant. Covariant sounds like it makes a positive statement (“this type is covariant”), which is not something we can realize with marker types (that can only add new constraints). In contrast, Invariant is actually a negative statement (“this type is neither covariant nor contravariant”) and as such can be realized by marker types. So, Covariant and Contravariant marker types have a much more confusing semantics than Invariant and they seem to be much less needed. Hence I think we should not add them at this point.

What do you think, does this make sense? Is the standard library the right place for such marker types?

10 Likes
2

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

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

This seems like a reasonable sane idea… I think it also kills the idea of adding a keyword phantom or similar to be able to write

struct K<T> {
  phantom: T, 
}

to replace PhantomData altogether.

I have to wonder, though, given the proliferation of such ZST marker types, I have to wonder if introducing _ as a replacement for _markern fields is worth it. Simple sketch:

  • _: T becomes a syntactically valid field declaration.
  • _ can be repeated, can only have ZST, !Drop type, cannot be initialized in struct-literal syntax, cannot be pattern matched on, and cannot be accessed with a dot. The last four properties ensure that it can be repeated.
  • The containing struct is dropcked as if it owned a T.
  • Silly corner cases like "_ should obviously not have a visibility modifier" are straightforward afaict. Maybe _: T should be a separate syntax production to emphasize that it is an extremely fake field.
6 Likes
4

Should be no drop glue not !Drop,

struct Foo;

struct Bar(Foo);

impl Drop for Foo { ... }

Here Bar: !Drop but it still has drop glue.

1 Like
5

Yes, that. Transitively !Drop.

6

Yep, I can imagine, in a fashion similar to PhantomPinned, having the following:

mod marker {
    struct PhantomData<T> { // ...

    struct PhantomPinned;
    impl !UnPin for PhantomPinned {}

    struct PhantomNotSync; // or type PhantomNotSync = PhantomData<Cell<()>>;
    impl !Sync for PhantomNotSync {}

    struct PhantomNotSend;
    impl !Send for PhantomNotSend {}

    // EDIT: &'static mut T requires T : 'static as @RalfJung pointed out 
    type PhantomInvariant<T> = PhantomData<fn(Box<T>) -> Box<T>>;

    type PhantomInvariantLifetime<'a> = PhantomInvariant<&'a ()>;
}

However, I have found that expressing the invariants is easier when reasoning about the kind of access we have.; if, for instance, we had something along the lines of:

type UniqueIdMarker = core::marker::PhantomData<(/* redacted */)>;

struct UniqueId {
    id: usize,
    marker: UniqueIdMarker,
}

use ::std::cell::Cell;
type StaticCounter = Cell<usize>;

impl UniqueId {
    fn new () -> Self
    {
        thread_local! {
            static COUNTER: StaticCounter = Cell::new(0);
        }
        let current = COUNTER.with(Cell::get);
        COUNTER.with(|slf| slf.set(
            current
                .checked_add(1)
                .expect("UniqueId overflow")
        ));
        UniqueId {
            id: current,
            marker: Default::default(),
        }
    }
}

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. Thus:

type UniqueIdMarker = core::marker::PhantomData<&'static StaticCounter>;
// (Hence !Send and !Sync)

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

This is why, for instance, PhantomContravariant should not exist (the only case where it is needed is for a callback argument, in which case PhantomData<fn(T)> (or fn(Box<T>) if T : ?Sized) expresses the intent much more clearly).

7

For historical context, similar marker types existed before Rust 1.0 but were removed as part of RFC 738:

  • Revamp the variance markers to make them more intuitive and less numerous. In fact, there are only two: PhantomData and PhantomFn .

The old marker types were different from the ones proposed here: The old ones were each separate lang items, while the new ones would all be built on top of PhantomData.

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.

3 Likes
8

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

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

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.

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

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

10

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

1 Like
11

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.

1 Like
12

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.

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.

1 Like
13

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.

1 Like
14

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.

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.

8 Likes
15

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

1 Like
16

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.

17

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

1 Like
18

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”.

19

I think we can have better than that:

  1. Introduce value inference with _ for all singleton types (~ZSTs where all fields (if any) are visible and the type is not #[non_exhaustive]).
  2. Introduce default field values, e.g.
    struct Foo<T> { _marker: core::marker::PhantomData<T> = _ }
    Now you can say Foo { .. } to make one.
  3. 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)

6 Likes
20

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.