Re: Overlays as an AA-tree

[Stefan Monnier <monnier@iro.umontreal.ca>]

>> 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?

Not much, no.  Do note that in compare_overlays, we do need a total ordering
(this is used for sort_overlays).  Your sorting and that of
compare_overlays can't be identical (compare_overlays has to obey the
`priority` property, whereas yours shouldn't pay attention to it), but
you can still use the same idea: i.e. when start and end are equal, just
use the overlays's memory addresses to decide which comes first.

>> 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.

Great.

>> 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.

The user doesn't have direct access to the markers, so IIUC this
situation happens through delete-overlay or move-overlay.

> So in the case of the overlay tree, I need to detect this and
> remove the overlay from the buffers tree.

Similarly, move-overlay can necessitate moving the overlay from one tree
to another.

>> 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.

I think a more important aspect is that insertion/deletion of text has
to update all char-positions of overlays after the point of
insertion/deletion.  I.e. it's an O(n) operation.  In the intervals tree
used for text-properties we avoid this by keeping track of distances
rather than positions. and then positions get (re)computed when needed.

>> - 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.

Hmm... forget it, I was confused.

>> 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?

Just remove the trailing whitespace.


        Stefan