Is this supposed to work with NLL?

EDIT: Revised examples to also include "owned" types and avoid overuse of u8

So, I have recently been playing with in-place deserialization (inside abomonation if you are curious), and there I hit some borrow checking edge cases which I thought should have been resolved by Non-Lexical Lifetimes.

Can someone help me figure it out if I'm asking too much of NLL here or if it's a bug/limitation of the current implementation?


For the purpose of discussion, let us introduce a trait which represents data types that can be deserialized in-place from a slice of bytes of a certain lifetime.

If you have ever played with serde, this notion is closely related to the 'de in its Deserialize<'de> trait:

pub trait InPlaceDeserialize<'bytes> {
    /* ... implementation details of deserialization from &'bytes mut [u8] ... */
}

Many types can be deserialized from any slice of bytes and can therefore have a blanket implementation of this trait for all 'bytes:

impl InPlaceDeserialize<'_> for bool {
    /* ... implementation details ... */
}

However, we need to be careful about this lifetime as soon as references come into play, because we're talking about in-place deserialization, which entails patching pointers within the serialized data to point at other serialized data.

Any &'target T will be turned into an &'bytes T, and for this substitution to be valid, we must only allow deserialization of references which are outlived by the bytes. Otherwise, the user would be able to open a memory safety hole by e.g. sneaking out a &'static T after the bytes have been dropped.

In the language of lifetimes, this constraint is expressed as follows:

// Deserialization is only allowed if &'bytes T lives strictly longer than &'target T
impl<'target, 'bytes: 'target> InPlaceDeserialize<'bytes> for &'target str {
   /* ... implementation details ... */
}

Now, let us write a deserialization interface. Intuitively, one could expect this to work...

// Actual signature is more complex, with error handling and other stuff
pub fn deserialize1<'bytes, T>(_bytes: &'bytes mut [u8]) -> &'bytes T
    where T: InPlaceDeserialize<'bytes>
{
    unimplemented!()
}

...but it doesn't, because it forbids us to deserialize references with any lifetime shorter than 'bytes, which is actually perfectly fine (e.g. it's okay to deserialize &'a T from &'static mut [u8]):

// Won't compile. T may not live long enough, consider adding a T: 'bytes bound
pub fn client<'bytes, T>(bytes: &'bytes mut [u8])
    where T: InPlaceDeserialize<'bytes>
{
    deserialize1::<&str>(bytes);
}

Personally, I already find this surprising. Why doesn't rustc report an error at the point where deserialize1 is defined, but only at the point where client is defined? Maybe a bug report is in order here?

But in any case, to handle this use case, it seems we need this signature instead:

pub fn deserialize2<'output, 'bytes, T>(_bytes: &'bytes mut [u8]) -> &'output T
    where 'bytes: 'output,
          T: InPlaceDeserialize<'bytes>
{
    unimplemented!()
}

To check if our deserialize2 signature is right, let's write some clients. At first, the easy stuff seems to work...

pub fn foo1<'bytes, T>(bytes: &'bytes mut [u8])
    where T: InPlaceDeserialize<'bytes>
{
    deserialize2::<T>(bytes);
}

pub fn bar1(bytes: &mut [u8]) {
    foo1::<&str>(bytes)
}

... but closer examination reveals that we have actually borrowed our bytes forever, and cannot do anything with them even after the &'output T has been dropped :frowning:

// Won't compile
pub fn foo2<'bytes, T>(bytes: &'bytes mut [u8]) -> &'bytes mut [u8]
    where T: InPlaceDeserialize<'bytes>
{
    // Can't borrow "bytes" more than once at a time.
    deserialize2::<T>(bytes);
    // First borrow   ^^^^^
    bytes
    // ^^ second borrow
}

I find this puzzling. I thought that, especially with NLL, rustc was supposed to only borrow data as long as necessary? Here, the 'output that it's picking is clearly much too greedy for an &'output T reference that is being dropped immediately...

Can someone more familiar than I am with lifetime puzzles tell me if this is expected behavior from the borrow checker, a known rustc bug, or an unknown rustc bug that I should report?

And, if it's a bug, is there a known workaround?

All code examples are available on the playground.

