Support unsized data in `Gc`

[Others]

It'd be nice if you could store unsized data in a Gc. Not sure how to implement this

[alekratz]

I'm looking at working on this - I don't know the library well enough, but I assume that adding + ?Sized bounds in appropriate places is going to be enough to cut it, will it?

[Others]

You’ll probably need to change the allocation logic as well, since we currently pass by value (not allowed for unsized values).

I think the simplest approach is probably to add a new constructor that takes a Box, then reworking the allocation path to handle that case. (And of course changing bounds.)

Let me know what you think. I’m @Others on the rust discord as well. Feel free to DM me there if you want to talk through it with me.

[alekratz]

WIP branch: https://github.com/alekratz/shredder/tree/unsized-types

On my branch I've added ?Sized bounds to pretty much everything that makes sense to have that bound. The only minor hiccup was the wrapper types for guards of the RefCell, Mutex, and RwLock types, because of issues with how those structs are generated using the rental! crate macro. Thus, the nice wrappers for the borrow() family of methods will not work for an e.g. Gc<RefCell<dyn T>>.

This does appear to accept unsized type declarations, which is great.

@Others As far as the new Box<dyn T> constructor goes, is the goal to have something like a fn new_unsized(v: Box<T>) -> Self where T: ?Sized { ... } function in Gc? I think the main problem is how deallocation would be handled, since I don't believe a pointer given by Box::into_raw can simply be thrown through deallocate when we're done using it. We would need the pointer to know it was sourced from a Box, and then drop it like a Box normally would be dropped upon deallocation, if that makes sense. Thoughts?

[Others]

Excellent point about deallocation! I think we can adapt "DeallocationStrategy" to solve that issue? Adding a new strategy to indicate it needs reboxed and dropped

Note that we won't be able to handle non-'static data with that approach, since dropping a box runs the destructor

[Others]

Excellent point about deallocation! I think we can adapt "DeallocationStrategy" to solve that issue? Adding a new strategy to indicate it needs reboxed and dropped

Note that we won't be able to handle non-'static data with that approach, since dropping a box runs the destructor

[alekratz]

I'm working on a function that will go in the impl GcAllocator body in collector/alloc.rs that I need a little help on. This is what I have so far:

    pub fn from_box<T: Scan + ?Sized + 'static>(v: Box<T>) -> (Self, *const T) {
        let raw_ptr: *const T = Box::into_raw(v);
        let scan_ptr: *const (dyn Scan + 'static) = raw_ptr;

        todo!()
    }

But when I compile it, I'm being given errors about how I can't copy raw_ptr, because T doesn't have a size known at compile time. This is the error specifically:

error[E0277]: the size for values of type `T` cannot be known at compilation time
  --> src/collector/alloc.rs:58:53
   |
56 |     pub fn from_box<T: Scan + ?Sized + 'static>(v: Box<T>) -> (Self, *const T) {
   |                     - this type parameter needs to be `std::marker::Sized`
