Safe slice rejoining

Borrow splitting slices can be very handy when trying to decompose things like no-std/no-alloc serializers.

However, when these serializers are done, it would be nice to be able to put these slices back together so as to give an immutable slice containing the entire finished document back to the caller.

This can be done with unsafe and e.g. slice::from_raw_parts with sufficient due diligence, however what would be really nice is to be able to do it from safe code:

let mut buf = [0u8; 1024];

let (header, rest) = buf.split_at_mut(42);
build_header(header)?;
let body_len = build_body(rest)?;
let body = &rest[..body_len];

let finished_doc = header.try_rejoin(body)?;

...the idea being that [T]::try_rejoin would succeed if the two slices are contiguous in memory, and fail otherwise.

I'm guessing there's probably some precedent around adding such a feature to core. If you happen to know of any, I'd appreciate a link.

(Note: I'm not interested in random crates that solve this one particular problem. I'd probably just use unsafe instead)

The problem is that this isn't a sufficient condition to guarantee that this is sound.

For example, consider

let a = [0u8; 8];
let b = [0u8; 8];
// These are laid out contiguous on the stack
assert_eq!(&a as *const _ as usize + 8, &b as *const _ as usize);
// But this must not succeed
a.try_rejoin(b).unwrap();

For it to be sound, you need at a minimum a guarantee that both references are into the same allocated object. There's no way to encode that data in pure safe references.

Additionally, with the current Stacked Borrows model, this isn't even sound if you do have such a guarantee, as the provenance of &T covers exactly size_of::<T>() bytes, and extending the reference beyond that is UB.[1]


  1. Ralf Jung seems hopeful that this limitation can be removed in a future model; it's basically required in order to support extern type. ↩︎

9 Likes

How does that work for [T], which is unsized?

References to unsized have provenance over size_of_val(&<place>) bytes. It's generally just exactly however many bytes the reference refers to based on the type and value of the (potentially wide) pointer.

The nominal borrow stack at the pointed location gets the Retag operation applied to it when doing a reborrow of the reference (basically, whenever passed between function boundaries; when lifetime variance, autoderef can apply) and that Retag has a unique tag for that new reference reborrow. That reference can only be used to access values from memory with that tag value.

This is a gross oversimplification of the Stacked Borrows model, but should illustrate why references only have provenance over the "expected size" in the current model.

1 Like

The precedent is: this operation under those requirements (safe, and the expected signature) is impossible with regards to stacked borrows. The chances of landing it in std, in the current state, is thus slim. Once you have split the two halves into references you can not get a reference for the complete buffer from them again. None of the halves have sufficient rights (as per provenance tracking) to access the other. You need to use a reference/pointer to the original complete buffer and even it's super unsafe as it would invalidate any other references that you may currently have into the complete buffer. Since the latter can't be outruled by lifetimes alone, no such safe operation exists.

To fix this would require introducing a new primitive operation that somehow joins the access rights of pointers. Handy example, visualized by which regions are covered by each reference.

^ top of the stack
|  header: &mut  | rest: &mut  | 'a
|  header0: &mut | rest0: &mut | 'b
|   buf: &mut                  | 'c
----------------------------------> memory

Under Stacked Borrows, the only way to somewhat soundly rejoin header and rest would be to rederive a new pointer from buf. But deriving a new pointer from buf is an access that conflicts with header0 and rest0—which invalidates them. No function that receives only header and rest can disprove the existence of header and rest0, rendering any such function necessarily unsafe (as in requiring the caller to disprove it). In particular, such reference header0 and rest0 mustn't be used after joining and they mustn't be function parameters either.

3 Likes

A weaker alternative which should not present provenance problems:

Define an operation which takes a reference to a 'large' slice and a 'small' slice and returns the index range in the large slice where the small slice is located. Then, you can safely join the ranges if their ends meet, and produce a joined slice from that range of the 'large' slice.

This requires comparing pointers which might not be in the same object, but it doesn't require expanding any single pointer's provenance.

1 Like

If there are Uniq (&mut) tags floating, yes, but Shr (&) tags won't invalidate other Shr tags. (I don't recall exactly how using Shr acts when Raw is above it on the stack, but...) I can use the root reference just fine, and even implement the operation safely:

// just byte slices to make this easier on my phone
// but you can do it with _overlapping just as safely
fn fuse(parent: &[u8], a: &[u8], b: &[u8]) -> Option<&[u8]> {
    let lhsa = a as *const _ as usize - parent as *const _ as usize;
    let lhsb = b as *const _ as usize - parent as *const _ as usize;
    let rhsa = lhsa + a.len();
    let rhsb = lhsb + b.len();
    // todo: require they're neighbors
    parent.get(lhsa.min(lhsb)..rhsa.min(rhsb))
}

It's not for the lack of trying that this alternative wasn't brought to fruition. That exact one was prototyped, and insufficient, for str-concat. We tried to keep it alive but death by SB keeps coming up. The only escape is having access to the original reference with its original shared tag and ensuring that no other tag exists. Which provides two possibilities:

  • &[u8] (ShareRO) for everything: Which is effectively only a slightly more compressed form of storing (&[u8], Range<usize>) with no particularly amazing gain that would warrant std-inclusion or special treatment. And also woefully insufficient for a lot of actual use cases.
  • *mut T (SharedRW) for everything: Which std already has but since its access is unsafe, because it derives an incompatible Unique pointer, it's also not a particularly good replacement. I suppose you could offer a sound write function on these pointers at least? (Edit: I may prototype this, as it actually sounds like I missed it. We can perform some operations with the raw pointer alone).

If I read the paper correctly, and remember the details: The problem is simply a fundamental mismatch between the borrow stack semantics that SB provides, and the semantics we want. Note that this location mismatch is completely independent of the kind of tag that we'll create. Hence it must always be fully compatible with all above, which restricts us to the above two shared cases to keep all of the above items valid.

|                              | <-- where our derived tag should live
|  header: &mut  | rest: &mut  | 'a
|  header0: &mut | rest0: &mut | 'b
|                              | <-- where SB inserts items derived from buf
|   buf: &mut                  | 'c
----------------------------------> memory

(Is this the lang-design equivalent of an annoying extension request issue report on a library?)

let mut buf = [0u8; 1024];

let header_len = 42
let body_len: usize;
{
    let (header, rest) = buf.split_at_mut(header_len);
    build_header(header)?;
    body_len = build_body(rest)?;
}

let finished_doc = &buf[..header_len + body_len];

At the risk of asking for the example to be overcomplicated, can we complicate the example so the above (or the moral equivalent) isn't the solution?

It seems like we need to drop all mutable references into buf before or during any recombination, so the above won't be possible if we are at a point in the program where we only have a reference to the header/body slices. In that case I would expect some reified constraint that the slices are contiguous, but that constraint could just have a reference to the underlying object which still means we can just drop the subslices.

1 Like

So this is in fact more or less the "solution" I'm using:

...but the problem is this only works where the original reference was in scope.

I would like for this function in a buffered encoder to be able to return a &[u8] as well, rather than a usize containing the length:

...but the problem is splitting the original slice to hand part of it off to a struct which stores a reference to it:

...or in other words, I'm trying to decompose the original mutable buffer in a way I can statefully separate responsibilities for encoding various parts of the buffer to types which are tasked with one particular aspect of the encoding.

Based on the comments here, it sounds like what I'd like really isn't possible in the stacked borrows model.

I guess this is fine, and wrapping things up in high-level functions which hold a mutable reference to the original contiguous buffer, with the stateful buffered parts returning the encoded length as a usize, which the high-level function can use to reslice the original buffer.

Hm, a reference type that is for all intents and purposes SharedRw and you can't be allowed to derive a direct reference to the underlying content. That … sounds like &Cell? Writing a sound join for ref-to-slice-cells specifically shouldn't be too hard, that's basically the trivial case of joining via an underlying & of the whole region. Can you make a list of methods that would you need to be added to &Cell<[u8]> and &Cell<str> for those types to be potent (and ergonomic) enough for your usecase? Because copy_from_slice sounds perfectly doable.

What about returning Result<(&'o [u8], &'o mut [u8])>?

I actually already rely on methods like that (i.e. when encoding PEM, after Base64 encoding is complete the PEM encoder still needs to add a post-encapsulation boundary):

...but the problem here is it would be nice to return the entire encoded document back to the caller in a single contiguous slice.

Having a high-level API which retains the reference to the contiguous buffer and can thus do that, and a lower-level one which returns a usize of the total encoded length (with the high-level API using that usize to slice the original buffer) seems like a reasonable tradeoff.

2 Likes