rust-lang / rfcs

RFCs for changes to Rust
https://rust-lang.github.io/rfcs/
Apache License 2.0
5.78k stars 1.55k forks source link

[RFC] `core::marker::Freeze` in bounds #3633

Open p-avital opened 1 month ago

p-avital commented 1 month ago

Rendered

RalfJung commented 1 month ago

IIRC @joshlf was also asking about exposing Freeze; maybe they can help provide some more motivating examples. Currently there's only really one. (I don't understand the "key of a map" note, and the RFC doesn't explain it in more than 5 words either.)

clarfonthey commented 1 month ago

The main reason for not stabilising Freeze was because it would now add an additional burden for API contracts: adding interior mutability could be considered a breaking change for some APIs, and thus people might want to add "phantom cells" of UnsafeCell<()> inside their types to ensure that they have this option for the future.

I don't think that just stabilising it for bounds affects this concern. The issue isn't the trait itself being exposed in the library, but APIs having to worry about whether they are Freeze or not as an API contract.

RalfJung commented 1 month ago

I don't think that just stabilising it for bounds affects this concern. The issue isn't the trait itself being exposed in the library, but APIs having to worry about whether they are Freeze or not as an API contract.

A bound is exactly what one is worried about here? If one writes a function fn myfunc(x: impl Freeze), then if I pass a value I got some some other crate to myfunc this will work off that type is Freeze -- meaning it's a breaking change for that crate to add non-Freeze fields.

This is exactly the same as Send and Sync. How often to people defensively add PhantomData<*mut ()> to make their type !Semd + !Sync?

Fundamentally there are some things the compiler only lets you do with Freeze types, and people naturally want to do these things in generic code, and they need Freeze bounds for that. I'm honestly surprised that we went so long without allowing these bounds.^^

(Or did I misunderstand what you mean? It sounded a bit like you're saying just stabilizing the bound means we don't have to worry about the concern. But upon re-reading I am less sure.)

The main reason for not stabilising Freeze was because it would now add an additional burden for API contracts

Letting people write unsafe impl Freeze for Type is even worse, given its role in the operational semantics, so I think we disagree on what the main reason was. ;)

joshlf commented 1 month ago

IIRC @joshlf was also asking about exposing Freeze; maybe they can help provide some more motivating examples. Currently there's only really one. (I don't understand the "key of a map" note, and the RFC doesn't explain it in more than 5 words either.)

Sure!

If you want to dive deeper, look at uses of Immutable in zerocopy's 0.8 alpha docs.

On zerocopy stable, we provide traits like FromBytes. T: FromBytes guarantees that transmute::<[u8; size_of::<T>()], T>(bytes) is sound regardless of the value of bytes. We also want to support reference transmutations (e.g., &[u8; N] to &T). Reference transmutations are necessarily more restrictive than value transmutations since they must ban interior mutation. For example, &[u8; N] to &Cell<U> is unsound because it would allow the referent bytes to be mutated while a &[u8; N] reference exists referencing the same memory. For this reason, T: FromBytes also requires that T contains no UnsafeCells.

However, this is overly-restrictive. The "no UnsafeCells" requirement is only relevant to reference transmutations, but not to value transmutations. E.g., transmute::<[u8; size_of::<T>()], UnsafeCell<T>>(bytes) can be sound (depending on T), but we can never implement FromBytes for UnsafeCell<T>. Our API supports value transmutations in places like FromBytes::read_from and transmute!. APIs like these are made less powerful because of this restriction.

Another restriction is that some authors want to use FromBytes as a bound to justify their own unsafe code blocks. For example, https://github.com/google/zerocopy/issues/251 was motivated by a user who wanted to derive FromBytes on a type containing an UnsafeCell for this purpose (see the "Motivation" section of that issue; cc @korran).

Our solution in the upcoming zerocopy 0.8 is to add a separate Immutable trait that is semantically very similar to Freeze*. We require T: Immutable where reference transmutations are happening, but don't require it where mutable reference transmutations (e.g. &mut [u8; N] to &mut T) or value transmutations are happening.