1 Like
pub fn foo2<'bytes, T>(bytes: &'bytes mut [u8]) -> &'bytes mut [u8]
    where T: InPlaceDeserialize<'bytes>
{
    {
        deserialize2::<T>(bytes);
    }
    bytes
}

Since it doesn't solve the error it doesn't seem to be a NLL issue. In the end you'd want "for all lifetimes shorter than this one", but I don't think your can express it with trait without more work done on higher-kinded types (GAT for example).

2 Likes

First of all, there is no NLL-issue whatsoever:

  • fn deserialize2<'output, 'bytes, T>(
        _: &'bytes mut [u8],
    ) -> &'output T
    where
        'bytes : 'output,
        T : InPlaceDeserialize<'bytes>,
    

    If the only thing we know about T is that T : InPlaceDeserialize<'bytes> then the borrow on the input bytes will last 'bytes, no matter the return type.
    So the choice of 'output plays no role in the choice of 'bytes, which is limited by the InPlaceDeserialize<'bytes> bound.

  • fn foo2<'bytes, T> (
        bytes: &'bytes mut [u8] // <-------------------------+
    ) -> &'bytes mut [u8] //                                 |
    where //                                                 | same as
        T : InPlaceDeserialize<'bytes>, // >-----------------+
    { //                                                     | leads to
        deserialize2::<T>(bytes); // <-----------------------+
        // First borrow lasts for `'bytes`, hence for the whole function's body
        bytes // Error
    }
    

So, to fix that function, you need a HRTB on the trait, but for a lifetime 'a where 'bytes : 'a. This is alas not expressible with for<...> quantification, hence the problem.


It feels, however, to me, that you got the lifetime bounds reversed:

IIUC, the InPlaceDeserialize<'bytes> has an implicit &'bytes Self type in mind, and thus an implicit Self : 'bytes bound (which can and should be made explicit); and then with Self = &'target u8, this leads to 'target : 'bytes (for the type &'bytes &'target u8.

If the return intended type was &'bytes u8 instead of &'bytes &'target u8 (which can become &'target u8 thanks to &'target u8 : Copy), then it feels to me that Self should be u8, and the lifetime quantification should not appear in the trait's impl but in the deserializing function impl:

unsafe
trait InPlaceDeserialize<'bytes> /* where Self */ : 'bytes {}

fn deserialize<'bytes, T> (_: &'bytes [u8]) -> &'bytes T
where
    T : InPlaceDeserialize<'bytes>,
{
     unimplemented!("Using `unsafe`, hence the unsafe on the trait")
}

unsafe
impl<'bytes> InPlaceDeserialize<'bytes> for u8
// where u8 : 'bytes /* trivial bound */
{}
2 Likes

Seems Yandros beat me to reply. I commented in playground, adds/complements theirs.
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=e479a626eed2cdfa3ee41b2605393d41

3 Likes

@Yandros Sorry, it seems that I over-simplified my actual problem by only providing an &'target u8 example, thus leading you in the wrong direction. To avoid misleading more people, I have updated the OP to 1/provide another example of serializable data than references and 2/avoiding use of u8 in both "bytes" and the serialized data.


I think I do not want InPlaceDeserialize<'bytes> to have an implicit : 'bytes bound, because if I'm not misunderestood, this would mean that only 'static data can be deserialized from 'static bytes, which is not the intent.

It is actually okay to deserialize short-lived data from long-lived bytes. What is not okay is to deserialize long-lived data from short-lived bytes. That is because the references will be patched by the deserializer to point into the neighboring bytes. Therefore, if you were allowed to deserialize an &'static T from &'bytes [u8], you would get an &'bytes T which masquerades as a &'static T, and then you could make a copy of it, drop the source bytes, and end up with a dangling reference...

Ultimately, though, I agree with you and @leudz that what I really want is some sort of for<'a where 'bytes: 'a> T: InPlaceDeserialize<'a> bound in client functions. Now matter how hard I try to work around the lack of it, I just keep hitting a wall where I end up borrowing my bytes for too long...


@jonh I'm not fond of returning T: InPlaceDeserialize<'_> from deserialize() because it means that every impl of InPlaceDeserialize must feature a reference instead of just targeting the type being serialized/deserialized. I suspect that you were also misled by the my original problem formulation, where I only implemented InPlaceDeserialize for references, so I would advise you to check the new and improved version of the OP that I just edited in.

