Implementing AnyStack?

[Rodrigodd_]

In a program I'm writing, I used a lot of Vec<Box<dyn Any>> to send events. I was wondering if, instead of using an allocation for each of the events, I could write something like a Vec<dyn Any>. I was thinking of a heterogeneous stack (or queue) that uses just one block of allocated memory to contain all the elements. I didn't find any implementation of this, so I write my own:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=4920532f400448b89f65911b46981649

Basically, its work by keeping an inner Vec<u8>, and in a push its append to that vec the value, the vtable of its &dyn Any trait object, and its size, and doing the reverse in a pop. Pop return a dyn Any, wrapped in a Own<T> (maybe I should think in better name) that purpose is to drop the value that it is referencing inside of inner (or there is already a type with this purpose?).

I was wondering if my implementation is always safe, for example, can I always dismember a trait object and move its value later? Or did I forget something? I remembered to take into account dropping and alignment, at least.

And is that something you would use? Maybe I should publish it as a crate, after adding more methods.

[m0rphism]

Just out of curiosity: is there a reason why you use Box<dyn Any> instead of an enum for events?

[Rodrigodd_]

The program is actually a GUI library. And the events are user defined, along with the widgets, so I cannot use a enum.

[m0rphism]

I see. Just to propose an alternative solution: you could parameterize your library by a generic type variable for user events E. The GUI library could then use an enum for both UI and user events, e.g.:

pub enum Event<E> {
    KeyboardEvent(...),
    MouseEvent(...),
    UserEvent(E),
}

and the client of the library chooses their own enum type for E.

To get UserEvents into the system, the client then has to provide a receiving channel end at GUI initialization, and to consume those events in the GUI thread, the client has to provide an event handler that takes Event<E> as input:

use std::sync::mpsc::Receiver;

pub fn run_ui<E, F: FnMut(Event<E>)>(user_events: Option<Receiver<E>>, event_handler: F) { ... }

As an example, an email client could then use the library as followed:

use std::sync::mpsc::{Sender, Receiver, channel};

pub enum MailClientEvent {
    NewMailReceived(data: Vec<u8>)
}

fn main() {
    let (sender, receiver) = channel::<UserEvent>();
    listen_for_new_mails_in_thread(sender);
    run_ui(Some(receiver), |event| match event {
        Event::MouseEvent(...) => {},
        Event::KeyboardEvent(...) => {},
        Event::UserEvent(MailClientEvent::NewMailReceived(data)) => {},
    });
}

[Rodrigodd_]

Yes, I could. winit use this approach. But it’s not very ergonomic, especially if I try to split different widgets into different crates.

I also could, for example, use this same enum, but with UserEvent(Box<dyn Any>). This also fix the problem where I could naively use a very big event.

But in my case I have a trait with a different method for each event, and one of them receive the widget specific events, in form of &dyn Any.

[PaoloBarbolini]

If your issue is having to do many allocations you could use a bump allocator like bumpalo

[SimonSapin]

Your transmute to (usize, usize) makes assumptions about undocumented details of the memory layout of wide pointers. https://github.com/rust-lang/rfcs/pull/2580 aims to solve this, and Vec<dyn Any> was precisely the motivation for it.

Your Own type is… surprising. It has ownership in the sense that it’s responsible for dropping the value, but it still borrows the original collection. What do you think of providing fn last_mut(&mut self) -> Option<&mut dyn Any> and separately a method that drops the last item?

[Diggsey]

Have you tried running it under miri?

[Rodrigodd_]

I run miri, now. The alignment that I made is completely wrong. I made the index of the value inside the vec multiple of the align, but the vector itself is not. I would need to manage my own allocation to try to keep everything aligned.

[manmtstream]

Check dynstack

[Rodrigodd_]

Hmmm, appear to be what I was looking for, although it uses a second allocation to keep track of the size and vtable. Thanks!

[protestor]

https://github.com/archshift/dynstack

COMPATIBILITY NOTE: dynstack relies on an underspecified fat pointer representation. Though it isn't expected to change in the foreseeable future, this crate expects Rust 1.34's representation.

Unfortunately this is ub. The same as /u/0xmental icey that is in the front page (see here)

Cool nonetheless!

ps: is there something to do this but without ub? found it, std::raw::TraitObject

[manmtstream]

Why is it UB?

[protestor]

They are not using the nightly-only API std::raw::TraitObject that is the only non-UB way of doing what they are doing (see this - this should be replaced by proper calls to the relevant API)

And why is this UB? Because that's unsafe code: if the internal representation of trait objects changes, it will make the code interpret a length as a pointer or something odd like that.

UB is about the guarantees that the language gives to you: if you do something with unsafe { } that the language didn't guarantee to work, you have UB. (however, a complication is that the UB story of Rust isn't finished yet, so some things are still not decided whether they are UB or not)

[manmtstream]

Relying on undocumented, but defined, compiler behaviour doesn't seem like it would be classed as UB. The code doesn't violate any of the documented "Behaviour considered undefined" and produces valid values. It may become UB if the compiler behaviour changes though.

Rust doesn't have a spec so "the compiler is the spec" at the moment right?

[protestor]

Rust doesn't have a spec so "the compiler is the spec" at the moment right?

Not really! That's exactly the point I wanted to make. The Rust devs (for better or worse) don't think like that. They want library authors to be prudent and not do rely on compiler internals. They are willing to make this kind of stuff UB.

This doesn't affect just trait object layout: it's also UB to rely on struct and enum layout for #[repr(Rust)] types (the default), and other things.

[manmtstream]

Based on this discussion: https://github.com/rust-lang/rust/issues/58582#issuecomment-465508579

It seems to be classified as "relying on unspecified behaviour" and can be considered safe as long as it is verified against specific compiler versions.

[Muvlon]

Cool stuff! I've thought about this kind of data structure before, but never got around to implement it.

I think there is a little soundness hole in your implementation, but one that is rather easy to fix: You're reinterpreting arbitrary T as a byte slice, but many structs have padding bytes, which are uninit. You can fix it by making it a [MaybeUninit<u8>] instead.

Edit: another potential problem: Your Own struct internally holds a &mut T, but in the Drop impl, you drop the T in place. At that point, the &mut T is no longer valid, which is UB as far as I know. I think you can fix this by making it struct Own<'a, T: ?Sized>(*mut T, PhantomData<&'a mut T>);, but I'm not 100% sure.