Endless recursion due to return type deduction of mutually-recursive templates

Clang Frontend
1

Hello,

The following code causes endless recursion leading to seg fault with the latest SVN.

clang tries to deduce g return type, which requires f return type, which requires g return type, repeats endlessly.

If the templates are modified to regular functions taking double, clang correctly errors upon parse:
error: function ‘g’ with deduced return type cannot be used before it is defined

return x*g(x-1);

but with templates there is no error parsing, just seg fault running.

Yaron

// Endless recursion with revision 190992.

template
auto g(T x);

template
auto f(T x) {
if (x>0)
return x*g(x-1);
else
return 1.0;
}

template
auto g(T x) {
if (x>0)
return x*f(x-1);
else
return 1.0;
}

int main() {
f(9.0);
}

2

This is not endless recursion, just a stack overflow. I get:

:2:6: fatal error: recursive template instantiation exceeded maximum depth of 256
auto g(T x);
^
:15:14: note: in instantiation of function template specialization ‘f’ requested here
return xf(x-1);
^
:7:14: note: in instantiation of function template specialization ‘g’ requested here
return xg(x-1);
^

[…]

This is not ideal, though. (There are a couple of other contexts where this kind of thing can happen, with constexpr and with decltype.) We should detect when we’re recursively instantiating a function template specialization from within itself and bail out.

3

Compiling under Visual C++ 2012 with the default stack = 1MB, the stack overflows at depth of 216 instantiations, well before the 256 limit. Either the maximum depth needs to be lower or the Visual C++ stack needs to be larger using the /STACK:number_of_bytes linker parameter.

In any case, the “recursive template instantiation exceeded maximum depth” error is followed by 256 notes where the instantiations happens…

Yaron

4

Hi,

I am not sure if this should go the llvm-cfe or here as this is a LLVM file but clang problem.

Anyway here is a patch file for HandleLLVMOptions.cmake to increase the stack size with Visual C++ to 2MB, which is more than enough to handle the default 256 template instantiations limit.

Yaron

llvm-HandleLLVMOptions-STACK.diff (566 Bytes)