ACP: `PtrRange<T>` type

[clarfonthey]

Proposal

Problem statement

Pointer ranges are a very useful way of working with slices, and they're currently how the standard library implements many of the slice iterator types.

However, these ranges have a problem that is only made more clear with the move toward strict provenance: there is no guarantee that the two pointers in the range are actually related to each other, or that they refer to the same buffer. While there are some efforts that have been made to rectify this within the standard library itself, it would be nice to have a dedicated pointer range type whose internals can be modified based upon whatever is most easily optimisable by the compiler.

Motivating examples or use cases

• Pointer ranges allow efficiently indexing from both the start and the end of a slice, which is what makes them ideal for implementing iterators.
• Code that uses this type can be certain that the two pointers are related and share the same provenance, instead of making this a precondition for every function that uses them.
• The optimisations from refining this type can not only be reaped by the standard library, but the entire Rust ecosystem

Solution sketch

The precedent from NonNull implies that the pointer range type should serves the purpose of both *const T and *mut T ranges. Additionally, NonNull should be implied, since Rust requires that allocations be non-null; this would enable niche optimisation for things like Option<PtrRange<T>>.

The internal layout for this type can initially just be the naïve:

struct PtrRange<T> {
    start: NonNull<T>,
    end: *const T,
}

(Note: The use of *const T for the second argument preserves covariance while also allowing working as you'd expect for ZSTs, which use the offset to encode the length of the range.)

Although further refinements can be made to, for example, make end just a usize whose provenance gets taken from start. To allow these kinds of optimisations, these fields should not be made public, and instead have methods:

impl<T> PtrRange<T> {
    // SAFETY: User must guarantee pointers have the same provenance, which also implicitly guarantees they are non-null. They should also be a multiple of `size_of::<T>()` apart.
    unsafe fn from_ptr_range(range: Range<*const T>) -> PtrRange<T>;
    unsafe fn from_mut_ptr_range(range: Range<*mut T>) -> PtrRange<T>;
    unsafe fn from_non_null_range(range: Range<NonNull<T>>) -> PtrRange<T>;

    fn start(self) -> NonNull<T>;
    fn end(self) -> NonNull<T>;
    fn start_ptr(self) -> *const T;
    fn end_ptr(self) -> *const T;
    fn start_mut_ptr(self) -> *mut T;
    fn end_mut_ptr(self) -> *mut T;
}

Presumably, there could be a few methods on these that are similar to slices, with the addition of back-indexing.

impl<T> PtrRange<T> {
    fn len(self) -> usize;
    fn is_empty(self) -> bool;

    fn get(self, idx: usize) -> Option<NonNull<T>>;
    fn get_back(self, idx: usize) -> Option<NonNull<T>>;

    unsafe fn get_unchecked(self, idx: usize) -> NonNull<T>;
    unsafe fn get_unchecked_back(self, idx: usize) -> NonNull<T>;

    fn index(self, idx: usize) -> NonNull<T>;
    fn index_back(self, idx: usize) -> NonNull<T>;
}

Presumably, over time, more methods could be added. I don't want to prescribe too much at this stage since I'm not sure what people would use them for.

Alternatives

There are a few options for this:

1. Make the start and end fields public. This feels like a bad option: if we're going to optimise the provenance here, then why do so in a struct which is clearly identical to Range? We could just optimise Range instead. Plus, this would also require something like unsafe fields, since modifying the fields is unsafe.
2. Optimise Range, somehow. This would probably involve adding some weird trickery to the compiler to allow relating the provenance of fields on one struct, and keeping that tagged throughout the entire flow of the program. We've done similar things with the borrow checker, but that feels like a lot of work and unlikely to get done any time soon.
3. Don't optimise Range, but add methods on it similar to the slice operations. We already have len and is_empty for them (technically, via ExactSizeIterator), so we're already partially there.
4. Do nothing.

Links and related work

• Tracking Issue for strict_provenance rust#95228
• Add a raw pointer iterator rust#91390
• Make slice iterators carry only a single provenance rust#122971
• Add slice::DrainRaw for internal use rust#127348

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[programmerjake]

impl<T> PtrRange<T> {
    fn len(self) -> usize;

assuming you want len to use offset_from, len needs to be unsafe since offset_from assumes the distance is a multiple of size_of::<T>() and size_of::<T>() != 0. you can probably have a safe byte_len() though.

[pitaj]

I think the following would be nice additions

impl<T> PtrRange<T> {
    // Caller must guarantee that the `length` is a valid offset from `start`.
    pub unsafe fn from_raw_parts(start: NonNull<T>, length: usize);
    // Totally safe to construct.
    pub fn new(slice: &[T]);
}

[scottmcm]

If you want this to work for ZSTs, you'll need (NonNull<T>, RawPtr<T>).

Fun to see this, since I actually have a PR open to make it internally: https://github.com/rust-lang/rust/pull/127348/files#diff-1f555155b76a53e257b9b4ee13a9a825a7f346cf4447763b2cb98a7a8bf11dd6R414-R426

[scottmcm]

Some previous conversations: rust-lang/rust#91390

[clarfonthey]

impl<T> PtrRange<T> {
    fn len(self) -> usize;

assuming you want len to use offset_from, len needs to be unsafe since offset_from assumes the distance is a multiple of size_of::<T>() and size_of::<T>() != 0. you can probably have a safe byte_len() though.

Hmm, I feel like part of this is ensuring that the pointer range is a legitimate representation of a slice, and so we'd want to make that another precondition for the range. But, that makes sense.

If you want this to work for ZSTs, you'll need (NonNull<T>, RawPtr<T>).

Fun to see this, since I actually have a PR open to make it internally: https://github.com/rust-lang/rust/pull/127348/files#diff-1f555155b76a53e257b9b4ee13a9a825a7f346cf4447763b2cb98a7a8bf11dd6R414-R426

I had totally forgotten that we do this weird thing for ZSTs. Makes sense to me.

---

Updated for both of these: the internal representation matches the one of the existing proposals, and the precondition now requires that the pointers be a multiple of size_of::<T>() apart. This cheekily also works for ZSTs since any numbers are a multiple of zero apart.

[kennytm]

5th alternative make use of the DST pointer types *const [T] and *mut [T]?

[clarfonthey]

5th alternative make use of the DST pointer types *const [T] and *mut [T]?

The main issue with that is that those are explicitly start + length and not start/end ranges. The main purpose of this is to represent slices as pointer ranges, which isn't how the fat pointers work.

Unless you meant like, make a new special slice type whose metadata would encode the end pointer. Which isn't the worst idea but I'm not sure how well it'd be received.

[kennytm]

The difference between *const [T] and PtrRange<T> is that the former intrinsically can't represent e.g.

let block = [1, 2, 3];
let [a @ .., _] = █
let [_, b @ ..] = █
let range = PtrRange::<[i32; 2]>::from_ptr_range(addr_of!(*a)..addr_of!(*b));

because the "length" of the range is going to be 0.5. But your safety requirement already mentioned that a and b must be size_of::<T>() apart so the code above is actually invalid and PtrRange<T> and *const [T] are isomorphic.

So I don't see any reason why you need to store end explicitly rather than recomputing it as start.add(len).

[programmerjake]

So I don't see any reason why you need to store end explicitly rather than recomputing it as start.add(len).

the whole point of this type is to store end explicitly because that has the same benefits as slice::Iter storing end explicitly...it makes iteration-style stuff faster, and probably a lot of other stuff.

[kennytm]

@programmerjake Then the type should be named like PtrIter, any new kind of Range should definitely not going to be an Iterator again in 2024.

[scottmcm]

@kennytm Agreed that it makes sense to phrase this as an iterator type. Then it can be normal Range<*const as the range type (or both of those range types, I guess 😬) for things like [T]::as_ptr_range, maybe with special unsafe methods to convert that to the new pointer iterator, as well as unsafe constructors on the pointer iterator (from pointers or pointer+len) and safe ways to go from &[T] or &mut [T] to the pointer iterator.

[BurntSushi]

I don't know what the exact shape of this ought to be, but I'm personally excited by experimenting in this space. I'm strongly in favor of making unsafe code easier to write, and this strikes me as a step forward in that direction. With that said, I would feel more comfortable if at least one other on libs-api member seconded my approval before moving forward.

[programmerjake]

@programmerjake Then the type should be named like PtrIter, any new kind of Range should definitely not going to be an Iterator again in 2024.

I didn't say it is an iterator, just that it makes iteration-style stuff more efficient. I am not proposing that it implement Iterator, nor did @clarfonthey afaik (though I won't object if people thinks that's better).