GNU bug report logs - #59426
29.0.50; [tree-sitter] Some functions exceed maximum recursion limit

Previous Next

Full log

Message #77 received at 59426 <at> debbugs.gnu.org (full text, mbox):

From: Yuan Fu <casouri <at> gmail.com>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Po Lu <luangruo <at> yahoo.com>, 59426 <at> debbugs.gnu.org,
 Eli Zaretskii <eliz <at> gnu.org>, Stefan Kangas <stefankangas <at> gmail.com>
Subject: Re: bug#59426: 29.0.50; [tree-sitter] Some functions exceed maximum
 recursion limit
Date: Tue, 22 Nov 2022 15:19:58 -0800

> On Nov 22, 2022, at 1:08 AM, Mattias Engdegård <mattiase <at> acm.org> wrote:
> 
> 21 nov. 2022 kl. 20.00 skrev Yuan Fu <casouri <at> gmail.com>:
> 
>> 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

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.