1 Like

Wait a minute...

Actually, for<'a where 'bytes: 'a> T: DeserializeInPlace<'a> is not what I want.

It requires DeserializeInPlace<'a> to be implemented for all lifetimes 'a smaller than 'bytes. Whereas the impl of DeserializeInPlace for reference types actually sets a lower bound of the set of lifetimes 'a for which DeserializeInPlace<'a> is implemented. Therefore, this enhanced HRTB syntax still excludes reference types, just like a regular HRTB would!

Another way to look at it is that because deserializing from bytes which are longer-lived than necessary is safe, T: DeserializeInPlace<'a> implies for<'b: 'a> T: DeserializeInPlace<'b>, and therefore setting a higher bound on the 'a-s for which we want DeserializeInPlace<'a> to be implemented is meaningless (higher bound on lower bound of 'b = no actual bound on 'b).

From this latter perspective, for<'a where 'bytes: 'a> T: DeserializeInPlace<'a> is actually equivalent to for<'a> T: DeserializeInPlace<'a>.

I was both misunderstanding the purpose of the trait and intent of deserialize that you have. Your only really intention is doing transmutation so was getting mixed up early rather than to the end.

Try this for helping you down the rabbit hole.
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=7e28542daa58e50282bcf60db5683c18

You know, I am surprised that the compiler will actually accept this:

pub trait Lo<'a> {
    type a: InPlaceDeserialize<'a>;
}
pub trait Hi: for<'a> Lo<'a> {}

impl<'a, 'b> Lo<'a> for &'b str {
    type a = &'a str;
}
impl<'b> Hi for &'b str{}

But crazily enough, this actually seems to work :wink: Let's try to tweak it some more and see if it can be made to work for any InPlaceDeserialize impl...

1 Like

So... err... I think I've found a simpler way.

It's also a darker, somewhat frightening way. But hey, this code is for a crate that has entomb() and exhume() unsafe methods in its public API, after all...

pub fn evil_foo<'bytes, T>(bytes: &'bytes mut [u8]) -> &'bytes mut [u8]
    where T: InPlaceDeserialize<'bytes>
{
    unsafe {
        // Since Rust won't work for us, we must resort to the C way.
        let (ptr, len) = (bytes.as_mut_ptr(), bytes.len());
        std::mem::forget(bytes);

        // Oh, and we're also going to need a scope. Bear with me.
        {
            // This is a perfect copy of the original "bytes"
            let bytes = std::slice::from_raw_parts_mut::<'bytes, _>(ptr, len);
            
            // The borrow checker can borrow it as long as it likes...
            deserialize2::<T>(bytes);
            // ...because we're just going to drop it anyhow.
        }
        
        // What we will return is... a _different_ clone of "bytes"
        std::slice::from_raw_parts_mut::<'bytes, _>(ptr, len)
    }
}

Although this code is rather horrifying, I believe that it is sound, because...

  1. There is no &mut aliasing. At any point of code, there are only zero or one Rust references to the bytes in flight.
  2. Input data lifetime is duly respected. Every copy of bytes that is created is an &'bytes mut [u8], there is no possibility of accidentally creating an &'static mut [u8] or something bad like that.
  3. Slice-cloning unsafe superpowers are not abused to leak extra references to the bytes which would violate Rust's aliasing rules. The references produced by deserialize2 do not exit the scope in which the function is called.

Forgetting a reference does nothing, so you may still have some unsoundness, although I am not knowledgeable enough in unsafe to know if it is sound.

Let's try to summon @RalfJung then! He's the kind of person who likes reading this sort of code late at night...

1 Like

MIRI complains about your code, playground,

removing the std::mem::forget does pass MIRI (but that still doesn't mean that it is sound, just that it isn't obviously unsound) playground

Without some variant of std::mem::forget, I'm pretty sure that this code violates Rust's aliasing rules, because we have two live &muts to the same data at the same time in the inner scope. Miri most likely isn't smart enough to notice it yet...

...on the other hand, I could be convinced that the following variant, while still super-shady, does not violate Rust's aliasing rules:

