Why does with_* require HRTB for non-covariant / is there a way to make this lifetime work

[alex]

When a tail field contains an UnsafeCell it must be #[non_covariant] which means you cannot have the nice borrow_* method, alas.

I'm struggling to figure out if there's any way to get this minimized code to work (requires nightly, sorry):

#![feature(once_cell)]

use std::lazy::OnceCell;
use std::sync::Arc;

#[ouroboros::self_referencing]
pub struct OwnedRawCertificateRevocationList {
    data: Vec<u8>,

    #[borrows(data)]
    #[not_covariant]
    sorted_revoked_certs: OnceCell<Vec<RawRevokedCertificate<'this>>>,
}

#[derive(Clone)]
pub struct RawRevokedCertificate<'a> {
    data: &'a [u8],
}

#[ouroboros::self_referencing]
pub struct OwnedRawRevokedCertificate {
    data: Arc<OwnedRawCertificateRevocationList>,
    #[borrows(data)]
    #[covariant]
    cert: RawRevokedCertificate<'this>,
}

fn foo(x: &Arc<OwnedRawCertificateRevocationList>) -> OwnedRawRevokedCertificate {
    OwnedRawRevokedCertificate::new(Arc::clone(x), |v| {
        v.with_sorted_revoked_certs(|c| {
            // For this example, just an empty vec. In real life, would be
            // initialized based on `v.data`
            let sorted = c.get_or_init(|| vec![]);
            // Random index
            sorted[10].clone()
        })
    })
}

The idea is to be able to take an Arc<OwnedRawCertificateRevocationList> and project it to a OwnedRawRevokedCertificate which shares the same underlying data.

However, because with_* use HRTB and the callback is required to be valid for all lifetimes, the lifetime bound for the RawRevokedCertificate inside of c is bound more tightly than v, so this code doesn't work.

I am struggling to understand if there's a way to make this work under the current APIs, or failing that if this is because any expanded API would be unsound or if it's just a missing API.

[alex]

I don't think that's the cause of the issue here -- this example doesn't actually use data inside foo at all :-) But perhaps I'm misunderstanding.

[someguynamedjosh]

It looks like this is a limitation of how the library checks for soundness. Higher ranked lifetimes are used as wildcards to say that the 'this lifetime has no faithful representation in the language and so the code must work for every possible lifetime to be safe. I don't see a way to propagate the fact that the two 'this lifetimes are the same to make this case work. The simplest fix would probably be to put all the data in a single struct.

[alex]

When you say "all the data in a single struct" what do you mean? (Thanks for taking the time to look at this!)

[someguynamedjosh]

If you put all the fields in a single struct, then when you use with, the higher ranked lifetime will be the same for all the fields so you can assign the cert field a value from the sorted_revoked_certs field.

[alex]

The current design is supposed to allow you to create multiple OwnedRawRevokedCertificate which refer to a single OwnedRawCertificateRevocationList, it seems like that's not possible if I simply put the cert field in the same struct?

[alex]

I think I've been able to turn this into a feature request, which is hopefully sound (😬) though I'm not sure what the right API is:

#[ouroboros::self_referencing]
struct O1 {
    data: Arc<X>,
    #[borrows(data)]
    #[covariant]
    value: T1<'this>,
}

#[ouroboros::self_referencing]
struct O2 {
    data: Arc<X>,
    #[borrows(data)]
    #[covariant]
    value: T2<'this>,
}

fn op(o: &O1, for<'this> impl FnOnce(&'this X, &T1<'this>) -> T2<'this>) -> O2 {
	// TODO
}

This is somewhat specific to cases where an Arc<T> is the borrowed data, but basically it's a map function that takes one type with Arc<T> + some borrowed fields and returns a different type with the same Arc<T> and different borrowed fields.

Because of the way lifetimes work + the fact that Arc::clone(&ref) gives you a fresh object, I don't think it's currently possible to express this, but I think it's sound and would be incredibly useful.

Does this make sense to you? Do you see any soudness issues? If you have an idea for what the API should be, I'd be happy to contribute a PR for this!

[someguynamedjosh]

I think as written the function could be used unsoundly:

struct T1<'a>(&'a ());
struct T2<'a>(&'a ());

