Impl Trait in struct without explicit generic, lifetime annotation or heap allocation

#1

I'm currently struggling to find the solution of a problem: how to create a generic structure that doesn't take any generic parameters, lifetime annotation or uses heap allocation?

The de-facto way to create a generic structure is to write:

struct Type<T: Trait> {
  field: T
}

If we want to get rid of the generic, we can instead use a dynamic reference:

struct Type<'a> {
  field: &'a dyn Trait
}

Which works because the reference also contains the length of the type we use under the hood.

If we want to get rid of the lifetime to avoid all generics in the struct, we can allocate the object on the heap:

struct Type {
  field: Box<dyn Trait>
}

But this is often not ideal because it requires heap allocation which results in costly memory accesses, and often even creating a value implementing Trait and then moving it to the heap.

So my question is: is it possible to store a dyn Trait in a struct without heap allocation nor any generic/lifetime annotation? Something that would store the value itself as well as its length, like Box<dyn Trait> does but on the stack, or like &'a dyn Trait does but without using a reference.

Thanks in advance for your help !

#2

No, because depending on the actual underlying type, your struct would have various sizes, but to use your struct in any meaningful way, the type must be known.

#3

What you essentially want is a regular generic. For the following definition:

struct Foo<T> {
    inner: T,
}

the compiler can generate code for any T and Foo<T> that codes no heap allocation and no indirection of any sort.

Which leaves me wondering: if you want generic behavior, why don't you want a generic type?

#4

I want to be able to store instances of the structure in a Vec<Type> but I cannot know in advance the generic type used in Type.

#5

You can have on-stack dyn Trait:

let concrete_type: u32 = 1;
let dyn_type: &dyn Display = &concrete_type;

but it has to involve a reference, since that's where the vtable is attached, and the level of indirection is necessary to make &dyn Trait a fixed-size type.

If you support only a limited number of types, then enum gives you a fixed-size type that reserves fixed (maximum) space for all of them.

Theoretically there could be a third option that reserves fixed maximum space and alignment like enum, but allows arbitrary dyn types, as long as they fit in the pre-allocated space. That may be doable, but you'd need unsafe hacks. You'd end up with a self-referential type, so you'd have to be careful about moves too.

1 Like
#6

Ok so the constraint for the compiler is all structs must have a fixed size?

#7

Structs don't have to have a fixed size, but when they don't have a known size, their usage is severely limited, e.g. you can't pass them by value.

#8

Looking at the answers given here, it seems it's not possible to do what I want to achieve: be able to store a Vec of my type without knowing in advance the types use in the struct and without using references.

#9

Do you have an example of this?

#10

That's because vec[n] has to work in constant time. You can't compute the offset if it can vary depending on what is already stored in the entries before it.

#11
2 Likes
#12

Thanks, I'll take a lot at this :slight_smile:

#13

The problem of storing a bunch of arbitrary-sized types in the same Vec is essentially a memory allocator. Have a look at various arena crates.

#14

You can't make a heterogeneous Vec. You can't store things of different type or size in a Vec. You either have to go with dyn Trait or pack the possible set of types into an enum.

But again, this seems like a low-level problem. This problem doesn't come up in Rust because when you think you want a heterogeneous array, you usually don't really need one and there are better solutions that you can reach for instead. What problem are you trying to solve? What's the broader context?

1 Like
#15

This is valid Rust today:

struct Type {
    field: dyn Trait,
}

But you can't do anything too interesting with Type: you can't even create one, because it doesn't have a size. It's possible with some unsafe you could use it behind a pointer, but you'd still have to choose between referencing or heap allocation. It's a valid type, but it's uninstantiable.

On nightly with feature(unsized_locals) it is possible to do some things with bare dyn Traits:

#![feature(unsized_locals)]

use std::any::Any;

fn main() {
    let x: Box<dyn Any> = Box::new(42);
    let x: dyn Any = *x;
    //  ^ unsized local variable
    //               ^^ unsized temporary
    foo(x);
}

fn foo(_: dyn Any) {}
//     ^^^^^^ unsized argument

However, this is still experimental and very limited. You can't write let x: dyn Any = 42;. You can't put dyn Traits in structs or return them from functions.

It's a long way off, but it's theoretically possible that some day we could expand on unsized_locals to allow more flexibility, and you could maybe write something like this:

#![not actual Rust code]
struct Type {
    field: dyn Any,
}

fn main() {
    let obj = Type { field: 42 };
    // or possibly
    let obj = make_type(42);
}

// Both takes and returns unsized types. This could work by returning a pointer
// under the hood and automatically copying the return value to the caller's
// stack frame. May be classified as minor magic.
fn make_type(field: dyn Any) -> Type {
    Type { field }
}

This would technically satisfy the constraints in your original question, but even this isn't magical enough to allow you to put an unsized value in a Vec, because as others have noted, Vec<T> needs T to be sized by its very definition.

Are you actually in need of a heterogeneous data structure (one where the elements can be different concrete types), or just a type-erased Vec (one where all the elements are the same type, but it's not known which)? The second thing is... kind of possible, depending on the context. (But you'd still need to use generics, trait objects, or unsafe to make it work.)

3 Likes