* Currently, Immutable bans UnsafeCells recursively, even via indirection. We will likely lift this restriction, at which point Immutable will be semantically identical to Freeze.

clarfonthey commented 1 month ago

Letting people write unsafe impl Freeze for Type is even worse, given its role in the operational semantics, so I think we disagree on what the main reason was. ;)

I should clarify, what I meant here was the adding of stuff like UnsafeCell<()> to make your type !Freeze, so that there's the option to add real interior mutability later without breaking existing APIs that rely on the type being Freeze.

Not the ability to make something Freeze despite interior mutability.

zachs18 commented 1 month ago

For another "motivating example", bytemuck is in basically the same position as zerocopy, in that some of the bounds are currently more strict than necessary (discussion). I have a branch with a sketch of bytemuck's API in the presence of core::mem::Freeze. (cc @Lokathor)


One possible alternative that would "work around" the semver issue would be to have Freeze be a "normal" (non-auto) trait that, like Copy, can only be implemented for types where all of their fields are also Freeze. This would require types to "opt-in" to guaranteeing they do not have interior mutability, just like types now have to "opt-in" to being Copyable. I don't necessarily think this option is better than the status quo[^1], but it is something to consider.

[^1]: since Freeze can be somewhat observed on stable via static-promotion, and this would either break that until libraries add impl Freeze for MyPODType, or require a second BikeshedRawFreeze actually-auto-trait as a supertrait of Freeze for the compiler to use for determining static-promotion etc.

RalfJung commented 1 month ago

Yeah that could work -- as you say, the existing Freeze trait has to stay around; we'd also have to make static promotion accept a type that's either AutoFreeze or OptInFreeze for the motivating example to work (which is all about static promotion of data at a generic type).

BurntSushi commented 1 month ago

Thanks for writing this up. I appreciate the effort that went into it and the desire to push things forward.

But... I think this RFC needs a fair bit of work. After reading it, I'm still left with some very fundamental questions (and I expect these to be answered in the RFC):

joshlf commented 1 month ago
  • I don't understand why we also aren't trying to stabilize unsafe impl Freeze.

IIUC, we couldn't do that today since Freeze promises that a type contains no UnsafeCells. That property is entirely visible to the compiler - either you have no UnsafeCells, in which case the compiler knows your type is Freeze, or you have some, in which case it would be unsound to implement Freeze for your type. We'd need to relax it to simply say "doesn't permit interior mutation" or something to that effect, in which case it'd be more about whether any of your public API permits interior mutation (so it's more of a runtime property and less of a type property).

If we decide to keep it a type property - ie, the absence of UnsafeCells - then we could do impl Freeze rather than unsafe impl Freeze per @zachs18:

One possible alternative that would "work around" the semver issue would be to have Freeze be a "normal" (non-auto) trait that, like Copy, can only be implemented for types where all of their fields are also Freeze. This would require types to "opt-in" to guaranteeing they do not have interior mutability, just like types now have to "opt-in" to being Copyable. I don't necessarily think this option is better than the status quo1, but it is something to consider.

Footnotes

  1. since Freeze can be somewhat observed on stable via static-promotion, and this would either break that until libraries add impl Freeze for MyPODType, or require a second BikeshedRawFreeze actually-auto-trait as a supertrait of Freeze for the compiler to use for determining static-promotion etc.
RalfJung commented 1 month ago

Freeze is used by the compiler (codegen, const-check) and Miri to determine whether a type allows shared mutation. We definitely don't want to allow people to disallow shared mutation on their UnsafeCell-carrying types -- I don't see when that would ever be useful, it opens so many questions, and it's not what anyone asked for. (That makes Freeze quite different from Send and Sync: Send and Sync are not used by codegen or Miri to do any optimizations, they are basically entirely library concepts with just a bit of involvement in the compiler to handle static. Freeze is very much a language/opsem concept.)

So if we want to expose the Freeze trait that exists, that decides for codegen and Miri and const-checking whether there's any interior mutability, then we can't allow impls.

ChayimFriedman2 commented 1 month ago

@joshlf For the purpose of zerocopy (and bytemuck), what advantages does exposing Freeze brings over a custom trait? You will have to derive it anyway because you have other required traits, right?

zachs18 commented 1 month ago

For the purpose of zerocopy (and bytemuck), what advantages does exposing Freeze brings over a custom trait?

IMO the main advantage is that Freeze can be definitively checked by the compiler. Under the current Freeze as an auto trait, no derives or impls are needed (or possible) for it since it is automatically implemented by the compiler when it can be. [^1]

An additional advantage is that there would be only one trait to encode the invariant. bytemuck and zerocopy (and any other cratr) could each implement their own Immutable trait, but with Freeze in the stdlib this would not be necessary.

You will have to derive it anyway because you have other required traits, right?

For my sketch of bytemuck's API with Freeze, Freeze is simply added as an additional bound on the functions where it is needed, it is not a supertrait or subtrait of any bytemuck trait itself.

[^1]: Also, even a hypothetical Copy-like "opt-in-but-still-validated-impls" version of Freeze would still be easier to correctly implement since an incorrect implementation simply wouldn't compile (just like impl Copy for struct Wrapper(String) doesn't compile today).

joshlf commented 1 month ago

@joshlf For the purpose of zerocopy (and bytemuck), what advantages does exposing Freeze brings over a custom trait? You will have to derive it anyway because you have other required traits, right?

The most important reason is that the compiler can see into the internals of types in the standard library. For example, I filed this extremely silly issue because there's technically no guarantee provided to code outside of the standard library that Box<T> doesn't contain any UnsafeCells. That's obviously true, but in order for zerocopy to uphold its soundness policy, we need an explicit guarantee. Such a guarantee would be useful to basically nobody but us. By contrast, Box already implements Freeze, so if we could use Freeze directly, we wouldn't have to quibble about things like that. Here's another PR that would be at least partially obviated by Freeze.

Besides that, here are some other reasons:

p-avital commented 1 month ago

Thanks to everyone taking an interest in this RFC.

First, a quick apology for it starting up so half-assed, I clearly underestimated the task. I started this RFC as a knee-jerk reaction to 1.78 merging the breaking change the RFC mentions without providing a way for const references to generics to exist.

I'm still committed to getting this to move forward, but I have limited availability for the next 2 weeks, so please bear with me as I rewrite this entire thing to the standard I should have started it with.

I would really appreciate getting some early feedback on the direction people around here would like to see this RFC take regarding:

Sorry for my high latency for the beginnings of this RFC. I really appreciate all the feedback you can give, and would like to mention that PRs to this PR's branch are very welcome :)

RalfJung commented 1 month ago

@p-avital happy to hear that you're not discouraged by all the extra work we're throwing your way. :)

core::marker::Freeze only accounts for "local" immutability. This is good enough for certain purposes (such as static promotion), but not for stuff like maps that would like to ensure their keys are totally immutable.

Even if Freeze was recursive, types can use raw pointers or global static to implement shared mutable state. So I don't think this RFC should try to do anything in that direction -- between promotion of generic consts, zerocopy, and bytemuck we have three users that all only care about "shallow" immutability. A map can use an unsafe trait PartialEqPure or so if a proof is required that partial_eq (and/or other functions) are pure.

BurntSushi commented 1 month ago

@p-avital It's hard for me to give you good feedback here because I think I lack a fair bit of context. Most of the discussion (and the RFC itself) seems to be very high context here, and it's context that I don't have.

With that said, I can say that adding a new auto/marker trait is a Very Big Deal. It's not just that "auto traits = bad," but that adding a new one comes with very significant trade offs. That doesn't mean that adding one is impossible, but it does mean, IMO, that adding one needs to come with significant benefits. Or that it's the only path forward for some feature that most everyone deems to be essential.

