Infinitely long generics

I want to implement an allocator for fixed size chunks. I feel like I took a bunch of steps each of which by itself seems reasonable, but have run into fighting the type system.

  • The allocator is generic on the size of chunk, this can be done with typenum or const generics, Allocator<N>.
  • I want a struct FixedAllocation<N> to represent returned allocations rather than just a raw pointer because I want the size in the type so it's statically known, I'm using a custom pointer-like type, and I want to panic on drop to catch users not freeing allocations (I know depending on this isn't safe, it's just a user debugging convenience).
  • I want as much static type safety as possible, so I make the allocation type generic on the type of allocator it is coming from, FixedAllocation<N, AllocatorType>. This prevents giving the allocation back to the wrong kind of allocator.
  • Also because I want as much static type safety as possible, I have a pointer-like type AllocationPointer<T, AllocationType>(*mut T, PhantomData<AllocationType>). AllocationType is used here only for type safety, so T pointers pointing into different kinds of allocations can't get mixed up with one another.
  • Now say we want to use this machinery to implement a singly linked list. Ideally, we would have something like:
struct Node<T, AllocationType> {
    data: T,
    next: AllocationPointer<Node<T>, AllocationType>

The question is how do we allocate this type. Lets try to instantiate the allocator:

let allocator = Allocator<TypeSize< Node< T, FixedAllocation<N, _> > >::new();

Note the _. The problem is the N argument to Allocator itself requires computing the size of a type that also needs Allocator. However, FixedAllocation only wants the type so that it can have a PhantomData since it being tied to the allocator type is only for type safety. The actual size of the type doesn't depend on the AllocatorType argument, so in practice the type would actually be finite size.

Full code example.

Is there a working approach that doesn't sacrifice type safety?

1 Like

I don't know how useful it is, but you can also have thin pointers with known size using *mut [T; LEN].

* mut[T; N] being a thin pointer is a useful tip. In the real situation I also need to store some additional metadata of my own, I just thought mentioning it being a thin pointer as the advantage was easier. I'll update my question.

I'm not sure I'm entirely getting all details of your requirements. In particular, I don't understand what the "chunk size" is. Is it the multiplier for how many times size_of::<T>() bytes fit in a single allocation? But it looks like you simply specify size_of::<T>() when asked for the "chunk size". In this case, however, I don't understand the difference between a FixedAllocation and an AllocationPointer.

Could you please show an example beyond your current doesnt_work() function as to how you would like to use the allocator? I.e., once you have the return value from allocator.allocate(), what can you or can you not do with it? What kind of usage should lead to a compiler error (in the name of type safety)? Do I need two distinct allocators for that?

Sorry, I was trying to bake the example down to bare bones.

The intention is the allocator can be configured via the generic parameter to be an allocator for allocations of one consistent size. It so happens in my example the size of allocation that I want is one big enough to hold a Node. I could have the allocator be templated on a specific type that it creates instead, but in my view allocators should always be working with bytes (who wants to pay for two monomorphizations for two types that are the same size?) so I ask for size_of::<Node>() size allocations rather than asking it to allocate Nodes for me.

In my real code, FixedAllocation has "ownership" of the allocation in the sense that it has a Drop implementation that panics, so you are expected to pass the allocation back into the allocator by move via the free method in order to "disarm" it. FixedAllocation is not Copy or Clone. Whereas AllocationPointer is just like a pointer whose type has been tagged, so it is Copy and Clone, and doesn't implement Drop. Also FixedAllocation is what you have to actually give the allocator to free it, whereas there is no requirement that allocators support freeing via AllocationPointer, so FixedAllocation could contain additional information AllocationPointer does not.

The goals for type safety are:

  • I should not be able to give a FixedAllocation back to a different type of allocator that also happens to produce FixedAllocations. This includes instantiations of FixedAllocator which create FixedAllocation with a different N, but we can imagine that there are other allocators besides instantiations of FixedAllocator that may also produce instances of FixedAllocation with the same N and we want to be protected against that as well.
  • I should not be able to mix up a pointer into a FixedAllocation<N> with pointers into other types of allocation. This is why AllocationPointer is generic on the allocation type.
1 Like

OK I think that's clear to me. Let me try to come up with some actual code.

One observation to make in order to simplify your situation is that an allocator only ever produces a single type of allocation. That is, the allocation type is functionally dependent on the allocator type. Thus, it can be an associated type.

Another simplifying observation is that apparently, you don't need to specify the type of any eventual pointers while constructing an allocator, nor do you need to specify it for allocating a chunk. The only time it seems relevant is when actually obtaining the pointers.

This means that you can just start with one marker type, and then build up a chain or "product" or marker types, in which you incorporate the allocation type as well as the allocation size. Finally, when you implement the pointer type, you only pass down this marker type (which already uniquely identifies the allocation type), and the type of the pointed value. This in turn obviates the need for making the pointer generic over either the allocator or the allocation type, breaking the infinite recursion.

Note how the marker type parameters K are potentially different at each level: K at a given level is always something that depends on the marker type of the level below, but it is not necessarily the same. Contrast the type shown in the compiler error with the declaration of Ptr, for instance!

Here's a playground demonstrating the relevant failure modes and the corresponding error messages.

Note that this is still not completely type-safe, just like your original implementation isn't:

  • It does not consider alignment. (That wasn't a question/concern, though, so maybe you are dealing with it elsewhere.)
  • Depending on how you implement obtaining a pointer from an allocation, it might result in allocations of the wrong size, since the T type parameter in the generic pointer type is independent of the chunk size of the allocator.
1 Like

Thanks for this, it's very thorough, the incrementally built marker type is a cool idea. Minor follow up question:

  • Is there any reason to prefer *const () to *const u8? I figured the latter is the closest to "I really have no idea what is behind this pointer it's just bytes."

I usually use *const () as the generic placeholder because it somewhat reminds me of void * in C. No particular reasons – do feel free to use *const u8 instead.