Re: Overlays as an AA-tree

[Joakim Jalap <joakim.jalap@fastmail.com>]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

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

Do you mean when a->char_start == b->char_start && a->char_end ==
b->char_end?

Does it even matter what char_end is? I have a feeling it's ok to just
return true if a->char_start == b->char_end.

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

Actually, this sounds like it could be quite complicated... I'm not sure
how to handle that in the tree.

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

Hm, I don't really understand this. Do you mean how LENGTH(i) is
computed from TOTAL_LENGTH(i->left) and TOTAL_LENGTH(i->right)? Hm, how
could I do that in the AA-tree? Store the position in the root and then
an offset from the parent in every child node?

But doing it like I do it now (updating all the char-positions after the
modification) shouldn't be slower than updating the positions of all
markers, right?

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

I just commited with --no-verify instead :)