From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier via "Bug reports for GNU Emacs, the Swiss army knife of text editors" Newsgroups: gmane.emacs.bugs Subject: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Date: Fri, 30 Sep 2022 09:25:29 -0400 Message-ID: References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Reply-To: Stefan Monnier Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="24885"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) Cc: Eli Zaretskii , 58158@debbugs.gnu.org To: Gerd =?UTF-8?Q?M=C3=B6llmann?= Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Fri Sep 30 15:26:42 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 1oeG2L-0006DB-IA for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 30 Sep 2022 15:26:41 +0200 Original-Received: from localhost ([::1]:46856 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oeG2K-0000In-GD for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 30 Sep 2022 09:26:40 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:39786) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oeG1i-0000GH-WC for bug-gnu-emacs@gnu.org; Fri, 30 Sep 2022 09:26:03 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:41767) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1oeG1i-0004dZ-Nx for bug-gnu-emacs@gnu.org; Fri, 30 Sep 2022 09:26:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1oeG1i-00070n-Bv for bug-gnu-emacs@gnu.org; Fri, 30 Sep 2022 09:26:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Stefan Monnier Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 30 Sep 2022 13:26:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 58158 X-GNU-PR-Package: emacs Original-Received: via spool by 58158-submit@debbugs.gnu.org id=B58158.166454434626914 (code B ref 58158); Fri, 30 Sep 2022 13:26:02 +0000 Original-Received: (at 58158) by debbugs.gnu.org; 30 Sep 2022 13:25:46 +0000 Original-Received: from localhost ([127.0.0.1]:40841 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeG1O-0006zx-IN for submit@debbugs.gnu.org; Fri, 30 Sep 2022 09:25:46 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:52786) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeG1K-0006zf-0Y for 58158@debbugs.gnu.org; Fri, 30 Sep 2022 09:25:41 -0400 Original-Received: from pmg1.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 40B031000F2; Fri, 30 Sep 2022 09:25:32 -0400 (EDT) Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id B4DD31000D0; Fri, 30 Sep 2022 09:25:30 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1664544330; bh=xru3+pAS+tv7VECc71y1UiokOcsZEtDXYzdyt9mSFEo=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=bgH6+Tatxx9C11QIWeYU1o3aVo3KgJ+SdOaUwLRipWCG7fKgjiDffzHNL/9S8bSfM 6+aElc4FXiqciBO9rwJ85hxBOm3c9WFjFmhKkLb9g6WONFMPdGs04xXw1hWMpLRtgQ sG7KMPyjhBYHcc11gQWSnXRG1lb8pUdde0ZuGFS14FLGWxLk/BaFP/ozK/RTsahnxv 5tVeF1/LCXfWGXsV4mRzmx2hco17jbHj77isqNUNL1CZtOVC3h0zYfn/ZRh6F7SXR+ vh36ckGvVDyDqwA9u+SbuCFR7vcOc61D5B3tCmreLXuSdQxINiYk8uzs6tRZkZWs8Q OcoJfLW6Ql7cQ== Original-Received: from alfajor (65-110-220-202.cpe.pppoe.ca [65.110.220.202]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 805441204B2; Fri, 30 Sep 2022 09:25:30 -0400 (EDT) In-Reply-To: ("Gerd =?UTF-8?Q?M=C3=B6llmann?="'s message of "Fri, 30 Sep 2022 07:28:26 +0200") 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" Xref: news.gmane.io gmane.emacs.bugs:244011 Archived-At: Gerd M=F6llmann [2022-09-30 07:28:26] wrote: > Stefan Monnier writes: >> I changed the code to store the `visited` bit in the work stack, but if >> you could rewrite the `interval_generator_next` along the lines of the >> code above that would be great. > Ok, I'll rewrite that :-). When I understand what that "narrowing" is > and how and for what it is used. The traversals are always bound by begin..end boundaries. Usually we know those bounds upfront (e.g. for `overlays-in` or `overlay-at`), but when doing things like `next/previous-overlay-change` one of the bounds is not know at first, so in order to try and avoid the O(N) complexity the code refines that other bound on the fly (e.g. when searching forward, after seeing an overlay that ends at POS we know that there's no point looking further than POS so we can move the end boundary to POS). > BTW, what do you think of changing function names to something a bit > shorter? I find myself constantly getting confused when reading the > code. I think an "itree_" prefix would suffice for non-static > functions, and static ones without prefix. Fine by me, yes. Stefan