From the discussion, it sounds like there are alternatives. So those alternatives, at minimum, should be explored.

RalfJung commented 1 month ago

@BurntSushi note that the Freeze marker trait, albeit being unstable, is already a semver hazard. Whenever I have a constant of type T, there are things the compiler will let me do only if T: Freeze. So, while new auto traits are a Very Big Deal, this is not an entirely new auto trait, and it merely extends the existing semver hazard to also affect crates that do not allow creating const values of their type. But any crate that has a const fn new() -> Self already needs to worry about Freeze, in today's Rust.

Here's a demonstration.

BurntSushi commented 1 month ago

@RalfJung Yikes. OK. Thank you for pointing that out. That's exactly the kind of context I was missing.

p-avital commented 1 month ago

Good news! I did find time to rewrite this as a proper RFC. Now ready for the next wave of comments :)

My thanks for all of your in-depth comments which have helped a lot in rewriting this RFC :)

RalfJung commented 1 month ago

(Btw, github supports committing multiple of these proposals into a single commit. That avoids a bunch of notification and commit log spam. You just have to go to the diff view and click "add to batch" on all the proposals you want to include.)

p-avital commented 1 month ago

(Btw, github supports committing multiple of these proposals into a single commit. That avoids a bunch of notification and commit log spam. You just have to go to the diff view and click "add to batch" on all the proposals you want to include.)

Oooh, didn't spot that one, sorry for the noise :(

nikomatsakis commented 1 month ago

I've not read the updated RFC, but I wanted to share a few general thoughts re: semver, opt-in, etc...

First, in terms of semver, there are two mitigations

  1. As @RalfJung pointed out, there is already a semver hazard around freeze-ness, because the compiler requires that types in some contexts are Freeze (even if you don't have a way to name it).
  2. It's already the case today that adding "interior mutability" in the form of a Cell is a breaking change (because Sync); with Freeze, adding a Mutex or AtomicI32 would now be a breaking change in addition -- but note that adding an Arc<Mutex> or Arc<AtomicI32> would not.

In general I feel that the semver rules for Rust are something like: using tree-like ownership with static dispatch is "idiomatic" and the most flexible. Straying from that is a kind of breaking change because some low-level software will stop working. I know that's not what we actually say and it's more complex, but it seems to be true.

I do think it's important that we have (at minimum) a way to opt out from Freeze. For example, I think that Mutex may on some platforms require an allocation, which means that it would be "shallowly Freeze", but it would want to opt-out from that. (There's an interesting interaction with MSRV here, in that older versions compiled with newer compilers cannot opt-out...i.e., if I have version X that uses Freeze, then Freeze is introduced in Rust 1.Y, and in version X.1 I opt-out, code could still have upgraded rust to version 1.Y and used version X of my library, making X.1 a breaking change; annoying).

Another option of course would be to make Freeze be like Copy: opt-in but checked.

I also feel there is a general tension between semver and safety, particularly in the context of systems programming. When you want to be able to do low-level hacks, you often need to rely on certain properties of types (e.g., their size, whether they can have interior mutation, whether they make use of thread-safety) that go beyond the traditional abstraction boundaries we see in other languages -- these boundaries are intentionally intended to obscure exactly what data is accessed and how, but that is precisely the kind of information you need to create these safety abstractions. This is why people used to say that parallelism is "anti-encapsulation". I think this existing semver hazard, which has to do with our ability to put statics into a read-only data section etc, is a similar example.

Overall I think it's important we expose the tools people need to build low-level optimizations. I also think it's important that people are able to check that these low-level optimziations are safe. This is true even if the combination works against semver.

RalfJung commented 1 month ago

I do think it's important that we have (at minimum) a way to opt out from Freeze

So, like a PhantomNotFreeze type?

nikomatsakis commented 1 month ago

So, like a PhantomNotFreeze type?

That would be the obvious way to go that matches precedent. I hope we can shift to negative impls but that's a separate effort.

nikomatsakis commented 1 month ago

