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

[thomcc]

I would prefer if it didn't implement Iterator, as I think there's value in this type being Copy. I think the iterator would presumably be forced to use wrapping_add anyway, which would be slightly undesirable.

(I'm in favor of this API btw, I've had (admittedly idiosyncratic) code where using a pair of *const u8 offered a few % speedup over using a slice)

[clarfonthey]

I also would prefer this not be an iterator, since otherwise it doesn't have much benefit over, for example, just using slice::Iter directly. An iterator type could exist also, but it would need to be be separate.

[scottmcm]

Hmm, I think I see it as the opposite. If it's not an iterator, what does it do that NonNull<[T]> or &[T] or unsafe<'a> &'a [T] or newstyle::Range<NonNull<T>> doesn't do fine?

The big reason for the two-pointers representation (instead of pointer-plus-count) is for Iterator::next (even next_back doesn't care), so if rather than being an iterator it's something that can be converted into an iterator, I think other things might be fine.

Thus the mention of calling it slice::NonNullIter<T> or similar, rather than something involving Range.

[clarfonthey]

My particular logic for not making it an iterator is that the representation is useful for iterators, but doesn't have to be an iterator by itself.

For example, the use case I was thinking of most recently is accessing expressions in suffix notation. In particular, if you have a slice of nodes like so:

struct Node<T> {
     token: T,
     lhs_len: usize,
     rhs_len: usize,
}

then you can simplify the computations done to return the operands, so that you don't need to constantly compute slice.len() - len and can instead just offset the back pointer by len.

Like, by all means, you can make them an iterator, although that incentivises making separate ones for NonNull, const, and mut when they would all normally share the same implementation internally… that type being PtrRange<T>.

My thought process here is that ultimately, the pointer-pair representation of a slice is useful, and while it's most useful for iterators, it has other uses too, and it's better to simply offer a type that offers the bare-minimum invariants we want and let people implement whatever wrapper around it they need.

That could involve offering said iterator wrappers in the standard library as well! I'm just offering the simplest (IMHO) solution rather than requesting the kitchen-sink package.

[kennytm]

For example, the use case I was thinking of most recently is accessing expressions in suffix notation. In particular, if you have a slice of nodes like so:

struct Node<T> {
     token: T,
     lhs_len: usize,
     rhs_len: usize,
}

then you can simplify the computations done to return the operands, so that you don't need to constantly compute slice.len() - len and can instead just offset the back pointer by len.

Sorry but this example is incomprehensible. Where did slice come? Is it a &[_]? And what is len? There are just lhs_len and rhs_len. How is Node<T> relevant? Why do you need to compute a pointer?

I suppose you mean to refactor something like

let val = &slice[slice.len() - len];

into

let range = slice.as_ptr_range();
{ ... }
let val = unsafe { &*range.end.sub(len) };

and want a structure rather than Range<*const _>, and can guarantees start and end have the same provenance by hiding direct access.

(This is assuming slice is not a ZST slice and len <= range.len(). If both are checked I think the code is no simpler than .into_iter().nth_back(len).unwrap())

[clarfonthey]

Sorry but this example is incomprehensible. Where did slice come? Is it a &[_]? And what is len? There are just lhs_len and rhs_len. How is Node<T> relevant? Why do you need to compute a pointer?

I was trying to be brief to avoid adding more details than necessary, but I suppose that actual code is better than theoretical code, so, here you go, with the most relevant bits:

struct Node<T> {
    token: T,
    lhs_len: usize,
    rhs_len: usize,
}
pub struct Expr<'a, T> {
    slice: &'a [Node<T>],
}
impl<'a, T> Expr<'a, T> {
    pub(crate) fn new(slice: &'a [Node<T>]) -> Option<Expr<'a, T>> {
        if slice.is_empty() {
            None
        } else {
            Some(Expr::new_unchecked(slice))
        }
    }
    pub fn operands(self) -> (Option<Expr<'a, T>>, Option<Expr<'a, T>>) {
        let (last, rest) = self
            .slice
            .split_last()
            .expect("expression should be non-empty");
        let (rest, rhs) = rest
            .split_at_checked(rest.len() - last.rhs_len)
            .expect("expression RHS should be in bounds");
        let (_, lhs) = rest
            .split_at_checked(rest.len() - last.lhs_len)
            .expect("expression LHS should be in bounds");
        (Expr::new(lhs), Expr::new(rhs))
    }
}

(Side note: allowing LHS or RHS to be empty regardless of circumstance gives a very natural way of distinguishing between prefix operators (like -) and suffix operators (like ?), effectively for free. That's why I use this representation.)

It's an expression in suffix notation, like 1 2 + 3 * which is equivalent to (1 + 2) * 3. The benefit of suffix notation is that you can keep pushing operands onto the stack while parsing things without having to move the existing operands around, and you can use algorithms like Dijkstra's shunting yard algorithm to parse things into it.

The point here is that, when navigating through the tree (which can be much larger than the examples I provided), you have to perform effectively double the arithmetic operations to index from the end instead of the beginning, due to the fact that you're computing start,add(len - idx) instead of end.sub(idx) every single time. While it would require unsafe code, PtrRange<T> would be more efficient here.

And this is one of the two primary cases where pointer-pair representations are efficient. There are effectively two of them:

1. When iterating through a slice, there are two operations you care about: getting the pointer to the item, and checking if you've reached the end of the iteration. While many architectures will make it effectively "free" to offset a memory address by a register (making indexing have no "real" cost), it's still rather natural to simply advance the pointer and compare it to the end pointer to perform this in a simpler manner.
2. By having both a start and end pointer, you can iterate in both directions without any loss in efficiency. This is genuinely more costly without pointer-pair structures, since while you can easily offset a memory address by one value, you often can't add a length and subtract an index in the same operation.

The second one is the one I'm particularly concerned about, but I acknowledge that the first is most common. The only alternative that would also solve the second issue is by having some kind of "reversed slice" representation where you still encode the length, but store the end pointer instead. I've tried this and it makes the compiler very unhappy no matter what you do, and I can't imagine a situation in which we'd actually support it. So, it makes sense to pursue the pointer-pair method instead, since that has much more broad support.

---

Also rereading and replying to this tidbit:

I think the code is no simpler than .into_iter().nth_back(len).unwrap()).

Yes, you can convert a slice into an iterator, but this gains no performance benefits if you do this at each step of the way, rather than keeping a pointer-pair representation throughout. Obtaining the end pointer for a pointer-pair representation requires adding the length to the start to begin with, which is the operation we're trying to avoid doing repeatedly.

[kennytm]

Also rereading and replying to this tidbit:

I think the code is no simpler than .into_iter().nth_back(len).unwrap()).

