r372359 causes stack overflow parsing large array

[smeenai]

Bugzilla Link	45333
Resolution	FIXED
Resolved on	Jun 26, 2020 13:51
Version	10.0
OS	All
Blocks	#44654
CC	@jwf,@mclow,@tambry,@zygoloid,@tstellar
Fixed by commit(s)	c6eb584 77d76b7

Extended Description

We have some generated code which creates a large std::array. After r372359, clang appears to call AnalyzeImplicitConversions recursively for each array element, which leads to a stack overflow for a sufficiently large array. Simple repro:

$ python -c "print '#include \n static constexpr std::array a {\n %s \n};' % ',\n '.join(['0.0f']*65536)" > /tmp/test.cpp
$ clang -std=c++17 -fsyntax-only /tmp/test.cpp

Explicitly passing the size of the array (std::array<float, n>) avoids this, but it's still a regression from Clang 9.

[smeenai]

Ping.

[zygoloid]

The problem is this deduction guide:

template<class _Tp, class... _Args,
class = typename enable_if<(is_same_v<_Tp, _Args> && ...), void>::type
>
array(_Tp, _Args...)
-> array<_Tp, 1 + sizeof...(_Args)>;

The && pack expansion forms a deeply-nested AST whose depth is the array bound. We can fix this particular stack overflow (done in llvmorg-11-init-8018-g8f2d2a7cb46), but it doesn't help: after the stack overflow in AnalyzeImplicitConversions, we also overflow the stack in SequenceChecker and in constant evaluation (and I don't know how many other places).

libc++ should really switch to an approach with constant AST depth, for example using std::all_of({is_same_v<_Tp, _Args>...}).

I suppose Clang should catch and diagnose this violation of an implementation limit -- we should probably at least bound the size of fold expressions we're prepared to tolerate.

[llvmbot]

Thanks for the analysis, I'll take this on.

[tstellar]

Is there a fix for this?

[smeenai]

Sorry, this had fallen off my radar. I believe Eric's c6eb584 should have addressed it.

[tstellar]

Eric, what do you think about backporting this?

https://reviews.llvm.org/rGc6eb584c64872fbb779df14acd31c1f3947f6e52

[tstellar]

Merged: 77d76b7