I've had some use cases for this, I think in salsa, I have to think about whether shallow- or deep- would've been useful. I suspect shallow is the thing I really need for the same reason as everyone else.

clarfonthey commented 1 month ago

Doesn't UnsafeCell<()> have the same effect as PhantomNotFreeze, admittedly with less ergonomics? Or have I been suggesting that incorrectly so far?

nikomatsakis commented 1 month ago

Reasonable optin for "disable all auto traits", I suppose.

On Wed, May 15, 2024, at 5:51 PM, Clar Fon wrote:

Doesn't UnsafeCell<()> have the same effect as PhantomNotFreeze, admittedly with less ergonomics? Or have I been suggesting that incorrectly so far?

— Reply to this email directly, view it on GitHub https://github.com/rust-lang/rfcs/pull/3633#issuecomment-2113512677, or unsubscribe https://github.com/notifications/unsubscribe-auth/AABF4ZR2IT557Y5X3CJGXD3ZCPKE5AVCNFSM6AAAAABHQ6KFQKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDCMJTGUYTENRXG4. You are receiving this because you commented.Message ID: @.***>

clarfonthey commented 1 month ago

Oh, fair point. I guess that Send and Sync also break with that as well.

RalfJung commented 1 month ago

Doesn't UnsafeCell<()> have the same effect as PhantomNotFreeze, admittedly with less ergonomics? Or have I been suggesting that incorrectly so far?

It currently does, but with some core questions around UnsafeCell still being open, maybe we want to provide something more explicit.

RalfJung commented 1 month ago

Reasonable optin for "disable all auto traits", I suppose.

And also disable inference of variance? Can we then also allow unused type and lifetime parameters, please? ;)

But all of that seems like outside the scope of a Freeze RFC.

RalfJung commented 1 month ago

(moved into the right thread)

nikomatsakis commented 1 month ago

I like the name Immutable. Maybe it will help shift people away from using the term "immutable reference" vs "shared reference". Agreed that the shallow vs deep distinction is potentially confusing, particularly in contrast to Send, and agreed that it is orthogonal.

Message ID: @.***>

p-avital commented 1 month ago

Hello again everyone,

I'm back and ready to keep pushing on this. I've already committed the result of every suggestion that seemed immediately actionable to me.

It appears to me that 2 remaining roadblocks are:

As an aside to maintainers around here, is there a chance we can slip this in 1.79 if we're quick enough about resolving those questions, or is the release cycle already too far gone?

joshlf commented 1 month ago

One remaining question in my mind. I'm not sure whether this would affect the design, but it might.

Do we want to leave open the possibility of implementing Freeze conditional on how many bytes are covered by UnsafeCell, even via generis? Ie:

struct Foo<T>(UnsafeCell<T>);

static_assertions::assert_not_impl_any!(Foo<u8>: Freeze);
static_assertions::assert_impl_all!(Foo<()>: Freeze);

This would make ZST-ness (or "zestiness", as @jswrenn prefers to pronounce it) a semver-visible property, but that's already true for some types (e.g. () is guaranteed to be a ZST). Do we at least want to hold open the possibility of doing this for types whose zestiness is already guaranteed?

Obviously a lot of thorny questions to work out - I'm not talking about working them out here, but just making sure we don't foreclose on the future possibility. Maybe add it to the "future possibilities" section of the RFC.

jswrenn commented 1 month ago

@joshlf, I believe that possibility is permitted. See the reference level explanation's proposal of Freeze's documentation: https://github.com/p-avital/rfcs/blob/stabilize-marker-freeze/text/0000-stabilize-marker-freeze.md#reference-level-explanation

Freeze marks all types that do not contain any un-indirected interior mutability. This means that their byte representation cannot change as long as a reference to them exists.

Note that T: Freeze is a shallow property: T is still allowed to contain interior mutability, provided that it is behind an indirection (such as Box<UnsafeCell<U>>). Notable !Freeze types are UnsafeCell and its safe wrappers such as the types in the cell module, Mutex, and atomics. Any type which contains any one of these without indirection is also !Freeze.

