Re: Overlays as an AA-tree

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

Andreas Politz <politza@hochschule-trier.de> writes:

> Hi, I'm interested in this problem as well.

Great!

I thought I might chime in since I've been bashing my head againt this
for a while now :)

> I want to clarify something:
>
> Overlays have begin B and end E positions each with a flag (front-advance
> resp. rear-advance).  These positions may change in one of 3 ways:
>
> 1. move-overlay is called
> 2. Text of length L is inserted at position P.
>    Here the flags decide whether begin B resp. end E will move or not
>    in the literal border-cases P = B resp. P = E .
> 3. Text of length L is deleted beginning at position P.

There is also the case of a replace, conceptually I guess it's similar
to a delete or an insert, but in the code it is handled separately.
Interestingly, in the case of a replace, we don't look at the insertion type.

> Is this the correct model ?  Someone mentioned in a different thread,
> that occasionally we may have B > E.  How does this happen ?

I think it happens in case 2 above, when B = E = P, and we have
front-advance = t and read-advance = nil. Then B will move but E will
not, so we end up with a negative size overlay. See also the comments at
adjust_markers_for_insert in insdel.c and fix_start_end_in_overlays in
buffer.c.

> ---
>
> I think if a tree is sorted by begin only and the front-advance of
> every node is either true or false, the tree can't possibly become
> disordered by insertion/deletion operations.  Further the disorder
> exists at most for nodes having the same begin but different
> front-advances after an insert at begin was performed.

But if the tree is sorted by begin only we can have multiple overlays in
the same position, how does that work? A linked list of all overlays
starting at that position? I toyed with the idea, but I haven't actually
tried it.

For reference, the last case I got stuck on was byte compiling
lisp/semantic/cpp.el, where there are a bunch overlays (26 I believe) at
different positions, but then almost all the buffer text is deleted so
that every overlay ends up being from 6 to 6! 

> This suggests using two trees or at least limits the amount of nodes
> having to be reinserted after a change.

Hm I don't understand this. How would we use two trees?
>
> Anyway, my attempt is to use the RB-tree from alloc.c and add some
> node-attributes:
>
> 1. max_end :: Holds the maximum E value of this node's sub-tree and
> bounds the complexity of queries in terms of their result, i.e. number
> of intervals. (The so called ,,Augmented Tree'' approach to Interval
> Trees (which is actually just an example for how to augment a tree in
> the book).)
>
> 2. offset :: The amount of shift of this node's sub-tree relative to
> its parent and applying to all position values (begin,end,max_end).
> This should limit the time it takes to modify the tree after an
> insertion/deletion in terms of intersecting intervals.

I was going to do this too (but left that for later as I have bigger
problems right now :)). The problem here is that you have to take the
insertion_type into account, so an overlay may or may not change as the
result of an insertion. Actually maybe that isn't a problem since it
only affects those overlays with an endpoint exactly at the point of
insertion... This whole thing makes me dizzy...

> 3. modified_tick :: Essentially just a flag, indicating that all
> parent offsets have been applied to this node.  This would allow for
> constant time access on B/E for repeated accesses.
>
> I'm essentially building an overlay model and if it works, will try to
> plug it into the Editor.

Sounds like a good idea. Let's hope you have better luck (or skill) than
me :)

> -ap

-- Joakim