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

From: Eli Zaretskii <[email-masked]>
Date: Mon, 21 Nov 2022 15:19:09 +0200

> From: Yuan Fu <[email-masked]>
> 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?

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.
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.

I'm sure there are other ideas as well.