Type Functions in C++

C++ metafunctions normally don't look like functions. What if this changed with C++11/C++14? What if metafunctions can be C++ functions? I decided to try it out.

I decided to begin with type functions. We want functions which take types as arguments and return types. Here's a type container for these functions to operate on.

template<class T>
struct Type
{
    using type = T;
};

Let's try something easy. ptr() turns a T into a T*.

template<class T>
auto ptr(Type<T>)
{
    return Type<T*>{};
}

Let's use this to declare an int**.

void testPtr1()
{
    int                                   i{};
    int*                                  p{&i};
    decltype(ptr(ptr(Type<int>{})))::type pp{&p};

    assert(typeid(pp) == typeid(int**));
}

We only "call" ptr() within decltype(); this prevents it from generating any runtime code, even in debug builds. This isn't very readable, so let's simplify the interface a bit.

static const Type<int> IntType;

#define EXTRACT_TYPE(e) decltype(e)::type

void testPtr2()
{
    int                             i{};
    int*                            p{&i};
    EXTRACT_TYPE(ptr(ptr(IntType))) pp{&p};

    assert(typeid(pp) == typeid(int**));
}

We established an approach for defining and using a type function; let's see how well this works with pattern matching.

template<class T>
auto removeCV(Type<T>)
{
    return Type<T>{};
}

template<class T>
auto removeCV(Type<const T>)
{
    return Type<T>{};
}

template<class T>
auto removeCV(Type<volatile T>)
{
    return Type<T>{};
}

template<class T>
auto removeCV(Type<const volatile T>)
{
    return Type<T>{};
}

void testRemoveCV1()
{
    EXTRACT_TYPE(ptr(removeCV(Type<int>{})))
        p1{};
    EXTRACT_TYPE(ptr(removeCV(Type<const int>{})))
        p2{};
    EXTRACT_TYPE(ptr(removeCV(Type<volatile int>{})))
        p3{};
    EXTRACT_TYPE(ptr(removeCV(Type<const volatile int>{})))
        p4{};
    EXTRACT_TYPE(ptr(Type<const volatile int>{}))
        p5{};

    assert(typeid(p1) == typeid(int*));
    assert(typeid(p2) == typeid(int*));
    assert(typeid(p3) == typeid(int*));
    assert(typeid(p4) == typeid(int*));
    assert(typeid(p5) == typeid(const volatile int*));
}

That works. Let's simplify our test case a bit.

#define ASSERT_EXTRACT_TYPE(a, b) \
    assert(typeid(EXTRACT_TYPE(a)) == typeid(b))

void testRemoveCV2()
{
    ASSERT_EXTRACT_TYPE(
        ptr(removeCV(Type<int>{})),
        int*);
    ASSERT_EXTRACT_TYPE(
        ptr(removeCV(Type<const int>{})),
        int*);
    ASSERT_EXTRACT_TYPE(
        ptr(removeCV(Type<volatile int>{})),
        int*);
    ASSERT_EXTRACT_TYPE(
        ptr(removeCV(Type<const volatile int>{})),
        int*);
    ASSERT_EXTRACT_TYPE(
        ptr(Type<const volatile int>{}),
        const volatile int*);
}

Let's try recursion. We want a function which retrieves the nth argument type from a function type.

template<int i>
using int_ = integral_constant<int, i>;

// Found it
template<class R, class A0, class... A>
auto argn(int_<0>, Type<R(A0, A...)>)
{
    return Type<A0>{};
}

// Continue search
template<int n, class R, class A0, class... A>
auto argn(int_<n>, Type<R(A0, A...)>)
{
    return argn(int_<n - 1>{}, Type<R(A...)>{});
}

void testArgn1()
{
    ASSERT_EXTRACT_TYPE(
        argn(int_<0>{}, Type<void(int, double, float)>{}),
        int);
    ASSERT_EXTRACT_TYPE(
        argn(int_<1>{}, Type<void(int, double, float)>{}),
        double);
    ASSERT_EXTRACT_TYPE(
        argn(int_<2>{}, Type<void(int, double, float)>{}),
        float);
}

argn(int_<n>{}, ...) seems a little silly; let's give it a nicer interface.

template<int n, class T>
auto argn(Type<T> t)
{
    return argn(int_<n>{}, t);
}

void testArgn2()
{
    ASSERT_EXTRACT_TYPE(
        argn<0>(Type<double(int, double, float)>{}), 
        int);
    ASSERT_EXTRACT_TYPE(
        argn<1>(Type<double(int, double, float)>{}), 
        double);
    ASSERT_EXTRACT_TYPE(
        argn<2>(Type<double(int, double, float)>{}), 
        float);
}

