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

[Yuan Fu]

> On Nov 21, 2022, at 5:19 AM, Eli Zaretskii <eliz@gnu.org> wrote:
> 
>> From: Yuan Fu <casouri@gmail.com>
>> Date: Sun, 20 Nov 2022 16:53:45 -0800
>> 
>> 
>> Emacs crashed on a very large C file when c-ts-mode is on, because
>> the function building the imenu list tries to walk through the whole
>> parse tree, and end up recusing ~10k times because of how deep the parse
>> tree is. These recursive functions should have a built-in limit. Does
>> Emacs already have some way to determined the max recursion limit on
>> each system? Or should we come up with some hard-coded numbers?
> 
> Is the recursion in our code, or is it in libtree-sitter?

In our code, when we walk the parse tree.

> 
> If the former, one solution, albeit a crude one, is to track the recursion
> level and error out if it becomes too deep.  Another solution is to handle
> the stack in our code, in which case the stack can be allocated on the heap.

That’s my idea, hence my asking for a reasonable way to get a limit. I think a 
hard limit is totally reasonable, because there is no way for a “normal” parse 
tree to be 10k levels deep (that means the source program is 10k levels deep, 
ver unlikely for any program a human would write or a machine would generated). 
The one I observed is likely due to the parser misunderstanding the source (due 
to errors in the code). Plus, I don’t think any user would want to walk that 
deep into the parse tree either. If someone expects to walk that deep into a 
parse tree, her program is ill-designed.

The tree-walking function already has a limit parameter, we just need to give 
it a default value.

> Yet another solution is to replace stack-based recursive algorithm with
> queue-based iteration, like if you replace depth-first search with
> breadth-first search.

Because of reasons above, I think a hard limit is good enough.

> 
> I'm sure there are other ideas as well.

Yuan