Pre-RFC: &[T: Trait] -> &dyn [Trait]

Hi all, I started work on this RFC, any and all feedback is appreciated!

Summary

We can support slices of traits by storing the v-table pointer once per slice instead of once per item. This is limited to slices where all the items have the same concrete type. In other words, the following conversion should be possible: &[T: Trait] -> &dyn [Trait]

Motivation

Suppose we are abstracting multiple API providers that do mostly the same thing. This can be almost anything where there are multiple competing products doing similar things, each with their own API. In this example I will focus on graphics APIs (i.e. DirectX, Vulkan, Metal, OpenGL, etc), since that is where I personally felt the need for this feature.

[!NOTE] This is specifically relevant when multiple implementations should be supported in a single binary. For example, bluetooth also needs multiple implementations because each platform has its own API, but you wouldn't enable more than one implementation at the same time. For these cases, a cfg switch works better than dyn.

I want to use the abstraction of a swapchain as a motivating example. A swapchain is an object that manages the presentation of rendered content to the screen. This swapchain usually contains multiple images; one that is presented to the screen, and another one that you can draw to directly. These then get swapped every frame (hence the name).

Lets start with the abstraction of an image:

trait Image {
	fn size(&self) -> (u32, u32);
}

struct DirectXImage { ... }
struct VulkanImage { ... }

impl Image for DirectXImage { ... }
impl Image for VulkanImage { ... }

This then allows us get the size of an image, without knowing the underlying API, using &dyn Image:

fn do_something_with_image(image: &dyn Image) {
	let size = image.size();
	...
	// profit
}

Now, when we try to do the same thing and abstract the swapchain, we run into an interesting issue:

trait Swapchain {
	fn images(&self) -> /* What do we return here? */
}

struct DirectXSwapchain { ... }
struct VulkanSwapchain { ... }

impl Swapchain for DirectXSwapchain { ... }
impl Swapchain for VulkanSwapchain { ... }

Associated type

The first logical thing to do seems to add an associated type, like so:

trait Swapchain {
	type Image: Image;
	fn images(&self) -> &[Self::Image];
}

However, when you try to use a dyn Swapchain, you will get the following error:

error[E0191]: the value of the associated type `Image` in `Swapchain` must be specified

This is because associated types are not object safe. We can't know the type of Image if all we have is a dyn Swapchain.

dyn Image

From the previous example we can deduce that we need Image to be dyn as well, since we have no way of knowing the concrete type. We can try some signatures, all of them with their own issues:

trait Swapchain {
	// error[E0277]: the size for values of type `dyn Image` cannot be known at compilation time
	fn images(&self) -> &[dyn Image];

	// error[E0277]: the size for values of type `[&dyn Image]` cannot be known at compilation time
	fn images(&self) -> [&dyn Image];
	
	// Good luck making an implementation that satisfies the borrow checker
	fn images(&self) -> &[&dyn Image];

	// This works, but will discuss why it's not desired below.
	fn images(&self) -> &[Box<dyn Image>];
}

Example 1 and 2 don't even compile. Example 3 looks like it would be incredibly hard to implement, if possible at all in safe rust.

Finally example 4. It works for sure, and the caller of this API probably doesn't care too much whether it's a slice of Box<dyn Image> or &dyn Image. However, lets look at the implementation instead:

struct VulkanSwapchain {
	// Cannot do this!
	// images: Vec<VulkanImage>

	// Needs to be stored like this instead
	images: Vec<Box<dyn Image>>
}

impl Swapchain for VulkanSwapchain {
	fn images(&self) -> &[Box<dyn Image>] {
		&*self.images
	}
}

Now the implementation has to deal with dyn Image objects, even though it knows exactly what type it is.

Give up and use indices?

We could of course give up and use indices instead:

trait Swapchain {
	fn image(&self, index: usize) -> &dyn Self::Image;
	fn image_count(&self) -> usize;
}

But this removes all the ergonomic benefits of having an actual slice. Iterating over these images becomes a lot more cumbersome. We seem to be having to decide whether the caller or the implementation has to deal with the workaround. I also believe there is a solution that can be the best of both worlds.

The root of the problem

The root of the problem lies in the fact that each item of the slice is it's own dyn type. This means that each item is now a fat pointer, with it's own pointer to the v-table. This increases the size of each item, making it impossible to transmute to and from a slice of a concrete type.

However, in this case we know that each and every item has the same type. So why do we need a v-table pointer for each item anyway? If we could instead make the entire slice dyn, meaning that each item shares the same v-table, we would no longer have that problem.

The solution

trait Swapchain {
	// Make the slice itself dyn instead.
	fn images(&self) -> &dyn [Image];
}

struct VulkanSwapchain {
	// Now we can still do this!
	images: Vec<VulkanImage>
}