This was assuming you were trying to get the nth last element since you did not specify the purpose. Turns out it is to take a subslice so this is no longer relevant. (Though AFAIK your proposed PtrRange API does not have a safe API to reconstruct a slice either. Maybe your use case is better supported by providing the as_slice()/consume_slice() inherent methods to Take<slice::Iter>, Rev<slice::Iter> and Take<Rev<slice::Iter>> 🤔)

Yes, you can convert a slice into an iterator, but this gains no performance benefits if you do this at each step of the way, rather than keeping a pointer-pair representation throughout.

I meant slice.as_ptr_range().into_iter().nth_back(len).unwrap() to obtain a *const T at $-len and obviously the Range<*const T>::IntoIter structure whether a new or old range is implemented as "a pair of *const T" no doubt?

Even slice::Iter and slice::IterMut are internally implemented as pointer-pairs, I'm not sure what you are trying to debunk here.

Obtaining the end pointer for a pointer-pair representation requires adding the length to the start to begin with, which is the operation we're trying to avoid doing repeatedly.

(I suppose you meant to say "Obtaining the end pointer for a pointer-length representation requires adding the length to the start to begin with,")

[scottmcm]

Thinking about this more, I remembered why I didn't try to expose the raw non-null iterator in rust-lang/rust#127348 : it can't be used in safe code.

Basically, if there's a safe constructor from a slice, it can no longer use add in Iterator::next, as you could keep the range of pointers after you'd deallocated the memory.

So I think the big question here is where the safety promise should be made. Is it that it only has unsafe constructors, and the promise made in the constructor is "I won't use this for too long"? That's my least favourite kind of safety precondition, because it's entirely uncheckable at the time, though maybe there's no way to avoid it.

Or should it have safe constructors from things like slices, but then unsafe fn len and such because it's a wrapper around unsafe ptr_sub?

Alternatively, should it have a lifetime on it anyway, and rely on the unsafe<'a> work for things that want to manage the lifetime by hand?

[clarfonthey]

If I had my way and didn't care at all about stability guarantees or what others think, I personally would like two new types that represent slices and can be cast between each other:

• the current start + len representation
• a new end (not past-end) + len representation
• a start + past-end representation

And then there's no need for extra unsafe APIs to accomplish this stuff. I guess that my main reasoning for the unsafe wrapper in this API is that it could be easily converted into a safe wrapper, but has substantially smaller API guarantees than a safe wrapper would have. But maybe this is the wrong path to go down and a safe wrapper is the way to go.

My end + len representation is basically DOA since it requires something to own memory before its pointer, which seems unlikely to be ever supported. But theoretically, with compiler help, it's entirely possible to make an unsized PointerPair type with metadata that represents the end pointer for non-ZSTs and the length for ZSTs. Maybe that would be the API that would make most people happy, and being a DST, it could just directly be borrowed as mutable or immutable without having to have separate versions.

I guess that would be best as an MCP, and not an ACP, then? Since it would be more a land/compiler change than a libs change.

[the8472]

We discussed this during today's libs-api meeting. Several people were not in favor, although for different reasons. We do understand the performance benefit of having the alternative slice representation, but the benefit of having this as a common abstraction, especially in std, seem unproven. And it's a rather low-level feature where different users might want different safety constraints. In std we also want to support ZSTs in slice iterators, maybe someone else would just want to exclude that special case or handle it differently. Additionally the code patterns that please the optimizers most change with time so the exact needed API surface might change too over time.

So for now we would want internal uses like rust-lang/rust#127348 or an implementation outside std. In the future when they've proven themselves useful we may reconsider.