Abstracting storage and pointer family using GATs and unfortunate extra lifetime annotation

[CBenoit]

Hi!

I’m building an API that is abstracting over the shared pointer family, including the usual shared reference &T. This means that values may or may not be stored on the heap.

I got something working quite easily using GATs:

trait SharedPtrFamily {
    type SharedPtr<'a, T: 'a + ?Sized>: Deref<Target = T> + Unpin + 'a;

    fn share<'a, T>(ptr: &Self::SharedPtr<'a, T>) -> Self::SharedPtr<'a, T>
    where
        T: ?Sized + 'a;
}

struct RcFamily;

impl SharedPtrFamily for RcFamily {
    type SharedPtr<'a, T: 'a + ?Sized> = Rc<T>;

    fn share<'a, T>(ptr: &Self::SharedPtr<'a, T>) -> Self::SharedPtr<'a, T>
    where
        T: ?Sized + 'a,
    {
        Rc::clone(ptr)
    }
}

struct RefFamily;

impl SharedPtrFamily for RefFamily {
    type SharedPtr<'a, T: 'a + ?Sized> = &'a T;

    fn share<'a, T>(ptr: &Self::SharedPtr<'a, T>) -> Self::SharedPtr<'a, T>
    where
        T: ?Sized + 'a,
    {
        ptr
    }
}

And I’m able to write a generic API on top of this:

struct Holder<'a, T, F>
where
    F: SharedPtrFamily,
    T: 'a,
{
    slot: F::SharedPtr<'a, Option<T>>,
}

struct OtherHolder<'a, T, F>
where
    F: SharedPtrFamily,
    T: 'a,
{
    slot: F::SharedPtr<'a, Option<T>>,
}

// Code generic over the pointer family
fn do_something<'a, F>(holder: &Holder<'a, &'a u8, F>) -> OtherHolder<'a, &'a u8, F>
where
    F: SharedPtrFamily,
{
    OtherHolder {
        slot: F::share(&holder.slot),
    }
}

// Helper to create a Holder backed by a Rc pointer; wrap the value into `Option` and move to the heap
fn create_rc_holder<'a>(value: &'a u8) -> Holder<'_, &'a u8, RcFamily> {
    Holder {
        slot: Rc::new(Some(value)),
    }
}

// Helper to create a Holder backed by a reference; just stealing the slot and nothing else
fn create_ref_holder<'a>(slot: &'a Option<&'a u8>) -> Holder<'a, &'a u8, RefFamily> {
    Holder { slot }
}

fn main() {
    let data = 240;

    // With allocation
    let rc_holder = create_rc_holder(&data);
    let rc_other_holder = do_something(&rc_holder);
    assert_eq!(
        Rc::as_ptr(&rc_holder.slot),
        Rc::as_ptr(&rc_other_holder.slot),
    );

    // No-alloc code, heapless
    let slot = Some(&data); // Put the slot on the stack
    let ref_holder = create_ref_holder(&slot);
    let ref_other_holder = do_something(&ref_holder); // Using the same generic function as above
    assert_eq!(ref_holder.slot as *const _, &slot as *const _);
    assert_eq!(ref_other_holder.slot as *const _, &slot as *const _);
}

All is good, it works. Of course the example here is a bit contrived, but the actual program I’m writing does benefit from this approach.

However, I’m wondering if I did it "the right way", or the "the most ergonomic way".

For instance, if I write the same code, but specialized for Rc, I get something like this:

struct RcHolder<T> {
    slot: Rc<Option<T>>,
}

struct RcOtherHolder<T> {
    slot: Rc<Option<T>>,
}

fn harcoded_do_something<'a>(holder: &RcHolder<&'a u8>) -> RcOtherHolder<&'a u8> {
    RcOtherHolder {
        slot: Rc::clone(&holder.slot),
    }
}

// This is exactly the same as `create_rc_holder` as seen above, but the signature is simpler
// I would like to keep "specialized" code as simple, while returning something compatible with the generic API
fn harcoded_create_holder<'a>(value: &'a u8) -> RcHolder<&'a u8> {
    RcHolder {
        slot: Rc::new(Some(value)),
    }
}

fn main() {
    let data = 240;

    let harcoded_holder = harcoded_create_holder(&data);
    let harcoded_other_holder = harcoded_do_something(&harcoded_holder);
    assert_eq!(
        Rc::as_ptr(&harcoded_holder.slot),
        Rc::as_ptr(&harcoded_other_holder.slot),
    );
}

The question is: is there something I could do to obtain something equivalent to a type alias such that there is no anonymous lifetime to specify when using a heap-based flavor?

Is there something smart to do for achieving something similar to that:

// This is of course not valid Rust, but that’s what I would like to achieve somehow
type RcHolder<T> = Holder<'_, T, RcFamily>;

This type could still be used and consumed by the generic API, but would be less verbose when the family is hardcoded (e.g. create_rc_holder).

