C++17 code to sort a list of types alphabetically at compile-time

metasort.cpp

#include <cstddef>
#include <utility>
#include <array>
#include <cstdio>
#include <string_view>

#if defined(__GNUC__)
#pragma GCC diagnostic ignored "-Wpragmas"
#pragma GCC diagnostic ignored "-Wunknown-warning-option"
#pragma GCC diagnostic ignored "-Wnon-template-friend"
#endif

namespace ustdex {
  // A constexpr swap since std::swap is not constexpr in C++17
  template <class T>
  constexpr void _mswap(T& a, T& b) noexcept {
    T t = a;
    a = b;
    b = t;
  }

  // A simple constexpr partition algorithm
  template <class T, std::size_t N>
  constexpr std::size_t _mpartition(std::array<T, N> &array, std::size_t low, std::size_t high) noexcept {
    auto pivot = array[high];
    std::size_t i = low;
    for (std::size_t j = low; j < high; ++j) {
      if (array[j] <= pivot) {
        _mswap(array[i], array[j]);
        ++i;
      }
    }
    _mswap(array[i], array[high]);
    return i;
  }

  // A simple constexpr quicksort implementation since std::sort is not constexpr in C++17
  template<class T, std::size_t N>
  constexpr void _mqsort(std::array<T, N>& array, std::size_t low = 0, std::size_t high = N-1) noexcept {
    if (low < high && high != ~std::size_t(0)) {
      std::size_t p = _mpartition(array, low, high);
      _mqsort(array, low, p-1);
      _mqsort(array, p+1, high);
    }
  }

  template <std::size_t Offset, std::size_t Suffix, std::size_t N>
  constexpr auto _mnameof_(const char (&name)[N]) noexcept {
    constexpr auto _mlength = N - 1 - Offset - Suffix;
    std::array<char, _mlength+1> result{};
    for (auto i = 0; i < _mlength; ++i) {
      result[i] = name[i+Offset];
    }
    return result;
  }

  // Get a string representing the name of a type
  template <class T>
  constexpr auto _mnameof() noexcept {
#if defined(_MSC_VER)
    return _mnameof_<29, 16>(__FUNCSIG__);
#elif defined(__clang__)
    constexpr std::size_t _moffset = sizeof("auto ustdex::_mnameof() [T = ") - 1;
    return _mnameof_<_moffset, 1>(__PRETTY_FUNCTION__);
#elif defined(__GNUC__)
    constexpr std::size_t _moffset = sizeof("constexpr auto ustdex::_mnameof() [with T = ") - 1;
    return _mnameof_<_moffset, 1>(__PRETTY_FUNCTION__);
#else
#error "unsupported compiler"
#endif
  }

  using _minfo_id = const struct _minfo*;

  // Something analogous to a compile-time std::type_index
  struct _minfo {
    const char* name_;
    std::size_t length_;
    _minfo_id id_ = this;

    constexpr std::string_view name() const noexcept {
      return std::string_view{name_, length_};
    }

    constexpr int compare(const _minfo& other) const noexcept {
      return name().compare(other.name());
    }

    constexpr auto operator==(const _minfo& other) const noexcept -> bool {
      return compare(other) == 0;
    }

    constexpr auto operator!=(const _minfo& other) const noexcept -> bool {
      return compare(other) != 0;
    }

    constexpr auto operator<(const _minfo& other) const noexcept -> bool {
      return compare(other) < 0;
    }

    constexpr auto operator>(const _minfo& other) const noexcept -> bool {
      return compare(other) > 0;
    }

    constexpr auto operator<=(const _minfo& other) const noexcept -> bool {
      return compare(other) <= 0;
    }

    constexpr auto operator>=(const _minfo& other) const noexcept -> bool {
      return compare(other) >= 0;
    }
  };

  namespace _detail {
    // The following two classes use the stateful metaprogramming trick to
    // create a spooky association between a _minfo object and the type it
    // represents.
    template <const _minfo* Id>
    struct _minfo_id_c {
      constexpr operator _minfo() const noexcept { return *Id; }
      friend auto _minfo_lookup(_minfo_id_c) noexcept;
    };

    template <class T>
    inline constexpr auto _type_mname{_mnameof<T>()};

    template <class T>
    inline constexpr _minfo _type_minfo{_type_mname<T>.data(), _type_mname<T>.size()-1};

    template <class T>
    struct _minfo_for {
      using type = T;
      static constexpr _minfo_id id = &_type_minfo<T>;

      friend auto _minfo_lookup(_minfo_id_c<id>) noexcept {
        return static_cast<_minfo_for*>(nullptr);
      }
    };

    template <_minfo_id Id>
    constexpr auto _mlookup() noexcept {
      return *_minfo_lookup(_minfo_id_c<Id>());
    }

    template <const _minfo* Id>
    using _mlookup_minfo_t = decltype(_detail::_mlookup<Id>());
  }

  // For a given type, return a _minfo object
  template <class T>
  constexpr _minfo _minfo_for() noexcept {
    return _detail::_minfo_id_c<_detail::_minfo_for<T>::id>();
  }

  template <_minfo_id Info>
  using _mtypeof_t = typename _detail::_mlookup_minfo_t<Info>::type;

  template <const auto& Info, std::size_t Idx>
  using _mtypeat_t = _mtypeof_t<Info[Idx].id_>;

  // For a list of types, return a sorted std::array of _minfo objects:
  template <class... Ts>
  constexpr auto _msort_types() noexcept {
    std::array<_minfo, sizeof...(Ts)> ids{_minfo_for<Ts>()...};
    _mqsort(ids);
    return ids;
  }

  template <class...>
  struct _mlist;

  // Convert an array of _minfo objects back into the types they represent:
  template <const auto& Info, class Indices = std::make_index_sequence<Info.size()>>
  struct _mtypes_of_;

  template <const auto& Info, std::size_t... Is>
  struct _mtypes_of_<Info, std::index_sequence<Is...>> {
    using type = _mlist<_mtypeat_t<Info, Is>...>;
  };

  template <const auto& Info>
  using _mtypes_of = typename _mtypes_of_<Info>::type;
}

int main() {
  static constexpr std::array<ustdex::_minfo, 5> ids =
    ustdex::_msort_types<int, short, float, double, char const*>();

  for (auto id : ids) {
    auto name = id.name();
    std::printf("%.*s\n", (int)name.length(), name.data());
  }

  using Actual = ustdex::_mtypes_of<ids>;
  using Expected = ustdex::_mlist<char const*, double, float, int, short>;
  static_assert(std::is_same_v<Actual, Expected>);
}