Collection<dyn FnOnce()> in stable?

I know it should be possible to implement it with Unsize/Pointee nightly features. But is it possible to implement such thing in stable (even if needs unsafe but still sound) at current time?

I also know that someone will tell "Just use Vec<Box<...>>", "measure perfomrnace", "why need it?", "use channels", etc.". This is more of an exercise / thought experiment to me and I want to learn more about Rust, not just use the easiest solution that works.

Let me describe my exercise. Basically it is a povider-consumed channel that sends closures but I want to avoid boxing the at all cost. Enum with variants is not an option as I want to actually work with "unknown" types. I don't need random-access, only consumption of all elements from start to end. This means that each item size can be different and they can be packed.

So, there are three problems I currently see:

  1. alignment and internal Vec<u8> reallocation.
    It can be ignored while storing the item (as items will not be used in stored state) but when consuming I can just move item to an intermediate buffer with respect to alignment. so if my assumptions are correct this problem is solvable.

  2. how to write vtable+data?
    Data is actually not a problem because item exact type+size is known when adding. but I don't see any way to do it with vtable... &dyn T has a vtable but how to extract it?

  3. how to to actually call it?
    Even if 2 is possible I still don't see how to call it after reading from the &[u8]. basically this is related to "reconstruction" of dyn FnOnce().

Is it even possible to solve above problems at this time without using nightly?

No, not really. A collection of dynamically-sized types is not possible due to fundamental reasons (memory layout); this is not merely a question of a "missing"/nightly-only feature.

Isn't memory layout basically just "size+alignment"?

Or are you talking about memory layout of the fat pointer? As I pointed out I need a way to break it into components (point 2) and restore it back (point 3). In that case I don't care what memory layout of the fat pointer.

Or did you mean something elase? Can you please explain?

You can't extract the compiler's vtable on stable AFAIK, but you can construct your own from the pre-erased type:

(compiles, but untested)

use std::ptr;
use std::mem;

#[derive(Copy,Clone)]
struct VTable {
    pub size: usize,
    /// Call the thunk.  Drops the closure in the process.
    pub call: unsafe fn(*mut ()),
    /// Drop the thunk without calling.  Do not call this if `call` has been run.
    pub drop: unsafe fn(*mut ())
}

impl VTable {
    fn new<F:FnOnce()>()->Self {
        VTable {
            size: mem::size_of::<F>(),
            call: |ptr: *mut ()| unsafe { (std::ptr::read_unaligned(ptr as *mut F))() },
            drop: |ptr: *mut ()| unsafe { let _ = std::ptr::read_unaligned(ptr as *mut F); },
        }
    }
}
1 Like

Hm... Interesting. This even might work. Thanks for the idea.

You need to use MaybeUninit<u8> at least. And preform only untyped copies when e.g. reallocating. Reading uninitialized data (such as padding bytes) as u8 is UB.

AFAIK, the plan is to never expose the actual vtables, so there's no sound way to extract one directly. I.e. building your own is probably the best shot.

2 Likes

And preform only untyped copies when e.g. reallocating.

It's actually internal Vec<u8> who will doo all of the reallocations.

Reading uninitialized data (such as padding bytes) as u8 is UB.

That's why I wrote about using intermediate buffer and copy objects with alignment there before calling them.

AFAIK, the plan is to never expose the actual vtables, so there's no sound way to extract one directly. I.e. building your own is probably the best shot.

I don't really like (but understand why it is needed) when languages hide somethig from developers. Also I don't need to know actual vtable, only how to break wide pointer and that reconstruct it. This is basically what this API is ment to do when stabilized:

What if about using a custom allocator?

If you every accidentally use a slice (for example) it's still UB. Just use MaybeUninit and rule it out IMO.

That is indeed a different thing, though it seems you're mostly reconstructing the same functionality. I threw out my playground POC and don't care to recreate it right now, but the approach in the bottom of this post to do the decontruction/reconstruction with a known implementable trait was pretty easy to knock out.

Just to elaborate on this, what's the problem with Box? It sounds like you want some sort of bump allocator for closures. If the allocator API were stable would Box<dyn FnOnce(), A> be acceptable?

