Re: Overlays as an AA-tree

[Joakim Jalap]

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