impl Swapchain for VulkanSwapchain {
	fn images(&self) -> &dyn [Image] {
		&*self.images
	}
}

Here we can have our cake and eat it too! The caller can get a simple slice to the images, while the implementation can keep a Vec with the concrete implementation. Since the v-table pointer is now stored once per slice instead of once per item, the size of the items does not change, allowing it to easily be transmuted to a dyn version of the slice.

3 Likes

That'd require a 3-wide pointer to hold both the length and the vtable pointer. That'd probably be a fairly large change.

Maybe it'd be possible to roll a custom slice-like type on top of dyn-star instead? Or by using the metadata API: from_raw_parts in std::ptr - Rust

Well, you could at least implement index operators and iterators on DynSlice<T>.

Looks like someone already made a proof of concept dyn-slice crate

3 Likes

That would only be required for &dyn [Trait], which does not exist yet. I'm not familiar with the compiler internals, but how would that be a big change if it does not affect anything that already exists?

I did some reading on this, and dyn star seems to be about making dyn traits sized when the concrete types are pointer sized, which seems unrelated unless I'm misunderstanding.

The metadata API that you linked seems to be used by the crate you linked as well. The crate however seems cumbersome to use, having to use macros to generate constructors for your dynamic slices. And it seems to still have open soundness issues as well, which I'd say I can't blame the author for, considering the complexity of the unsafe metadata API code.

So let me ask you this: Would you prefer people to write their own unsafe slices with the unstable metadata API, or is a language feature like &dyn [Trait] a better fit? To me at least the second option seems more reasonable, especially considering how clean and simple the final example becomes.

It's a big change because all existing fat pointers are only 2-wide.

Doing this as a struct Bikeshed<'a, T>(NonNull<()>, usize, Metadata<T>, PhantomLifetime<'a>); seems fine, no?

Everything should use a library solution if possible, rather than a language one.

2 Likes

Is there any reason other than history for not having a separate narrow pointer and wide pointer type? Is it important to allow references to be a concrete type and not a generic impl NarrowOrWideRef?

The main point of this would be so the wide pointer type could be a library type consisting of a narrow pointer and metadata. There could also be a separate wide pointer type for a slice and for a trait object, which would make the "metadata" less overloaded.

This idea can be generalized as relaxing [T] to [T: ?Sized + SomeWeakerBound] with the constraint that the elements share the same Metadata, which would be included in that of the slice. I.e. <[T]>::Metadata would be something like (usize, T::Metadata).

In addition to "slice of some type which implements Trait", you'd get natural multidimensional slices, as well as slices of types with an unsized trailing field.

1 Like

Nit: They are, but become parameters of the dyn Trait. (These days you can even make them only available to Sized implementors and get rid of the extra dyn parameter, but that doesn't really address your "everything is type-erased" use case.)


There's an argument that a hypothetical &dyn [Trait] coerced from a &[T] should erase [T],[1] not T.[2] (Then dyn [Trait] could implement Trait too).

From some perspectives this is just a bikeshed over which gets the nicest ergonomics and syntax (if either).


References are magical in many ways such as built-in deref, borrow splitting, and reborrows. This would have simiilar hurdles to making Box non-magical (PureDeref and whatnot).


  1. have a pointer to <[T] as Trait>'s vtable ↩︎

  2. have a pointer to <T as Trait>'s vtable ↩︎

1 Like

Gankra has written about this before:

(which is not to say going from “2” to “many” is a trivial change)

5 Likes

Language-level support could be helpful for polymorphization passes. I would envision it starting out as a Rust ABI implementation detail with an unstable surface syntax for experimentation.

1 Like

Looking at the currently open soundness issue it seems to me this is not related to the metadata API, but rather a consequence of the poor UX for making custom pointers. The library wants to offer two nice quality of life features for making DynSlice and DynSliceMut easy to use:

  • DynSlice implements Copy, just like any shared reference implements Copy
  • DynSliceMut implements Deref<Target = DynSlice>, which allows for a sorta-implicit conversion from DynSliceMut to DynSlice, similarly to how you can pass a &mut T where a &T is expected.

The second point however differs from the actual reference conversion in an important way. While &'short &'long mut T can be reborrowed to a &'short T, the conversion implemented here is more akin to converting &'short &'long mut T to a &'short &'long T, which can then be converted to a &'long T, making it unsound.


As often happens, properly mimicking a reference API would require some sort of GAT-ified Deref trait, but that doesn't exist yet. Making this a reference would effectively be equivalent to implementing an escape-hatch for this usecase in the compiler/type system.

I'm not convinced this should actually be implemented as a reference type, but it's yet another case where it would be very useful to have a more powerful mechanism than Deref to mimic references' reborrowing.

1 Like