From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: Tree Sitter (was Re: cc-mode fontification feels random) Date: Tue, 20 Jul 2021 21:28:44 -0400 Message-ID: References: <83o8cge4lg.fsf@gnu.org> <62e438b5-d27f-1d3c-69c6-11fe29a76d74@dancol.org> <83fsxsdxhu.fsf@gnu.org> <179f22a44d8.2816.cc5b3318d7e9908e2c46732289705cb0@dancol.org> <179f38c0370.2816.cc5b3318d7e9908e2c46732289705cb0@dancol.org> <236e62c2-be9b-b26d-8cd0-4b5a1a86e19a@dancol.org> <86mtqsoh3f.fsf@stephe-leake.org> <286d815e-d1a1-07ca-6696-a7f51923ab4e@piermont.com> <86wnpl6f0y.fsf@stephe-leake.org> <865yx45y7g.fsf@stephe-leake.org> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="35701"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux) Cc: "Perry E. Metzger" , emacs-devel@gnu.org To: Stephen Leake Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Wed Jul 21 03:29:38 2021 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 1m613J-00094F-7n for ged-emacs-devel@m.gmane-mx.org; Wed, 21 Jul 2021 03:29:37 +0200 Original-Received: from localhost ([::1]:57032 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1m613I-0004fK-7H for ged-emacs-devel@m.gmane-mx.org; Tue, 20 Jul 2021 21:29:36 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:35004) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1m612b-00040V-D6 for emacs-devel@gnu.org; Tue, 20 Jul 2021 21:28:53 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:50257) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1m612X-00004z-EX for emacs-devel@gnu.org; Tue, 20 Jul 2021 21:28:52 -0400 Original-Received: from pmg1.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id ACAC610020E; Tue, 20 Jul 2021 21:28:46 -0400 (EDT) Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 78B701001F3; Tue, 20 Jul 2021 21:28:45 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1626830925; bh=m2USob4VXqeSJHgiauKcUiGhs3I4pxigRceBBOSp1ws=; h=From:To:Cc:Subject:References:Date:In-Reply-To:From; b=GOxG5QdEpRBMQ2cBKaf8uWD7hIuY6QyyfEcPUtW6RrVQ2RwaF2a7hv9sJzhBvrYYj MYVqMaOpkws9OpbGvap76T+hPj77G9Dut2LdoOfzsrlL2zOBmS3moJNouqHLx7mgtw WkJ+DYXKQmM6kupuQXHk69J7TbSzJoW0Dp8D1QhkNjUv9gSYWqnA41m4/taWLM0Ke4 +uxUE1n3Fn+HFT49B17+e863sBgVtxP2/pbnMPJ36gAbR7rq8aNHlsOoEYy8G/vuO5 VMcsgTYsnfCFP2CXZXs57I3d9UC2HoOsBGvfyaMRpFtmVhhTEiNkPqI83jyCdzQ1QK 5Qq+Un1pcMF9g== Original-Received: from alfajor (unknown [216.154.29.138]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 435741205E5; Tue, 20 Jul 2021 21:28:45 -0400 (EDT) In-Reply-To: <865yx45y7g.fsf@stephe-leake.org> (Stephen Leake's message of "Tue, 20 Jul 2021 17:04:35 -0700") Received-SPF: pass client-ip=132.204.25.50; envelope-from=monnier@iro.umontreal.ca; helo=mailscanner.iro.umontreal.ca X-Spam_score_int: -42 X-Spam_score: -4.3 X-Spam_bar: ---- X-Spam_report: (-4.3 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3, 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.23 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" Xref: news.gmane.io gmane.emacs.devel:271398 Archived-At: > Alternately, you can only store the length of each token (as tree-sitter > does); then when processing queries, you have to add up all the lengths > of the preceding tokens in order to report the buffer position of the > information you are computing. That is also linear in the length of the > buffer. You can probably get better than linear performance in "the usual case" by storing the total length of the subtree at each node of the AST. It's still theoretically linear in the worst case, of course. Stefan