Traversing CRTP inheritance chain for template base classes with non-type template parameters

Question

This is a follow up to the question: Get deepest class in CRTP inheritance chain

The following code finds the first template argument which derives from the given instantiation of template CRTP base class and possibly recurses (this is just a more general solution to the previous question):

// Find the first type that matches the predicate
template <template <class T> class Predicate, class... Args>
struct FindFirstMatching {
    using Type = ...; // Default NullType
    static const bool has_match = ...; // whether there has been a match
};

// Utility class to get the deepest class in CRTP inheritance chain
template <typename T>
struct GetDeepest {
    using Type = T;
};

template <template <class...> class DT, class... T>
struct GetDeepest<DT<T...>> {
    template <class CLS>
    struct Predicate {
        static const bool value = std::is_base_of_v<DT<T...>, CLS>;
    };

    static const bool HasCRTPDerived = FindFirstMatching<Predicate, T...>::has_match;
    using DerivedT = typename FindFirstMatching<Predicate, T...>::Type;

    using Type = std::conditional_t<HasCRTPDerived, 
                                    typename GetDeepest<DerivedT>::Type, 
                                    DT<T...>>;
};

So I suppose that DT<T...> is in instantiation of CRTP base class. The problem is, it may have non-type template parameters as well, and I don't know how to cope with it in the most general way.

For example:

template <class DerivedT, bool param>
class ParamBase {
};

class Derived : public ParamBase<Derived, false> {
};

GetDeepest<ParamBase<Derived, false>>::Type == ParamBase<Derived, false>
// instead of desirable
// GetDeepest<ParamBase<Derived, false>>::Type == Derived

One of the possible solutions is to use something like type tags instead of non-type template parameters:

template <class T>
A {};

A<TrueType>;
A<FalseType>;

instead of

template <bool param>
A{};

But I believe it is not a good solution.

Also I could use something like template <class..., auto...> DT, but that would force me to use non-type template parameters in the end of parameter list. It is acceptable, but the problem is that it will fail disastrously if I forget about it.

It would be ok if I could write something like this:

template <typename T>
struct GetDeepest {
    static_assert(!IsTemplateInstantiation<T>::value);
    using Type = T;
};

My question is:

How can I generalize the code to possible non-type template parameters?

OR

How can I implement IsTemplateInstantiantion?

Edit: it seems like one cannot write template <class..., auto...> in C++17, so the latter is not an option.

Answer 1

I would go back to the first solution you proposed in your original question (the one that assumes that each non-leaf class template declares a DerivedT type that aliases its derived class). Let's recall your first implementation:

template <class T>
struct GetDeepest {
    template <class Test, class = typename Test::DerivedT>
    static std::true_type Helper(const Test&);
    static std::false_type Helper(...);

    using HelperType = decltype(Helper(std::declval<T>()));
    using Type = std::conditional_t<std::is_same_v<std::true_type, HelperType>,
                    GetDeepest<typename T::DerivedT>::Type,
                    T>;
};

You seem to be missing that leaf classes also inherit the DerivedT member type declaration from their base class. Which means that calling Helper(std::declval<D>()) will call the overload that returns std::true_type. In other words:

template <typename T>
struct A {
    using DerivedT = T;
};

struct D : A<D> {
    using DerivedT = D; // inherited from A<D>
};

As a result, when instantiating GetDeepest<D>, GetDeepest<D>::Type ends up aliasing GetDeepest<D::DerivedT>::Type which is GetDeepest<D>::Type and the compiler complains about GetDeepest<D>::Type not being a complete type since it is trying to be an alias to itself!

Therefore, we need to change our recursion stopping condition. One solution that comes into mind is:

A type T is a leaf-node in the CRTP hierarchy iff its DerivedT member type is an alias to T

And the implementation is pretty straightforward:

#include <type_traits>

// a type T is a leaf-node in the CRTP hierarchy iff:
// its DerivedT member type is an alias to T
template <typename T>
inline constexpr bool is_leaf_type_v = std::is_same_v<T, typename T::DerivedT>;

// general case:
// GetDeepest<T>::Type is an alias to GetDeepest<T::DerivedT>::Type
template <typename T, typename = void>
struct GetDeepest {
    using Type = typename GetDeepest<typename T::DerivedT>::Type;
};

// base case: when T is a leaf type
// We have reached a leaf node => GetDeepest<T>::Type is an alias to T
template <typename T>
struct GetDeepest<T, std::enable_if_t<is_leaf_type<T> > > {
    using Type = T;
};

// tests
template <class T>
struct A {
    using DerivedT = T;
};

template <class T>
struct B : public A<B<T> > {
    using DerivedT = T;
};

struct C : B<C> {
};

struct D : A<D> {
};

int main()
{
    static_assert(std::is_same<GetDeepest<A<D> >::Type, D>::value);
    static_assert(std::is_same<GetDeepest<B<C> >::Type, C>::value);
    static_assert(std::is_same<GetDeepest<A<B<C> > >::Type, C>::value);
}

This approach does not require you to state the template arguments to your class in GetDeepest (which is the main issue in your 2nd questions If I understand correctly). I think that you can also implement FindFirstMathing in a similar manner.

I would also stay away from depending on IsTemplateInstantiation to query whether a type is a leaf-type in the CRTP hierarchy or not (even if it is possible to implement). One counter-example that comes into mind is Eigen::Matrix<int, 3, 3> which is a class template CRTP leaf-type that inherits from Eigen::PlainObjectBase<Eigen::Matrix<int, 3, 3>>. Such a distinction between classes and class template instantiations is not what you are looking for.