Let's try conditionals.

template<class T, class F>
auto if_(true_type, T t, F)
{
    return t;
}

template<class T, class F>
auto if_(false_type, T, F f)
{
    return f;
}

// demoIf's return type depends on Cond
template<class Cond>
auto demoIf(Cond c)
{
    return if_(c, Type<int>{}, Type<double**>{});
}

// Let's give the compiler more work to do
template<class Cond1, class Cond2>
auto demoNestedIf(Cond1 c1, Cond2 c2)
{
    return if_(c1,
        if_(c2,
            Type<char>{},
            Type<short>{}),
        if_(c2,
            Type<int>{},
            Type<long>{}));
}

void testIf()
{
    ASSERT_EXTRACT_TYPE(demoIf(true_type{}),  int);
    ASSERT_EXTRACT_TYPE(demoIf(false_type{}), double**);

    ASSERT_EXTRACT_TYPE(
        demoNestedIf(true_type{},  true_type{}),
        char);
    ASSERT_EXTRACT_TYPE(
        demoNestedIf(true_type{},  false_type{}),
        short);
    ASSERT_EXTRACT_TYPE(
        demoNestedIf(false_type{}, true_type{}),
        int);
    ASSERT_EXTRACT_TYPE(
        demoNestedIf(false_type{}, false_type{}),
        long);
}

We could try a type list at this point, but I'm feeling a bit ambitious. Let's try a type map.

// Each KV must be a pair. first_type and second_type must be
// default-constructable and copyable. Type<...> works well as a
// key or a value.
template<class... KV>
struct Map
{
};

// Match found
template<class K0, class V0, class... KV>
auto at(Map<pair<K0, V0>, KV...>, K0)
{
    return V0{};
}

// Continue search. Generates a compiler error if K is not
// found.
template<class KV0, class... KV, class K>
auto at(Map<KV0, KV...>, K k)
{
    return at(Map<KV...>{}, k);
}

void testMapAt()
{
    using M = Map<
        pair<int_<4>,    Type<double>>,
        pair<Type<int*>, Type<int>>,
        pair<Type<int>,  Type<int*>>>;

    ASSERT_EXTRACT_TYPE(at(M{}, int_<4>{}),    double);
    ASSERT_EXTRACT_TYPE(at(M{}, Type<int*>{}), int);
    ASSERT_EXTRACT_TYPE(at(M{}, Type<int>{}),  int*);
}

erase() takes a bit more work.

template<class KV0, class... KV1>
auto prepend(KV0, Map<KV1...>)
{
    return Map<KV0, KV1...>{};
}

// Key found
template<class K0, class V0, class... KV>
auto erase(Map<pair<K0, V0>, KV...>, K0)
{
    return Map<KV...>{};
}

// Continue search
template<class KV0, class... KV, class K>
auto erase(Map<KV0, KV...>, K k)
{
    return prepend(KV0{}, erase(Map<KV...>{}, k));
}

// End of map
template<class K>
auto erase(Map<>, K)
{
    return Map<>{};
}

void testMapErase()
{
    using M = Map<
        pair<int_<4>, Type<double>>,
        pair<Type<int*>, Type<int>>,
        pair<Type<int>, Type<int*>>>;

    // key not found
    assert(
        typeid(erase(M{}, int_<2>{})) ==
        typeid(M));

    // remove row 0, 1
    assert(
        typeid(erase(erase(M{}, int_<4>{}), Type<int*>{})) ==
        typeid(Map<pair<Type<int>, Type<int*>>>));

    // remove row 0, 2
    assert(
        typeid(erase(erase(M{}, int_<4>{}), Type<int>{})) ==
        typeid(Map<pair<Type<int*>, Type<int>>>));

    // remove row 2, 1
    assert(
        typeid(erase(erase(M{}, Type<int>{}), Type<int*>{})) ==
        typeid(Map<pair<int_<4>, Type<double>>>));
}

I'll leave insert() as an exercise.

I like how these type functions turned out; they seem a little less messy than the template struct approach. There's a lot more to template metaprogramming than just manipulating types; I plan to keep exploring.

#include <assert.h>
#include <iostream>
#include <type_traits>
#include <typeinfo>
#include <utility>

using namespace std;

... code snippets from above ...

int main()
{
    testPtr1();
    testPtr2();
    testRemoveCV1();
    testRemoveCV2();
    testArgn1();
    testArgn2();
    testIf();
    testMapAt();
    testMapErase();

    cout << "Tests passed" << endl;
}

Full source at ideone