pub fn evil_foo<'bytes, T>(bytes: &'bytes mut [u8]) -> &'bytes mut [u8] {
    unsafe {
        // Dear borrow checker, please go out of the way for a second
        let bytes_uc: &'bytes UnsafeCell<[u8]> = std::mem::transmute(bytes);
        
        // Now, we're going to need a scope to contain some evil deeds
        {
            // This is a perfect copy of the original "bytes"
            let bytes: &'bytes mut [u8] = &mut *bytes_uc.get();
            
            // The borrow checker can borrow it as long as it likes...
            deserialize2::<T>(bytes);
            // ...because we're just going to drop it anyhow.
        }
        
        // What we will return is... a _different_ clone of "bytes"
        let bytes: &'bytes mut [u8] = &mut *bytes_uc.get();
        bytes
    }
}

That's because the transmute moves away "bytes" (if you try to use it afterwards, you will see that rustc complains that it is used after move). And if it's considered to be moved by the compiler, it probably isn't taken into consideration for the purpose of &mut alias analysis.

FWIW, miri is happy about this one as well.

1 Like

...well, after closer examination, my actual use case (which does not involve &'bytes mut [u8] but a more general S: DerefMut<Target=[u8]> + 'bytes generic parameter) is actually taken care of by straightforward use of UnsafeCell<S>. So my immediate problem is solved:

pub fn less_evil<'bytes, S: DerefMut<Target=[u8]> + 'bytes>(bytes: S) -> S {
    unsafe {
        let bytes_uc = UnsafeCell::new(bytes);
        {
            let bytes = &'bytes mut [u8] = (*bytes_uc.get()).deref_mut();
            // ... do whatever horrible stuff is necessary without leaking references ...
        }
        bytes_uc.into_inner()
    }
}

I'm still interested in 1/whether the transmute-based variant of evil_foo above was UB and 2/whether the API of either foo2 or deserialize2 can be straightforwardly adjusted to get the intended semantics without resorting to evil unsafe tricks, though.

1 Like

For those like me who are still intrigued by the underlying API design puzzle, I think the key question is, why this variant of the deserialize and client API that tries hard to decouple the 'bytes lifetime from the 'output lifetime won't solve the problem:

pub fn deserialize3<'output, 'bytes, T>(_bytes: &'bytes mut [u8]) -> &'output T
    where 'bytes: 'output,
          T: InPlaceDeserialize<'output> + 'output
{
    unimplemented!()
}

pub fn client<'bytes, 'output, T>(bytes: &'bytes mut [u8]) -> &'bytes mut [u8]
    where T: InPlaceDeserialize<'output> + 'output,
          'bytes: 'output
{
    deserialize3::<T>(bytes);
    bytes
}

I think the answer is that with this design, the caller of "client" is in principle able to pick any 'output lifetime smaller than 'bytes, and therefore the borrow checker must in particular prove that the code works in the 'bytes == 'output case.

Thus, we effectively go back to a T: InPlaceDeserialize<'bytes> constraint, which as @Yandros pointed out is the heart of the issue.

To fix this, we would need a way to express a kind of "for some 'output lifetime of my choosing, not yours" concept in the API of client().

Higher-ranked trait bounds almost provide this, but their actual meaning is "for any possible 'output lifetime", which is too broad and effectively restricts us to T: InPlaceDeserialize<'null> implementations (where 'null is an imaginary lifetime which never lives long enough no matter what borrow constraint you are trying to prove => no borrow allowed inside of T).

I think the constraint we actually need is "for some reborrow of the bytes input slice that does not exit this function's stack". But I'm not sure how it could be expressed in a Rust API. Maybe @jonh was on the right track, but all my attempts at trying to generalize this solution to any InPlaceDeserialize implementation ended up hitting a "either we need GATs or we must write much more code for each InPlaceDeserialize implementation" wall.

Yes, the more I think about it, the more I am convinced in that the issue here is between you and Rust dealing with lifetime parameters differently. The main thing is that a lifetime paramater bound to a generic function represents a lifetime that outlives the body of the function.

The only way to get arbitrarily short-lived lifetime parameters is with HRTB, which are usually present in CPS/callback-based APIs:

pub
fn with_deserialize<'bytes, T, R, F> (
    bytes: &'bytes mut [u8],
    f: F,
) -> R
where
    for<'output> F : FnOnce(&'output T) -> R,
    for<'output> T : InPlaceDeserialize<'output>,
{
    f(unimplemented!())
}

