Map a set of types to unique IDs and runtime reinterpret back from ID and pointer in C++17

Question

I wanted to create a relatively universal way of serialising an object, by doing a memcpy and generating a unique type ID. Stored together they can be used, for example, by another thread to restore a copy of the object for further processing.

This is used, for example, where one tread has a logging function requiring minimal overhead and converting the object to its logged state is considerably more expensive than making a raw copy.

Some other requirements / design choices:

• IDs should be dense (no gaps)
• IDs should fit the smallest unsigned possible
• No RTTI allowed
• A slight convenience overhead at the runtime restoring side is acceptable (and present in the form of the generated 'if' tree to match an ID to a type)
• Both sides have access to the definition of the mapping
• Handling of constructors with side-effects is left up to the user

Id'd love to hear any critiques or possible pitfalls! Below is the header pasted into a silly example to show the idea and interface:

// This keeps a variable in the final output:
#define KEEP(x) volatile auto x __attribute__((unused))

#include <type_traits>
#include <cstdint>
#include <cstddef>

namespace type_list {
        /**
     * @brief Extract the N-th type of a set of template arguments
     *
     * @tparam N    Index of type to extract
     * @tparam Ts   Arguments
     */
    template <std::size_t N, typename T, typename... Ts>
    struct nth_type {
        using type = typename nth_type<N-1, Ts...>::type;
    };

    template <typename T, typename... Ts>
    struct nth_type<0, T, Ts...> {
        using type = T;
    };

    /**
     * @brief Extract the N-th type of a set of template arguments
     *
     * @tparam N    Index of type to extract
     * @tparam Ts   Arguments
     */
    template <std::size_t N, typename... Ts>
    using nth_type_t = typename nth_type<N, Ts...>::type;

    /**
     * @brief Find the index of the first matching type `IN` in a set of types.
     *
     * @tparam IN   Type to find
     * @tparam T    First of type list
     * @tparam Ts   Rest of type list
     */
    template <typename IN, typename T, typename... Ts>
    struct index_of_type {
        static_assert(sizeof...(Ts) != 0 || std::is_same_v<IN, T>, "No index for type found");
        static constexpr const std::size_t value { 1 + index_of_type<IN, Ts...>::value };
    };

    template <typename IN, typename... Ts>
    struct index_of_type<IN, IN, Ts...> {
        static constexpr const std::size_t value { 0 };
    };

    /**
     * @brief Find the index of the first matching type `IN` in a set of types.
     *
     * @tparam IN   Type to find
     * @tparam Ts   Type list
     */
    template <typename IN, typename... Ts>
    static constexpr const auto index_of_type_v { index_of_type<IN, Ts...>::value };

    namespace {
        static constexpr void noop(const std::size_t = 0) {}

        template <size_t I, typename... Ts>
        struct map_visit_impl {
            template <typename F, typename E>
            static constexpr decltype(auto) visit(const std::size_t id, const void *const ptr, F func, E on_error) {
                if (id == I - 1) {
                    return func(*reinterpret_cast<const nth_type_t<I-1, Ts...> *const>(ptr));
                } else {
                    return map_visit_impl<I - 1, Ts...>::visit(id, ptr, func, on_error);
                }
            }

            template <typename F, typename E>
            static constexpr decltype(auto) visit(const std::size_t id, void *const ptr, F func, E on_error) {
                if (id == I - 1) {
                    return func(*reinterpret_cast<nth_type_t<I-1, Ts...> *const>(ptr));
                } else {
                    return map_visit_impl<I - 1, Ts...>::visit(id, ptr, func, on_error);
                }
            }
        };

        template <typename... Ts>
        struct map_visit_impl<0, Ts...> {
            template <typename F, typename E>
            static constexpr void visit(const std::size_t id, const void *const, F func, E on_error) {
                // If arrived here we have a invalid id
                on_error(id);
            }

            template <typename F, typename E>
            static constexpr void visit(const std::size_t id, void *const, F func, E on_error) {
                // If arrived here we have a invalid id
                on_error(id);
            }
        };
    }

    /**
     * @brief Create an ID map of a set of types.
     *
     * @tparam Ts Type list
     */
    template <typename... Ts>
    struct map {
        /**
         * @brief Get the type with index `N`
         *
         * @tparam N Index of type to get
         */
        template <std::size_t N>
        using type = type_list::nth_type_t<N, Ts...>;

