Metafunction to convert a type to an integer and vice-versa

Question

The typeid allows to assign a unique std::type_index to each type at runtime. I would like to do the same, statically using two metafunctions :

// Get a unique integral number associated with the provided type
template <class T>
struct encode_type
{
    using type = T;
    static constexpr std::size_t value = /* Metaprogramming magic */;
};

// Get the type uniquely associated with the provided value
template <std::size_t V>
struct decode_type
{
    static constexpr std::size_t value = V;
    using type = /* Metaprogramming magic */;
};

Is there a way to do that in C++11?

Boll

Why would want this, since at compile time you got the type itself? – Haplography

Excluding some evil hacks, I don't think counting (or generating other unique integers) at compile time like this is possible, unless you are willing to enumerate all the types for which this is supposed to work (tuple<Ts...>, then use the index). – Maudiemaudlin

As I have pointed out below, the answer is "no". However, the odds are you are asking for more than you actually need. Odds are you have an application in mind, and that is really what you want to try. But you did not include your overarching motivation in the above. Feel free to ask a question including what you actually want to do in another question! – Baziotes

Another potential difficulty has to do with, linkage / agreement across compilation units. Yakk already showed that you can't implement it universally for all types. It was suggested you could enumerate a global list of types for which it should work, in a tuple, but this is unattractive. You could imagine automatically accumulating a list of types for which it should work using a macro, or, better, "registering" the types lazily, i.e. at the time that the metafunctions are evaluated. But keeping the type-number pairs synced across compilation units I think would be extremely difficult. – Hilary

What do you envision should happen with shared libraries? The difference between compile time type and run time type is slightly vague in that case. While the types are fixed when the library is compiled, the order in which libraries may be compiled is not fixed. So the order in which the types are fixed is not predictable. It could, however, be possible if all types are always defined in the same order in one header file. – Beau

The integral numbers do not need to be in a given order. The only requirement is that if std::is_same<T1, T2>::value is true, then the two integral numbers associated to T1 and T2 should be the same, and if std::is_same<T1, T2>::value is false, then, the two integral number associated with T1 and T2 should be different. – Boll

Something along the lines of this and this might work, but CWG hates it, so I don't see much point. – Eula

Take a look at boost's serialization library. Deserialization has to, by definition, map data to types based on some discriminating values. Since the library already exists, they are doing something at compile time to get the effect that you want. – Beau

Answer 1

Here's a possible solution which "works" with GCC 5.2 and Clang 3.7.

I use Filip Roséen's Constexpr Meta-Container with some slight alterations. As T.C. pointed out, this may be made ill-formed in the future, so this solution is totally unreasonable in production code, but it's pretty cool for now. I'm not even sure if this is 100% standards-conformant.

// This is our meta-container
using TypeMap = atch::meta_list<class A>;

// Get a unique integral number associated with the provided type
template <class T>
struct encode_type
{
    using type = T;
    // Push T into the container and store the pre-push size
    //( requires slight change to Filip's code)
    static constexpr std::size_t value = TypeMap::push<T>();
};

// Get the type uniquely associated with the provided value
template <std::size_t V>
struct decode_type
{
    static constexpr std::size_t value = V;
    // Get the type at index V
    // (requires a small helper function addition)
    using type = decltype(TypeMap::at<V>());
};

---

The alterations I made to the original code:

template<class T, class H = meta_list, std::size_t Size = counter::value()>
static constexpr std::size_t push (
  size_type = push_state<
    typename H::template value<>::template push<T>::result
  > ()
) { return Size; } 

I modified atch::meta_list::push to return the size of the meta-container before the push. I used a template parameter with a default argument to ensure that the size is calculated before the push.

template<size_type Idx, class H = meta_list>
static constexpr auto at () -> typename H::template value<>::template at<Idx>::result;

I added a small decltype helper function in atch::meta_list in order to hide all that dependent name mess.

---

Some test code:

int main () {
    std::array<int, 4> encoded { 
        encode_type<int>::value,
        encode_type<double>::value,
        encode_type<std::string>::value,
        encode_type<float>::value
    };
  
  std::cout << "Encoding: ";
  for (auto i : encoded) std::cout << i << ", ";
  std::cout << std::endl;
  
  std::array<std::type_index, 4> decoded {
      typeid(decode_type<0>::type),  
      typeid(decode_type<1>::type),
      typeid(decode_type<2>::type),
      typeid(decode_type<3>::type),
  };
  
  std::cout << "Decoding: ";
  for (auto i : decoded) std::cout << i.name() << ", ";
  std::cout << std::endl;
}

Both Clang and GCC spew a bunch of warnings, but they both "work"!

Clang compiles, runs and outputs:

Encoding: 0, 1, 2, 3,

Decoding: i, d, NSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE, f,

GCC compiles, runs and outputs:

Encoding: 0, 1, 2, 3,

Decoding: i, d, NSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE, f,

---

Maybe you would be better with a pre-processing step...

Limitation

I'm not sure this is useful, but clearly this is fun! Thanks! – Centroid

Does this handle multiple encode_type<int> invocations? (and doesn't re-encode a new value that is) – Baziotes

@Yakk Yes, the encoding is done through the template instantiation, so multiple invocations with the same argument is a no-op. – Limitation

How would I access the value of something of type encoding type NSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE? – Adjoint

Answer 2

There are more than types in C++ than can be counted by size_t.

As proof:

template<size_t N> struct bob {};

there are exactly as many bob<X> types as there are size_t values.

template<class...> struct alice {};

now, alice<bob<1>, bob<2>> is a valid type. So is alice<alice<bob<1>>.

There are many more alice types than there are bob types.

Thus there is no injection from the set of size_t values to the set of types.

Thus any such mapping must be incomplete if bijective. You can only map some subset of types to size_t and back again.

You did not specify you only wanted to handle a subset of types, so the answer is, you cannot do what you asked.

Note that std::type_index is simply a hashable, comparable object. It is not an "index" like an integer value.

Baziotes

This argument is irrelevant. Any finite program only instantiates a finite number of types. There's no requirement that assigned integer values be consistent across programs. So for any single program there's no infinitary-related obstacle to creating a map from types to integers as the questioner is asking for. – Reck

@Reck I can instantiate more than size_t types in a single program. It would be a large program on a system with a small size_t, but it isn't hard. The assumption that the OP only wants to restrict it to types declared in the current program, or the current compilation unit, or only types which are passed to instantiated encode_type or decode_types in the current compilation unit, that is a different question than what the OP asked. – Baziotes

Angels and pinheads. I assume that the questioner would satisfied with a map to any integral type and would also be satisfied with a limitation of total size of programs. There's nothing in your argument that's any different than the ordinary relation between a formal language defined on inputs of arbitrary length and a finite implementation of that language. The implementation is always an approximation to some subset of finite length. – Reck

Answer 3

I'll give a partial solution, since I'm not interested in working out all the messy details. Use a macro that takes an argument containing the entire type definition. Now do three things with that argument (there will need to be helper macros):

• Use the argument as-is to define the type.
• Pass the argument stringified to a cryptographic hash function.
  • The output of that function will be an integer of some number of bits. No doubt because is cryptographically secure, that integer will be larger than the built-in integral types. So instead of type_id or size_t or whatnot, use your own index type; it can be a POD.
• The value of that hash function is the magic value for defining encode_type and decode_type.
  • Because of the limitation on the types in the template argument, you might have to use the address of constexpr storage holding the hash value to define decode_type.

The basic principle here is the same one use in Gödel's proof of his incompleteness theorem, namely, that a string of characters always has two interpretations, first as a member of a formal system and second as a number. (The core of the proof, incidentally, is to create a way of speaking about that number from within the formal system.)

The details of using tools readily available in a C++ tool chain are messy, to be sure. The key element, though, that makes it possible is the stringification operator #. This is analogue of the second interpretation above, that of the definition not as a member of a language, but as "just data".

Reck