Undecidable C++ Grammar Example

PCP.cpp

#include <algorithm>
#include <type_traits>

template <int... Ints>
struct Row {
    constexpr static bool empty = (sizeof...(Ints) == 0);
};

template <typename Upper, typename Lower>
struct Domino {
    using upper = Upper;
    using lower = Lower;
};

template <int... Ints, int... MoreInts>
auto concat(Row<Ints...>, Row<MoreInts...>) -> Row<Ints..., MoreInts...>;

template <typename Row1, typename Row2>
using Concat = decltype(concat(Row1{}, Row2{}));

template <typename Row1, typename Row2>
struct State {
    using row1 = Row1;
    using row2 = Row2;
    using is_match = std::bool_constant<!Row1::empty && std::is_same_v<Row1, Row2>>;
};

template <typename... Elems>
struct Queue;

template <typename First, typename... Rest>
struct Queue<First, Rest...> {
    using head = First;
    using pop = Queue<Rest...>;
    template <typename... Elems>
    using push = Queue<First, Rest..., Elems...>;
    constexpr static bool empty = false;
};

template <>
struct Queue<> {
    template <typename... Elems>
    using push = Queue<Elems...>;
    constexpr static bool empty = true;
};

template <int... Upper, int... Lower>
constexpr auto partial_match(Row<Upper...>, Row<Lower...>)
{
    int upper[]{0, Upper...};
    int lower[]{0, Lower...};
    auto size = std::min(sizeof...(Upper), sizeof...(Lower));
    for (std::size_t i = 1; i <= size; ++i) {
        if (upper[i] != lower[i]) {
            return false;
        }
    }
    return true;
}

template <typename Queue, typename... Dominos>
struct Match {
    using Row1 = typename Queue::head::row1;
    using Row2 = typename Queue::head::row2;
    constexpr static bool value = std::disjunction_v<
        typename Queue::head::is_match,
        std::conjunction<
            std::bool_constant<partial_match(Row1{}, Row2{})>,
            Match<typename Queue::pop::template push<
                      State<Concat<Row1, typename Dominos::upper>, Concat<Row2, typename Dominos::lower>>...>,
                Dominos...>>>;
};

template <typename... Dominos>
struct Match<Queue<>, Dominos...> {
    constexpr static bool value = false;
};

template <typename... Dominos>
struct DominoList {
    constexpr static bool match = Match<Queue<State<Row<>, Row<>>>, Dominos...>::value;
};

template <typename Dominos, typename = void>
struct ParseThis;

template <typename Dominos>
struct ParseThis<Dominos, typename std::enable_if_t<Dominos::match>> {
    using typeOrValue = int;
};

template <typename Dominos>
struct ParseThis<Dominos, typename std::enable_if_t<!Dominos::match>> {
    static constexpr int typeOrValue = 0;
};

// x is a function if a solution exists, a variable otherwise
int x(ParseThis<DominoList<
        Domino<Row<'b', 'b', 'a'>, Row<'b', 'b'>>,
        Domino<Row<'a', 'b'>, Row<'a', 'a'>>,
        Domino<Row<'a'>, Row<'b', 'a', 'a'>>>>::typeOrValue);

int main()
{
}