From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: JD Smith Newsgroups: gmane.emacs.devel Subject: Re: Tree-sitter navigation time grows as sqrt(line-number) Date: Tue, 22 Aug 2023 17:07:19 -0400 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> <48CD64C5-CC2A-42C5-8496-33B188497B99@gmail.com> Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3731.700.6\)) 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="30102"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Dmitry Gutov , emacs-devel@gnu.org To: Yuan Fu Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Tue Aug 22 23:08:31 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 1qYYc2-0007az-OL for ged-emacs-devel@m.gmane-mx.org; Tue, 22 Aug 2023 23:08:30 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qYYbC-0003dw-3F; Tue, 22 Aug 2023 17:07:38 -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 1qYYbB-0003dm-2e for emacs-devel@gnu.org; Tue, 22 Aug 2023 17:07:37 -0400 Original-Received: from mail-oa1-x32.google.com ([2001:4860:4864:20::32]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1qYYb7-0003Gs-Ks for emacs-devel@gnu.org; Tue, 22 Aug 2023 17:07:36 -0400 Original-Received: by mail-oa1-x32.google.com with SMTP id 586e51a60fabf-1ccb58b0099so508946fac.0 for ; Tue, 22 Aug 2023 14:07:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1692738452; x=1693343252; 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=FLch6+iyu6GVZvxd75RE5kxmlW2pp9DFphSV+VIuWnk=; b=HfLXNkcWeiHpXYzaW6kC1LIfsIvX9PP+lwE/BLTT4QMeI+iN+4GVc94hxpdHBm7LaB 3dj94bknz8Vrz2swA+OXaRGV9+p9kH44oiOqt+VCD3BLXPpiAwZXovxmvWxWfftYpiTR Hfk1U+mdkpdtHg5ZfEiExx987pdSeQR57yYIN/1CGlC5t8uMNaF12M9CZjbintem/kZU ZRpKgDsFcSGATd37f+qlCSKbWjcpib/IRZ8O2dzk1gyZqCB7No4/7+T6GksJQHqMlm7a jFrEzRjJvmGgPgJ06EM7t7Ge2ECcOnnbswzAZYxiRGWxMAGpQnm4eT5aklaWoEG9CXHm Rnyw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692738452; x=1693343252; 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=FLch6+iyu6GVZvxd75RE5kxmlW2pp9DFphSV+VIuWnk=; b=WodACBUH+QcRmfttlH5Uu9xCMI9KmMca1dqAUjUUd8IxWQ/Vm/RjMFZuzi5/y1CE8o HN4eTYveCZW0w7CclGBaVFesmyaNsLbsMPllz/L91t5bAIN+zy6sxT9sq99d+lqiwkis DkWRzLyC8vHUc2NCtbSQTsefIppBx4NKWoKWfJ3aLBLQS8Us2KoN6JV7Ut3LgziSDZx3 suWVuxG6bEgRsFKEoms4VCBj1yvNt2V2Wmk+xeBgjapuGS52iGExHsEp0VZWAuW8Z18/ xamoLkVIeIuBYaHChibdK2DYxuZYdaCmqbWPlX2p1DUNgPw0baRJrK/K9Uyk76l8VcSZ zmpA== X-Gm-Message-State: AOJu0YwwSEjmcxNzkHexcn7TahTF1HyIE0EdclkGJcZKDxTzSEtFCisD zjmzaIask+1y80stN/CXSRY= X-Google-Smtp-Source: AGHT+IGLFHq2Zrf8KJnvZ6TReX8dIcXqYZjOPT/FOSeCvqOkFJ8S/2+lD5NJsh2Y2YRYce/Swvb+cw== X-Received: by 2002:a05:6871:153:b0:1bf:7e94:bbb5 with SMTP id z19-20020a056871015300b001bf7e94bbb5mr13231858oab.7.1692738451772; Tue, 22 Aug 2023 14:07:31 -0700 (PDT) Original-Received: from smtpclient.apple ([131.183.131.33]) by smtp.gmail.com with ESMTPSA id w193-20020a8149ca000000b00585e2c112fdsm3007619ywa.111.2023.08.22.14.07.30 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Tue, 22 Aug 2023 14:07:30 -0700 (PDT) In-Reply-To: <48CD64C5-CC2A-42C5-8496-33B188497B99@gmail.com> X-Mailer: Apple Mail (2.3731.700.6) Received-SPF: pass client-ip=2001:4860:4864:20::32; envelope-from=jdtsmith@gmail.com; helo=mail-oa1-x32.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.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, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=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:309116 Archived-At: > On Aug 21, 2023, at 9:41 PM, Yuan Fu wrote: >=20 >=20 >=20 >> On Aug 20, 2023, at 1:26 PM, Dmitry Gutov wrote: >>=20 >> On 20/08/2023 15:40, JD Smith wrote: >>> Looks like a winner (see below, or the gist)! Thanks all. >>=20 >> Same here, thanks all indeed. >=20 > Let=E2=80=99s run with this patch for sometime. If all goes well, = I=E2=80=99ll push to emacs-29.=20 >=20 >>=20 >>> 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., =E2=80=9C= am I in an if block?=E2=80=9D 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. >>=20 >> 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. >>=20 >> OTOH, node-parent-until/while could be rewritten in a way that only = allocates Lisp on-demand. >=20 > Yeah, node-parent is already fast, and a tree=E2=80=99s height mostly = doesn=E2=80=99t grow higher than, say, 30 levels, so I won=E2=80=99t = worry about it until some real scenario pops up. >=20 Sounds good. In the meantime I have discovered treesit-query-capture, = which is already very fast and can generate a list of all parents (of a = certain type etc.): (let* ((qry (treesit-query-compile 'python '([(argument_list) = (parameters) (list) (dictionary) (parenthesized_expression) (subscript)] @ctx))) (n (treesit-node-at (point))) (bg (treesit-node-start n)) (en (treesit-node-end n))) (treesit-query-capture 'python qry bg en t)) It is key to compile the query in advance. It=E2=80=99s actually pretty = similar in speed to the parent navigation.=