From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Dmitry Gutov Newsgroups: gmane.emacs.devel Subject: Re: Tree-sitter navigation time grows as sqrt(line-number) Date: Sun, 20 Aug 2023 23:26:36 +0300 Message-ID: References: <3E82D409-6903-4679-9031-939CA35791FF@gmail.com> <32507689-3b2c-ccbf-dd14-e7bf0bed1ac7@gutov.dev> <6db52945-5459-197c-405d-153ff395a824@gutov.dev> <1F7C956D-6D22-4CC1-8656-6E2A4D07D5FB@gmail.com> <69D18963-D94F-4792-9FF1-159897A99E50@gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="8669"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.13.0 Cc: emacs-devel@gnu.org To: JD Smith , Yuan Fu Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sun Aug 20 22:27:44 2023 Return-path: Envelope-to: ged-emacs-devel@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 1qXp1S-00022g-7b for ged-emacs-devel@m.gmane-mx.org; Sun, 20 Aug 2023 22:27:43 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qXp0Z-0007tF-JP; Sun, 20 Aug 2023 16:26:47 -0400 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 1qXp0X-0007ss-5F for emacs-devel@gnu.org; Sun, 20 Aug 2023 16:26:45 -0400 Original-Received: from out1-smtp.messagingengine.com ([66.111.4.25]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1qXp0U-00044o-SX for emacs-devel@gnu.org; Sun, 20 Aug 2023 16:26:44 -0400 Original-Received: from compute5.internal (compute5.nyi.internal [10.202.2.45]) by mailout.nyi.internal (Postfix) with ESMTP id 1C55E5C00C1; Sun, 20 Aug 2023 16:26:40 -0400 (EDT) Original-Received: from mailfrontend1 ([10.202.2.162]) by compute5.internal (MEProxy); Sun, 20 Aug 2023 16:26:40 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gutov.dev; h=cc :cc:content-transfer-encoding:content-type:content-type:date :date:from:from:in-reply-to:in-reply-to:message-id:mime-version :references:reply-to:sender:subject:subject:to:to; s=fm2; t= 1692563200; x=1692649600; bh=szdHTo/bwNJJ1S7sySFFhj4Ilpr06eEolT7 rdNIDkvA=; b=LL/5zqUrkrimFsmsrLY6/2hh/+CcM1yzlBgPBtGO8cqso1rqi+C F+jJwaj2QBo0El/1IW8qFJXlSCj3JeNYrLomZ4brND9hRlp3ZzRsa/0j5/eOQ05v j54nZd2guS7gLYWqjr4RFLzyyJZ78izzVkZWgSf+KFEd/LGOooHjQJkAdKUPp5SD djXxzxf+2W95vA5ni9Sjs/3WXHmHUA5sc4beXrpG1qBccznSQwxu+znTEol2fesF w1t9Q9Q0r04NwTLjgeNBwSGIGE8l7+cDjfQUr5HjX094EZcQO3ZyJlkzt/xOtmPe xWtO68gsHloGyjoqZ8JKhH/vcbR7ZbBrT/w== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :content-type:content-type:date:date:feedback-id:feedback-id :from:from:in-reply-to:in-reply-to:message-id:mime-version :references:reply-to:sender:subject:subject:to:to:x-me-proxy :x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=fm1; t= 1692563200; x=1692649600; bh=szdHTo/bwNJJ1S7sySFFhj4Ilpr06eEolT7 rdNIDkvA=; b=bPyu5e5AapNrennFu9HkRcU7dgj/oIECGpuH+vf8aO3CICIo5zB 6LXgUd/1o8jx4v7VrvwpUb89Wq0zouYddnTsN6OpOVQnSXzLs5+IFZuU2VyabKYs hC+pxd77/SVanIDHhoHXr4vDnVjKWoVwc/DyRT+9jGQk23tSB2wNDpwYkoMYsDtK +65xtHEWNelCiJSt4gSAHPtABzMwWH/TUqxRnluWTWZX3RnJXw95k5defoeManEq 32mHYSRUU7wi9NbGdFGNkf1ZL7LKCEyrw2rFbA7xdyCe4EIZV+TpV3S5NbGD2ywk y66NJ2OElhxBvL5mo9doQ6DGc5qPvL9JsHw== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedviedruddujedgudehvdcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmd enucfjughrpefkffggfgfuvfevfhfhjggtgfesthekredttdefjeenucfhrhhomhepffhm ihhtrhihucfiuhhtohhvuceoughmihhtrhihsehguhhtohhvrdguvghvqeenucggtffrrg htthgvrhhnpefhffehleejffegffeugefhkeektdffgfehjedvgeejtedtudehueffgffg feejheenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpe gumhhithhrhiesghhuthhovhdruggvvh X-ME-Proxy: Feedback-ID: i0e71465a:Fastmail Original-Received: by mail.messagingengine.com (Postfix) with ESMTPA; Sun, 20 Aug 2023 16:26:38 -0400 (EDT) Content-Language: en-US In-Reply-To: Received-SPF: pass client-ip=66.111.4.25; envelope-from=dmitry@gutov.dev; helo=out1-smtp.messagingengine.com X-Spam_score_int: -70 X-Spam_score: -7.1 X-Spam_bar: ------- X-Spam_report: (-7.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, NICE_REPLY_A=-4.279, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.devel:308996 Archived-At: On 20/08/2023 15:40, JD Smith wrote: > Looks like a winner (see below, or the gist)! Thanks all. Same here, thanks all indeed. > I do think we should consider a treesit-node-ancestors function that collects all the parent (of parent) nodes in one go into an (emacs) list, since you basically have to descend the whole tree from root to find the 1st parent anyway. Then people who want to know, e.g., “am I in an if block?” can just test node type down the full ancestor list. Of course, also, node-parent-until/while could be re-written to use node-ancestors, for some additional efficiency. Should be useful, but the speedup from traversing only once might be negated by the work of allocating the full list of Lisp objects. So it might improve only certain applications. OTOH, node-parent-until/while could be rewritten in a way that only allocates Lisp on-demand.