From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Yuan Fu Newsgroups: gmane.emacs.bugs Subject: bug#59426: 29.0.50; [tree-sitter] Some functions exceed maximum recursion limit Date: Mon, 21 Nov 2022 08:52:53 -0800 Message-ID: References: <837czo4f8y.fsf@gnu.org> Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3696.120.41.1.1\)) Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="3255"; mail-complaints-to="usenet@ciao.gmane.io" Cc: 59426@debbugs.gnu.org To: Eli Zaretskii Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Mon Nov 21 17:54:27 2022 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1oxA3u-0000da-JN for geb-bug-gnu-emacs@m.gmane-mx.org; Mon, 21 Nov 2022 17:54:26 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oxA3Y-0002p1-HN; Mon, 21 Nov 2022 11:54:04 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oxA3W-0002mw-BE for bug-gnu-emacs@gnu.org; Mon, 21 Nov 2022 11:54:02 -0500 Original-Received: from debbugs.gnu.org ([209.51.188.43]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1oxA3W-0004eh-1b for bug-gnu-emacs@gnu.org; Mon, 21 Nov 2022 11:54:02 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1oxA3V-0005OG-UO for bug-gnu-emacs@gnu.org; Mon, 21 Nov 2022 11:54:01 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Yuan Fu Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Mon, 21 Nov 2022 16:54:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 59426 X-GNU-PR-Package: emacs Original-Received: via spool by 59426-submit@debbugs.gnu.org id=B59426.166904958520601 (code B ref 59426); Mon, 21 Nov 2022 16:54:01 +0000 Original-Received: (at 59426) by debbugs.gnu.org; 21 Nov 2022 16:53:05 +0000 Original-Received: from localhost ([127.0.0.1]:48629 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oxA2b-0005M9-Da for submit@debbugs.gnu.org; Mon, 21 Nov 2022 11:53:05 -0500 Original-Received: from mail-pl1-f181.google.com ([209.85.214.181]:38606) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oxA2W-0005La-UU for 59426@debbugs.gnu.org; Mon, 21 Nov 2022 11:53:04 -0500 Original-Received: by mail-pl1-f181.google.com with SMTP id j12so11112711plj.5 for <59426@debbugs.gnu.org>; Mon, 21 Nov 2022 08:53:00 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=to:references:message-id:content-transfer-encoding:cc:date :in-reply-to:from:subject:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=MMlxc+oAIX8DXCz4OlDjGu6q5VV0OtNdomVNWZXx4bc=; b=pJADoCCF8zsojD5K33xS23WMeGXGA+Nlbd1nEYgXKRFRIst/Xj/hRLlC5qSwGeSmlN c0n/p99e0Abm6zAxPdnQgVCwq/pmOeJZnzIfL3N/4/WpOv3azmJIDTe0dXBFNMTr0Ury hVWJTj+udm2SNTPWgGLiupzJX5Iy11ayETGjU73c/Qe5mg73OfO4Go9nOTlrnL/VH5Jx 4SBrYuOLJhXFvO32jXqcKg68x2SOy9FSDelEsZJdOaaU2B3ahDPOn3qGET3eQyVZfp5E 6/r6g/pU3KNm4xPkei6MAH4sx1drWzTBvtkUTASESwfHn8UVSa6sqt9HedNf7UhTpj9D x/Wg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=to:references:message-id:content-transfer-encoding:cc:date :in-reply-to:from:subject:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=MMlxc+oAIX8DXCz4OlDjGu6q5VV0OtNdomVNWZXx4bc=; b=x71cbCzAmsHrEbx546Y5TTrkbdmaMX2vIfKRVX+GYXDmruIm8+z2IbMAOd+ogYgqAZ AuLdpAVPl0DsPNeVmfwnVGeByWDX5PidyjzZnls76THr0V730KcIB+oKrskyBYrFxi2M L0hItWArFBzwjvpdMY2p7DYqdcgEZIuiCP4mXo+sH3wovBhxruEsrHSyuq2Sjnk18BCC xU5sCq0X6qr6D3XxPWrgESYGYsDFmBDpFZ47RJMYnyDaAuVS4VcPxZFcnKnvjeX526wN hvwOVBCq1F13wVdLSdTWrDqr81moFKu/ydIeViIIi/J2xe1Yd02dOWhNakj6uvOTE/u6 CENQ== X-Gm-Message-State: ANoB5plEs4yN+JJGTC2mCmjWylFurjkrQHJuhLHkCEbPPgkYpXJd7Bsd pjSvwwX5k2k3jqUfrxTU0WR13sjVpUg= X-Google-Smtp-Source: AA0mqf5JNXnStfQnsWam8cPKyQbho35KE+xXmid0VDOOEeTkOOoq6kf07wfHvL03fDjIlsKisjwm9Q== X-Received: by 2002:a17:90b:48c8:b0:20b:25f6:3e30 with SMTP id li8-20020a17090b48c800b0020b25f63e30mr21566102pjb.227.1669049575201; Mon, 21 Nov 2022 08:52:55 -0800 (PST) Original-Received: from smtpclient.apple (cpe-172-117-161-177.socal.res.rr.com. [172.117.161.177]) by smtp.gmail.com with ESMTPSA id ix11-20020a170902f80b00b001788ccecbf5sm9992317plb.31.2022.11.21.08.52.54 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Mon, 21 Nov 2022 08:52:54 -0800 (PST) In-Reply-To: <837czo4f8y.fsf@gnu.org> X-Mailer: Apple Mail (2.3696.120.41.1.1) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.bugs:248549 Archived-At: > On Nov 21, 2022, at 5:19 AM, Eli Zaretskii wrote: >=20 >> From: Yuan Fu >> Date: Sun, 20 Nov 2022 16:53:45 -0800 >>=20 >>=20 >> 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? >=20 > Is the recursion in our code, or is it in libtree-sitter? In our code, when we walk the parse tree. >=20 > 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=E2=80=99s 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 =E2=80=9Cnormal=E2=80=9D 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=E2=80=99t 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. >=20 > I'm sure there are other ideas as well. Yuan=