GNU bug report logs - #58158
29.0.50; [overlay] Interval tree iteration considered harmful

Previous Next

Package: emacs;

Reported by: Gerd Möllmann <gerd.moellmann <at> gmail.com>

Date: Thu, 29 Sep 2022 05:30:02 UTC

Severity: normal

Found in version 29.0.50

Fixed in version 30.1

Done: Gerd Möllmann <gerd.moellmann <at> gmail.com>

Bug is archived. No further changes may be made.

Full log

Message #116 received at 58158 <at> debbugs.gnu.org (full text, mbox):

From: Andreas Politz <mail <at> andreas-politz.de>
To: Gerd Möllmann <gerd.moellmann <at> gmail.com>
Cc: Eli Zaretskii <eliz <at> gnu.org>, 58158 <at> debbugs.gnu.org,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#58158: 29.0.50;
 [overlay] Interval tree iteration considered harmful
Date: Tue, 4 Oct 2022 12:50:54 +0200

My implementation seems to work. The correctness of the algorithm would follow from 

1. The Rb tree algorithm produces a tree with left <= root <= right,
2. the algorithm you’ve posted, and I’ve  adapted, produces an in–order of the tree and
3. the conditions guiding the traversal are correct, i.e. they don’t exclude matching intervals.

Since I believe these statements are true, I believe the algorithm is correct.

Andreas



> Am 03.10.2022 um 06:35 schrieb Gerd Möllmann <gerd.moellmann <at> gmail.com>:
> 
> Andreas Politz <mail <at> andreas-politz.de> 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,
This bug report was last modified 1 year and 311 days ago.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.