Decide on validity for metadata of wide pointer/reference with slice tail

[RalfJung]

This is a part of #166, needed to unblock rust-lang/rust#121965 and rust-lang/rust#116542.

A type T has "slice tail" if it is unsized and its last field (recursively descending through structs/tuples) is of the shape [U]. For such types, we say that

1. The validity invariant of the metadata part of *const T and *mut T is exactly the same as that of usize.
2. The validity invariant of the metadata part of &T and &mut T is that of usize with the further constraint that the total size of a T with that metadata must not exceed isize::MAX.

The representation relation is otherwise that of an integer (so, what happens when the metadata has provenance matches what happens when a usize has provenance -- we haven't decided what exactly that will be, but it should be consistent).

Rationale:

1. We don't have a choice here, as slice_from_raw_parts is a stable safe function that can construct a wide raw slice pointer with an arbitrary value for its metadata.
2. This will allow us to add niches in slice metadata.

I think the only possibly controversial point here is that the validity invariant is not the same for metadata of *const [U] and &[U]. However, given that the validity invariant is already not the same for the data part of these (obviously), maybe that's not so surprising?

I am not including vtables in this as I think we have more discussing to do there.

@rust-lang/opsem what do you think? Any objections to moving to FCP swiftly?

[CAD97]

No objections here and seconded that this is good to FCP yesterday. This may have some interesting implications w.r.t. ptr_metadata (&T needs to logically be different from just (&_, <T as Pointee>::Metadata)), but that doesn't seem like it'd be a fundamental issue.

Most cases that require validity will also retag the reference (thus require dereferencability which implies the same metadata constraints), with the exception being ManuallyDrop IIRC. While the difference existing could be a bit surprising, I don't expect it to cause issues in practice.

[workingjubilee]

Rationale:

1. We don't have a choice here, as slice_from_raw_parts is a stable safe function that can construct a wide raw slice pointer with an arbitrary value for its metadata.

The function could always do a conversion to another metadata format, I suppose.

2. This will allow us to add niches in slice metadata.

But this seems justification enough.

As far as the difference of the validity invariant, I think that it is fine: &Tailed implies that for the metadata size, that data is legible, right? It seems pointers having no equivalent validity invariant on the metadata part necessarily follows from the pointer not carrying an assertion that the pointee is valid, leaving that at the moment of creation. That's basically the same reason why *const T has no niches but &T does.

[RalfJung]

As far as the difference of the validity invariant, I think that it is fine: &Tailed implies that for the metadata size, that data is legible, right? It seems pointers having no equivalent validity invariant on the metadata part necessarily follows from the pointer not carrying an assertion that the pointee is valid, leaving that at the moment of creation. That's basically the same reason why *const T has no niches but &T does.

Kind of... there's the point @CAD97 mentioned about MaybeDangling<&SliceTailed> (assuming an implementation of rust-lang/rfcs#3336), which cancels out dereferenceable but preserves the niche.

But for slices I think that's just fine, with the semantics the way I proposed them above.

[workingjubilee]

Like a very... interesting... spelling of NonNull.

[RalfJung]

Under the above semantics, MaybeDangling<&SliceTailed> would spell: not null, well-aligned, and the metadata is such that the entire type fits in isize::MAX.

[RalfJung]

No objections here and seconded that this is good to FCP yesterday

Let's get the show started, then.
@rfcbot fcp merge

[workingjubilee]

...does rfcbot not listen to this repo?

[RalfJung]

IIRC it doesn't have a hook but instead just checks every few hours or so.

[RalfJung]

However, I thought it did the check every full hour. Maybe the command is wrong. I took it from the docs, but last time I used a different command...
@rfcbot merge

[rfcbot]

Team member @RalfJung has proposed to merge this. The next step is review by the rest of the tagged team members:

• @CAD97
• @JakobDegen
• @RalfJung
• @digama0
• @saethlin

No concerns currently listed.

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[saethlin]

The only crate I'm aware of that tries to violate this requirement is https://crates.io/crates/deepmesa-collections, and that crate tries to do so by calling slice::from_raw_parts, which now contains a runtime UB check. Thus the crate's test suite does not pass on stable and it has no published dependents (aside from its own workspace members).

[saethlin]

rfcbot is unchecking our boxes.

[workingjubilee]

I have filed deepmesa/deepmesa-rs#14 as a courtesy to the author and a notification to anyone who inspects the repo.

[CAD97]

let's try

@rfcbot reviewed

[RalfJung]

let's try

@rfcbot reviewed

Yeah, then at least we can see in the log who approved, even if rfcbot unchecks boxes again

[saethlin]

@rfcbot reviewed

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔

[joshlf]

2. The validity invariant of the metadata part of &T and &mut T is that of usize with the further constraint that the total size of a T with that metadata must not exceed isize::MAX.

Given that we want to hold open the possibility that the validity invariants of &T/&mut T include that its referent is bit-valid, do we also want to hold open the possibility that the validity invariants of the metadata part of &T/&mut T also include something about the entire referent being inside a single allocation, the reference having valid provenance for its entire referent, etc etc? In other words, are there other constraints we might want to add in the future, and does saying that these are the exact validity invariants preclude us from adding those in the future?

[RalfJung]

Given that we want to hold open the possibility that the validity invariants of &T/&mut T include that its referent is bit-valid, do we also want to hold open the possibility that the validity invariants of the metadata part of &T/&mut T also include something about the entire referent being inside a single allocation, the reference having valid provenance for its entire referent, etc etc?

All of this applies to sized and unsized types equally, so I don't think it is part of this discussion. All of this is a property of the pointer part of the wide pointer, but this issue is about the metadata part and only the metadata part. Maybe validity of the pointer part depends on the value of the metadata part, but certainly not the other way around, so the pointer part is irrelevant here.

[scottmcm]

Thanks for writing this up! It makes sense to me, and is much clearer in phrasing than my attempt in that rust issue :P

[rfcbot]

The final comment period, with a disposition to merge, as per the review above, is now complete.

As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed.

This will be merged soon.

[RalfJung]

Great, thanks all. :) The issue can be closed then.

[RalfJung]

Reference PR: rust-lang/reference#1499