all messages for Emacs-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
From: "Gerd Möllmann" <gerd.moellmann@gmail.com>
To: Stefan Monnier <monnier@iro.umontreal.ca>
Cc: Eli Zaretskii <eliz@gnu.org>,
	Andreas Politz <mail@andreas-politz.de>,
	58158@debbugs.gnu.org
Subject: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful
Date: Sat, 01 Oct 2022 09:25:47 +0200	[thread overview]
Message-ID: <m24jwo2ef8.fsf@Mini.fritz.box> (raw)
In-Reply-To: <jwvy1u07w2n.fsf-monnier+emacs@gnu.org> (Stefan Monnier's message of "Fri, 30 Sep 2022 11:25:30 -0400")

Stefan Monnier <monnier@iro.umontreal.ca> 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 <mail@andreas-politz.de>.  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-<left is <= and
> 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.





  parent reply	other threads:[~2022-10-01  7:25 UTC|newest]

Thread overview: 68+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-09-29  5:29 bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Gerd Möllmann
2022-09-29  6:28 ` Eli Zaretskii
2022-09-29  7:03   ` Gerd Möllmann
2022-09-29  8:08     ` Eli Zaretskii
2022-09-29  9:09       ` Gerd Möllmann
2022-09-29  9:37         ` Eli Zaretskii
2022-09-29 10:05           ` Gerd Möllmann
2022-09-29 10:43             ` Eli Zaretskii
2022-09-29 11:33               ` Gerd Möllmann
2022-09-29 13:10               ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-29 13:23                 ` Eli Zaretskii
2022-09-29 16:48                   ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-29 13:40                 ` Eli Zaretskii
2022-09-29 14:15                 ` Gerd Möllmann
2022-09-29 14:37                   ` Gerd Möllmann
2022-09-29 22:09                     ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-30  5:28                       ` Gerd Möllmann
2022-09-30  6:11                         ` Eli Zaretskii
2022-09-30 11:31                           ` Gerd Möllmann
2022-09-30 18:29                             ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-02  8:06                               ` Gerd Möllmann
2022-10-06 22:36                           ` Dmitry Gutov
2022-10-07 19:47                             ` Eli Zaretskii
2022-10-08 18:50                               ` Dmitry Gutov
2022-10-10  8:10                                 ` Eli Zaretskii
2022-10-11  2:12                                   ` Dmitry Gutov
2022-10-11  6:37                                     ` Eli Zaretskii
2022-10-11 11:36                                       ` xref-query-replace-in-results error message after xref-find-definitions, was: " Dmitry Gutov
2022-10-11 11:51                                         ` Eli Zaretskii
2022-10-11 12:10                                           ` Dmitry Gutov
2022-10-11 12:17                                             ` Eli Zaretskii
2022-10-11 12:44                                               ` Dmitry Gutov
2022-10-11 12:55                                                 ` Eli Zaretskii
2022-10-11 14:55                                                   ` Dmitry Gutov
2022-10-11 16:01                                                     ` Eli Zaretskii
2022-10-11 16:41                                                       ` Dmitry Gutov
2022-10-11 16:50                                                         ` Eli Zaretskii
2022-10-11 20:31                                                           ` Dmitry Gutov
2022-10-12  5:17                                                             ` Eli Zaretskii
2022-10-12 10:06                                                               ` John Yates
2022-10-12 10:17                                                                 ` Eli Zaretskii
     [not found]                                                                   ` <CAJnXXogKsM=gMTFi2NivDMHW4A3EBtBtsNDBV3o5vcu2xXfuvw@mail.gmail.com>
2022-10-12 13:21                                                                     ` Eli Zaretskii
2022-10-12 16:12                                                                       ` John Yates
2022-10-12 13:47                                                               ` Dmitry Gutov
2022-10-12 14:05                                                                 ` Eli Zaretskii
2022-10-11 14:04                                           ` Stefan Monnier
2022-10-11 14:07                                             ` Stefan Monnier
2022-10-11 15:07                                               ` Dmitry Gutov
2022-10-11 15:37                                             ` Eli Zaretskii
2022-09-30 13:25                         ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-30 14:08                           ` Gerd Möllmann
2022-09-30 15:25                             ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-30 16:04                               ` Eli Zaretskii
2022-09-30 17:11                                 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-01  5:06                               ` Gerd Möllmann
2022-10-01 13:54                                 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-02  8:22                                   ` Gerd Möllmann
2022-10-02 16:32                                     ` Andreas Politz
2022-10-03  4:35                                       ` Gerd Möllmann
2022-10-04 10:50                                         ` Andreas Politz
2022-10-01  7:25                               ` Gerd Möllmann [this message]
2022-10-01 10:55                                 ` Gerd Möllmann
2022-10-01 14:01                                 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-29 16:40                   ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-01  1:57         ` Richard Stallman
2022-10-01  7:00           ` Eli Zaretskii
2022-10-06 22:26 ` Matt Armstrong
2023-10-06 13:14 ` Gerd Möllmann

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=m24jwo2ef8.fsf@Mini.fritz.box \
    --to=gerd.moellmann@gmail.com \
    --cc=58158@debbugs.gnu.org \
    --cc=eliz@gnu.org \
    --cc=mail@andreas-politz.de \
    --cc=monnier@iro.umontreal.ca \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this external index

	https://git.savannah.gnu.org/cgit/emacs.git
	https://git.savannah.gnu.org/cgit/emacs/org-mode.git

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.