[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Overlays as an AA-tree
From: |
Joakim Jalap |
Subject: |
Re: Overlays as an AA-tree |
Date: |
Thu, 22 Sep 2016 12:35:29 +0200 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/25.1.50 (gnu/linux) |
Stefan Monnier <address@hidden> writes:
Thanks for looking at this! It is, after all, your idea :)
> Could you describe how you use this tree? An AA-tree is indexed by
> a single "number", whereas overlays have two independent "numbers".
> So how to use this AA-tree to implement an *interval* tree?
See below.
> This should be documented in the code. E.g. the "struct Lisp_Overlay"
> should define very clearly the meaning of char_start, char_end, left,
> and right (i.e. which overlays go to the left, and which go to the
> right).
>
> While looking for an answer in the text I found:
>
> /* This function determines where overlays are inserted in the tree.
> FIXME: I didn't think too hard about this...
> */
>
> which makes me suspect your design might not be quite right.
Well, I didn't think *too* hard about it. I didn't really think about
what to do when the intervals of two overlays are the same. Does it even
matter? I have a feeling that if I want to insert an overlay which
starts at the same place as another, it could just be inserted to the
left of the latter. Is that correct?
> Have you read https://en.wikipedia.org/wiki/Interval_tree ?
Yes. Well, I tried to anyway.
> [ BTW, our convention is to put the "*/" at the end of the last line
> rather than alone on the next line. ]
Got it. I'll fix that.
> This said, reading overlay_tree_insert_internal, I have the impression
> that you're implementing what wikipedia describes as an "Augmented tree"
> where the basic tree is your AA-tree, indexed by the left position of
> the overlays, with the `max` field being the "augmented" data, which
> sounds just fine.
> Is that right?
That is exactly right.
> The only places you absolutely need to replace are all the places that
> need to modify the tree. There shouldn't be that many of them
> (basically, make-overlay, move-overlay, delete-overlay, plus text
> insertion/deletion).
> Then the rest can be modified little by little.
I think I ran into some other subtle things. For example an overlay can
be in "no buffer" if both it's markers were detached from their buffer,
I think. So in the case of the overlay tree, I need to detect this and
remove the overlay from the buffers tree.
> Some tricky parts:
> - because of the insertion_type, two overlays may start with end1<end2
> and finish with end1>end2 without any call to move-overlay.
Hm, ok. I will have to look into this further.
> - the overlay tree needs to be "weak" (i.e. we'll need to add special
> code in the GC).
I don't really understand what this means. Could you please elaborate? I
was hoping it would work with the current marking and sweeping.
> I wouldn't worry about merging (better yet: merge from master right away
> and then keep doing that on a regular basis, which should be easy since
> I don't think we've touched (nor will touch) this code very much).
I tried to do that yesterday. There were some conflicts in insdel.c
(which I think I fixed) but now I can't commit, because 'git commit'
complains about trailing whitespace in some regex test files. How do I
get around this?
> AFAIK, the byte-position of markers is used, but the byte-position of
> overlays isn't, so you should be able to get rid of them.
That's great!
Thanks.
-- Joakim
- Re: Overlays as an AA-tree, (continued)
Re: Overlays as an AA-tree, Stefan Monnier, 2016/09/21
Re: Overlays as an AA-tree,
Joakim Jalap <=
- Re: Overlays as an AA-tree, Stefan Monnier, 2016/09/22
- Re: Overlays as an AA-tree, Joakim Jalap, 2016/09/22
- Re: Overlays as an AA-tree, Stefan Monnier, 2016/09/22
- Re: Overlays as an AA-tree, Joakim Jalap, 2016/09/27
- Re: Overlays as an AA-tree, Stefan Monnier, 2016/09/27
- Re: Overlays as an AA-tree, Eli Zaretskii, 2016/09/27
- Re: Overlays as an AA-tree, Joakim Jalap, 2016/09/28