[clang-tidy] Check request: misc-no-template-recursion

[denzor200]

clang-tidy already has misc-no-recursion check that detects recursive function calls in non-template code. However, in C++, recursion can also occur at compile time, via recursive template instantiation, which can lead to:

• Significantly increased compilation time;
• Inflated binary file size due to multiple instantiations;
• Compiler stack overflow.

Need a check that will discover direct and indirect recursion in templates.

Example direct:

template<int N> struct Factorial {
    static const int value = N * Factorial<N-1>::value;  // BAD
};

Example indirect (B → C → B):

template<typename T> struct B { using Type = typename C<T>::Type; };   // BAD
template<typename T> struct C { using Type = typename B<T>::Type; };   // BAD 

All the samples above were simplified to not have the base case.

[llvmbot]

@llvm/issue-subscribers-clang-tidy

Author: Denis Mikhailov (denzor200)

clang-tidy already has [misc-no-recursion](https://clang.llvm.org/extra/clang-tidy/checks/misc/no-recursion.html) check that detects recursive function calls in non-template code. However, in C++, recursion can also occur at compile time, via recursive template instantiation, which can lead to: - Significantly increased compilation time; - Inflated binary file size due to multiple instantiations; - Compiler stack overflow.

Need a check that will discover direct and indirect recursion in templates.

Example direct:

template<int N> struct Factorial {
    static const int value = N * Factorial<N-1>::value;  // BAD
};

Example indirect (B → C → B):

template<typename T> struct B { using Type = typename C<T>::Type; };   // BAD
template<typename T> struct C { using Type = typename B<T>::Type; };   // BAD 

All the samples above were simplified to not have the base case.

[denzor200]

Also this future check must ignore potential false positive in CRTP cases:

template<typename T>
struct Derived : Base<Derived<T>> {};