let o1 = make_o1_instance();
let o2 = op(&o1, |x, t1| T2(t1.0));
drop(o1);
// UB:
// o2.with_value();

[alex]

I attempted to actually implement that example:

use std::sync::Arc;

#[ouroboros::self_referencing]
struct O1 {
    data: Arc<X>,
    #[borrows(data)]
    #[covariant]
    value: T1<'this>,
}

#[ouroboros::self_referencing]
struct O2 {
    data: Arc<X>,
    #[borrows(data)]
    #[covariant]
    value: T2<'this>,
}

struct X(());
struct T1<'a>(&'a ());
#[derive(Debug)]
struct T2<'a>(&'a ());

unsafe fn relifetime<'a, 'b>(t: &'a T1<'a>) -> &'b T1<'b> {
    std::mem::transmute(t)
}

fn op(o: &O1, f: impl for<'this> FnOnce(&'this X, &T1<'this>) -> T2<'this>) -> O2 {
    O2::new(Arc::clone(&o.borrow_data()), |x| {
        f(&x, unsafe { relifetime(o.borrow_value()) })
    })
}

fn main() {
    let o1 = O1::new(Arc::new(X(())), |x| T1(&x.0));
    let o2 = op(&o1, |x, t1| T2(t1.0));
    drop(o1);

    o2.with_value(|v| println!("{:?}", v));
}

And it looks ok under ASAN:

~/p/h/t/ourb-exps ❯❯❯ env RUSTFLAGS="-Z sanitizer=address" cargo +nightly run --target x86_64-unknown-linux-gnu
   Compiling ourb-exps v0.1.0 (/home/alexgaynor/projects/hacks/tmp/ourb-exps)                                              
    Finished dev [unoptimized + debuginfo] target(s) in 0.74s
     Running `target/x86_64-unknown-linux-gnu/debug/ourb-exps`                                                             
T2(())                                                                                                                     

Did I implement what you expected, or did I get some detail wrong?

[alex]

Also seems good under miri:

~/p/h/t/ourb-exps ❯❯❯ cargo +nightly miri run
    Finished dev [unoptimized + debuginfo] target(s) in 0.01s                                                              
     Running `/home/alexgaynor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/cargo-miri target/miri/x86_64-unknown-linux-gnu/debug/ourb-exps`                                                                                               
T2(())                                                                                                                     

[someguynamedjosh]

It might be showing fine because it's a reference to a zero-sized type, my bad. Try replacing () with i32 and you should get errors.

[alex]

Still green under miri. IMO it makes sense that this is fine: both o1 and o2 have Arc<X> which each maintain a reference. The reference inside o2.value points into that Arc. The Arc is kept alive by o2 so it's fine.

[someguynamedjosh]

Ah, I didn't notice that part. When creating O2, there is nothing guaranteeing that the Arc will be a clone of the old one. If you create a new Arc and have the second field reference the old Arc, then dropping the instance of O1 will cause UB.

[alex]

In the general case I agree, but I don't think that situation can ever occur with the op API, can it? Because that's the goal: Have an API which is sound, and allows things like this.

[someguynamedjosh]

I think I understand now, I had been looking at it differently. I agree that it's sound, although since it is targeting only one very specific format I would want to hold off on putting it in the library unless there's a more general solution. I'll give it some more thought over the coming days. For now, if you are reliant on doing something specific like this in your code I would say that would justify rolling your own unsafe self-referencing struct.

[someguynamedjosh]

Having a macro to generate a proper implementation for this one specific pattern would be equivalent to writing a proper implementation by hand and using that in your code (a la owning_ref)

[alex]

Ok! Thanks for considering this. I'll just integrate this into my existing project for now -- will share a link to the PR here once it's done. I think this is a very powerful and useful pattern, so hopefully we can think of a clever way to incorporate it into the design of ouroboros!

[alex]

pyca/cryptography#6276 now contains the open-coded implementations of the API discussed here (as well as their usage)

[alex]

And https://github.com/pyca/cryptography/blob/ee5c05cfe745c125baa06be1de43c181532cfa58/src/rust/src/ocsp.rs#L595-L614 contains another implementation of this API