57 |         let raw_ptr: *const T = Box::into_raw(v);
58 |         let scan_ptr: *const (dyn Scan + 'static) = raw_ptr;
   |                                                     ^^^^^^^ doesn't have a size known at compile-time
   |
   = help: the trait `std::marker::Sized` is not implemented for `T`
   = note: to learn more, visit <https://doc.rust-lang.org/book/ch19-04-advanced-types.html#dynamically-sized-types-and-the-sized-trait>
   = note: required for the cast to the object type `dyn scan::Scan`

error: aborting due to previous error

This is confusing to me, because while this is technically true, I'm trying to copy the pointer, not the value itself. Do you know what I'm doing wrong?

[Others]

Hmmm I think this is the tricky bit of this issue. Going to write out my full thoughts--apologize if I explain stuff you already know!

Your direct issue here is that Rust only lets you make trait objects out of Sized types. This is because making a trait object out of an unsized type is tricky, for example consider if we implemented Scan for [u32] (not the slice, the array type itself). *const [u32] is a fat pointer, basically it's equivalent to (*const u32, usize), where usize is the size of the underlying data. *const dyn Scan is also a fat pointer, basically equivalent to (*const DATA, *const VTABLE). Now consider trying to turn *const [u32] into *const dyn Scan. We would need a "super-fat pointer", since we need a pointer to the data, a size, and a VTABLE. Since all instances of *const dyn Scan need to be the same size, we can't do this.

So let's forget about slices for this issue. Let's limit ourselves to trait objects. Imagine a trait T with T: Scan. We should be able to covert Box<dyn T> to Box<dyn Scan>, or at least convert *const dyn T to *const dyn Scan. This would let us create Gc<dyn T> (with some work). It would also be "trait upcasting", which is a feature that never landed (see rust-lang/rust#60900).

So as far as I can see we have three options to proceed here:

1. A clever hack to create a dyn Scan somehow (don't see an obvious path)
2. Modify the backend of the collector to not rely on trait objects (probably hard)
3. Get trait upcasting merged (I made a comment, but I'm not too optimistic)

Writing this out while a bit tired, so feel free to drop some questions.

[alekratz]

@Others thanks for the thorough explanation, I had a feeling it had to do with trait objects, sizedness, and how trait objects are represented under the hood. I can't really say I have a good solution either - I'll have to put some thought into it, too. I've also experimented with the idea of using an Any hack, but downcasting doesn't have support for unsized types. I'm pretty stumped by this one, unless you have other ideas of how it could possibly be structured.

[alekratz]

Some other thoughts: the ultimate goal is to be able to allocate a value (sized or otherwise), and then being able to coerce it to an unsized type. That is, this behavior:

let value: Gc<MyType> = Gc::new(MyType::new());  // <-- some well-defined struct
let dyn_value: Gc<dyn MyTrait> = value;   // <-- assuming MyType implements MyTrait

basically accomplishes the same thing, right? There's a couple of nightly-only traits called std::marker::Unsize (which appears to be an auto-trait) and std::ops::CoerceUnsized. I've written a small example that implements CoerceUnsized in the playground: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=3ffd1bf3c583f360dc51276e2365c9a9

I feel like I'm skipping over something, but would allow for unsized data in Gc, just like the issue in question states.

[Others]

@alekratz

I think that for nightly CoerceUnsized would work; skimming the code I don't see any obvious issues. I wouldn't be opposed to creating a nightly feature flag + nightly specific features either--I think I want that for deref stuff anyway (see #32).

For stable, I think this may still be possible. What about creating a new ToScan trait and forcing it instead of Scan. I wrote out an explanation of what I mean, but I'm not good at explaining things so I decided to write some code instead. Here's a link to the playground with a proof of concept. No promises this idea will work out in practice, but it might.

[alekratz]

@Others I'm working on implementing a ToScan trait and getting it integrated with the rest of the system using your example. Very good idea and helpful - thank you!

I think the CoerceUnsized trait implementation would also be useful outside of this issue alone, since it allows the pointer to be used more like the other smart pointers in Rust. Obviously either having a feature gate and/or nightly gate would be necessary for that but I think it'd be worthwhile to implement because it's only three or four lines.

[Others]

@alekratz Yeah totally agree that CoerceUnsized is something we want! I think we'd want a generic nightly feature, and we can hide it behind that.

As far as ToScan goes, I think we don't even need any macros, probably can write it like:

// Unsafe since `to_scan` must always be implemented as `&*self`
pub unsafe trait ToScan {
    fn to_scan(&self) -> &(dyn Scan + 'static);
}

unsafe impl<T: Scan + Sized + 'static> ToScan for T {
    fn to_scan(&self) -> &(dyn Scan + 'static) {
        &*self
    }
}

[alekratz]

@Others I figure having the macro would be a nice ergonomics feature, but if you don't think it's necessary, I won't include it.