        /**
         * @brief The ID number (index) of a given type `T`
         *
         * @tparam T
         */
        template <typename T>
        static constexpr const std::size_t id { type_list::index_of_type_v<T, Ts...> };

        /**
         * @brief Number of types stored
         */
        static constexpr const std::size_t size { sizeof...(Ts) };

        /**
         * @brief Convert any given pointer to the type matching `id` and pass
         * it to a function `func` as only argument using a `reinterpret_cast`.
         *
         * @tparam F    Function type
         * @param id    id / index of type
         * @param ptr   Storage location
         * @param func  Handler function
         * @return      Result of handler function
         */
        template <typename F, typename E = decltype(noop)>
        static constexpr decltype(auto) parse(const std::size_t id, const void *const ptr, F func, E on_error = noop) {
            return map_visit_impl<sizeof...(Ts), Ts...>::visit(id, ptr, func, on_error);
        }

        /**
         * @brief Convert any given pointer to the type matching `id` and pass
         * it to a function `func` as only argument using a `reinterpret_cast`.
         *
         * @tparam F    Function type
         * @param id    id / index of type
         * @param ptr   Storage location
         * @param func  Handler function
         * @return      Result of handler function
         */
        template <typename F, typename E = decltype(noop)>
        static constexpr decltype(auto) parse(const std::size_t id, void *const ptr, F func, E on_error = noop) {
            return map_visit_impl<sizeof...(Ts), Ts...>::visit(id, ptr, func, on_error);
        }
    };
}

// Generate unique types
template <size_t N> struct c {};

// Demo set of types
using map = type_list::map<
    uint8_t, uint16_t, uint32_t, int8_t, int16_t, int32_t,
    c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>,
    c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>,
    c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>,
    c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>,
    c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>,
    c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>,
    c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>,
    c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>,
    c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>,
    c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>, c<__COUNTER__>
>;

// Just a quick hack to initialise some test data:
char bytes[] = "Test string, bla bla";

uint64_t counter = 0;

void fn(const std::size_t n, const std::size_t i) {
    __asm volatile("# LLVM-MCA-BEGIN type_map_overhead");
    map::parse(n, &bytes[i], [&](auto& val) {
        __asm volatile("# LLVM-MCA-END");
        // Needed because the handler needs to apply to any type in the map:
        if constexpr (std::is_integral_v<decltype(val)>) {
            counter += val;
        }
    });
}

int main() {
    KEEP(k1) = map::id<uint16_t>; // size_t => 1
    KEEP(k2) = std::is_same_v<map::type<1>, uint16_t>; // bool => true

    fn(0, 0);
    fn(1, 1);
    fn(2, 2);

    KEEP(k4) = counter;
}

Answer 1

It would be nice to pass a size with the buffer, so we can check the size of the type vs the size of the buffer. Also, a pointer to unsigned char or std::byte would be better than a void*.

I think using reinterpret_cast like this is undefined behaviour. We can copy the object representation (by reinterpret_casting to char or unsigned char and copying manually, or using std::memcpy). However, the object may have alignment requirements or padding that aren't observable in this representation.

Since the character array was created as a character array, it doesn't have the necessary alignment / padding, so using it directly as if it were the object is undefined behaviour. We have to use std::memcpy to copy the bytes back into memory that was actually allocated as the object in question.

Note that std::memcpy has requirements of its own. Specifically that types be TriviallyCopyable, so constructors with side-effects will not work. It would be good to check this when serializing the object with a static_assert(is_trivially_copyable_v<T>, "...").

Answer 2

// This keeps a variable in the final output:
#define KEEP(x) volatile auto x __attribute__((unused))

Getting off to a controversial start here, aren't we? :) This macro is used only in your test harness main(), so it should be defined way down at the bottom of the file, right above main(). That way the reader doesn't get scared that your actual library functionality requires such a wacky macro.

In general, you should make it clearer which part of your code is the library and which part is the test harness. Consider adding #ifdef TESTING around the harness code, which, IIUC, basically begins at the line

// Generate unique types

---

If all you're using KEEP for is to "keep a variable in the final output," why don't you just make the variable global? That is, replace

int main() {
    KEEP(k1) = map::id<uint16_t>; // size_t => 1
    KEEP(k2) = std::is_same_v<map::type<1>, uint16_t>; // bool => true

    fn(0, 0);
    fn(1, 1);
    fn(2, 2);

    KEEP(k4) = counter;
}

with simply

size_t k1 = map::id<uint16_t>;  // should be 1
bool k2 = std::is_same_v<map::type<1>, uint16_t>;  // should be true
size_t k4 = 0;