1 Like

As I said it is more or less an exercise for me, I want to remove all redundancies I can. There is nothing wrong with the Box itself but by removing it and "inlining" objects we can:

  1. remove one source of indirection
  2. remove the need of per-object allocation

In theory it should be possible to create a following vector:
[alignment] [vtable] [alignment] [object data] ... [alignment] [vtable] [alignment] [object data]

Bump allocator will definitely solve this but I want to do it in stable. For nightly there is also a Pointee which AFAIK allows breaking down and reconstructing wide pointers.

If you every accidentally use a slice (for example) it's still UB. Just use MaybeUninit and rule it out IMO.

This would be a problem when I use Vec::reserve instead of Vec::resize for reallocation. With resize there should be no UB but reserve should be faster (no need to 'zero' out all memory).

I threw out my playground POC

Nice trick, detecting where vtable is stored at runtime while compiler should optimize it away. I thought to do the same but had hopes there will be a better way.

I'm not aware of any guarantees that Vec won't perform operations that require the initialized contents (as per the length) to be valid. :man_shrugging: It's not like the packed, erased values are more useful as u8, so I really don't get why you're resistant to being robust.

1 Like

Here's a POC that works by defining its own vtable. This example passes MIRI, but I make no guarantees about it being actually sound; I'm not confident enough in my unsafe skills to use anything like this for real without a proper code review by someone more knowledgable.

#[derive(Default)]
pub struct ThunkQueue<'a, Ret> {
    queue: VecDeque<mem::MaybeUninit<u8>>,
    ret: std::marker::PhantomData<dyn 'a + FnOnce()->Ret>
}

impl<'a, Ret> ThunkQueue<'a, Ret> {
    pub fn push<F:'a + FnOnce()->Ret>(&mut self, f:F) {
        self.push_raw(VTable::<'a, Ret>::for_fn::<F>());
        self.push_raw(f);
    }
    
    pub fn call_next(&mut self)->Option<Ret> {
        if self.queue.len() == 0 { return None; }
        let vtable: VTable<'a, Ret> = unsafe { self.pop_raw() };
        Some(unsafe { (vtable.call)(self) })
    }
    
    fn push_raw<T>(&mut self, val:T) {
        let val = mem::ManuallyDrop::new(val);
        unsafe {
            for b in std::slice::from_raw_parts(
                (&val) as *const mem::ManuallyDrop<T> as *const mem::MaybeUninit<u8>,
                mem::size_of::<T>()
            ) {
                self.queue.push_back(*b);
            }
        }
    }
    
    /// Safety: T must match the corresponding `push_raw` call
    unsafe fn pop_raw<T>(&mut self)->T {
        let mut uninit = mem::MaybeUninit::<T>::uninit();
        unsafe {
            for b in std::slice::from_raw_parts_mut(
                uninit.as_mut_ptr() as *mut mem::MaybeUninit<u8>,
                mem::size_of::<T>()
            ) {
                *b = self.queue.pop_front().unwrap();
            }
            uninit.assume_init()
        }
    }
}

impl<'a, Ret> Drop for ThunkQueue<'a, Ret> {
    fn drop(&mut self) {
        while self.queue.len() > 0 {
            unsafe {
                let vtable: VTable<'a, Ret> = self.pop_raw();
                (vtable.drop)(self);
            }
        }
    }
}

struct VTable<'a, Ret> {
    /// Call the thunk.  Drops the closure in the process.
    call: unsafe fn(&mut ThunkQueue<'a, Ret>)->Ret,
    /// Drop the thunk without calling.  Do not call this if `call` has been run.
    drop: unsafe fn(&mut ThunkQueue<'a, Ret>)
}

impl<'a, Ret> VTable<'a, Ret> {
    fn for_fn<F:'a + FnOnce()->Ret>()->Self {
        VTable {
            call: |q: &mut ThunkQueue<Ret>| unsafe { (q.pop_raw::<F>())() },
            drop: |q: &mut ThunkQueue<Ret>| unsafe { let _ = q.pop_raw::<F>(); },
        }
    }
}
2 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.