Deleting rubbish
OK, I had a previous post that started this discussion but it was not very complete. It is about the heap, the block it hands out, and the cast I relied on to get between them. So I deleted that post. This is the new version of that discussion. Design story is then continued, so see the next post about text and subtext and how those structures also work together.
So, how to get the best out of a heap delivering a classic block of three members, a pointer, a size and a capacity, and how it then get used by various typed data structures.
The structures below are what I ended up with, but the full design process is outlined in full after that. To be honest the full journey is written up here so I can remember the pros and cons of each solution I tried. Note that the journey was done with Claude (Opus 5.5 Medium) pointing out the pros and cons of each option and helping with refactoring.
TLDR: The pointer type is set by a template, so a utf8block_s points at char8_t and a utf32block_s points at u32. The heap does not care about the type, only the item size. So it hands out memory_s, a block whose pointer is just u8(*)[_itemBytes_].
template <typename _item_t_, u32 _itemBytes_ = sizeof(_item_t_)>
struct _block_s
{
_item_t_* pointer{nullptr};
u32 size{0};
u32 capacity{0};
};
template <u32 _itemBytes_>
struct _block_s<void, _itemBytes_>
{
u8(*pointer)[_itemBytes_] { nullptr };
u32 size{0};
u32 capacity{0};
};
template <u32 _itemBytes_>
using memory_s = _block_s<void, _itemBytes_>;
Same three members, same 16 bytes. The heap takes and returns memory_s, and my code wants typed blocks. Originally the call sites just cast their way to the new type:
utf32Block_s utf32; memory_s& utf32AsMemory = *(memory_s*)&utf32; utf32AsMemory = u32Heap_.allocate(utf32.size); defer_(u32Heap_.deallocate(utf32AsMemory));
It worked, but every function that touched the heap had this type casting. One even used the same memory as two text types at once, with the comment “Subtle: Abusing utf7 as the same memory as the final utf8.” This is clearly messy even if it does do exactly what I wanted. A new typed variable name that was the same structure the the heap gave back.
The conversion operators, and the aliasing
I tried to make it less messy by putting the casts into _block_s itself. My commit note said “Much cleaner to add the conversions to the block class than litter the main code.” A typed block could now turn itself into a memory_s reference whenever the heap wanted one:
// Auto conversion to this block type.
// Cast the pointer to avoid triggering the reference conversion operator
inline operator _block_s<void, _itemBytes_>& () { return *(_block_s<void, _itemBytes_>*)this; }
inline operator const _block_s<void, _itemBytes_>& () const { return *(const _block_s<void, _itemBytes_>*)this; }
That second comment is its own small story. The first version wrote (_block_s<void, _itemBytes_>&)*this. A C style cast to a reference type will happily use the conversion operator you are in the middle of writing. So it called itself. Casting the pointer and then dereferencing it does not go near the operator.
Now deallocate(utf8) just worked, and the call sites were clean. I knew it was not strictly legal, so text_c.h got a guard at the top:
#if defined(__GNUC__) || defined(__clang__) #error "STRICT ALIASING VIOLATION: ... You must compile with -fno-strict-aliasing or rewrite the cast using std::bit_cast." #endif
The problem is the strict aliasing rule. C++ says an object may only be read or written through its own type, plus char and a few others. A utf8block_s and a memory_s are two different types, however identical their bytes. So the optimiser may assume a write through one can never change the other. It can keep utf8.pointer in a register while deallocate() sets the memory_s pointer to nullptr, and then use the old value.
MSVC does not optimise on that rule, which is why I never saw a problem. GCC and Clang do. So the code was correct on one compiler, by luck, and I wanted it to be correct even though the plan is to only have the code on Windows. My commit notes: “I still think C++ is stupid here. MSVC did not alias but other compilers did. Sigh.”
The ways out I did not like
I already had two possible fixes. Neither is good, and the rest are not much better.
Compile with -fno-strict-aliasing
Tell GCC and Clang to behave like MSVC and stop assuming different types never overlap.
Blocked by: the code is still not C++. It is correct only under a build switch, and a switch does not travel with a header. Anyone who drops block_s.h into their project has to know. It also turns the optimisation off for the whole build, not just my two operators.
std::bit_cast
The legal way to see the bytes of one type as another.
Blocked by: it makes a copy. bit_cast returns a new value, so you can read a block as memory but you cannot write back through it. deallocate() has to clear the caller’s block, and allocate() has to fill it. It is also a std header in a library whose whole point is no CRT. This is another C++ gem really. What does bit_cast mean to you? Cast or Copy (double sigh).
memcpy in and out
Copy the block into a memory_s, call the heap, copy it back. That is legal and the optimiser removes most of it.
Blocked by: The code was changed to memcpy instead of a cast. Every call site, two extra lines. It is blocked because its ugly and dumb.
A union of the two block types
Put the typed block and the memory_s in a union and use whichever one the call needs.
Blocked by: I had been here already with the slice. Reading the member you did not write last is fine in C and undefined in C++. Same problem as aliasing, just a different spelling. It is also a warning to have nameless unions.
A move assignment from memory
This one was also prototyped. Give the typed block an operator= that takes a memory_s&&, takes its pointer and zeroes the source.
_block_s& operator=(_block_s<void, _itemBytes_>&& memory) noexcept
{
pointer = (_item_t_*)memory.pointer;
size = memory.size;
capacity = memory.capacity;
memory.pointer = nullptr;
memory.size = 0;
memory.capacity = 0;
return *this;
}
Blocked by: two things. Declaring an operator= cost me the plain {pointer, size, capacity} brace initialiser, so I had to write a constructor to put it back. And it only goes one way. The block coming back out of allocate() was fine, but deallocate(), copy() and clear() still wanted a memory_s&, so I still needed the cast the other way. It sat commented out in block_s.h for a while.
| Attempt | Blocked by |
|---|---|
| Casts at every call site | messy; strict aliasing |
| Reference conversion operators | strict aliasing on GCC and Clang |
| -fno-strict-aliasing | still not C++; a flag does not travel with a header |
| std::bit_cast | a copy, so no write back; std in a no CRT library |
| memcpy in and out | the call site mess again |
| Union | undefined behaviour in C++ |
| Move assignment from memory | one way only; lost the brace initialiser |
Conversion during copy assignment
The fix was to stop pretending one object is two types. Each direction gets its own answer.
From the heap to my code, memory becomes a block by copying it into a new one. That is a constructor, not a cast:
// Conversion during copy assignment.
inline constexpr _block_s(const _block_s<void, _itemBytes_>& memory) :
pointer{(_item_t_*)memory.pointer}, size{memory.size}, capacity{memory.capacity} {}
inline constexpr _block_s(_block_s<void, _itemBytes_>& memory) :
pointer{(_item_t_*)memory.pointer}, size{memory.size}, capacity{memory.capacity} {}
So utf8block_s output = utf8heap_.allocate(size); builds a brand new utf8block_s from the returned memory_s. Two objects, each read through its own type. The pointer member is cast, and that is fine: casting a pointer value is not aliasing, reading an object through the wrong type is. The copy is three members and, critically, gets optimised away.
Once the block declares its own constructors it is no longer an aggregate, so the plain {pointer, size, capacity} has to be written out as a constructor too. That is the “Put back list initialiser” line in block_s.h. I added one for borrowed data at the same time, which sets the capacity to zero:
inline constexpr _block_s(_item_t_* pointer, u32 size, u32 capacity) : pointer{pointer}, size{size}, capacity{capacity} {}
inline constexpr _block_s(const _item_t_* pointer, u32 size) : pointer{(_item_t_*)pointer}, size{size}, capacity{0} {}
The memory_s side got locked down. It can not be copied, only moved:
_block_s(const _block_s&) = delete; _block_s& operator=(const _block_s&) = delete; _block_s& operator=(_block_s&&) = default;
Raw memory is the one thing I do not want two copies of lying around. It comes out of allocate() and goes straight into a typed block, and that is all it is for.
The other direction, a typed block going back to the heap, is the one the cast was really for. There I gave up on conversion altogether.
Templating the heap functions
Instead of turning a block into memory, the heap learnt to take any block whose items are the right size. The heap is already templated on _itemBytes_, so the functions that take a block back are templated on the item type as well:
template <typename _item_t_> void deallocate(_block_s<_item_t_, _itemBytes_>& oldBlock); template <typename _item_t_> void shrink(_block_s<_item_t_, _itemBytes_>& block); template <typename _item_t_> void clear(_block_s<_item_t_, _itemBytes_>& block) const; template <typename _itemTo_t_, typename _itemFrom_t_> void copy(_block_s<_itemTo_t_, _itemBytes_>& to, const _block_s<_itemFrom_t_, _itemBytes_>& from) const;
Now utf8heap_.deallocate(work) gets the caller’s actual utf8block_s by reference, through its own type. It clears the pointer, size and capacity in place. No second type anywhere, so nothing to alias.
The safety I wanted from the size check originally is still there, just in a better place. _itemBytes_ is fixed by the heap, so a utf32block_s simply does not match a 1 byte heap. And the block checks itself:
static_assert(sizeof(_item_t_) == _itemBytes_, "Block item size does not match the type.");
The two copy() types are separate on purpose, so a u8block_s can copy into a utf8block_s without anyone casting. Same item size, so memcpy is fine.
I had resisted templating these because it felt like cheating, and because of code size. In practice each one is a few lines, inlined, and there are only a handful of item types per heap. The difference is that GCC and Clang are now allowed to compile it. The #error came out a few days later, when text_c.h stopped inheriting from the block.
Then spans
Continuing the design process made the read-only source look iffy. copy() takes a const _block_s&, so copying from a borrowed string meant building a block around a const pointer with its const cast away. A _span_s is the honest type for that: a const pointer, a size and a zero capacity. So copy() got an overload that reads from one:
template <typename _itemTo_t_, typename _itemFrom_t_>
void copy(_block_s<_itemTo_t_, _itemBytes_>& to, const _span_s<_itemFrom_t_>& from) const
{
static_assert(sizeof(_itemFrom_t_) == _itemBytes_, "Span item size does not match the heap.");
_assert(from.size <= to.capacity);
memcpy(to.pointer, from.pointer, (size_t)from.size * _itemBytes);
to.size = from.size;
}
Same rule as the blocks: a new overload for a new type, not a cast to an old one.
Where that leaves it
The rule I came out with is simple. Moving data between two types is a copy into a new object, and a function that has to write into the caller’s object is templated on its type. No reference casts between structs, however identical they look.
The commented-out operators are still in block_s.h, with a note saying why, so I do not put them back in a weak moment.
That rule is also exactly where text and subtext ran into trouble. A text_c and a subtext_c are the same 16 bytes too, and I wanted one function to take either. I tried most of these ideas again before I accepted the same answer: copy, or template. That is the next post, Text, Subtext and the Sixteen Byte Problem.