int main() {
    fn(0, 0);
    fn(1, 1);
    fn(2, 2);

    k4 = counter;  // should be ???
}

Since other translation units might access k1, k2, and k4 by name, the compiler has to keep them around. No volatile or __attribute__ needed!

---

void fn(const std::size_t n, const std::size_t i) {

Lose the meaningless consts. They just make your function prototype harder to read. (Personally, I would also lose the std::s; they aren't needed. But some people like them, and if you're such a person, I won't argue.)

void fn(size_t n, size_t i) {

So much cleaner! Now we even have room to give n and i real names, if we want to.

---

FWIW, I don't understand the purpose of the __asm volatile comments.

---

map::parse(n, &bytes[i], [&](auto& val) {
    __asm volatile("# LLVM-MCA-END");
    // Needed because the handler needs to apply to any type in the map:
    if constexpr (std::is_integral_v<decltype(val)>) {
        counter += val;
    }
});

It is highly unusual to write a generic lambda that takes a parameter of type auto&. Pass-by-value auto, sure. Pass-by-forwarding-reference auto&&, sure. Pass-by-const-ref const auto&, quite plausibly. But pass-by-nonconst-ref auto&? That's a weird one. Are you sure that's what you want? In generic code you usually want auto&& for perfect forwarding.

Since decltype(val) is always a reference type, it's never an integral type. Do you observe this if constexpr branch ever being taken? I don't think it is being taken. What was its purpose supposed to be?

---

static constexpr void noop(const std::size_t = 0) {}

What is the purpose of the default function argument here? I would prefer to see this as

static void noop(size_t) {}

or, even better if you care about inlining,

struct Noop { void operator()(size_t) const {} };

And then down where you use noop:

template <typename F, typename E = decltype(noop)>
static constexpr decltype(auto) parse(const std::size_t id, const void *const ptr, F func, E on_error = noop) {
    return map_visit_impl<sizeof...(Ts), Ts...>::visit(id, ptr, func, on_error);
}

this would be better optimizable if you wrote it as

template<class F, class E = Noop>
static constexpr decltype(auto) parse(size_t id, const void *ptr, F func, E on_error = E()) {
    return map_visit_impl<sizeof...(Ts), Ts...>::visit(id, ptr, func, on_error);
}

And if you really care about efficiency, and don't want to burden your end-user with wrapping their error handler in std::ref() all the time, then you'll break with STL tradition and either pass the error handler by reference, or move-out-of it (instead of copying it) when you pass it by value:

template<class F, class E = Noop>
static constexpr decltype(auto) parse(size_t id, const void *ptr, const F& func, const E& on_error = E()) {
    return map_visit_impl<sizeof...(Ts), Ts...>::visit(id, ptr, func, on_error);
}

or

template<class F, class E = Noop>
static constexpr decltype(auto) parse(size_t id, const void *ptr, F func, E on_error = E()) {
    return map_visit_impl<sizeof...(Ts), Ts...>::visit(id, ptr, std::move(func), std::move(on_error));
}

---

template <typename IN, typename... Ts>
static constexpr const auto index_of_type_v { index_of_type<IN, Ts...>::value };

This is the weirdest way of writing

template<class T, class... Ts>
inline constexpr size_t index_of_type_v = index_of_type<T, Ts...>::value;

that I've ever seen. :)

---

    /*
     * @tparam F    Function type
     * @param id    id / index of type
     * @param ptr   Storage location
     * @param func  Handler function
     * @return      Result of handler function

You know, if you renamed ptr to storage and renamed func to handler, then you could get rid of this comment. (Self-documenting code!)

---

return func(*reinterpret_cast<const nth_type_t<I-1, Ts...> *const>(ptr));

As I mentioned in a comment on user673679's answer, you should avoid reinterpret_cast whenever possible. It's a big red flag that makes the reader wonder what trickery you're doing. So, if you're not doing any trickery, you should avoid waving that red flag unnecessarily.

Also, as usual, you've got useless consts that merely clutter the code.

return func(*static_cast<const nth_type_t<I-1, Ts...> *>(ptr));

---

Both index_of_type and map_visit_impl are done with recursive template instantiations. You should consider how to rewrite them as non-recursive templates using pack expansion and/or fold-expressions. Especially map_visit_impl, since function instantiation is basically the slowest thing you can ask a compiler to do. See this blog post for inspiration if you need it.