pub
fn client<'bytes, T>(bytes: &'bytes mut [u8]) -> &'bytes mut [u8]
where
    for<'output> T : InPlaceDeserialize<'output>,
{
    bytes.with_deserialize(|_thing: &T| {

    });
    bytes
}

Now, the HRTB cannot be bounded, but it does not matter, since a function requiring a &'static Something as input will not be able to fulfill the for<'any> &'any Something input bound (non-covariance w.r.t. function parameters). Only a function that, on the contrary, can handle an input with a small lifetime, no matter how small, will be able to also handle the big lifetimes (by contravariance).

That's why even if there is no 'bytes : 'output bound, there should nevertheless be no soundness issue:

error: borrowed data cannot be stored outside of its closure
  --> src/main.rs:53:13
   |
50 |     let mut s = "static";
   |         -----   -------- cannot infer an appropriate lifetime...
   |         |
   |         ...so that variable is valid at time of its declaration
51 |     let bytes = &mut [];
52 |     with_deserialize::<str, _, _>(bytes, |short_s: &str| {
   |                                          --------------- borrowed data cannot outlive this closure
53 |         s = short_s;
   |             ^^^^^^^ cannot be stored outside of its closure

Now, I think that instead of having an "existential" small lifetime parameter, having a classic API where the return type is borrowed for as long as its input should be fine too, since variance and the compiler choosing the smallest possible lifetime at each call site should provide the same flexibility:

/// Types which implement this can be deserialized in-place from &'bytes mut [u8]
///
///
pub
trait InPlaceDeserialize {}
impl InPlaceDeserialize for str {}

pub
fn deserialize<'bytes, T : ?Sized + 'bytes> (
    bytes: &'bytes mut [u8],
) -> &'bytes T
where
    T : InPlaceDeserialize
{
    unimplemented!()
}

pub
fn client<'bytes, T> (
    bytes: &'bytes mut [u8],
) -> &'bytes mut [u8]
where
    T : InPlaceDeserialize,
{
    deserialize::<T>(bytes); // borrowed for an ephemeral lifetime
    bytes
}

fn main ()
{
    let mut s: &'static str = "static";
    let mut bytes = [];
    let short_s = deserialize::<str>(&mut bytes);
    s = short_s; // Error
}

Ah, it's too bad you weren't at tonight's Rust Paris meetup (or I somehow missed you in the room), we could have iterated on this more quickly through the magic of face-to-face interaction.

But basically, the problem with the approach that you suggest at the end of your post is that it doesn't work for transitive references. You cannot (safely) deserialize more complex types like those in place without setting some sort of lifetime bound on the InPlaceDeserialize trait:

struct Composite<'a> {
    b: bool,
    s: &'a str,
}

struct AndThenSome<'a, 'b, 'c> {
    c: &'b Composite<'a>,
    s: &'c str,
}

The reason is that sooner or later, beyond a certain reference tree depth, if it wants to produce an &T without allocating extra memory, the deserializer will have to resort to the trick of patching the references within the serialized bytes to point elsewhere into the serialized bytes (thus creating a kind of hidden self-referential struct, FWIW). And when we reach that point, we cannot allow the user to, say, request deserialization of a Composite<'static> from some bytes of finite lifetime.

This would lead the deserializer to create a fake &'static str reference which actually points into an &'bytes [u8] slice, which would be Very Bad (as it trivially enables memory unsafety by copying the fake &'static str then dropping the bytes).

As for HRTBs, I have already explained why they don't work for this use case at the end of the opening post's playground example.

"Liveness" for Stacked Borrows (in Miri) right now is defined based on when a reference is actually used. It has nothing to do with its lexical scope. This matches NLL. Curiously, calling mem::forget extends the liveness of a references and passing it to a function counts as a use. :slight_smile:

I'm afraid I don't have the time right now to dig into this API any deeper. I am happy to explain Miri's behavior on concrete examples though, and defend it where necessary. :wink:

2 Likes