This explanation is phrased in terms of mutability-without-indirection, rather than the presence of absence of Freeze.

That said, the current implementation of Freeze is quite conservative. For instance, it [T; 0] is only Freeze if T: Freeze.

joshlf commented 1 month ago

Yeah, so I think we'd just want to update the proposed doc comment to be more explicit about the fact that T: Freeze does not promise that T contains no UnsafeCell internally, only that it cannot be used to exercise interior mutation. That's the sort of thing that would be very easy to accidentally rely upon if we don't disclaim it loudly.

RalfJung commented 1 month ago

As an aside to maintainers around here, is there a chance we can slip this in 1.79 if we're quick enough about resolving those questions, or is the release cycle already too far gone?

1.79 is in beta and not going to receive any new features. If an implementation of this got merged before June 7th, it would be part of 1.80. But given t-lang capacity and the 10-day FCP period for the RFC, I don't want to raise any false expectations -- that's very unlikely. If it makes it into 1.81 (which branches on July 19th) that would be extremely fast by RFC standards, but we can possibly used the fact that this fixes a regression as an argument for prioritizing this in t-lang discussions. (I can't make that call, I am not on the lang team.)

Rust is moving too fast for some people's liking, but not that fast.

p-avital commented 1 month ago

One remaining question in my mind. I'm not sure whether this would affect the design, but it might.

Do we want to leave open the possibility of implementing Freeze conditional on how many bytes are covered by UnsafeCell, even via generis? Ie:

struct Foo<T>(UnsafeCell<T>);

static_assertions::assert_not_impl_any!(Foo<u8>: Freeze);
static_assertions::assert_impl_all!(Foo<()>: Freeze);

I think it does. I think a nice way to allow for this to fit the RFC nicely would be to:

p-avital commented 1 month ago

Rust is moving too fast for some people's liking, but not that fast.

Bunch of grumps! :smiling_face_with_tear:

If it makes it into 1.81 (which branches on July 19th) that would be extremely fast by RFC standards

So at least 2 more months of sad stabby. Imma push as hard as I can for this to happen without putting a sour taste in t-lang's mouth :)

RalfJung commented 1 month ago

I'm afraid it's going to be more than 2 months -- 1.81 branches on July 19th, i.e. that's when the 6-week beta period starts. It is going to be released on Sep 5th.

I hope this is not too much of a downer, your help here is much appreciated! It's just generally not good idea to rush irreversible decisions that the entire Rust community will have to live with forever.

p-avital commented 1 month ago

I hope this is not too much of a downer, your help here is much appreciated! It's just generally not good idea to rush irreversible decisions that the entire Rust community will have to live with forever.

Honestly, the downer was 1.78; now I'm just fired up to get that situation resolved!

I fully understand wanting to do due diligence on these things, I've been hurt by both ends of the stabilization stick before (looking at you, forever ABI-unstable core::task::Waker because the constructor takes extern "Rust" fns).

But just to keep a sense of urgency: not making it to 1.81 would be a downer :stuck_out_tongue:

As an aside: I've updated the proposal to include PhantomNotFreeze for semver nerds :)

p-avital commented 1 month ago

Hiya @RalfJung (sorry if the ping is a bit cavalier), do you see any work this RFC still needs before it can enter FCP? :)

RalfJung commented 1 month ago

Hiya @RalfJung (sorry if the ping is a bit cavalier), do you see any work this RFC still needs before it can enter FCP? :)

That's a question for t-lang, not for me. :) I have nominated the RFC to be discussed by the lang team.

p-avital commented 3 weeks ago

Hi @RalfJung, sorry for pestering you, any updates on the RFC's status?

Let me know if there's a more appropriate place/person to follow up with on this RFC :)

RalfJung commented 3 weeks ago

It's in the lang team's nomination queue. They probably have several dozen items in that queue so we'll have to see when they get around to discussing this RFC.