From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Gerd =?UTF-8?Q?M=C3=B6llmann?= Newsgroups: gmane.emacs.bugs Subject: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Date: Fri, 30 Sep 2022 16:08:36 +0200 Message-ID: References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.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="29679"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) Cc: Eli Zaretskii , 58158@debbugs.gnu.org To: Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Fri Sep 30 16:21:35 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 1oeGtR-0007Pz-0S for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 30 Sep 2022 16:21:33 +0200 Original-Received: from localhost ([::1]:36292 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oeGtP-00017L-US for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 30 Sep 2022 10:21:31 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:49176) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oeGhK-0004UG-BE for bug-gnu-emacs@gnu.org; Fri, 30 Sep 2022 10:09:11 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:43510) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1oeGhK-0004Ab-39 for bug-gnu-emacs@gnu.org; Fri, 30 Sep 2022 10:09:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1oeGhJ-0006hm-T8 for bug-gnu-emacs@gnu.org; Fri, 30 Sep 2022 10:09:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Gerd =?UTF-8?Q?M=C3=B6llmann?= Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 30 Sep 2022 14:09:01 +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.166454692625752 (code B ref 58158); Fri, 30 Sep 2022 14:09:01 +0000 Original-Received: (at 58158) by debbugs.gnu.org; 30 Sep 2022 14:08:46 +0000 Original-Received: from localhost ([127.0.0.1]:42588 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeGh3-0006hI-NG for submit@debbugs.gnu.org; Fri, 30 Sep 2022 10:08:45 -0400 Original-Received: from mail-ej1-f50.google.com ([209.85.218.50]:41814) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeGh2-0006h4-Cj for 58158@debbugs.gnu.org; Fri, 30 Sep 2022 10:08:44 -0400 Original-Received: by mail-ej1-f50.google.com with SMTP id hy2so9267583ejc.8 for <58158@debbugs.gnu.org>; Fri, 30 Sep 2022 07:08:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:cc:to:from:from:to:cc:subject:date; bh=ok+JqWNdK5ErNyPVQ8sglGPH4FEVResOXUpQGwrXT/k=; b=be/6Cx4UaDd9Z+bQa+/c/t0vxzBAeuSyH6jpbycObuCilg9XOjpuDFyxSZn0viPCIj tkWIVcLQYv0hT3GJORFePgVCFjIxxtpRHMdnlJjcGV64D4ciIkyPRbvvn8FTypl6EpeL 7cN2MlNqfiS9gdMAlX5fEDQ83LEkQlPJ28cdsUPyQQoetZ+hV9iIQ3vh180dZFWkwXYO oUyx4IeSYRWV9sdqhi+8VHReOgcVj4rckR8COR/7hRpaOZV9CmGxKiS/GeXQk4Y6nugX vWeooeHhMaS7m8IKd1ua2yYBNqkPJMV+nWWfCMfLZ9c3JZSZxr1c7mv4sqbvUp4gFSJp Zg6g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:cc:to:from:x-gm-message-state:from:to:cc:subject:date; bh=ok+JqWNdK5ErNyPVQ8sglGPH4FEVResOXUpQGwrXT/k=; b=sA4iLB3VPqgCNrlD30z9alcqnrvXJ52Ka9O9NZhTmbTcEuaNTZN3Hp2yeKZJi05HcR RdV6YpAH790I9cZ60aQgFZea7zkWf8y3ngFAB6n0389SfGreOVxJ2NpM5SkUr9SkrFde ktnHi90uo/yRsOg4Ay4xYuTFX372NfJDYM/XymC9UB+EaZ6o9hMYB2qp1UW2B8SQQLNU SGXGXCgWDKoqD3oVfEelXf/2MX5EDqjKHQBbpBwTOqYvy1YqDshjuas+nIh94ZQRvBpj W8zfNUInCk8pD6Lhnk4hvKAPzVdzA9A0Q4Xt0JP6OSlf/X8UkLCTrS8Gq5fe7YN+OHSx p1Ww== X-Gm-Message-State: ACrzQf27rZF1whfiyyzz5prvcDF86Qq07jH7Ev7r7EQM0W1YDLJ18Kko kADiAReVmDPllYSXVHfbu4rFIwsXX3U= X-Google-Smtp-Source: AMsMyM7YbAy7O+VsVJs6oz6baSeMR3u5cc8mqwKGu78dsJcFSWNGyGgq7Q0KrXneOmrcQuYbjkkfsw== X-Received: by 2002:a17:907:1b0e:b0:72f:9b43:b98c with SMTP id mp14-20020a1709071b0e00b0072f9b43b98cmr6584223ejc.710.1664546917949; Fri, 30 Sep 2022 07:08:37 -0700 (PDT) Original-Received: from Mini.fritz.box (pd9e36cee.dip0.t-ipconnect.de. [217.227.108.238]) by smtp.gmail.com with ESMTPSA id p12-20020a17090653cc00b0074150f51d86sm1221452ejo.162.2022.09.30.07.08.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 30 Sep 2022 07:08:37 -0700 (PDT) In-Reply-To: (Stefan Monnier's message of "Fri, 30 Sep 2022 09:25:29 -0400") 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:244022 Archived-At: Stefan Monnier writes: > 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). Thanks, that helps. Maybe you could also help me with the questions below? I'm assuming, from a comment somewhere, that an interval tree is an rb-tree with keys being interval start positions, and allowing duplicates. That is, if N is a node, all nodes in the subtree N->left are strictly < N, and nodes in N->right are >=. Or in a picture, if [start, end] is an interval, and we insert some intervals with the same start, we could arrive at [5, a] / \ [4, b] [6, c] /\ / \ 0 0 0 [6, d] /\ ... where 0 means null, and 6 is a duplicate start. 1. Is that correct? 2. Does the tree order duplicates in a particular way? Maybe by overlay priority, or by interval end? And, perhaps, if it doesn't order duplicates, would it be an idea to order them, maybe at some later point? I'm asking this because a successor(N) function would return nodes in the order in the tree, always, and I don't know what the order is now. 3. If my mental picture is right, we could of course end up with a tree that has degenerated to a list. Or a subtree, maybe. Do you know if that can happen?