> It is awkward in C, where the implementation has to be macro-generated.

You can avoid having the implementation be macro-generated by "hiding" the list pointers before a char payload[0]. See https://pastebin.com/DE69mbJD for an example.

The same technique is used by glibc's malloc to store metadata about the allocation right next to your data, and then recover it when you call realloc/free, without needing a separate metadata allocation.

The caveat is that the type of the pointer does not indicate provenance. For example, nothing stops you from calling list_next on an arbitrary pointer to data that is not on a list, and that would be UB. The same happens with realloc and free, where it's UB if you pass them a pointer that was not returned by the heap allocator.

▲ el_pollo_diablo 3 hours ago | parent [-]

Zero-sized arrays are not standard. Accessing an array out of bounds is UB. At the very least, you should use a flexible array member instead (char payload[];).

But even if you did that, strict aliasing implies that 'payload' can only be accessed as an array of character type. It is correct to memcpy between 'payload' and another object of arbitrary type T of the appropriate size (as list_push_ does in your example), but it is UB to access 'payload' in place as a T (as main does, by casting to struct point * and dereferencing). Oh, and 'payload' may not satisfy the alignment requirement of T.

There is no realistic strict-aliasing-abiding way around a distinct node type per payload type.

▲ Joker_vD 3 hours ago | parent | next [-]

> Accessing an array out of bounds is UB.

There is no OoB access of an array; the calculated pointer is pointing to the payload object that's residing in the malloc-returned storage right after the node struct.

I think the actual problem is the alignment; that malloc-returned storage simply can't have enough space to hold a "struct { struct node header; PAYLOAD_TYPE payload; }" (which is what the parent comment is trying to emulate) if the payload type has an alignment that's greater than the size of a pointer, and that pointer will be pointing at what would've been the padding in that struct.

▲ el_pollo_diablo 3 hours ago | parent [-]

> There is no OoB access of an array

Yes, there is. It does not matter that storage happens to be allocated beyond the end of said array. Strict aliasing implies that it is UB to reinterpret the array as anything else. And it is UB to access an array out of bounds.

Flexible array members specifically exist for these dynamically-allocated trailing arrays. They do not solve the strict aliasing problem, though.

> if the payload type has an alignment that's greater than the size of a pointer

The amount of padding is implementation-defined. The only portable guarantee is that 'payload' is aligned for its element type, char. To over-align, use _Alignas, as in:

    struct node {
        struct node *next;
        _Alignas(max_align_t) char payload[]; // Satisfies all fundamental alignment requirements
    };

▲ Joker_vD 2 hours ago | parent [-]

> It does not matter that storage happens to be allocated beyond the end of said array.

It does matter, for malloc-returned storage. You can put whatever objects you want into that storage as long as it fits and the pointer is properly aligned.

> Strict aliasing

...is not violated; memcpy takes a void pointer as its destination, sets the effective type of the storage behind it, and the treats it as an array of unsigned chars.

▲ el_pollo_diablo 2 hours ago | parent [-]

> It does matter, for malloc-returned storage. You can put whatever objects you want into that storage as long as it fits and the pointer is properly aligned.

You can certainly store an object of arbitrary type, but here it is done through a pointer to an object with pointer arithmetic going beyond the allowed bounds.

> memcpy takes a void pointer as its destination, sets the effective type of the storage behind it

And, in doing so, may very well overwrite the unspecified padding following 'payload' in the structure, thus instantly destroying the effective type of the structure object itself. Subsequent accesses to the structure or its members will be UB.

It seems to me that your argument hinges on two assumptions:

    - there is no padding following 'payload' (this would have to be statically asserted),
    - the pointer to 'payload' is indistinguishable from the pointer past the structure; in particular, provenance is not an issue.

That is a very interesting discussion.

	▲	drdexebtjl an hour ago \| parent [-]
		If payload was ever dereferenced as a char array as well, I would buy the strict aliasing argument. But it’s not, it exists as a char pointer solely for pointer arithmetic. AFAIK The purpose of strict aliasing rules is to let the compiler assume that dereferencing pointers of different types never refer to the same memory. If ISO C treats this as UB, shouldn’t ISO C be fixed?

▲ drdexebtjl 3 hours ago | parent | prev [-]

In practice you wouldn’t have the payload in the struct at all, just a fixed offset aligned with the maximum alignment, but this is more illustrative of what’s happening for an example.

IIRC GCC and Clang lets character types alias to any type. Otherwise glibc’s malloc also doesn’t abide to strict aliasing.

	▲	el_pollo_diablo 2 hours ago \| parent [-]
		> IIRC GCC and Clang lets character types alias to any type. It is always legal to access the memory representation of any object as an array of characters. The other way around (interpreting an array of characters as a T, even though it does not have effective type T) is not. > Otherwise glibc’s malloc also doesn’t abide to strict aliasing. It may not have to. From the point of view of C, malloc is special because it is part of the implementation. The compiler is free to handle UB as it sees fit. In particular, it can decide that aliasing has different semantics in malloc.c than outside it.