My take is that it’s (currently) not possible to do much better that this:

type RcHolder<'a, T> = Holder<'a, T, RcFamily>;

But I really hope someone can prove me wrong!

Here is the playground link containing all the code:

Rust Playground

[quinedot]

I haven't thought through your use case yet, but just skimming, it seems you could make this change.

+/// Required semantics: cloning results in something that derefs
+/// to the same underlying `T`
trait SharedPtrFamily {
+    type SharedPtr<'a, T: 'a + ?Sized>: Clone + Deref<Target = T> + Unpin + 'a;
-    type SharedPtr<'a, T: 'a + ?Sized>: Deref<Target = T> + Unpin + 'a;
-
-    fn share<'a, T>(ptr: &Self::SharedPtr<'a, T>) -> Self::SharedPtr<'a, T>
-    where
-        T: ?Sized + 'a;
}

For the actual question, you probably need something like a HRTB^[1] over your GAT, which can still be problematic

• when you're dealing with non-'static types
• when you need equality checks

But I haven't had time to play with it to see what progress might be possible yet.

If you have a less contrived use-case, that may help guide exploration.^[2] Are you mapping things within your families or something like that?

---

1. higher-ranked trait bound, where ... for<'a> ... ↩︎

2. I don't think I've seen a storage system for nested references or Rcs of references outside of being generic for the sake of being generic. ↩︎

[CBenoit]

Thank you for your answer!

I’m sorry for the delay, I figured the best was for me to move forward and clean my current code so I could share it to you directly.

Here is the project where I’m applying this pattern:

GitHub - CBenoit/genoise: Minimum viable generators on stable Rust...

@quinedot

I haven't thought through your use case yet, but just skimming, it seems you could make this change.

You are absolutely right! I initially thought that a dedicated share function was making the code easier to read:

let cloned_ptr = F::share(&ptr);

But after experimenting a bit, it’s actually not any worse to have:

let cloned_ptr = F::SharedPtr::clone(&ptr);

It actually feels more idiomatic given that Rc::clone(&ptr) and Arc::clone(&ptr) is a thing.
Not to mention it’s way easier to implement the trait now.

@quinedot

For the actual question, you probably need something like a HRTB over your GAT,

I thought about this as well, but I’m a bit unsure about how I could use one.
Incidentally, this piece of code is triggering a compiler error I never saw before that is related to higher-ranked lifetimes (without me declaring a HRTB):

error: implementation of `Send` is not general enough
  --> tests/heap.rs:88:9
   |
88 |         sync::Gn::new(|co| generator_yielding_ref(co, input))
   |         ^^^^^^^^^^^^^ implementation of `Send` is not general enough
   |
   = note: `Send` would have to be implemented for the type `&'0 str`, for any lifetime `'0`...
   = note: ...but `Send` is actually implemented for the type `&'1 str`, for some specific lifetime `'1`

error: higher-ranked lifetime error
  --> tests/heap.rs:88:9
   |
88 |         sync::Gn::new(|co| generator_yielding_ref(co, input))
   |         ^^^^^^^^^^^^^

error: could not compile `genoise` (test "genoise_tests") due to 2 previous errors

@quinedot

If you have a less contrived use-case, that may help guide exploration. Are you mapping things within your families or something like that?

That is fair. My use-case is to share a mutable memory location in order to simulate generators using async/await. The idea is to poll a Future that is is holding a special type for sharing the mutable memory location with the executor. This type provides another Future that may be used to store a yield value before yielding back to the executor using Poll::Pending. The executor takes the value from the memory location and hands it to the library user. Same idea for resuming the generator.

I’m using this GAT-based trait so that I can provide different flavors of generators without rewriting all the code using a different container.

It’s also useful to write generator code that is not relying on a specific container and that may be either Send + Sync, non-Send + Sync or even heapless depending on caller’s requirements.

However, even code that doesn’t require all this flexibility must add extra lifetime annotations now:

async fn local_generator<'a>(mut co: local::Co<'_, &'a str, usize>, input: &'a str) -> bool {
    let len = co.suspend(input).await;
    len == input.len()
}

fn produce_a_generator(input: &str) -> local::Gn<'_, '_, &str, usize, bool> {
    local::Gn::new(|co| local_generator(co, input))
}

let input = String::from("hello");
let mut g = produce_a_generator(&input);

In theory there is no need for this code to have the extra '_.
When hardcoding everything to Rc + Cell, this is what I get:

async fn local_generator<'a>(mut co: local::Co<&'a str, usize>, input: &'a str) -> bool {
    let len = co.suspend(input).await;
    len == input.len()
}

fn produce_a_generator(input: &str) -> local::Gn<'_, &str, usize, bool> {
    local::Gn::new(|co| local_generator(co, input))
}

let input = String::from("hello");
let mut g = produce_a_generator(&input);