Class Template Argument Deduction failure

Hello everyone,
I’m writing to report what I think is an issue related to Class Template Argument Deduction (CTAD for short). Compiling this short snippet:

#include
#include

template
void printV(const std::vector& v)
{
if (v.size() == 1) {
printf("%d ", v[0]);
return;
}
int middle = v.size()/2;
printV(std::vector{v.begin(), v.end()+middle});
}

int main()
{
std::vector v = {10,1};
printV(v);
return 0;
}

will result in clang generating an infinite error report (at least, I left it running for several hours, then I stopped the process…), due to (I guess) wrongly deducted template arguments. If the “printf” line is removed, no error is generated but clang will compile for what it looks like forever (the process is constantly at 100% and does not stop after several hours).
This has been tested also with the following versions of clang: “Apple LLVM version 10.0.0 (clang-1000.10.44.4)”, “clang version 7.0.1 (Fedora 7.0.1-6.fc29)”. I also tested clang 8.0 and clang-HEAD on wandbox.org , with the same results (on wandbox.org the process gets killed after a while).
Obviously this only happens when compiling with “–std=c++17” or “–std=c++2a”.
Strangely enough, I got more or less the same results with gcc (7, 8.3 and HEAD), so my guess is that this might be related to some ambiguity either on the standard or in its interpretation. Given that as far as I know, clang and gcc are using two completely unrelated parsers and frontends.

Using () instead of {} will properly give a syntax error. So my guess is that this is related to both CTAD and uniform initialization because of std::vector having an std::initializer_list constructor. At least form what I could understand from the huge error output, it looks like the compiler is recursively instantiating std::vector with T = std::initializer_list, but this may be wrong.

If required I can provide part of the huge error output, but it can be generated by compiling the provided snippet on wandbox.

Thanks to anyone who can sort this out!

Best regards,

Lorenzo

The Clang issue is not related to CTAD. You can achieve the same “infinite” error message via explicitly (wrongly) supplied template arguments, too. Just replace

printV(std::vector{v.begin(), v.end()+middle});

with

using VI = std::vector<typename std::vector::const_iterator>;
printV(VI{v.begin(), v.end()+middle});

By the way, CTAD is behaving as intended here: you gave an initializer-list of const_iterators, and so you get a vector of const_iterators. If you didn’t want a vector of const_iterators, you should have used the sequence-container-constructor syntax (round parens), not the braced-initializer-list syntax (braces).
See also Contra CTAD” and “The Knightmare of Initialization in C++”.

Here’s an ultra-reduced test case.

[[nodiscard]] int dummy();

template

void printV(T t) {

dummy();

printV(&t);

}

int main() {

printV(42);

}

The same O(1024^2) lines of error output are produced, but much faster, because Clang doesn’t have to instantiate all those nested template types (or render their names in the error messages).

I think it might be convenient if Clang lowered the nested template limit from 1024 to, say, 32, in the case that a warning or error message has been produced already.

–Arthur

Very interesting find! You are correct that this happens due to infinite template recursion, not due to a bug in the standard. Consider:

template <typename> struct tag {};

template <typename T> void f(T a) { f(tag<T>{}); }

int main() { f(1); }

This also has infinite template recursion, but in that case, gcc and clang stop after a specified -ftemplate-depth. Seems like in your specific example this limit is somehow bypassed.

The limit is not bypassed. But the default -ftemplate-depth is 1024, so the number of messages output is (1+2+3+4+…+1023+1024), and the size of each message is O(n), so in total we’re seeing about O(102410241024) characters printed. (Except that on trunk, Clang already skips most of the messages output, which takes the size of the output back down to O(1024*1024) — that is, O(1024) messages each of size O(1024) characters.)

A local build of Clang trunk on my machine takes 148 seconds to finish printing all the messages in Lorenzo’s original test.

$ time $ROOT/llvm/build/bin/clang++ x.cc -std=c++17 2>&1 | wc

18211 8373912 128703709

real 1m28.044s

user 1m26.359s

sys 0m2.073s

–Arthur

Hi,
thanks for clarifying this. I tried to compile the above testcase on a faster system and it produced much less error output. So I guess I was just out of luck with my original code (it was more complex than the testcase I tried to create, with several levels of recursion), because it filled up my 250GB ssd and made my linux box unusable (I had errors redirected to a file). I guess that when clang hangs if “printf” line is removed is related to the same issue.

Anyway, if trunk is already giving less error output then I guess is fine, but probably lowering the nested template limit in case of error or warning would be helpful in similar cases. Especially if you’re using an IDE that does parsing/autocompletion with clang. If I try that code on clion for example, it just hangs and makes it unusable. But of course this is not a clang issue.
Thanks anyway!

Best regards,

Lorenzo