From: Yuan Fu <casouri@gmail.com>
To: Eli Zaretskii <eliz@gnu.org>
Cc: 59426@debbugs.gnu.org
Subject: bug#59426: 29.0.50; [tree-sitter] Some functions exceed maximum recursion limit
Date: Mon, 21 Nov 2022 08:52:53 -0800 [thread overview]
Message-ID: <CDDFCA51-1294-4743-93B2-92E31490F4A9@gmail.com> (raw)
In-Reply-To: <837czo4f8y.fsf@gnu.org>
> 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
next prev parent reply other threads:[~2022-11-21 16:52 UTC|newest]
Thread overview: 34+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-11-21 0:53 bug#59426: 29.0.50; [tree-sitter] Some functions exceed maximum recursion limit Yuan Fu
2022-11-21 6:40 ` Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-11-21 7:38 ` Stefan Kangas
2022-11-21 12:00 ` Mattias Engdegård
2022-11-21 13:55 ` Eli Zaretskii
2022-11-21 14:46 ` Mattias Engdegård
2022-11-21 16:43 ` Yuan Fu
2022-11-21 16:54 ` Eli Zaretskii
2022-11-21 17:10 ` Eli Zaretskii
2022-11-21 17:45 ` Eli Zaretskii
2022-11-21 18:20 ` Mattias Engdegård
2022-11-21 18:26 ` Eli Zaretskii
2022-11-21 18:59 ` Mattias Engdegård
2022-11-21 19:00 ` Yuan Fu
2022-11-22 9:08 ` Mattias Engdegård
2022-11-22 23:19 ` Yuan Fu
2022-11-23 10:40 ` Mattias Engdegård
2022-11-23 18:46 ` Yuan Fu
2022-11-23 20:01 ` Mattias Engdegård
2022-11-24 9:17 ` Yuan Fu
2022-11-24 10:24 ` Mattias Engdegård
2022-11-24 19:25 ` Yuan Fu
2022-11-24 19:28 ` Eli Zaretskii
2022-11-27 2:36 ` Yuan Fu
2022-11-24 10:24 ` Eli Zaretskii
2022-11-21 16:56 ` Mattias Engdegård
2022-11-21 17:01 ` Yuan Fu
2022-11-21 17:44 ` Eli Zaretskii
2022-11-22 1:46 ` Stefan Kangas
2022-11-22 0:27 ` Po Lu via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-11-22 8:59 ` Mattias Engdegård
2022-11-21 13:19 ` Eli Zaretskii
2022-11-21 16:52 ` Yuan Fu [this message]
2022-11-21 17:16 ` Eli Zaretskii
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CDDFCA51-1294-4743-93B2-92E31490F4A9@gmail.com \
--to=casouri@gmail.com \
--cc=59426@debbugs.gnu.org \
--cc=eliz@gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).