Case: A lazily evaluated self-referential type for the standard library

language design
1

Rough (working) sketch: Rust Playground

Basic trait:

/// A case is a self-referential container of a value.
///
/// Cases are lazily evaluated on first access.
trait Case<'a> {
    type Output;
    
    fn get(self: Pin<&'a Self>) -> Self::Output;
}

Usage:

fn return_owned_byte_slice(bytes: Box<[u8]>) -> impl for<'a> Case<'a, &'a [u8]> {
    // (alternatively: #[case] move || { ... })
    case! {
        move {
            let bytes = bytes;
            let (header, tail) = Header::parse(&bytes);
            tail
        }
    }
}

fn get_bytes() {
    let pin = std::pin::pin!(return_owned_byte_slice(Box::new([0; 64]))); // Or Box::pin
    let tail = pin.as_ref().get();
}

Self-referential data has been a pain point for a while. Current solutions leave much to be desired, and are outside of the standard library.

Case utilizes the existing coroutine transform within the compiler to create a self-referential scope. Once pinned (either through std::pin::pin! or Box::pin), it can be evaluated and return values that reference its interior.

Case is always !Sync (it contains interior mutability) and requires a lock in threaded scenarios.

Case is dyn safe, so Box<dyn for<'a> Case<'a, &'a [u8]>> is fully supported.

2

How does this compare to Naming is hard

3 Likes
3

One thing I see is that nolife requires allocations.

1 Like
4

Interesting. How many of the nightly features are strictly needed in Case?

5

In addition to allocations, nolife also requires the implementation of the nolife::Family trait. For Case, the higher kinded type "hack" is an implementation detail.

6

The nightly features are only needed for the example implementation, the trait itself does not require any.

The hkt + unsafe binder allows passing types by value out of the coroutine. I don't see a way you could do this using a Future on stable Rust. Pass by pointer is possible with a Future but it's an extra layer of indirection.

Never type is used because why not ¯⁠\⁠_⁠(⁠ツ⁠)⁠_⁠/⁠¯. It could be replaced with std::convert::Infallible, the effect is the same.

7

If we add a trait generalizing OnceLock and OnceCell we could then express a thread-safe (Sync) Case:

#[case(std::sync::OnceLock)] move || {
    ...
}

Also Case would have to be restricted to returning Copy or Clone values. Values that are neither should be returned by reference (which is Copy).

8

Couldn't the Coroutine trait be changed to

pub trait Coroutine<R = ()> {
    type Yield<'a>;
    type Return;

    fn resume<'a>(
        self: Pin<&'a mut Self>,
        arg: R,
    ) -> CoroutineState<Self::Yield<'a>, Self::Return>;
}

Then it would be trivial to define self referential types and they would implement Send and Sync correctly.

fn return_owned_byte_slice(
    bytes: Box<[u8]>,
) -> impl for<'a> Coroutine<Yield<'a> = &'a [u8], Return = !> {
    #[coroutine]
    move || {
        let (header, tail) = Header::parse(&bytes);
        let data_to_yield: &[u8] = tail;
        loop {
            yield data_to_yield;
        }
    }
}

Playground

Edit: just realized this requires a mutable reference, so it would not work with shared references.