Subject: bug#59426: 29.0.50; [tree-sitter] Some functions exceed maximum recursion limit

From: Yuan Fu <[email-masked]>
Date: Tue, 22 Nov 2022 15:19:58 -0800

> On Nov 22, 2022, at 1:08 AM, Mattias Engdegård <[email-masked]> wrote:
> 
> 21 nov. 2022 kl. 20.00 skrev Yuan Fu <[email-masked]>:
> 
>> Fortunately tree-sitter doesn’t need a deep stack. I don’t think any human-written or even machine generated source file is ever intended to parse into a tree of more than 1k level. Eg, who would write/generate a function that has thousands level of nested brackets {{{{{{{{{{{{{{{{…. ? (Unless they want to try to break the parser/compiler.) So a sane limit is more than enough, just to guard against weird source files that makes the parser (erroneously) generate very very tall trees.
> 
> Thank you, this is good to hear. (Standard minimum limits for languages such as C are quite low; for example see C99 section 5.2.4.1.)
> 
> What was the reason for the crash that prompted this bug report? Was it an 'unreasonable' C source file, a grammar mistake (using left recursion where right recursion should have been used, or vice versa), or something else?

It’s a machine generated file with syntax that tree-sitter-c can’t handle very well. The file is from bug#45248.

> 
> I hope that tree-sitter does not require a deep stack to handle C files that are merely very long or has long functions, initialisers etc; this is common for program-generated source code.

Being merely long is no problem: you’ll get a normal-height but very wide tree. The problem is when the parse tree is very tall. As I mentioned earlier, I don’t think programming language sources would produce ~10k levels nesting under normal circumstances. Having 10k function definitions don’t produce a tall tree, having 10k nested function definitions do. But who would want a program with 10k nested functions?

Yuan