From unknown Wed Sep 10 12:14:41 2025 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Mailer: MIME-tools 5.509 (Entity 5.509) Content-Type: text/plain; charset=utf-8 From: bug#58158 <58158@debbugs.gnu.org> To: bug#58158 <58158@debbugs.gnu.org> Subject: Status: 29.0.50; [overlay] Interval tree iteration considered harmful Reply-To: bug#58158 <58158@debbugs.gnu.org> Date: Wed, 10 Sep 2025 19:14:41 +0000 retitle 58158 29.0.50; [overlay] Interval tree iteration considered harmful reassign 58158 emacs submitter 58158 Gerd M=C3=B6llmann severity 58158 normal thanks From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 29 01:29:33 2022 Received: (at submit) by debbugs.gnu.org; 29 Sep 2022 05:29:33 +0000 Received: from localhost ([127.0.0.1]:35625 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odm73-0003YU-5h for submit@debbugs.gnu.org; Thu, 29 Sep 2022 01:29:33 -0400 Received: from lists.gnu.org ([209.51.188.17]:41622) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odm71-0003YM-Ah for submit@debbugs.gnu.org; Thu, 29 Sep 2022 01:29:32 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:36076) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odm71-0006NL-3N for bug-gnu-emacs@gnu.org; Thu, 29 Sep 2022 01:29:31 -0400 Received: from mail-ej1-x629.google.com ([2a00:1450:4864:20::629]:42874) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1odm6z-0004rI-B0 for bug-gnu-emacs@gnu.org; Thu, 29 Sep 2022 01:29:30 -0400 Received: by mail-ej1-x629.google.com with SMTP id sb3so473756ejb.9 for ; Wed, 28 Sep 2022 22:29:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:message-id:date:subject:to:from:from:to:cc:subject :date; bh=GFy0XUzk9kF13HDNytI7kwW/pnisRSbc85c+9TbWBOE=; b=qyrnAOEdjGmiDoxPuhPtLqeetn82xeNijRPVj/SxPkq5FIScUoM56R1ZmPAigwTVh1 JYhwrnEn2PudRA8lYwr5Wa/tAlaQFVFjm6SvwqIELXMeGC5ktlboHoFkZBzX66n5Pguy wyDgrrHEGAQATyL9Xoq25v7SohnkECixK1/H/bRwV7eXfLuiv0BYE8jq2pB1Z+AKskY8 I846v8PX3zO/8YY1JUHWVOQDwjigJc4ledmzC+piku34pQHswU3UjHNdoIHnSh4PH2dW AEklU+55aeNbAPAoHEBRj2L006mA5EiXWRvxxwVj1xGkBDhjVom6LOMnAEyxIWNfUhxM VZJQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=mime-version:message-id:date:subject:to:from:x-gm-message-state :from:to:cc:subject:date; bh=GFy0XUzk9kF13HDNytI7kwW/pnisRSbc85c+9TbWBOE=; b=QY1IbBidnjxlQ/9G8RrrB/CEfX1983MTU6ilDHAV0Nb/Pw+mallPweYUDf8AFTFMOK VE0bIxhZ9SUQRIMYMkERsZ8P08nZVQPblY3kKMahTKL8jIu8ma9qYLADy9uWa3Y44A6Y W2lkOw8o1E+ZXEv9XE5Dxc5ATbp0C/FCL6z44K+nHo0ShWwqnIMZ91WctQA6ibnzQ7rJ h86Q1qlRsvFTCDg0lNRPah+uptb4n1oNQvrOhuaBXs/tNKp2Qqj8r9iBeeGMU/2VFQmk uH1VaHN2xE9YpvhkKsKvPyZDHLsREfdx+kPa86YOHb+UdGpjX4kZFIeI9ONWuKQA4ELB SYQA== X-Gm-Message-State: ACrzQf3hoQlbX7XBDgtLbjCnMnm+3dGvJbAMLpy/WomMbu/w+3KWtLvm pzexGuaxHGHrHcuk8ohAygMfoFyaFs4= X-Google-Smtp-Source: AMsMyM5CYzrP4cgsrwrGAVRJUqmiuo6/kLEtHiaXiPL4jbxvP7n8FASoWm4WlaPvGjxyVXGvuKUlEQ== X-Received: by 2002:a17:907:94c6:b0:787:9157:a87a with SMTP id dn6-20020a17090794c600b007879157a87amr1199329ejc.5.1664429366790; Wed, 28 Sep 2022 22:29:26 -0700 (PDT) Received: from Mini.fritz.box (pd9e36935.dip0.t-ipconnect.de. [217.227.105.53]) by smtp.gmail.com with ESMTPSA id y5-20020a50ce05000000b00457607603f9sm4652756edi.67.2022.09.28.22.29.25 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 28 Sep 2022 22:29:26 -0700 (PDT) From: =?utf-8?Q?Gerd_M=C3=B6llmann?= To: bug-gnu-emacs@gnu.org Subject: 29.0.50; [overlay] Interval tree iteration considered harmful Date: Thu, 29 Sep 2022 07:29:25 +0200 Message-ID: MIME-Version: 1.0 Content-Type: text/plain Received-SPF: pass client-ip=2a00:1450:4864:20::629; envelope-from=gerd.moellmann@gmail.com; helo=mail-ej1-x629.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-Spam-Score: -1.3 (-) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) In its current form, interval tree iteration works like this: 1. Call begin_iteration(T) to iterate over tree T 2. do stuff 3. Call end_iteration(T) with the following rules: - Begin_iteration and end_iteration must be paired. - There can be only one iteration per tree at a time. Nested iteration over the same tree is not supported (abort). - No GC may happen in step 2. This is because mark_buffer iterates over buffer overlays. I think this is an exceedingly dangerous design. From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 29 02:28:15 2022 Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 06:28:15 +0000 Received: from localhost ([127.0.0.1]:35724 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odn1q-0007Lb-Sy for submit@debbugs.gnu.org; Thu, 29 Sep 2022 02:28:15 -0400 Received: from eggs.gnu.org ([209.51.188.92]:53404) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odn1p-0007LL-Bo for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 02:28:13 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:52334) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odn1j-0005gE-5Y; Thu, 29 Sep 2022 02:28:07 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=4Wa+bXDSEaSiGaW+oXSRekkO0o0o/rFF5zysqSABDcs=; b=QiinJBfIMw0tlcAKi+qY qFXoid4cOJ3lR5rYfJq/vrkEef2N2dfl4ZoifeYD0AYHys76pOUovQ7zSeMExwjlAGt67j7RXf6CW styh5ivhbb1PuMDGU6U8tsU0tNOgVFLkQWYb4w02IjvHFke8QYZ7ElMAl1TTVVF65kCO/Vhlxsf7M L8xSz6INY7Yk31R134kIT9GBUTf01MG3SbMkULUOnefBEG8sQQQ340jw4r9QlmbE6T0fbKacfWtaT E+iGLomtUet5fUjwdnl90XvxKn1pe3Bd7DAzfn5iw7a/yNT7qzF8YgC/pG3X9IoCTFM5M79ffA58F ILvpEMzGA6R1gQ==; Received: from [87.69.77.57] (port=2640 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odn1i-0007bB-Ka; Thu, 29 Sep 2022 02:28:06 -0400 Date: Thu, 29 Sep 2022 09:28:03 +0300 Message-Id: <83h70qhez0.fsf@gnu.org> From: Eli Zaretskii To: Gerd =?utf-8?Q?M=C3=B6llmann?= In-Reply-To: (message from Gerd =?utf-8?Q?M=C3=B6llmann?= on Thu, 29 Sep 2022 07:29:25 +0200) Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful References: MIME-version: 1.0 Content-type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > From: Gerd Möllmann > Date: Thu, 29 Sep 2022 07:29:25 +0200 > > In its current form, interval tree iteration works like this: > > 1. Call begin_iteration(T) to iterate over tree T > 2. do stuff > 3. Call end_iteration(T) > > with the following rules: > > - Begin_iteration and end_iteration must be paired. > > - There can be only one iteration per tree at a time. Nested iteration > over the same tree is not supported (abort). > > - No GC may happen in step 2. This is because mark_buffer iterates over > buffer overlays. > > I think this is an exceedingly dangerous design. Why, because of "no GC" requirement? We could ensure that by calling inhibit_garbage_collection (if the code doesn't do that already). That is not very elegant, and might even cause memory pressure in some (hopefully rare) situations, but we do have some users of this in the sources. What higher-level operations require "interval tree iteration" that you describe? Which primitives end up doing such iterations? From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 29 03:03:29 2022 Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 07:03:29 +0000 Received: from localhost ([127.0.0.1]:35776 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odnZw-0008Ii-VF for submit@debbugs.gnu.org; Thu, 29 Sep 2022 03:03:29 -0400 Received: from mail-ed1-f52.google.com ([209.85.208.52]:43776) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odnZv-0008IU-04 for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 03:03:27 -0400 Received: by mail-ed1-f52.google.com with SMTP id y8so687272edc.10 for <58158@debbugs.gnu.org>; Thu, 29 Sep 2022 00:03:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:user-agent:message-id:date :references:in-reply-to:subject:cc:to:from:from:to:cc:subject:date; bh=3w39RTklEdnIqFOJPGt4SKJM69eEAjS/NXaSwwmYf6Q=; b=gabWP0fCZ7RHCZCRKSx3xT0s/x9DFUgvav0vpm+K7ZrZ4XpyqKQliWcR2KuwWp8fWV +kvspsQqrogO5eHcQX8KhipknSqSYMRtzvaCCSlGuv0z8HX2axjQ0UlAgE+5mGXuEXjj iBkLjyJaomjmNpnP8eJzuRmNFQhPSDLg6yWz1JYeznZPp1jyp+DPqJc+L8rO7VhaZEG0 wAUoQZBGZrybWZRy0DgAKRn7lpMEvm3NzIK1beGbVqGcFfYRYZqc6VEcBZ04Hxf9e6F3 WcDf/x7naITxIN1ywPq8hsQb1ahbVuFwlDETB1oQRhK5GS3oeI2FqHbhtX08H/V9QhZp 96uw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding: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=3w39RTklEdnIqFOJPGt4SKJM69eEAjS/NXaSwwmYf6Q=; b=kbWtWrTy+NrOCkh3LZwwO3ATRt9MFQoSpriJIeMsE7O9YmQyC7MLvb+c99OVjIVsRV 0FOoxGvlGzYnSGJ0RnFEHOVgz4aNqWZ+lXsGJtTimypfWdeJBivqRtInYP0Eyh94D/vK jto3Ygl/BHOtHIWCv+GS02efT5ZA6yw2r3aesp6gV8C1BconGg6Nmu9aR5qAVRTWV7/9 NYNNiq3aD3PgJrn9GuIWVFUoR+txnNmxtnb8xFaWohyfDRy6CSNvTudDe3czBW2L2Ym2 Q4oIN/0D05XOsCJ84RY3N1oeVANOmAGCRcjV/OhuFxxUxaooEQtu4es7Tr5umTR8LEi1 r/Sw== X-Gm-Message-State: ACrzQf1UGloriOmjxFAsUzHdQrrzagRSXz629d56q/IMvHjJtlGSE90K j4PFPyxN5sxKbgbaNhdCV+JQWkMkSXAUzw== X-Google-Smtp-Source: AMsMyM4GCblqbiFSPF9MnZp+O/EZmjJkQk6tztAsOZtswavyY3rMp21p/DLM5I9UEKv0d86srGEb7g== X-Received: by 2002:aa7:cd76:0:b0:457:cada:6cb7 with SMTP id ca22-20020aa7cd76000000b00457cada6cb7mr1795674edb.369.1664435000456; Thu, 29 Sep 2022 00:03:20 -0700 (PDT) Received: from Mini.fritz.box (pd9e36935.dip0.t-ipconnect.de. [217.227.105.53]) by smtp.gmail.com with ESMTPSA id e11-20020a170906080b00b0073c8d4c9f38sm3653342ejd.177.2022.09.29.00.03.18 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Sep 2022 00:03:19 -0700 (PDT) From: =?utf-8?Q?Gerd_M=C3=B6llmann?= To: Eli Zaretskii Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: <83h70qhez0.fsf@gnu.org> (Eli Zaretskii's message of "Thu, 29 Sep 2022 09:28:03 +0300") References: <83h70qhez0.fsf@gnu.org> Date: Thu, 29 Sep 2022 09:03:17 +0200 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 58158 Cc: 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) Eli Zaretskii writes: >> From: Gerd M=C3=B6llmann >> Date: Thu, 29 Sep 2022 07:29:25 +0200 >>=20 >> In its current form, interval tree iteration works like this: >>=20 >> 1. Call begin_iteration(T) to iterate over tree T >> 2. do stuff >> 3. Call end_iteration(T) >>=20 >> with the following rules: >>=20 >> - Begin_iteration and end_iteration must be paired. >>=20 >> - There can be only one iteration per tree at a time. Nested iteration >> over the same tree is not supported (abort). >>=20 >> - No GC may happen in step 2. This is because mark_buffer iterates over >> buffer overlays. >>=20 >> I think this is an exceedingly dangerous design. > > Why, because of "no GC" requirement? We could ensure that by calling > inhibit_garbage_collection (if the code doesn't do that already). It doesn't. BTW, if anything signals in step 2, so that end_iteration isn't called, we're also hosed. > What higher-level operations require "interval tree iteration" that > you describe? Which primitives end up doing such iterations? What has to do with overlays. To name a few: overlay-at, overlays-in, next-overlay-change, previous-overlay-change, overlay-lists, ... I personally think this is a no-go. From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 29 04:08:35 2022 Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 08:08:35 +0000 Received: from localhost ([127.0.0.1]:35850 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odoaw-0001aT-MZ for submit@debbugs.gnu.org; Thu, 29 Sep 2022 04:08:35 -0400 Received: from eggs.gnu.org ([209.51.188.92]:33624) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odoau-0001aH-S4 for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 04:08:34 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:51332) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odoan-0003Mm-Dx; Thu, 29 Sep 2022 04:08:26 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=IKa/eQPeSnERcn28E951LyAW4YzItWHxtjS/OFXi6EI=; b=WtBzYh7vLOSsAvSrL4jQ OYxQFrd1nrh4Mz2NkLAdAh24SVsN18ATXT+HEGYzAMExW4jLUrbbIcOYptfdJ9+57ZnrK8nJIsQX/ NLZ6Vgj2FoidggOiPfpDdabuPHMd8GkhWItTbsaJ4SiYtVTkSagU+CzwW6dgZGE3uVwxB/Vy4BtVR DGFZhM3CyTUH7Oqqn1qTPtQo8FK5JSm9jEj3zc1gosHrV7dhjj+kUr3pRgrObMR0P1nfY54QquALt 3IYlrQGFah8dziH9vAzpQGDKrTXVRjEVzdAJ3cS7untgAM9Tbt4B0o+1epBgQ+xpja7L8RUu0z2ai /f48qVhLt0F6Dw==; Received: from [87.69.77.57] (port=4798 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odoah-0002kU-Gb; Thu, 29 Sep 2022 04:08:23 -0400 Date: Thu, 29 Sep 2022 11:08:17 +0300 Message-Id: <83edvuhaby.fsf@gnu.org> From: Eli Zaretskii To: Gerd =?utf-8?Q?M=C3=B6llmann?= , Stefan Monnier In-Reply-To: (message from Gerd =?utf-8?Q?M=C3=B6llmann?= on Thu, 29 Sep 2022 09:03:17 +0200) Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful References: <83h70qhez0.fsf@gnu.org> MIME-version: 1.0 Content-type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > From: Gerd Möllmann > Cc: 58158@debbugs.gnu.org > Date: Thu, 29 Sep 2022 09:03:17 +0200 > > >> - No GC may happen in step 2. This is because mark_buffer iterates over > >> buffer overlays. > >> > >> I think this is an exceedingly dangerous design. > > > > Why, because of "no GC" requirement? We could ensure that by calling > > inhibit_garbage_collection (if the code doesn't do that already). > > It doesn't. Should be easy to fix, no? > BTW, if anything signals in step 2, so that end_iteration isn't called, > we're also hosed. record_unwind_protect should fix that, right? (inhibit_garbage_collection already employs this mechanism). > > What higher-level operations require "interval tree iteration" that > > you describe? Which primitives end up doing such iterations? > > What has to do with overlays. To name a few: overlay-at, overlays-in, > next-overlay-change, previous-overlay-change, overlay-lists, ... > > I personally think this is a no-go. Really? Even if we take all the measures mentioned above? Why so? From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 29 05:09:27 2022 Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 09:09:27 +0000 Received: from localhost ([127.0.0.1]:35971 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odpXq-0003Bh-Uo for submit@debbugs.gnu.org; Thu, 29 Sep 2022 05:09:27 -0400 Received: from mail-ej1-f46.google.com ([209.85.218.46]:40938) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odpXp-0003BT-9W for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 05:09:25 -0400 Received: by mail-ej1-f46.google.com with SMTP id l14so1441092eja.7 for <58158@debbugs.gnu.org>; Thu, 29 Sep 2022 02:09:25 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:user-agent:message-id:date :references:in-reply-to:subject:cc:to:from:from:to:cc:subject:date; bh=80mmmdFveyPqk7RrQ7oSEMwmSnIW7XWchV8m70bFx78=; b=ejD+WsYPSO2i1frsbAShoTjJAXig7LVnj+kGIJztT3epGSDglsHL96wiRHxPY0x1op qhKFFbHR5fpZz2FWm5tsDU9r5agnfSuZJkn8FBDgLijCEyM3xwNm13o9+newbE2fNHTK iMvE+0X1DaD3ClP/fPiO+HJgrSR005EdNoMaRaVHTEEw23K5/ENGfTEh45JSYbVRKZKu DeqG6Qi0H21C5ltIeJwvh4oQyBi0RCJqPvnQD8A5GWr0Gl0H5a6XEm3SPqM6rwyuhr/y YL3VOBxx9x05lBvu38NQXtjO5C8gLpVLNm6U4pHBQ0pPevaMGFbUboSK9nrUD3ryYvMt kOZg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding: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=80mmmdFveyPqk7RrQ7oSEMwmSnIW7XWchV8m70bFx78=; b=UU3UqU9qSS7XlT+erYdOzRv+mpSSmn8NoDEkF0a+xWlZnyocFUW3uZQUcB4aA1DYTv SNs2XZ10/KfniZSsBsxH6lsrstBaSWDxslJyEovba7rBvHZUi5AugjW/v1J16WwSg7ou 7k7W7v58NEnTlD+r8BMdqis9/wmzZOAeKCBh4xlQYkDz8pZUnWzmxRngJUI5Q1NPHxVH DcTh0J673l4tSBaZLmmSjICgm/8Lvx719vQXL3cZTCNRCKwtj0Uta785rrUiB0Vd/A54 pGilJMnjVrcAvcQvenFmfEe6unVK2gZ9dhzV3TKxfS9VXotN2N3pFa7uw6QjXYMxDZPb +sqQ== X-Gm-Message-State: ACrzQf3g5XJEyD3pOD6plMuEZF4M4bUrov+/9rNjkbtUOHIh636iwWQu Kandq78jgDfsRMIyO5RizMhRDsjuOcKSqw== X-Google-Smtp-Source: AMsMyM4qz4qDhEOl7ydM7fmq6CiQ+LiJPRyrpiJI6kx1BxfnVxDSJQQ5I8EkBzQEOkgS48qWamqHQg== X-Received: by 2002:a17:907:8a0b:b0:783:be41:40b4 with SMTP id sc11-20020a1709078a0b00b00783be4140b4mr1900891ejc.111.1664442558962; Thu, 29 Sep 2022 02:09:18 -0700 (PDT) Received: from Mini.fritz.box (pd9e36935.dip0.t-ipconnect.de. [217.227.105.53]) by smtp.gmail.com with ESMTPSA id 20-20020a170906309400b0073dc5bb7c32sm3668293ejv.64.2022.09.29.02.09.18 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Sep 2022 02:09:18 -0700 (PDT) From: =?utf-8?Q?Gerd_M=C3=B6llmann?= To: Eli Zaretskii Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: <83edvuhaby.fsf@gnu.org> (Eli Zaretskii's message of "Thu, 29 Sep 2022 11:08:17 +0300") References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> Date: Thu, 29 Sep 2022 11:09:17 +0200 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 58158 Cc: 58158@debbugs.gnu.org, Stefan Monnier X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) Eli Zaretskii writes: >> From: Gerd M=C3=B6llmann >> I personally think this is a no-go. > > Really? Even if we take all the measures mentioned above? Yes. > Why so? I think it simply can't be that what is basically walking a binary tree requires such restrictions. And if it does because of some quirk of the interval tree in itree.c, something is seriously wrong with the design. That's a bit harsh, but I mean it :-). From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 29 05:37:27 2022 Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 09:37:27 +0000 Received: from localhost ([127.0.0.1]:36018 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odpyw-0006H9-Qw for submit@debbugs.gnu.org; Thu, 29 Sep 2022 05:37:27 -0400 Received: from eggs.gnu.org ([209.51.188.92]:60850) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odpyu-0006Gu-BD for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 05:37:26 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:39876) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odpyo-0002bY-Fk; Thu, 29 Sep 2022 05:37:18 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=PpYU7aXZxOGsI1VjjQP2jB2NxL8XXYfo4LBwh+dPuKA=; b=OL3j6juozg5FG41f8bg3 ExFVwK3TvVJ0wurqjavM7M149Nm8bqlLYPQgCZEki00ca+FrjheCLQWMAod5xdpVlGKvIhZcT6uja tyi3C8OZUhYt1EVq1npXTTX8ycDrOK2ZH7RfjRYOZZCxLFP3JG97UmAUv8hlc2CpB5Qqvu9a3FgdX mdIyUvf8/h57pVx7HL2Pd6QvVOUpRT+xLofz2SCRlMZHIBD1UM9P4VOUF0rO/loFHYhJlwrDOVC+U RsbuHTin2fCVe94r3TRJZsxBJiPQFbECJ1tqITPRuYpd25ZQ5/k3VYM6fCga0dlsXuh2y+oNlOtu7 PIZaAkimOOP7eQ==; Received: from [87.69.77.57] (port=2316 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odpyn-0007W6-SX; Thu, 29 Sep 2022 05:37:18 -0400 Date: Thu, 29 Sep 2022 12:37:15 +0300 Message-Id: <831qruh67o.fsf@gnu.org> From: Eli Zaretskii To: Gerd =?utf-8?Q?M=C3=B6llmann?= In-Reply-To: (message from Gerd =?utf-8?Q?M=C3=B6llmann?= on Thu, 29 Sep 2022 11:09:17 +0200) Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> MIME-version: 1.0 Content-type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: 58158@debbugs.gnu.org, monnier@iro.umontreal.ca X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > From: Gerd Möllmann > Cc: Stefan Monnier , 58158@debbugs.gnu.org > Date: Thu, 29 Sep 2022 11:09:17 +0200 > > I think it simply can't be that what is basically walking a binary tree > requires such restrictions. And if it does because of some quirk of the > interval tree in itree.c, something is seriously wrong with the design. > > That's a bit harsh, but I mean it :-). Fair enough. Can you propose a fix? I guess the begin_iteration/end_iteration dance is because the tree could be in inconsistent state in-between? If so, what would it take to avoid the inconsistency? From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 29 06:05:59 2022 Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 10:05:59 +0000 Received: from localhost ([127.0.0.1]:36061 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odqQZ-00071s-IT for submit@debbugs.gnu.org; Thu, 29 Sep 2022 06:05:59 -0400 Received: from mail-ej1-f51.google.com ([209.85.218.51]:38648) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odqQY-00071d-2X for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 06:05:58 -0400 Received: by mail-ej1-f51.google.com with SMTP id nb11so1742869ejc.5 for <58158@debbugs.gnu.org>; Thu, 29 Sep 2022 03:05:58 -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=wNJHOnFenxgCrgYgcvn+dz5umAa8oLwCZSMWDMi4KCY=; b=S99k6Q3O4FhGcd7grDmDHPOxng4K2JUOGQB3wGsUiZhCE4/A1sbsuWpBIzw/4U8FKa KpAZRAzgti8Ht6RqN4Sv2Z0cPnMEZVGuIpO8Gq2WS4lyxMDTa5onAeELT5nG73jOZXEh CyUtjoUdLdsu2dyhmIr/pwEsUtpEtCb7CagK9Kj82nh83JUwGQnBEA8/1VP/fbEkJz8H Oz81sm8pcvmPhNR+QHGnYLgbXrSEc6YvS/xIdFe/AaOP+HAuDv3x8lQPMufz5tI9MaVN EkAHAGw1PWrgeiXYq64B05PZxmPBFDNPJGd3WkVsR1YIbkw1cNeQL0tKmhehUWwMDjQH Mzqw== 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=wNJHOnFenxgCrgYgcvn+dz5umAa8oLwCZSMWDMi4KCY=; b=XYrVpi4N7J+QFrseQ9DG3V3r+UrSLhENLhyXuFxCsdMIOUpMmGFU3JllN25d126rj2 MnzMTR8/Xi+vVekEEfezXVSmI2fK+n5lOhx0WKFKt5Om2/ytOYu0ipyY8SurJLxd17UN vgtt7tX/YeI7oiatQUlfuwkiocqaDLrmgVflL3ymXnAo5wp38rJWK3Jw8LyHnhKy4Wxx plUsEKcEBi22DAJy+yBRsWntqI0mzjCvypvYKniYsEWns3m4wTxAmFxJlbK3OAvOnl81 /8nA5aXeLgeRWnG4c5R2h+3LyiaajEhIMpkawcY37M5s68uiNxFaDbTtBJKlWNWw+1hj DFGA== X-Gm-Message-State: ACrzQf0vF/uuwAu/YLNVboyRr2/ODqkWThvsgTkSkksVu05295eTQWrT /mfUVUA/MX0pDUngn4kQDVDzzSnhv30mxw== X-Google-Smtp-Source: AMsMyM5B3O2xftlO/MkXCJb/G/P49RiIL/SZy88BATJ+Jyanble6CwQFFyXXZBnmWFGXJ56wDbxmOg== X-Received: by 2002:a17:906:8a66:b0:781:714a:1f2a with SMTP id hy6-20020a1709068a6600b00781714a1f2amr2099039ejc.205.1664445951629; Thu, 29 Sep 2022 03:05:51 -0700 (PDT) Received: from Mini.fritz.box (pd9e36935.dip0.t-ipconnect.de. [217.227.105.53]) by smtp.gmail.com with ESMTPSA id dk9-20020a0564021d8900b0043df042bfc6sm5018583edb.47.2022.09.29.03.05.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Sep 2022 03:05:51 -0700 (PDT) From: =?utf-8?Q?Gerd_M=C3=B6llmann?= To: Eli Zaretskii Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: <831qruh67o.fsf@gnu.org> (Eli Zaretskii's message of "Thu, 29 Sep 2022 12:37:15 +0300") References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> Date: Thu, 29 Sep 2022 12:05:50 +0200 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 58158 Cc: 58158@debbugs.gnu.org, monnier@iro.umontreal.ca X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) Eli Zaretskii writes: > Can you propose a fix? Other than completely rewrite at least this part, no. > I guess the begin_iteration/end_iteration dance is because the tree > could be in inconsistent state in-between? If so, what would it take > to avoid the inconsistency? I find it very hard to tell why this is done the way it is. If someone knowing the code can think of a reason, please speak up. From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 29 06:43:23 2022 Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 10:43:23 +0000 Received: from localhost ([127.0.0.1]:36120 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odr0l-0008LG-5a for submit@debbugs.gnu.org; Thu, 29 Sep 2022 06:43:23 -0400 Received: from eggs.gnu.org ([209.51.188.92]:44964) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odr0g-0008Kx-H4 for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 06:43:21 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:42644) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odr0Y-0005Iz-2c; Thu, 29 Sep 2022 06:43:12 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=S6yQjKgE3jJhY+pWW2lJLkTPMMIqDg3MrIL8uZ/caTk=; b=hrJRjSOAlgLmR5JDircA Ct+aqdZNiY4zTlZYWb6vH0PWShW2EZmmeoam+ixk0PBySbXM/GqVn4Yax29kooOJzFKhWgpTAS6+e +L9VxRB+XnFqQGPQsr1ajq1n+HOSVtulIrl78mI+SlEsJ+tskEdDSOs+XkNgK2W4TuWqQ0NVJoiMx KvStHYfrPyvG+u7UsiLUN+EoYlrPXcjdjjIUAVpC4PupI4uYuPdLFE2HNBtN7qbQGkjvABoAfc46O 02j1rlVldXS0MBFuwkYymGhkvCBh0a9KCgrCSzEjoymlR7zYcMEtNsVbdPWpyQjvpnLvOGe/oEhDl gbaaJZEHIVnhFQ==; Received: from [87.69.77.57] (port=2720 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odr0W-000805-OJ; Thu, 29 Sep 2022 06:43:09 -0400 Date: Thu, 29 Sep 2022 13:43:05 +0300 Message-Id: <83y1u2foli.fsf@gnu.org> From: Eli Zaretskii To: Gerd =?utf-8?Q?M=C3=B6llmann?= In-Reply-To: (message from Gerd =?utf-8?Q?M=C3=B6llmann?= on Thu, 29 Sep 2022 12:05:50 +0200) Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> MIME-version: 1.0 Content-type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: 58158@debbugs.gnu.org, monnier@iro.umontreal.ca X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > From: Gerd Möllmann > Cc: monnier@iro.umontreal.ca, 58158@debbugs.gnu.org > Date: Thu, 29 Sep 2022 12:05:50 +0200 > > Eli Zaretskii writes: > > > Can you propose a fix? > > Other than completely rewrite at least this part, no. > > > I guess the begin_iteration/end_iteration dance is because the tree > > could be in inconsistent state in-between? If so, what would it take > > to avoid the inconsistency? > > I find it very hard to tell why this is done the way it is. If someone > knowing the code can think of a reason, please speak up. I may be missing something, but it looks like the sole purpose of the iter_start/iter_finish dance is to ensure only one iteration per tree is running at any given time, and that's because the iteration uses some state variable(s) of which there's only one instance per tree. Stefan, am I missing something? From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 29 07:33:35 2022 Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 11:33:35 +0000 Received: from localhost ([127.0.0.1]:36442 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odrnL-00082j-Gw for submit@debbugs.gnu.org; Thu, 29 Sep 2022 07:33:35 -0400 Received: from mail-ej1-f52.google.com ([209.85.218.52]:46910) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odrnJ-00082V-CC for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 07:33:34 -0400 Received: by mail-ej1-f52.google.com with SMTP id bj12so2120806ejb.13 for <58158@debbugs.gnu.org>; Thu, 29 Sep 2022 04:33:33 -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=5UAdfhp4C+9xiu/qGj/hxHwL9WJDd7evJ2B9fv5Vy6s=; b=YjEXiE6YScsZPzt9Lb5DFQfGWUHDm2xZLwtwVqYtSpRHd6QeX81bUEzyLDD0l+n7jx eMMofzyV4cq422SBA/kpMIJM1F88HIpnNhAcNBEgMoENrHOpHz6K7dZUWeNRZNlXNZIH lMP2XjesxsrXaHc77fzoVfZ4iYZyD0NokcDhIhshFje2TX+a3EDAfu98MCdWvBpvBc56 eNjWVHPDCl4uf5ruJYgKY1RBnKWVE3cleAY0O3c9ETHgtyxPbLAtqVdA+pLAA5N5gIPH h3cStztOJHk8yVrTePqZHgqTtcFtu0X0oH7s5YnWzCBAKbCCmw8Q3+gmD09n2Ijye73o rfWw== 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=5UAdfhp4C+9xiu/qGj/hxHwL9WJDd7evJ2B9fv5Vy6s=; b=UwxPFiQMn5fZb1efDjcsCBUwG2lYZck7B/iAcTaK8qNCDum3UML6Xn3OAzKDlEJRP/ ynYGR7mod+SG6Ew4tpaN9G731iAVV9ZOrh1OMsY49Oqhus+gpMqpOr7/EVE9gM/Fg6+O RjxzOd+g80HILVg6vT+rdy/uQzNmf4jXQsUJr31d0mjTxbDXF6+HfJan6eioOVleLBIa oPurhLPwQ1fD3WJL6pOxtaBQ+Ou7czZCOv2iVxaTF3dCHkWs+WWTWmj4/irP1rUI7LUR ap+gomT04zoYPLDYjrv6oqyosyQb8B5vv/slS4Ujx+zoCTf2AwVsFdtXmtxbBjMqhOPD hXOA== X-Gm-Message-State: ACrzQf07AvdYVZS6IyZRcx9bxc+qyWwDW9FP0jlA4DVQwP32WI8IO1qA x2kmNDp4pfoZ7IHdKdrOkRB33J9arTRfig== X-Google-Smtp-Source: AMsMyM7LlAZTA6ty02DmhV8n8xlw3mhupBGyiKcnDxGoXMiHpgrdf7FPCQYpXiGc7VU99GXWtQ7Lcw== X-Received: by 2002:a17:907:6089:b0:783:592a:5d3f with SMTP id ht9-20020a170907608900b00783592a5d3fmr2425783ejc.385.1664451207149; Thu, 29 Sep 2022 04:33:27 -0700 (PDT) Received: from Mini.fritz.box (pd9e36935.dip0.t-ipconnect.de. [217.227.105.53]) by smtp.gmail.com with ESMTPSA id j2-20020a17090623e200b0078080a97edbsm3895393ejg.111.2022.09.29.04.33.25 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Sep 2022 04:33:26 -0700 (PDT) From: =?utf-8?Q?Gerd_M=C3=B6llmann?= To: Eli Zaretskii Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: <83y1u2foli.fsf@gnu.org> (Eli Zaretskii's message of "Thu, 29 Sep 2022 13:43:05 +0300") References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Date: Thu, 29 Sep 2022 13:33:25 +0200 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 58158 Cc: 58158@debbugs.gnu.org, monnier@iro.umontreal.ca X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) Eli Zaretskii writes: >> I find it very hard to tell why this is done the way it is. If someone >> knowing the code can think of a reason, please speak up. > > I may be missing something, but it looks like the sole purpose of the > iter_start/iter_finish dance is to ensure only one iteration per tree > is running at any given time, and that's because the iteration uses > some state variable(s) of which there's only one instance per tree. BTW, It currently uses a "visited" flag in tree nodes, which is kind of such a state, but something like that is normally not needed when walking an rb-tree. From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 29 09:10:30 2022 Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 13:10:30 +0000 Received: from localhost ([127.0.0.1]:36600 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odtJ8-0004MO-0C for submit@debbugs.gnu.org; Thu, 29 Sep 2022 09:10:30 -0400 Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:37600) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odtJ5-0004M2-Og for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 09:10:28 -0400 Received: from pmg1.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 57B94100136; Thu, 29 Sep 2022 09:10:22 -0400 (EDT) Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id DA24E1000FC; Thu, 29 Sep 2022 09:10:20 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1664457020; bh=308FgYlwpV+x9hQ1L8VVgbieCZ5EBNAD9x+EcOBhPBk=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=EPCnRC2q6k0wxmdoVW7ZODbeospHvVFb2hQWMsqGIxt0aKcbZfiP3NRGybY35gIFn ttuuyvT5q0kIrUicyLe4aWVbI1z3RvJPLTw/z1EtJhWKmctvyYjrr9Irl2ObE09xNe Pdw/9aBpMOni+KV/cou+RlK5FgsBO/AV3NmFeOh7boUtlbb5Lniv0Uf7G8q4/7d5Zn 2hKyzYczUs1Kx7jVaMA17OVIXbS5sLEXi2YaLCV8SxxNSeKKS5j41w8gOTrghTM38p 76UVOCaFltlkFrIVBI1GbDWkqzMaWi9Tu3IReWviwLJfkksrf9D95Zj+yvkuAyHx5T rIVjTR5QmfAuA== Received: from pastel (65-110-220-202.cpe.pppoe.ca [65.110.220.202]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id A698112047D; Thu, 29 Sep 2022 09:10:20 -0400 (EDT) From: Stefan Monnier To: Eli Zaretskii Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: <83y1u2foli.fsf@gnu.org> (Eli Zaretskii's message of "Thu, 29 Sep 2022 13:43:05 +0300") Message-ID: References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Date: Thu, 29 Sep 2022 09:10:19 -0400 User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-SPAM-INFO: Spam detection results: 0 ALL_TRUSTED -1 Passed through trusted hosts only via SMTP AWL -0.045 Adjusted score from AWL reputation of From: address BAYES_00 -1.9 Bayes spam probability is 0 to 1% DKIM_SIGNED 0.1 Message has a DKIM or DK signature, not necessarily valid DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's domain X-SPAM-LEVEL: X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: Gerd =?windows-1252?Q?M=F6llmann?= , 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > I may be missing something, but it looks like the sole purpose of the > iter_start/iter_finish dance is to ensure only one iteration per tree > is running at any given time, and that's because the iteration uses > some state variable(s) of which there's only one instance per tree. > > Stefan, am I missing something? One reason is that traversing a binary tree usually requires something like recursion, but that wouldn't fit very conveniently with the current code (nor with C in general since you can't make a local recursive closure which accesses local variables from the surrounding function). Another is the need to update the begin/end fields (these need updating because of insertions/deletions but they're updated lazily while traversing the tree to avoid an O(N) complexity during the insertions/deletions). Hiding that behind 'some kind of "next node" function keeps the code more readable. But yes, the current restriction to have a single iteration at a time is a bit of a problem, especially because it's very "global". I added a comment yesterday describing how we could make it non-global (hence getting rid of the `visited` flag in the nodes). For now, I pushed a simple fix to traverse the tree "by hand" in the GC rather than via the iterator. Stefan From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 29 09:24:04 2022 Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 13:24:04 +0000 Received: from localhost ([127.0.0.1]:36667 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odtWG-0004lu-7w for submit@debbugs.gnu.org; Thu, 29 Sep 2022 09:24:04 -0400 Received: from eggs.gnu.org ([209.51.188.92]:53680) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odtWC-0004lN-BA for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 09:24:02 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:52204) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odtW6-0002eW-El; Thu, 29 Sep 2022 09:23:54 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=fW0vdirI1dWr+tOW9a9wL53xcpbqLauR8TuhluRZipM=; b=c8fm4lXY/iAKhYbkeLuj /7i7mDQTUJdhC0+FFT7qgtzt73C224tGQCTCiqICjFoczriaPyiMwhAVGQ5aoKdzGpe5qVPj2OV7r lpaiKnyjFxYsWVw2l+8Xzt4hD6/B7zyGym1AhEUW2k3/sqB3T5MhbwVv0KWC9Gj4fZ7QfT7mZi6Mi Fcc5eXWqrnb3sGAIKyOHyhsPL0xnxx55UD5oafvrh1MSGoeWlYKXiM3EAuFRSWTlyvw+ap3/OIaMQ 8/++EX8CUgz18/nPt30UoUyaGVPmG1VdSG52hm5cGNUIhD9spsgeEs4xVe8d01fgPpCERdynTzFIp cIEA1uDW6xKAug==; Received: from [87.69.77.57] (port=4604 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odtW4-0005Sx-WB; Thu, 29 Sep 2022 09:23:54 -0400 Date: Thu, 29 Sep 2022 16:23:47 +0300 Message-Id: <83o7uyfh5o.fsf@gnu.org> From: Eli Zaretskii To: Stefan Monnier In-Reply-To: (message from Stefan Monnier on Thu, 29 Sep 2022 09:10:19 -0400) Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful 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; charset=utf-8 Content-Transfer-Encoding: 8bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: gerd.moellmann@gmail.com, 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > From: Stefan Monnier > Cc: Gerd Möllmann , > 58158@debbugs.gnu.org > Date: Thu, 29 Sep 2022 09:10:19 -0400 > > > I may be missing something, but it looks like the sole purpose of the > > iter_start/iter_finish dance is to ensure only one iteration per tree > > is running at any given time, and that's because the iteration uses > > some state variable(s) of which there's only one instance per tree. > > > > Stefan, am I missing something? > > One reason is that traversing a binary tree usually requires something > like recursion, but that wouldn't fit very conveniently with the current > code (nor with C in general since you can't make a local recursive > closure which accesses local variables from the surrounding function). I'm not sure I understand how recursion is related. Are you saying that recursion is replaced with iteration? But then, if _start and _finish are called by the same caller, we don't really need the protection, since no one can start another iteration while the first one runs. Right? > Another is the need to update the begin/end fields (these need updating > because of insertions/deletions but they're updated lazily while > traversing the tree to avoid an O(N) complexity during the > insertions/deletions). Hiding that behind 'some kind of "next node" > function keeps the code more readable. Where in the code do you see iteration that adds or deletes nodes? > For now, I pushed a simple fix to traverse the tree "by hand" in the GC > rather than via the iterator. So this removes the restriction of not having GC during iteration? Also, I take it that you don't consider the current code is as "harmful" as Gerd thinks it is? IOW, you don't share his opinion that this implementation is a "no-go"? From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 29 09:40:25 2022 Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 13:40:25 +0000 Received: from localhost ([127.0.0.1]:36685 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odtm4-00059e-MT for submit@debbugs.gnu.org; Thu, 29 Sep 2022 09:40:25 -0400 Received: from eggs.gnu.org ([209.51.188.92]:57872) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odtm3-00059N-1w for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 09:40:23 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:35746) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odtlx-0005CP-3w; Thu, 29 Sep 2022 09:40:17 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=9JGmNIcp4trp60/HHPctb7rUn/M53Ri2DdAZB8eTzVk=; b=BuXDQeu+lw0+KzH+po+W n+4idUSaBpfBGcF0C+bvZxcVz2E5hGRwucB/kr+1Qtlr6xbqL/nvbUCdm5u/T49D6fSyThkjFL/A1 Zxkwz489mJBxkmcI94wnFwMNQ7iYAzYSfdRCN/pr/gt2KcJgvDyBeTOR9+RsVJUzULgQ/jIqIc1Zl lADkJNDhKfQYdBY5gviIZFglSv+CISAqnanZHd62wtas4NGUAFAB7H+7sMhauBr/Dc9NOE/SYkUqr oTk75zabGLIJwmwMC7mVoy9RZOKo3dCpWBoXN3JEuF1Jc4z81hpME18tCCGkxBiCEeEmCd6qTcpae M/wWD/crXL9nmg==; Received: from [87.69.77.57] (port=1666 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odtlw-000792-Ig; Thu, 29 Sep 2022 09:40:16 -0400 Date: Thu, 29 Sep 2022 16:40:10 +0300 Message-Id: <83leq2fged.fsf@gnu.org> From: Eli Zaretskii To: Stefan Monnier In-Reply-To: (message from Stefan Monnier on Thu, 29 Sep 2022 09:10:19 -0400) Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful 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; charset=utf-8 Content-Transfer-Encoding: 8bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: gerd.moellmann@gmail.com, 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > From: Stefan Monnier > Cc: Gerd Möllmann , > 58158@debbugs.gnu.org > Date: Thu, 29 Sep 2022 09:10:19 -0400 > > Another is the need to update the begin/end fields (these need updating > because of insertions/deletions but they're updated lazily while > traversing the tree to avoid an O(N) complexity during the > insertions/deletions). Hiding that behind 'some kind of "next node" > function keeps the code more readable. Btw, couldn't we handle this by having a flag in the node that tells us whether the begin/end fields can be trusted? Then the first caller who need them would run the update and reset the flags, and we still have lazy update, albeit somewhat less lazy, but without the need for guarding the iteration with start/finish calls. Would that work? From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 29 10:15:22 2022 Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 14:15:22 +0000 Received: from localhost ([127.0.0.1]:39172 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oduJu-0006gs-0R for submit@debbugs.gnu.org; Thu, 29 Sep 2022 10:15:22 -0400 Received: from mail-ej1-f47.google.com ([209.85.218.47]:35438) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oduJq-0006ga-9q for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 10:15:20 -0400 Received: by mail-ej1-f47.google.com with SMTP id sd10so3130102ejc.2 for <58158@debbugs.gnu.org>; Thu, 29 Sep 2022 07:15:18 -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=oWmLNZNkBvKstZg4Ohdy2sNKhCJvdX3RTv8U9goAB+8=; b=Ijqx0WmQnpcFy8aHtksvEvKi1/uXB/9/KGv7IhzXUaq+DpSOy0fm4B9b4O49XAihvm r8Yd0H5pSYi7Q3QWSQFg2vOU/IID9NJRB3g6u1G1auQ2mILju6NtQd55a8mHKg9WSt5w Wd72ZRZaGnU0Wnwij+ZF7xjHBnAXOPSCgHnW253uM5U4keU9A1VNe40zI8ZfK6LBxzfj mvLZIwuUnwk1b+u4GULk1r9C2UN/0GpF+PbeLZc7D9dlT2zLKiPnAOv17NdLjxfwWs3v 0m4H5FbdiXvOdgSK3ydDeS/8VqOt/+ap5+bGxpn/3n/zydFSsbk3NDxgtezeSd7oda42 NpRQ== 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=oWmLNZNkBvKstZg4Ohdy2sNKhCJvdX3RTv8U9goAB+8=; b=u0v6fajm1toY+la9AINbTJggiWIKLGXHPoy3J1hOY+NW1t20Qtnv0HTmlt0hi+45Ib AXiYvjhCOXgxmrE5s7MsS/hkkQzGyQc2/9RdnZmrBHwWaFIdzUwZHi1MzBaxeC7lzhkS IYM01MWDbigha+r90ni90mZNLk/n4grdKjXs4Ct1nf0i79jkDO9qqMb4ZXYptpjDk+en q7wAjZ04kdq8FP5AYQrM6Guc8akTSM/Zdui5hkYrpyYruINJONiPH//NaS5ElalFsh0J udl6UNFArO9AKOcK+JXj2ScJS0+7Dm0bSKR09iwZut81koM2raloX+EksUp80WYHUDB2 C/3Q== X-Gm-Message-State: ACrzQf1gkbbgsIWa1LbEZ8oSlFgS0fBjvyZFXpD6pM3CRKAejdgURK7U p4KTIH9Ic5qpLT9TSPbFQQHDFUqTCz6GXA== X-Google-Smtp-Source: AMsMyM67tLmMYk84pcUicpcLf7+3bi/nmePHGL6o3N3F7YSFoQ7VNLZqoMcw2Yp62YSBZgZ68JOUWw== X-Received: by 2002:a17:906:2699:b0:781:a473:9791 with SMTP id t25-20020a170906269900b00781a4739791mr2930970ejc.644.1664460911916; Thu, 29 Sep 2022 07:15:11 -0700 (PDT) Received: from Mini.fritz.box (pd9e36935.dip0.t-ipconnect.de. [217.227.105.53]) by smtp.gmail.com with ESMTPSA id v2-20020a170906292200b0073c80d008d5sm3998920ejd.122.2022.09.29.07.15.10 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Sep 2022 07:15:11 -0700 (PDT) From: =?utf-8?Q?Gerd_M=C3=B6llmann?= To: Stefan Monnier Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: (Stefan Monnier's message of "Thu, 29 Sep 2022 09:10:19 -0400") References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Date: Thu, 29 Sep 2022 16:15:09 +0200 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) Stefan Monnier writes: > One reason is that traversing a binary tree usually requires something > like recursion, but that wouldn't fit very conveniently with the current > code (nor with C in general since you can't make a local recursive > closure which accesses local variables from the surrounding function). Ok, usually, but not necessarily. The alternative is to implement an iterator that starts with a node N, and an implementation of a successor function, which return the successor of N in a given order. This requires a parent pointer in nodes, but that we have. (Something like this is used for ordered containers like "map" and "set" in C++ STL, for instance, which are based on rb-trees in GCC's libstdc++.) > Another is the need to update the begin/end fields (these need updating > because of insertions/deletions but they're updated lazily while > traversing the tree to avoid an O(N) complexity during the > insertions/deletions). Hiding that behind 'some kind of "next node" > function keeps the code more readable. Is this for buffer text changes, something akin to a delayed update of marker positions? I already wondered where that was. > But yes, the current restriction to have a single iteration at a time is > a bit of a problem, especially because it's very "global". I added > a comment yesterday describing how we could make it non-global (hence > getting rid of the `visited` flag in the nodes). BTW, and related to iteration directly, did you notice this in interval_tree_insert? /* This suggests that nodes in the right subtree are strictly greater. But this is not true due to later rotations. */ child = node->begin <= child->begin ? child->left : child->right; From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 29 10:38:02 2022 Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 14:38:02 +0000 Received: from localhost ([127.0.0.1]:39230 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odufp-0007Hp-Q5 for submit@debbugs.gnu.org; Thu, 29 Sep 2022 10:38:02 -0400 Received: from mail-ej1-f45.google.com ([209.85.218.45]:46059) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odufn-0007HU-Nt for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 10:38:00 -0400 Received: by mail-ej1-f45.google.com with SMTP id dv25so3203356ejb.12 for <58158@debbugs.gnu.org>; Thu, 29 Sep 2022 07:37:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:user-agent:message-id:date :references:in-reply-to:subject:cc:to:from:from:to:cc:subject:date; bh=BW9KqAyaC9VT8Y1KCNDntO52On0zO30gIztAZoX+b1w=; b=Y+MdZh22wuOapmR8I+NnA+jV3oenfaK/MaTmh/shoJi7GM5E5vwgcqwO/k9GUhjUwv NG13Y+XuobQzAM3GOGZMHFtIGCmiSrEUQYtBUL9LTZ2+EyNo1A9oisYoCBJ+upUW6mcZ CIYkFlG003seFr3bDxfS68ck4+IfJqeNa4KuROk0bjmZrXCFEv06uv5tkzWE7mdADvfK WfdNGI/HIF1ppwZ0rJ6QC928bInRSFWiBtGvQzSHhvHJX6gL015KNijlnC4YGihlFgrR Yg6hm3ei5XULU+4WBYZQGnqeccfWITfFTqp1+FOgMtsxKdXcQ8JHUGej2zcankDwpGdA bUjA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding: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=BW9KqAyaC9VT8Y1KCNDntO52On0zO30gIztAZoX+b1w=; b=NO9Y/a76DKkCwuugwkCIgV3stxC+dDiHuHuo4nlYDzBMhSIggP4IowWHvCWtMApuK6 yiyAp9hZfO6xDCoXa6CIhq/CJxQ7C+J+lcg8G4F5a/uH/SHQJeJghuMUpevVF15+GTG0 GrIeZZDRjiP5CcOWtfyH7QKu6zgeT+QJi+Nin1jz9GmtXefFJKXC8z0q7Wa22y1SzvBD iUGv2jBpVp5EojC4M24dOWk7St/S0hCYGk5eEl0XfEuv7XnX784o+T+HE5k3/CG0qLeq TrvEVvjZPovXJJz2VdjXuDm/HCHjupgPDu0jOpFbBsNNJ+tC5A3MtG+JQdyCshqys27j LRww== X-Gm-Message-State: ACrzQf2vtzflTDTKgRTLhSgulQLrjGHwL+hJE7vv7c028mj8dXnOQMZP SW3VaUBlhuD9WvkXMpoMXDa11MFZtuc2mg== X-Google-Smtp-Source: AMsMyM4WJ8PZRkL+HBPRIdFE0jxU2wEOnD4HCtx0eAfZvvIFAxHmuUk1LWOX8IpjMVLSmSpyCOo16A== X-Received: by 2002:a17:907:3f8c:b0:787:a14d:65a7 with SMTP id hr12-20020a1709073f8c00b00787a14d65a7mr3065830ejc.108.1664462273346; Thu, 29 Sep 2022 07:37:53 -0700 (PDT) Received: from Mini.fritz.box (pd9e36935.dip0.t-ipconnect.de. [217.227.105.53]) by smtp.gmail.com with ESMTPSA id m9-20020a509989000000b0045391f7d877sm5775857edb.53.2022.09.29.07.37.52 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Sep 2022 07:37:52 -0700 (PDT) From: =?utf-8?Q?Gerd_M=C3=B6llmann?= To: Stefan Monnier Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: ("Gerd =?utf-8?Q?M=C3=B6llman?= =?utf-8?Q?n=22's?= message of "Thu, 29 Sep 2022 16:15:09 +0200") References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Date: Thu, 29 Sep 2022 16:37:51 +0200 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) Gerd M=C3=B6llmann writes: > Stefan Monnier writes: > >> One reason is that traversing a binary tree usually requires something >> like recursion, but that wouldn't fit very conveniently with the current >> code (nor with C in general since you can't make a local recursive >> closure which accesses local variables from the surrounding function). > > Ok, usually, but not necessarily. The alternative is to implement an > iterator that starts with a node N, and an implementation of a successor > function, which return the successor of N in a given order. This > requires a parent pointer in nodes, but that we have. > > (Something like this is used for ordered containers like "map" and "set" > in C++ STL, for instance, which are based on rb-trees in GCC's > libstdc++.) The code from libstdc++ is this (from libstdc++-v3/src/c++98/tree.cc): static _Rb_tree_node_base* local_Rb_tree_increment(_Rb_tree_node_base* __x) throw () { if (__x->_M_right !=3D 0) { __x =3D __x->_M_right; while (__x->_M_left !=3D 0) __x =3D __x->_M_left; } else { _Rb_tree_node_base* __y =3D __x->_M_parent; while (__x =3D=3D __y->_M_right) { __x =3D __y; __y =3D __y->_M_parent; } if (__x->_M_right !=3D __y) __x =3D __y; } return __x; } I hope one can read that. The idea is to find the root of the smallest subtree containing the current node, and proceed from there. That's why the parent pointer is needed. Symmmetrical for max->min ordering. And finding min/max is trivial. From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 29 12:40:40 2022 Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 16:40:40 +0000 Received: from localhost ([127.0.0.1]:39412 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odwaW-00028m-7D for submit@debbugs.gnu.org; Thu, 29 Sep 2022 12:40:40 -0400 Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:35643) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odwaP-00028E-BO for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 12:40:38 -0400 Received: from pmg1.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id D36DC100138; Thu, 29 Sep 2022 12:40:27 -0400 (EDT) Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 28F2D1000FC; Thu, 29 Sep 2022 12:40:26 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1664469626; bh=vnOYG21YnYzvzyiBpZ/ZaBMm58G73v9/WSgDmA9WCFE=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=VNN6lwGeUZ5ce7QbLow+PCTbw6eZbeu3MH4fRedAtIxhcfYgTi1pj1T23cpXli9K3 jUNsUtiPoxQs/85SKtV/fdc0CLTFxl2r9K0tbHWRb8aRdLftDU9iGWJGMyfNowvNtp vjudKhsvZXFES+RIIGv5fo2CTc2ELHg1cggbWLb+MYO8g68OoyVYKhMyo2BUtVSBCY LX2ucjw4+jMaDfllGn/8f2jHg6zCpppLTBCKV7sOsb1BOe3L8R+LLpo1m81rXpJmCr dSdQuYQFfoerJor3o0yssB9VewPh+wuPXkFghRwP/J8GSruoDowRpuHWTF6GPsYOpv zIaI8JryAL4NA== Received: from lechazo (lechon.iro.umontreal.ca [132.204.27.242]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 032631203D7; Thu, 29 Sep 2022 12:40:25 -0400 (EDT) From: Stefan Monnier To: Gerd =?windows-1252?Q?M=F6llmann?= Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: ("Gerd =?windows-1252?Q?M=F6l?= =?windows-1252?Q?lmann=22's?= message of "Thu, 29 Sep 2022 16:15:09 +0200") Message-ID: References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Date: Thu, 29 Sep 2022 12:40:25 -0400 User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable X-SPAM-INFO: Spam detection results: 0 ALL_TRUSTED -1 Passed through trusted hosts only via SMTP AWL 0.165 Adjusted score from AWL reputation of From: address BAYES_00 -1.9 Bayes spam probability is 0 to 1% DKIM_SIGNED 0.1 Message has a DKIM or DK signature, not necessarily valid DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's domain X-SPAM-LEVEL: X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) Gerd M=F6llmann [2022-09-29 16:15:09] wrote: > Stefan Monnier writes: >> One reason is that traversing a binary tree usually requires something >> like recursion, but that wouldn't fit very conveniently with the current >> code (nor with C in general since you can't make a local recursive >> closure which accesses local variables from the surrounding function). > Ok, usually, but not necessarily. The alternative is to implement an > iterator that starts with a node N, and an implementation of a successor > function, which return the successor of N in a given order. The approach currently used is somewhat similar to that. Some of the difference is that we need an actual "iterator/generator" object to remember the parameter of the filtering we want to apply to the set of objects. And the problem is that this "object" is currently implemented not only as a global value (thus restricting us to one-iteration at a time) but also with some parts of the data stored in the tree. I think this is the part that really needs to be changed. > This requires a parent pointer in nodes, but that we have. > > (Something like this is used for ordered containers like "map" and "set" > in C++ STL, for instance, which are based on rb-trees in GCC's > libstdc++.) Another difference is that itree.c's iterator uses a local "work stack" instead of traversing the tree exclusively via left/right/parent like in the code you show. I don't know if that difference is important, tho. >> Another is the need to update the begin/end fields (these need updating >> because of insertions/deletions but they're updated lazily while >> traversing the tree to avoid an O(N) complexity during the >> insertions/deletions). Hiding that behind 'some kind of "next node" >> function keeps the code more readable. > > Is this for buffer text changes, something akin to a delayed update of > marker positions? Yes, exactly. >> But yes, the current restriction to have a single iteration at a time is >> a bit of a problem, especially because it's very "global". I added >> a comment yesterday describing how we could make it non-global (hence >> getting rid of the `visited` flag in the nodes). > > BTW, and related to iteration directly, did you notice this in > interval_tree_insert? > > /* This suggests that nodes in the right subtree are strictly > greater. But this is not true due to later rotations. */ > child =3D node->begin <=3D child->begin ? child->left : child->righ= t; No, I had not noticed that yet, and I don't understand this comment. Stefan From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 29 12:48:48 2022 Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 16:48:48 +0000 Received: from localhost ([127.0.0.1]:39443 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odwiO-0002Mz-BA for submit@debbugs.gnu.org; Thu, 29 Sep 2022 12:48:48 -0400 Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:15985) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odwiJ-0002Mj-7R for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 12:48:47 -0400 Received: from pmg3.iro.umontreal.ca (localhost [127.0.0.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id A642C442F98; Thu, 29 Sep 2022 12:48:37 -0400 (EDT) Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id 953F3442F94; Thu, 29 Sep 2022 12:48:35 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1664470115; bh=eOh6g4WtUR/fEw2F4endAWNdlv/ADGvgWQKbYXwoF78=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=SBt3yjNNbLOF1Q6jiHWHYHiiiy1FZ5iTLi3pp5WM5rnkMHFe/hQDmo+kTjyTVGUZJ SmlBpQoPXYIhgtsZEj1WNRNEVWbKggv6wnJzzRvx+5HK48wcjcgOozhqS0STxJO5Zg g2XENSSxTXhds2WpasWOKjFeM3Ltuesci3iSP61+K877MPnhTyo4ZO/omGuo+n2B1d jpnUmnk5DUL1bQrqhbDbaT5o47zwGNCZ8RSJPyCINTMvT2u6/aT0RYOpAJbrhB1qf7 C1InNBNmQNmp9/Jx/eo9LNqk5EOqpOlO9zI3qlAWTast3dl3xsqzOvlGXi1qjGukm6 GslMM8ZVblwxg== Received: from lechazo (lechon.iro.umontreal.ca [132.204.27.242]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 88E03120DA7; Thu, 29 Sep 2022 12:48:35 -0400 (EDT) From: Stefan Monnier To: Eli Zaretskii Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: <83o7uyfh5o.fsf@gnu.org> (Eli Zaretskii's message of "Thu, 29 Sep 2022 16:23:47 +0300") Message-ID: References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> <83o7uyfh5o.fsf@gnu.org> Date: Thu, 29 Sep 2022 12:48:34 -0400 User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-SPAM-INFO: Spam detection results: 0 ALL_TRUSTED -1 Passed through trusted hosts only via SMTP AWL -0.018 Adjusted score from AWL reputation of From: address BAYES_00 -1.9 Bayes spam probability is 0 to 1% DKIM_SIGNED 0.1 Message has a DKIM or DK signature, not necessarily valid DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's domain X-SPAM-LEVEL: X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: gerd.moellmann@gmail.com, 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) >> > I may be missing something, but it looks like the sole purpose of the >> > iter_start/iter_finish dance is to ensure only one iteration per tree >> > is running at any given time, and that's because the iteration uses >> > some state variable(s) of which there's only one instance per tree. >> > >> > Stefan, am I missing something? >> >> One reason is that traversing a binary tree usually requires something >> like recursion, but that wouldn't fit very conveniently with the current >> code (nor with C in general since you can't make a local recursive >> closure which accesses local variables from the surrounding function). > > I'm not sure I understand how recursion is related. Are you saying > that recursion is replaced with iteration? But then, if _start and > _finish are called by the same caller, we don't really need the > protection, since no one can start another iteration while the first > one runs. Right? Typically, current code will look something like: int x; Lisp_Object y; buffer_overlay_iter_start (current_buffer, prev, pos, ITREE_DESCENDING); while ((node = buffer_overlay_iter_next (current_buffer))) { ... do something that updates x and y ... } buffer_overlay_iter_finish (current_buffer); If we were to use recursion, then we'd need to define a new (recursive) function which does what's currently done in the `while` loop, but this function can't access `x` and `y`, so it would need to take them as argument, or a reference to them... The use of an iterator is definitely convenient (and is a standard approach in many languages). >> Another is the need to update the begin/end fields (these need updating >> because of insertions/deletions but they're updated lazily while >> traversing the tree to avoid an O(N) complexity during the >> insertions/deletions). Hiding that behind 'some kind of "next node" >> function keeps the code more readable. > > Where in the code do you see iteration that adds or deletes nodes? No, I meant insertion/deletion of text in the buffer, thus requiring updates to `begin/end` fields. > Btw, couldn't we handle this by having a flag in the node that tells > us whether the begin/end fields can be trusted? Then the first caller > who need them would run the update and reset the flags, and we still > have lazy update, albeit somewhat less lazy, but without the need for > guarding the iteration with start/finish calls. Would that work? Yes, it would, but it's still O(N). The current approach is inspired by the approach used in `intervals.c` which also updates those fields lazily/ondemand so as to avoid the O(N) performance impact. >> For now, I pushed a simple fix to traverse the tree "by hand" in the GC >> rather than via the iterator. > So this removes the restriction of not having GC during iteration? Yes. > Also, I take it that you don't consider the current code is as > "harmful" as Gerd thinks it is? I don't like the global state it uses, but I think we can fix this aspect without too much trouble. > IOW, you don't share his opinion that this implementation is > a "no-go"? No, indeed, I don't. Stefan From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 29 18:09:13 2022 Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 22:09:13 +0000 Received: from localhost ([127.0.0.1]:39860 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oe1iT-000288-Ej for submit@debbugs.gnu.org; Thu, 29 Sep 2022 18:09:13 -0400 Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:4085) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oe1iQ-00027u-N6 for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 18:09:11 -0400 Received: from pmg2.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id 4A4B180740; Thu, 29 Sep 2022 18:09:05 -0400 (EDT) Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id ACC3A802A7; Thu, 29 Sep 2022 18:09:03 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1664489343; bh=aAWjzvAwYgtD09bYnVK4/L2jLPJB9KvaFH21lBFahcw=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=NSBvLEPNw30njsvZBXXzZ4UplSRrQMaV6Hxl84KzJGac4wDGfVps2zNpsIZMr32b1 LMLhEMJupVvLl6voQa0DZ5CMCGyicPaddPtwxexIOjWWXxzbJ0Q2Pf2ROtHMof4Lmt iW9z1yF/UBtS7Uryp9/yoyqSQscVH+ZTAcHLN6YwA8PGLosQSOFSwI+ZwW5XRYdc2g EQ2iKHqFUGn2SSYyeL/QIKKr6LtPl3Dhlgcs4xaPApn9sOyfIhR2f9HPLQt/vR5Xnh lPF0Az7PX3mUmhvjTzaVPtYSaOT4lPeeAyTUlgJWSzD0z9fYFXkT2MyuNawIAsc1+E jnUFZkAQ4FrQg== Received: from pastel (65-110-220-202.cpe.pppoe.ca [65.110.220.202]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 6984E1203FE; Thu, 29 Sep 2022 18:09:03 -0400 (EDT) From: Stefan Monnier To: Gerd =?windows-1252?Q?M=F6llmann?= Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: ("Gerd =?windows-1252?Q?M=F6l?= =?windows-1252?Q?lmann=22's?= message of "Thu, 29 Sep 2022 16:37:51 +0200") Message-ID: References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Date: Thu, 29 Sep 2022 18:09:01 -0400 User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-SPAM-INFO: Spam detection results: 0 ALL_TRUSTED -1 Passed through trusted hosts only via SMTP AWL -0.095 Adjusted score from AWL reputation of From: address BAYES_00 -1.9 Bayes spam probability is 0 to 1% DKIM_SIGNED 0.1 Message has a DKIM or DK signature, not necessarily valid DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's domain X-SPAM-LEVEL: X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > static _Rb_tree_node_base* > local_Rb_tree_increment(_Rb_tree_node_base* __x) throw () > { > if (__x->_M_right != 0) > { > __x = __x->_M_right; > while (__x->_M_left != 0) > __x = __x->_M_left; > } > else > { > _Rb_tree_node_base* __y = __x->_M_parent; > while (__x == __y->_M_right) > { > __x = __y; > __y = __y->_M_parent; > } > if (__x->_M_right != __y) > __x = __y; > } > return __x; > } > > I hope one can read that. 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. [ An alternative would be to try and get rid of the `parent` field :-) ] Stefan From debbugs-submit-bounces@debbugs.gnu.org Fri Sep 30 01:28:40 2022 Received: (at 58158) by debbugs.gnu.org; 30 Sep 2022 05:28:40 +0000 Received: from localhost ([127.0.0.1]:40265 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oe8Zk-0004zE-16 for submit@debbugs.gnu.org; Fri, 30 Sep 2022 01:28:40 -0400 Received: from mail-ej1-f50.google.com ([209.85.218.50]:35794) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oe8Ze-0004yy-Sb for 58158@debbugs.gnu.org; Fri, 30 Sep 2022 01:28:38 -0400 Received: by mail-ej1-f50.google.com with SMTP id sd10so6833454ejc.2 for <58158@debbugs.gnu.org>; Thu, 29 Sep 2022 22:28:34 -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=nd0/Z0pE+CK4ofum+int/5HYfEIg0SL2BcnyZuTXqUs=; b=qnjMtf3+f71lNaBdmqAVw1/5xBJa8XNGRo/HiITwTP7ZJC4FmCWlBeh60OBhhK4VCa 3LkgPPki5Lp9dGmNPMxteLZuRXLBiwvLKEqrDKaCrkVWM8bbcE7VRgEXQykDsyOc7rG5 AVvSAbUAjl5Nwxi6Ifb6SbZZmfrZCh4ZVIVfo2z+T5ibeA+nFfyqG1k5xNrzrEz0Hn95 rdDvKuQ4P/iGLqv/yATGl79aZArG8EeWzyuLPCWKOhHTzj2upU+XDN07kEiKvb87ZCYB bmZMruwih0qd7Gi6szu7bTmqs1dlyyr9OMnu2OGB278ZgZaBNHY1veZq49Oriz0GyaS4 xtgw== 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=nd0/Z0pE+CK4ofum+int/5HYfEIg0SL2BcnyZuTXqUs=; b=qFzSJy26238L4xLaN3M8CnWa5sdl9QpRGa5g54cA34iCSID/b6Tbi2fshHwTRT2D9t wuP9sSbEMklRj2svMbvtAb7LmFdqmFsqapD4DSdCHXDRt8Pf4ibcDkzIgTxIeKtrUB6S 2jFnlvRE8G82jyvhl7+URI3kaznyTyGZJGkOjZ4WitTXUVT23/Ip4KZ2sx1Kzhge+Caj 1jqip9GkD05uWFQ6ZYKLnaaP2Qjs3Dd+o2LAi2NLFhMyOyJmCbOSy0Dy1iqoNBFUxKHE LDx30BVbWSCi08zD8L1zYpyRb+tf1beEfk29WNbtd1j7zsoVe7ag9r1P8jsH/jceSTvD Huyg== X-Gm-Message-State: ACrzQf0/8epT14jCVOOo759kmTuMS2NZsc8C0qST0bBMCglsChI3RMJK 2nTNo6tfS303IVE0bvz/TbR6Icoe72Qd4Q== X-Google-Smtp-Source: AMsMyM6hrExa4kyouu6bAw66aNb3Xup4Ar/wcOQK+EOZ0XgbRUn9+ovVKC6hp+IGQn+fJnAXN4EO2w== X-Received: by 2002:a17:907:6e1e:b0:782:19e7:f5e8 with SMTP id sd30-20020a1709076e1e00b0078219e7f5e8mr5204282ejc.215.1664515708601; Thu, 29 Sep 2022 22:28:28 -0700 (PDT) Received: from Mini.fritz.box (pd9e36cee.dip0.t-ipconnect.de. [217.227.108.238]) by smtp.gmail.com with ESMTPSA id kz20-20020a17090777d400b00780982d77d1sm594957ejc.154.2022.09.29.22.28.27 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Sep 2022 22:28:27 -0700 (PDT) From: =?utf-8?Q?Gerd_M=C3=B6llmann?= To: Stefan Monnier Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: (Stefan Monnier's message of "Thu, 29 Sep 2022 18:09:01 -0400") References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Date: Fri, 30 Sep 2022 07:28:26 +0200 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) 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. 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. Renaming that is hopefully not that much work with LSP. > [ An alternative would be to try and get rid of the `parent` field :-) > ] :-) From debbugs-submit-bounces@debbugs.gnu.org Fri Sep 30 02:11:33 2022 Received: (at 58158) by debbugs.gnu.org; 30 Sep 2022 06:11:33 +0000 Received: from localhost ([127.0.0.1]:40318 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oe9FF-00068r-0I for submit@debbugs.gnu.org; Fri, 30 Sep 2022 02:11:33 -0400 Received: from eggs.gnu.org ([209.51.188.92]:39538) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oe9FC-00068d-D7 for 58158@debbugs.gnu.org; Fri, 30 Sep 2022 02:11:31 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:52606) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oe9F6-0002qh-FQ; Fri, 30 Sep 2022 02:11:24 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=Wbcy5k25PV4Xd6f3TSGkVgrx9GgyXrbLqvc7Imx1hOg=; b=krnWhxU7/mLj8GpZ11Wr 9dCrOIDgJeDz/kaKu2lHOok2ZaI/8IOYvk6Y8U/nGEjKmUBiUTMQ03IYi5s5saI5Tga6tpB1ygwbT Fse14t2NYHUyqRmGH1E4U+KRzKawlAk/0FV3JdX/c67SvyjSixkVVTzDbjhEAVgxMXx3j/tF5X5uh YXBiajGddK5oCBO39jl6fJCOEQcsgu0jHplar4/pkssKCAixwpSoRXN7NN338+MH/EYAC0Fbem2mJ CPh1drnYyf8N/sPRz8kaojGWHAKbGy57VJ0ffRTBqlcHiGERK5nlsiU+QVddBVgelWymJhe0cPkp8 zUuVfwVRfBkm8g==; Received: from [87.69.77.57] (port=2387 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oe9F5-0005B7-Uw; Fri, 30 Sep 2022 02:11:24 -0400 Date: Fri, 30 Sep 2022 09:11:09 +0300 Message-Id: <83zgehe6iq.fsf@gnu.org> From: Eli Zaretskii To: Gerd =?utf-8?Q?M=C3=B6llmann?= In-Reply-To: (message from Gerd =?utf-8?Q?M=C3=B6llmann?= on Fri, 30 Sep 2022 07:28:26 +0200) Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful 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; charset=utf-8 Content-Transfer-Encoding: 8bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: 58158@debbugs.gnu.org, monnier@iro.umontreal.ca X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > From: Gerd Möllmann > Cc: Eli Zaretskii , 58158@debbugs.gnu.org > Date: Fri, 30 Sep 2022 07:28:26 +0200 > > Renaming that is hopefully not that much work with LSP. You should be able to do this with M-? followed by "M-x xref-query-replace-in-results RET" (the latter should be invoked in the "*xref*" buffer produced by M-?). From debbugs-submit-bounces@debbugs.gnu.org Fri Sep 30 07:31:37 2022 Received: (at 58158) by debbugs.gnu.org; 30 Sep 2022 11:31:38 +0000 Received: from localhost ([127.0.0.1]:40645 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeEEx-00082b-VT for submit@debbugs.gnu.org; Fri, 30 Sep 2022 07:31:37 -0400 Received: from mail-ej1-f49.google.com ([209.85.218.49]:44870) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeEEs-00082L-4V for 58158@debbugs.gnu.org; Fri, 30 Sep 2022 07:31:34 -0400 Received: by mail-ej1-f49.google.com with SMTP id r18so8392585eja.11 for <58158@debbugs.gnu.org>; Fri, 30 Sep 2022 04:31:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :from:to:cc:subject:date; bh=6HL0HwUo6m6n6HYKSv3b/B29sOQumpuFed5GBtEg+Kk=; b=eyChHmsKMp9xzdL/Pv4ziUC1uokFmwOf7eAwqCDZ6Xt5BXyHCslbEDH1P1NjqN/SYm f39QB72mVMM6k/xRowzf0TDVU3q/fc5l7TSP5W9wBduaIqY1T9hB5eJkNENeFQabHb1z 7hDnfbBUXhMhHFMaZdEvZ8RR5xhAIDxg/1vF6uqTJTrLolXNtpXXWNHavQxQpCE0RMfJ cClo3dvzlAzCmNKYN/DXHOkIExQkhhp1GhK2JQ4DoqRTPoxyVuymT1sw14VI7Yf8gjwe N1PHsZUdoxvoyYwZ3VHeV/kihNbcbzwpo2lo40UcUTh77DyyIomWdqu+qkxhXOzOGIl/ tTAQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :x-gm-message-state:from:to:cc:subject:date; bh=6HL0HwUo6m6n6HYKSv3b/B29sOQumpuFed5GBtEg+Kk=; b=BXje72T1sArOuhhkJaKS9I7Z+CFIvQzvv8ryQOYR6I8nskC6mWEGXz70avW1iVVmvW LOnwKHECXdYKtl4zQsBW6m9M2lhUgmBOESUXXbyuJKLEzCuNa3CKslsP7fiK2hQvyA71 AFm9GtElGUXWP8tG6SJnWLz6D9QPGOPHT1Ja5nQl8XlilQQEyVmtVbyvS0HaAEVV/kGX 9zM+V3ZDZRsPyO9kfqHvZssv3jCw9WPY6ZI79FfwGhfTdygWDVBCFm3g/HSZh3RSG2xI QGqbJXNhEAVtd2iQAq5K5Pz6PySAfe6anHqnebw1mm3mUB7zyiRDW39LITedv8LFa/9e c9Gg== X-Gm-Message-State: ACrzQf0kcRNlaTkO7jBY+IZSVf8rGhJAIiMlaJLQJESh88MiEE1vPLFZ zfDiU1KsEEQNeX5Ylhg2ocA= X-Google-Smtp-Source: AMsMyM7paOUTf4C1r2t41q5IRrMY/t5G1r3WgeAUrz7oyvDErwA44W1r6Jnr653wDpCranO11PgQEQ== X-Received: by 2002:a17:907:7e88:b0:783:305:8cac with SMTP id qb8-20020a1709077e8800b0078303058cacmr6084832ejc.439.1664537483951; Fri, 30 Sep 2022 04:31:23 -0700 (PDT) Received: from [192.168.178.21] (pd9e36cee.dip0.t-ipconnect.de. [217.227.108.238]) by smtp.gmail.com with ESMTPSA id c5-20020a17090603c500b007835316a1aesm1057795eja.65.2022.09.30.04.31.22 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 30 Sep 2022 04:31:22 -0700 (PDT) Message-ID: <13f3e7fa-4690-3ab0-f803-0812303f90f7@gmail.com> Date: Fri, 30 Sep 2022 13:31:21 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0) Gecko/20100101 Thunderbird/91.13.0 Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Content-Language: en-US To: Eli Zaretskii References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> <83zgehe6iq.fsf@gnu.org> From: =?UTF-8?Q?Gerd_M=c3=b6llmann?= In-Reply-To: <83zgehe6iq.fsf@gnu.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Score: -1.8 (-) X-Debbugs-Envelope-To: 58158 Cc: 58158@debbugs.gnu.org, monnier@iro.umontreal.ca X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.8 (--) On 22-09-30 8:11 , Eli Zaretskii wrote: >> From: Gerd Möllmann >> Cc: Eli Zaretskii , 58158@debbugs.gnu.org >> Date: Fri, 30 Sep 2022 07:28:26 +0200 >> >> Renaming that is hopefully not that much work with LSP. > > You should be able to do this with M-? followed by > "M-x xref-query-replace-in-results RET" (the latter > should be invoked in the "*xref*" buffer produced by M-?). Ok, thanks for the tip. Info for Stefan: I've now removed the per-tree null node, and make check shows no unexpected results. From debbugs-submit-bounces@debbugs.gnu.org Fri Sep 30 09:25:46 2022 Received: (at 58158) by debbugs.gnu.org; 30 Sep 2022 13:25:46 +0000 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 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 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) 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== 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) From: Stefan Monnier To: Gerd =?windows-1252?Q?M=F6llmann?= Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: ("Gerd =?windows-1252?Q?M=F6l?= =?windows-1252?Q?lmann=22's?= message of "Fri, 30 Sep 2022 07:28:26 +0200") Message-ID: References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Date: Fri, 30 Sep 2022 09:25:29 -0400 User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable X-SPAM-INFO: Spam detection results: 0 ALL_TRUSTED -1 Passed through trusted hosts only via SMTP AWL -0.044 Adjusted score from AWL reputation of From: address BAYES_00 -1.9 Bayes spam probability is 0 to 1% DKIM_SIGNED 0.1 Message has a DKIM or DK signature, not necessarily valid DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's domain X-SPAM-LEVEL: X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) 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 From debbugs-submit-bounces@debbugs.gnu.org Fri Sep 30 10:08:46 2022 Received: (at 58158) by debbugs.gnu.org; 30 Sep 2022 14:08:46 +0000 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 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 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) 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) From: =?utf-8?Q?Gerd_M=C3=B6llmann?= To: Stefan Monnier Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: (Stefan Monnier's message of "Fri, 30 Sep 2022 09:25:29 -0400") References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Date: Fri, 30 Sep 2022 16:08:36 +0200 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) 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? From debbugs-submit-bounces@debbugs.gnu.org Fri Sep 30 11:25:45 2022 Received: (at 58158) by debbugs.gnu.org; 30 Sep 2022 15:25:45 +0000 Received: from localhost ([127.0.0.1]:42675 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeHtZ-0002RO-05 for submit@debbugs.gnu.org; Fri, 30 Sep 2022 11:25:45 -0400 Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:6310) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeHtT-0002R6-JZ for 58158@debbugs.gnu.org; Fri, 30 Sep 2022 11:25:43 -0400 Received: from pmg3.iro.umontreal.ca (localhost [127.0.0.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id 207314422FB; Fri, 30 Sep 2022 11:25:34 -0400 (EDT) Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id 1C1B8441EDD; Fri, 30 Sep 2022 11:25:32 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1664551532; bh=OivdNllY/14RVEMogDOTuhTzY4HeG6d3ne33GAuCsiU=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=Bof0Ovt6an/npPjOLoGodQ7V0uMS6DtDIVi6tudSR63kZR487m3Ta4Ngg+DyXWETp qJPDUtwaq6khjS+2hTe1tYQjXl5pSl6rs2YKbzhY5lk6iYCml6u/yhpj0I+eom+HQm dNz9GdL7HLftilZgWvqJavK/iUc2RpASRm4+IEjY22ajQKp0BHsNIBPB6+sWXtS1+k 0dFbRFAkkF5LqxWii5mZf1W5V2Okc0xBRK6NaRr5shbrSU6OI8RvCpHc6l5ttZA79H kJi9jGc7t5pe4cR/1f853GRIWmYQH+I08ICxfKGUPJImp7/2PrMrzQJJSLRxxf3sc2 5TDmq9ZeyhK3g== Received: from pastel (65-110-220-202.cpe.pppoe.ca [65.110.220.202]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id C656A12023A; Fri, 30 Sep 2022 11:25:31 -0400 (EDT) From: Stefan Monnier To: Gerd =?windows-1252?Q?M=F6llmann?= Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: ("Gerd =?windows-1252?Q?M=F6l?= =?windows-1252?Q?lmann=22's?= message of "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> Date: Fri, 30 Sep 2022 11:25:30 -0400 User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-SPAM-INFO: Spam detection results: 0 ALL_TRUSTED -1 Passed through trusted hosts only via SMTP AWL -0.017 Adjusted score from AWL reputation of From: address BAYES_00 -1.9 Bayes spam probability is 0 to 1% DKIM_SIGNED 0.1 Message has a DKIM or DK signature, not necessarily valid DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's domain X-SPAM-LEVEL: X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , Andreas Politz , 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > Maybe you could also help me with the questions below? I'll try (BTW, the original author is Andreas Politz who we can still reach at . He doesn't have much time to devote to it, tho, so best not to Cc him through all the conversations). > I'm assuming, from a comment somewhere, that an interval tree is an > rb-tree with keys being interval start positions, and allowing > duplicates. Yup. > That is, if N is a node, all nodes in the subtree N->left are strictly < > N, and nodes in N->right are >=. The following code in `interval_tree_insert`: while (child != ITREE_NULL) { parent = child; offset += child->offset; child->limit = max (child->limit, node->end - offset); /* This suggests that nodes in the right subtree are strictly greater. But this is not true due to later rotations. */ child = node->begin <= child->begin ? child->left : child->right; } suggests that N->left are <= and N->right are > but my reading of the comment is that the only thing we can rely on is that N-right is >= [ I do understand this comment now :-) ] > 2. Does the tree order duplicates in a particular way? > Maybe by overlay priority, or by interval end? AFAICT, no it does not. > 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. Ordering based on interval end could arguably make sense. I'm not completely sure how/where it would benefit us, tho. Most times we look at the itree, we just look at *all* the nodes within a specific interval, so the order in which they're returned doesn't matter very much (the ordering within the tree does matter in terms of how we manage to prune the tree, but that has more to do with which elements are near the root, which is a different kind of "ordering" than the "binary tree ordering" itself). Maybe the `next/previous-overlay-change` code benefit from sub-ordering based on `end`, but I suspect the effect would be lost in the noise: if we want to speed up that part of the code, I expect that a better avenue is to rewrite the `next/previous-single-overlay-change` so as not to work by (while .. (next/previous-overlay-change ..) .. (get-char-property ..) ..) where both functions do the O(log N) itree-iteration dance, but instead doing the itree iteration itself. > 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? In terms of tree depth, no: the code preserves the RB invariants, which ensure balance regardless of ordering (or lack thereof). Stefan From debbugs-submit-bounces@debbugs.gnu.org Fri Sep 30 12:04:31 2022 Received: (at 58158) by debbugs.gnu.org; 30 Sep 2022 16:04:31 +0000 Received: from localhost ([127.0.0.1]:42713 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeIV5-0003RP-33 for submit@debbugs.gnu.org; Fri, 30 Sep 2022 12:04:31 -0400 Received: from eggs.gnu.org ([209.51.188.92]:42078) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeIV1-0003RA-2S for 58158@debbugs.gnu.org; Fri, 30 Sep 2022 12:04:29 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:33770) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oeIUt-0005sr-AF; Fri, 30 Sep 2022 12:04:20 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=References:Subject:In-Reply-To:To:From:Date: mime-version; bh=IcoRPEpT9fs4zTvRlng1X9GbLgtEMJViCg64KeEmRp8=; b=OIQA3AdwfLZz qtU9O0zqa04/t5TZJClxIRDV6XYCRiG8R4HYBHVi3M5bQKfwFuiSpaMKWoqUqYvTxaq6RibzW/VNT F5BLG6ekvqXy0HHSfTQKf6JzIJWNsQWka/sBuPMgj2Y2DPMF1KOyOoSikVHxUp+9FdBPffykkmYcs 8RJ3slU/z1S5g22ExMF0mxEyzj4wx3rUcHYLjmEHzdBY1Pa9XRRGeB6Y3n+GBJSWZwwzeaYUZuuqr wpJUBuhxAA6u4b+FqTMXrEtuSUy46jUsDrqA2JXT9C8SKZPc1AU4pCIZq+kUOJFwyiw4oMQFF+ejO EGlb4r9Qc7YGnkv2Ahq1Pw==; Received: from [87.69.77.57] (port=3065 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oeIUs-0004nQ-DJ; Fri, 30 Sep 2022 12:04:18 -0400 Date: Fri, 30 Sep 2022 19:04:05 +0300 Message-Id: <83v8p4df2i.fsf@gnu.org> From: Eli Zaretskii To: Stefan Monnier In-Reply-To: (message from Stefan Monnier on Fri, 30 Sep 2022 11:25:30 -0400) Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: gerd.moellmann@gmail.com, mail@andreas-politz.de, 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > From: Stefan Monnier > Cc: Eli Zaretskii , 58158@debbugs.gnu.org, Andreas Politz > > Date: Fri, 30 Sep 2022 11:25:30 -0400 > > > 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. > > Ordering based on interval end could arguably make sense. I'm not > completely sure how/where it would benefit us, tho. Most times we look > at the itree, we just look at *all* the nodes within a specific > interval, so the order in which they're returned doesn't matter very > much (the ordering within the tree does matter in terms of how we manage > to prune the tree, but that has more to do with which elements are near > the root, which is a different kind of "ordering" than the "binary tree > ordering" itself). Maybe the `next/previous-overlay-change` code > benefit from sub-ordering based on `end`, but I suspect the effect would > be lost in the noise: if we want to speed up that part of the code, > I expect that a better avenue is to rewrite the > `next/previous-single-overlay-change` so as not to work by (while .. > (next/previous-overlay-change ..) .. (get-char-property ..) ..) where > both functions do the O(log N) itree-iteration dance, but instead doing > the itree iteration itself. The display engine sorts the overlays, so order could be important. From debbugs-submit-bounces@debbugs.gnu.org Fri Sep 30 13:11:19 2022 Received: (at 58158) by debbugs.gnu.org; 30 Sep 2022 17:11:19 +0000 Received: from localhost ([127.0.0.1]:42838 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeJXi-0005DT-Gi for submit@debbugs.gnu.org; Fri, 30 Sep 2022 13:11:19 -0400 Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:52512) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeJXf-0005Cv-Sr for 58158@debbugs.gnu.org; Fri, 30 Sep 2022 13:11:16 -0400 Received: from pmg3.iro.umontreal.ca (localhost [127.0.0.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id 19D5044272A; Fri, 30 Sep 2022 13:11:10 -0400 (EDT) Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id 95D87442727; Fri, 30 Sep 2022 13:11:07 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1664557867; bh=VOuD7Jdhirx9qrz7e92ifV6GxUDcPSidokw1/hI4Wmk=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=L8qOOpoy3dKt0Tepjvwbl8JsiDyEVLUVv8qxQ4IzsPnigDXFodEihuoE/a7xrypSW LjxZp+7IrBT02M/m1Hs/9Ntp2c+h6svY5SmKmy3sxicdUYeDUFtE0I5G6BicZHQUdl kE2yX3WQGCgkdzujR2Ki65lsOP1YR7/cYv5D4WhXvqI2XJ09kze8N1K80Ti4TWoc1G GYdCq2y1kcTXtHqjpiaQAyoFWwhVg90kVwuDf4J3KowgEhOkSFuVJ6sGC7cb8le0fi AvvuwfB7OIXLNdvgYg8E7XDHWJuCNcKxnJ6fb3VI4wpAF9PVKizzGUqfduFCVNP7lF 3HfAlRmLgplzA== Received: from pastel (65-110-220-202.cpe.pppoe.ca [65.110.220.202]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 571D612031C; Fri, 30 Sep 2022 13:11:07 -0400 (EDT) From: Stefan Monnier To: Eli Zaretskii Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: <83v8p4df2i.fsf@gnu.org> (Eli Zaretskii's message of "Fri, 30 Sep 2022 19:04:05 +0300") Message-ID: References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> <83v8p4df2i.fsf@gnu.org> Date: Fri, 30 Sep 2022 13:11:06 -0400 User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-SPAM-INFO: Spam detection results: 0 ALL_TRUSTED -1 Passed through trusted hosts only via SMTP AWL -0.015 Adjusted score from AWL reputation of From: address BAYES_00 -1.9 Bayes spam probability is 0 to 1% DKIM_SIGNED 0.1 Message has a DKIM or DK signature, not necessarily valid DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's domain X-SPAM-LEVEL: X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: gerd.moellmann@gmail.com, mail@andreas-politz.de, 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) >> Ordering based on interval end could arguably make sense. I'm not >> completely sure how/where it would benefit us, tho. Most times we look >> at the itree, we just look at *all* the nodes within a specific >> interval, so the order in which they're returned doesn't matter very >> much (the ordering within the tree does matter in terms of how we manage >> to prune the tree, but that has more to do with which elements are near >> the root, which is a different kind of "ordering" than the "binary tree >> ordering" itself). Maybe the `next/previous-overlay-change` code >> benefit from sub-ordering based on `end`, but I suspect the effect would >> be lost in the noise: if we want to speed up that part of the code, >> I expect that a better avenue is to rewrite the >> `next/previous-single-overlay-change` so as not to work by (while .. >> (next/previous-overlay-change ..) .. (get-char-property ..) ..) where >> both functions do the O(log N) itree-iteration dance, but instead doing >> the itree iteration itself. > > The display engine sorts the overlays, so order could be important. Indeed, for things like `overlays_at` it would be handy if the iterator could return the right overlays already in the right order, so we don't have to `sort_overlays`. But in `sort_overlays` the `priority` property takes precedence, so if we order the RB tree based on that ordering, we will lose the main purpose of the change, i.e. finding the overlays at POS in O(log N) time, because the `compare_overlays` ordering does not let us know that all of the left or right subtree is outside of a given interval. IOW the itree has to use a different ordering than that of `compare_overlays` anyway, so we're still forced to (re-)sort afterwards with `sort_overlays` :-( Stefan From debbugs-submit-bounces@debbugs.gnu.org Fri Sep 30 14:30:12 2022 Received: (at 58158) by debbugs.gnu.org; 30 Sep 2022 18:30:13 +0000 Received: from localhost ([127.0.0.1]:42905 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeKm4-00078G-LG for submit@debbugs.gnu.org; Fri, 30 Sep 2022 14:30:12 -0400 Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:9281) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeKm0-00076s-02 for 58158@debbugs.gnu.org; Fri, 30 Sep 2022 14:30:10 -0400 Received: from pmg1.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 9C11E1000F2; Fri, 30 Sep 2022 14:30:02 -0400 (EDT) Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 01D901000D0; Fri, 30 Sep 2022 14:30:01 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1664562601; bh=On669WFac4eQgGU99fqodlM8avIjno290327po+K8Vk=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=WUZ9nUaaoHRBbTd8o6zVYwnMVg6rbOXBhLXJB6zuE4GXEnWDosSeYz1XHMaeA+Vg0 PzK9ljE360p1Bbh18SKIHbt5sNxt5mwo6XXS/JBksmkLs9rVjoTkYORA8OAIAjtAHf NsOQIzdOGNCBapsVR07nROV9ps07jdomE58cjH6XZR56lxmZrijm1bdhJ0tcIGJZM+ vQODURnoLuWkmEbeDGx2hdzkYoeVY5QInMymMP2vc7GQkJB9YTUWHEa7dNiFTbYy26 FBlwU+sZLeLsj03DnaYxhj+bE1mXrSOY5JPoJQ9SPXkxh6GMZ/vaDaeB2l71gCZIAR cXRqb0iDEdrvQ== Received: from alfajor (unknown [45.44.229.252]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id D24F9120DDB; Fri, 30 Sep 2022 14:30:00 -0400 (EDT) From: Stefan Monnier To: Gerd =?windows-1252?Q?M=F6llmann?= Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: <13f3e7fa-4690-3ab0-f803-0812303f90f7@gmail.com> ("Gerd =?windows-1252?Q?M=F6llmann=22's?= message of "Fri, 30 Sep 2022 13:31:21 +0200") Message-ID: References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> <83zgehe6iq.fsf@gnu.org> <13f3e7fa-4690-3ab0-f803-0812303f90f7@gmail.com> Date: Fri, 30 Sep 2022 14:29:59 -0400 User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-SPAM-INFO: Spam detection results: 0 ALL_TRUSTED -1 Passed through trusted hosts only via SMTP AWL -0.070 Adjusted score from AWL reputation of From: address BAYES_00 -1.9 Bayes spam probability is 0 to 1% DKIM_SIGNED 0.1 Message has a DKIM or DK signature, not necessarily valid DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's domain X-SPAM-LEVEL: X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > Info for Stefan: I've now removed the per-tree null node, and make check > shows no unexpected results. Thanks. It's an improvement, but I still don't understand how it works :-( Stefan From debbugs-submit-bounces@debbugs.gnu.org Fri Sep 30 21:57:47 2022 Received: (at 58158) by debbugs.gnu.org; 1 Oct 2022 01:57:47 +0000 Received: from localhost ([127.0.0.1]:43236 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeRlC-0003cx-RB for submit@debbugs.gnu.org; Fri, 30 Sep 2022 21:57:47 -0400 Received: from eggs.gnu.org ([209.51.188.92]:56288) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeRl8-0003ci-Rc for 58158@debbugs.gnu.org; Fri, 30 Sep 2022 21:57:46 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:44074) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oeRl2-0002oM-Tm; Fri, 30 Sep 2022 21:57:36 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=Date:References:Subject:In-Reply-To:To:From: mime-version; bh=6kB74Bjqghqwb+0rWx1Ds/h4lC3HI3W+Wo88kM+s5DI=; b=e4AyfhHlkLtD xCKYxYRkYwN/oeHq5eRzKWYygG3USnxtndmjsw6VwZkbv1lj7nTsoZiQ80mJVXxyI5lbdjFFek5So Nb9C2oqhgVL/DRhj/MOMppFf9Pr03rEV2Ch8ZF/ZFj0i3C12N86XGMjKW4VTG0Bm7bOn3hzXqMosj sz/WOr/bqs1BKtfWRiX78Q9fMAgOAAq8oQxaUBcNQeTl53NX5XW6Cs+dDj/LxGJVSnZlbYI4RjUta 0qjXSs7ADAy5f+5geEKSnAQqCXv634p3kC+Pzq1A1/GyGWWmoyiVB/PeTeUX5tQ0RU+gZvW50o1ad NNnHANuYSQq87IEXmmCgXw==; Received: from rms by fencepost.gnu.org with local (Exim 4.90_1) (envelope-from ) id 1oeRl2-0001Ra-AU; Fri, 30 Sep 2022 21:57:36 -0400 Content-Type: text/plain; charset=Utf-8 From: Richard Stallman To: Gerd =?iso-8859-1?Q?M=C3=B6llmann?= In-Reply-To: (message from Gerd =?iso-8859-1?Q?M=C3=B6llmann?= on Thu, 29 Sep 2022 11:09:17 +0200) Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> Message-Id: Date: Fri, 30 Sep 2022 21:57:36 -0400 X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: eliz@gnu.org, 58158@debbugs.gnu.org, monnier@iro.umontreal.ca X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: rms@gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) [[[ To any NSA and FBI agents reading my email: please consider ]]] [[[ whether defending the US Constitution against all enemies, ]]] [[[ foreign or domestic, requires you to follow Snowden's example. ]]] > I think it simply can't be that what is basically walking a binary tree > requires such restrictions. If we allow running complicated code during the tree walk, that would be asking for trouble. But if the operations done during the tree walk are simple and written in C, it should be clear that there is no possibility of this kind of a bug. Isn't that the case? > > What has to do with overlays. To name a few: overlay-at, overlays-in, > > next-overlay-change, previous-overlay-change, overlay-lists, ... Those operations can be done in C with no risk of signaling an error. That ought to be sufficient, as long as we don't need the code to be reentrant. If the code needs to be reentrant then we would have to eliminate the "visited" flag. But if we don't run Lisp code during the tree-walk, we should not need it to be reentrant. -- Dr Richard Stallman (https://stallman.org) Chief GNUisance of the GNU Project (https://gnu.org) Founder, Free Software Foundation (https://fsf.org) Internet Hall-of-Famer (https://internethalloffame.org) From debbugs-submit-bounces@debbugs.gnu.org Sat Oct 01 01:07:02 2022 Received: (at 58158) by debbugs.gnu.org; 1 Oct 2022 05:07:02 +0000 Received: from localhost ([127.0.0.1]:43411 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeUiM-0008RQ-6C for submit@debbugs.gnu.org; Sat, 01 Oct 2022 01:07:02 -0400 Received: from mail-ed1-f41.google.com ([209.85.208.41]:37797) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeUiI-0008QH-UB for 58158@debbugs.gnu.org; Sat, 01 Oct 2022 01:07:01 -0400 Received: by mail-ed1-f41.google.com with SMTP id a41so8332517edf.4 for <58158@debbugs.gnu.org>; Fri, 30 Sep 2022 22:06:58 -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=+YCkiWRhBoBJStJZSY7qKRgSYZSiqG4Juy72jxJD84g=; b=HyaAm4EgH0FtZmSIvUM+kcOPsBQW/RllOB/eaxNboBjLaP/nKAFFxrCDbheluBbxun C5nRhoiR7umly5hf5wYbrIYCxZyHWI2YuIIbxbV0mnz5f3bWtRcuJ33GDQdc2pRwcPss f5vCvQ3pG2CezDq89NDXmeUv+bvP/0PjuLf4Jv3hRWuOILmOqTMJUd+wG6bzIbp/6uip R45C9ZnxpxI1xZOCMuz7wJ0QNtiIkDmn3vSlGrTJw/7d1bJ1rFYxq3evoRP2msWg+pIc 7Z735r9vIM1bk5u3bX0q31WMr0G6UGwTk1ZlIbECYnqwl0h/H+p0BuO3iGGkoHkOaJfR W+Cg== 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=+YCkiWRhBoBJStJZSY7qKRgSYZSiqG4Juy72jxJD84g=; b=KQvYuJ9Txli88z1zIwPzFCR2pEjBuQecpNcJJuvcDDQccoWOAaxoXKjPnThMNP+Y5g aBhhcN1g6UPapj6UJrdVshXAsco8gAXbGnoLUgGJfkWyvKY9Fje3rQyUmM9ljEepDDZw S9uuARoeChluHVt+ZFqBMrSr8OGWzzECANRlYZjfCsXInB6w7QdMxBg5RMMCGH7UoHRB nPUSOgpsi0Gd1OCGzEl2GQRRloGoaVIqK6KEnm6QwUF4P/hXb2VMXfuHJY6bHiC1Z9zc 4cezGm435odXAP8JVrSvym3Ts7lfPcPRGZRV12JOCLNLgN8sSy6OULU2zrDFHO2Gw09r lOFA== X-Gm-Message-State: ACrzQf1MvgO1fez94TfG5QevUxJMvdfQuLSVrQMCceiwSOHCtr17I7Fn NOo15FqRz252P/bgYfVzTdY= X-Google-Smtp-Source: AMsMyM7zVw00VFOqaIf8gXIMXLOUzkHX0upRIF4RnKj2Acys0TkW2FFMAQfwynLYbO3G4xLzBQrC4g== X-Received: by 2002:a05:6402:d05:b0:425:b5c8:faeb with SMTP id eb5-20020a0564020d0500b00425b5c8faebmr9975780edb.273.1664600813020; Fri, 30 Sep 2022 22:06:53 -0700 (PDT) Received: from Mini.fritz.box (p4fe3ace2.dip0.t-ipconnect.de. [79.227.172.226]) by smtp.gmail.com with ESMTPSA id v18-20020a50d092000000b00457e5a760e3sm2876778edd.54.2022.09.30.22.06.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 30 Sep 2022 22:06:52 -0700 (PDT) From: =?utf-8?Q?Gerd_M=C3=B6llmann?= To: Stefan Monnier Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: (Stefan Monnier's message of "Fri, 30 Sep 2022 11:25:30 -0400") References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Date: Sat, 01 Oct 2022 07:06:50 +0200 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , Andreas Politz , 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) Stefan Monnier writes: >> That is, if N is a node, all nodes in the subtree N->left are strictly < >> N, and nodes in N->right are >=. > > The following code in `interval_tree_insert`: > > while (child != ITREE_NULL) > { > parent = child; > offset += child->offset; > child->limit = max (child->limit, node->end - offset); > /* This suggests that nodes in the right subtree are strictly > greater. But this is not true due to later rotations. */ > child = node->begin <= child->begin ? child->left : child->right; > } > > suggests that N->left are <= and N->right are > but my reading of the > comment is that the only thing we can rely on is that N- N->right is >= Phew. I'm not sure but I get the feeling that makes implementing a successor function, let's say, challenging. I wonder how std::multimap deals with that. Hm. Anyways, with your removal of the visited flag (N thumbs up, for large values of N :-)), most of the problems I preceived are gone anyway. So, I guess we can live with the iteration stack, which seems to work fine, and the alternative is only nice to have, now. (And impacts are getting closer in the real world here, so I'm a bit distracted anyway.) > > [ I do understand this comment now :-) ] :-) > >> 2. Does the tree order duplicates in a particular way? >> Maybe by overlay priority, or by interval end? > > AFAICT, no it does not. Ok. >> 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. > > Ordering based on interval end could arguably make sense. I'm not > completely sure how/where it would benefit us, tho. Most times we look > at the itree, we just look at *all* the nodes within a specific > interval, so the order in which they're returned doesn't matter very > much (the ordering within the tree does matter in terms of how we manage > to prune the tree, but that has more to do with which elements are near > the root, which is a different kind of "ordering" than the "binary tree > ordering" itself). Maybe the `next/previous-overlay-change` code > benefit from sub-ordering based on `end`, but I suspect the effect would > be lost in the noise: if we want to speed up that part of the code, > I expect that a better avenue is to rewrite the > `next/previous-single-overlay-change` so as not to work by (while .. > (next/previous-overlay-change ..) .. (get-char-property ..) ..) where > both functions do the O(log N) itree-iteration dance, but instead doing > the itree iteration itself. Thanks. > >> 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? > > In terms of tree depth, no: the code preserves the RB invariants, which > ensure balance regardless of ordering (or lack thereof). Ok, thanks for your insights! From debbugs-submit-bounces@debbugs.gnu.org Sat Oct 01 03:00:33 2022 Received: (at 58158) by debbugs.gnu.org; 1 Oct 2022 07:00:33 +0000 Received: from localhost ([127.0.0.1]:43521 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeWUB-0005Ca-Cz for submit@debbugs.gnu.org; Sat, 01 Oct 2022 03:00:33 -0400 Received: from eggs.gnu.org ([209.51.188.92]:41840) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeWU6-0005C6-U5 for 58158@debbugs.gnu.org; Sat, 01 Oct 2022 03:00:30 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:59564) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oeWU0-0000u4-Pu; Sat, 01 Oct 2022 03:00:20 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=References:Subject:In-Reply-To:To:From:Date: mime-version; bh=n2+vtYhktYDAMmZL0gU7mVyqMsuI9CCJuB4XIju+Q8g=; b=rBHIzFGL7PNW fzp57qWIPQLqHRY668gn7dWarcU7PNElzPxAyHqZ+le8Nb4Efp3dpvCMNtG+/18PR1dsiKbpXgWhF Vxz6GLyxGoh2B48d3jAuGL/mByIqSHBKLgyJpexZkhOvrojaBnDi8e2FEAy1ISmk+iFXVJLdBN/TQ +hZPQsJLIimyhmHoIHdaHoW+93je84IdvCQt4QBDkO72Twcv7A/Rh/GaZ1IV4ROlG118TVYi3EyN4 +u7nf2LuqLasHX7nNAr+gEbi7cKQQgT1KbQ+813GLjQhs4/NPYME1LAdmUmtBqrGlLLJ5NKudJmud WL4Fc1XVFdNjkfeQFd5Qeg==; Received: from [87.69.77.57] (port=1965 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oeWTz-00053n-5n; Sat, 01 Oct 2022 03:00:19 -0400 Date: Sat, 01 Oct 2022 10:00:03 +0300 Message-Id: <83zgegav0s.fsf@gnu.org> From: Eli Zaretskii To: rms@gnu.org In-Reply-To: (message from Richard Stallman on Fri, 30 Sep 2022 21:57:36 -0400) Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: gerd.moellmann@gmail.com, 58158@debbugs.gnu.org, monnier@iro.umontreal.ca X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > From: Richard Stallman > Cc: eliz@gnu.org, 58158@debbugs.gnu.org, monnier@iro.umontreal.ca > Date: Fri, 30 Sep 2022 21:57:36 -0400 > > > > What has to do with overlays. To name a few: overlay-at, overlays-in, > > > next-overlay-change, previous-overlay-change, overlay-lists, ... > > Those operations can be done in C with no risk of signaling an error. I think such assumptions were proven dangerous at best in the long run. The way Emacs develops, we constantly add more and more hooks to C code, and more and more direct calls into Lisp from C. These invalidate any assumptions about "no risk of signaling an error", even if they were originally true when the code was first written. Moreover, we test for QUIT in operations that can be prolonged ones (and for a good reason), so any long loop in C could potentially throw to top level if the user pressed C-g. All in all, experience shows that making such assumptions in Emacs is unsafe. From debbugs-submit-bounces@debbugs.gnu.org Sat Oct 01 03:25:57 2022 Received: (at 58158) by debbugs.gnu.org; 1 Oct 2022 07:25:57 +0000 Received: from localhost ([127.0.0.1]:43566 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeWsm-0005ok-P5 for submit@debbugs.gnu.org; Sat, 01 Oct 2022 03:25:57 -0400 Received: from mail-ej1-f46.google.com ([209.85.218.46]:43635) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeWsl-0005oX-NH for 58158@debbugs.gnu.org; Sat, 01 Oct 2022 03:25:56 -0400 Received: by mail-ej1-f46.google.com with SMTP id lh5so13092885ejb.10 for <58158@debbugs.gnu.org>; Sat, 01 Oct 2022 00:25:55 -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=ublTLgVmngEgr3/sxVqNEUE4OnoBOxZjwkVLtho+nJk=; b=qUoIy5UvAy6w9PBWT8EZG1hW7RGTVpFhf1lzxU2G8VUDtOXaRvnplwAGmAIkkuUYBb UnNVkXX1KOCe5/3++YaWwXehCmho/ogrdYNMBahB4aLnvMn9QkgAtdfr8Jd7sXPzhEjU uGizDyrGf0Vj+u4WvxEGePwFxYauFp8ZX903hKGT3EnI8MMM61upEWI9TV/snKuOMs4j rzUnwALRpZy/SV6A9ClSybagtzwVthcp1FVnnD7ZDXmi/B/JYQfj9SNmFHwjsPFN9NZU Ovu+V26RNKUGTCrL9u5c2N5VxmeZ86F47ZlAKnaB8lp/AqUNKlMJODqOZ4bJiTuhgLZH 8OzA== 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=ublTLgVmngEgr3/sxVqNEUE4OnoBOxZjwkVLtho+nJk=; b=iBaPuY5nT2XfkV7vcFN7WRXKCY9vZW42pJ47eZ0uNe6bVAzeihdU7RBB+3KWlqawMH mwDV0fj8WM28+Ej8fdzNXi73vp/MH3EaFozqM1KWygKldcWuGD0uGv3xsNWz4gX8/uB4 +WrOwfAH1vXy68GY5FsrSxj/JOtXBbm39WHiCPJcPZ35SJ2mxpN6Pt0ZqiGHtV5Or4lZ V+bNMlecgRsF0MDdBytTt9hEL3m2vtR+klpQETx1D/c+diKKvRtTfE60cWNhKLxSgbMe YakDmyvgDZ/a27LFMfbahPvhTI1SnoS9VRqVYafF+CnpqpZfbP+ElKveeNSUonLchelR 7POQ== X-Gm-Message-State: ACrzQf0sUOScoY4/RctPqqxVSMcwLj+HWDXlYNnpDizqrU6YGOQCjW8Y uXypXTCZUD6euU4gH50LY8QcQ75g22g= X-Google-Smtp-Source: AMsMyM7bviJ5/HENSJRClSHYeTzJ3IdSizaZkXfF9+EgZnEADRP7aHzostx1O2nB/1HDXrdOQFQ9Lg== X-Received: by 2002:a17:907:9708:b0:787:6f95:2bff with SMTP id jg8-20020a170907970800b007876f952bffmr8851867ejc.81.1664609149557; Sat, 01 Oct 2022 00:25:49 -0700 (PDT) Received: from Mini.fritz.box (p4fe3ace2.dip0.t-ipconnect.de. [79.227.172.226]) by smtp.gmail.com with ESMTPSA id q26-20020a17090676da00b0077ce503bd77sm2268950ejn.129.2022.10.01.00.25.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 01 Oct 2022 00:25:48 -0700 (PDT) From: =?utf-8?Q?Gerd_M=C3=B6llmann?= To: Stefan Monnier Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: (Stefan Monnier's message of "Fri, 30 Sep 2022 11:25:30 -0400") References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Date: Sat, 01 Oct 2022 09:25:47 +0200 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , Andreas Politz , 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) Stefan Monnier writes: >> Maybe you could also help me with the questions below? > > I'll try (BTW, the original author is Andreas Politz who we can still > reach at . He doesn't have much time to devote > to it, tho, so best not to Cc him through all the conversations). > >> I'm assuming, from a comment somewhere, that an interval tree is an >> rb-tree with keys being interval start positions, and allowing >> duplicates. > > Yup. > >> That is, if N is a node, all nodes in the subtree N->left are strictly < >> N, and nodes in N->right are >=. > > The following code in `interval_tree_insert`: > > while (child != ITREE_NULL) > { > parent = child; > offset += child->offset; > child->limit = max (child->limit, node->end - offset); > /* This suggests that nodes in the right subtree are strictly > greater. But this is not true due to later rotations. */ > child = node->begin <= child->begin ? child->left : child->right; > } > > suggests that N->left are <= and N->right are > but my reading of the > comment is that the only thing we can rely on is that N- N->right is >= > Yup. I've used overlay-tree a bit (compile with ITREE_DEBUG defined after pulling), and used this: (defun make-ivs () (with-current-buffer (get-buffer-create "*iv*") (delete-all-overlays) (erase-buffer) (insert (make-string 50 ?x)) (let ((o1 (make-overlay 1 1)) (o2 (make-overlay 10 11)) (o3 (make-overlay 10 12)) (o4 (make-overlay 1 1)) ) (move-overlay o4 10 13) (overlay-tree)))) (pp (make-ivs)) ((:begin 10 :end 12 :limit 13 :offset 0 :rear-advance nil :front-advance nil) ((:begin 1 :end 1 :limit 13 :offset 0 :rear-advance nil :front-advance nil) nil ((:begin 10 :end 13 :limit 13 :offset 0 :rear-advance nil :front-advance nil) nil nil)) ((:begin 10 :end 11 :limit 11 :offset 0 :rear-advance nil :front-advance nil) nil nil)) That's [10, 12] / \ [1, 1] [10, 11] / \ /\ [10, 13] / \ The 10 is found "all over the place". I surmise no reasonable successor function can be written for such a tree. I have to look at std::multimap, they manage to do this somehow. From debbugs-submit-bounces@debbugs.gnu.org Sat Oct 01 06:55:53 2022 Received: (at 58158) by debbugs.gnu.org; 1 Oct 2022 10:55:53 +0000 Received: from localhost ([127.0.0.1]:43770 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oea9x-000516-1w for submit@debbugs.gnu.org; Sat, 01 Oct 2022 06:55:53 -0400 Received: from mail-ej1-f52.google.com ([209.85.218.52]:38513) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oea9u-00050s-Tg for 58158@debbugs.gnu.org; Sat, 01 Oct 2022 06:55:51 -0400 Received: by mail-ej1-f52.google.com with SMTP id nb11so13728855ejc.5 for <58158@debbugs.gnu.org>; Sat, 01 Oct 2022 03:55:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:user-agent:message-id:date :references:in-reply-to:subject:cc:to:from:from:to:cc:subject:date; bh=qNAPSkWxQ7PNcU3lfdVdiVRNi9sWCpmvUKlRlu1IOBw=; b=TghEZR7fsmeLGgbkjzz9NeFF9roBNaSbxFLGMtUdNC1yvlOGkpQQpk3LH12M4QEO1R 1+1I90oXkAuXRmXFJ4DpxL1giovKmbxR8itqZ9tM/mSPSyAPCQv9qMR+3qW0QYQ8wYka UHR9nudicmkdiNr/soiqM/BWHC/Z2JauwpZ6oEdyVcsSu9m5vTu+1dSiU9ELHopnyS7P NPClaZLkn4Jxid3D2Lkg9IYCYQgin3BI1pPCodIT7CyaizjB4cUZ4zsMTv/E/QQkDDSI KGAYf8JwQv8kmtqrWefdtT3tjhf7axsiVxoOXIrKb+sl04x1gRp7Ef63yqHe754Dfofg j1cw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding: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=qNAPSkWxQ7PNcU3lfdVdiVRNi9sWCpmvUKlRlu1IOBw=; b=Kx7vdc9MBnbOkTB+2hYhopBfgbikyH6P3nWFO1tgDt2RKuWoZFf0aNmiLOL5tP+rLW kNY/fvFTIb1QKXam0zmvtfUGI5doEd+NAZm3fK6zv0hz6jOS+csrqJn0NSs/ztJ+nMzo bpaTYlcVCF6rNuXzKCEOOXXuDqZ+CvvMr/4x7axhGd1D5eAs/P0flBBSgB5MmDWQAASn wRl9TG+77klqBQhWAlSaCGgmP22xXyYdd4InEMU5j9+gzZRbkzSXujMgAfGlYm73TgtC 1c/57FAUQQe6K5FiE6yyF2BSg5XQ5qJoK3NrubnGrYJS2997n/ulx2cthqaRENsx6p1J dSIw== X-Gm-Message-State: ACrzQf0Qel0sDPUZH2CFj3BSByGkqLqlfKFH3x8dCjSUS4ZuIpt0rPO6 HhzhoZrvG5/3r6XsUctnxmsp/+ibGW8= X-Google-Smtp-Source: AMsMyM66h15grNCLfDgOpde74pTAZhCHyDvO56QkLBHqjmHyW7aWzpG5wsUK49eneZMTWWzU4rCtQg== X-Received: by 2002:a17:906:a3c2:b0:783:19a2:74d3 with SMTP id ca2-20020a170906a3c200b0078319a274d3mr9290543ejb.288.1664621744561; Sat, 01 Oct 2022 03:55:44 -0700 (PDT) Received: from Mini.fritz.box (p4fe3ace2.dip0.t-ipconnect.de. [79.227.172.226]) by smtp.gmail.com with ESMTPSA id cz7-20020a0564021ca700b0045724875fa2sm3353814edb.15.2022.10.01.03.55.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 01 Oct 2022 03:55:43 -0700 (PDT) From: =?utf-8?Q?Gerd_M=C3=B6llmann?= To: Stefan Monnier Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: ("Gerd =?utf-8?Q?M=C3=B6llman?= =?utf-8?Q?n=22's?= message of "Sat, 01 Oct 2022 09:25:47 +0200") References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Date: Sat, 01 Oct 2022 12:55:42 +0200 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , Andreas Politz , 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) Gerd M=C3=B6llmann writes: > I have to look at std::multimap, they manage to do this somehow. Well, I should have thought of that, because it's obvious from the fact they are able to use successor/predecessor functions :-/. The equivalent in our code would go like below, which is just written down in a hurry, so please bear with me. It's just about the idea. So: Insert a new interval_node only if overlay start is not in the tree already. If the contains a node for the start, make the node's value a list of overlays, and add the new one to it in an order that's convenient (The STL uses insertion order). As a consequence, keys is the rb-tree are unique, and it is always strictly ordered, rotations don't change that. The min node is the left-most node in a tree, and so on. So far so good. An iterator in the order min->max would have to record the interval_node in the tree plus information where in the list of overlays it is, if it is in any. Finding the next node is implemented with a successor function like the one I've shown from libstdc++. To find all overlays containing a given position POS, find the node whose start is <=3D POS. Start at the root of the tree, and walk the left link until we find the ndoes's start is <=3D POS. Then iterate forward until start > POS, returning only overlapping overlays. Finding overlays intersecting an interval [BEG, END] is not as nice, but we can exclude intervals starting after END. So we have to iterate over all overlays from the minimum of the tree, and iterate forward until we reach the first excluded one. That's so "easy" that even I can understand how it works :-). What am I overlooking? From debbugs-submit-bounces@debbugs.gnu.org Sat Oct 01 09:54:54 2022 Received: (at 58158) by debbugs.gnu.org; 1 Oct 2022 13:54:54 +0000 Received: from localhost ([127.0.0.1]:44048 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oecxB-0005vY-Oc for submit@debbugs.gnu.org; Sat, 01 Oct 2022 09:54:54 -0400 Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:41687) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oecx9-0005vI-S4 for 58158@debbugs.gnu.org; Sat, 01 Oct 2022 09:54:52 -0400 Received: from pmg1.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 191DA100121; Sat, 1 Oct 2022 09:54:46 -0400 (EDT) Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 8FA601000DF; Sat, 1 Oct 2022 09:54:44 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1664632484; bh=Rv05Biz8FSRw63tFlyG6CXwRDHnELMoSJUzLK9ytav4=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=buujRDAZI7N7OHu+BM8qdi+wQw2GYFFdUlck3v2a4WtoSf3xE9pOrLJep4844R2WL mD0hu0usU42nPQf5TFwyT5rd2T5wgliblzIRyJ18KGGaGw2bfS+SqDv6FcBf/x0xZA JsJc8GTa4IrYVMepLWpV7SOHZ9Du1RXHO11jlprQXeZ5yRkDK3BgPsa6mbp7BpOdVZ N1HdSg2yEqxq5CXbS1b+9eM/UeGJi9TSY6bt7BpL5Eh/vwltLyPGtY38Z5LkGT8zdT I3GDLuHOwkmuvxZxCvnNT9GMmkncz1l8ypSZTwmTeYL1K5/hm7kmDPF9de06u0rSdV T/8FoFUzyOBXA== Received: from pastel (65-110-220-202.cpe.pppoe.ca [65.110.220.202]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 54766120513; Sat, 1 Oct 2022 09:54:44 -0400 (EDT) From: Stefan Monnier To: Gerd =?windows-1252?Q?M=F6llmann?= Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: ("Gerd =?windows-1252?Q?M=F6l?= =?windows-1252?Q?lmann=22's?= message of "Sat, 01 Oct 2022 07:06:50 +0200") Message-ID: References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) Date: Sat, 01 Oct 2022 09:54:36 -0400 MIME-Version: 1.0 Content-Type: text/plain X-SPAM-INFO: Spam detection results: 0 ALL_TRUSTED -1 Passed through trusted hosts only via SMTP AWL -0.040 Adjusted score from AWL reputation of From: address BAYES_00 -1.9 Bayes spam probability is 0 to 1% DKIM_SIGNED 0.1 Message has a DKIM or DK signature, not necessarily valid DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's domain X-SPAM-LEVEL: X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , Andreas Politz , 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) >> The following code in `interval_tree_insert`: [...] >> suggests that N->left are <= and N->right are > but my reading of the >> comment is that the only thing we can rely on is that N-> N->right is >= > > Phew. I'm not sure but I get the feeling that makes implementing a > successor function, let's say, challenging. I don't think it makes any difference in that respect, no. The notion of "successor" is just "the successor in the in-order traversal of the tree" and while rotations change the initial property that "N->right are >", they don't change the in-order traversal output (they don't re-order nodes w.r.t in-order traversal (or in reverse order for that matter)). As alluded to at the end of my previous email, while RB trees are typically used for your usual binary tree which comes with some notion of ordering that makes lookup O(log N), the RB trees ensure balance without relying on any notion of ordering since the rotations just blindly preserve the order as a side effect but they don't themselves need to call the ordering function to decide how to do their job. Stefan From debbugs-submit-bounces@debbugs.gnu.org Sat Oct 01 10:01:15 2022 Received: (at 58158) by debbugs.gnu.org; 1 Oct 2022 14:01:15 +0000 Received: from localhost ([127.0.0.1]:45445 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oed3L-0006Ss-B4 for submit@debbugs.gnu.org; Sat, 01 Oct 2022 10:01:15 -0400 Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:15939) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oed3J-0006Se-Iv for 58158@debbugs.gnu.org; Sat, 01 Oct 2022 10:01:13 -0400 Received: from pmg1.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 6B95B100138; Sat, 1 Oct 2022 10:01:07 -0400 (EDT) Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 1C39B1000E7; Sat, 1 Oct 2022 10:01:06 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1664632866; bh=dZnrnCtRfmMKo9bms32TlHq1W3uROLF7pxIb2KUiWl4=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=o+sucbuf4PzQNbWy9zOwjAV0O+fwM8qPNkxCWiZqM3EkQ0dS0i+bv/fPLd6McT2lZ VgmZlH/o38AdHovcD9+u7tX+3vn8cW3ArKSQ6z2K0YIx4G8WdUd8hs9mFIX+gD3d/o Wfu85p8URT5cRwVSICjYdDBrmxBnUrvXXRj0JJtKxFgEMCsw8HETMP4QmFafZEl+ub gQs8hqt/Mf2zbeoFKSKrw8MCtNHwL3pFFPwoCo7a4Yz5Oezamc3ShLusI2Crv2Xx+V tyDQNt3wB5+pYvctPl5C5utaXEqzBNiSIxdE8oHOiJTjHwCl75CenSjhnADPxtPh55 TYuODEKPSybGw== Received: from pastel (65-110-220-202.cpe.pppoe.ca [65.110.220.202]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id E41AE120815; Sat, 1 Oct 2022 10:01:05 -0400 (EDT) From: Stefan Monnier To: Gerd =?windows-1252?Q?M=F6llmann?= Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: ("Gerd =?windows-1252?Q?M=F6l?= =?windows-1252?Q?lmann=22's?= message of "Sat, 01 Oct 2022 09:25:47 +0200") Message-ID: References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Date: Sat, 01 Oct 2022 10:01:04 -0400 User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-SPAM-INFO: Spam detection results: 0 ALL_TRUSTED -1 Passed through trusted hosts only via SMTP AWL -0.040 Adjusted score from AWL reputation of From: address BAYES_00 -1.9 Bayes spam probability is 0 to 1% DKIM_SIGNED 0.1 Message has a DKIM or DK signature, not necessarily valid DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's domain X-SPAM-LEVEL: X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , Andreas Politz , 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > That's > > [10, 12] > / \ > [1, 1] [10, 11] > / \ /\ > [10, 13] > / \ > > The 10 is found "all over the place". "all over the place" if you consider the pre-order or post-order traversal, indeed. But if you look at the in-order traversal (e.g., the one you'd get from C++ `local_Rb_tree_increment` you showed), you get the expected result: [1, 1] [10, 13] [10, 12] [10, 11] -- Stefan From debbugs-submit-bounces@debbugs.gnu.org Sun Oct 02 04:06:10 2022 Received: (at 58158) by debbugs.gnu.org; 2 Oct 2022 08:06:10 +0000 Received: from localhost ([127.0.0.1]:46192 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oetzG-00024J-9N for submit@debbugs.gnu.org; Sun, 02 Oct 2022 04:06:10 -0400 Received: from mail-ed1-f46.google.com ([209.85.208.46]:46612) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oetzF-000247-3Q for 58158@debbugs.gnu.org; Sun, 02 Oct 2022 04:06:09 -0400 Received: by mail-ed1-f46.google.com with SMTP id m15so10878293edb.13 for <58158@debbugs.gnu.org>; Sun, 02 Oct 2022 01:06:09 -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=RqmRB/USNsJWk68wcvZOkRSPzBZEZIq7eKYoP9uR5Kw=; b=i9LdP8Oyb1acU8JPcfCBcXFhVBi8uTfb4BhDbqyZGtzzpm6sRCcOV8iGUE/Wpqp21b my4HhZrmghA5DGtL1HGc85Ah9qaTZAHw1r4foVvbDGe4pq17NmxHNp2yYNc88DiemWoe +CjCuakJvh/nrLXZ2IGrz6EYRn8wafw8TfHf74QQYOHGLCaS9vqKbZoSN2rK82ZhZG6a ohqWJvLqgp2kzRRMzCieSx5+Z8GgRlvssuuUB4GrlN2WVTaFSfgus4xGTjEwHNeSUhjd ocN/VfH/KzkT1Qz/HBGft1uxLTlesMFC+lcdemYhLpHjqXJP0r54D05qtHNVBaLvzqLa UhvQ== 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=RqmRB/USNsJWk68wcvZOkRSPzBZEZIq7eKYoP9uR5Kw=; b=kD0Xlu5gHfilVqVIq8oUzZojechrGWnDJz8YyvJazyF8PhxU8pDxb9CNw6flByTOtR h7gsOKHB/FHN+fGAIrlxIzzQq3E2Y5fbbaG9XF5yLkVPMEz4FMKKBLUNS0+kKb9rra6r Jr/pwBQgmOX3FK3AZGqP6S1Sg1SagjrGgEkH4VgIT2ZvrCGgF+OCqfiOmsR/KC9umigo aRnfFDDAHfOfrXJBa2LT2uO6dTIB0w1lGTZRBGFhe2HkqKhJfr9RfnaoauCe7UdQ3kxl MBMTYtXlF/Qxn3zZJa9itvD83NSTT4BJWW7ji2zXIzIXMI4H12IbBwcqYKGKhcUJNRXf COgA== X-Gm-Message-State: ACrzQf3vaX5E7MKAAE73dZvaZDWf6uu53XvRtsAdijyb4x0x5dHZjoCi fgVCqilN7X9NKn2Wa/tFjyFEG8v7ooo= X-Google-Smtp-Source: AMsMyM5k4fs3z065OhROrdL2eM71Xhxl5imp1p/b5YYx5IcplGolgGVizVjUDu+UR77HasYI0kQ2Jg== X-Received: by 2002:a05:6402:2694:b0:450:d537:f6d6 with SMTP id w20-20020a056402269400b00450d537f6d6mr14543564edd.344.1664697962759; Sun, 02 Oct 2022 01:06:02 -0700 (PDT) Received: from Mini.fritz.box (p54b0c1f2.dip0.t-ipconnect.de. [84.176.193.242]) by smtp.gmail.com with ESMTPSA id w9-20020aa7da49000000b0045391f7d877sm4910545eds.53.2022.10.02.01.06.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 02 Oct 2022 01:06:02 -0700 (PDT) From: =?utf-8?Q?Gerd_M=C3=B6llmann?= To: Stefan Monnier Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: (Stefan Monnier's message of "Fri, 30 Sep 2022 14:29:59 -0400") References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> <83zgehe6iq.fsf@gnu.org> <13f3e7fa-4690-3ab0-f803-0812303f90f7@gmail.com> Date: Sun, 02 Oct 2022 10:06:01 +0200 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) Stefan Monnier writes: >> Info for Stefan: I've now removed the per-tree null node, and make check >> shows no unexpected results. > > Thanks. It's an improvement, but I still don't understand how it > works :-( Is it still null->parent? If so, maybe it helps to picture that null is a child of many parents :-). Every node having null on the left or right is a parent in that sense. Therefore, if some code uses null->parent to do something it can not be right. From debbugs-submit-bounces@debbugs.gnu.org Sun Oct 02 04:22:30 2022 Received: (at 58158) by debbugs.gnu.org; 2 Oct 2022 08:22:30 +0000 Received: from localhost ([127.0.0.1]:46205 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeuF4-0002SW-7w for submit@debbugs.gnu.org; Sun, 02 Oct 2022 04:22:30 -0400 Received: from mail-ed1-f54.google.com ([209.85.208.54]:34628) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeuF2-0002SJ-Jk for 58158@debbugs.gnu.org; Sun, 02 Oct 2022 04:22:29 -0400 Received: by mail-ed1-f54.google.com with SMTP id s30so7251730eds.1 for <58158@debbugs.gnu.org>; Sun, 02 Oct 2022 01:22:28 -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=Fdi+me/iuvYvsi48ukiZyXLNGoEZapStVWoVwzHfxiA=; b=J4W/+/r7GKgtJUVaywpfj28U+lqjwmdfqn2oQaQNMPZa/nCMAT7d54wkMhZM+H56TK L6Z7Q4B4deOXZ6zgqyhT0T2A1orKL/UBRF+YF677MHdLEVsRWIUdM+Y2LD1NsksCL2zT zDNMFcPfbLltUCi+j6nmBFWywY9dMXXzlwyza0fhHKdHUoQfGU6xsC+rX6hYskC/WOiX pU8p7q6Y0qlNvqcrOTfFbDDwHE2Mpgt6hYFZdyYffFUtqwuW/re/FghounGhty6nWieK zlYKf9XQeBqiFm+c35cQYvx8Kqn4M6j7ebMxsD/1+PzMcUQiKtwXsYNE/yP5g1au1pZX Rmyw== 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=Fdi+me/iuvYvsi48ukiZyXLNGoEZapStVWoVwzHfxiA=; b=1/E+cNYRsc9XztC0MbafxEZY6lM0DDaA6O0b5EWsHBHISgxJFXmKNMHHu3tbkDhtz4 VJdj1gEt8218aCeZ9/NNkEXv45eGBRYPW8n5y/Vshliagf/VK6x6WmO1Rwnwc1umIL2l ae9nOT6wrQG6KKct5VMHJ+b0Tu8VQo430O+WoGcuuolKtHEcfjP+soLgVIARpliH9BTU UTRwGpT/qSZDbPWRRG2hGCVXTdqbQ8MkyM4HJmtfxvZGM1YLfGPGg7UZ90y/WmzD/7A5 ccOpbw8Y1kGeLkI6UTL8lptjyDaTzg+SCBu2ejhGHpyEK9GGQejADRQgIiBCBBXB3dSO kUbw== X-Gm-Message-State: ACrzQf1vSpjnSi3514GJBjSDnKCrY16NMGMD1hFKm5IHtkixqOoIhVK/ aOK2s8HrKxsfU7dwTGXiAj0= X-Google-Smtp-Source: AMsMyM7jWY04tiwJpzip2zbOSbgQW/ns+rzhmakGdbjzIexh8EXsVNIQvi13hdYdh3CWeaIm67VbqQ== X-Received: by 2002:a05:6402:357:b0:458:5cb6:f587 with SMTP id r23-20020a056402035700b004585cb6f587mr11545322edw.183.1664698942702; Sun, 02 Oct 2022 01:22:22 -0700 (PDT) Received: from Mini.fritz.box (p54b0c1f2.dip0.t-ipconnect.de. [84.176.193.242]) by smtp.gmail.com with ESMTPSA id y8-20020a056402358800b0044dbecdcd29sm5012468edc.12.2022.10.02.01.22.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 02 Oct 2022 01:22:22 -0700 (PDT) From: =?utf-8?Q?Gerd_M=C3=B6llmann?= To: Stefan Monnier Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: (Stefan Monnier's message of "Sat, 01 Oct 2022 09:54:36 -0400") References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Date: Sun, 02 Oct 2022 10:22:21 +0200 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , Andreas Politz , 58158@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) Stefan Monnier writes: >> Phew. I'm not sure but I get the feeling that makes implementing a >> successor function, let's say, challenging. > > I don't think it makes any difference in that respect, no. The reason I find it challenging, and I'm sure now, is that I've written the following code, and failed :-). /* FIXME: This assumption is wrong. Nodes on the left of P are <=, and nodes on the right are >=. */ /* Value is the successor of interval node X in ascending order. It is assumed that the tree is organized so that nodes < X are in X->left and nodes in X->right are >= X. */ static struct interval_node * in_order_successor (struct interval_node *x) { if (x->right != ITREE_NULL) { /* X has a right child, which means X's right subtree has elements >= X. Proceed to the left-most child in the right subtree, which is the smallest in that subtree. */ x = x->right; while (x->left != 0) x = x->left; } else { /* X's left subtree is uninteresting, because everything there is < X. Therefore follow the parent chain. If X is the parent's right child, this means the parent is < X, We are looking for a parent that is >=. */ struct interval_node *y = x->parent; while (x == y->right) { x = y; y = y->parent; } /* If we found a parent that's >=, the parent is what we sought. Otherwise, X has arrived at the null node, whose right child is the sentinel node itself. */ if (x->right != y) x = y; } return x; } I tried to change the comments and/or modify the code for a tree like we have (left subtree <=, right >=), and couldn't explain why it works, but I also couldn't produce a counter-example that the existing tree code actually can produce. IOW, I couldn't prove anything. P.S. With the "all over the place" I indented to hint at the fact that the tree is not a "normal" BST. I should probably have said that directly, sorry. From debbugs-submit-bounces@debbugs.gnu.org Sun Oct 02 12:51:53 2022 Received: (at 58158) by debbugs.gnu.org; 2 Oct 2022 16:51:53 +0000 Received: from localhost ([127.0.0.1]:47907 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1of2C0-0007lU-O7 for submit@debbugs.gnu.org; Sun, 02 Oct 2022 12:51:53 -0400 Received: from mout.kundenserver.de ([217.72.192.75]:59777) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1of1tP-0007Gj-1U for 58158@debbugs.gnu.org; Sun, 02 Oct 2022 12:32:39 -0400 Received: from localhost ([77.180.185.96]) by mrelayeu.kundenserver.de (mreue106 [213.165.67.113]) with ESMTPSA (Nemesis) id 1MTAW9-1on1jK31lX-00UejG; Sun, 02 Oct 2022 18:32:25 +0200 From: Andreas Politz To: Gerd =?utf-8?Q?M=C3=B6llmann?= Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Date: Sun, 02 Oct 2022 18:32:19 +0200 In-Reply-To: ("Gerd =?utf-8?Q?M=C3=B6llman?= =?utf-8?Q?n=22's?= message of "Sun, 02 Oct 2022 10:22:21 +0200") Message-ID: <87zgeegp9o.fsf@andreas-politz.de> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.1 (gnu/linux) MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Provags-ID: V03:K1:mlafmVVJ5KEPMZSU7arhvU94X+ClbrYLm7vJ9kQvSmOn1LGWDVh KnS4LlkqSP4ltbxTP45Bp2Rb4LEb7dsMJSPMtOaOioulMhutKJYTKSPaL+s1ZuubhEZ7Y4h 9WHk6fFChot+yAZH+VpmFs+PM68kYim3Kyz+D9A/bjftN1fXLqjL6qMLRq3l+TRth5Fviph 2soR6glRCKAEWWNYLkTEg== X-Spam-Flag: NO X-UI-Out-Filterresults: notjunk:1;V03:K0:6o2ihyT/1cg=:mgtOyeDSARMsW7olWa/iuq tig9fpOgGjUS/koIYS8gsFSce5oFYEBYWL3wrs6fBW0FTfiufCpB/zMUY8o0n//UP0O5uap5N RpVyvjb+r3KDDz4tE26pxjhzp09seiICgvR4uVtEDbcnBvFj7pBKIbGEc+q1DYDWXsU5eqxp6 Y2hIdJx4q3KUi+ofEWJkS0RwpvYU3AqqksFt9VPBLDO8ezXarCzCbVaYWhCdrsm+wSBEdeOHH EvSnoFJAfPIIiSfA3ffEAIHD6f0p8sVFjsISckxq0jRSGmi4gBJ3P+7MkUJrOCDTNp8fSQg5R bp3wDFTx3H4TzH3daq8bP+SYezz3ChDj9nLHN5d06ULf20sZaxENNWBS0WkaQyP7TnqXriytF JDUaviax3kVWi0mRV6BHYtrAquFIhx46UA6DajIyW2npkSEZRHtZDncz/AMGaeAt4bVdOmi89 B2Xmr0LtWuUhIq0pT69gO80SnGWoMmUDhIXpFk3yMTWK3o/1vGFyhYZKcNmo1MT9FhYamNy60 HyzzMYWfT++2HyjrNuuKKwhsrn5/SJlnJx7PTWyLDwkngUtDkwPbOvZIG675GZXABOwhKUvin fts9QFfsPWwY7ZLbLvcUG2XUsH+tuTHT9W/fmGKV4mi6IOfqsvsJYlYViPFpK/KnMN0nTKzMI SsxhADxKwKXJj4qhZgxLFnYACTZ7bShQ3K1OxyTOtS+6ZGkN87fXMvYbE22sQuKM0mJN9XmNB mc/ilEhNeKrctEUklml/mCzMtu8ES6sumz8l4lzhYPn/7pJ0pkAyAHcIeJz+l0IS+hQ3ceiNO W/grfj12xAUfQK36XnYAedDg0L0rw== X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 58158 X-Mailman-Approved-At: Sun, 02 Oct 2022 12:51:51 -0400 Cc: Eli Zaretskii , 58158@debbugs.gnu.org, Stefan Monnier X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) --=-=-= Content-Type: text/plain I've managed to construct a prototype of this "stateless" iterator. I've only implemented the in-order case and only applied it in the overlays_in function. The only real trouble I had was with pushing the offset to the children during the tree navigation in some kind of sensible way. In the end I gave up and simply pasted calls to the corresponding function "all over the place". It seems to work, at least buffer-tests are passing. Andreas --=-=-= Content-Type: text/x-patch Content-Disposition: inline; filename=noverlay-stateless-iterator.diff diff --git a/src/buffer.c b/src/buffer.c index f59fddcbde..6a53b49aad 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -2948,15 +2948,16 @@ overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend, ptrdiff_t next = ZV; Lisp_Object *vec = *vec_ptr; struct interval_node *node; + struct interval_tree_iterator iterator; - ITREE_FOREACH (node, current_buffer->overlays, beg, - /* Find empty OV at Z ? */ - (end >= ZV && empty) ? ZV + 1 : ZV, ASCENDING) + interval_tree_iterator_init(&iterator, current_buffer->overlays, beg, + (end >= ZV && empty) ? ZV + 1 : ZV, ITREE_ASCENDING); + + while ((node = interval_tree_iterator_next(&iterator))) { if (node->begin > end) { next = min (next, node->begin); - ITREE_FOREACH_ABORT (); break; } else if (node->begin == end) @@ -2964,7 +2965,6 @@ overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend, next = node->begin; if ((! empty || end < ZV) && beg < end) { - ITREE_FOREACH_ABORT (); break; } } diff --git a/src/itree.c b/src/itree.c index eeecaf1839..21549fe8a7 100644 --- a/src/itree.c +++ b/src/itree.c @@ -1190,3 +1190,132 @@ interval_tree_subtree_min (const struct interval_tree *tree, struct interval_nod * +===================================================================================+ */ /* See Foverlay_tree in buffer.c */ + + +/* +===================================================================================+ + * | Stateless iterator + * +===================================================================================+ */ + +static bool +interval_tree_iter_traverse_p(struct interval_tree_iterator *iterator, + struct interval_node *node); +static +struct interval_node * +interval_tree_iterator_in_order_successor (struct interval_tree_iterator* iterator); + +void +interval_tree_iterator_init(struct interval_tree_iterator *iterator, + struct interval_tree *tree, + ptrdiff_t begin, + ptrdiff_t end, + enum interval_tree_order order) { + iterator->tree = tree; + iterator->node = tree && begin <= end ? ITREE_NULL : NULL; + iterator->begin = begin; + iterator->end = end; + iterator->order = order; +} + +struct interval_node * +interval_tree_iterator_next(struct interval_tree_iterator *iterator) { + if (iterator->node) { + do { + switch (iterator->order) { + case ITREE_ASCENDING: + iterator->node = interval_tree_iterator_in_order_successor (iterator); + break; + default: + fprintf (stderr, "interval_tree_order != ITREE_ASCENDING not implemented"); + emacs_abort (); + } + } while (iterator->node && + ! interval_node_intersects (iterator->node, iterator->begin, iterator->end)); + } + + if (iterator->node == ITREE_NULL) { + fprintf (stderr, "Next node: ITREE_NULL\n"); + } else if (! iterator->node) { + fprintf (stderr, "Next node: NULL\n"); + } else { + fprintf (stderr, "Next node: begin = %ld, end = %ld (iterator: begin = %ld, end = %ld)\n", + iterator->node->begin, iterator->node->end, iterator->begin, iterator->end); + } + return iterator->node; +} + +static bool +interval_tree_iter_traverse_p(struct interval_tree_iterator *iterator, + struct interval_node *node) { + eassert (node); + + if (node == ITREE_NULL) { + return false; + } else { + eassert (node->parent != ITREE_NULL); + if (node->parent->left == node) { + return iterator->begin <= node->limit + node->offset; + } else { + return node->parent->begin <= iterator->end; + } + } +} + +static +struct interval_node * +interval_tree_iterator_in_order_successor (struct interval_tree_iterator* iterator) +{ + struct interval_node *node = iterator->node; + + if (node != ITREE_NULL) { + interval_tree_inherit_offset (iterator->tree, node); + } + + if (node == ITREE_NULL) { + node = iterator->tree->root; + if (node != ITREE_NULL) { + interval_tree_inherit_offset (iterator->tree, node); + } + while (interval_tree_iter_traverse_p(iterator, node->left)) { + node = node->left; + if (node != ITREE_NULL) { + interval_tree_inherit_offset (iterator->tree, node); + } + } + } else if (interval_tree_iter_traverse_p(iterator, node->right)) + { + node = node->right; + if (node != ITREE_NULL) { + interval_tree_inherit_offset (iterator->tree, node); + } + while (interval_tree_iter_traverse_p(iterator, node->left)) { + node = node->left; + if (node != ITREE_NULL) { + interval_tree_inherit_offset (iterator->tree, node); + } + } + } + else + { + struct interval_node *parent = node->parent; + while (node == parent->right) + { + node = parent; + parent = parent->parent; + } + if (node != ITREE_NULL) + node = parent; + } + + return node == ITREE_NULL ? NULL : node; +} + +void +interval_tree_iterator_narrow (struct interval_tree_iterator *iterator, + ptrdiff_t begin, + ptrdiff_t end) +{ + eassert (begin >= iterator->begin); + eassert (end <= iterator->end); + iterator->begin = max (begin, iterator->begin); + iterator->end = min (end, iterator->end); +} diff --git a/src/itree.h b/src/itree.h index 1f019a2607..53f03cca35 100644 --- a/src/itree.h +++ b/src/itree.h @@ -72,6 +72,15 @@ #define ITREE_NULL (&itree_null) ITREE_PRE_ORDER, }; +struct interval_tree_iterator +{ + struct interval_tree *tree; + struct interval_node *node; + ptrdiff_t begin; + ptrdiff_t end; + enum interval_tree_order order; +}; + void interval_node_init (struct interval_node *, ptrdiff_t, ptrdiff_t, bool, bool, Lisp_Object); ptrdiff_t interval_node_begin (struct interval_tree *, struct interval_node *); ptrdiff_t interval_node_end (struct interval_tree *, struct interval_node *); @@ -135,4 +144,15 @@ #define ITREE_FOREACH_ABORT() \ #define ITREE_FOREACH_NARROW(beg, end) \ interval_generator_narrow (itree_iter_, beg, end) +void interval_tree_nodes (struct interval_tree *tree, struct interval_node **nodes, enum interval_tree_order order); + +void interval_tree_iterator_init(struct interval_tree_iterator *iterator, + struct interval_tree *tree, + ptrdiff_t begin, + ptrdiff_t end, + enum interval_tree_order order); +struct interval_node *interval_tree_iterator_next(struct interval_tree_iterator *iterator); +void interval_tree_iterator_narrow (struct interval_tree_iterator *iterator, + ptrdiff_t begin, + ptrdiff_t end); #endif --=-=-=-- From debbugs-submit-bounces@debbugs.gnu.org Mon Oct 03 00:35:12 2022 Received: (at 58158) by debbugs.gnu.org; 3 Oct 2022 04:35:12 +0000 Received: from localhost ([127.0.0.1]:48589 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ofDAd-0003S1-OQ for submit@debbugs.gnu.org; Mon, 03 Oct 2022 00:35:11 -0400 Received: from mail-ed1-f48.google.com ([209.85.208.48]:43581) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ofDAc-0003Rm-Dl for 58158@debbugs.gnu.org; Mon, 03 Oct 2022 00:35:10 -0400 Received: by mail-ed1-f48.google.com with SMTP id y8so12925533edc.10 for <58158@debbugs.gnu.org>; Sun, 02 Oct 2022 21:35:10 -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=JcPFZ4bEriEgceTerjz4XOfDUMTk63KPw92fnWH5xVU=; b=O66zajKDqPLxVKlMrhenUmrd1JLo0WGXhProbRdGSDpMeeDfn+l5+dZ/H1eSve1xlF QfyM1cJ30a1Ch5474WwMhOSuIWtZrXleX1pGZ/oAelLXeq1IUqWjgikaWo4Dl1xHVTqT 5d9HGWXCuT0+IoGJXFtwf/PfQHB/0R3Nmh4JNADtvGLF9ciUyKLtDEabozai8TLis3GE ICVp/qqJ4OWfZBQLHMRf4ZHRhY7TskERRa1pKZse7vgjaZRogu4oeqnNQZ8f024Mfrup 3LoavWzkEddgbkSYS58exErdMw8LMjUkf55i6Nae94OQg5KNrOauUuSZFX+WUcNj2ceg /Ekg== 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=JcPFZ4bEriEgceTerjz4XOfDUMTk63KPw92fnWH5xVU=; b=TV9yf9Kd9nKcumU1GjZoWw46WYuGWUOsMTe4IEMFSkEZwjniaFUGCIDDu5fjDr+EgB kLg+IVbjzVcuHHqOKVBQ0pmjIehqCabG0wTpwKJywJlcz6U1bWijLbtYqnSzWvMMGRcN 7+DZIOw54IKEN/KHP210quG55OWsDE7ca05y4LYxzCApexRME0spFLTeiifAHOtHmg6R BCm4NynVAH21jti3aEeQgCx964GA2CGt4HAlRno8XmrQ1NCqyyUEbdLyUngCSz4kTye/ RZNYiw4BT+BbYuuDyTdPCBUZ/u2iJqF4NHtDLhMQlT09XGmpml9vshA8KN0NDFBoQkXZ BzcQ== X-Gm-Message-State: ACrzQf3Wqswy06Z+8kI9DMlIyTt0sVibNFb14gfuX4QCdSt5fJlnKeBy aUSeVtpQp4xjpOFEASdfXioAhz0cp9g= X-Google-Smtp-Source: AMsMyM4J4LJCnqLGSXLda0DSOFb0nx6cG9rJduJzW0MuVIUoHgzHexy19QOeuvbqaYo76+E48f68Hg== X-Received: by 2002:a05:6402:28a1:b0:458:81c0:a379 with SMTP id eg33-20020a05640228a100b0045881c0a379mr11940939edb.388.1664771703062; Sun, 02 Oct 2022 21:35:03 -0700 (PDT) Received: from Mini.fritz.box (pd9e36c30.dip0.t-ipconnect.de. [217.227.108.48]) by smtp.gmail.com with ESMTPSA id d22-20020a056402001600b00458e73fe1c1sm2370026edu.8.2022.10.02.21.35.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 02 Oct 2022 21:35:01 -0700 (PDT) From: =?utf-8?Q?Gerd_M=C3=B6llmann?= To: Andreas Politz Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: <87zgeegp9o.fsf@andreas-politz.de> (Andreas Politz's message of "Sun, 02 Oct 2022 18:32:19 +0200") References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> <87zgeegp9o.fsf@andreas-politz.de> Date: Mon, 03 Oct 2022 06:35:00 +0200 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , 58158@debbugs.gnu.org, Stefan Monnier X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) Andreas Politz writes: > It seems to work, at least buffer-tests are passing. "seems to work" is a bit weak. Can we prove it? I don't mean mathematically, but by reasoning like I tried in the comments in successor function I posted, From debbugs-submit-bounces@debbugs.gnu.org Tue Oct 04 07:05:18 2022 Received: (at 58158) by debbugs.gnu.org; 4 Oct 2022 11:05:18 +0000 Received: from localhost ([127.0.0.1]:52648 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1offjh-0004Ke-RY for submit@debbugs.gnu.org; Tue, 04 Oct 2022 07:05:18 -0400 Received: from mout.kundenserver.de ([212.227.17.13]:44571) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1offW0-0001lJ-Vm for 58158@debbugs.gnu.org; Tue, 04 Oct 2022 06:51:09 -0400 Received: from smtpclient.apple ([77.179.162.75]) by mrelayeu.kundenserver.de (mreue109 [213.165.67.113]) with ESMTPSA (Nemesis) id 1MzQc2-1pSFt41yeu-00vOmH; Tue, 04 Oct 2022 12:50:58 +0200 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable From: Andreas Politz Mime-Version: 1.0 (1.0) Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Date: Tue, 4 Oct 2022 12:50:54 +0200 Message-Id: <7B9B9541-E1D3-4553-BE8D-5197D3CB1018@andreas-politz.de> References: In-Reply-To: To: =?utf-8?Q?Gerd_M=C3=B6llmann?= X-Mailer: iPad Mail (19G82) X-Provags-ID: V03:K1:mWBVn8vHSxVVkx34Zk3YgZZW86yWkxc5Fa5QedFuBphb0F4M4jP LvUTY/i5gwIX2NUIFD8QyRJXyvW/WB2jvhgW3Y1na8xe8hU5rcpqPPQ3N8Q1VGKEoJXIBpg ufT8NJ9ga5K6s4q9k/BcwEqHVuvPgZswVSj8PFnEFVovovnHrUGrvNHHftaNql3SOj2Pk06 3avMgSiQ5mWU8sEeoFY9A== X-Spam-Flag: NO X-UI-Out-Filterresults: notjunk:1;V03:K0:U9FHf1GoFhY=:C5izIiVVlNFN8TB2xJdGNr pY7P6rIlLGcHBbm7A1f297MuJ3zzggShBkpb67mJNbXiybiRyozfF60hvhX9MFWqI5RI6W4Wb zApl3TCV3f03YaAhlFDATkKgj4fqVEkI7bI4trKpnpZI9Ev5DOua3Y3OcrRsiSwWs3p24hqkm X3QVgPLexvqt0oo3BX+iu+ICs3iatWfBE5ktgdH7DjZ5a+CNYBRhgjjvNJrd8lgUL0IqG1NUn PFQuZ2J4TyO8V7xQDeIykO8NnrEDyRq73M7aoxR+0OZXg5+e4kwUzpWFUq10BYVYLdQNohzHD tZ2SrM1/8ih7V2oeVQjwiGqHhZMHYZ+gqzEBlaUMH9T4+iMOYc3w9ckM/eSIs3g7cla6DYTZS vJ7uxlnsxrLXNu8VJRhtAlOFslQ8/HtB3zOnn1TmT4VrgtkTHTftfzTt+22qJfq9RQau0Jrz6 TtCpBDJF0GKBKPDQnOSPcmTTcHz5DaCTT/+4aV+5iP+erlZMjqx3IM4ZWTCc4V45HHJUGcQJN 04wETxi+0HW4UtPfLmBevfwEFjxV5FB4dP0v0ExecyZnY1ixwZNLSFUl7UqyPA2VtYMvigN9j iJHRIPS8P5VEpSZgrAohnZZ8GTkIcRVUq46OxzI7oejSkkVr07SpWCMk20uh5I45Z2wMJCcGN stKPns+VA0oJWbN/Avnjga5l6RmzcnY5ogjmCTjZyqHH3R63eGV6ek+lC+H8rgujv/QsrJbEr b4m0fVpaTmDukwjZdxkdFpNaivMFik93126JOFYvNZ6OHcl/RRvIiFX6FsIsF19OXkdzux+wj +aklgVAIzF7PJZDk066gVKifXbeMg== X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 58158 X-Mailman-Approved-At: Tue, 04 Oct 2022 07:05:12 -0400 Cc: Eli Zaretskii , 58158@debbugs.gnu.org, Stefan Monnier X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) My implementation seems to work. The correctness of the algorithm would foll= ow from=20 1. The Rb tree algorithm produces a tree with left <=3D root <=3D right, 2. the algorithm you=E2=80=99ve posted, and I=E2=80=99ve adapted, produces a= n in=E2=80=93order of the tree and 3. the conditions guiding the traversal are correct, i.e. they don=E2=80=99t= exclude matching intervals. Since I believe these statements are true, I believe the algorithm is correc= t. Andreas > Am 03.10.2022 um 06:35 schrieb Gerd M=C3=B6llmann : >=20 > =EF=BB=BFAndreas Politz writes: >=20 >> It seems to work, at least buffer-tests are passing. >=20 > "seems to work" is a bit weak. Can we prove it? >=20 > I don't mean mathematically, but by reasoning like I tried in the > comments in successor function I posted, From debbugs-submit-bounces@debbugs.gnu.org Thu Oct 06 18:26:53 2022 Received: (at 58158) by debbugs.gnu.org; 6 Oct 2022 22:26:53 +0000 Received: from localhost ([127.0.0.1]:33769 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogZKO-0007X5-O7 for submit@debbugs.gnu.org; Thu, 06 Oct 2022 18:26:53 -0400 Received: from relay2-d.mail.gandi.net ([217.70.183.194]:37717) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogZKJ-0007Wo-Oq for 58158@debbugs.gnu.org; Thu, 06 Oct 2022 18:26:51 -0400 Received: (Authenticated sender: matt@rfc20.org) by mail.gandi.net (Postfix) with ESMTPSA id 5D92940006; Thu, 6 Oct 2022 22:26:40 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1665095201; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type; bh=7zAQQXk4w70sHM9M0EujZoyJa/jVCsy6nPZozma+mrQ=; b=cEHkPu7Qqn7buYfIxBz9DZwb67YwwFLVVPWd7L5gtmNFc/eurM0LW2L5/pFlbkS7UTgjMA 9vmxG2khtl6OGaG9523id17YFf9NJjKiBCGHlIhqgPxXQ6glj0BtagPW8WMnEMdhTjWmE7 7oSnL/Upg2qlJK+kDzWOZ+D36bjtIpgD7Oq2Kn97YhUbaUtl857ZIvBvKblx2TR51cHSae PcsBk6SwsWKmItwWSgTr+xm1X09dXzgtSLOknvlJjmFZ+duCvjKik8sGPLP0QvYg4ZuLQX EGxLrR8sm17EoHzHsKrT3ucnrL8ewOWUvqOyqloCGw9IUi/eeKITkoiw6ep7yg== Received: from matt by naz with local (Exim 4.96) (envelope-from ) id 1ogZK9-00438r-24; Thu, 06 Oct 2022 15:26:37 -0700 From: Matt Armstrong To: Andreas Politz , Gerd =?utf-8?Q?M=C3=B6llmann?= Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Date: Thu, 06 Oct 2022 15:26:37 -0700 Message-ID: <87h70gd1wi.fsf@rfc20.org> MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 58158 Cc: Eli Zaretskii , 58158@debbugs.gnu.org, Stefan Monnier X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.7 (-) Andreas Politz writes: > I've managed to construct a prototype of this "stateless" iterator. > > I've only implemented the in-order case and only applied it in the overlays_in function. > > The only real trouble I had was with pushing the offset to the children > during the tree navigation in some kind of sensible way. In the end I > gave up and simply pasted calls to the corresponding function "all over > the place". It seems to work, at least buffer-tests are passing. Hey Andreas, this looks pretty good to me but I have some questions on it. > +static > +struct interval_node * > +interval_tree_iterator_in_order_successor (struct interval_tree_iterator* iterator) > +{ > + struct interval_node *node = iterator->node; > + > + if (node != ITREE_NULL) { > + interval_tree_inherit_offset (iterator->tree, node); > + } > + if (node == ITREE_NULL) { > + node = iterator->tree->root; I don't understand this branch. If the node is NULL upon entry to the successor call, why start at the root? Why is the "next in order node" of NULL the root? The root is just an node whose BEG is roughly in the middle of the total inorder traversal, right? The "stateless" inorder traversal algorithm I am used to starts with the minimum node (walk only left links down from the root until at a leaf and that is the minimum). Then do inorder traversal from there. > + if (node != ITREE_NULL) { > + interval_tree_inherit_offset (iterator->tree, node); > + } > + while (interval_tree_iter_traverse_p(iterator, node->left)) { > + node = node->left; > + interval_tree_inherit_offset (iterator->tree, node); > + } > + } else if (interval_tree_iter_traverse_p(iterator, node->right)) > + { > + node = node->right; > + interval_tree_inherit_offset (iterator->tree, node); > + while (interval_tree_iter_traverse_p(iterator, node->left)) { > + node = node->left; > + interval_tree_inherit_offset (iterator->tree, node); > + } > + } > + else > + { > + struct interval_node *parent = node->parent; > + while (node == parent->right) > + { > + node = parent; > + parent = parent->parent; > + } > + if (node != ITREE_NULL) > + node = parent; > + } > + > + return node == ITREE_NULL ? NULL : node; > +} I don't understand how the last "else" case works correctly in the face of a call to `interval_generator_narrow` during iteration. Narrowing could render a node's parent out of the "interesting" range, and so the iterator should not return it but instead keep trying to find a successor in range. Right? From debbugs-submit-bounces@debbugs.gnu.org Thu Oct 06 18:36:29 2022 Received: (at 58158) by debbugs.gnu.org; 6 Oct 2022 22:36:29 +0000 Received: from localhost ([127.0.0.1]:33774 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogZTg-0007mO-S5 for submit@debbugs.gnu.org; Thu, 06 Oct 2022 18:36:29 -0400 Received: from mail-wr1-f53.google.com ([209.85.221.53]:47012) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogZTd-0007m9-JD for 58158@debbugs.gnu.org; Thu, 06 Oct 2022 18:36:27 -0400 Received: by mail-wr1-f53.google.com with SMTP id bk15so4700113wrb.13 for <58158@debbugs.gnu.org>; Thu, 06 Oct 2022 15:36:25 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :sender:from:to:cc:subject:date; bh=ngDD66N4776oPBxefUzi7YYFBgC5N+tGVz9YaZNWZHQ=; b=VsLcg4N5c7Cx9JIerBFWblleLAgPmtJ0cMlnaWBLwszIMZRA6fYVxun3s2j2rzAgge acs55CQSwiW2wJ0N4qcTQNSRhjhILcY0tDvvWUfVCa5RzYQgvnoXWkPNJm9HlzKNbFpR DkGp3wOYwxVxxYxn2DCy3IGLMPnUsOcPbrWyk5VL1RQBZZbw7JQYTfGN5D1uWXkb80sd DLhd/5rz3z6oCM5ciLaoAIfHoF0WR8e0b9wvjuxucFr7200AUQVIrXP1bWd1oPKxSTjT y6WnoYBz1I2l/PlFsrdTqvwk/nLNIUlbaeQztjIgmvSffoCzJlvaBPJ6ev0S4nOXhVBF ZnvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :sender:x-gm-message-state:from:to:cc:subject:date; bh=ngDD66N4776oPBxefUzi7YYFBgC5N+tGVz9YaZNWZHQ=; b=8Mnved1s8uTMPGGPzoD38eVtAoqwQPVmZV8+piCx6a1ukOREbvNShBs82inJoqsg2n mrEdoeCPr65nDZCRpXVXqlGTZBFMmclm6C1rz/82rUcjo3sb9YxW0b6/vicTmG5z2/IW utXiyhDsTtHBVQ5oU3dAI0Rx49oLAP+qgkDf3TohQSuiK3N2oG+om9B+VsKGdmn9OC4O I3aGENdurrDCcA4c7dSNERTnNykSJN0049M2mfePFMbnSydJSxiHy/XRoXlnJaLwn6nk lGIwcQJ3GElq1e+bhhJQs8hBk8EuwNuUXl1NUTEAJAw38U2JCXuBgoHGC3jFnKo8kcQe xpCw== X-Gm-Message-State: ACrzQf1/c4q1Q+NcLwgS7E4HWOaboY/Ryj9a1RoZGRRFWMjZWM+8Yemm RVMw7bovYIWFMj9F2PPgN8A= X-Google-Smtp-Source: AMsMyM4Znx7umVVLgFLtr2wO0FjdBH87vHZ05adBCohyKV4jY4Vu/5BzpSImIiAZPEmpytRk403bXg== X-Received: by 2002:a05:6000:15c3:b0:22e:60d2:6ec6 with SMTP id y3-20020a05600015c300b0022e60d26ec6mr1371752wry.296.1665095779673; Thu, 06 Oct 2022 15:36:19 -0700 (PDT) Received: from [192.168.0.6] ([46.251.119.176]) by smtp.googlemail.com with ESMTPSA id s16-20020adfdb10000000b0022ae8b862a7sm469504wri.35.2022.10.06.15.36.18 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 06 Oct 2022 15:36:19 -0700 (PDT) Message-ID: <95113379-99d8-eba4-f980-a7fca11430d5@yandex.ru> Date: Fri, 7 Oct 2022 01:36:17 +0300 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.2.2 Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Content-Language: en-US To: Eli Zaretskii , =?UTF-8?Q?Gerd_M=c3=b6llmann?= References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> <83zgehe6iq.fsf@gnu.org> From: Dmitry Gutov In-Reply-To: <83zgehe6iq.fsf@gnu.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -1.3 (-) X-Debbugs-Envelope-To: 58158 Cc: 58158@debbugs.gnu.org, monnier@iro.umontreal.ca X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) On 30.09.2022 09:11, Eli Zaretskii wrote: > "M-x xref-query-replace-in-results RET" JFYI this command has the convenient binding 'r' in Xref output buffers. From debbugs-submit-bounces@debbugs.gnu.org Fri Oct 07 15:47:37 2022 Received: (at 58158) by debbugs.gnu.org; 7 Oct 2022 19:47:37 +0000 Received: from localhost ([127.0.0.1]:37450 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogtJp-0006Hi-Eu for submit@debbugs.gnu.org; Fri, 07 Oct 2022 15:47:37 -0400 Received: from eggs.gnu.org ([209.51.188.92]:49586) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogtJn-0006HW-LR for 58158@debbugs.gnu.org; Fri, 07 Oct 2022 15:47:36 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:44886) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogtJh-0002gO-Fr; Fri, 07 Oct 2022 15:47:29 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=References:Subject:In-Reply-To:To:From:Date: mime-version; bh=wBHkUBA2oUBLzOiZbqgkORUmuqN2UtmymJZ0HIMtY2w=; b=BsK1dNkVPW/q RqV9/jUEUWvMkgtrigHF7Dvz++dSW9ScBqPgcezxQrZunQyIsqE+v7JqYboIeXyrhEHbeTbzXp/jC dko2GVDyzBT8UrFyKJD+xGVzMiaQoN7D7h0vIF27woAaoGfbFuA9aLjshOfmMzz1F8veMwp5M1aTJ /xHDVv0KLSNRQb4fYJqVpOIM+PTQzH7IRj61JrDgbEm4zUzjR2Eofg4riJkEqa6L3TR66h7aQpx9r p2ouHOptx1jg51K8QSEwn90HNIxxKUWh4bSweoh8DVMaPO6YucsKjOhgJ1foeQaQGt+Xgo0V//PLG Gdh+njd28qMmK0mAjwd7Dg==; Received: from [87.69.77.57] (port=4647 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogtJg-0001jT-V0; Fri, 07 Oct 2022 15:47:29 -0400 Date: Fri, 07 Oct 2022 22:47:29 +0300 Message-Id: <834jwfmn5a.fsf@gnu.org> From: Eli Zaretskii To: Dmitry Gutov In-Reply-To: <95113379-99d8-eba4-f980-a7fca11430d5@yandex.ru> (message from Dmitry Gutov on Fri, 7 Oct 2022 01:36:17 +0300) Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> <83zgehe6iq.fsf@gnu.org> <95113379-99d8-eba4-f980-a7fca11430d5@yandex.ru> X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: gerd.moellmann@gmail.com, 58158@debbugs.gnu.org, monnier@iro.umontreal.ca X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > Date: Fri, 7 Oct 2022 01:36:17 +0300 > Cc: 58158@debbugs.gnu.org, monnier@iro.umontreal.ca > From: Dmitry Gutov > > On 30.09.2022 09:11, Eli Zaretskii wrote: > > "M-x xref-query-replace-in-results RET" > > JFYI this command has the convenient binding 'r' in Xref output buffers. It also works only when invoked from the Xref buffer, right? Btw, what am I doing wrong below? emacs -Q C-x C-f src/character.h RET M-x visit-tags-table RET RET M-. char_string RET r whatever RET Unexpected result: "No suitable matches here". Huh? what did I miss? From debbugs-submit-bounces@debbugs.gnu.org Sat Oct 08 14:50:51 2022 Received: (at 58158) by debbugs.gnu.org; 8 Oct 2022 18:50:52 +0000 Received: from localhost ([127.0.0.1]:41450 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ohEuR-0005Y7-JB for submit@debbugs.gnu.org; Sat, 08 Oct 2022 14:50:51 -0400 Received: from mail-wm1-f52.google.com ([209.85.128.52]:43645) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ohEuN-0005Xs-Nf for 58158@debbugs.gnu.org; Sat, 08 Oct 2022 14:50:50 -0400 Received: by mail-wm1-f52.google.com with SMTP id r3-20020a05600c35c300b003b4b5f6c6bdso4234566wmq.2 for <58158@debbugs.gnu.org>; Sat, 08 Oct 2022 11:50:47 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :sender:from:to:cc:subject:date:message-id:reply-to; bh=l8FXWyVSthpuYnVASERuOe43IyekO3Fz3D6bmwJbmdA=; b=J7tKEvQyF9ZU/5zdscye1TFxxafGy+Xak56D/xJH2wWAMEUAV551fGmyFrnhEaJ12o wOPPx9eraoD+iLFVV81MD4xHe8nUZZ8fhNopD8VP9ttuWuI0Xlz78BOzMWAoUlkqmJse VFPtomOCvodes/rqK4ZM0uDUctoaS/KaIsQRpQIq+mQGU1JuZStfMsGxhg0V4ro1+rkb Tsg9i+PKt7e8jbT0MgfAX6vYjKWYsvLibscoErnqyBek3+h5HctMjheL1lRCB6fLxIET Vx+EjuzFE53C2C5228+9tenYHlNfKipnDjh0uLzjXkrjRwHAM91CrkXolLLas4S+MOBX SpTA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :sender:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=l8FXWyVSthpuYnVASERuOe43IyekO3Fz3D6bmwJbmdA=; b=e1NotDp7FZD+kcE1ykmkKKuJFQ5zfwIpGQqzobRDzxxtIaiGh5zmqrR4J+89MrcGkc OGnibu84z43mLrqJBt8Ja7EgEalxOwk769va5bKDMY5lX8NFZ9gMcJsybB4Uv4JKDtbq ucq3InDsLO/Mk/PVdWoBofRwizGJJcSoJ2hhn6E2kMoFYKDRo5CqqW7TGB9tm7d2Wwc7 fNDpf15P/ZdsSGsWM/1nOZcVQN92/SWp22SzsD7yL1LHQZkwo2N0h5hI8ENH0D5t9YRj oi92sMtDCnFfO+BuMlj3xwE2qyTDSa85XpwYkP68+UW0SBn2G8C6PHB3dFKWv4adX8Um E4cg== X-Gm-Message-State: ACrzQf07Hz5rv+hRgQ+G+bORDR63sDTzzbUg8lPN7mWAWPMBg/dQmeji lymSTeXEGdfzI5kuuiD/SM8= X-Google-Smtp-Source: AMsMyM7DtIWFyl8cRhmmAgh2ciu/UoV6l8SNZE8+7PtbxD9hU9TXY32epBbNrE5Z0lh4XdFtl2RWSg== X-Received: by 2002:a1c:7412:0:b0:3b4:7a81:e7e4 with SMTP id p18-20020a1c7412000000b003b47a81e7e4mr6828868wmc.15.1665255041782; Sat, 08 Oct 2022 11:50:41 -0700 (PDT) Received: from [192.168.0.6] ([46.251.119.176]) by smtp.googlemail.com with ESMTPSA id h7-20020a05600c350700b003b4868eb71bsm11802523wmq.25.2022.10.08.11.50.40 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sat, 08 Oct 2022 11:50:41 -0700 (PDT) Message-ID: Date: Sat, 8 Oct 2022 21:50:39 +0300 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.2.2 Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Content-Language: en-US To: Eli Zaretskii References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> <83zgehe6iq.fsf@gnu.org> <95113379-99d8-eba4-f980-a7fca11430d5@yandex.ru> <834jwfmn5a.fsf@gnu.org> From: Dmitry Gutov In-Reply-To: <834jwfmn5a.fsf@gnu.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -1.3 (-) X-Debbugs-Envelope-To: 58158 Cc: gerd.moellmann@gmail.com, 58158@debbugs.gnu.org, monnier@iro.umontreal.ca X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) On 07.10.2022 22:47, Eli Zaretskii wrote: >> Date: Fri, 7 Oct 2022 01:36:17 +0300 >> Cc: 58158@debbugs.gnu.org, monnier@iro.umontreal.ca >> From: Dmitry Gutov >> >> On 30.09.2022 09:11, Eli Zaretskii wrote: >>> "M-x xref-query-replace-in-results RET" >> >> JFYI this command has the convenient binding 'r' in Xref output buffers. > > It also works only when invoked from the Xref buffer, right? Yep. But we also have commands like xref-find-references-and-replace and dired-do-find-regexp-and-replace. > Btw, what am I doing wrong below? > > emacs -Q > C-x C-f src/character.h RET > M-x visit-tags-table RET RET > M-. char_string RET > r whatever RET > > Unexpected result: "No suitable matches here". Huh? what did I miss? We can't replace over "find definition" matches: they are more abstract and don't contain the necessary information to perform the replacement (such as the length of a match, for instance). And such xrefs might navigate you to the beginning of the line, for example, rather than to the beginning of the name. But that makes sense, doesn't it? If replacing over "find definitions" results worked fine, in the end you would get a codebase where all declarations of a method 'foo' got renamed, but all callsites of it remain unchanged. That couldn't have been your intention, could it? The error message could use some improvement, I suppose, but I'm not sure how to make it better. From debbugs-submit-bounces@debbugs.gnu.org Mon Oct 10 04:10:48 2022 Received: (at 58158) by debbugs.gnu.org; 10 Oct 2022 08:10:48 +0000 Received: from localhost ([127.0.0.1]:45845 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ohns7-0006Ho-NI for submit@debbugs.gnu.org; Mon, 10 Oct 2022 04:10:48 -0400 Received: from eggs.gnu.org ([209.51.188.92]:49564) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ohns5-0006Hb-LY for 58158@debbugs.gnu.org; Mon, 10 Oct 2022 04:10:46 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:33294) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ohnrx-0007jx-J2; Mon, 10 Oct 2022 04:10:37 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=References:Subject:In-Reply-To:To:From:Date: mime-version; bh=MdkRl8nZtBK3Ijq6cPAt49+l4TA5hcZnxzS+WLmhGOc=; b=E/DcS3ikuHf1 b081R4fARGVQvXwpThqKOx22TtsBhFmYwcYvy4Cidp7Te8EbKO7P+DGfnATg8DVF2QjFePJdUaGx8 HWcMcLoK0ncOAWFuWuDTkXC4U6j2ot44qopwDc9u31UmtQ3pPs1xf8xz/u79THDuZohIQSghh13m0 NmMhTWbA1N6jsZ7emnrMAEMT9+sMYsl8dCQoIJlfcGxlE/bURUYCTDmjsUSbq5Oj4+vV3AiUQfyPc nFxShbu/Na5Cb4JcvGuYrxRi4ymUOuKbwkZiyVdkwcT+eeP4vTYCLPKjPjNNXZlw8nNmwHCQsI9j3 t1iSDIFcVv/tD4pOVSxh3Q==; Received: from [87.69.77.57] (port=1366 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ohnrt-0002Ic-BE; Mon, 10 Oct 2022 04:10:36 -0400 Date: Mon, 10 Oct 2022 11:10:39 +0300 Message-Id: <838rlohzeo.fsf@gnu.org> From: Eli Zaretskii To: Dmitry Gutov In-Reply-To: (message from Dmitry Gutov on Sat, 8 Oct 2022 21:50:39 +0300) Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> <83zgehe6iq.fsf@gnu.org> <95113379-99d8-eba4-f980-a7fca11430d5@yandex.ru> <834jwfmn5a.fsf@gnu.org> X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: gerd.moellmann@gmail.com, 58158@debbugs.gnu.org, monnier@iro.umontreal.ca X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > Date: Sat, 8 Oct 2022 21:50:39 +0300 > Cc: gerd.moellmann@gmail.com, 58158@debbugs.gnu.org, monnier@iro.umontreal.ca > From: Dmitry Gutov > > > Btw, what am I doing wrong below? > > > > emacs -Q > > C-x C-f src/character.h RET > > M-x visit-tags-table RET RET > > M-. char_string RET > > r whatever RET > > > > Unexpected result: "No suitable matches here". Huh? what did I miss? > > We can't replace over "find definition" matches: they are more abstract > and don't contain the necessary information to perform the replacement > (such as the length of a match, for instance). > > And such xrefs might navigate you to the beginning of the line, for > example, rather than to the beginning of the name. > > But that makes sense, doesn't it? If replacing over "find definitions" > results worked fine, in the end you would get a codebase where all > declarations of a method 'foo' got renamed, but all callsites of it > remain unchanged. That couldn't have been your intention, could it? > > The error message could use some improvement, I suppose, but I'm not > sure how to make it better. I tried to improve the situation, both in the error message, the doc string, and the manual. From debbugs-submit-bounces@debbugs.gnu.org Mon Oct 10 22:12:21 2022 Received: (at 58158) by debbugs.gnu.org; 11 Oct 2022 02:12:21 +0000 Received: from localhost ([127.0.0.1]:50398 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oi4kn-0003mn-7K for submit@debbugs.gnu.org; Mon, 10 Oct 2022 22:12:21 -0400 Received: from mail-wm1-f45.google.com ([209.85.128.45]:39734) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oi4kl-0003ma-0t for 58158@debbugs.gnu.org; Mon, 10 Oct 2022 22:12:19 -0400 Received: by mail-wm1-f45.google.com with SMTP id 8-20020a1c0208000000b003c6c154d528so188635wmc.4 for <58158@debbugs.gnu.org>; Mon, 10 Oct 2022 19:12:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :sender:from:to:cc:subject:date:message-id:reply-to; bh=lBtpSQKNbBuCsG48CYjIJOXtisQ2QMK5oeI+qf4glYk=; b=I6YcONTNHPJ0rO6Zxvq1Z5CsvEpPPf0NUZlrIKZllvP+py7OxubiHT/XTvpQ9VcJaD N0+zKGt+N8uRTx2QkaxRtpaJ2zOEUuXNgyF84P6RhRkFOYqZOZllDMI+Khw0hyKnv7KV EoraaUmk2JAHlXCJRtTdyCHu6/L/7rtMrdiBq/3sFzfu3bFbBBhfSTYSp+NSkeegCa0e pvNc06IUoz5ITrEe/LraCpqo8S+4JaQE13vBW1ws++qZy4zBW0o1IB037sFkt0xkEwTa o46qWwV5wmEcgM2AGH+clVQTVHkpkEQhJcaq2RSmkET5uNVgCXWvxDeD1pGRyhVUBqu3 gwVQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :sender:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=lBtpSQKNbBuCsG48CYjIJOXtisQ2QMK5oeI+qf4glYk=; b=IWbrRI1MOwHqN/HuPnF+8vauU+2Fbs6RJHUD5upyEF4Exgv8o73PxhTesk2aoJ7Bgi iwEYvXmUxWbzidZ5PcVZqk8cT7Fjb4bO0hdywfvmZ4oQPjDzwc0lgI3MwtudEJZOyhMP Ivg557cm0ztSb5fGYhVDfrMnGevWQKOT+LYgEs5a3v1FXoAtP7qZyk88lvSCfiPRxNYd r2GZntGcICRwzSPKhAfPZ1eGPvePo0zepat0zzl8SbxakqFt+YmoCd4tjDJsEqq/EXXM /HMJxMQOAKSrAA4A0ubxPfuOkV0SipbkjKAyHZy5Tt6YfZsIU7s669fLFgJapn85QA4D V4RQ== X-Gm-Message-State: ACrzQf0MshkXhDZ+e0q4QK5x8i/iK04UV2uQqxVB88rCvGRIag5oZwCf R99G/eAStIxvXXvqrgqvhjY= X-Google-Smtp-Source: AMsMyM6anPDUq1efeT/b42TC374ofjGMxMAz8Kb+fKFrXBIkNNh4oSmNSupeAqiL/jBOxJAyMFeWsg== X-Received: by 2002:a05:600c:5112:b0:3c0:eabe:80df with SMTP id o18-20020a05600c511200b003c0eabe80dfmr18355177wms.65.1665454332912; Mon, 10 Oct 2022 19:12:12 -0700 (PDT) Received: from [192.168.0.6] ([46.251.119.176]) by smtp.googlemail.com with ESMTPSA id ck15-20020a5d5e8f000000b0022afe4fb459sm10366880wrb.51.2022.10.10.19.12.12 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 10 Oct 2022 19:12:12 -0700 (PDT) Message-ID: Date: Tue, 11 Oct 2022 05:12:11 +0300 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.2.2 Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Content-Language: en-US To: Eli Zaretskii References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> <83zgehe6iq.fsf@gnu.org> <95113379-99d8-eba4-f980-a7fca11430d5@yandex.ru> <834jwfmn5a.fsf@gnu.org> <838rlohzeo.fsf@gnu.org> From: Dmitry Gutov In-Reply-To: <838rlohzeo.fsf@gnu.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -0.3 (/) X-Debbugs-Envelope-To: 58158 Cc: gerd.moellmann@gmail.com, 58158@debbugs.gnu.org, monnier@iro.umontreal.ca X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) On 10.10.2022 11:10, Eli Zaretskii wrote: >> Date: Sat, 8 Oct 2022 21:50:39 +0300 >> Cc:gerd.moellmann@gmail.com,58158@debbugs.gnu.org,monnier@iro.umontreal.ca >> From: Dmitry Gutov >> >>> Btw, what am I doing wrong below? >>> >>> emacs -Q >>> C-x C-f src/character.h RET >>> M-x visit-tags-table RET RET >>> M-. char_string RET >>> r whatever RET >>> >>> Unexpected result: "No suitable matches here". Huh? what did I miss? >> We can't replace over "find definition" matches: they are more abstract >> and don't contain the necessary information to perform the replacement >> (such as the length of a match, for instance). >> >> And such xrefs might navigate you to the beginning of the line, for >> example, rather than to the beginning of the name. >> >> But that makes sense, doesn't it? If replacing over "find definitions" >> results worked fine, in the end you would get a codebase where all >> declarations of a method 'foo' got renamed, but all callsites of it >> remain unchanged. That couldn't have been your intention, could it? >> >> The error message could use some improvement, I suppose, but I'm not >> sure how to make it better. > I tried to improve the situation, both in the error message, the doc > string, and the manual. It's probably better now, but still likely confusing. What is a "subset of matches"? The user makes a search, gets a bunch of matches. Is it fair to call them "only a subset" is the user only searched for definitions? Or to take another example, the user can search for some regexp inside a particular directly, with dired-do-find-regexp. Imagine that that directory is not the whole project (perhaps just a minor subdirectory). Would it be fair to call the results "only a subset" then? But xref-query-replace-in-results will work in that case, because the search returns values which have enough info to perform the replacements. Perhaps we should make the error very specific, like "you can't replace inside xref-find-definitions results". Since that is going to be the exception in like 99.9% of the cases. It's possible for other backend commands (such as find-references) to return unsuitable xref values in third-party backends, or for other code to use xref-show-xrefs with such, but those will be really very rare, if happen at all. From debbugs-submit-bounces@debbugs.gnu.org Tue Oct 11 02:37:39 2022 Received: (at 58158) by debbugs.gnu.org; 11 Oct 2022 06:37:39 +0000 Received: from localhost ([127.0.0.1]:50674 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oi8tW-0006f1-Um for submit@debbugs.gnu.org; Tue, 11 Oct 2022 02:37:39 -0400 Received: from eggs.gnu.org ([209.51.188.92]:45542) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oi8tU-0006em-HV for 58158@debbugs.gnu.org; Tue, 11 Oct 2022 02:37:37 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:53604) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oi8tO-0002NE-Ia; Tue, 11 Oct 2022 02:37:31 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=References:Subject:In-Reply-To:To:From:Date: mime-version; bh=DQIqHeBUjpgCC4mRKsjj2Hm+KYWl2QHtkDyCaX7iX0E=; b=dUVpeFRUgVhX +Dnhy4cJh37aoXLVDyRgaUP5q0doSlvzagHcLeV4XEncb3/2F5umkDykn35KGFI/jtz3Xi5nn/WYO OkjplbA2odQ6IT3PuH30xWeS+n4Ip20WkfThn88Zvw47JYI0XFsQXDSFDZHNpLTHLXv90z1nn4l0I TJ2IUyYu98Ltav242EsB4D80JazPXuM1yMr8nV1Dw3CzdO7HiBcsXku9T45oWcWTcoDtsCF/YlfIi YyjzEw7pMbbWYE4WsO7Bq4D6tSQ6e8U0Gx/tOLHYcAAoXp/dbOQWsmdvrI3kcaWGOiDmw/mJASx0+ 5A0P1FddUV4M/8QwwMhWQA==; Received: from [87.69.77.57] (port=4960 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oi8tO-0005bS-1i; Tue, 11 Oct 2022 02:37:30 -0400 Date: Tue, 11 Oct 2022 09:37:38 +0300 Message-Id: <83mta2g91p.fsf@gnu.org> From: Eli Zaretskii To: Dmitry Gutov In-Reply-To: (message from Dmitry Gutov on Tue, 11 Oct 2022 05:12:11 +0300) Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> <83zgehe6iq.fsf@gnu.org> <95113379-99d8-eba4-f980-a7fca11430d5@yandex.ru> <834jwfmn5a.fsf@gnu.org> <838rlohzeo.fsf@gnu.org> X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 58158 Cc: gerd.moellmann@gmail.com, 58158@debbugs.gnu.org, monnier@iro.umontreal.ca X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > Date: Tue, 11 Oct 2022 05:12:11 +0300 > Cc: gerd.moellmann@gmail.com, 58158@debbugs.gnu.org, monnier@iro.umontreal.ca > From: Dmitry Gutov > > What is a "subset of matches"? Feel free to suggest a less vague description. The idea is that the list in Xref buffer doesn't show all the references to the identifier, making renaming infeasible. > Perhaps we should make the error very specific, like "you can't replace > inside xref-find-definitions results". Since that is going to be the > exception in like 99.9% of the cases. That'd be my preference, but what are those 0.1% of cases where the Xref buffer produced by other commands could fit? More generally, what exactly does xref.el test to produce the error message, and how to describe that in user-level terms? > It's possible for other backend commands (such as find-references) to > return unsuitable xref values in third-party backends, or for other code > to use xref-show-xrefs with such, but those will be really very rare, if > happen at all. You are saying that 'r' is only useful after M-?, is that right? The manual says so, but the manual doesn't have to say "the whole truth". The doc string should. From debbugs-submit-bounces@debbugs.gnu.org Fri Oct 06 09:15:11 2023 Received: (at 58158) by debbugs.gnu.org; 6 Oct 2023 13:15:11 +0000 Received: from localhost ([127.0.0.1]:49443 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qokfe-0001eV-Rj for submit@debbugs.gnu.org; Fri, 06 Oct 2023 09:15:11 -0400 Received: from mail-wm1-x32e.google.com ([2a00:1450:4864:20::32e]:53698) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qokfd-0001Fv-3q for 58158@debbugs.gnu.org; Fri, 06 Oct 2023 09:15:09 -0400 Received: by mail-wm1-x32e.google.com with SMTP id 5b1f17b1804b1-4053c6f0db8so18799835e9.3 for <58158@debbugs.gnu.org>; Fri, 06 Oct 2023 06:14:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1696598084; x=1697202884; darn=debbugs.gnu.org; h=content-transfer-encoding:mime-version:user-agent:message-id:date :references:in-reply-to:subject:to:from:from:to:cc:subject:date :message-id:reply-to; bh=oStGSFJfWEKRSHUs4cf6ccqX+5vW5UkpwCZ0hhbnFjM=; b=jd/RzM2eTBvs85fED7nrFVFo39xFwk3+zKMxXbVyn3A9pf0RhotlZpRVCieU/NVLSD uXW44wo326uYt1AYzYXiHlPyu585UI9sjLKAE1z9TGYywf7JEYhfF5StYNIUlcxLJ2Wf Ufnp5C4oazfUmoWlAC2K3BVhHsOtGX8uJZ8aYr3Doarl3UU4QfHOl7a+GFpZLgpVflxB cfhqHj8A6PviPtyfSVGd0W2qFjw6BmSBNTsDSXUTAEZKlHfwLpwEHXV5kUDbcMIYS8ef I/6QL6lf24tai6SoOEcJr1P61pVpQCkbD+QgUW4+bXtVyeCG8fAeKA+ulllX8hLbl/96 dyRA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696598084; x=1697202884; h=content-transfer-encoding:mime-version:user-agent:message-id:date :references:in-reply-to:subject:to:from:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=oStGSFJfWEKRSHUs4cf6ccqX+5vW5UkpwCZ0hhbnFjM=; b=FGgXpRsdU8IhGnFNuSUkrzWgn/gXPw3VJRe4DVDX1QoQvKVoqraLYH5UcMaxNYSYKv d19RlS5//xBs+8nUX69ojmA3dFu7xt/ndshar0pttnry44S0WhhXjnyQhNsDQKl/beAm EGdF4MJVtV7A5j0aOhRiKX+v0C56iqzwMJNc143bzVHpMaPeKe7FqynGCvUi44ff8SAj SObEoR1QUp1lDfO6qirpUDlH+1waweu/SHa2UqKGdFuzntbyKFvh+JEsZZBC/8oq7yyJ zWDr4BaTGTq5ox3fVxSo0vltqi9hA8hCxnX2MUR6CGg8mwsCrt3ph2mssdKpDnNV3zPo DF6w== X-Gm-Message-State: AOJu0YxrLzRX7dmb/RKAWkO3VbYLVmszoSwlHnHAF8Rta5hgmiM8XC6U Iw8ZXMDClgpGFi9p9QirKwmM/0vgiGw= X-Google-Smtp-Source: AGHT+IHIBaiSHIwAI3lHHquG94CxYHSsWty4J5LERJuPl+NCghhM/EYx3rAr8YPlXbqKhQ3GHMYlTA== X-Received: by 2002:a1c:ed17:0:b0:404:7480:d821 with SMTP id l23-20020a1ced17000000b004047480d821mr7310949wmh.37.1696598083930; Fri, 06 Oct 2023 06:14:43 -0700 (PDT) Received: from Pro.fritz.box (pd9e36179.dip0.t-ipconnect.de. [217.227.97.121]) by smtp.gmail.com with ESMTPSA id hn32-20020a05600ca3a000b004053e9276easm5988827wmb.32.2023.10.06.06.14.43 for <58158@debbugs.gnu.org> (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 06 Oct 2023 06:14:43 -0700 (PDT) From: =?utf-8?Q?Gerd_M=C3=B6llmann?= To: 58158@debbugs.gnu.org Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful In-Reply-To: ("Gerd =?utf-8?Q?M=C3=B6llman?= =?utf-8?Q?n=22's?= message of "Thu, 29 Sep 2022 07:29:25 +0200") References: Date: Fri, 06 Oct 2023 15:14:42 +0200 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 58158 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) Gerd M=C3=B6llmann writes: > In its current form, interval tree iteration works like this: > > 1. Call begin_iteration(T) to iterate over tree T > 2. do stuff > 3. Call end_iteration(T) > > with the following rules: > > - Begin_iteration and end_iteration must be paired. > > - There can be only one iteration per tree at a time. Nested iteration > over the same tree is not supported (abort). > > - No GC may happen in step 2. This is because mark_buffer iterates over > buffer overlays. > > I think this is an exceedingly dangerous design. Time has passed, and I think this is no longer relevant. I'm therefore closing this bug. From debbugs-submit-bounces@debbugs.gnu.org Fri Oct 06 09:15:17 2023 Received: (at control) by debbugs.gnu.org; 6 Oct 2023 13:15:17 +0000 Received: from localhost ([127.0.0.1]:49446 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qokfl-0001xb-6G for submit@debbugs.gnu.org; Fri, 06 Oct 2023 09:15:17 -0400 Received: from mail-wr1-x432.google.com ([2a00:1450:4864:20::432]:51257) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qokfj-0001dR-RG for control@debbugs.gnu.org; Fri, 06 Oct 2023 09:15:16 -0400 Received: by mail-wr1-x432.google.com with SMTP id ffacd0b85a97d-3296b3f03e5so400456f8f.2 for ; Fri, 06 Oct 2023 06:14:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1696598091; x=1697202891; darn=debbugs.gnu.org; h=content-transfer-encoding:mime-version:subject:from:to:message-id :date:from:to:cc:subject:date:message-id:reply-to; bh=+En2EQVoOzgxaAd46vgzDnorAItYwhZCouiY+Qz0qn4=; b=O0ExucFFNb1WeBqGSnKTAwjkXYC19uoCkmTDpGuhgRi11ValJQpUmsjC2jaFPckc5a zWPSYfpypy44oUxlEdJaT2Ay1uY+0InQvGhhjqHmTPXZWRZUKbXaKC2THkSYDEko2DYP INe8H0V42NHOCGkYswNvL//MBinUxs0TV1I20foXxMmDpymHcGw2/+KVmmMQcCluPfI8 XDxMsgKT7P+8AXRd6CxXFNdLogUnLHj7OvVWAJtfNBffbNrq2TVvctntME5uoOCZlwp6 H5HafHf4ZwtUyuA2V4roO4/YF0p+4gUMRvLJi2KN+Sayzjd/sMFhFbChujbamssEzv29 IV9w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696598091; x=1697202891; h=content-transfer-encoding:mime-version:subject:from:to:message-id :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=+En2EQVoOzgxaAd46vgzDnorAItYwhZCouiY+Qz0qn4=; b=cv6CwCU9onpuB80uLsmW2pssReDwH5tVHmjeJ970JbZanSF9QQH2qmljMXtZxlxDju B6eififgTILptKHoFMi/LwAVrkgTF515AqCyDU/4MK2uu8Ap7o0mfjpFwxDRprnQTGUc a3PFQpjIE3NBmLbo4KU7vA8alBzPHdtYUExZxb17n7yIuXf/a7kofSMDBkvjXcxjzHrk 5DfQ6JdKXwlJfpJpYr4g9TW+RBia/PMR9Kubilg4G4f/+1jwV7Dtr4xHJJ7/98QgAKpg 5K55IOM0m0ugK+VVVeuU9tzw/xKMVDRcDNuGTmoGiek19GQ0mYp3yrxVvPDLteARaUY5 54aQ== X-Gm-Message-State: AOJu0YwqqjQcA+R+bBJ2xyMzkn0byOIxQwefz3YzhuX7Z0T3nJ19ELRo UZjxIfSHLp20Ol2K5wGkyX7E/QhVC8Q= X-Google-Smtp-Source: AGHT+IE07hLIOj5b22jo40Fi0KbdJ8+/E/B57VVuhlcz7o7EXznUpWGCMv3E4FDHIRhTdiasb0kV+w== X-Received: by 2002:adf:ed10:0:b0:313:f783:262b with SMTP id a16-20020adfed10000000b00313f783262bmr7443572wro.26.1696598090940; Fri, 06 Oct 2023 06:14:50 -0700 (PDT) Received: from Pro.fritz.box (pd9e36179.dip0.t-ipconnect.de. [217.227.97.121]) by smtp.gmail.com with ESMTPSA id t25-20020a1c7719000000b004065daba6casm6004469wmi.46.2023.10.06.06.14.50 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 06 Oct 2023 06:14:50 -0700 (PDT) Date: Fri, 06 Oct 2023 15:14:49 +0200 Message-Id: To: control@debbugs.gnu.org From: =?utf-8?Q?Gerd_M=C3=B6llmann?= Subject: control message for bug #58158 MIME-version: 1.0 Content-type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: control X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) close 58158 30.1 quit From unknown Wed Sep 10 12:14:41 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Sat, 04 Nov 2023 11:24:05 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator